Index structure for supporting structural XML queries

• US 7,890,471 B2
• Filed: 07/19/2007
• Issued: 02/15/2011
• Est. Priority Date: 11/26/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fan, Wei, Wang, Haixun, Yu, Philip Shi-Lung
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Hocker; John P
• Application Number:
  US11/780,095
• Publication Number:
  US 20070271243A1
• Time in Patent Office: 1,307 Days
• Field of Search: 707100-102, 707/673, 707/E17.122, 707/E17.127, 707/999.1
• US Class Current: 707/673
• 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 respective structure-encoded sequences;

generating the ViST structure comprising;

generating a D-Ancestor index of node pairs in the respective structure-encoded sequences;

generating an S-Ancestor index of labels in one or more suffix trees corresponding to respective ones of the structure-encoded sequences; and

generating a doc-ID index encoding the D-Ancestor index and the S-Ancestor index for each node of the structure-encoded sequences, wherein the encoding of the doc-ID index contains an answer to a query matching a non-contiguous subsequence in the doc-ID index; and

updating the ViST structure, the updating comprising;

receiving a new XML document;

transforming the new XML document into a respecitve structure-encoded sequence;

inserting each element of the sequence into the D-Ancestor index to update relationships among nodes of the D-Ancestor index wherein the insertion of at least one of the elements results in the creation of a new node;

assigning a new label to the new node based on an estimated number of different elements following the element corresponding to the new node and an occurrence probability of each of the elements following the element corresponding to the new node; and

inserting the new label into the S-Ancestor index.

2. The method of claim 1, wherein generating the 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 the 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 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 respective structure-encoded sequences;

generating the ViST structure comprising;

generating a D-Ancestor index of node pairs in the respective structure-encoded sequences;

generating an S-Ancestor index of labels in one or more suffix trees corresponding to respective ones of the structure-encoded sequences; and

generating a doc-ID index encoding the D-Ancestor index and the S-Ancestor index for each node of the structure-encoded sequences, wherein the encoding of the doc-ID index contains an answer to a query matching a non-contiguous subsequence in the doc-ID index;

updating the ViST structure, the updating comprising;

receiving a new XML document;

transforming the new XML document into a respective structure-encoded sequence;

inserting each element of the sequence into the D-Ancestor index to update relationships among nodes of the D-Ancestor index wherein the insertion of at least one of the elements results in the creation of a new node;

assigning a new label to the new node based on an estimated number of different elements following the element corresponding to the new node and an occurrence probability of each of the elements following the element corresponding to the new node; and

inserting the new label into the S-Ancestor index.

7. The machine-readable medium of claim 6, wherein generating the 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.

8. The machine-readable medium of claim 6, 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].

9. The machine-readable medium of claim 8, wherein IDs of descendent nodes of a node whose label is (begin-ID,end-ID) are in the range of [begin-ID,end-ID].

10. The machine-readable medium of claim 6, wherein generating the 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.