|
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]
| |
|
DOI
|
|
|
|
10.1145/2810037
| |
|
Volume/pages
|
|
|
|
63
:1
(2016)
, p. 1-63
| |
|
Article Reference
|
|
|
|
7
| |
|
ISI
|
|
|
|
000373852100007
| |
|
Medium
|
|
|
|
E-only publicatie
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|
Full text (publisher's version - intranet only)
|
|
|
|
| |
|