Patent ID: 7346625

Claim:
A method for use in a tree-structured document query processing system for performing structural joins of two element sets of a tree-structered document, wherein one of the two element sets is an ancestor element set and the other of the two element sets is a descendant element set, and further wherein each element is represented as an interval representing a start position and an end position of the element in the document, comprising the steps of: dynamically building an index for the ancestor element set; and performing one or more structural joins by searching the index with the interval start position of each element in the descendant element set; wherein the step of dynamically building an index for the ancestor element set further comprises the steps of: partitioning an interval range among the elements in the ancestor set into one or more segments of a fixed size; defining a set of containment-encoded virtual intervals for each segment; decomposing each ancestor interval element into one or more containment-encoding virtual intervals; and associating an ancestor interval identifier with identifier lists associated with the decomposed virtual intervals; further wherein the step of defining a set of virtual intervals for each of the one or more segments further comprises the steps of: defining a virtual interval which covers the segment and labeling the virtual interval with a first local identifier; partitioning the segment into two equal-length virtual intervals and respectively labeling the two equal-length virtual intervals from left to right with second and third local identifiers; partitioning the segment into four equal-length virtual intervals and respectively labeling the four equal-length virtual intervals from left to right with fourth, fifth, sixth and seventh local identifiers; and continuing the partitioning step until each virtual interval has a length of one; still further wherein the defining step further comprises the containment-encoded virtual intervals (CEIs) for each segment having a local identifier (ID) and a global ID, and for a CEI with a local ID of m, the CEI containing two half-sized CEIs with local IDs of 2 m and 2 m+ 1; yet further wherein results of the performance of the one or more structural joins are useable to process a query of the tree-structured document.