Patent ID: 8117182

Claim:
A method for optimizing descendant path evaluation in XPath/XQuery, the method comprising: generating a list of unique paths from a plurality of tree structures for a collection of Extensible Markup Language (“XML”) documents prior to receiving queries targeted at the XML documents in the collection of XML documents, each unique path comprising a distinct route through a tree structure of a particular XML document from one or more root nodes to one or more non-root nodes, the tree structure comprising one or more hierarchical levels of nodes; ordering the unique paths in the list in reverse path order to optimize searching of the list; receiving a query in XPath/XQuery format targeted toward the collection of XML documents, the query specifying a descendant node for retrieval from a tree structure of the plurality of tree structures; identifying, from the list, each unique path that include the descendant node specified by the query; generating a navigation aid for the query, the navigation aid comprising a hash table of all nodes with a same identifier as an identifier of a first node in a first path that comprises the descendent node specified by the query, wherein the identifier is not unique and paths of the nodes of the hash table are not known to include the descendent node specified by the query and are not known to include the first path such that the hash table includes false positives of the descendent node; performing a hash table lookup of the hash table at each hierarchical level in the tree structure to determine sub-trees with a node comprising the identifier, the hash table lookup using a hierarchical level identifier and a sub-tree identifier; evaluating, at each hierarchical level in the tree structure, sub-trees with the node comprising the identifier; skipping, at each hierarchical level in the tree structure, evaluation of sub-trees of the XML document for a node of each hierarchical level in the tree structure for which no entry exists in the navigation aid as determined by the hash table lookup; and retrieving, using the navigation aid, descendant nodes in the tree structure by traversing only the sub-trees that include the descendant node.