[ZODB-Dev] n-way join algoritms

[Steve Alexander]

Roché Compaan wrote:
> * Phillip J. Eby <pje at telecommunity.com> [2003-06-22 00:13]:
> 
>>I don't understand what you're saying.  But, the basic merge algorithm for 
>>joining is trivial.  All of the complexity of joining comes from 
>>optimization.
>>
>>The most trivial algorithm would look like this:
>>
>>for a in A:
>>    for b in B:
>>        if a.x == b.x:
>>            for c in C:
>>                if b.y==c.y:
>>                    for d in D:
>>                        if c.z==d.z:
>>                            yield a,b,c,d
> 
> 
> Thanks Phillip this will work perfectly. I already have a filtered
> result per class and there are indexes for all the joins available so it
> should be quite fast.

You might also want to look at the operations described in IMerge of the 
BTrees package.

class IMerge(Interface):
     """Object with methods for merging sets, buckets, and trees.

     These methods are supplied in modules that define collection
     classes with particular key and value types. The operations apply
     only to collections from the same module.  For example, the
     IIBTree.union can only be used with IIBTree.IIBTree,
     IIBTree.IIBucket, IIBTree.IISet, and IIBTree.IITreeSet.

     The implementing module has a value type. The IOBTree and OOBTree
     modules have object value type. The IIBTree and OIBTree modules
     have integer value types. Other modules may be defined in the
     future that have other value types.

     The individual types are classified into set (Set and TreeSet) and
     mapping (Bucket and BTree) types.
     """

     def difference(c1, c2):
         """Return the keys or items in c1 for which there is no key in
         c2.

         If c1 is None, then None is returned.  If c2 is None, then c1
         is returned.

         If neither c1 nor c2 is None, the output is a Set if c1 is a Set or
         TreeSet, and is a Bucket if c1 is a Bucket or BTree.
         """

     def union(c1, c2):
         """Compute the Union of c1 and c2.

         If c1 is None, then c2 is returned, otherwise, if c2 is None,
         then c1 is returned.

         The output is a Set containing keys from the input
         collections.
         """

     def intersection(c1, c2):
         """Compute the Intersection of c1 and c2.

         If c1 is None, then c2 is returned, otherwise, if c2 is None,
         then c1 is returned.

         The output is a Set containing matching keys from the input
         collections.
         """


--
Steve Alexander