|
Title
|
|
|
|
Algebraic structures for capturing the provenance of SPARQL queries
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| We show that the evaluation of SPARQL algebra queries on various notions of annotated RDF graphs can be seen as particular cases of the evaluation of these queries on RDF graphs annotated with elements of so-called spm-semirings. Spm-semirings extend semirings, used for positive relational algebra queries on annotated relational data, with a new operator to capture the semantics of the non-monotone SPARQL operator OPTIONAL. Furthermore, spm-semiring-based annotations ensure that desired SPARQL query equivalences hold when querying annotated RDF. 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 to construct spm-semirings and to identify a universal object in the class of spm-semirings. Finally, we show that this universal object provides a concise provenance representation and can be used to evaluate SPARQL queries on arbitrary spm-semiring-annotated RDF graphs. |
| |
|
Language
|
|
|
|
English
| |
|
Source (book)
|
|
|
|
Proceedings of the 16th International Conference on Database Theory (ICDT 2013), Genoa, Italy, March 18-22, 2013 / Tan, Wang-Chiew [edit.]; et al.
| |
|
Publication
|
|
|
|
New York, N.Y.
:
ACM
,
2013
| |
|
ISBN
|
|
|
|
978-1-4503-1598-2
| |
|
DOI
|
|
|
|
10.1145/2448496.2448516
| |
|
Volume/pages
|
|
|
|
p. 153-164
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|