SPARQL Query Containment under SHI Axioms

Melisachew Wudagae Chekol 1 Jérôme Euzenat 1 Pierre Genevès 2 Nabil Layaïda 2
1 EXMO - Computer mediated exchange of structured knowledge
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 WAM - Web, adaptation and multimedia
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
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.
Document type :
Reports
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00691638
Contributor : Melisachew Wudagae Chekol <>
Submitted on : Thursday, April 26, 2012 - 5:05:54 PM
Last modification on : Friday, April 5, 2019 - 1:30:30 AM
Long-term archiving on : Thursday, December 15, 2016 - 2:33:56 AM

File

RR-7943.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00691638, version 1

Collections

Citation

Melisachew Wudagae Chekol, Jérôme Euzenat, Pierre Genevès, Nabil Layaïda. SPARQL Query Containment under SHI Axioms. [Research Report] RR-7943, Inria - Sophia Antipolis. 2012. ⟨hal-00691638⟩

Share

Metrics

Record views

535

Files downloads

177