Covering Indexes for XML Queries: Bisimulation - Simulation = Negation Prakash Ramanan   View Paper (PDF)   Return to XML Queries Processing I (Session A4) Abstract Tree Pattern Queries (TPQ), Branching Path Queries (BPQ), and Core XPath (CXPath) are subclasses of the XML query language XPath, TPQ propersubset BPQ propersubset CXPath propersubset XPath. Let TPQ = TPQ+ propersubset BPQ+ propersubset CXPath+ propersubset XPath+ denote the corresponding subclasses, consisting of queries that do not involve the boolean negation operator not in their pred- icates. Simulation and bisimulation are two different binary relations on graph vertices that have previously been studied in con- nection with some of these classes. For in- stance, TPQ queries can be minimized using simulation. Most relevantly, for an XML doc- ument, its bisimulation quotient is the small- est index that covers (i.e., can be used to an- swer) all BPQ queries. Our results are as fol- lows: - A CXPath+ query can be evaluated on an XML document by computing the simulation of the query tree by the doc- ument graph. - For an XML document, its simulation quotient is the smallest covering index for BPQ+. This, together with the previously-known result stated above, leads to the following: For BPQ cover- ing indexes of XML documents, Bisimulation - Simulation = Negation. - For an XML document, its simulation quotient, with the idref edges ignored throughout, is the smallest covering in- dex for TPQ. For any XML document, its simulation quo- tient is never larger than its bisimulation quo- tient; in some instances, it is exponentially smaller. Our last two results show that disal- lowing negation in the queries could substan- tially reduce the size of the smallest covering index. ©2004 Association for Computing Machinery