Indexing and querying XML structured documents with XPath queries

摘要

With the growing importance of XML in data representation and exchange in large-scale scientific and commercial applications, substantial research efforts have been made to provide efficient indexing and querying mechanisms to retrieve data from XML-formatted data. However, traditional sequence-based indexing and querying mechanism suffers from the following three shortcomings. (i) Semantic flaw problem. That is, an XML document which semantically satisfies an XML query may not be returned; (ii) False answer (alarm) problem, i.e., documents which do not satisfy a query may be wrongly returned. Additional time-consuming refinement or post-processing phase has to be called to eliminate false query answers; (iii) Traditional sequence-based mechanism cannot guarantee the linear size complexity of structure-encoded sequences. In the worst case, its space complexity reaches O(n2) (where n is the total number of nodes in an XML data tree). To overcome its shortcomings, in this pattern application, we present another efficient and novel geometric sequence mechanism, which transforms XML documents and XPath queries into the corresponding geometric data/query sequences. XML querying is thus converted to finding non-contiguous geometric subsequence matches. Our approach ensures correct (i.e., without semantic false) and fast (i.e., without the costly post-processing phase) evaluation of XPath queries, while at the same time guaranteeing the linear space complexity.