research-article

Algebraic Structures for Capturing the Provenance of SPARQL Queries

Authors:

Grigoris Karvounarakis,

Irini Fundulaki,

Vassilis ChristophidesAuthors Info & Claims

Journal of the ACM (JACM), Volume 63, Issue 1

Article No.: 7, Pages 1 - 63

https://doi.org/10.1145/2810037

Published: 12 February 2016 Publication History

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.

References

[1]

Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley.

Digital Library

[2]

Yael Amsterdamer, Daniel Deutch, and Val Tannen. 2011a. On the limitations of provenance for queries with difference. In Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance (TaPP’11). USENIX Association.

[3]

Yael Amsterdamer, Daniel Deutch, and Val Tannen. 2011b. Provenance for aggregate queries. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’11). ACM, 153--164.

Digital Library

[4]

Renzo Angles and Claudio Gutierrez. 2008. The expressive power of SPARQL. In International Semantic Web Conference (Lecture Notes in Computer Science), Vol. 5318. Springer, 114--129.

Digital Library

[5]

Peter Buneman, James Cheney, and Stijn Vansummeren. 2008. On the expressiveness of implicit provenance in query and update languages. ACM Transactions on Database Systems 33, 4, Article 28 (2008), 47 pages.

Digital Library

[6]

Peter Buneman and Egor V. Kostylev. 2011. Annotation algebras for RDFS. In Proceedings of the 2nd International Workshop on the role of Semantic Web in Provenance Management. CEUR Workshop Proceedings, Article 1, 6 pages. ceur-ws.org/Vol-670/paper_4.pdf.

[7]

Stanley Burris and H. P. Sankappanavar. 1981. A Course in Universal Algebra. Number 78 in Graduate Texts in Mathematics. Springer-Verlag.

[8]

Jeremy Carroll, Christian Bizer, Pat Hayes, and Patrick Stickler. 2005. Named graphs. Web Semantics: Science, Services and Agents on the World Wide Web 3, 4 (2005), 247--267.

Digital Library

[9]

James Cheney, Laura Chiticariu, and Wang-Chiew Tan. 2009. Provenance in databases: Why, how, and where. Found Trends Databases 1, 4 (2009), 379--474.

Digital Library

[10]

Carlos Viegas Damásio, Anastasia Analyti, and Grigoris Antoniou. 2012. Provenance for SPARQL queries. In Proceedings of the 11th International Conference on the Semantic Web (ISWC’12). Lecture Notes in Computer Science, Vol. 7649. Springer, 625--640.

Digital Library

[11]

Renata Dividino, Sergej Sizov, Steffen Staab, and Bernhard Schueler. 2009. Querying for provenance, trust, uncertainty and other meta knowledge in RDF. Web Semantics: Science, Services and Agents on the World Wide Web 7, 3 (2009), 204--219.

Digital Library

[12]

J. Nathan Foster, Todd J. Green, and Val Tannen. 2008. Annotated XML: Queries and provenance. In Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’08). ACM, 271--280.

Digital Library

[13]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

Digital Library

[14]

Floris Geerts, Grigoris Karvounarakis, Vassilis Christophides, and Irini Fundulaki. 2013. Algebraic structures for capturing the provenance of SPARQL queries. In Proceedings of the 16th International Conference on Database Theory (ICDT’13). ACM, 153--164.

Digital Library

[15]

Floris Geerts and Antonella Poggi. 2010. On database query languages for K-relations. Journal of Applied Logic 8, 2 (2010), 173--185.

[16]

Boris Glavic and Gustavo Alonso. 2009. Perm: Processing provenance and data on the same data model through query rewriting. In Proceedings of the 25th International Conference on Data Engineering (ICDE’09). IEEE, 174--185.

Digital Library

[17]

Todd J. Green. 2011. Containment of conjunctive queries on annotated relations. Theory of Computing Systems 49, 2 (2011), 429--459.

Digital Library

[18]

Todd J. Green, Gregory Karvounarakis, and Val Tannen. 2007. Provenance semirings. In Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’07). ACM, 31--40.

Digital Library

[19]

Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. Retrieved http://www.w3.org/TR/sparql11-query/.

[20]

