Techniques for efficiently storing and querying in a relational database, XML documents conforming to schemas that contain cyclic constructs

• US 7,523,131 B2
• Filed: 02/10/2005
• Issued: 04/21/2009
• Est. Priority Date: 02/10/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Manikutty, Anand, Arora, Vikas, Zhang, Hui, Angrish, Rohan, Agrawal, Abhyudaya, Warner, James W., Murthy, Ravi, Krishnaprasad, Muralidhar, Agarwal, Nipun, Liu, Zhen Hua, Kotsovolos, Susan M.
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Ng; Amy
• Application Number:
  US11/056,312
• Publication Number:
  US 20060179068A1
• Time in Patent Office: 1,531 Days
• Field of Search: 707/2, 707/104.1, 707/100, 707/102, 707/3, 707/4, 707/101, 715/500, 715/234
• US Class Current: 1/1
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

To associate XML data objects (“child objects”), stored in rows of relational or object-relational tables, with the appropriate XML data objects (“parent objects”) from which the child objects descend, tables that contain child objects (“out-of-line” tables) are constructed with an additional column. In one embodiment, this column stores values that identify the root objects, in the appropriate table, from which the respective child objects descend. Hence, the root object from which any given object descends is traceable by following the respective value back to the corresponding root object. In one embodiment, this column stores values that identify the complete XML hierarchical path, through multiple tables, back to the root object from which the respective child objects descend. Consequently, XML query language queries against XML documents stored in such tables can be rewritten as SQL queries against the data in the tables, even in the presence of cyclic constructs.

Claims

1. A computer-implemented method for storing XML documents in a relational database, the method comprising:

populating a first table and a second table, which are stored within said relational database on a storage medium, with data from an XML document that conforms to an XML schema, wherein the document contains an occurrence of a root element type and a first occurrence of a second element type and a second occurrence of said second element type;

wherein the first and second occurrences that descend from the occurrence of a root element type;

wherein the step of populating comprises;

a processor storing a record in the first table, wherein the record in the first table corresponds with at least the occurrence of the root element type; and

storing a first record in the second table, wherein the first record in the second table corresponds with the first occurrence of the second element type;

storing a second record in the second table, wherein the second record corresponds to said second occurrence of the second element type that descends from the first occurrence of the second element type;

wherein each of the first record and the second record in the second table includes a value that identifies the record in the first table; and

wherein the first table is a separate table than the second table;

wherein the schema describes a cyclic construct and the XML document contains a cyclic construct of which the first and second occurrences of the second element type is part.

2. The method of claim 1, the method further comprising:

receiving an XML query language query that specifies a path for selecting the occurrence of the second element type; and

based on the query, generating a SQL query that accesses the first and second tables, wherein the SQL query includes a join operation on the record in the first table and the first record in the second table.

3. The method of claim 2, wherein the query is an XPath query.

4. The method of claim 2, wherein the query is an XQuery query.

5. The method of claim 2, wherein the step of generating a SQL query includes generating a SQL query that includes a join operation based on a join key column, in the first table, that stores an identifier of the record in the first table and a join key column, in the second table, that stores the value that identifies the record in the first table.

6. The method of claim 2, wherein the query includes a descendent-or-self operator between the second element type and the root element type.

7. The method of claim 6, wherein the step of generating a SQL query includes generating a SQL query that includes a join operation based on a join key column, in the first table, that stores an identifier of the record in the first table and a join key column, in the second table, that stores the value that identifies the record in the first table.

8. The method of claim 1, the method further comprising:

populating a third table with data from the XML document, wherein the document contains an occurrence of a third element type that descends immediately from the first occurrence of the second element type; and

wherein the step of populating the third table includes;

storing a record in the third table, wherein the record in the third table includes a value that identifies a path to the record in the first table, wherein the path identifies the first record in the second table and the record in the first table.

9. The method of claim 8, wherein the first record in the second table includes a value that identifies the record, in the third table, that corresponds with the occurrence of the third element type.

10. The method of claim 1, wherein the second table contains records that correspond to each respective occurrence of the second element type in the XML document.

11. The method of claim 1, wherein, in the XML document, the first occurrence of the second element type descends immediately from the occurrence of the root element type.

12. The method of claim 1, wherein, in the XML document, the first occurrence of the second element type does not descend immediately from the occurrence of the root element type.

13. The method of claim 1, further comprising:

determining that the XML document contains a cyclic construct; and

wherein the steps of storing the record in the first table and storing the first record in the second table are performed in response to determining that the XML document contains a cyclic construct.

14. The method of claim 1, wherein the second table contains records that correspond to each respective occurrence of the second element type in the XML document, and wherein the first record in the second table includes a value that identifies the second record in the second table.

15. The method of claim 14, wherein the second record in the second table includes a value that identifies the first record in the second table.

16. A machine-readable storage medium storing 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.

17. A machine-readable storage medium storing 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.

18. A machine-readable storage medium storing 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.

19. A machine-readable storage medium storing 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.

20. A machine-readable storage medium storing 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.

21. A machine-readable storage medium storing 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.

22. A machine-readable storage medium storing 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.

23. A machine-readable storage medium storing 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.

24. A machine-readable storage medium storing 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.

25. A machine-readable storage medium storing 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.

26. A machine-readable storage medium storing 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.

27. A machine-readable storage medium storing 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.

28. A machine-readable storage medium storing 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.

29. A machine-readable storage medium storing 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.

30. A machine-readable storage medium storing 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.