Method for matching XML twigs using index structures and relational query processors

• US 20060053122A1
• Filed: 09/09/2004
• Published: 03/09/2006
• Est. Priority Date: 09/09/2004
• Status: Abandoned Application

• Current Assignee: AT&T Corporation (AT&T, Inc.), Cornell Research Foundation Incorporated (Cornell University)
• Original Assignee: Cornell Research Foundation Incorporated (Cornell University)
• Inventors: Srivastava, Divesh, Koudas, Nikolaos, Gehrke, Johannes, Korn, Philip Russell, Shanmugasundaram, Jayavel, Chen, Zhiyuan
• Application Number:
  US10/937,641
• Publication Number:
  US 20060053122A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/84 Mapping; Conversion

Abstract

A framework defining a family of index structures useful in evaluating XML path expressions (i.e., twigs) in XML database is disclosed. Within this framework, two particular index structures with different space-time tradeoffs are presented that prove effective for the evaluation of twigs with value conditions. These index structures can be realized using access methods of an underlying relational database system. Experimental results show that the indices disclosed achieve significant improvement in performance for evaluating twig queries as compared with previously proposed XML path indices.

Claims

1. A data processing method for indexing a tree-structured database, D, storing a plurality of XML documents, D comprising an ordered plurality of nodes, said nodes in D being selected from the group comprising element nodes, attribute nodes and value nodes, each of said nodes in D having a respective node id, d_i, said nodes in D being selectively connected by edges, a data path in D comprising one or more edges, D including at least one root node, a plurality of leaf nodes, and a plurality of root-to-leaf paths, each data path in D comprising a schema path and, when a data path in D reaches a leaf node, a leaf value, said element nodes having respective tags, said attribute nodes having respective attribute names, said schema path comprising only element tags and attribute names, the method comprising

generating a set of representations of data paths that are subpaths of said root-to-leaf paths, each said data path having a representation in said set of representations being associated with the node at which it is rooted, said representations of subpaths included in said set of representations comprising SchemaPath, LeafValue, and IdList information for each respective subpath, where IdList is the list of all node ids along the schema path, except for the HeadId, where HeadId is the node id of the node at the start of the data path,

generating an index based on the concatenation of LeafValue and the reverse of SchemaPath, said index returning at least a portion of said IdList for each data path having a representation in said set of representations.

2. The method of claim 1 wherein said index is a B+-tree index.

3. The method of claim 1 wherein said data paths are parent-child (PC) data paths.

4. The method of claim 1 wherein said concatenation of LeafValue and the reverse of SchemaPath includes only the concentration of LeafValue and prefixes of said root-to-leaf paths.

5. The method of claim 1 wherein said concatenation further includes HeadId.

6. The method of claim 5 wherein said reverse of SchemaPath includes all subpaths of said root-to-leaf paths.

7. The method of claim 1 wherein said index returns the entire IdList for each data path having a representation in said set of representations.

8. The method of claim 1 further comprising compressing IdLists.

9. The method of claim 8 wherein said compressing comprises differentially encoding said IdLists.

10. The method of claim 1 further comprising compressing schema paths.

11. The method of claim 10 wherein said compressing comprises performing dictionary encoding of each of said schema paths into integer ids.

12. A data processing method for matching at least one query to XML twigs in a tree-structured database, D, storing a plurality of XML documents, D comprising an ordered plurality of nodes, said nodes in D being selected from the group comprising element nodes, attribute nodes and value nodes, each of said nodes in D having a respective node id, d_i, said nodes in D being selectively connected by edges, a data path in D comprising one or more edges, D including at least one root node, a plurality of leaf nodes, and a plurality of root-to-leaf paths, each data path in D comprising a schema path and, when a data path in D reaches a leaf node, a leaf value, said element nodes having respective tags, said attribute nodes having respective attribute names, said schema path comprising only element tags and attribute names, the method comprising

applying said at least one query to a relational database management system, RDBMS, said RDBMS storing an index based on a set of representations of data paths in D that are subpaths of said root-to-leaf paths, each said data path having a representation in said set of representations being associated with the node at which it is rooted, said representations of subpaths included in said set of representations comprising SchemaPath, LeafValue, and IdList information, where IdList is the list of all node ids along the schema path, except for the HeadId, where HeadId is the node id of the node at the start of the data path, said index being the concatenation of LeafValue and the reverse of SchemaPath said index returning at least a portion of said IdList for each data path having a representation in said set of representations,

processing said at least one query in a relational query processor in said RDBMS to identify twigs in D matching said at least one query.

13. The method of claim 12 wherein said index is a B+-tree index.

14. The method of claim 12 wherein said data paths are parent-child (PC) data paths.

15. The method of claim 12 wherein said concatenation of LeafValue and the reverse of SchemaPath includes only the concatenation of LeafValue and prefixes of said root-to-leaf paths.

16. The method of claim 12 wherein said concatenation further includes HeadId.

17. The method of claim 16 wherein said reverse of SchemaPath includes all subpaths of said root-to-leaf paths.

18. The method of claim 12 wherein said index returns the entire IdList for each data path having a representation in said set of representations.

19. The method of claim 12 wherein said IdLists comprise compressed IdLists.

20. The method of claim 19 wherein said compressed IdLists comprise differentially encoded IdLists.

21. The method of claim 12 wherein said schema paths comprise compressed schema paths.

22. The method of claim 21 wherein said compressed schema paths comprise dictionary-encoded schema paths.

23. The method of claim 12 wherein said applying said at least one query to said RDBMS comprises receiving at least one parent-child subpath (PCsubpath) pattern P, P comprising n node labels and at least one specific database node id d.

24. The method of claim 23 wherein said at least one query comprises at least one recursive query.

25. The method of claim 23 wherein said processing said at least one query in a relational query processor in said RDBMS comprises a single index lookup to identify all n-tuples (d₁, . . . , d_n) that identify matches of P in D, which matches are rooted at node d.

26. The method of claim 12 wherein said processing said at least one query in a relational query processor comprises receiving a plurality of parent-child subpath (PCsubpath) patterns P_i, 2<

i<

N, each P_i comprising a plurality of node labels and at least one specific database node id d_i,

a single index lookup to identify all n-tuples that identify matches of any P_i in D, which matches are rooted at node d_i, and

performing index-nested-loop join operations on at least some of said matches.