zc.relation 2.0

Overview

The relation catalog can be used to optimize intransitive and transitive searches for N-ary relations of finite, preset dimensions.

For example, you can index simple two-way relations, like employee to supervisor; RDF-style triples of subject-predicate-object; and more complex relations such as subject-predicate-object with context and state. These can be searched with variable definitions of transitive behavior.

The catalog can be used in the ZODB or standalone. It is a generic, relatively policy-free tool.

It is expected to be used usually as an engine for more specialized and constrained tools and APIs. Three such tools are zc.relationship containers, plone.relations containers, and zc.vault. The documents in the package, including this one, describe other possible uses.

History

This is a refactoring of the ZODB-only parts of the zc.relationship package. Specifically, the zc.relation catalog is largely equivalent to the zc.relationship index. The index in the zc.relationship 2.x line is an almost-completely backwards-compatible wrapper of the zc.relation catalog. zc.relationship will continue to be maintained, though active development is expected to go into zc.relation.

Many of the ideas come from discussions with and code from Casey Duncan, Tres Seaver, Ken Manheimer, and more.

Setting Up a Relation Catalog

In this section, we will be introducing the following ideas.

• Relations are objects with indexed values.

• You add value indexes to relation catalogs to be able to search. Values can be identified to the catalog with callables or interface elements. The indexed value must be specified to the catalog as a single value or a collection.

• Relations and their values are stored in the catalog as tokens: unique identifiers that you can resolve back to the original value. Integers are the most efficient tokens, but others can work fine too.

• Token type determines the BTree module needed.

• You must define your own functions for tokenizing and resolving tokens. These functions are registered with the catalog for the relations and for each of their value indexes.

• Relations are indexed with index.

We will use a simple two way relation as our example here. A brief introduction to a more complex RDF-style subject-predicate-object set up can be found later in the document.

            Alice
         __/     \__
    Betty           Chuck
    /   \           /   \
Diane   Edgar   Frank   Galyn
  |
Howie

Searching

In this section, we will introduce the following ideas.

• Queries to the relation catalog are formed with dicts.

• Query keys are the names of the indexes you want to search, or, for the special case of precise relations, the zc.relation.RELATION constant.

• Query values are the tokens of the results you want to match; or None, indicating relations that have None as a value (or an empty collection, if it is a multiple). Search values can use zc.relation.catalog.any(args) or zc.relation.catalog.Any(args) to specify multiple (non-None) results to match for a given key.

• The index has a variety of methods to help you work with tokens. tokenizeQuery is typically the most used, though others are available.

• To find relations that match a query, use findRelations or findRelationTokens.

• To find values that match a query, use findValues or findValueTokens.

• You search transitively by using a query factory. The zc.relation.queryfactory.TransposingTransitive is a good common case factory that lets you walk up and down a hierarchy. A query factory can be passed in as an argument to search methods as a queryFactory, or installed as a default behavior using addDefaultQueryFactory.

• To find how a query is related, use findRelationChains or findRelationTokenChains.

• To find out if a query is related, use canFind.

• Circular transitive relations are handled to prevent infinite loops. They are identified in findRelationChains and findRelationTokenChains with a zc.relation.interfaces.ICircularRelationPath marker interface.

• search methods share the following arguments:

  • maxDepth, limiting the transitive depth for searches;

  • filter, allowing code to filter transitive paths;

  • targetQuery, allowing a query to filter transitive paths on the basis of the endpoint;

  • targetFilter, allowing code to filter transitive paths on the basis of the endpoint; and

  • queryFactory, mentioned above.

• You can set up search indexes to speed up specific transitive searches.

      ______
     /      \
    /     Zane
   /        |
  /       Alice
 /     __/     \__
/ Betty__         Chuck
\-/  /   \         /   \
   Diane Edgar Frank   Galyn
    |
  Howie

Working with More Complex Relations

So far, our examples have used a simple relation, in which the indexed object is one end of the relation, and the indexed value on the object is the other. This example has let us look at all of the basic zc.relation catalog functionality.

As mentioned in the introduction, though, the catalog supports, and was designed for, more complex relations. This section will quickly examine a few examples of other uses.

In this section, we will see several examples of ideas mentioned above but not yet demonstrated.

• We can use interface attributes (values or callables) to define value indexes.

• Using interface attributes will cause an attempt to adapt the relation if it does not already provide the interface.

• We can use the multiple argument when defining a value index to indicate that the indexed value is a collection.

• We can use the name argument when defining a value index to specify the name to be used in queries, rather than relying on the name of the interface attribute or callable.

• The family argument in instantiating the catalog lets you change the default btree family for relations and value indexes from BTrees.family32.IF to BTrees.family64.IF.

Karyn   Lee
     \ /
    Jacob   Iphigenia
         \ /
        Gertrude    Harry
                \  /
             /-------\
         Fred        Eugenia
           Donald   /     \    Charles
                 \ /       \  /
                Betty      Alice

Additional Functionality

This section introduces peripheral functionality. We will learn the following.

• Listeners can be registered in the catalog. They are alerted when a relation is added, modified, or removed; and when the catalog is cleared and copied (see below).

• The clear method clears the relations in the catalog.

• The copy method makes a copy of the current catalog by copying internal data structures, rather than reindexing the relations, which can be a significant optimization opportunity. This copies value indexes and search indexes; and gives listeners an opportunity to specify what, if anything, should be included in the new copy.

• The ignoreSearchIndex argument to the five pertinent search methods causes the search to ignore search indexes, even if there is an appropriate one.

• findRelationTokens() (without arguments) returns the BTree set of all relation tokens in the catalog.

• findValueTokens(INDEX_NAME) (where “INDEX_NAME” should be replaced with an index name) returns the BTree set of all value tokens in the catalog for the given index name.

Conclusion

Introduction and Set Up

This document assumes you have read the introductory README.rst and want to learn a bit more by example. In it, we will explore a more complicated set of relations that demonstrates most of the aspects of working with tokens. In particular, we will look at joins, which will also give us a chance to look more in depth at query factories and search indexes, and introduce the idea of listeners. It will not explain the basics that the README already addressed.

Imagine we are indexing security assertions in a system. In this system, users may have roles within an organization. Each organization may have multiple child organizations and may have a single parent organization. A user with a role in a parent organization will have the same role in all transitively connected child relations.

We have two kinds of relations, then. One kind of relation will model the hierarchy of organizations. We’ll do it with an intrinsic relation of organizations to their children: that reflects the fact that parent organizations choose and are comprised of their children; children do not choose their parents.

The other relation will model the (multiple) roles a (single) user has in a (single) organization. This relation will be entirely extrinsic.

We could create two catalogs, one for each type. Or we could put them both in the same catalog. Initially, we’ll go with the single-catalog approach for our examples. This single catalog, then, will be indexing a heterogeneous collection of relations.

Let’s define the two relations with interfaces. We’ll include one accessor, getOrganization, largely to show how to handle methods.

>>> import zope.interface
>>> class IOrganization(zope.interface.Interface):
...     title = zope.interface.Attribute('the title')
...     parts = zope.interface.Attribute(
...         'the organizations that make up this one')
...
>>> class IRoles(zope.interface.Interface):
...     def getOrganization():
...         'return the organization in which this relation operates'
...     principal_id = zope.interface.Attribute(
...         'the pricipal id whose roles this relation lists')
...     role_ids = zope.interface.Attribute(
...         'the role ids that the principal explicitly has in the '
...         'organization.  The principal may have other roles via '
...         'roles in parent organizations.')
...

