{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:09Z","timestamp":1750220469358,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Royal Society Research Professorship","award":["RP\/R1\/201074"],"award-info":[{"award-number":["RP\/R1\/201074"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S003800\/1"],"award-info":[{"award-number":["EP\/S003800\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["VRG18-013"],"award-info":[{"award-number":["VRG18-013"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"name":"EPSRC Programme","award":["EP\/M025268\/1"],"award-info":[{"award-number":["EP\/M025268\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>\n            Vadalog is a system for performing complex reasoning tasks such as those required in advanced knowledge graphs. The logical core of the underlying Vadalog language is the warded fragment of tuple-generating dependencies (TGDs). This formalism ensures tractable reasoning in data complexity, while a recent analysis focusing on a practical implementation led to the reasoning algorithm around which the Vadalog system is built. A fundamental question that has emerged in the context of Vadalog is whether we can limit the recursion allowed by wardedness in order to obtain a formalism that provides a convenient syntax for expressing useful recursive statements, and at the same time achieves space-efficiency. After analyzing several real-life examples of warded sets of TGDs provided by our industrial partners, as well as recent benchmarks, we observed that recursion is often used in a restricted way: the body of a TGD contains at most one atom whose predicate is mutually recursive with a predicate in the head. We show that this type of recursion, known as\n            <jats:italic>piece-wise linear<\/jats:italic>\n            in the Datalog literature, is the answer to our main question. We further show that piece-wise linear recursion alone, without the wardedness condition, is not enough as it leads to undecidability. We also study the relative expressiveness of the query languages based on (piece-wise linear) warded sets of TGDs. Finally, we give preliminary experimental evidence for the practical effect of piece-wise linearity on Vadalog.\n          <\/jats:p>","DOI":"10.1145\/3488720","type":"journal-article","created":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T12:27:52Z","timestamp":1649248072000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Space-Efficient Core of Vadalog"],"prefix":"10.1145","volume":"47","author":[{"given":"Gerald","family":"Berger","sequence":"first","affiliation":[{"name":"TU Wien, Vienna, Austria"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK &amp; TU Wien, Vienna, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4779-3469","authenticated-orcid":false,"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK &amp; University of Cyprus, Nicosia, Cyprus"}]},{"given":"Emanuel","family":"Sallinger","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK &amp; TU Wien, Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2022,4,6]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00730-2"},{"key":"e_1_3_3_3_2","first-page":"14","volume-title":"PODS","author":"Arenas Marcelo","year":"2014","unstructured":"Marcelo Arenas, Georg Gottlob, and Andreas Pieris. 2014. Expressive languages for querying the semantic web. In PODS. 14\u201326."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3238304"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850586"},{"key":"e_1_3_3_6_2","first-page":"712","volume-title":"IJCAI","author":"Baget Jean-Fran\u00e7ois","year":"2011","unstructured":"Jean-Fran\u00e7ois Baget, Marie-Laure Mugnier, Sebastian Rudolph, and Micha\u00ebl Thomazo. 2011. Walking the complexity lines for generalized guarded existential rules. In IJCAI. 712\u2013717."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.002"},{"key":"e_1_3_3_8_2","first-page":"73","volume-title":"ICALP","author":"Beeri Catriel","year":"1981","unstructured":"Catriel Beeri and Moshe Y. Vardi. 1981. The implication problem for data dependencies. In ICALP. 73\u201385."},{"key":"e_1_3_3_9_2","first-page":"2","volume-title":"IJCAI","author":"Bellomarini Luigi","year":"2017","unstructured":"Luigi Bellomarini, Georg Gottlob, Andreas Pieris, and Emanuel Sallinger. 2017. Swift logic for big data and knowledge graphs. In IJCAI. 2\u201310."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213888"},{"key":"e_1_3_3_11_2","first-page":"37","volume-title":"PODS","author":"Benedikt Michael","year":"2017","unstructured":"Michael Benedikt, George Konstantinidis, Giansalvatore Mecca, Boris Motik, Paolo Papotti, Donatello Santoro, and Efthymia Tsamoura. 2017. Benchmarking the chase. In PODS. 37\u201352."},{"key":"e_1_3_3_12_2","first-page":"270","volume-title":"PODS","author":"Berger Gerald","year":"2019","unstructured":"Gerald Berger, Georg Gottlob, Andreas Pieris, and Emanuel Sallinger. 2019. The space-efficient core of Vadalog. In PODS. 270\u2013284."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2661643"},{"key":"e_1_3_3_14_2","first-page":"331","volume-title":"Complexity, Logic, and Recursion Theory","author":"Boas Peter Van Emde","year":"1997","unstructured":"Peter Van Emde Boas. 1997. The convenience of tilings. In Complexity, Logic, and Recursion Theory. 331\u2013363."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2591248.2591252"},{"key":"e_1_3_3_16_2","first-page":"228","volume-title":"LICS","author":"Cal\u00ec Andrea","year":"2010","unstructured":"Andrea Cal\u00ec, Georg Gottlob, Thomas Lukasiewicz, Bruno Marnette, and Andreas Pieris. 2010. Datalog+\/-: A family of logical knowledge representation and query languages for new applications. In LICS. 228\u2013242."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2638546"},{"key":"e_1_3_3_19_2","first-page":"2999","volume-title":"IJCAI","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 IJCAI. 2999\u20133007."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.3233\/SW-140153"},{"key":"e_1_3_3_22_2","first-page":"552","volume-title":"ISWC","author":"Kontchakov Roman","year":"2014","unstructured":"Roman Kontchakov, Martin Rezk, Mariano Rodriguez-Muro, Guohui Xiao, and Michael Zakharyaschev. 2014. Answering SPARQL queries over databases under OWL 2 QL entailment regime. In ISWC. 552\u2013567."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_3_3_24_2","first-page":"267","volume-title":"PODS","author":"Naughton Jeffrey F.","year":"1986","unstructured":"Jeffrey F. Naughton. 1986. Data independent recursion in deductive databases. In PODS. 267\u2013279."},{"key":"e_1_3_3_25_2","first-page":"227","volume-title":"PODS","author":"Naughton Jeffrey F.","year":"1987","unstructured":"Jeffrey F. Naughton and Yehoshua Sagiv. 1987. A decidable class of bounded recursions. In PODS. 227\u2013236."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488720","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:28Z","timestamp":1750193308000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,31]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3488720"],"URL":"https:\/\/doi.org\/10.1145\/3488720","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2022,3,31]]},"assertion":[{"value":"2020-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}