Patent ID: 6334125
Filing Date: 2001-12-25
Classification: G06F,Y10S

Abstract:
A device for updating a cube forest F, which is a collection of indices I.sub.1, . . . , I.sub.n having a plurality of templates T.sub.1, . . . , T.sub.n, each of which template is a tree having a plurality of spines with a plurality of nodes, and the plurality of nodes of the tree represent aggregate values to be updated with a single tuple, comprising:a) means for forming a catenated key for an index, as determined by a sequence of template nodes on a spine of the index;b) means for descending the index using a B-tree search algorithm and for searching for the catenated key, including:(i) means for searching, at every node that the descent touches, for an effective leaf that is tagged by a subkey of the catenated key;(ii) means for updating, if such an effective leaf is found, any aggregates at the effective leaf;(iii) means for updating recursively any subindices at the effective leaf; and(iv) means for marking the subkey as processed;c) means for inserting, after the descent, if there is an unprocessed subkey, the catenated key into the index;d) means for creating a plurality of effective leaves for all unprocessed subkeys and inserting them into the node;e) means for restructuring, if the node becomes too full after inserting, the index using a B-tree restructuring algorithms; andf) means for moving, after each restructuring step, effective leaves as necessary to ensure that the effective leaf location invariant is preserved.