{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:52Z","timestamp":1773481912408,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T00:00:00Z","timestamp":1521763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Nucleus Millenium Center for Semantic Web Research","award":["NC12004"],"award-info":[{"award-number":["NC12004"]}]},{"name":"CONICYT-PCHA Doctorado Nacional","award":["2017-21171731"],"award-info":[{"award-number":["2017-21171731"]}]},{"name":"FONDECYT Project","award":["11160383"],"award-info":[{"award-number":["11160383"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/N023056\/1 and EP\/M025268\/1"],"award-info":[{"award-number":["EP\/N023056\/1 and EP\/M025268\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>Navigational queries over RDF data are viewed as one of the main applications of graph query languages, and yet the standard model of graph databases\u2014essentially labeled graphs\u2014is different from the triples-based model of RDF. While encodings of RDF databases into graph data exist, we show that even the most natural ones are bound to lose some functionality when used in conjunction with graph query languages. The solution is to work directly with triples, but then many properties taken for granted in the graph database context (e.g., reachability) lose their natural meaning.<\/jats:p>\n          <jats:p>Our goal is to introduce languages that work directly over triples and are closed, i.e., they produce sets of triples, rather than graphs. Our basic language is called TriAL, or Triple Algebra: it guarantees closure properties by replacing the product with a family of join operations. We extend TriAL with recursion and explain why such an extension is more intricate for triples than for graphs. We present a declarative language, namely a fragment of datalog, capturing the recursive algebra. For both languages, the combined complexity of query evaluation is given by low-degree polynomials. We compare our language with previously studied graph query languages such as adaptations of XPath, regular path queries, and nested regular expressions; many of these languages are subsumed by the recursive triple algebra. We also provide an implementation of recursive TriAL on top of a relational query engine, and we show its usefulness by running a wide array of navigational queries over real-world RDF data, while at the same time testing how our implementation compares to existing RDF systems.<\/jats:p>","DOI":"10.1145\/3154385","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T12:29:49Z","timestamp":1521808189000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["TriAL"],"prefix":"10.1145","volume":"43","author":[{"given":"Leonid","family":"Libkin","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2186-0312","authenticated-orcid":false,"given":"Juan L.","family":"Reutter","sequence":"additional","affiliation":[{"name":"Pontifica Universidad Cat\u00f3lica de Chile and Center for Semantic Web Research, Santiago, Chile"}]},{"given":"Adri\u00e1n","family":"Soto","sequence":"additional","affiliation":[{"name":"Pontifica Universidad Cat\u00f3lica de Chile and Center for Semantic Web Research, Santiago, Chile"}]},{"given":"Domagoj","family":"Vrgo\u010d","sequence":"additional","affiliation":[{"name":"Pontifica Universidad Cat\u00f3lica de Chile and Center for Semantic Web Research, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2018,3,23]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.   S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2012.31"},{"key":"e_1_2_2_3_1","unstructured":"Renzo Angles Marcelo Arenas Pablo Barcel\u00f3 Aidan Hogan Juan L. Reutter and Domagoj Vrgoc. 2016. Foundations of modern graph query languages. Retrieved from http:\/\/arxiv.org\/abs\/1610.06264.  Renzo Angles Marcelo Arenas Pablo Barcel\u00f3 Aidan Hogan Juan L. Reutter and Domagoj Vrgoc. 2016. Foundations of modern graph query languages. Retrieved from http:\/\/arxiv.org\/abs\/1610.06264."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484440"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775249"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594555"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989312"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2633993"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the American mathematical Society (AMW\u201912)","author":"Barcel\u00f3 P.","unstructured":"P. Barcel\u00f3 , J. P\u00e9rez , and J. L. Reutter . 2012. Relative expressiveness of nested regular expressions . In Proceedings of the American mathematical Society (AMW\u201912) . 180--195. P. Barcel\u00f3, J. P\u00e9rez, and J. L. Reutter. 2012. Relative expressiveness of nested regular expressions. In Proceedings of the American mathematical Society (AMW\u201912). 180--195."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448520"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the Alberto Mendelzon International Workshop on Foundations of Data Management. 162","author":"Bienvenu Meghyn","year":"2015","unstructured":"Meghyn Bienvenu , Magdalena Ortiz , and Mantas Simkus . 2015 . Navigational queries based on frontier-guarded datalog: Preliminary results . In Proceedings of the Alberto Mendelzon International Workshop on Foundations of Data Management. 162 . Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus. 2015. Navigational queries based on frontier-guarded datalog: Preliminary results. In Proceedings of the Alberto Mendelzon International Workshop on Foundations of Data Management. 162."},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Christian Bizer and Andreas Schultz. 2009. The Berlin sparql benchmark. (2009).  Christian Bizer and Andreas Schultz. 2009. The Berlin sparql benchmark. (2009).","DOI":"10.4018\/jswis.2009040101"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201915)","author":"Bourhis Pierre","year":"2015","unstructured":"Pierre Bourhis , Markus Kr\u00f6tzsch , and Sebastian Rudolph . 2015 . Reasonable highly expressive query languages . In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201915) . 2826--2832. Pierre Bourhis, Markus Kr\u00f6tzsch, and Sebastian Rudolph. 2015. Reasonable highly expressive query languages. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201915). 2826--2832."},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR). 176--185","author":"Calvanese D.","unstructured":"D. Calvanese , G. De Giacomo , M. Lenzerini , and M. Y. Vardi . 2000. Containment of conjunctive regular path queries with inverse . In Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR). 176--185 . D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. 2000. Containment of conjunctive regular path queries with inverse. In Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR). 176--185."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1805"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959076"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298591"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38749"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402810"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2014.11.031"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938578"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28472-4_8"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/504077.504079"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962450"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484443"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.06.005"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"D. Harel D. Kozen and J. Tiuryn. 2000. Dynamic Logic. MIT Press.   D. Harel D. Kozen and J. Tiuryn. 2000. Dynamic Logic. MIT Press.","DOI":"10.7551\/mitpress\/2516.001.0001"},{"key":"e_1_2_2_32_1","unstructured":"S. Harris and A. Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/sparql11-query.  S. Harris and A. Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/sparql11-query."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46547-0_10"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989456"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_1"},{"key":"e_1_2_2_36_1","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"L. Libkin . 2004. Elements of Finite Model Theory . Springer . L. Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448513"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465226"},{"key":"e_1_2_2_40_1","volume-title":"I-III. J. Cybernet.","author":"Longyear Christopher","year":"1972","unstructured":"Christopher Longyear . 1972. Towards a triadic calculus , I-III. J. Cybernet. ( 1972 ), 50--65. Christopher Longyear. 1972. Towards a triadic calculus, I-III. J. Cybernet. (1972), 50--65."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213573"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114247"},{"key":"e_1_2_2_43_1","unstructured":"Neo4j. 2013. Neo4j The graph database. Retrieved from http:\/\/www.neo4j.org\/.  Neo4j. 2013. Neo4j The graph database. Retrieved from http:\/\/www.neo4j.org\/."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/2369451"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2010.01.002"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.2013.798992"},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of the 18th International Conference on Database Theory (ICDT\u201915)","volume":"31","author":"Reutter Juan L.","unstructured":"Juan L. Reutter , Miguel Romero , and Moshe Y. Vardi . 2015. Regular queries on graph databases . In Proceedings of the 18th International Conference on Database Theory (ICDT\u201915) , Vol. 31 . 177--194. Juan L. Reutter, Miguel Romero, and Moshe Y. Vardi. 2015. Regular queries on graph databases. In Proceedings of the 18th International Conference on Database Theory (ICDT\u201915), Vol. 31. 177--194."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_2"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31839-2_8"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465227"},{"key":"e_1_2_2_52_1","unstructured":"E. Schr\u00f6der. 1890. 1905: Vorlesungen \u00fcber die Algebra der Logik. 3 Bde. (1890).  E. Schr\u00f6der. 1890. 1905: Vorlesungen \u00fcber die Algebra der Logik. 3 Bde. (1890)."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242667"},{"key":"e_1_2_2_54_1","doi-asserted-by":"crossref","unstructured":"A. Tarski and S. Givant. 1987. A Formalization of Set Theory Without Variables. AMS.  A. Tarski and S. Givant. 1987. A Formalization of Set Theory Without Variables. AMS.","DOI":"10.1090\/coll\/041"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154385","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:26Z","timestamp":1750212686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154385"}},"subtitle":["A Navigational Algebra for RDF Triplestores"],"short-title":[],"issued":{"date-parts":[[2018,3,23]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3154385"],"URL":"https:\/\/doi.org\/10.1145\/3154385","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,23]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}