Query Reasoning on Trees with Types, Interleaving, and Counting

Bárcenas, Everardo; Genevès, Pierre; Layaïda, Nabil; Schmitt, Alan

doi:10.5591/978-1-57735-516-8/IJCAI11-127

Query Reasoning on Trees with Types, Interleaving, and Counting

Everardo Bárcenas, Pierre Genevès, Nabil Layaïda, Alan Schmitt

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 718-722.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-127

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.

Everardo Bárcenas, Pierre Genevès, Nabil Layaïda, and Alan Schmitt. 2011. Query Reasoning on Trees with Types, Interleaving, and Counting. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 718–722. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-127

@inproceedings{ijcai2011p127,
  title     = {Query Reasoning on Trees with Types, Interleaving, and Counting},
  author    = {Bárcenas, Everardo and Genevès, Pierre and Layaïda, Nabil and Schmitt, Alan},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {718--722},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-127},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-127},
}

TY  - CPAPER
TI  - Query Reasoning on Trees with Types, Interleaving, and Counting
AU  - Bárcenas, Everardo
AU  - Genevès, Pierre
AU  - Layaïda, Nabil
AU  - Schmitt, Alan
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 718
EP  - 722
DO  - 10.5591/978-1-57735-516-8/IJCAI11-127
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-127
ER  -