GENERIC INDEXING FOR EFFICIENTLY SUPPORTING AD-HOC QUERY OVER HIERARCHICALLY MARKED-UP DATA

摘要

Hierarchical data objects are indexed using an index referred to herein as a hierarchy-value index. A hierarchy-value index has, as index keys, tokens (tag name, a word in node string value) that are extracted from hierarchical data objects. Each token is mapped to the locations that correspond to the data for the token in hierarchical data objects. A token can represent a non-leaf node, such as an XML element or a JSON field. A location can be a region covering and subsuming child nodes. For a token that represents a non-leaf node, a location to which the token is mapped contains the location of any token corresponding to a descendant node of the non-leaf node. Thus, token containment based on the locations of tokens within a hierarchical data object may be used to determine containment relationships between nodes in a hierarchical data object.