SPARQL Query Containment Under SHI Axioms

Melisachew Wudage 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.
Type de document :
Communication dans un congrès
26th AAAI Conference on Artificial Intelligence, Jul 2012, Toronto, Canada. AAAI Press, pp.10-16, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00749080
Contributeur : Vincent Quint <>
Soumis le : mardi 6 novembre 2012 - 15:50:15
Dernière modification le : mercredi 7 novembre 2012 - 08:52:50
Document(s) archivé(s) le : samedi 17 décembre 2016 - 08:13:40

Fichier

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

Identifiants

  • HAL Id : hal-00749080, version 1

Collections

Citation

Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, Nabil Layaïda. SPARQL Query Containment Under SHI Axioms. 26th AAAI Conference on Artificial Intelligence, Jul 2012, Toronto, Canada. AAAI Press, pp.10-16, 2012. <hal-00749080>

Partager

Métriques

Consultations de
la notice

331

Téléchargements du document

83