Optimizations of XPaths

• US 7,877,400 B1
• Filed: 11/18/2003
• Issued: 01/25/2011
• Est. Priority Date: 11/18/2003
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Marcus, Matthew
• Primary Examiner(s): Saeed; Usmaan
• Application Number:
  US10/716,840
• Time in Patent Office: 2,625 Days
• Field of Search: 707/3, 707/10, 707/6
• US Class Current: 707/758
• CPC Class Codes: G06F 16/8373 Query execution

Abstract

Methods and apparatus, including computer program products, for searching for one or more logical elements in a hierarchical tree structure of an extended markup language document conforming to a schema used for XML. The method includes the steps of (1) providing a representation of an extended markup language document instance containing two or more logical elements, one being a parent node and one a child node in a hierarchical tree structure describing the representation; (2) receiving a query for logical elements satisfying an XPath expression; and (3) searching in the hierarchical tree structure only nodes that potentially have child nodes satisfying the XPath expression.

Claims

1. A method for searching for one or more logical elements in a hierarchical tree structure of an extensible markup language (XML) document conforming to a schema used for XML, comprising:

providing a representation of an XML document instance containing two or more logical elements, wherein at least one logical element is a parent node and at least one logical element is a child node in a hierarchical tree structure describing the representation;

receiving a query for logical elements satisfying an XPath expression;

searching in the hierarchical tree structure only nodes that potentially have child nodes satisfying the XPath expression; and

providing the logical elements satisfying the XPath expression.

2. The method of claim 1, including the further step of generating a collection of parent nodes that potentially have child nodes satisfying the XPath expression from a table relating a class of parent nodes and a class of child nodes, and wherein the table is used in the final searching step.

3. The method of claim 1, including the further step of generating a collection of parent nodes that potentially have child nodes satisfying the XPath expression from a table relating parent nodes and child nodes, and wherein the table is used in the searching step.

4. The method of claim 2, wherein the table comprises entries containing hash representations of a class of parent nodes and a class of child nodes.

5. The method of claim 3, wherein the table comprises entries containing hash representations of the parent nodes and child nodes.

6. The method of claim 2, wherein the table comprises a listing of permitted classes of child nodes for each class of parent node.

7. The method of claim 3, wherein the table comprises a listing of child nodes for each parent node.

8. The method of claim 2, wherein the table comprises a listing of permitted classes of parent nodes for each class of child node.

9. The method of claim 3, wherein table comprises a listing of permitted parent nodes for each child node.

10. The method of claim 1, further comprising:

receiving a rule set identifying allowable combinations between child nodes and parent nodes in a hierarchical document structure;

transforming the rule set into a table relating a class of parent nodes and a class of child nodes; and

using the table in the searching step.

11. The method of claim 1, further comprising:

receiving a rule set identifying allowable combinations between child nodes and parent nodes in a hierarchical document structure;

transforming the rule set into a table relating parent nodes and child nodes; and

using the table in the searching step.

12. The method of claim 10, wherein:

the rule set includes one of;

an XML schema, a DTD, and a RelaxNg schema.

13. The method of claim 11, wherein:

the rule set includes one of;

an XML schema, a DTD, and a RelaxNg schema.

14. The method of claim 2, wherein the table includes a listing of a not-permitted class of child nodes for each class of parent node.

15. The method of claim 3, wherein the table includes a listing of not-permitted child nodes for each parent node.

16. The method of claim 2, wherein the table includes a listing of a not-permitted class of parent nodes for each class of child node.

17. The method of claim 3, wherein the table includes a listing of a not-permitted parent nodes for each child node.

18. The method of claim 1, further comprising the additional steps of:

receiving a rule set identifying non-allowable combinations between child nodes and parent nodes in a hierarchical document structure; and

transforming the rule set into a table relating a class of parent nodes and a class of child nodes.

19. The method of claim 1, further comprising the additional steps of:

receiving a rule set identifying non-allowable combinations between child nodes and parent nodes in a hierarchical document structure; and

transforming the rule set into a table relating parent nodes and child nodes.

20. A computer program product, tangibly encoded on a computer-readable storage medium, for searching for one or more logical elements in a hierarchical tree structure of an extensible markup language (XML) document conforming to a schema used for XML, comprising instructions operable to cause a programmable processor to:

provide a representation of an XML document instance containing two or more logical elements, wherein at least one logical element is a parent node and at least one logical element is a child node in a hierarchical tree structure describing the representation;

receive a query for logical elements satisfying an XPath expression;

search in the hierarchical tree structure only nodes that potentially have child nodes satisfying the math expression; and

provide the logical elements satisfying the XPath expression.

21. The computer program product of claim 20, wherein the instructions cause a programmable processor to generate a collection of parent nodes that potentially have child nodes satisfying the XPath expression from a table relating a class of parent nodes and a class of child nodes, and wherein the instructions cause the table to be used in the search.

22. The computer program product of claim 20, wherein the instructions cause a programmable processor to generate a collection of parent nodes that potentially have child nodes satisfying the XPath expression from a table relating parent nodes and child nodes, and wherein the instructions cause the table to be used in the search.

23. The computer program product of claim 21, wherein the table comprises entries containing hash representations of the class of parent nodes and class of child nodes.

24. The computer program product of claim 22, wherein the table comprises entries containing hash representations of the parent nodes and child nodes.

25. The computer program product of claim 22, wherein the table comprises a listing of a permitted class of child nodes for each class of parent node.

26. The computer program product of claim 21, wherein the table comprises a listing of permitted child nodes for each parent node.

27. The computer program product of claim 21, wherein the table comprises a listing of a permitted class of parent nodes for each class of child node.

28. The computer program product of claim 22, wherein the table comprises a listing of permitted parent nodes for each child node.

29. The computer program product of claim 20, further comprising instructions to:

receive a rule set identifying allowable combinations between a class of child nodes and a class of parent nodes in a hierarchical document structure;

transform the rule set into a table relating the class of parent nodes and the class of child nodes; and

use the table in the search.

30. The computer program product of claim 20, further comprising instructions to:

receive a rule set identifying allowable combinations between child nodes and parent nodes in a hierarchical document structure;

transform the rule set into a table relating parent nodes and child nodes; and

use the table in the search.

31. The computer program product of claim 29, wherein:

the rule set includes one of;

an XML schema, a DTD, and a RelaxNg schema.

32. The computer program product of claim 30, wherein:

the rule set includes one of;

an XML schema, a DTD, and a RelaxNg schema.

33. The computer program product of claim 21, wherein the wherein the table includes a listing of a class of not-permitted child nodes for each class of parent node.

34. The computer program product of claim 22, wherein the wherein the table includes a listing of not-permitted child nodes for each parent node.

35. The computer program product of claim 21, wherein the wherein the table includes a listing of a class of not-permitted parent nodes for each class of child node.

36. The computer program product of claim 22, wherein the wherein the table includes a listing of not-permitted parent nodes for each child node.

37. The computer program product of claim 20, further comprising instructions to:

receive a rule set identifying non-allowable combinations between a class of child nodes and a class of parent nodes in a hierarchical document structure; and

transform the rule set into a table relating the class of parent nodes and the class of child nodes.

38. The computer program product of claim 20, further comprising instructions to:

receive a rule set identifying non-allowable combinations between child nodes and parent nodes in a hierarchical document structure; and

transform the rule set into a table relating parent nodes and child nodes.