SPARQL Query Containment Under SHI Axioms
Abstract
SPARQL query containment under schema axioms is the problem of determining whether, for any RDF graph satisfying a given set of schema axioms, the answers to a query are contained in the answers of another query. This problem has major applications for verification and optimization of queries. In order to solve it, we rely on the mu-calculus. Firstly, we provide a mapping from RDF graphs into transition systems. Secondly, SPARQL queries and RDFS and SHI axioms are encoded into mu-calculus formulas. This allows us to reduce query containment and equivalence to satisfiability in the mu-calculus. Finally, we prove a double exponential upper bound for containment under SHI schema axioms.
Cite
Text
Chekol et al. "SPARQL Query Containment Under SHI Axioms." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8108Markdown
[Chekol et al. "SPARQL Query Containment Under SHI Axioms." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/chekol2012aaai-sparql/) doi:10.1609/AAAI.V26I1.8108BibTeX
@inproceedings{chekol2012aaai-sparql,
title = {{SPARQL Query Containment Under SHI Axioms}},
author = {Chekol, Melisachew Wudage and Euzenat, Jérôme and Genevès, Pierre and Layaïda, Nabil},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {10-16},
doi = {10.1609/AAAI.V26I1.8108},
url = {https://mlanthology.org/aaai/2012/chekol2012aaai-sparql/}
}