Efficient queribility and manageability of an XML index with path subsetting

• US 20050228791A1
• Filed: 02/15/2005
• Published: 10/13/2005
• Est. Priority Date: 04/09/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sedlar, Eric, Thusoo, Ashish, Chandrasekar, Sivasankaran, Murthy, Ravi, Agarwal, Nipun, Mukkamalla, Sreedhar, Koo, Reema
• Granted Patent: US 7,493,305 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: G06F 16/8365 Query optimisation
• CPC Class Codes: G06F 16/8373 Query execution
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and system are provided for determining whether a given path is an indexed path of XML documents stored in a database management system. A finite state machine is built using the path subsetting rules specified by a user. The finite state machine is traversed using the given path. If any accepting states are reached during the traversal of the finite state machine, the given path is determined to matching the path subsetting rules.

Claims

1. A method determining whether an input path matches a path subsetting rule used to create a path-based index for a set of XML documents, wherein the path subsetting rule includes a set of path expressions, said set of path expressions represented by a finite state machine, said finite state machine including a plurality of states and a start state, said method comprising the computer-implemented steps of:

(a) receiving an input path comprised of a sequence of location step components;

(b) setting a’

current state of the finite state machine to the start state;

(c) setting a current location step component to a first location step component of the input path;

(d) setting the current state of the finite state machine to a state determined by traversing the finite state machine for the current location step component;

(e) if the current state of the finite state machine is an accepting state, determining that the received input path matches the path subsetting rule, and if the current state of the finite state machine is not an accepting state, performing the steps of;

(i) if there is a next location step component in the input path, then setting the current path expression component to the next location step component and repeating steps (d) and (e); and

(iii) if there is not a next location step component in the input path, then determining that the input path does not match the path subsetting rule.

2. The method of claim 1 wherein if it is determined that the input path matches the path subsetting rule, the method further including the step of:

determining that the input path is a path indexed by the path-based index.

3. The method of claim 1 wherein if it is determined that the input path matches the path subsetting rule, the method further including the step of:

determining that the input path is not a path indexed by the path-based index.

4. The method of claim 1 wherein a location step component is comprised of an axis and a node test.

5. The method of claim 4, wherein said axis is selected from the group consisting of a parent child axis and a descendent-or-self axis.

6. The method of claim 4, wherein said node test is selected from the group consisting of an element name and a wildcard symbol.

19. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

20. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

21. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

22. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

23. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

24. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

7. A method of determining whether an input path matches a path subsetting rule that was used to create a path-based index for a set of XML documents, said method comprising the computer-implemented steps of:

creating a finite state machine that represents the path subsetting rule;

traversing the finite state machine using the input path; and

if an accepting state of the finite state machine is reached while traversing the finite state machine, then determining that the input path matches the path subsetting rule.

8. The method of claim 7 wherein the path subsetting rule is an inclusion rule, wherein if an accepting state of the finite state machine is reached, the method further including the step of:

determining that the input path is a path indexed by the path-based index.

9. The method of claim 8 further comprising:

determining based on determining that the input path is indexed, using the path-based index to access information within the set of XML documents that is associated with the input path.

10. The method of claim 7 wherein the path subsetting rule is an exclusion rule, wherein if an accepting state of the finite state machine is reached, the method further including the step of:

determining that the input path is not a path indexed by the path-based index.

11. The method of claim 7 wherein the finite state machine is a combined non-deterministic automaton that represents a set of path expressions specified in the path subsetting rule.

12. The method of claim 11 wherein the finite state machine includes multiple accepting states.

13. The method of claim 12 wherein if an accepting state that represents an ancestor of the input path is reached, then determining that the input path matches the path subsetting rule.

14. The method of claim 7, wherein said input path is a path expression from a path-based query, wherein if the input path matches the path subsetting rule, then determining that the path-based query can be satisfied using the path-based index.

15. The method of claim 7, wherein said received input path is a path in an XML document being added to the set of XML documents, wherein if the received input path matches the path subsetting rules, then determining that the path in the XML document should be added to the path-based index.

16. The method of claim 15, additionally comprising the step of determining that all ancestors of the path in the XML document should be added to the path-based index.

17. The method of claim 7 wherein the path-based index includes path, value and order indexes.

18. The method of claim 7, wherein the path subsetting rules are specified through a parameter when the path-based index is created.

25. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

26. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

27. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

28. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

29. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

30. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

31. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

32. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

33. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

34. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

35. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

36. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.