# US 9,436,779 B2 · Techniques of efficient XML query using combination of XML table index and path/value index > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,436,779 B2 - Document ID: US9436779B2 - Status: Granted - Kind: B2 - Application number: 11/601,146 - Filed: 2006-11-17 - Published: 2008-05-22 - Granted: 2016-09-06 - Earliest claimed: 2006-11-17 - Assignees: Oracle International Corporation - Applicants: Zhen Hua Liu; Muralidhar Krishnaprasad; Hui Joe Chang; Vikas Arora - Inventors: Zhen Hua Liu; Muralidhar Krishnaprasad; Hui Joe Chang; Vikas Arora - Web page: https://patentgrep.com/patent/US9436779B2 ## CPC - G06F 16/86: {Mapping to a database} - G06F 16/24542: {Plan optimisation} - G06F 16/81: Indexing, e.g. XML tags; Data structures therefor; Storage structures - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A mechanism is provided for accessing XML data in a database system using a combination of a XML Table Index table and a XML Path Index table. By using a combination of a XML Table Index and a XML Path Index, both selection access and navigational access involved in a query can be optimized. For example, the XML Table Index gives the database system an ability to readily evaluate the predicate expression, thereby improving the selection access. Moreover, in some embodiments, the selection access can be further improved by using secondary indexes on columns contained in the XML Table Index table. In a complementary manner, the XML Path Index table gives the database system an ability to navigate to a specific location given a path expression, thereby improving the navigational access. Thus, by combining both tables, both selection and navigational accesses are improved. ## Claims ### Claim 1 A computer-implemented method comprising: causing execution of an index generation statement identifying a plurality of path expressions and a plurality of columns of a first table for indexing a collection of documents, wherein said plurality of path expressions identify less than all nodes in the collection of documents; wherein for each column of said plurality of columns, said index generation statement specifies an association between said each column and a respective path expression of said plurality of path expressions; wherein execution of said index generation statement causes generation of said first table, wherein the first table comprises a first set of entries; wherein for each column of the plurality of columns of said first table, each entry of the first set of entries contains a node value of a node identified by the respective path expression of said each column, said node value being from a document of said collection of documents; wherein the collection of documents is also indexed by a second table, wherein the second table comprises a second set of entries, each entry in the second set of entries: being associated with a given node of a document in the collection of documents, and including location data for locating content in the document, wherein the content is associated with the given node and path data that corresponds to a path to the given node in the document; intercepting, by a database system, a query for first information from a collection of documents, wherein the query for first information does not reference said first table and said second table; said database system rewriting the query for first information to generate a rewritten query that references said first table and said second table; wherein the query comprises one or more predicates; based on the rewritten query, said database system generating a first query plan using both the first table and the second table, wherein the first query plan, when executed by the database system, causes the database system to perform: identifying one or more first entries from the first table that contain a node value that satisfies the one or more predicates; extracting second information from the one or more first entries identified from the first table; extracting, using the second information, the first information from one or more second entries in the second table; wherein the first table and the second table are two different tables. ### Claim 2 (depends on 1) The method of claim 1, further comprising building a secondary index for one or more columns in the plurality of columns in the first table. ### Claim 3 (depends on 1) The method of claim 1, further comprising performing a joining of the first table and the second table based on one or more columns indexed by a secondary index. ### Claim 4 (depends on 3) The method of claim 3, wherein one of the one or more columns indexed by the secondary index is a document identifier column. ### Claim 5 (depends on 3) The method of claim 3, wherein the one or more columns indexed by the secondary index comprise hierarchical order information. ### Claim 6 (depends on 1) The method of claim 1, further generating one or more different query plans without accessing both said first table and the second table; and determining cost information for each of the first query plan and the one or more different query plans; and selecting a second query plan among the first query plan and the one or more different query plans using the cost information based on a set of selection criteria. ### Claim 7 (depends on 1) The method of claim 1, wherein the first table includes one or more references to a set of additional tables, and wherein the one or more references to the set of additional tables create a table chain. ### Claim 8 (depends on 1) The method of claim 1, wherein at least one document in the collection of documents is stored in aggregate storage. ### Claim 9 (depends on 1) The method of claim 1, wherein at least one document in the collection of documents is stored object-relationally. ### Claim 10 (depends on 1) The method of claim 1, wherein at least one document in the collection of documents is stored in a tree form. ### Claim 11 (depends on 1) The method of claim 1, wherein one of the plurality of columns is a virtual column. ### Claim 12 (depends on 1) The method of claim 1, wherein a column from the plurality of columns maps to two or more nodes. ### Claim 13 (depends on 1) The method of claim 1, wherein the first table includes at least one column of the plurality of columns that stores node hierarchical order information projected by a row pattern. ### Claim 14 (depends on 1) The method of claim 1, further comprising generating the first table using a data definition language statement. ### Claim 15 A volatile or non-volatile computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, cause: executing an index generation statement identifying a plurality of path expressions and a plurality of columns of a first table for indexing a collection of documents wherein said plurality of path expressions identify less than all nodes in the collection of documents wherein for each column of said plurality of columns, said index generation statement specifies an association between said each column and a respective path expression of said plurality of path expressions; wherein execution of said index generation statement causes generation of said first table, wherein the first table comprises a first set of entries; wherein for each column of the plurality of columns of said first table, each entry of the first set of entries contains a node value of a node identified by the respective path expression of said each column, said node value being from a document of said collection of documents; wherein the collection of documents is also indexed by a second table, wherein the second table comprises a second set of entries, each entry in the second set of entries: being associated with a given node of a document in the collection of documents, and including location data for locating content in the document, wherein the content is associated with the given node and path data that corresponds to a path to the given node in the document; and intercepting, by a database system, a query for first information from a collection of documents, wherein the query for first information does not reference said first table and said second table; said database system rewriting the query for first information to generate a rewritten query that references said first table and said second table; wherein the query comprises one or more predicates; based on the rewritten query, said database system generating a first query plan using both the first table and the second table, wherein the first query plan, when executed by the database system, causes the database system to perform: identifying one or more first entries from the first table that contain a node value that satisfies the one or more predicates; extracting second information from the one or more first entries identified from the first table; extracting, using the second information, the first information from one or more second entries in the second table wherein the first table and the second table are two different tables. ### Claim 16 (depends on 15) The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform building a secondary index for one or more columns in the plurality of columns in the first table. ### Claim 17 (depends on 15) The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform a joining of the first table and the second table based on one or more columns indexed by a secondary index. ### Claim 18 (depends on 17) The medium of claim 17, wherein one of the one or more columns indexed by the secondary index is a document identifier column. ### Claim 19 (depends on 17) The medium of claim 17, wherein the one or more columns indexed by the secondary index comprise hierarchical order information. ### Claim 20 (depends on 15) The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform: generating one or more different query plans without accessing both said first table and the second table; and determining cost information for each of the first query plan and the one or more different query plans; and selecting a second query plan among the first query plan and the one or more different query plans using the cost information based on a set of selection criteria. ### Claim 21 (depends on 15) The medium of claim 15, wherein the first table includes one or more references to a set of additional tables, and wherein the one or more references to the set of additional tables create a table chain. ### Claim 22 (depends on 15) The medium of claim 15, wherein at least one document in the collection of documents is stored in aggregate storage. ### Claim 23 (depends on 15) The medium of claim 15, wherein at least one document in the collection of documents is stored object-relationally. ### Claim 24 (depends on 15) The medium of claim 15, wherein at least one document in the collection of documents is stored in a tree form. ### Claim 25 (depends on 15) The medium of claim 15, wherein one of the plurality of columns is a virtual column. ### Claim 26 (depends on 15) The medium of claim 15, wherein a column from the plurality of columns maps to two or more nodes. ### Claim 27 (depends on 15) The medium of claim 15, wherein the first table includes at least one column of the plurality of columns that stores node hierarchical order information projected by a row pattern. ### Claim 28 (depends on 15) The medium of claim 15, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform generating the first table using a data definition language statement.