{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T11:25:32Z","timestamp":1772796332370,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>Over the past years, there has been a growing demand for ontological reasoning systems based on languages of the Datalog+\/- family, such as Vadalog, for their ability to effectively model a wide range of real-world problems with powerful features such as existential quantification. As the scale and complexity of data analysis tasks continue to grow, the ability to distribute the computational workload across multiple non-communicating processors has become vital for these systems to achieve scalable performance.<\/jats:p>\n          <jats:p>The joint presence of existential quantification and recursion poses new challenges, currently unsolved by existing distributed systems, which only concentrate on Datalog and are therefore unsuitable for ontological reasoning. When working across multiple processors, generating all the facts to answer a specific reasoning query, avoiding duplication, and guaranteeing termination are non-trivial tasks as infinitely many new symbols and facts can be generated by existential quantification and recursion.<\/jats:p>\n          <jats:p>In this paper, we address such challenges and introduce the first distributed framework in the Datalog+\/- space. We propose the condition of homomorphic decomposability, which identifies sets of Datalog+\/- rules with good distribution properties. We put homomorphic decomposability into action with a distributed reasoning algorithm for Warded Datalog+\/-, the core of Vadalog. We implement Vadalog Parallel, a distributed reasoner for Vadalog and provide experimental evaluation against state-of-the-art systems.<\/jats:p>","DOI":"10.14778\/3704965.3704970","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:22:57Z","timestamp":1739899377000},"page":"4614-4626","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Vadalog Parallel System: Distributed Reasoning with Datalog+\/-"],"prefix":"10.14778","volume":"17","author":[{"given":"Luigi","family":"Bellomarini","sequence":"first","affiliation":[{"name":"Banca d'Italia"}]},{"given":"Davide","family":"Benedetto","sequence":"additional","affiliation":[{"name":"Prometheux &amp; Universit\u00e0 Roma Tre"}]},{"given":"Matteo","family":"Brandetti","sequence":"additional","affiliation":[{"name":"TU Wien"}]},{"given":"Emanuel","family":"Sallinger","sequence":"additional","affiliation":[{"name":"TU Wien &amp; University of Oxford"}]},{"given":"Adriano","family":"Vlad","sequence":"additional","affiliation":[{"name":"Prometheux, TU Wien &amp; University of Oxford"}]}],"member":"320","published-online":{"date-parts":[[2025,2,18]]},"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."},{"key":"e_1_2_1_2_1","volume-title":"Ullman","author":"Afrati Foto N.","year":"2012","unstructured":"Foto N. Afrati and Jeffrey D. Ullman. 2012. Transitive Closure and Recursive Datalog Implemented on Clusters. In EDBT."},{"key":"e_1_2_1_3_1","unstructured":"Tommaso Alfonsi Luigi Bellomarini Anna Bernasconi and Stefano Ceri. 2022. Expressing Biological Problems with Logical Reasoning Languages. In RuleML+RR."},{"key":"e_1_2_1_4_1","volume-title":"4th International Workshop on the Resurgence of Datalog in Academia and Industry.","author":"Alviano Mario","year":"2022","unstructured":"Mario Alviano and Andreas Pieris (Eds.). 2022. 4th International Workshop on the Resurgence of Datalog in Academia and Industry."},{"key":"e_1_2_1_5_1","volume-title":"Todd J. Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L. Veldhuizen, and Geoffrey Washburn.","author":"Aref Molham","year":"2015","unstructured":"Molham Aref, Balder ten Cate, Todd J. Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L. Veldhuizen, and Geoffrey Washburn. 2015. Design and Implementation of the LogicBlox System. In SIGMOD."},{"key":"e_1_2_1_6_1","volume-title":"Miller","author":"Arocena Patricia C.","year":"2015","unstructured":"Patricia C. Arocena, Boris Glavic, Radu Ciucanu, and Ren\u00e9e J. Miller. 2015. The iBench Integration Metadata Generator. In PVLDB."},{"key":"e_1_2_1_7_1","volume-title":"International Joint Conference on Rules and Reasoning.","author":"Atzeni Paolo","year":"2022","unstructured":"Paolo Atzeni, Teodoro Baldazzi, Luigi Bellomarini, and Emanuel Sallinger. 2022. iWarded: A Versatile Generator to Benchmark Warded Datalog+\/-Reasoning. In International Joint Conference on Rules and Reasoning."},{"key":"e_1_2_1_8_1","unstructured":"Paolo Atzeni Luigi Bellomarini Michela Iezzi Emanuel Sallinger and Adriano Vlad. 2020. Augmenting Logic-based Knowledge Graphs: The Case of Company Graphs.. In KR4L@ ECAI."},{"key":"e_1_2_1_9_1","volume-title":"International Joint Conference on Rules and Reasoning.","author":"Baldazzi Teodoro","year":"2021","unstructured":"Teodoro Baldazzi, Luigi Bellomarini, Emanuel Sallinger, and Paolo Atzeni. 2021. Eliminating Harmful Joins in Warded Datalog+\/-. In International Joint Conference on Rules and Reasoning."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Pablo Barcel\u00f3 and Reinhard Pichler (Eds.). 2012. Datalog in Academia and Ind.","DOI":"10.1007\/978-3-642-32925-8"},{"key":"e_1_2_1_11_1","volume-title":"https:\/\/drive.google.com\/file\/d\/1ZSMFUrEMmDrFYHR7C_RiQJoZ29gn2G_L\/view?usp=sharing [Online","author":"Bellomarini Luigi","year":"2024","unstructured":"Luigi Bellomarini, Davide Benedetto, Matteo Brandetti, Emanuel Sallinger, and Adriano Vlad. 2024. Appendix. https:\/\/drive.google.com\/file\/d\/1ZSMFUrEMmDrFYHR7C_RiQJoZ29gn2G_L\/view?usp=sharing [Online; July-2024]."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Luigi Bellomarini Daniele Fakhoury Georg Gottlob and Emanuel Sallinger. 2019. Knowledge Graphs and Enterprise AI: The Promise of an Enabling Technology. In ICDE.","DOI":"10.1109\/ICDE.2019.00011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Luigi Bellomarini Emanuel Sallinger and Georg Gottlob. 2018. The Vadalog System: Datalog-based Reasoning for Knowledge Graphs. VLDB.","DOI":"10.14778\/3213880.3213888"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Michael Benedikt George Konstantinidis Giansalvatore Mecca Boris Motik Paolo Papotti Donatello Santoro and Efthymia Tsamoura. 2017. Benchmarking the chase. In SIGMOD.","DOI":"10.1145\/3034786.3034796"},{"key":"e_1_2_1_15_1","article-title":"Taming the Infinite Chase: Query Answering under Expressive Relational Constraints","author":"Cal\u00ec Andrea","year":"2013","unstructured":"Andrea Cal\u00ec, Georg Gottlob, and Michael Kifer. 2013. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. Journal of Artificial Intelligence Research.","journal-title":"Journal of Artificial Intelligence Research."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Andrea Cal\u00ec Georg Gottlob and Thomas Lukasiewicz. 2009. A general datalog-based framework for tractable query answering over ontologies. In PODS.","DOI":"10.1145\/1559795.1559809"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","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.","DOI":"10.1109\/LICS.2010.27"},{"key":"e_1_2_1_18_1","article-title":"Towards more expressive ontology languages: The query answering problem","author":"Cal\u00ec Andrea","year":"2012","unstructured":"Andrea Cal\u00ec, G. Gottlob, and A. Pieris. 2012. Towards more expressive ontology languages: The query answering problem. Journal of Artificial Intelligence.","journal-title":"Journal of Artificial Intelligence."},{"key":"e_1_2_1_19_1","unstructured":"Paris Carbone Asterios Katsifodimos Stephan Ewen Volker Markl Seif Haridi and Kostas Tzoumas. 2015. Apache flink: Stream and batch processing in a single engine. The Bulletin of the Technical Committee on Data Engineering."},{"key":"e_1_2_1_20_1","volume-title":"What you Always Wanted to Know About Datalog (And Never Dared to Ask)","author":"Ceri Stefano","unstructured":"Stefano Ceri, Georg Gottlob, and Letizia Tanca. 1989. What you Always Wanted to Know About Datalog (And Never Dared to Ask). In IEEE Transactions on Knowledge and Data Engineering."},{"key":"e_1_2_1_21_1","volume-title":"Kanellakis","author":"Cosmadakis Stavros S.","year":"1986","unstructured":"Stavros S. Cosmadakis and Paris C. Kanellakis. 1986. Parallel Evaluation of Recursive Rule Queries. In SIGMOD."},{"key":"e_1_2_1_22_1","unstructured":"DBpedia. 2023. DBpedia tables. http:\/\/wiki.dbpedia.org\/services-resources\/downloads\/dbpedia-tables. [Online; 27-Dec-2023]."},{"key":"e_1_2_1_23_1","unstructured":"Owen P Dwyer Teodoro Baldazzi Jim Davies Emanuel Sallinger and Adriano Vlad. 2023. Reasoning over Health Records with Vadalog: a Rule-based Approach to Patient Pathways. In RuleML+RR."},{"key":"e_1_2_1_24_1","volume-title":"Data exchange: semantics and query answering. Theoretical Computer Science","author":"Fagin Ronald","year":"2005","unstructured":"Ronald Fagin, Phokion G Kolaitis, Ren\u00e9e J Miller, and Lucian Popa. 2005. Data exchange: semantics and query answering. Theoretical Computer Science (2005)."},{"key":"e_1_2_1_25_1","volume-title":"Patel","author":"Fan Zhiwei","year":"2019","unstructured":"Zhiwei Fan, Jianqiao Zhu, Zuyu Zhang, Aws Albarghouthi, Paraschos Koutris, and Jignesh M. Patel. 2019. Scaling-up in-Memory Datalog Processing: Observations and Techniques. In VLDB."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Sumit Ganguly Avi Silberschatz and Shalom Tsur. 1990. A Framework for the Parallel Processing of Datalog Queries. In SIGMOD.","DOI":"10.1145\/93597.98724"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Floris Geerts Giansalvatore Mecca Paolo Papotti and Donatello Santoro. 2014. That's All Folks! LLUNATIC Goes Open Source. In PVLDB.","DOI":"10.14778\/2733004.2733031"},{"key":"e_1_2_1_28_1","unstructured":"Georg Gottlob and Andreas Pieris. 2015. Beyond SPARQL under OWL 2 QL Entailment Regime: Rules to the Rescue. In IJCAI."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Todd J Green Dan Olteanu and Geoffrey Washburn. 2015. Live programming in the LogicBlox system: A MetaLogiQL approach. In VLDB.","DOI":"10.14778\/2824032.2824075"},{"key":"e_1_2_1_30_1","article-title":"LUBM: A benchmark for OWL knowledge base systems","author":"Guo Yuanbo","year":"2005","unstructured":"Yuanbo Guo, Zhengxiang Pan, and Jeff Heflin. 2005. LUBM: A benchmark for OWL knowledge base systems. Journal of Web Semantics.","journal-title":"Journal of Web Semantics."},{"key":"e_1_2_1_31_1","volume-title":"7th Python in Science Conference.","author":"Hagberg Aric A.","unstructured":"Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. In 7th Python in Science Conference."},{"key":"e_1_2_1_32_1","volume-title":"Victor Teixeira de Almeida, et al","author":"Halperin Daniel","year":"2014","unstructured":"Daniel Halperin, Victor Teixeira de Almeida, et al. 2014. Demonstration of the Myria big data management service. In SIGMOD."},{"key":"e_1_2_1_33_1","unstructured":"Aidan Hogan et al. 2022. Knowledge Graphs. In ACM Computing Surveys."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Muhammad Imran G\u00e1bor E G\u00e9vay and Volker Markl. 2020. Distributed graph analytics with datalog queries in flink. In Software Foundations for Data Interoperability and Large Scale Graph Data Analytics.","DOI":"10.1007\/978-3-030-61133-0_6"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3303084.3309490"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Paris C. Kanellakis. 1986. Logic programming and parallel complexity. In ICDT.","DOI":"10.1007\/3-540-17187-8_27"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Bas Ketsman Aws Albarghouthi and Paraschos Koutris. 2020. Distribution Policies for Datalog. In Theory of Computing Systems.","DOI":"10.1007\/s00224-019-09959-3"},{"key":"e_1_2_1_38_1","unstructured":"Craig Larman et al. 1998. Applying UML and patterns. Prentice Hall Upper Saddle River."},{"key":"e_1_2_1_39_1","unstructured":"Nicola Leone Marco Manna Giorgio Terracina and Pierfrancesco Veltri. 2012. Efficiently Computable Datalog\u2203 Programs. In Principles of Knowledge Representation and Reasoning."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Nicola Leone Marco Manna Giorgio Terracina and Pierfrancesco Veltri. 2019. Fast Query Answering over Existential Rules. In ACM Transaction on Computational Logic.","DOI":"10.1145\/3308448"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"David Maier Alberto O. Mendelzon and Yehoshua Sagiv. 1979. Testing Implications of Data Dependencies. In ACM Transactions on Database Systems.","DOI":"10.1145\/582117.582119"},{"key":"e_1_2_1_42_1","volume-title":"AAAI Conference on Artificial Intelligence.","author":"Motik Boris","year":"2015","unstructured":"Boris Motik, Yavor Nenov, Robert Piro, and Ian Horrocks. 2015. Incremental update of datalog materialisation: the backward\/forward algorithm. In AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_43_1","volume-title":"AAAI Conference on Artificial Intelligence.","author":"Motik Boris","year":"2014","unstructured":"Boris Motik, Yavor Nenov, Robert Piro, Ian Horrocks, and Dan Olteanu. 2014. Parallel materialisation of datalog programs in centralised, main-memory RDF systems. In AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_44_1","volume-title":"Datalography: Scaling datalog graph analytics on graph processing systems","author":"Moustafa Walaa Eldin","year":"2016","unstructured":"Walaa Eldin Moustafa, Vicky Papavasileiou, Ken Yocum, and Alin Deutsch. 2016. Datalography: Scaling datalog graph analytics on graph processing systems. In IEEE."},{"key":"e_1_2_1_45_1","volume-title":"NVIDIA RAPIDS Accelerator for Apache Spark. https:\/\/resources.nvidia.com\/en-us-spark. [Online","year":"2024","unstructured":"Nvidia. 2023. NVIDIA RAPIDS Accelerator for Apache Spark. https:\/\/resources.nvidia.com\/en-us-spark. [Online; 25-May-2024]."},{"key":"e_1_2_1_46_1","volume-title":"Quickstep: A data platform based on the scaling-up approach. In VLDB.","author":"Patel Jignesh M","year":"2018","unstructured":"Jignesh M Patel, Harshad Deshmukh, Jianqiao Zhu, Navneet Potti, Zuyu Zhang, Marc Spehlmann, Hakan Memisoglu, and Saket Saurabh. 2018. Quickstep: A data platform based on the scaling-up approach. In VLDB."},{"key":"e_1_2_1_47_1","volume-title":"Patrick Xiaogang Peng, and Joshua Zhexue Huang","author":"Salloum Salman","year":"2016","unstructured":"Salman Salloum, Ruslan Dautov, Xiaojun Chen, Patrick Xiaogang Peng, and Joshua Zhexue Huang. 2016. Big data analytics on Apache Spark. International Journal of Data Science and Analytics."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892226"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"J\u00fcrgen Seib and Georg Lausen. 1991. Parallelizing Datalog Programs by Generalized Pivoting. In PODS.","DOI":"10.1145\/113413.113435"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Alexander Shkapsky Mohan Yang Matteo Interlandi Hsuan Chiu Tyson Condie and Carlo Zaniolo. 2016. Big Data Analytics with Datalog Queries on Spark. In SIGMOD.","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_2_1_51_1","volume-title":"International Conference on Data Engineering.","author":"Shkapsky Alexander","year":"2015","unstructured":"Alexander Shkapsky, Mohan Yang, and Carlo Zaniolo. 2015. Optimizing recursive queries with monotonic aggregates in DeALS. In International Conference on Data Engineering."},{"key":"e_1_2_1_52_1","volume-title":"Stanford Large Network Dataset Collection: Collaboration Network. https:\/\/snap.stanford.edu\/data\/#canets. [Online","author":"Stanford University","year":"2023","unstructured":"Stanford University. 2007. Stanford Large Network Dataset Collection: Collaboration Network. https:\/\/snap.stanford.edu\/data\/#canets. [Online; Dec-2023]."},{"key":"e_1_2_1_53_1","volume-title":"Stanford Large Network Dataset Collection: LiveJournal. https:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html. [Online","author":"Stanford University","year":"2023","unstructured":"Stanford University. 2008. Stanford Large Network Dataset Collection: LiveJournal. https:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html. [Online; Dec-2023]."},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Michael Stonebraker and Lawrence A Rowe. 1986. The design of Postgres. In ACM Sigmod Record.","DOI":"10.1145\/16856.16888"},{"key":"e_1_2_1_55_1","volume-title":"http:\/\/fastutil.di.unimi.it\/. [Online","year":"2023","unstructured":"Unimi. 2023. Fastutil. http:\/\/fastutil.di.unimi.it\/. [Online; 27-Dec-2023]."},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Victor Vianu. 2021. Datalog Unchained. In PODS.","DOI":"10.1145\/3452021.3458815"},{"key":"e_1_2_1_57_1","volume-title":"International Conference on Management of Data.","author":"Wang Yisu Remy","year":"2022","unstructured":"Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q Ngo, Reinhard Pichler, and Dan Suciu. 2022. Optimizing recursive queries with progam synthesis. In International Conference on Management of Data."},{"key":"e_1_2_1_58_1","volume-title":"Sharing the Load of Logic-Program Evaluation. In First International Symposium on Databases in Parallel and Distributed Systems.","author":"Wolfson O.","year":"2000","unstructured":"O. Wolfson. 2000. Sharing the Load of Logic-Program Evaluation. In First International Symposium on Databases in Parallel and Distributed Systems."},{"key":"e_1_2_1_59_1","volume-title":"International Conference on Management of Data.","author":"Wolfson Ouri","year":"1990","unstructured":"Ouri Wolfson and Aya Ozeri. 1990. A New Paradigm for Parallel and Distributed Rule-Processing. In International Conference on Management of Data."},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Ouri Wolfson and Avi Silberschatz. 1988. Distributed Processing of Logic Programs. In SIGMOD.","DOI":"10.1145\/971701.50242"},{"key":"e_1_2_1_61_1","unstructured":"Jiacheng Wu Jin Wang and Carlo Zaniolo. 2022. Optimizing Parallel Recursive Datalog Evaluation on Multicore Machines. In SIGMOD."},{"key":"e_1_2_1_62_1","volume-title":"International Conference on Big Data.","author":"Yang Mohan","year":"2014","unstructured":"Mohan Yang and Carlo Zaniolo. 2014. Main memory evaluation of recursive queries on multicore machines. In International Conference on Big Data."},{"key":"e_1_2_1_63_1","article-title":"Data Partition and Parallel Evaluation of Datalog Programs. In IEEE","author":"Zhang Weining","year":"1995","unstructured":"Weining Zhang, Ke Wang, and Siu-Cheung Chau. 1995. Data Partition and Parallel Evaluation of Datalog Programs. In IEEE Trans. Knowl. Data Eng.","journal-title":"Trans. Knowl. Data Eng."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3704965.3704970","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:37:11Z","timestamp":1739900231000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3704965.3704970"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":63,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.14778\/3704965.3704970"],"URL":"https:\/\/doi.org\/10.14778\/3704965.3704970","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"2025-02-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}