Olaf Hartig. 2008. Specification for tSPARQL. (2008). http://trdf.sf.net/documents/tsparql.pdf.

[21]

Olaf Hartig. 2009. Querying trust in rdf data with tSPARQL. In Proceedings of the 6th European Semantic Web Conference on The Semantic Web: Research and Applications (ESWC’09). Lecture Notes in Computer Science, Vol. 5554. Springer, 5--20.

Digital Library

[22]

Hai Huang and Chengfei Liu. 2009. Query evaluation on probabilistic RDF databases. In Proceedings of the 10th International Conference on Web Information Systems Engineering (WISE’09) (Lecture Notes in Computer Science), Vol. 5802. Springer, 307--320.

Digital Library

[23]

Edward V. Huntington. 1933a. Boolean algebra. A correction. Transactions of the American Mathematical Society 35, 2 (1933), pp. 557--558.

[24]

Edward V. Huntington. 1933b. New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell. Transactions of the American Mathematical Society 35 (1933), 274--304.

[25]

Grigoris Karvounarakis, Todd J. Green, Zachary G. Ives, and Val Tannen. 2013. Collaborative data sharing via update exchange and provenance. ACM Transactions on Database Systems 38, 3, Article 19 (2013), 42 pages.

Digital Library

[26]

Grigoris Karvounarakis, Zachary G. Ives, and Val Tannen. 2010. Querying data provenance. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD’10). ACM, 951--962.

Digital Library

[27]

Anastasios Kementsietsidis, Enela Pema, and Wang-Chiew Tan. 2014. Query answering over incomplete and uncertain RDF. In Proceedings of the 17th International Workshop on the Web and Databases (WebDB’14).

[28]

Frank Manola, Eric Miller, and Brian McBride. 2004. RDF Primer. Retrieved from www.w3.org/TR/rdf-primer.

[29]

Mauro Mazzieri and Aldo Franco Dragoni. 2008. A fuzzy semantics for the resource description framework. In SWC International Workshops Uncertainty Reasoning for the Semantic Web I (URSW). Lecture Notes in Computer Science, Vol. 5327. Springer, 244--261.

Digital Library

[30]

William McCune. 2005--2010. Prover9 and Mace4. Retrieved from http://www.cs.unm.edu/&sim;mccune/prover9/.

[31]

Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. 2009. Semantics and complexity of SPARQL. ACM Transactions on Database Systems 34, 3, Article 16 (2009), 45 pages.

Digital Library

[32]

Eric Prud’hommeaux and Andy Seaborne. 2008. SPARQL Query Language for RDF. www.w3.org/TR/rdf-sparql-query. (January 2008).

[33]

Michael Schmidt, Michael Meier, and Georg Lausen. 2010. Foundations of SPARQL query optimization. In Proceedings of the 13th International Conference on Database Theory (ICDT’10). ACM, 4--33.

Digital Library

[34]

Umberto Straccia. 2013. Foundations of Fuzzy Logic and Semantic Web Languages. Chapman and Hall/CRC.

Digital Library

[35]

Yannis Theoharis, Irini Fundulaki, Grigoris Karvounarakis, and Vassilis Christophides. 2011. On provenance of queries on semantic web data. IEEE Internet Computing 15, 1 (2011), 31--39.

Digital Library

[36]

Octavian Udrea, Diego Reforgiato Recupero, and V. S. Subrahmanian. 2010. Annotated RDF. ACM Transactions on Computational Logic 11, 2, Article 10 (2010), 41 pages.

Digital Library

[37]

Moshe Y. Vardi. 1982. The complexity of relational query languages (extended abstract). In Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC’82). ACM, 137--146.

Digital Library

[38]

Antoine Zimmermann, Nuno Lopes, Axel Polleres, and Umberto Straccia. 2012. A general framework for representing, reasoning and querying with annotated Semantic Web data. Journal of Web Semantics 11 (2012), 72--95.

Digital Library

Cited By