Now we can create some classes. In the README example, the setup was a bit of a toy. This time we will be just a bit more practical. We’ll also expect to be operating within the ZODB, with a root and transactions. [14]

Here’s how we will dump and load our relations: use a “registry” object, similar to an intid utility. [15]

In this implementation of the “dump” method, we use the cache just to show you how you might use it. It probably is overkill for this job, and maybe even a speed loss, but you can see the idea.

>>> def dump(obj, catalog, cache):
...     reg = cache.get('registry')
...     if reg is None:
...         reg = cache['registry'] = catalog._p_jar.root()['registry']
...     return reg.getId(obj)
...
>>> def load(token, catalog, cache):
...     reg = cache.get('registry')
...     if reg is None:
...         reg = cache['registry'] = catalog._p_jar.root()['registry']
...     return reg.getObject(token)
...

Now we can create a relation catalog to hold these items.

>>> import zc.relation.catalog
>>> catalog = root['catalog'] = zc.relation.catalog.Catalog(dump, load)
>>> transaction.commit()

Now we set up our indexes. We’ll start with just the organizations, and set up the catalog with them. This part will be similar to the example in README.rst, but will introduce more discussions of optimizations and tokens. Then we’ll add in the part about roles, and explore queries and token-based “joins”.

Organizations

The organization will hold a set of organizations. This is actually not inherently easy in the ZODB because this means that we need to compare or hash persistent objects, which does not work reliably over time and across machines out-of-the-box. To side-step the issue for this example, and still do something a bit interesting and real-world, we’ll use the registry tokens introduced above. This will also give us a chance to talk a bit more about optimizations and tokens. (If you would like to sanely and transparently hold a set of persistent objects, try the zc.set package XXX not yet.)

>>> import BTrees
>>> import persistent
>>> @zope.interface.implementer(IOrganization)
... @total_ordering
... class Organization(persistent.Persistent):
...
...     def __init__(self, title):
...         self.title = title
...         self.parts = BTrees.family32.IF.TreeSet()
...     # the next parts just make the tests prettier
...     def __repr__(self):
...         return '<Organization instance "' + self.title + '">'
...     def __lt__(self, other):
...         # pukes if other doesn't have name
...         return self.title < other.title
...     def __eq__(self, other):
...         return self is other
...     def __hash__(self):
...         return 1  # dummy
...

OK, now we know how organizations will work. Now we can add the parts index to the catalog. This will do a few new things from how we added indexes in the README.

>>> catalog.addValueIndex(IOrganization['parts'], multiple=True,
...                       name="part")

So, what’s different from the README examples?

First, we are using an interface element to define the value to be indexed. It provides an interface to which objects will be adapted, a default name for the index, and information as to whether the attribute should be used directly or called.

Second, we are not specifying a dump or load. They are None. This means that the indexed value can already be treated as a token. This can allow a very significant optimization for reindexing if the indexed value is a large collection using the same BTree family as the index–which leads us to the next difference.

Third, we are specifying that multiple=True. This means that the value on a given relation that provides or can be adapted to IOrganization will have a collection of parts. These will always be regarded as a set, whether the actual colection is a BTrees set or the keys of a BTree.

Last, we are specifying a name to be used for queries. I find that queries read more easily when the query keys are singular, so I often rename plurals.

As in the README, We can add another simple transposing transitive query factory, switching between ‘part’ and None.

>>> import zc.relation.queryfactory
>>> factory1 = zc.relation.queryfactory.TransposingTransitive(
...     'part', None)
>>> catalog.addDefaultQueryFactory(factory1)

Let’s add a couple of search indexes in too, of the hierarchy looking up…

>>> import zc.relation.searchindex
>>> catalog.addSearchIndex(
...     zc.relation.searchindex.TransposingTransitiveMembership(
...         'part', None))

…and down.

>>> catalog.addSearchIndex(
...     zc.relation.searchindex.TransposingTransitiveMembership(
...         None, 'part'))

PLEASE NOTE: the search index looking up is not a good idea practically. The index is designed for looking down [16].

Let’s create and add a few organizations.

We’ll make a structure like this [24]:

        Ynod Corp Mangement                 Zookd Corp Management
         /      |      \                       /      |      \
  Ynod Devs  Ynod SAs  Ynod Admins  Zookd Admins   Zookd SAs  Zookd Devs
    /      \              \                 /                /         \
Y3L4 Proj  Bet Proj      Ynod Zookd Task Force      Zookd hOgnmd     Zookd Nbd

Here’s the Python.

>>> orgs = root['organizations'] = BTrees.family32.OO.BTree()
>>> for nm, parts in (
...     ('Y3L4 Proj', ()),
...     ('Bet Proj', ()),
...     ('Ynod Zookd Task Force', ()),
...     ('Zookd hOgnmd', ()),
...     ('Zookd Nbd', ()),
...     ('Ynod Devs', ('Y3L4 Proj', 'Bet Proj')),
...     ('Ynod SAs', ()),
...     ('Ynod Admins', ('Ynod Zookd Task Force',)),
...     ('Zookd Admins', ('Ynod Zookd Task Force',)),
...     ('Zookd SAs', ()),
...     ('Zookd Devs', ('Zookd hOgnmd', 'Zookd Nbd')),
...     ('Ynod Corp Management', ('Ynod Devs', 'Ynod SAs', 'Ynod Admins')),
...     ('Zookd Corp Management', ('Zookd Devs', 'Zookd SAs',
...                                'Zookd Admins'))):
...     org = Organization(nm)
...     for part in parts:
...         ignore = org.parts.insert(registry.getId(orgs[part]))
...     orgs[nm] = org
...     catalog.index(org)
...

Now the catalog knows about the relations.

>>> len(catalog)
13
>>> root['dummy'] = Organization('Foo')
>>> root['dummy'] in catalog
False
>>> orgs['Y3L4 Proj'] in catalog
True

Also, now we can search. To do this, we can use some of the token methods that the catalog provides. The most commonly used is tokenizeQuery. It takes a query with values that are not tokenized and converts them to values that are tokenized.

>>> Ynod_SAs_id = registry.getId(orgs['Ynod SAs'])
>>> catalog.tokenizeQuery({None: orgs['Ynod SAs']}) == {
...     None: Ynod_SAs_id}
True
>>> Zookd_SAs_id = registry.getId(orgs['Zookd SAs'])
>>> Zookd_Devs_id = registry.getId(orgs['Zookd Devs'])
>>> catalog.tokenizeQuery(
...     {None: zc.relation.catalog.any(
...         orgs['Zookd SAs'], orgs['Zookd Devs'])}) == {
...     None: zc.relation.catalog.any(Zookd_SAs_id, Zookd_Devs_id)}
True

Of course, right now doing this with ‘part’ alone is kind of silly, since it does not change within the relation catalog (because we said that dump and load were None, as discussed above).

>>> catalog.tokenizeQuery({'part': Ynod_SAs_id}) == {
...     'part': Ynod_SAs_id}
True
>>> catalog.tokenizeQuery(
...     {'part': zc.relation.catalog.any(Zookd_SAs_id, Zookd_Devs_id)}
...     ) == {'part': zc.relation.catalog.any(Zookd_SAs_id, Zookd_Devs_id)}
True

The tokenizeQuery method is so common that we’re going to assign it to a variable in our example. Then we’ll do a search or two.

So…find the relations that Ynod Devs supervise.

>>> t = catalog.tokenizeQuery
>>> res = list(catalog.findRelationTokens(t({None: orgs['Ynod Devs']})))

