Index Structure for Supporting Structural XML Queries

• US 20070271243A1
• Filed: 07/19/2007
• Published: 11/22/2007
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: Haixun Wang, Philip Yu, Wei Fan
• Original Assignee: Haixun Wang, Philip Yu, Wei Fan
• Inventors: Fan, Wei, Wang, Haixun, Yu, Philip
• Granted Patent: US 7,890,471 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The present invention provides a ViST (or “virtual suffix tree”), which is a novel index structure for searching XML documents. By representing both XML documents and XML queries in structure-encoded sequences, it is shown that querying XML data is equivalent to finding (non-contiguous) subsequence matches. A variety of XML queries, including those with branches, or wild-cards (‘*’ and ‘//’), can be expressed by structure-encoded sequences. Unlike index methods that disassemble a query into multiple sub-queries, and then join the results of these sub-queries to provide the final answers, ViST uses tree structures as the basic unit of query to avoid expensive join operations. Furthermore, ViST provides a unified index on both content and structure of the XML documents, hence it has a performance advantage over methods indexing either just content or structure. ViST supports dynamic index update, and it relies solely on B⁺Trees without using any specialized data structures that are not well supported by common database management systems (hereinafter referred to as “DBMSs”).

Claims

1. A method of generating a virtual suffix tree (ViST) structure for searching XML documents, comprising:

receiving one or more XML documents;

converting the one or more XML documents into one or more structure-encoded sequences; and

generating the ViST structure comprising;

generating a D-Ancestor index;

generating an S-Ancestor index; and

generating a doc-ID index.

2. The method of claim 1, wherein generating a D-Ancestor index comprises generating a D-Ancestor B⁺Tree, wherein the D-Ancestor B⁺Tree indexes one or more (key, data) pairs and wherein the key element is a unique (symbol,path) pair in the one or more structure-encoded sequences, and the data element is a pointer to an S-Ancestor B+Tree.

3. The method of claim 1, wherein generating the S-Ancestor index comprises generating an S-Ancestor B⁺Tree, wherein the S-Ancestor B⁺Tree indexes one or more keys, wherein each of the one or more keys is a pair [begin-ID,end-ID].

4. The method of claim 3, wherein IDs of descendent nodes of a node whose label is [begin-ID,end-ID] are in the range of [begin-ID,end-ID].

5. The method of claim 1, wherein generating a doc-ID index comprises generating a doc-ID B⁺Tree, wherein the doc-ID B⁺Tree indexes one or more (key,data) pairs and wherein the key element is a node ID, and the data element is a list of XML document IDs.

6. A method of answering an XML query, comprising:

receiving an XML query;

transforming the XML query into a structure-encoded sequence;

searching a virtual suffix tree (ViST) structure using the structure-encoded sequence and returning one or more document IDs.

7. The method of claim 6, wherein searching a ViST structure using the structure encoded sequence, comprises:

(a). assuming the query sequence is <

q_—

1,q_—

2, . . . ,q_n>

;

(b) assigning. i=1,begin=0,end=infinity;

(c) searching a D-Ancestor B⁺Tree using key q_i, which returns an S-Ancestor B⁺Tree; and

(d) performing a range search (begin,end) on the S-Ancestor B⁺Tree,

wherein performing the range search comprises;

(e) returning a set of ranges (x.sub.--1,y.sub.--1), . . . ,(x_n,y_n);

(f) for each (x_i,y_i) doing (g) and (h);

(g) if (i=n) then

performing a range query (x_i,y_) on the doc-ID index and returning one or more document IDs;

(h) if (i<

n) then

assigning i=i+1;

begin=x_i,end=y_i;

going to (c).

8. A method of dynamically updating a virtual suffix tree (ViST) structure, comprising

receiving a new XML document;

transforming the XML document into a structure-encoded sequence;

inserting each element of the sequence into D-Ancestor B⁺Tree;

assigning a new label if the step of inserting creates a new node; and

inserting the new label into the S-Ancestor B⁺Tree.

9. The method of claim 8, further comprising assigning a new label if the step of inserting creates a new node.

10. The method of claim 8, wherein inserting the new label into the S-Ancestor B⁺Tree comprises inserting the new label (x,y) into the S-Ancestor B⁺Tree.

11. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method of generating a virtual suffix tree (ViST) structure for searching XML documents, comprising the steps of:

receiving one or more XML documents;

converting the one or more XML documents into one or more structure-encoded sequences;

generating the ViST structure comprising;

generating a D-Ancestor index;

generating an S-Ancestor index; and

generating a doc-ID index.

12. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method answering an XML query, comprising the steps of:

receiving an XML query;

transforming the XML query into a structure-encoded sequence;

searching a virtual suffix tree (ViST) structure using the structure-encoded sequence and returning one or more document IDs.

13. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method of dynamically updating the virtual suffix tree (ViST) structure, comprising the steps of:

receiving a new XML document transforming the XML document into a structure-encoded sequence inserting each element of the sequence into D-Ancestor B⁺Tree;

assigning a new label if the step of inserting creates a new node; and

inserting the new label into the S-Ancestor B⁺Tree.