We represent the nodes of the Index in the IndexISect class.
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.
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.
Consider two Intersection objects (f1, fs1, ff1, p1) and (f2, fs2, ff2, p2).
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.
This operation is only meaningful in certain cases, but it can be always
carried out correcty.
(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.