SPARQL Query Containment under Schema

Melisachew Chekol 1 Jérôme Euzenat 2 Pierre Genevès 3 Nabil Layaïda 3
2 MOEX - Evolution de la connaissance
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Query containment is defined as the problem of determining if the result of a query is included in the result of another query for any dataset. It has major applications in query optimization and knowledge base verification. The main objective of this work is to provide sound and complete procedures to determine containment of SPARQL queries under expressive description logic schema axioms. Beyond that, these procedures are experimentally evaluated. To date, testing query containment has been performed using different techniques: containment mapping, canonical databases, automata theory techniques and through a reduction to the validity problem in logic. In this work, we use the latter technique to test containment of SPARQL queries using an expressive modal logic called µ-calculus. For that purpose, we define an RDF graph encoding as a transition system which preserves its characteristics. In addition, queries and schema axioms are encoded as µ-calculus formulae. Thereby, query containment can be reduced to testing validity in the logic. We identify various fragments of SPARQL and description logic schema languages for which containment is decidable. Additionally, we provide theoretically and experimentally proven procedures to check containment of these decidable fragments. Finally, we propose a benchmark for containment solvers which is used to test and compare the current state-of-the-art containment solvers.
Type de document :
Article dans une revue
Journal on Data Semantics, Springer, 2018, 7 (3), pp.133-154. 〈10.1007/s13740-018-0087-1〉
Liste complète des métadonnées

Littérature citée [45 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01767887
Contributeur : Tyrex Equipe <>
Soumis le : mercredi 6 juin 2018 - 11:25:10
Dernière modification le : samedi 15 décembre 2018 - 01:50:08

Fichier

jods18.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Melisachew Chekol, Jérôme Euzenat, Pierre Genevès, Nabil Layaïda. SPARQL Query Containment under Schema. Journal on Data Semantics, Springer, 2018, 7 (3), pp.133-154. 〈10.1007/s13740-018-0087-1〉. 〈hal-01767887v2〉

Partager

Métriques

Consultations de la notice

143

Téléchargements de fichiers

122