OK…we used findRelationTokens, as opposed to findRelations, so res is a couple of numbers now. How do we convert them back? resolveRelationTokens will do the trick.

>>> len(res)
3
>>> sorted(catalog.resolveRelationTokens(res))
... # doctest: +NORMALIZE_WHITESPACE
[<Organization instance "Bet Proj">, <Organization instance "Y3L4 Proj">,
 <Organization instance "Ynod Devs">]

resolveQuery is the mirror image of tokenizeQuery: it converts tokenized queries to queries with “loaded” values.

>>> original = {'part': zc.relation.catalog.any(
...                 Zookd_SAs_id, Zookd_Devs_id),
...             None: orgs['Zookd Devs']}
>>> tokenized = catalog.tokenizeQuery(original)
>>> original == catalog.resolveQuery(tokenized)
True

>>> original = {None: zc.relation.catalog.any(
...                 orgs['Zookd SAs'], orgs['Zookd Devs']),
...             'part': Zookd_Devs_id}
>>> tokenized = catalog.tokenizeQuery(original)
>>> original == catalog.resolveQuery(tokenized)
True

Likewise, tokenizeRelations is the mirror image of resolveRelationTokens.

>>> sorted(catalog.tokenizeRelations(
...     [orgs["Bet Proj"], orgs["Y3L4 Proj"]])) == sorted(
...     registry.getId(o) for o in
...     [orgs["Bet Proj"], orgs["Y3L4 Proj"]])
True

The other token-related methods are as follows [17]:

• tokenizeValues, which returns an iterable of tokens for the values of the given index name;

• resolveValueTokens, which returns an iterable of values for the tokens of the given index name;

• tokenizeRelation, which returns a token for the given relation; and

• resolveRelationToken, which returns a relation for the given token.

Why do we bother with these tokens, instead of hiding them away and making the API prettier? By exposing them, we enable efficient joining, and efficient use in other contexts. For instance, if you use the same intid utility to tokenize in other catalogs, our results can be merged with the results of other catalogs. Similarly, you can use the results of queries to other catalogs–or even “joins” from earlier results of querying this catalog–as query values here. We’ll explore this in the next section.

Roles

We have set up the Organization relations. Now let’s set up the roles, and actually be able to answer the questions that we described at the beginning of the document.

In our Roles object, roles and principals will simply be strings–ids, if this were a real system. The organization will be a direct object reference.

>>> @zope.interface.implementer(IRoles)
... @total_ordering
... class Roles(persistent.Persistent):
...
...     def __init__(self, principal_id, role_ids, organization):
...         self.principal_id = principal_id
...         self.role_ids = BTrees.family32.OI.TreeSet(role_ids)
...         self._organization = organization
...     def getOrganization(self):
...         return self._organization
...     # the rest is for prettier/easier tests
...     def __repr__(self):
...         return "<Roles instance (%s has %s in %s)>" % (
...             self.principal_id, ', '.join(self.role_ids),
...             self._organization.title)
...     def __lt__(self, other):
...         _self = (
...             self.principal_id,
...             tuple(self.role_ids),
...             self._organization.title,
...         )
...         _other = (
...             other.principal_id,
...             tuple(other.role_ids),
...             other._organization.title,
...         )
...         return _self <_other
...     def __eq__(self, other):
...         return self is other
...     def __hash__(self):
...         return 1  # dummy
...

Now let’s add add the value indexes to the relation catalog.

>>> catalog.addValueIndex(IRoles['principal_id'], btree=BTrees.family32.OI)
>>> catalog.addValueIndex(IRoles['role_ids'], btree=BTrees.family32.OI,
...                       multiple=True, name='role_id')
>>> catalog.addValueIndex(IRoles['getOrganization'], dump, load,
...                       name='organization')

Those are some slightly new variations of what we’ve seen in addValueIndex before, but all mixing and matching on the same ingredients.

As a reminder, here is our organization structure:

        Ynod Corp Mangement                 Zookd Corp Management
         /      |      \                       /      |      \
  Ynod Devs  Ynod SAs  Ynod Admins  Zookd Admins   Zookd SAs  Zookd Devs
    /      \              \                 /                /         \
Y3L4 Proj  Bet Proj      Ynod Zookd Task Force      Zookd hOgnmd     Zookd Nbd

Now let’s create and add some roles.

>>> principal_ids = [
...     'abe', 'bran', 'cathy', 'david', 'edgar', 'frank', 'gertrude',
...     'harriet', 'ignas', 'jacob', 'karyn', 'lettie', 'molly', 'nancy',
...     'ophelia', 'pat']
>>> role_ids = ['user manager', 'writer', 'reviewer', 'publisher']
>>> get_role = dict((v[0], v) for v in role_ids).__getitem__
>>> roles = root['roles'] = BTrees.family32.IO.BTree()
>>> next = 0
>>> for prin, org, role_ids in (
...     ('abe', orgs['Zookd Corp Management'], 'uwrp'),
...     ('bran', orgs['Ynod Corp Management'], 'uwrp'),
...     ('cathy', orgs['Ynod Devs'], 'w'),
...     ('cathy', orgs['Y3L4 Proj'], 'r'),
...     ('david', orgs['Bet Proj'], 'wrp'),
...     ('edgar', orgs['Ynod Devs'], 'up'),
...     ('frank', orgs['Ynod SAs'], 'uwrp'),
...     ('frank', orgs['Ynod Admins'], 'w'),
...     ('gertrude', orgs['Ynod Zookd Task Force'], 'uwrp'),
...     ('harriet', orgs['Ynod Zookd Task Force'], 'w'),
...     ('harriet', orgs['Ynod Admins'], 'r'),
...     ('ignas', orgs['Zookd Admins'], 'r'),
...     ('ignas', orgs['Zookd Corp Management'], 'w'),
...     ('karyn', orgs['Zookd Corp Management'], 'uwrp'),
...     ('karyn', orgs['Ynod Corp Management'], 'uwrp'),
...     ('lettie', orgs['Zookd Corp Management'], 'u'),
...     ('lettie', orgs['Ynod Zookd Task Force'], 'w'),
...     ('lettie', orgs['Zookd SAs'], 'w'),
...     ('molly', orgs['Zookd SAs'], 'uwrp'),
...     ('nancy', orgs['Zookd Devs'], 'wrp'),
...     ('nancy', orgs['Zookd hOgnmd'], 'u'),
...     ('ophelia', orgs['Zookd Corp Management'], 'w'),
...     ('ophelia', orgs['Zookd Devs'], 'r'),
...     ('ophelia', orgs['Zookd Nbd'], 'p'),
...     ('pat', orgs['Zookd Nbd'], 'wrp')):
...     assert prin in principal_ids
...     role_ids = [get_role(l) for l in role_ids]
...     role = roles[next] = Roles(prin, role_ids, org)
...     role.key = next
...     next += 1
...     catalog.index(role)
...

Now we can begin to do searches [18].

What are all the role settings for ophelia?

>>> sorted(catalog.findRelations({'principal_id': 'ophelia'}))
... # doctest: +NORMALIZE_WHITESPACE
[<Roles instance (ophelia has publisher in Zookd Nbd)>,
 <Roles instance (ophelia has reviewer in Zookd Devs)>,
 <Roles instance (ophelia has writer in Zookd Corp Management)>]

That answer does not need to be transitive: we’re done.

Next question. Where does ophelia have the ‘writer’ role?

>>> list(catalog.findValues(
...     'organization', {'principal_id': 'ophelia',
...                        'role_id': 'writer'}))
[<Organization instance "Zookd Corp Management">]

