Algebraic Structures for Capturing the Provenance of SPARQL Queries

Abstract : The evaluation of SPARQL algebra queries on various kinds of annotated RDF graphs can be seen as a particular case of the evaluation of these queries on RDF graphs annotated with elements of so-called spm-semirings. Spm-semirings extend semirings, used for representing the provenance of positive relational algebra queries on annotated relational data, with a new operator to capture the semantics of the non-monotone SPARQL operators. Furthermore, spm-semiring-based annotations ensure that desired SPARQL query equivalences hold when querying annotated RDF. In this work, in addition to introducing spm-semirings, we study their properties and provide an alternative characterization of these structures in terms of semirings with an embedded boolean algebra (or seba-structure for short). This characterization allows us to construct spm-semirings and identify a universal object in the class of spm-semirings. Finally, we show that this universal object provides a provenance representation of poly-sized overhead and can be used to evaluate SPARQL queries on arbitrary spm-semiring-annotated RDF graphs.
Type de document :
Article dans une revue
Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (1), pp.7. . 〈10.1145/2810037〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01411827
Contributeur : Vassilis Christophides <>
Soumis le : mercredi 7 décembre 2016 - 16:41:26
Dernière modification le : mercredi 30 mai 2018 - 10:26:02
Document(s) archivé(s) le : lundi 20 mars 2017 - 21:30:41

Fichier

a7-geerts.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Collections

Citation

Floris Geerts, Thomas Unger, Grigoris Karvounarakis, Irini Fundulaki, Vassilis Christophides. Algebraic Structures for Capturing the Provenance of SPARQL Queries. Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (1), pp.7. . 〈10.1145/2810037〉. 〈hal-01411827〉

Partager

Métriques

Consultations de la notice

165

Téléchargements de fichiers

79