Managing XPath expressions in a database system

• US 7,107,282 B1
• Filed: 02/12/2003
• Issued: 09/12/2006
• Est. Priority Date: 05/10/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Yalamanchi, Aravind
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/365,771
• Time in Patent Office: 1,308 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 717/124
• US Class Current: 707/754
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: Y10S 707/961 Associative
• 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

First data that represents a level associated with an element within an expression, such as an XPath expression, is generated from the expression, and stored in one or more columns of a table. Second data that represents a condition on an attribute of the element is generated from the expression, and stored in one or more columns of the same or a different table. A plurality of expressions can be processed as such, and a determination made whether any of the expressions match with a given hierarchical data item, such as an XML document, that includes a value that corresponds to an attribute that is associated with an element that resides at a particular level within the data item. Such determination is made based on whether the particular level matches the first data and the value satisfies the second data associated with a given expression.

Claims

1. A computer-implemented method for managing expressions in a database, the method comprising the computer-implemented steps of:

receiving a first pathname expression that identifies a particular element within a hierarchical structure and that includes a first conditional expression relating to a particular attribute of the particular element;

generating, based on the first pathname expression, position filter data that represents a level, corresponding to the particular element, within the hierarchical structure;

storing the position filter data in one or more first columns of a database table, for use in determining whether a data item satisfies the first conditional expression in the pathname expression;

generating, based on the first pathname expression, value filter data that represents the first conditional expression relating to the particular attribute of the particular element; and

storing the value filter data in one or more second columns of a database table, for use in determining whether a data item satisfies the first conditional expression in the pathname expression.

2. The method of claim 1, wherein the first pathname expression received is an XPath expression.

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

receiving a hierarchical data item that includes a value that corresponds to an attribute that is associated with an element that resides at a particular level within the hierarchical data item; and

determining whether the hierarchical data item matches the first pathname expression based at least on whether the particular level matches the level represented by the position filter data in the one or more first columns and whether the value satisfies the first conditional expression represented as the value filter data in the one or more second columns.

4. The method of claim 3, wherein the step of determining whether the hierarchical data item matches the first pathname expression includes:

determining that the particular level matches the level represented by the position filter data upon the particular level having a particular logical relationship to the level represented by the position filter data;

wherein the particular logical relationship is selected from a set consisting of equal to, greater than, less than, greater an or equal to, and less than or equal to.

5. The method of claim 3, further comprising the steps of:

receiving a second expression that includes a second conditional expression;

generating, based on the second expression, third data that represents the second conditional expression;

storing the third data in one or more third columns of a database table;

determining whether the hierarchical data item matches the second expression based at least on whether the hierarchical data item satisfies the second conditional expression represented as the third data in the one or more third columns; and

wherein the second expression received is not an XPath expression.

6. The method of claim 5, wherein the first, second and third columns are all in the same table.

7. The method of claim 3, wherein the step of determining whether the hierarchical data item matches the first pathname expression includes the steps of:

parsing the hierarchical data item to obtain levels for elements and values for attributes within the hierarchical data item;

building an array that includes data that represents the elements and their respective levels and that represents the attributes and their respective values; and

issuing a query on the array and the one or more tables that include the one or more first columns and the one or more second columns, to determine whether the hierarchical data item matches the first pathname expression.

8. The method of claim 3, wherein the input document is an XML document and the first pathname expression is an XPath expression.

9. The method of claim 3, wherein the input document is a set of hierarchically structured name-value pairs and the first pathname expression is a pathname associated with the hierarchical structure.

10. The method of claim 3, wherein a plurality of first pathname expressions are received and respective position filter and value filter data generated, and wherein the step of determining includes determining, based on the respective position and value filter data, which of the plurality of first pathname expressions are matched with the hierarchical data item.

11. The method of claim 1, further comprising the step of:

creating a concatenated bitmap index on the one or more first columns of the table.

12. The method of claim 1, further comprising the step of:

creating a concatenated bitmap index on the one or more second columns of the table.

13. The method of claim 1, wherein the one or more first columns and the one or more second columns are in the same table, the method further comprising the step of:

creating a concatenated bitmap index on the one or more first columns of the table and the one or more second columns of the table.

14. The method of claim 1, wherein the step of representing the first level includes representing the first level as a combination of a level constraint and a bounding level.

15. The method of claim 1, wherein the step of representing the first conditional expression include representing the first conditional expression as a combination of a relational operator and a constant.

16. The method of claim 1, further comprising the step of:

representing the first conditional expression in a corresponding original form in one or more fourth columns of the table.

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

receiving a third pathname expression that identifies the particular element within a hierarchical structure;

generating, based on the third pathname expression, position filter data that represents a level associated with the particular element within the hierarchical structure associated with the third pathname expression;

storing the position filter data in the one or more first columns of the database table;

wherein the level associated with the particular element within the first pathname expression is different than the level associated with the particular element within the third pathname expression;

receiving a hierarchical data item that includes a value that corresponds to an attribute that is associated with an element that resides at a particular level within the hierarchical data item;

determining whether the hierarchical data item matches the first expression based at least on whether the particular level matches the level represented by the position filter data corresponding to the first pathname expression in the one or more first columns; and

determining whether the hierarchical data item matches the third expression based at least on whether the particular level matches the level represented by the position filter data corresponding to the third pathname expression in the one or more first columns.

18. An apparatus for managing expressions in a database, comprising:

