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

• US 7,181,680 B2
• Filed: 04/30/2003
• Issued: 02/20/2007
• 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
• Primary Examiner(s): HUTTON JR, WILLIAM D
• Application Number:
  US10/427,276
• Publication Number:
  US 20040221226A1
• Time in Patent Office: 1,392 Days
• Field of Search: 715/501.1, 715/530, 707/102
• US Class Current: 715/229
• 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 comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause 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 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 for element names, wherein the entry for a particular element name includes location information for the particular element name,

wherein the location information for the particular element name specifies (a) which XML documents, of a plurality of XML documents indexed by said index, contain elements with said particular element name, and (b) where, within each of said XML documents containing said elements with said particular element name, the elements with the particular element name are located;

a second set of entries for element attributes, wherein the entry for a particular element attribute includes location information for the particular element attribute,

wherein the location information for the particular element attribute specifies (a) which XML documents, of said plurality of XML documents indexed by said index, contain elements with said particular element attribute, and (b) where, within each of said XML documents containing said elements with said particular element attribute, the elements with the particular element attribute are located; and

a third set of entries for element values, wherein the entry for a particular element value includes location information for the particular element value,

wherein the location information for the particular element value specifies (a) which XML documents, of said plurality of XML documents indexed by said index, contain elements with said particular element value, and (b) where, within each of said XML documents containing said elements with said particular element value, the elements with the particular element value are located.

2. The method of claim 1, wherein:

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

said one or more tables store said 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 2, further comprising:

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

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

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

determining if said query is compatible with said index.

5. The method of claim 4, 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.

6. The method of claim 4, 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 matching XML documents is faster than not using said index to obtain said set of matching XML documents.

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

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

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, and a depth value.

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

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

examining each of said XML documents that may qualify as members of said set of matching XML documents to identify each member in said set of matching XML documents.

10. The method of claim 1, wherein each entry in the first set of entries indicates where, within a hierarchy of elements within each of said XML documents, any element having an element name associated with the entry is located.

11. The method of claim 1, wherein each entry in the second set of entries indicates where, within a hierarchy of elements within each of said XML documents, any element having an attribute name associated with the entry is located.

12. The method of claim 1, wherein each entry in the third set of entries indicates where, within a hierarchy of elements within each of said XML documents, any element having an element value associated with the entry is located.

13. The method of claim 1, wherein the first set of entries, the second set of entries, and the third set of entries are separate from each other.

14. The method of claim 1, wherein the location information for the particular element name specifies a length value and a depth value for each element identified.

15. A method comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause 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 that each identify the location, within the hierarchy of elements of the particular XML document, of element names contained within the particular XML document, a second set of entries that each identify the location, within the hierarchy of elements of the particular XML document, of element attributes contained within the particular XML document, and a third set of entries that each identify the location, within the hierarchy of elements of the particular XML document, of element values contained within the particular XML document,

wherein the first set of entries specify (a) which XML documents, of a plurality of XML documents indexed by said index, contain elements with a particular element name, and (b) where, within each of said XML documents containing said elements with said particular element name, the elements with the particular element name are located,

wherein the second set of entries specify (a) which XML documents, of said plurality of XLML documents indexed by said index, contain elements with a particular element attribute, and (b) where, within each of said XML documents containing said elements with said particular element attribute, the elements with the particular element attribute are located, and

wherein the third set of entries specify (a) which XML documents, of said plurality of XML documents indexed by said index, contain elements with a particular element value, and (b) where, within each of said XML documents containing said elements with said particular element value, the elements with the particular element value are located.

16. The method of claim 15, 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 rows,

wherein said indexed rows are indexed by said index.