[ZODB-Dev] n-way join algoritms
Steve Alexander
steve at cat-box.net
Sun Jun 22 18:57:34 EDT 2003
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
More information about the ZODB-Dev
mailing list