{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T10:18:51Z","timestamp":1777889931665,"version":"3.51.4"},"reference-count":50,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T00:00:00Z","timestamp":1630022400000},"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":[[2021,8,27]]},"abstract":"<jats:p>The need for recursive queries in the Semantic Web setting is becoming more and more apparent with the emergence of datasets where different pieces of information are connected by complicated patterns. This was acknowledged by the W3C committee by the inclusion of property paths in the SPARQL standard. However, as more data becomes available, it is becoming clear that property paths alone are not enough to capture all recursive queries that the users are interested in, and the literature has already proposed several extensions to allow searching for more complex patterns. We propose a rather different, but simpler approach: add a general purpose recursion operator directly to SPARQL. In this paper we provide a formal syntax and semantics for this proposal, study its theoretical properties, and develop algorithms for evaluating it in practical scenarios. We also show how to implement this extension as a plug-in on top of existing systems, and test its performance on several synthetic and real world datasets, ranging from small graphs, up to the entire Wikidata database.<\/jats:p>","DOI":"10.3233\/sw-200401","type":"journal-article","created":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T11:05:27Z","timestamp":1603191927000},"page":"711-740","source":"Crossref","is-referenced-by-count":1,"title":["Recursion in SPARQL"],"prefix":"10.1177","volume":"12","author":[{"given":"Juan","family":"Reutter","sequence":"first","affiliation":[{"name":"Departamento de Ciencia de la Computaci\u00f3n, Pontificia Universidad Cat\u00f3lica de Chile and IMFD Chile, Chile. E-mail:\u00a0jreutter@ing.puc.cl"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adri\u00e1n","family":"Soto","sequence":"additional","affiliation":[{"name":"Faculty of Engineering and Sciences Universidad Adolfo Ib\u00e1\u00f1ez, Data Observatory Foundation and IMFD Chile, Chile. E-mail:\u00a0adrian.soto@uai.cl"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domagoj","family":"Vrgo\u010d","sequence":"additional","affiliation":[{"name":"Instituto de Ingenier\u00eda Matem\u00e1tica y Computacional, Pontificia Universidad Cat\u00f3lica de Chile and IMFD Chile, Chile. E-mail:\u00a0dvrgoc@ing.puc.cl"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/SW-200401_ref1","unstructured":"S.\u00a0Abiteboul, R.\u00a0Hull and V.\u00a0Vianu, Foundations of Databases, Addison-Wesley, 1995."},{"issue":"2","key":"10.3233\/SW-200401_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":"J. Web Sem."},{"issue":"5","key":"10.3233\/SW-200401_ref3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3104031","article-title":"Foundations of modern query languages for graph databases","volume":"50","author":"Angles","year":"2017","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"10.3233\/SW-200401_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46523-4_2"},{"key":"10.3233\/SW-200401_ref5","doi-asserted-by":"crossref","unstructured":"K.\u00a0Anyanwu and A.P.\u00a0Sheth, \u03c1-Queries: Enabling querying for semantic associations on the semantic web, in: 12th International World Wide Web Conference (WWW), 2003.","DOI":"10.1145\/775152.775249"},{"key":"10.3233\/SW-200401_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594555"},{"key":"10.3233\/SW-200401_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04329-1_13"},{"key":"10.3233\/SW-200401_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/ICSC.2014.54"},{"issue":"4","key":"10.3233\/SW-200401_ref9","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1109\/TKDE.2016.2633993","article-title":"gMark: Schema-driven generation of graphs and queries","volume":"29","author":"Bagan","year":"2017","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"10.3233\/SW-200401_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45221-5_5"},{"key":"10.3233\/SW-200401_ref11","unstructured":"P.\u00a0Barcel\u00f3, J.\u00a0P\u00e9rez and J.L.\u00a0Reutter, Relative expressiveness of nested regular expressions, in: AMW, 2012, pp.\u00a0180\u2013195."},{"issue":"9","key":"10.3233\/SW-200401_ref12","doi-asserted-by":"publisher","first-page":"975","DOI":"10.14778\/3213880.3213888","article-title":"The vadalog system: Datalog-based reasoning for knowledge graphs","volume":"11","author":"Bellomarini","year":"2018","journal-title":"Proceedings of the VLDB Endowment"},{"key":"10.3233\/SW-200401_ref13","unstructured":"M.\u00a0Bienvenu, D.\u00a0Calvanese, M.\u00a0Ortiz and M.\u00a0Simkus, Nested regular path queries in description logics, in: KR 2014, Vienna, Austria, July 20\u201324, 2014, 2014."},{"key":"10.3233\/SW-200401_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_37"},{"key":"10.3233\/SW-200401_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68288-4_7"},{"issue":"3","key":"10.3233\/SW-200401_ref16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00873ED1V01Y201808DTM051","article-title":"Querying graphs","volume":"10","author":"Bonifati","year":"2018","journal-title":"Synthesis Lectures on Data Management"},{"key":"10.3233\/SW-200401_ref17","unstructured":"P.\u00a0Bourhis, M.\u00a0Kr\u00f6tzsch and S.\u00a0Rudolph, How to best nest regular path queries, in: Informal Proceedings of the 27th International Workshop on Description Logics, 2014."},{"key":"10.3233\/SW-200401_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298591"},{"key":"10.3233\/SW-200401_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_9"},{"key":"10.3233\/SW-200401_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58068-5_2"},{"key":"10.3233\/SW-200401_ref21","doi-asserted-by":"crossref","unstructured":"V.\u00a0Fionda, G.\u00a0Pirr\u00f2 and M.P.\u00a0Consens, Extended property paths: Writing more SPARQL queries in a succinct way, in: Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.","DOI":"10.1609\/aaai.v29i1.9188"},{"issue":"1","key":"10.3233\/SW-200401_ref22","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2697393","article-title":"NautiLod: A formal language for the web of data graph","volume":"9","author":"Fionda","year":"2015","journal-title":"ACM Transactions on the Web (TWEB)"},{"issue":"3","key":"10.3233\/SW-200401_ref23","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1145\/174130.174142","article-title":"Undecidable optimization problems for database logic programs","volume":"40","author":"Gaifman","year":"1993","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"10.3233\/SW-200401_ref24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1561\/1900000017","article-title":"Datalog and recursive query processing","volume":"5","author":"Green","year":"2013","journal-title":"Foundations and Trends in Databases"},{"key":"10.3233\/SW-200401_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484443"},{"key":"10.3233\/SW-200401_ref28","unstructured":"P.\u00a0Hitzler, M.\u00a0Krotzsch and S.\u00a0Rudolph, Foundations of Semantic Web Technologies, CRC Press, 2011."},{"key":"10.3233\/SW-200401_ref29","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2016.5"},{"key":"10.3233\/SW-200401_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72667-8_12"},{"key":"10.3233\/SW-200401_ref31","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2015.212"},{"issue":"1","key":"10.3233\/SW-200401_ref32","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/3154385","article-title":"TriAL: A navigational algebra for RDF triplestores","volume":"43","author":"Libkin","year":"2018","journal-title":"ACM Trans. Database Syst."},{"key":"10.3233\/SW-200401_ref33","unstructured":"Linked movie database."},{"key":"10.3233\/SW-200401_ref34","doi-asserted-by":"publisher","DOI":"10.1145\/2457317.2457375"},{"key":"10.3233\/SW-200401_ref35","doi-asserted-by":"crossref","unstructured":"B.\u00a0Motik, Y.\u00a0Nenov, R.\u00a0Piro, I.\u00a0Horrocks and D.\u00a0Olteanu, Parallel materialisation of datalog programs in centralised, main-memory RDF systems, in: AAAI, 2014.","DOI":"10.1609\/aaai.v28i1.8730"},{"key":"10.3233\/SW-200401_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25010-6_1"},{"issue":"3\u20134","key":"10.3233\/SW-200401_ref37","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1023\/A:1018930122475","article-title":"Logic programs with stable model semantics as a constraint programming paradigm","volume":"25","author":"Niemel\u00e4","year":"1999","journal-title":"Ann. Math. Artif. Intell."},{"key":"10.3233\/SW-200401_ref38","unstructured":"Open Link Virtuoso, 2015."},{"key":"10.3233\/SW-200401_ref39","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"issue":"4","key":"10.3233\/SW-200401_ref40","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.websem.2010.01.002","article-title":"nSPARQL: A navigational language for RDF","volume":"8","author":"P\u00e9rez","year":"2010","journal-title":"J. Web Sem."},{"issue":"1\u20132","key":"10.3233\/SW-200401_ref41","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":"Journal of Applied Non-Classical Logics"},{"key":"10.3233\/SW-200401_ref42","unstructured":"PostgreSQL documentation."},{"issue":"1","key":"10.3233\/SW-200401_ref43","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00224-016-9676-2","article-title":"Regular queries on graph databases","volume":"61","author":"Reutter","year":"2017","journal-title":"Theory of Computing Systems"},{"key":"10.3233\/SW-200401_ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_2"},{"key":"10.3233\/SW-200401_ref45","doi-asserted-by":"publisher","DOI":"10.2307\/2963937"},{"key":"10.3233\/SW-200401_ref46","unstructured":"The Apache Jena Manual, 2015."},{"key":"10.3233\/SW-200401_ref47","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"},{"key":"10.3233\/SW-200401_ref48","unstructured":"W3C, PROV Model Primer, 2013."},{"key":"10.3233\/SW-200401_ref49","unstructured":"W3C, PROV-O: The PROV Ontology, 2013."},{"key":"10.3233\/SW-200401_ref50","unstructured":"YAGO: A High-Quality Knowledge Base."},{"key":"10.3233\/SW-200401_ref51","unstructured":"N.\u00a0Yakovets, P.\u00a0Godfrey and J.\u00a0Gryz, Evaluation of SPARQL property paths via recursive SQL, in: AMW, 2013."},{"key":"10.3233\/SW-200401_ref52","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2015.49"}],"container-title":["Semantic Web"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SW-200401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:25:04Z","timestamp":1777613104000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SW-200401"}},"subtitle":[],"editor":[{"given":"Oscar","family":"Corcho","sequence":"additional","affiliation":[{"name":"Universidad Polit\u00e9cnica de Madrid, Spain"}],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,8,27]]},"references-count":50,"journal-issue":{"issue":"5"},"URL":"https:\/\/doi.org\/10.3233\/sw-200401","relation":{},"ISSN":["2210-4968","1570-0844"],"issn-type":[{"value":"2210-4968","type":"electronic"},{"value":"1570-0844","type":"print"}],"subject":[],"published":{"date-parts":[[2021,8,27]]}}}