Algebraic Structures for Capturing the Provenance of SPARQL Queries

作者：Geerts Floris^*; Unger Thomas^*; Karvounarakis Grigoris^*; Fundulaki Irini^*; Christophides Vassilis^*

来源：Journal of the ACM, 2016, 63(1): 7.

DOI：10.1145/2810037

• Algebraic structures
• annotations
• provenance models
• query languages
• RDF
• SPARQL

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.

• 出版日期2016-3