Asma ZHernández DGalárraga LFlouris GFundulaki IHose KChua TNgo CKa-Wei Lee RKumar RLauw H(2024)NPCS: Native Provenance Computation for SPARQLProceedings of the ACM Web Conference 202410.1145/3589334.3645557(2085-2093)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645557
Pan XHernández DSeifer PLämmel RStaab S(2024)eSPARQL: Representing and Reconciling Agnostic and Atheistic Beliefs in RDF-star Knowledge GraphsThe Semantic Web – ISWC 202410.1007/978-3-031-77850-6_9(155-172)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1007/978-3-031-77850-6_9
Galárraga LHernández DKatim AHose K(2023)Visualizing How-Provenance Explanations for SPARQL QueriesCompanion Proceedings of the ACM Web Conference 202310.1145/3543873.3587350(212-216)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543873.3587350
Show More Cited By

Index Terms

Algebraic Structures for Capturing the Provenance of SPARQL Queries
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Data model extensions
        Data provenance
    2. Query languages
      1. Query languages for non-relational engines

Recommendations

Algebraic structures for capturing the provenance of SPARQL queries
ICDT '13: Proceedings of the 16th International Conference on Database Theory

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 ...
RDF, Jena, SparQL and the 'Semantic Web'
SIGUCCS '09: Proceedings of the 37th annual ACM SIGUCCS fall conference: communication and collaboration

The Resource Description Format (RDF) is used to represent information modeled as a "graph": a set of individual objects, along with a set of connections among those objects. In that role, RDF is one of the pillars of the so-called Semantic Web. This ...
Using SPARQL to query bioportal ontologies and metadata
ISWC'12: Proceedings of the 11th international conference on The Semantic Web - Volume Part II

BioPortal is a repository of biomedical ontologies--the largest such repository, with more than 300 ontologies to date. This set includes ontologies that were developed in OWL, OBO and other languages, as well as a large number of medical terminologies ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 63, Issue 1

March 2016

353 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2893450

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 February 2016

Accepted: 01 July 2015

Revised: 01 July 2015

Received: 01 June 2015

Published in JACM Volume 63, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
442
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)4

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Asma ZHernández DGalárraga LFlouris GFundulaki IHose KChua TNgo CKa-Wei Lee RKumar RLauw H(2024)NPCS: Native Provenance Computation for SPARQLProceedings of the ACM Web Conference 202410.1145/3589334.3645557(2085-2093)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645557
Pan XHernández DSeifer PLämmel RStaab S(2024)eSPARQL: Representing and Reconciling Agnostic and Atheistic Beliefs in RDF-star Knowledge GraphsThe Semantic Web – ISWC 202410.1007/978-3-031-77850-6_9(155-172)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1007/978-3-031-77850-6_9
Galárraga LHernández DKatim AHose K(2023)Visualizing How-Provenance Explanations for SPARQL QueriesCompanion Proceedings of the ACM Web Conference 202310.1145/3543873.3587350(212-216)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543873.3587350
Hose K(2023)Knowledge Engineering in the Era of Artificial IntelligenceAdvances in Databases and Information Systems10.1007/978-3-031-42914-9_1(3-15)Online publication date: 28-Aug-2023
https://doi.org/10.1007/978-3-031-42914-9_1
Hernández DGalárraga LHose K(2021)Computing how-provenance for SPARQL queries via query rewritingProceedings of the VLDB Endowment10.14778/3484224.348423514:13(3389-3401)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3484224.3484235
Baur MStuder T(2021)Semirings of EvidenceJournal of Logic and Computation10.1093/logcom/exab007Online publication date: 24-Feb-2021
https://doi.org/10.1093/logcom/exab007
Grädel ETannen V(2020)Provenance analysis for logic and gamesMoscow Journal of Combinatorics and Number Theory10.2140/moscow.2020.9.2039:3(203-228)Online publication date: 15-Oct-2020
https://doi.org/10.2140/moscow.2020.9.203
Bourhis PDeutch DMoskovitch YMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Equivalence-Invariant Algebraic Provenance for Hyperplane Update QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3380578(415-429)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3380578
Sikos LPhilp D(2020)Provenance-Aware Knowledge Representation: A Survey of Data Models and Contextualized Knowledge GraphsData Science and Engineering10.1007/s41019-020-00118-0Online publication date: 8-May-2020
https://doi.org/10.1007/s41019-020-00118-0
Bourgaux COzaki A(2019)Querying attributed DL-lite ontologies using provenance semiringsProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33012719(2719-2726)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33012719
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents