Publication
Title
Algebraic structures for capturing the provenance of SPARQL queries
Author
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.
Language
English
Source (journal)
Journal of the Association for Computing Machinery. - New York, N.Y., 1954, currens
Publication
New York, N.Y. : 2016
ISSN
0004-5411 [print]
1557-735X [online]
Volume/pages
63:1(2016), p. 1-63
Article Reference
7
ISI
000373852100007
Medium
E-only publicatie
Full text (Publishers DOI)
Full text (publishers version - intranet only)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 07.03.2016
Last edited 27.03.2017
To cite this reference