Algebraic Structures for Capturing the Provenance of SPARQL Queries | Zendy

Floris Geerts | Zendy; Thomas Unger | Zendy; Grigoris Karvounarakis | Zendy; Irini Fundulaki | Zendy; Vassilis Christophides | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Algebraic Structures for Capturing the Provenance of SPARQL Queries

Author(s) -

Floris Geerts,

Thomas Unger,

Grigoris Karvounarakis,

Irini Fundulaki,

Vassilis Christophides

Publication year - 2016

Publication title -

journal of the acm

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.672

H-Index - 134

eISSN - 1557-735X

pISSN - 0004-5411

DOI - 10.1145/2810037

Subject(s) - sparql , rdf , computer science , rdf schema , semiring , object (grammar) , theoretical computer science , information retrieval , mathematics , discrete mathematics , semantic web , artificial intelligence

International audienceThe 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research