Method and mechanism for processing queries for XML documents using an index

• US 20040221226A1
• Filed: 04/30/2003
• Published: 11/04/2004
• Est. Priority Date: 04/30/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Kaminaga, Garrett, Matsuda, Yasuhiro, Lin, Wesley
• Granted Patent: US 7,181,680 B2
• Time in Patent Office: Days
• US Class Current: 715/501.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 40/123 Storage facilities
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

A method and apparatus for processing a query is provided. A query for a set of Matching XML documents is received. A client may transmit the query for a set of XML documents to the database server. The database server transmits a request for the set of XML documents to a persistent storage. The persistent storage uses an index, at least in part, to obtain the set of XML documents sought by the query. The index stores a first set of entries comprising information about the location of elements, a second set of entries comprising information about element attributes, and a third set of entries comprising information about element values. In responding to a particular query, additional XML documents that are not indexed by the index may also be checked to determine if they correspond to the set of search criteria.

Claims

1. A method for processing a query, comprising:

receiving a query for a set of matching XML documents, wherein the set of matching XML documents are XML documents, from a set of XML documents, that satisfy search criteria specified in said query; and

using an index to identify one or more XML documents that qualify as members of said set of matching XML documents, wherein said index stores a first set of entries comprising information about the location of elements, a second set of entries comprising information about element attributes, and a third set of entries comprising information about element values.

2. The method of claim 1, wherein:

said set of XML documents are stored within one or more tables in a database,

said one or more tables store said set of XML documents in a set of indexed rows and a set of non-indexed rows,

said set of indexed rows are indexed by said index, and

said set of non-indexed rows are not indexed by said index.

3. The method of claim 1, wherein said step of using an index comprises:

determining if said query is compatible with said index.

4. The method of claim 3, wherein said step of using an index further comprises:

if said query is not compatible with said index, then modifying said query to produce a modified query for a second set of XML documents, wherein said modified query is compatible with said index; and

wherein said second set of XML documents is a superset of said set of matching XML documents.

5. The method of claim 3, wherein said step of using an index further comprises:

if said query is compatible with said index, then determining if using said index to obtain said set of XML documents is faster than not using said index to obtain said set of XML documents.

6. The method of claim 5, wherein said step of using an index further comprises:

if using said index to obtain said set of XML documents is faster than not using said index to obtain said set of XML documents, then determining membership of at least a subset of said set of matching XML documents using said index.

7. The method of claim 2, further comprising:

determining if any rows in said set of non-indexed rows correspond to said set of search criteria; and

determining membership of at least a subset of said matching set of XML documents based on those rows in said set of non-indexed rows that correspond to said set of search criteria.

8. The method of claim 1, wherein said first set of entries includes for each element a document identification value, an offset value, a length value, a depth value, and a parent offset value.

9. The method of claim 1, wherein said step of using an index comprises:

obtaining a set of potential XML documents that may qualify as members of said set of matching XML documents using, at least in part, said index; and

examining each member of said set of potential XML documents to identify each member in said set of matching XML documents.

10. A method for maintaining an index, comprising:

upon receiving a request to store a particular XML document, storing said particular XML document; and

updating an index to include a reference to said particular XML document, wherein said reference includes a first set of entries comprising information about the location of elements in said particular XML document, a second set of entries comprising information about element attributes in said particular XML document, and a third set of entries comprising information about element values in said particular XML document.

11. The method of claim 10, wherein:

said particular XML document is stored within one or more tables in a database, and

said one or more tables store said particular XML document in a set of indexed row, wherein said indexed rows are indexed by said index.

12. 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 steps of:

receiving a query for a set of matching XML documents, wherein the set of matching XML documents are XML documents, from a set of XML documents, that satisfy search criteria specified in said query; and

using an index to identify one or more XML documents that qualify as members of said set of matching XML documents, wherein said index stores a first set of entries comprising information about the location of elements, a second set of entries comprising information about element attributes, and a third set of entries comprising information about element values.

13. The computer-readable medium of claim 12, wherein:

said set of XML documents are stored within one or more tables in a database,

said one or more tables store said set of XML documents in a set of indexed rows and a set of non-indexed rows,

said set of indexed rows are indexed by said index, and

said set of non-indexed rows are not indexed by said index.

14. The computer-readable medium of claim 12, wherein said step of using an index comprises:

determining if said query is compatible with said index.

15. The computer-readable medium of claim 14, wherein said step of using an index further comprises:

if said query is not compatible with said index, then modifying said query to produce a modified query for a second set of XML documents, wherein said modified query is compatible with said index; and

wherein said second set of XML documents is a superset of said set of matching XML documents.

16. The computer-readable medium of claim 14, wherein said step of using an index further comprises:

if said query is compatible with said index, then determining if using said index to obtain said set of XML documents is faster than not using said index to obtain said set of XML documents.

17. The computer-readable medium of claim 16, wherein said step of using an index further comprises:

if using said index to obtain said set of XML documents is faster than not using said index to obtain said set of XML documents, then determining membership of at least a subset of said set of matching XML documents using said index.

18. The computer-readable medium of claim 13, wherein said sequences of instructions further cause the one or more processors to perform the steps of:

determining if any rows in said set of non-indexed rows correspond to said set of search criteria; and

determining membership of at least a subset of said matching set of XML documents based on those rows in said set of non-indexed rows that correspond to said set of search criteria.

19. The computer-readable medium of claim 12, wherein said first set of entries includes for each element a document identification value, an offset value, a length value, a depth value, and a parent offset value.

20. The computer-readable medium of claim 12, wherein said step of using an index comprises:

obtaining a set of potential XML documents that may qualify as members of said set of matching XML documents using, at least in part, said index; and

examining each member of said set of potential XML documents to identify each member in said set of matching XML documents.

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 steps of:

upon receiving a request to store a particular XML document, storing said particular XML document; and

updating an index to include a reference to said particular XML document, wherein said reference includes a first set of entries comprising information about the location of elements in said particular XML document, a second set of entries comprising information about element attributes in said particular XML document, and a third set of entries comprising information about element values in said particular XML document.

22. The computer-readable medium of claim 21, wherein:

said particular XML document is stored within one or more tables in a database, and said one or more tables store said particular XML document in a set of indexed row, wherein said indexed rows are indexed by said index.