{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T12:16:44Z","timestamp":1773317804604,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,9,30]],"date-time":"2018-09-30T00:00:00Z","timestamp":1538265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Fondecyt","award":["1161473"],"award-info":[{"award-number":["1161473"]}]},{"name":"Instituto Milenio Fundamentos de los Datos"},{"name":"EPSRC Programme Grant \u201cVADA: Value Added Data Systems - Principles and Architecture\u201d","award":["EP\/M025268\/"],"award-info":[{"award-number":["EP\/M025268\/"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"<jats:p>The problem of querying RDF data is a central issue for the development of the Semantic Web. The query language SPARQL has become the standard language for querying RDF since its W3C standardization in 2008. However, the 2008 version of this language missed some important functionalities: reasoning capabilities to deal with RDFS and OWL vocabularies, navigational capabilities to exploit the graph structure of RDF data, and a general form of recursion much needed to express some natural queries. To overcome these limitations, a new version of SPARQL, called SPARQL 1.1, was released in 2013, which includes entailment regimes for RDFS and OWL vocabularies, and a mechanism to express navigation patterns through regular expressions. Unfortunately, there are a number of useful navigation patterns that cannot be expressed in SPARQL 1.1, and the language lacks a general mechanism to express recursive queries. To the best of our knowledge, no efficient RDF query language that combines the above functionalities is known. It is the aim of this work to fill this gap. To this end, we focus on a core fragment of the OWL 2 QL profile of OWL 2 and show that every SPARQL query enriched with the above features can be naturally translated into a query expressed in a language that is based on an extension of Datalog, which allows for value invention and stratified negation. However, the query evaluation problem for this language is highly intractable, which is not surprising since it is expressive enough to encode some inherently hard queries. We identify a natural fragment of it, and we show it to be tractable and powerful enough to define SPARQL queries enhanced with the desired functionalities.<\/jats:p>","DOI":"10.1145\/3238304","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Expressive Languages for Querying the Semantic Web"],"prefix":"10.1145","volume":"43","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile 8 IMFD, Chile"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"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","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2009.02.002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88564-1_8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594555"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03754-2_4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 8th International Colloquium on Automata, Languages and Programming. 73--85","author":"Beeri Catriel","unstructured":"Catriel Beeri and Moshe Y. Vardi . 1981. The implication problem for data dependencies . In Proceedings of the 8th International Colloquium on Automata, Languages and Programming. 73--85 . Catriel Beeri and Moshe Y. Vardi. 1981. The implication problem for data dependencies. In Proceedings of the 8th International Colloquium on Automata, Languages and Programming. 73--85."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171643"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213888"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 38th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. To Appear.","author":"Berger Gerald","year":"2018","unstructured":"Gerald Berger , Georg Gottlob , Andreas Pieris , and Emanuel Sallinger . 2018 . The space-efficient core of Vadalog . In Proceedings of the 38th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. To Appear. Gerald Berger, Georg Gottlob, Andreas Pieris, and Emanuel Sallinger. 2018. The space-efficient core of Vadalog. In Proceedings of the 38th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. To Appear."},{"key":"e_1_2_1_12_1","volume-title":"Datalog: Bag semantics via set semantics. CoRR abs\/1803.06445","author":"Bertossi Leopoldo E.","year":"2018","unstructured":"Leopoldo E. Bertossi , Georg Gottlob , and Reinhard Pichler . 2018 . Datalog: Bag semantics via set semantics. CoRR abs\/1803.06445 (2018). arxiv:1803.06445 http:\/\/arxiv.org\/abs\/1803.06445. Leopoldo E. Bertossi, Georg Gottlob, and Reinhard Pichler. 2018. Datalog: Bag semantics via set semantics. CoRR abs\/1803.06445 (2018). arxiv:1803.06445 http:\/\/arxiv.org\/abs\/1803.06445."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591248.2591252"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.27"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9078-x"},{"key":"e_1_2_1_17_1","volume-title":"Logic Programming and Databases","author":"Ceri Stefano","unstructured":"Stefano Ceri , Georg Gottlob , and Letizia Tanca . 1990. Logic Programming and Databases . Springer . Stefano Ceri, Georg Gottlob, and Letizia Tanca. 1990. Logic Programming and Databases. Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2009.04.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187875"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Tim Furche Benedikt Linse Fran\u00e7ois Bry Dimitris Plexousakis and Georg Gottlob. 2006. RDF querying: Language constructs and evaluation methods compared. In Reasoning Web. 1--52.  Tim Furche Benedikt Linse Fran\u00e7ois Bry Dimitris Plexousakis and Georg Gottlob. 2006. RDF querying: Language constructs and evaluation methods compared. In Reasoning Web. 1--52.","DOI":"10.1007\/11837787_1"},{"key":"e_1_2_1_22_1","volume-title":"Retrieved","author":"Glimm Birte","year":"2013","unstructured":"Birte Glimm and Chimezie Ogbuji . 2013 . SPARQL 1.1 Entailment Regimes . Retrieved March 21, 2013 from, http:\/\/www.w3.org\/TR\/sparql11-entailment\/. Birte Glimm and Chimezie Ogbuji. 2013. SPARQL 1.1 Entailment Regimes. Retrieved March 21, 2013 from, http:\/\/www.w3.org\/TR\/sparql11-entailment\/."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2999--3007","author":"Gottlob Georg","year":"2015","unstructured":"Georg Gottlob and Andreas Pieris . 2015 . Beyond SPARQL under OWL 2 QL entailment regime: Rules to the rescue . In Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2999--3007 . Georg Gottlob and Andreas Pieris. 2015. Beyond SPARQL under OWL 2 QL entailment regime: Rules to the rescue. In Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2999--3007."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594556"},{"key":"e_1_2_1_25_1","volume-title":"Retrieved","author":"Harris Steve","year":"2013","unstructured":"Steve Harris and Andy Seaborne . 2013 . SPARQL 1.1 Query Language . Retrieved March 21, 2013 from http:\/\/www.w3.org\/TR\/sparql11-query\/. Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. Retrieved March 21, 2013 from http:\/\/www.w3.org\/TR\/sparql11-query\/."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465229"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2014.06.004"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008892.2008925"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465226"},{"key":"e_1_2_1_30_1","volume-title":"OWL Web Ontology Language Overview. Retrieved on","author":"Deborah","year":"2004","unstructured":"Deborah L. McGuinness and Frank van Harmelen. 2004 . OWL Web Ontology Language Overview. Retrieved on February 10, 2004 from http:\/\/www.w3.org\/TR\/owl-features\/. Deborah L. McGuinness and Frank van Harmelen. 2004. OWL Web Ontology Language Overview. Retrieved on February 10, 2004 from http:\/\/www.w3.org\/TR\/owl-features\/."},{"key":"e_1_2_1_31_1","volume-title":"Retrieved","author":"Motik Boris","year":"2012","unstructured":"Boris Motik , Bernardo Cuenca Grau , Ian Horrocks , Zhe Wu , Achille Fokoue , and Carsten Lutz . 2012 . OWL 2 Web Ontology Language Profiles (2nd ed.) . Retrieved December 11, 2012 from http:\/\/www.w3.org\/TR\/owl2-profiles\/. Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, Zhe Wu, Achille Fokoue, and Carsten Lutz. 2012. OWL 2 Web Ontology Language Profiles (2nd ed.). Retrieved December 11, 2012 from http:\/\/www.w3.org\/TR\/owl2-profiles\/."},{"key":"e_1_2_1_32_1","volume-title":"OWL 2 Web Ontology Language Structural Specification and Functional-Style Syntax","author":"Motik Boris","year":"2012","unstructured":"Boris Motik , Peter F. Patel-Schneider , and Bijan Parsia . 2012. OWL 2 Web Ontology Language Structural Specification and Functional-Style Syntax ( 2 nd ed.). Retrieved December 11, 2012 from http:\/\/www.w3.org\/TR\/owl2-syntax\/. Boris Motik, Peter F. Patel-Schneider, and Bijan Parsia. 2012. OWL 2 Web Ontology Language Structural Specification and Functional-Style Syntax (2nd ed.). Retrieved December 11, 2012 from http:\/\/www.w3.org\/TR\/owl2-syntax\/.","edition":"2"},{"key":"e_1_2_1_33_1","volume-title":"Patel-Schneider and Boris Motik","author":"Peter","year":"2012","unstructured":"Peter F. Patel-Schneider and Boris Motik . 2012 . OWL 2 Web Ontology Language Mapping to RDF Graphs (2nd ed.). Retrieved 11 December 2012 from http:\/\/www.w3.org\/TR\/owl2-mapping-to-rdf\/. Peter F. Patel-Schneider and Boris Motik. 2012. OWL 2 Web Ontology Language Mapping to RDF Graphs (2nd ed.). Retrieved 11 December 2012 from http:\/\/www.w3.org\/TR\/owl2-mapping-to-rdf\/."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2010.01.002"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242679"},{"key":"e_1_2_1_37_1","volume-title":"Retrieved","author":"Prud\u2019hommeaux Eric","year":"2008","unstructured":"Eric Prud\u2019hommeaux and Andy Seaborne . 2008 . SPARQL Query Language for RDF . Retrieved January 15, 2008 from http:\/\/www.w3.org\/TR\/rdf-sparql-query\/. Eric Prud\u2019hommeaux and Andy Seaborne. 2008. SPARQL Query Language for RDF. Retrieved January 15, 2008 from http:\/\/www.w3.org\/TR\/rdf-sparql-query\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465227"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74565-5_14"},{"key":"e_1_2_1_41_1","volume-title":"OWL 2 Web Ontology Language Document Overview","author":"W3C OWL Working Group","year":"2012","unstructured":"W3C OWL Working Group . 2012. OWL 2 Web Ontology Language Document Overview ( 2 nd ed.). Retrieved December 11, 2012 from http:\/\/www.w3.org\/TR\/owl2-overview\/. W3C OWL Working Group. 2012. OWL 2 Web Ontology Language Document Overview (2nd ed.). Retrieved December 11, 2012 from http:\/\/www.w3.org\/TR\/owl2-overview\/.","edition":"2"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3238304","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3238304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:41Z","timestamp":1750210781000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3238304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,30]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3238304"],"URL":"https:\/\/doi.org\/10.1145\/3238304","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,30]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}