Well, that’s correct intransitively. Do we need a transitive queries factory? No! This is a great chance to look at the token join we talked about in the previous section. This should actually be a two-step operation: find all of the organizations in which ophelia has writer, and then find all of the transitive parts to that organization.

>>> sorted(catalog.findRelations({None: zc.relation.catalog.Any(
...     catalog.findValueTokens('organization',
...                             {'principal_id': 'ophelia',
...                              'role_id': 'writer'}))}))
... # doctest: +NORMALIZE_WHITESPACE
[<Organization instance "Ynod Zookd Task Force">,
 <Organization instance "Zookd Admins">,
 <Organization instance "Zookd Corp Management">,
 <Organization instance "Zookd Devs">,
 <Organization instance "Zookd Nbd">,
 <Organization instance "Zookd SAs">,
 <Organization instance "Zookd hOgnmd">]

That’s more like it.

Next question. What users have roles in the ‘Zookd Devs’ organization? Intransitively, that’s pretty easy.

>>> sorted(catalog.findValueTokens(
...     'principal_id', t({'organization': orgs['Zookd Devs']})))
['nancy', 'ophelia']

Transitively, we should do another join.

>>> org_id = registry.getId(orgs['Zookd Devs'])
>>> sorted(catalog.findValueTokens(
...     'principal_id', {
...         'organization': zc.relation.catalog.any(
...             org_id, *catalog.findRelationTokens({'part': org_id}))}))
['abe', 'ignas', 'karyn', 'lettie', 'nancy', 'ophelia']

That’s a little awkward, but it does the trick.

Last question, and the kind of question that started the entire example.

What roles does ophelia have in the “Zookd Nbd” organization?

>>> list(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'ophelia'})))
['publisher']

Intransitively, that’s correct. But, transitively, ophelia also has reviewer and writer, and that’s the answer we want to be able to get quickly.

We could ask the question a different way, then, again leveraging a join. We’ll set it up as a function, because we will want to use it a little later without repeating the code.

>>> def getRolesInOrganization(principal_id, org):
...     org_id = registry.getId(org)
...     return sorted(catalog.findValueTokens(
...         'role_id', {
...             'organization': zc.relation.catalog.any(
...                 org_id,
...                 *catalog.findRelationTokens({'part': org_id})),
...             'principal_id': principal_id}))
...
>>> getRolesInOrganization('ophelia', orgs['Zookd Nbd'])
['publisher', 'reviewer', 'writer']

As you can see, then, working with tokens makes interesting joins possible, as long as the tokens are the same across the two queries.

We have examined tokens methods and token techniques like joins. The example story we have told can let us get into a few more advanced topics, such as query factory joins and search indexes that can increase their read speed.

Query Factory Joins

We can build a query factory that makes the join automatic. A query factory is a callable that takes two arguments: a query (the one that starts the search) and the catalog. The factory either returns None, indicating that the query factory cannot be used for this query, or it returns another callable that takes a chain of relations. The last token in the relation chain is the most recent. The output of this inner callable is expected to be an iterable of BTrees.family32.OO.Bucket queries to search further from the given chain of relations.

Here’s a flawed approach to this problem.

>>> def flawed_factory(query, catalog):
...     if (len(query) == 2 and
...         'organization' in query and
...         'principal_id' in query):
...         def getQueries(relchain):
...             if not relchain:
...                 yield query
...                 return
...             current = catalog.getValueTokens(
...                 'organization', relchain[-1])
...             if current:
...                 organizations = catalog.getRelationTokens(
...                     {'part': zc.relation.catalog.Any(current)})
...                 if organizations:
...                     res = BTrees.family32.OO.Bucket(query)
...                     res['organization'] = zc.relation.catalog.Any(
...                         organizations)
...                     yield res
...         return getQueries
...

That works for our current example.

>>> sorted(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'ophelia'}),
...     queryFactory=flawed_factory))
['publisher', 'reviewer', 'writer']

However, it won’t work for other similar queries.

>>> getRolesInOrganization('abe', orgs['Zookd Nbd'])
['publisher', 'reviewer', 'user manager', 'writer']
>>> sorted(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'abe'}),
...     queryFactory=flawed_factory))
[]

oops.

The flawed_factory is actually a useful pattern for more typical relation traversal. It goes from relation to relation to relation, and ophelia has connected relations all the way to the top. However, abe only has them at the top, so nothing is traversed.

Instead, we can make a query factory that modifies the initial query.

>>> def factory2(query, catalog):
...     if (len(query) == 2 and
...         'organization' in query and
...         'principal_id' in query):
...         def getQueries(relchain):
...             if not relchain:
...                 res = BTrees.family32.OO.Bucket(query)
...                 org_id = query['organization']
...                 if org_id is not None:
...                     res['organization'] = zc.relation.catalog.any(
...                         org_id,
...                         *catalog.findRelationTokens({'part': org_id}))
...                 yield res
...         return getQueries
...

>>> sorted(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'ophelia'}),
...     queryFactory=factory2))
['publisher', 'reviewer', 'writer']

>>> sorted(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'abe'}),
...     queryFactory=factory2))
['publisher', 'reviewer', 'user manager', 'writer']

A difference between this and the other approach is that it is essentially intransitive: this query factory modifies the initial query, and then does not give further queries. The catalog currently always stops calling the query factory if the queries do not return any results, so an approach like the flawed_factory simply won’t work for this kind of problem.

We could add this query factory as another default.

>>> catalog.addDefaultQueryFactory(factory2)

>>> sorted(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'ophelia'})))
['publisher', 'reviewer', 'writer']

>>> sorted(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'abe'})))
['publisher', 'reviewer', 'user manager', 'writer']

The previously installed query factory is still available.

>>> list(catalog.iterDefaultQueryFactories()) == [factory1, factory2]
True

>>> list(catalog.findRelations(
...     {'part': registry.getId(orgs['Y3L4 Proj'])}))
...     # doctest: +NORMALIZE_WHITESPACE
[<Organization instance "Ynod Devs">,
 <Organization instance "Ynod Corp Management">]

>>> sorted(catalog.findRelations(
...     {None: registry.getId(orgs['Ynod Corp Management'])}))
...     # doctest: +NORMALIZE_WHITESPACE
[<Organization instance "Bet Proj">, <Organization instance "Y3L4 Proj">,
 <Organization instance "Ynod Admins">,
 <Organization instance "Ynod Corp Management">,
 <Organization instance "Ynod Devs">, <Organization instance "Ynod SAs">,
 <Organization instance "Ynod Zookd Task Force">]

Search Index for Query Factory Joins

Now that we have written a query factory that encapsulates the join, we can use a search index that speeds it up. We’ve only used transitive search indexes so far. Now we will add an intransitive search index.

The intransitive search index generally just needs the search value names it should be indexing, optionally the result name (defaulting to relations), and optionally the query factory to be used.

We need to use two additional options because of the odd join trick we’re doing. We need to specify what organization and principal_id values need to be changed when an object is indexed, and we need to indicate that we should update when organization, principal_id, or parts changes.

