Paper Info
Title
Query reasoning on trees with types, interleaving, and counting
Abstract
A major challenge of query language design is the combination of expressivity with effective static analyses such as query containment. In the setting of XML, documents are seen as finite trees, whose structure may additionally be constrained by type constraints such as those described by an XML schema. 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 describing the absence of order between nodes satisfying a logical property. We provide a logic-based framework supporting these operators, which can be used to solve common query reasoning problems such as satisfiability and containment of queries in exponential time.
Year
DOI
Venue
2011
10.5591/978-1-57735-516-8/IJCAI11-127
IJCAI
Keywords
Field
DocType
query containment,effective static analysis,common query reasoning problem,xml schema,exponential time,query language design,interleaving operator,type constraint,finite tree,logical property
Query optimization,Discrete mathematics,Notation,Query language,XML,Computer science,Satisfiability,Theoretical computer science,XML schema,Operator (computer programming),Interleaving
Conference
Citations 
PageRank 
References 
11
0.72
13
Authors
4
Name
Order
Citations
PageRank
Everardo Bárcenas1239.15
Pierre Genevès222525.61
Nabil Layaïda350147.84
Alan Schmitt454731.50