Query Reasoning on Trees with Types, Interleaving, and Counting

Everardo Barcenas-Patino 1 Pierre Genevès 1 Nabil Layaïda 1 Alan Schmitt 2
1 WAM - Web, adaptation and multimedia
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 SARDES - System architecture for reflective distributed computing environments
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download
https://hal.inria.fr/inria-00609556
Contributor : Vincent Quint <>
Submitted on : Tuesday, July 19, 2011 - 2:02:31 PM
Last modification on : Thursday, February 21, 2019 - 1:31:23 AM
Long-term archiving on : Monday, November 12, 2012 - 3:02:01 PM

File

IJCAI2011.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00609556, version 1

Collections

INRIA | UGA | LIG_MFML_TYREX | LIG_MFML | LIG

Citation

Everardo Barcenas-Patino, Pierre Genevès, Nabil Layaïda, Alan Schmitt. Query Reasoning on Trees with Types, Interleaving, and Counting. 22nd International Joint Conference on Artificial Intelligence IJCAI'2011, Jul 2011, Barcelone, Spain. ⟨inria-00609556⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

1462

Files downloads

195

Contact


archive-ouverte@inria.fr