The Intersection



IndexISect class

We need to know where the Objectivity containers are located to be able to extract data quickly. The Index provides us with a list of nodes for each Sky Domain and each Flux Domain.

We represent the nodes of the Index in the IndexISect class.

Data Members

Each bit in the BitList represents a Leaf Node of the Sky/Flux index. If it is set, the query has to be run on that Database/Container.

Member Functions

Logical operations need to be provided on this class, to get the list of Databases/Containers for a whole Predicate Tree which may consist of several Sky/Flux Domains, connected by logical AND or ORs.

Intersection class

The information whether a Container or a Database lies fully within a Query Volume or not can be stored if we store 4 IndexISect objects for a Predicate Tree:
 

Full – Every object in every Database/Containers given by this IndexISect is hit by the Sky/Flux domains in the Predicate Tree (requirements of Sky and Flux Domains intrinsically fulfilled)

FullSky – Every object in the Database/Containers of this IndexISect already fulfills the Sky Domain requirement of the Predicate Tree (only run Flux predicate)

FullFlux – Every object in the Database/Containers of this IndexISect already fulfills the Flux Domain requirement of the Predicate Tree (only run Sky predicate)

Partial – Queries with both Flux and Sky predicates have to be run on the Database/Containers of this IndexISect

 
The Intersection class is appended to the Predicate Tree Leaf Node of the Query Tree.
 

Logical operations on the Intersection class

The AND and OR operations between Intersection Objects are highly nontrivial. Espetially to maintain a consistent OR may result in loosing lots of information. Such inefficient OR operations will be declared as new Query Tree Nodes (Unions) and the left and right branches will be defined as new Predicate Tree Leaf Nodes with their own Intersection objects.

Consider two Intersection objects (f1, fs1, ff1, p1) and (f2, fs2, ff2, p2).

AND

The resulting object (f, fs, ff, p) is given as follows:
 

f     =     f1 && f2

fs   =     f1 && fs2 || fs1 && f2 || fs1 && fs2

ff    =     f1 && ff2 || ff1 && f2 || ff1 && ff2

p    =     p1 && f2 || p1 && fs2 || p1 && ff2 ||

                f1 && p2 || fs1 && p2 || ff1 && p2 ||

                fs1 && ff2 || ff1 && fs2 || p1 && p2

 
For very special cases this may still lead into non-distinct classes, i.e. the same Database/Container bit is set in more than just one of these 4 classes. It may be set in a pair of (p,[f or ff or fs]). If this case occurs, all bits of [f or ff or fs] are placed into p to keep consistency.

OR

This operation is only meaningful in certain cases, but it can be always carried out correcty.
 

1. If both Intersections have all SkyBits set or both Intersections have all FluxBits set then
 

(f, fs, ff, p) = [(f1||f2, fs1||fs2, ff1||ff2, p1||p2)]

 
where the bracket means to keep consistency. Every bit that is set in f must not be set in (fs, ff, p). Every bit set in fs must not be set in (ff, p) and every bit set in ff must not be set in p. These bit-clearances may be done only in this special case.
 

2. If one of the Intersections (say the first) has either all Sky Bits set or all Flux Bits set

(f, fs, ff) = (f1, fs1, ff1)

p = p1 || f2 || fs2 || ff2 || p2     &&     !(f1, fs1, ff1)

i.e. place all bits not in f1, fs1, ff1 but in either p1 or one of the IndesISect's of the second Intersection into p.

 
3. If both are just partially filled, just keep the one with the most set bits and proceed with point 2.

Of course, cases 2 and 3 are very inefficient. Information on the second Intersection object are completely lost. Also, some of the Database/Container combinations that appear in p may not be intersecting with the query at all. The procedure how to deal with cases 2 and 3 is described above: replace the OR with a Union and create two Predicate Tree leaves with separate Intersection objects.