{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T22:30:43Z","timestamp":1778106643173,"version":"3.51.4"},"reference-count":56,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SW"],"published-print":{"date-parts":[[2022,8,18]]},"abstract":"<jats:p>We define a procedure for canonicalising SPARQL 1.1 queries. Specifically, given two input queries that return the same solutions modulo variable names over any RDF graph (which we call congruent queries), the canonicalisation procedure aims to rewrite both input queries to a syntactically canonical query that likewise returns the same results modulo variable renaming. The use-cases for such canonicalisation include caching, optimisation, redundancy elimination, question answering, and more besides. To begin, we formally define the semantics of the SPARQL 1.1 language, including features often overlooked in the literature. We then propose a canonicalisation procedure based on mapping a SPARQL query to an RDF graph, applying algebraic rewritings, removing redundancy, and then using canonical labelling techniques to produce a canonical form. Unfortunately a full canonicalisation procedure for SPARQL 1.1 queries would be undecidable. We rather propose a procedure that we prove to be sound and complete for a decidable fragment of monotone queries under both set and bag semantics, and that is sound but incomplete in the case of the full SPARQL 1.1 query language. Although the worst case of the procedure is super-exponential, our experiments show that it is efficient for real-world queries, and that such difficult cases are rare.<\/jats:p>","DOI":"10.3233\/sw-212871","type":"journal-article","created":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T12:38:48Z","timestamp":1642768728000},"page":"829-893","source":"Crossref","is-referenced-by-count":7,"title":["Semantics and canonicalisation of SPARQL\u00a01.1"],"prefix":"10.1177","volume":"13","author":[{"given":"Jaime","family":"Salas","sequence":"first","affiliation":[{"name":"DCC, Universidad de Chile; IMFD, Chile. E-mails:\u00a0jaime.os.salas@gmail.com,\u00a0ahogan@dcc.uchile.cl"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"DCC, Universidad de Chile; IMFD, Chile. E-mails:\u00a0jaime.os.salas@gmail.com,\u00a0ahogan@dcc.uchile.cl"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"issue":"10","key":"10.3233\/SW-212871_ref1","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.ipl.2010.02.017","article-title":"Query containment under bag and bag-set semantics","volume":"110","author":"Afrati","year":"2010","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10.3233\/SW-212871_ref2","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.websem.2009.02.002","article-title":"Extending SPARQL with regular expression patterns (for querying RDF)","volume":"7","author":"Alkhateeb","year":"2009","journal-title":"Web Semantics"},{"key":"10.3233\/SW-212871_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"10.3233\/SW-212871_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41338-4_18"},{"key":"10.3233\/SW-212871_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33158-9_3"},{"issue":"4","key":"10.3233\/SW-212871_ref6","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/3129247","article-title":"Designing a query language for RDF: Marrying open and closed worlds","volume":"42","author":"Arenas","year":"2017","journal-title":"ACM Trans. Database Syst."},{"issue":"2\u20133","key":"10.3233\/SW-212871_ref7","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s00778-019-00558-9","article-title":"An analytical study of large SPARQL query logs","volume":"29","author":"Bonifati","year":"2020","journal-title":"VLDB J."},{"key":"10.3233\/SW-212871_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1963.263416"},{"key":"10.3233\/SW-212871_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16985-4_12"},{"key":"10.3233\/SW-212871_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"10.3233\/SW-212871_ref12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/153850.153856","volume-title":"Optimization of Real Conjunctive Queries, in: Principles of Database Systems (PODS)","author":"Chaudhuri","year":"1993"},{"key":"10.3233\/SW-212871_ref13","doi-asserted-by":"crossref","unstructured":"M.W. Chekol, J. Euzenat, P. Genev\u00e8s and N. Laya\u00efda, SPARQL Query Containment Under SHI Axioms, in: AAAI Conference on Artificial Intelligence, AAAI Press, 2012.","DOI":"10.1007\/978-3-642-31365-3_13"},{"key":"10.3233\/SW-212871_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41338-4_26"},{"issue":"11","key":"10.3233\/SW-212871_ref15","doi-asserted-by":"publisher","first-page":"1482","DOI":"10.14778\/3236187.3236200","article-title":"Axiomatic foundations and algorithms for deciding semantic equivalences of SQL queries","volume":"11","author":"Chu","year":"2018","journal-title":"Proc. VLDB Endow."},{"key":"10.3233\/SW-212871_ref16","unstructured":"S. Chu, C. Wang, K. Weitz and A. Cheung, Cosette: An automated prover for SQL, in: Conference on Innovative Data Systems Research (CIDR), 2017, www.cidrdb.org."},{"key":"10.3233\/SW-212871_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303992"},{"key":"10.3233\/SW-212871_ref19","unstructured":"R. Cyganiak, D. Wood and M. Lanthaler, RDF 1.1 Concepts and Abstract Syntax, 2014. http:\/\/www.w3.org\/TR\/rdf11-concepts\/."},{"key":"10.3233\/SW-212871_ref20","doi-asserted-by":"publisher","DOI":"10.17487\/RFC3987"},{"key":"10.3233\/SW-212871_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68234-9_61"},{"issue":"3","key":"10.3233\/SW-212871_ref22","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1016\/j.jcss.2010.04.009","article-title":"Foundations of Semantic Web databases","volume":"77","author":"Gutierrez","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10.3233\/SW-212871_ref23","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/MPRV.2008.80","article-title":"OpenStreetMap: User-generated street maps","volume":"7","author":"Haklay","year":"2008","journal-title":"IEEE Pervasive Comput."},{"key":"10.3233\/SW-212871_ref26","isbn-type":"print","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-031-79432-2","volume-title":"Linked Data: Evolving the Web into a Global Data Space","author":"Heath","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9781608454310"},{"issue":"4","key":"10.3233\/SW-212871_ref28","doi-asserted-by":"publisher","first-page":"22:1","DOI":"10.1145\/3068333","article-title":"Canonical forms for isomorphic and equivalent RDF graphs: Algorithms for leaning and labelling blank nodes","volume":"11","author":"Hogan","year":"2017","journal-title":"ACM TOW"},{"key":"10.3233\/SW-212871_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"issue":"3","key":"10.3233\/SW-212871_ref30","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/211414.211419","article-title":"Containment of conjunctive queries: Beyond relations as sets","volume":"20","author":"Ioannidis","year":"1995","journal-title":"ACM Trans. Database Syst."},{"key":"10.3233\/SW-212871_ref31","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.13"},{"issue":"3","key":"10.3233\/SW-212871_ref32","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3083898","article-title":"Query nesting, assignment, and aggregation in SPARQL 1.1","volume":"42","author":"Kaminski","year":"2017","journal-title":"ACM Trans. Database Syst."},{"key":"10.3233\/SW-212871_ref33","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.websem.2017.05.005","article-title":"Ontology based data access in statoil","volume":"44","author":"Kharlamov","year":"2017","journal-title":"J. Web Semant."},{"key":"10.3233\/SW-212871_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_1"},{"issue":"2","key":"10.3233\/SW-212871_ref35","doi-asserted-by":"publisher","first-page":"167","DOI":"10.3233\/SW-140134","article-title":"DBpedia \u2013 a large-scale, multilingual knowledge base extracted from Wikipedia","volume":"6","author":"Lehmann","year":"2015","journal-title":"Semantic Web"},{"issue":"4","key":"10.3233\/SW-212871_ref36","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/2500130","article-title":"Static analysis and optimization of semantic web queries","volume":"38","author":"Letelier","year":"2013","journal-title":"ACM Trans. Database Syst."},{"key":"10.3233\/SW-212871_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_23"},{"issue":"6","key":"10.3233\/SW-212871_ref38","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1109\/MIC.2002.1067737","article-title":"Jena: A Semantic Web toolkit","volume":"6","author":"McBride","year":"2002","journal-title":"IEEE Internet Computing"},{"key":"10.3233\/SW-212871_ref39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1007\/978-3-540-76298-0_58","volume-title":"Recipes for Semantic Web Dog Food \u2013 the ESWC and ISWC Metadata Projects, in: International Semantic Web Conference (ISWC)","author":"M\u00f6ller","year":"2007"},{"key":"10.3233\/SW-212871_ref40","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-319-46547-0_16","article-title":"Conference linked data: The ScholarlyData project, in: International Semantic Web Conference (ISWC)","volume":"9982","author":"Nuzzolese","year":"2016","journal-title":"Lecture Notes in Computer Science"},{"key":"10.3233\/SW-212871_ref41","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723714"},{"key":"10.3233\/SW-212871_ref42","unstructured":"P.F. Patel-Schneider and D. Martin, EXISTStential aspects of SPARQL, in: ISWC 2016 Posters & Demonstrations Track, CEUR Workshop Proceedings, Vol. 1690, CEUR-WS.org, 2016."},{"key":"10.3233\/SW-212871_ref43","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/11926078_3","volume-title":"Semantics and Complexity of SPARQL, in: International Semantic Web Conference (ISWC)","author":"P\u00e9rez","year":"2006"},{"key":"10.3233\/SW-212871_ref44","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"10.3233\/SW-212871_ref45","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594542"},{"key":"10.3233\/SW-212871_ref46","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242679"},{"issue":"1\u20132","key":"10.3233\/SW-212871_ref47","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1080\/11663081.2013.798992","article-title":"On the relation between SPARQL1.1 and answer set programming","volume":"23","author":"Polleres","year":"2013","journal-title":"J. Appl. Non Class. Logics"},{"issue":"4","key":"10.3233\/SW-212871_ref49","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1145\/322217.322221","article-title":"Equivalences among relational expressions with the union and difference operators","volume":"27","author":"Sagiv","year":"1980","journal-title":"J. ACM"},{"key":"10.3233\/SW-212871_ref50","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00671-6_35"},{"key":"10.3233\/SW-212871_ref52","series-title":"International Semantic Web Conference (ISWC)","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-319-25010-6_15","volume-title":"LSQ: The Linked SPARQL Queries Dataset","author":"Saleem","year":"2015"},{"key":"10.3233\/SW-212871_ref53","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804675"},{"issue":"4","key":"10.3233\/SW-212871_ref56","doi-asserted-by":"publisher","first-page":"333","DOI":"10.3233\/SW-2011-0052","article-title":"LinkedGeoData: A core for a web of spatial open data","volume":"3","author":"Stadler","year":"2012","journal-title":"Semantic Web"},{"key":"10.3233\/SW-212871_ref57","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91662-0_16"},{"key":"10.3233\/SW-212871_ref58","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91662-0_16"},{"issue":"6","key":"10.3233\/SW-212871_ref59","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","article-title":"Regular expression search algorithm","volume":"11","author":"Thompson","year":"1968","journal-title":"Commun. ACM"},{"key":"10.3233\/SW-212871_ref60","unstructured":"B. Trakhtenbrot, The impossibility of an algorithm for the decidability problem on finite classes, in: Proceedings of the USSR Academy of Sciences, Vol. 70, 1950, pp. 569\u2013572."},{"issue":"10","key":"10.3233\/SW-212871_ref61","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2629489","article-title":"Wikidata: A free collaborative knowledgebase","volume":"57","author":"Vrandecic","year":"2014","journal-title":"Commun. ACM"},{"key":"10.3233\/SW-212871_ref62","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25073-6_48"},{"key":"10.3233\/SW-212871_ref63","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/777"},{"key":"10.3233\/SW-212871_ref64","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-62419-4_38"},{"issue":"11","key":"10.3233\/SW-212871_ref65","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.14778\/3342263.3342267","article-title":"Automated verification of query equivalence using satisfiability modulo theories","volume":"12","author":"Zhou","year":"2019","journal-title":"Proc. VLDB Endow."}],"container-title":["Semantic Web"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SW-212871","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:26:17Z","timestamp":1777613177000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SW-212871"}},"subtitle":[],"editor":[{"given":"Guilin","family":"Qi","sequence":"additional","affiliation":[{"name":"Southeast University, China"}],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":56,"journal-issue":{"issue":"5"},"URL":"https:\/\/doi.org\/10.3233\/sw-212871","relation":{},"ISSN":["2210-4968","1570-0844"],"issn-type":[{"value":"2210-4968","type":"electronic"},{"value":"1570-0844","type":"print"}],"subject":[],"published":{"date-parts":[[2022,8,18]]}}}