SPARQL Query Containment Under SHI Axioms

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 µ-calculus. Firstly, we provide a mapping from RDF graphs into transition systems. Secondly, SPARQL queries and RDFS and SH I axioms are encoded into µ-calculus formulas. This allows us to reduce query containment and equivalence to satisfiability in the µcalculus. Finally, we prove a double exponential upper bound for containment under SH I schema axioms.

Authors

• Melisachew Wudage Chekol
• Jérôme Euzenat Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG
• Pierre Genevès Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG F-38000 Grenoble, France
• Nabil Layaïda Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG F-38000 Grenoble, France

Keywords

No keywords are indexed for this paper.