getValueTokens specifies the values that need to be indexed. It gets the index, the name for the tokens desired, the token, the catalog that generated the token change (it may not be the same as the index’s catalog, the source dictionary that contains a dictionary of the values that will be used for tokens if you do not override them, a dict of the added values for this token (keys are value names), a dict of the removed values for this token, and whether the token has been removed. The method can return None, which will leave the index to its default behavior that should work if no query factory is used; or an iterable of values.

>>> def getValueTokens(index, name, token, catalog, source,
...                    additions, removals, removed):
...     if name == 'organization':
...         orgs = source.get('organization')
...         if not removed or not orgs:
...             orgs = index.catalog.getValueTokens(
...                 'organization', token)
...             if not orgs:
...                 orgs = [token]
...                 orgs.extend(removals.get('part', ()))
...         orgs = set(orgs)
...         orgs.update(index.catalog.findValueTokens(
...             'part',
...             {None: zc.relation.catalog.Any(
...                 t for t in orgs if t is not None)}))
...         return orgs
...     elif name == 'principal_id':
...         # we only want custom behavior if this is an organization
...         if 'principal_id' in source or index.catalog.getValueTokens(
...             'principal_id', token):
...             return ''
...         orgs = set((token,))
...         orgs.update(index.catalog.findRelationTokens(
...             {'part': token}))
...         return set(index.catalog.findValueTokens(
...             'principal_id', {
...                 'organization': zc.relation.catalog.Any(orgs)}))
...

>>> index = zc.relation.searchindex.Intransitive(
...     ('organization', 'principal_id'), 'role_id', factory2,
...     getValueTokens,
...     ('organization', 'principal_id', 'part', 'role_id'),
...     unlimitedDepth=True)
>>> catalog.addSearchIndex(index)

>>> res = catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'ophelia'}))
>>> list(res)
['publisher', 'reviewer', 'writer']
>>> list(res)
['publisher', 'reviewer', 'writer']

>>> res = catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'abe'}))
>>> list(res)
['publisher', 'reviewer', 'user manager', 'writer']
>>> list(res)
['publisher', 'reviewer', 'user manager', 'writer']

[19]

Now we can change and remove relations–both organizations and roles–and have the index maintain correct state. Given the current state of organizations–

        Ynod Corp Mangement                 Zookd Corp Management
         /      |      \                       /      |      \
  Ynod Devs  Ynod SAs  Ynod Admins  Zookd Admins   Zookd SAs  Zookd Devs
    /      \              \                 /                /         \
Y3L4 Proj  Bet Proj      Ynod Zookd Task Force      Zookd hOgnmd     Zookd Nbd

–first we will move Ynod Devs to beneath Zookd Devs, and back out. This will briefly give abe full privileges to Y3L4 Proj., among others.

>>> list(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Y3L4 Proj'],
...                   'principal_id': 'abe'})))
[]
>>> orgs['Zookd Devs'].parts.insert(registry.getId(orgs['Ynod Devs']))
1
>>> catalog.index(orgs['Zookd Devs'])
>>> res = catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Y3L4 Proj'],
...                   'principal_id': 'abe'}))
>>> list(res)
['publisher', 'reviewer', 'user manager', 'writer']
>>> list(res)
['publisher', 'reviewer', 'user manager', 'writer']
>>> orgs['Zookd Devs'].parts.remove(registry.getId(orgs['Ynod Devs']))
>>> catalog.index(orgs['Zookd Devs'])
>>> list(catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Y3L4 Proj'],
...                   'principal_id': 'abe'})))
[]

As another example, we will change the roles abe has, and see that it is propagated down to Zookd Nbd.

>>> rels = list(catalog.findRelations(t(
...     {'principal_id': 'abe',
...      'organization': orgs['Zookd Corp Management']})))
>>> len(rels)
1
>>> rels[0].role_ids.remove('reviewer')
>>> catalog.index(rels[0])

>>> res = catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'abe'}))
>>> list(res)
['publisher', 'user manager', 'writer']
>>> list(res)
['publisher', 'user manager', 'writer']

Note that search index order matters. In our case, our intransitive search index is relying on our transitive index, so the transitive index needs to come first. You want transitive relation indexes before name. Right now, you are in charge of this order: it will be difficult to come up with a reliable algorithm for guessing this.

Listeners, Catalog Administration, and Joining Across Relation Catalogs

We’ve done all of our examples so far with a single catalog that indexes both kinds of relations. What if we want to have two catalogs with homogenous collections of relations? That can feel cleaner, but it also introduces some new wrinkles.

Let’s use our current catalog for organizations, removing the extra information; and create a new one for roles.

>>> role_catalog = root['role_catalog'] = catalog.copy()
>>> transaction.commit()
>>> org_catalog = catalog
>>> del catalog

We’ll need a slightly different query factory and a slightly different search index getValueTokens function. We’ll write those, then modify the configuration of our two catalogs for the new world.

The transitive factory we write here is for the role catalog. It needs access to the organzation catalog. We could do this a variety of ways–relying on a utility, or finding the catalog from context. We will make the role_catalog have a .org_catalog attribute, and rely on that.

>>> role_catalog.org_catalog = org_catalog
>>> def factory3(query, catalog):
...     if (len(query) == 2 and
...         'organization' in query and
...         'principal_id' in query):
...         def getQueries(relchain):
...             if not relchain:
...                 res = BTrees.family32.OO.Bucket(query)
...                 org_id = query['organization']
...                 if org_id is not None:
...                     res['organization'] = zc.relation.catalog.any(
...                         org_id,
...                         *catalog.org_catalog.findRelationTokens(
...                             {'part': org_id}))
...                 yield res
...         return getQueries
...

>>> def getValueTokens2(index, name, token, catalog, source,
...                    additions, removals, removed):
...     is_role_catalog = catalog is index.catalog # role_catalog
...     if name == 'organization':
...         if is_role_catalog:
...             orgs = set(source.get('organization') or
...                        index.catalog.getValueTokens(
...                         'organization', token) or ())
...         else:
...             orgs = set((token,))
...             orgs.update(removals.get('part', ()))
...         orgs.update(index.catalog.org_catalog.findValueTokens(
...             'part',
...             {None: zc.relation.catalog.Any(
...                 t for t in orgs if t is not None)}))
...         return orgs
...     elif name == 'principal_id':
...         # we only want custom behavior if this is an organization
...         if not is_role_catalog:
...             orgs = set((token,))
...             orgs.update(index.catalog.org_catalog.findRelationTokens(
...                 {'part': token}))
...             return set(index.catalog.findValueTokens(
...                 'principal_id', {
...                     'organization': zc.relation.catalog.Any(orgs)}))
...     return ''

If you are following along in the code and comparing to the originals, you may see that this approach is a bit cleaner than the one when the relations were in the same catalog.

Now we will fix up the the organization catalog [20].

This also shows using the removeDefaultQueryFactory and removeSearchIndex methods [21].

Now we will set up the role catalog [22].

The new role_catalog index needs to be updated from the org_catalog. We’ll set that up using listeners, a new concept.

>>> org_catalog.addListener(index2)
>>> list(org_catalog.iterListeners()) == [index2]
True

Now the role_catalog should be able to answer the same questions as the old single catalog approach.

>>> t = role_catalog.tokenizeQuery
>>> list(role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'abe'})))
['publisher', 'user manager', 'writer']

>>> list(role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'ophelia'})))
['publisher', 'reviewer', 'writer']

We can also make changes to both catalogs and the search indexes are maintained.

>>> list(role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Y3L4 Proj'],
...                   'principal_id': 'abe'})))
[]
>>> orgs['Zookd Devs'].parts.insert(registry.getId(orgs['Ynod Devs']))
1
>>> org_catalog.index(orgs['Zookd Devs'])
>>> list(role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Y3L4 Proj'],
...                   'principal_id': 'abe'})))
['publisher', 'user manager', 'writer']
>>> orgs['Zookd Devs'].parts.remove(registry.getId(orgs['Ynod Devs']))
>>> org_catalog.index(orgs['Zookd Devs'])
>>> list(role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Y3L4 Proj'],
...                   'principal_id': 'abe'})))
[]

