Efficient method of using XML value indexes without exact path information to filter XML documents for more specific XPath queries

Patent metadata

Field	Value
Publication number	US-9430582-B2
Application number	US-201514605833-A
Country	US
Kind code	B2
Filing date	Jan 26, 2015
Priority date	Oct 25, 2007
Publication date	Aug 30, 2016
Grant date	Aug 30, 2016

Abstract

A system and method is provided for query processing comprises: creating an index of a database and ordering a set of index candidates from the index into a list based on a set of heuristic rules. A query defining a query path is then reduced into a list of single path expressions. Each index candidate is matched against the list of single path expressions according to the ordering of the index candidates. The matched candidate nodes are also verified to insure that they satisfy the query path.

First claim

We claim:

1. A method for query processing comprising:
creating, via a processor, an index of a database;
ordering, via the processor, a set of index candidates from the index into a list based on heuristic rules, wherein the heuristic rules reduce a matching cost for an index pattern via a preference for a matching without a descendant axis over a matching with a descendant axis and via a preference for a matching without a wildcard over a matching with a wildcard and via a preference for a pattern with greater number of steps than for a pattern with fewer number of steps, wherein determination of the matching with or without a descendant axis is performed prior to determination of the matching with or without a wildcard, and wherein the determination of the matching with or without a wildcard is performed prior to determination of whether a current pattern contains fewer steps than a previous pattern; and
reducing, via the processor, a query defining a query path into a list of single path expressions.

2. The method of claim 1 wherein extra index candidates for inexact match are eliminated.

3. The method of claim 1 , wherein creating an index comprises creating an XML value index.

4. The method of claim 1 , wherein a candidate result set is reduced to an exact result set while verifying that each index candidate matched against a list of single path expressions satisfies a query path.

5. The method of claim 1 , wherein the matching comprises determining exact and inexact matches and determining when the inexact matches become exact matches.

6. A system for query processing, comprising:
a memory; and
a processor coupled to said memory, wherein said processor performs operations, said operations comprising:
creating an index of a database;
ordering a set of index candidates from the index into a list based on heuristic rules, wherein the heuristic rules reduce a matching cost for an index pattern via a preference for a matching without a descendant axis over a matching with a descendant axis and via a preference for a matching without a wildcard over a matching with a wildcard and via a preference for a pattern with greater number of steps than for a pattern with fewer number of steps, wherein determination of the matching with or without a descendant axis is performed prior to determination of the matching with or without a wildcard, and wherein the determination of the matching with or without a wildcard is performed prior to determination of whether a current pattern contains fewer steps than a previous pattern; and
reducing a query defining a query path into a list of single path expressions.

7. The system of claim 6 wherein extra index candidates for inexact match are eliminated.

8. The system of claim 6 , wherein creating an index comprises creating an XML, value index.

9. The system of claim 6 , wherein a candidate result set is reduced to an exact result set while verifying that each index candidate matched against a list of single path expressions satisfies a query path.

10. The system of claim 6 , wherein the matching comprises determining exact and inexact matches and determining when the inexact matches become exact matches.

11. An article of manufacture for use in a computer system tangibly embodying computer instructions executable by said computer system to perform operations, the operations comprising:
creating, via a processor, an index of a database;
ordering, via the processor, a set of index candidates from the index into a list based on heuristic rules, wherein the heuristic rules reduce a matching cost for an index pattern via a preference for a matching without a descendant axis over a matching with a descendant axis and via a preference for a matching without a wildcard over a matching with a wildcard and via a preference for a pattern with greater number of steps than for a pattern with fewer number of steps, wherein determination of the matching with or without a descendant axis is performed prior to determination of the matching with or without a wildcard, and wherein the determination of the matching with or without a wildcard is performed prior to determination of whether a current pattern contains fewer steps than a previous pattern; and
reducing, via the processor, a query defining a query path into a list of single path expressions.

12. The article of manufacture of claim 11 wherein extra index candidates for inexact match are eliminated.

13. The article of manufacture of claim 11 , wherein creating an index comprises creating an XML, value index.

14. The article of manufacture of claim 11 , wherein a candidate result set is reduced to an exact result set while verifying that each index candidate matched against a list of single path expressions satisfies a query path.

15. The article of manufacture of claim 11 , wherein the matching comprises determining exact and inexact matches and determining when the inexact matches become exact matches.

Assignees

• IBM

Inventors

• Cai Mengchu
• Li Ruiping
• Zhang Guogen

Classifications

• G06F16/81 Primary

  Indexing, e.g. XML tags; Data structures therefor; Storage structures · CPC title

• G06F16/8373

  Query execution · CPC title

• G06F17/30911 Primary

  Physics · mapped topic

• G06F17/30938

  Physics · mapped topic