means for receiving a first pathname expression that identifies a particular element within a hierarchical structure and that includes a first conditional expression relating to a particular attribute of the particular element;

means for generating, based on the first pathname expression, position filter data that represents a level, corresponding to the particular element, within the hierarchical structure;

means for storing the position filter data in one or more first columns of a database table, for use in determining whether a data item satisfies the first conditional expression in the pathname expression;

means for generating, based on the first pathname expression, value filter data that represents the first conditional expression relating to the particular attribute of the particular element; and

means for storing the value filter data in one or more second columns of a database table, for use in determining whether a data item satisfies the first conditional expression in the pathname expression.

19. A computer-readable storage medium carrying one or more sequences of instructions which, when executed, cause one or more processors to perform the steps of:

receiving a first pathname expression that identifies a particular element within a hierarchical structure and that includes a first conditional expression relating to a particular attribute of the particular element;

generating, based on the first pathname expression, position filter data that represents a level, corresponding to the particular element, within the hierarchical structure;

storing the position filter data in one or more first columns of a database table, for use in determining whether a data item satisfies the first conditional expression in the pathname expression;

generating, based on the first pathname expression, value filter data that represents the first conditional expression relating to the particular attribute of the particular element; and

storing the value filter data in one or more second columns of a database table, for use in determining whether a data item satisfies the first conditional expression in the pathname expression.

20. The computer-readable storage medium of claim 19, wherein the first pathname expression received is an XPath expression.

21. The computer-readable storage medium of claim 19, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a hierarchical data item that includes a value that corresponds to an attribute that is associated with an element that resides at a particular level within the hierarchical data item; and

determining whether the hierarchical data item matches the first pathname expression based at least on whether the particular level matches the level represented by the position filter data in the one or more first columns and whether the value satisfies the first conditional expression represented as the value filter data in the one or more second columns.

22. The computer-readable storage medium of claim 21, wherein the instructions causing determining whether the hierarchical data item matches the first pathname expression include instructions causing the one or more processors to perform the steps of:

determining that the particular level matches the level represented by the position filter data upon the particular level having a particular logical relationship to the level represented by the position filter data;

wherein the particular logical relationship is selected from a set consisting of equal to, greater than, less than, greater than or equal to, and less than or equal to.

23. The computer-readable storage medium of claim 21, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a second expression that includes a second conditional expression;

generating, based on the second expression, third data that represents the second conditional expression;

storing the third data in one or more third columns of a database table;

determining whether the hierarchical data item matches the second expression based at least on whether the hierarchical data item satisfies the second conditional expression represented as the third data in the one or more third columns; and

wherein the second expression received is not an XPath expression.

24. The computer-readable storage medium of claim 23, wherein the first, second and third columns are all in the same table.

25. The computer-readable storage medium of claim 21, wherein the instructions causing determining whether the hierarchical data item matches the first pathname expression include instructions causing the one or more processors to perform the steps of:

parsing the hierarchical data item to obtain levels for elements and values for attributes within the hierarchical data item;

building an array that includes data that represents the elements and their respective levels and that represents the attributes and their respective values; and

issuing a query on the array and the one or more tables that include the one or more first columns and the one or more second columns, to determine whether the hierarchical data item matches the first pathname expression.

26. The computer-readable storage medium of claim 21, wherein the input document is an XML document and the first pathname expression is an XPath expression.

27. The computer-readable storage medium of claim 21, wherein the input document is a set of hierarchically structured name-value pairs and the first pathname expression is a pathname associated with the hierarchical structure.

28. The computer-readable storage medium of claim 21, wherein a plurality of first pathname expressions are received and respective position filter and value filter data generated, and wherein the instructions causing determining include instructions causing determining, based on the respective position and value filter data, which of the plurality of first pathname expressions are matched with the hierarchical data item.

29. The computer-readable storage medium of claim 19, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

creating a concatenated bitmap index on the one or more first columns of the table.

30. The computer-readable storage medium of claim 19, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

creating a concatenated bitmap index on the one or more second columns of the table.

31. The computer-readable storage medium of claim 19, wherein the one or more first columns and the one or more second columns are in the same table, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

creating a concatenated bitmap index on the one or more first columns of the table and the one or more second columns of the table.

32. The computer-readable storage medium of claim 19, wherein the instructions causing representing the first level include instructions causing representing the first level as a combination of a level constraint and a bounding level.

33. The computer-readable storage medium of claim 19, wherein the instructions causing representing the first conditional expression include instructions causing representing the first conditional expression as a combination of a relational operator and a constant.

34. The computer-readable storage medium of claim 19, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

representing the first conditional expression in a corresponding original form in one or more fourth columns of the table.

35. The computer-readable storage medium of claim 19, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a third pathname expression that identifies the particular element within a hierarchical structure;

generating, based on the third pathname expression, position filter data that represents a level associated with the particular element within the hierarchical structure associated with the third pathname expression;

storing the position filter data in the one or more first columns of the database table;

wherein the level associated with the particular element within the first pathname expression is different than the level associated with the particular element within the third pathname expression;

receiving a hierarchical data item that includes a value that corresponds to an attribute that is associated with an element that resides at a particular level within the hierarchical data item;

determining whether the hierarchical data item matches the first expression based at least on whether the particular level matches the level represented by the position filter data corresponding to the first pathname expression in the one or more first columns; and

determining whether the hierarchical data item matches the third expression based at least on whether the particular level matches the level represented by the position filter data corresponding to the third pathname expression in the one or more first columns.