{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T01:11:15Z","timestamp":1788570675450,"version":"build-2803163510"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T00:00:00Z","timestamp":1455235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,3,30]]},"abstract":"<jats:p>\n                    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\n                    <jats:italic>spm-semirings<\/jats:italic>\n                    . 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.\n                  <\/jats:p>","DOI":"10.1145\/2810037","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T08:07:16Z","timestamp":1456128436000},"page":"1-63","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Algebraic Structures for Capturing the Provenance of SPARQL Queries"],"prefix":"10.1145","volume":"63","author":[{"given":"Floris","family":"Geerts","sequence":"first","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Unger","sequence":"additional","affiliation":[{"name":"University College Dublin, Dublin, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Grigoris","family":"Karvounarakis","sequence":"additional","affiliation":[{"name":"LogicBlox, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Irini","family":"Fundulaki","sequence":"additional","affiliation":[{"name":"ICS-FORTH, Heraklion, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vassilis","family":"Christophides","sequence":"additional","affiliation":[{"name":"Inria Paris-Rocquencourt, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,2,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance (TaPP\u201911)","author":"Amsterdamer Yael","year":"2011","unstructured":"Yael Amsterdamer , Daniel Deutch , and Val Tannen . 2011 a. On the limitations of provenance for queries with difference . In Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance (TaPP\u201911) . USENIX Association. 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\u201911). USENIX Association."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88564-1_8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412340"},{"key":"e_1_2_1_6_1","volume-title":"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.","author":"Buneman Peter","unstructured":"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. 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."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Stanley Burris and H. P. Sankappanavar. 1981. A Course in Universal Algebra. Number 78 in Graduate Texts in Mathematics. Springer-Verlag.  Stanley Burris and H. P. Sankappanavar. 1981. A Course in Universal Algebra. Number 78 in Graduate Texts in Mathematics. Springer-Verlag.","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.09.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35176-1_39"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2009.07.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376954"},{"key":"e_1_2_1_13_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448516"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2009.09.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.15"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_19_1","unstructured":"Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. Retrieved http:\/\/www.w3.org\/TR\/sparql11-query\/.  Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. Retrieved http:\/\/www.w3.org\/TR\/sparql11-query\/."},{"key":"e_1_2_1_20_1","unstructured":"Olaf Hartig. 2008. Specification for tSPARQL. (2008). http:\/\/trdf.sf.net\/documents\/tsparql.pdf.  Olaf Hartig. 2008. Specification for tSPARQL. (2008). http:\/\/trdf.sf.net\/documents\/tsparql.pdf."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02121-3_5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04409-0_32"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"557","DOI":"10.2307\/1989783","article-title":"Boolean algebra. A correction","volume":"35","author":"Huntington Edward V.","year":"1933","unstructured":"Edward V. Huntington . 1933 a. Boolean algebra. A correction . Transactions of the American Mathematical Society 35 , 2 (1933), pp. 557 -- 558 . Edward V. Huntington. 1933a. Boolean algebra. A correction. Transactions of the American Mathematical Society 35, 2 (1933), pp. 557--558.","journal-title":"Transactions of the American Mathematical Society"},{"key":"e_1_2_1_24_1","first-page":"274","article-title":"New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell","volume":"35","author":"Huntington Edward V.","year":"1933","unstructured":"Edward V. Huntington . 1933 b. 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 . 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.","journal-title":"Transactions of the American Mathematical Society"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500127"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807269"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 17th International Workshop on the Web and Databases (WebDB\u201914)","author":"Kementsietsidis Anastasios","year":"2014","unstructured":"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\u201914) . 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\u201914)."},{"key":"e_1_2_1_28_1","unstructured":"Frank Manola Eric Miller and Brian McBride. 2004. RDF Primer. Retrieved from www.w3.org\/TR\/rdf-primer.  Frank Manola Eric Miller and Brian McBride. 2004. RDF Primer. Retrieved from www.w3.org\/TR\/rdf-primer."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89765-1_15"},{"key":"e_1_2_1_30_1","unstructured":"William McCune. 2005--2010. Prover9 and Mace4. Retrieved from http:\/\/www.cs.unm.edu\/&sim;mccune\/prover9\/.  William McCune. 2005--2010. Prover9 and Mace4. Retrieved from http:\/\/www.cs.unm.edu\/&sim;mccune\/prover9\/."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_1_32_1","volume-title":"SPARQL Query Language for RDF. www.w3.org\/TR\/rdf-sparql-query. (January","author":"Prud\u2019hommeaux Eric","year":"2008","unstructured":"Eric Prud\u2019hommeaux and Andy Seaborne . 2008. SPARQL Query Language for RDF. www.w3.org\/TR\/rdf-sparql-query. (January 2008 ). Eric Prud\u2019hommeaux and Andy Seaborne. 2008. SPARQL Query Language for RDF. www.w3.org\/TR\/rdf-sparql-query. (January 2008)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804675"},{"key":"e_1_2_1_34_1","volume-title":"Foundations of Fuzzy Logic and Semantic Web Languages","author":"Straccia Umberto","unstructured":"Umberto Straccia . 2013. Foundations of Fuzzy Logic and Semantic Web Languages . Chapman and Hall\/CRC. Umberto Straccia. 2013. Foundations of Fuzzy Logic and Semantic Web Languages. Chapman and Hall\/CRC."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2010.127"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1656242.1656245"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2011.08.006"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2810037","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2810037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:48:35Z","timestamp":1750211315000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2810037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,12]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,3,30]]}},"alternative-id":["10.1145\/2810037"],"URL":"https:\/\/doi.org\/10.1145\/2810037","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,12]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}