>>> rels = list(role_catalog.findRelations(t(
...     {'principal_id': 'abe',
...      'organization': orgs['Zookd Corp Management']})))
>>> len(rels)
1
>>> rels[0].role_ids.insert('reviewer')
1
>>> role_catalog.index(rels[0])

>>> res = role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd Nbd'],
...                   'principal_id': 'abe'}))
>>> list(res)
['publisher', 'reviewer', 'user manager', 'writer']

Here we add a new organization.

>>> orgs['Zookd hOnc'] = org = Organization('Zookd hOnc')
>>> orgs['Zookd Devs'].parts.insert(registry.getId(org))
1
>>> org_catalog.index(orgs['Zookd hOnc'])
>>> org_catalog.index(orgs['Zookd Devs'])

>>> list(role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd hOnc'],
...                   'principal_id': 'abe'})))
['publisher', 'reviewer', 'user manager', 'writer']

>>> list(role_catalog.findValueTokens(
...     'role_id', t({'organization': orgs['Zookd hOnc'],
...                   'principal_id': 'ophelia'})))
['reviewer', 'writer']

Now we’ll remove it.

>>> orgs['Zookd Devs'].parts.remove(registry.getId(org))
>>> org_catalog.index(orgs['Zookd Devs'])
>>> org_catalog.unindex(orgs['Zookd hOnc'])

TODO make sure that intransitive copy looks the way we expect

[23]

Introduction

This document assumes you have read the README.rst document, and want to learn a bit more by example. In it, we will explore a set of relations that demonstrates most of the aspects of working with search indexes and listeners. It will not explain the topics that the other documents already addressed. It also describes an advanced use case.

As we have seen in the other documents, the relation catalog supports search indexes. These can return the results of any search, as desired. Of course, the intent is that you supply an index that optimizes the particular searches it claims.

The searchindex module supplies a few search indexes, optimizing specified transitive and intransitive searches. We have seen them working in other documents. We will examine them more in depth in this document.

Search indexes update themselves by receiving messages via a “listener” interface. We will also look at how this works.

The example described in this file examines a use case similar to that in the zc.revision or zc.vault packages: a relation describes a graph of other objects. Therefore, this is our first concrete example of purely extrinsic relations.

Let’s build the example story a bit. Imagine we have a graph, often a hierarchy, of tokens–integers. Relations specify that a given integer token relates to other integer tokens, with a containment denotation or other meaning.

The integers may also have relations that specify that they represent an object or objects.

This allows us to have a graph of objects in which changing one part of the graph does not require changing the rest. zc.revision and zc.vault thus are able to model graphs that can have multiple revisions efficiently and with quite a bit of metadata to support merges.

Let’s imagine a simple hierarchy. The relation has a token attribute and a children attribute; children point to tokens. Relations will identify themselves with ids.

>>> import BTrees
>>> relations = BTrees.family64.IO.BTree()
>>> relations[99] = None # just to give us a start

>>> class Relation(object):
...     def __init__(self, token, children=()):
...         self.token = token
...         self.children = BTrees.family64.IF.TreeSet(children)
...         self.id = relations.maxKey() + 1
...         relations[self.id] = self
...

>>> def token(rel, self):
...     return rel.token
...
>>> def children(rel, self):
...     return rel.children
...
>>> def dumpRelation(obj, index, cache):
...     return obj.id
...
>>> def loadRelation(token, index, cache):
...     return relations[token]
...

The standard TransposingTransitiveQueriesFactory will be able to handle this quite well, so we’ll use that for our index.

>>> import zc.relation.queryfactory
>>> factory = zc.relation.queryfactory.TransposingTransitive(
...     'token', 'children')
>>> import zc.relation.catalog
>>> catalog = zc.relation.catalog.Catalog(
...     dumpRelation, loadRelation, BTrees.family64.IO, BTrees.family64)
>>> catalog.addValueIndex(token)
>>> catalog.addValueIndex(children, multiple=True)
>>> catalog.addDefaultQueryFactory(factory)

Now let’s quickly create a hierarchy and index it.

>>> for token, children in (
...     (0, (1, 2)), (1, (3, 4)), (2, (10, 11, 12)), (3, (5, 6)),
...     (4, (13, 14)), (5, (7, 8, 9)), (6, (15, 16)), (7, (17, 18, 19)),
...     (8, (20, 21, 22)), (9, (23, 24)), (10, (25, 26)),
...     (11, (27, 28, 29, 30, 31, 32))):
...     catalog.index(Relation(token, children))
...

[25] That hierarchy is arbitrary. Here’s what we have, in terms of tokens pointing to children:

                                 _____________0_____________
                                /                           \
                       ________1_______                ______2____________
                      /                \              /          |        \
               ______3_____            _4_          10       ____11_____   12
              /            \          /   \         / \     / /  |  \ \ \
      _______5_______       6       13     14     25  26  27 28 29 30 31 32
     /       |       \     / \
   _7_      _8_       9   15 16
  / | \    / | \     / \
17 18 19  20 21 22  23 24

Twelve relations, with tokens 0 through 11, and a total of 33 tokens, including children. The ids for the 12 relations are 100 through 111, corresponding with the tokens of 0 through 11.

Without a transitive search index, we can get all transitive results. The results are iterators.

>>> res = catalog.findRelationTokens({'token': 0})
>>> getattr(res, '__next__') is None
False
>>> getattr(res, '__len__', None) is None
True
>>> sorted(res)
[100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111]
>>> list(res)
[]

>>> res = catalog.findValueTokens('children', {'token': 0})
>>> sorted(res) == list(range(1, 33))
True
>>> list(res)
[]

[26] canFind also can work transitively, and will use transitive search indexes, as we’ll see below.

>>> catalog.canFind({'token': 1}, targetQuery={'children': 23})
True
>>> catalog.canFind({'token': 2}, targetQuery={'children': 23})
False
>>> catalog.canFind({'children': 23}, targetQuery={'token': 1})
True
>>> catalog.canFind({'children': 23}, targetQuery={'token': 2})
False

findRelationTokenChains won’t change, but we’ll include it in the discussion and examples to show that.

>>> res = catalog.findRelationTokenChains({'token': 2})
>>> chains = list(res)
>>> len(chains)
3
>>> len(list(res))
0

Transitive Search Indexes

Now we can add a couple of transitive search index. We’ll talk about them a bit first.

There is currently one variety of transitive index, which indexes relation and value searches for the transposing transitive query factory.

The index can only be used under certain conditions.

• The search is not a request for a relation chain.

• It does not specify a maximum depth.

• Filters are not used.

If it is a value search, then specific value indexes cannot be used if a target filter or target query are used, but the basic relation index can still be used in that case.

The usage of the search indexes is largely transparent: set them up, and the relation catalog will use them for the same API calls that used more brute force previously. The only difference from external uses is that results that use an index will usually be a BTree structure, rather than an iterator.

When you add a transitive index for a relation, you must specify the transitive name (or names) of the query, and the same for the reverse. That’s all we’ll do now.

>>> import zc.relation.searchindex
>>> catalog.addSearchIndex(
...     zc.relation.searchindex.TransposingTransitiveMembership(
...         'token', 'children', names=('children',)))

Now we should have a search index installed.

Notice that we went from parent (token) to child: this index is primarily designed for helping transitive membership searches in a hierarchy. Using it to index parents would incur a lot of write expense for not much win.

There’s just a bit more you can specify here: static fields for a query to do a bit of filtering. We don’t need any of that for this example.

Now how does the catalog use this index for searches? Three basic ways, depending on the kind of search, relations, values, or canFind. Before we start looking into the internals, let’s verify that we’re getting what we expect: correct answers, and not iterators, but BTree structures.

>>> res = catalog.findRelationTokens({'token': 0})
>>> list(res)
[100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111]
>>> list(res)
[100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111]

>>> res = catalog.findValueTokens('children', {'token': 0})
>>> list(res) == list(range(1, 33))
True
>>> list(res) == list(range(1, 33))
True

>>> catalog.canFind({'token': 1}, targetQuery={'children': 23})
True
>>> catalog.canFind({'token': 2}, targetQuery={'children': 23})
False

[27] Note that the last two canFind examples from when we went through these examples without an index do not use the index, so we don’t show them here: they look the wrong direction for this index.

So how do these results happen?

The first, findRelationTokens, and the last, canFind, are the most straightforward. The index finds all relations that match the given query, intransitively. Then for each relation, it looks up the indexed transitive results for that token. The end result is the union of all indexed results found from the intransitive search. canFind simply casts the result into a boolean.

findValueTokens is the same story as above with only one more step. After the union of relations is calculated, the method returns the union of the sets of the requested value for all found relations.

It will maintain itself when relations are reindexed.

>>> rel = list(catalog.findRelations({'token': 11}))[0]
>>> for t in (27, 28, 29, 30, 31):
...     rel.children.remove(t)
...
>>> catalog.index(rel)

>>> catalog.findValueTokens('children', {'token': 0})
... # doctest: +NORMALIZE_WHITESPACE
LFSet([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
       20, 21, 22, 23, 24, 25, 26, 32])
>>> catalog.findValueTokens('children', {'token': 2})
LFSet([10, 11, 12, 25, 26, 32])
>>> catalog.findValueTokens('children', {'token': 11})
LFSet([32])

>>> rel.children.remove(32)
>>> catalog.index(rel)

>>> catalog.findValueTokens('children', {'token': 0})
... # doctest: +NORMALIZE_WHITESPACE
LFSet([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
       20, 21, 22, 23, 24, 25, 26])
>>> catalog.findValueTokens('children', {'token': 2})
LFSet([10, 11, 12, 25, 26])
>>> catalog.findValueTokens('children', {'token': 11})
LFSet([])

>>> rel.children.insert(27)
1
>>> catalog.index(rel)

>>> catalog.findValueTokens('children', {'token': 0})
... # doctest: +NORMALIZE_WHITESPACE
LFSet([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
       20, 21, 22, 23, 24, 25, 26, 27])
>>> catalog.findValueTokens('children', {'token': 2})
LFSet([10, 11, 12, 25, 26, 27])
>>> catalog.findValueTokens('children', {'token': 11})
LFSet([27])

When the index is copied, the search index is copied.

>>> new = catalog.copy()
>>> res = list(new.iterSearchIndexes())
>>> len(res)
1
>>> new_index = res[0]
>>> res = list(catalog.iterSearchIndexes())
>>> len(res)
1
>>> old_index = res[0]
>>> new_index is old_index
False
>>> old_index.index is new_index.index
False
>>> list(old_index.index.keys()) == list(new_index.index.keys())
True
>>> from __future__ import print_function
>>> for key, value in old_index.index.items():
...     v = new_index.index[key]
...     if v is value or list(v) != list(value):
...         print('oops', key, value, v)
...         break
... else:
...     print('good')
...
good
>>> old_index.names is not new_index.names
True
>>> list(old_index.names) == list(new_index.names)
True
>>> for name, old_ix in old_index.names.items():
...     new_ix = new_index.names[name]
...     if new_ix is old_ix or list(new_ix.keys()) != list(old_ix.keys()):
...         print('oops')
...         break
...     for key, value in old_ix.items():
...         v = new_ix[key]
...         if v is value or list(v) != list(value):
...             print('oops', name, key, value, v)
...             break
...     else:
...         continue
...     break
... else:
...     print('good')
...
good

Helpers

When writing search indexes and query factories, you often want complete access to relation catalog data. We’ve seen a number of these tools already:

• getRelationModuleTools gets a dictionary of the BTree tools needed to work with relations.

  >>> sorted(catalog.getRelationModuleTools().keys())
  ... # doctest: +NORMALIZE_WHITESPACE
  ['BTree', 'Bucket', 'Set', 'TreeSet', 'difference', 'dump',
   'intersection', 'load', 'multiunion', 'union']
  

  ‘multiunion’ is only there if the BTree is an I* or L* module. Use the zc.relation.catalog.multiunion helper function to do the best union you can for a given set of tools.

• getValueModuleTools does the same for indexed values.

  >>> tools = set(('BTree', 'Bucket', 'Set', 'TreeSet', 'difference',
  ...              'dump', 'intersection', 'load', 'multiunion', 'union'))
  >>> tools.difference(catalog.getValueModuleTools('children').keys()) == set()
  True
  

  >>> tools.difference(catalog.getValueModuleTools('token').keys()) == set()
  True
  

• getRelationTokens can return all of the tokens in the catalog.

  >>> len(catalog.getRelationTokens()) == len(catalog)
  True
  

  This also happens to be equivalent to findRelationTokens with an empty query.

  >>> catalog.getRelationTokens() is catalog.findRelationTokens({})
  True
  

  It also can return all the tokens that match a given query, or None if there are no matches.

  >>> catalog.getRelationTokens({'token': 0}) # doctest: +ELLIPSIS
  <BTrees.LOBTree.LOTreeSet object at ...>
  >>> list(catalog.getRelationTokens({'token': 0}))
  [100]
  

  This also happens to be equivalent to findRelationTokens with a query, a maxDepth of 1, and no other arguments.

  >>> catalog.findRelationTokens({'token': 0}, maxDepth=1) is (
  ...     catalog.getRelationTokens({'token': 0}))
  True
  

  Except that if there are no matches, findRelationTokens returns an empty set (so it always returns an iterable).

  >>> catalog.findRelationTokens({'token': 50}, maxDepth=1)
  LOSet([])
  >>> print(catalog.getRelationTokens({'token': 50}))
  None
  

• getValueTokens can return all of the tokens for a given value name in

  the catalog.

  >>> list(catalog.getValueTokens('token')) == list(range(12))
  True
  

  This is identical to catalog.findValueTokens with a name only (or with an empty query, and a maxDepth of 1).

  >>> list(catalog.findValueTokens('token')) == list(range(12))
  True
  >>> catalog.findValueTokens('token') is catalog.getValueTokens('token')
  True
  

  It can also return the values for a given token.

  >>> list(catalog.getValueTokens('children', 100))
  [1, 2]
  

  This is identical to catalog.findValueTokens with a name and a query of {None: token}.

  >>> list(catalog.findValueTokens('children', {None: 100}))
  [1, 2]
  >>> catalog.getValueTokens('children', 100) is (
  ...     catalog.findValueTokens('children', {None: 100}))
  True
  

  Except that if there are no matches, findValueTokens returns an empty set (so it always returns an iterable); while getValueTokens will return None if the relation has no values (or the relation is unknown).

  >>> catalog.findValueTokens('children', {None: 50}, maxDepth=1)
  LFSet([])
  >>> print(catalog.getValueTokens('children', 50))
  None
  

  >>> rel.children.remove(27)
  >>> catalog.index(rel)
  >>> catalog.findValueTokens('children', {None: rel.id}, maxDepth=1)
  LFSet([])
  >>> print(catalog.getValueTokens('children', rel.id))
  None
  

• yieldRelationTokenChains is a search workhorse for searches that use a

  query factory. TODO: describe.

Optimizing Relation Catalog Use

There are several best practices and optimization opportunities in regards to the catalog.

• Use integer-keyed BTree sets when possible. They can use the BTrees’ multiunion for a speed boost. Integers’ __cmp__ is reliable, and in C.

• Never use persistent objects as keys. They will cause a database load every time you need to look at them, they take up memory and object caches, and they (as of this writing) disable conflict resolution. Intids (or similar) are your best bet for representing objects, and some other immutable such as strings are the next-best bet, and zope.app.keyreferences (or similar) are after that.

• Use multiple-token values in your queries when possible, especially in your transitive query factories.

• Use the cache when you are loading and dumping tokens, and in your transitive query factories.

• When possible, don’t load or dump tokens (the values themselves may be used as tokens). This is especially important when you have multiple tokens: store them in a BTree structure in the same module as the zc.relation module for the value.

For some operations, particularly with hundreds or thousands of members in a single relation value, some of these optimizations can speed up some common-case reindexing work by around 100 times.

The easiest (and perhaps least useful) optimization is that all dump calls and all load calls generated by a single operation share a cache dictionary per call type (dump/load), per indexed relation value. Therefore, for instance, we could stash an intids utility, so that we only had to do a utility lookup once, and thereafter it was only a single dictionary lookup. This is what the default generateToken and resolveToken functions in zc.relationship’s index.py do: look at them for an example.

A further optimization is to not load or dump tokens at all, but use values that may be tokens. This will be particularly useful if the tokens have __cmp__ (or equivalent) in C, such as built-in types like ints. To specify this behavior, you create an index with the ‘load’ and ‘dump’ values for the indexed attribute descriptions explicitly set to None.

>>> import zope.interface
>>> class IRelation(zope.interface.Interface):
...     subjects = zope.interface.Attribute(
...         'The sources of the relation; the subject of the sentence')
...     relationtype = zope.interface.Attribute(
...         '''unicode: the single relation type of this relation;
...         usually contains the verb of the sentence.''')
...     objects = zope.interface.Attribute(
...         '''the targets of the relation; usually a direct or
...         indirect object in the sentence''')
...

>>> import BTrees
>>> relations = BTrees.family32.IO.BTree()
>>> relations[99] = None # just to give us a start

>>> @zope.interface.implementer(IRelation)
... class Relation(object):
...
...     def __init__(self, subjects, relationtype, objects):
...         self.subjects = subjects
...         assert relationtype in relTypes
...         self.relationtype = relationtype
...         self.objects = objects
...         self.id = relations.maxKey() + 1
...         relations[self.id] = self
...     def __repr__(self):
...         return '<%r %s %r>' % (
...             self.subjects, self.relationtype, self.objects)

>>> def token(rel, self):
...     return rel.token
...
>>> def children(rel, self):
...     return rel.children
...
>>> def dumpRelation(obj, index, cache):
...     return obj.id
...
>>> def loadRelation(token, index, cache):
...     return relations[token]
...

>>> relTypes = ['has the role of']
>>> def relTypeDump(obj, index, cache):
...     assert obj in relTypes, 'unknown relationtype'
...     return obj
...
>>> def relTypeLoad(token, index, cache):
...     assert token in relTypes, 'unknown relationtype'
...     return token
...

>>> import zc.relation.catalog
>>> catalog = zc.relation.catalog.Catalog(
...     dumpRelation, loadRelation)
>>> catalog.addValueIndex(IRelation['subjects'], multiple=True)
>>> catalog.addValueIndex(
...     IRelation['relationtype'], relTypeDump, relTypeLoad,
...     BTrees.family32.OI, name='reltype')
>>> catalog.addValueIndex(IRelation['objects'], multiple=True)
>>> import zc.relation.queryfactory
>>> factory = zc.relation.queryfactory.TransposingTransitive(
...     'subjects', 'objects')
>>> catalog.addDefaultQueryFactory(factory)

>>> rel = Relation((1,), 'has the role of', (2,))
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 1}))
[2]

If you have single relations that relate hundreds or thousands of objects, it can be a huge win if the value is a ‘multiple’ of the same type as the stored BTree for the given attribute. The default BTree family for attributes is IFBTree; IOBTree is also a good choice, and may be preferrable for some applications.

>>> catalog.unindex(rel)
>>> rel = Relation(
...     BTrees.family32.IF.TreeSet((1,)), 'has the role of',
...     BTrees.family32.IF.TreeSet())
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 1}))
[]
>>> list(catalog.findValueTokens('subjects', {'objects': None}))
[1]

Reindexing is where some of the big improvements can happen. The following gyrations exercise the optimization code.

>>> rel.objects.insert(2)
1
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 1}))
[2]
>>> rel.subjects = BTrees.family32.IF.TreeSet((3,4,5))
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 3}))
[2]

>>> rel.subjects.insert(6)
1
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 6}))
[2]

>>> rel.subjects.update(range(100, 200))
100
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 100}))
[2]

>>> rel.subjects = BTrees.family32.IF.TreeSet((3,4,5,6))
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 3}))
[2]

>>> rel.subjects = BTrees.family32.IF.TreeSet(())
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 3}))
[]

>>> rel.subjects = BTrees.family32.IF.TreeSet((3,4,5))
>>> catalog.index(rel)
>>> list(catalog.findValueTokens('objects', {'subjects': 3}))
[2]

tokenizeValues and resolveValueTokens work correctly without loaders and dumpers–that is, they do nothing.

>>> catalog.tokenizeValues((3,4,5), 'subjects')
(3, 4, 5)
>>> catalog.resolveValueTokens((3,4,5), 'subjects')
(3, 4, 5)

2.0 (2023-04-05)

• Drop support for Python 2.7, 3.5, 3.6. [ale-rt]

• Fix the dependency on the ZODB, we just need to depend on the BTrees package. Refs. #11. [ale-rt]

1.2 (2023-03-28)

• Adapt code for PEP-479 (Change StopIteration handling inside generators). See: https://peps.python.org/pep-0479. Fixes #11. [ale-rt]

1.1.post2 (2018-06-18)

• Another attempt to fix PyPI page by using correct expected metadata syntax.

1.1.post1 (2018-06-18)

• Fix PyPI page by using correct ReST syntax.

1.1 (2018-06-15)

• Add support for Python 3.5 and 3.6.

1.0 (2008-04-23)

This is the initial release of the zc.relation package. However, it represents a refactoring of another package, zc.relationship. This package contains only a modified version of the relation(ship) index, now called a catalog. The refactored version of zc.relationship index relies on (subclasses) this catalog. zc.relationship also maintains a backwards-compatible subclass.

This package only relies on the ZODB, zope.interface, and zope.testing software, and can be used inside or outside of a standard ZODB database. The software does have to be there, though (the package relies heavily on the ZODB BTrees package).

If you would like to switch a legacy zc.relationship index to a zc.relation catalog, try this trick in your generations script. Assuming the old index is old, the following line should create a new zc.relation catalog with your legacy data:

>>> new = old.copy(zc.relation.Catalog)

Why is the same basic data structure called a catalog now? Because we exposed the ability to mutate the data structure, and what you are really adding and removing are indexes. It didn’t make sense to put an index in an index, but it does make sense to put an index in a catalog. Thus, a name change was born.

The catalog in this package has several incompatibilities from the earlier zc.relationship index, and many new features. The zc.relationship package maintains a backwards-compatible subclass. The following discussion compares the zc.relation catalog with the zc.relationship 1.x index.