A registry service is described which uses a partitioned publisher assertion recording and accessing scheme. A publisher assertion regarding a relationship between entities (e.g., business or other types of entities) is encoded within a directory information tree in a memory. The publisher assertion includes publisher assertion part nodes corresponding to entity nodes in the directory information tree. The publisher assertion is complete if all publisher assertion parts corresponding to entities in the relationship are present in the directory information tree. The service may include a network including directory servers and registry servers. The publisher assertions are manipulated by authorized publishers and accessed by users using a variety of techniques, the operations of which are performed by such parties and/or are encoded upon computer-readable media.