Query reasoning on trees with types, interleaving and counting
Everardo Barcenas, Pierre Geneves, Nabil Layaida and Alan Schmitt
One major challenge in XML programming consists in identifying expressive XPath-like query languages for which static analysis tasks such as query containment can be effectively decided. In this setting, XML documents are seen as finite trees, whose structure may additionally be constrained by an XML schema regarded as a regular tree type. We consider the problem of query containment in the presence of type constraints for a class of regular path queries extended with counting and interleaving operators. The counting operator restricts the number of occurrences of children nodes satisfying a given logical property. The interleaving operator provides a succinct notation for the absence of order between nodes satisfying a logical properties in finite ordered trees. We provide a logic-based framework supporting these notions, which can be used to solve common query reasoning problems such as satisfiability and containment of queries in exponential time.