{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:06:16Z","timestamp":1777424776212,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p>\n            The\n            <jats:italic>chase<\/jats:italic>\n            is a well-established family of algorithms used to materialize Knowledge Bases (KBs) for tasks like query answering under dependencies or data cleaning. A general problem of chase algorithms is that they might perform redundant computations. To counter this problem, we introduce the notion of\n            <jats:italic>Trigger Graphs<\/jats:italic>\n            (TGs), which guide the execution of the rules avoiding redundant computations. We present the results of an extensive theoretical and empirical study that seeks to answer when and how TGs can be computed and what are the benefits of TGs when applied over real-world KBs. Our results include introducing algorithms that compute (minimal) TGs. We implemented our approach in a new engine, called GLog, and our experiments show that it can be significantly more efficient than the chase enabling us to materialize Knowledge Graphs with 17B facts in less than 40 min using a single machine with commodity hardware.\n          <\/jats:p>","DOI":"10.14778\/3447689.3447699","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:20:06Z","timestamp":1618244406000},"page":"943-956","source":"Crossref","is-referenced-by-count":9,"title":["Materializing knowledge bases via trigger graphs"],"prefix":"10.14778","volume":"14","author":[{"given":"Efthymia","family":"Tsamoura","sequence":"first","affiliation":[{"name":"Samsung AI Research, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Carral","sequence":"additional","affiliation":[{"name":"University of Montpellier, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrico","family":"Malizia","sequence":"additional","affiliation":[{"name":"University of Bologna, Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacopo","family":"Urbani","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Amsterdam, Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850586"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/280474"},{"key":"e_1_2_1_5_1","volume-title":"Graal: A Toolkit for Query Answering with Existential Rules","author":"Baget Jean-Fran\u00e7ois","year":"2015","unstructured":"Jean-Fran\u00e7ois Baget , Michel Lecl\u00e8re , Marie-Laure Mugnier , Swan Rocher , and Cl\u00e9ment Sipieter . 2015 . Graal: A Toolkit for Query Answering with Existential Rules . In RuleML. Springer , Berlin, Germany , 328--344. Jean-Fran\u00e7ois Baget, Michel Lecl\u00e8re, Marie-Laure Mugnier, Swan Rocher, and Cl\u00e9ment Sipieter. 2015. Graal: A Toolkit for Query Answering with Existential Rules. In RuleML. Springer, Berlin, Germany, 328--344."},{"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\/6012.15399"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90038-Q"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213888"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034796"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733028"},{"key":"e_1_2_1_12_1","volume-title":"Goal-Driven Query Answering for Existential Rules With Equality","author":"Benedikt Michael","unstructured":"Michael Benedikt , Boris Motik , and Efthymia Tsamoura . 2018. Goal-Driven Query Answering for Existential Rules With Equality . In AAAI. AAAI Press , New Orleans, LA, USA , 1761--1770. Michael Benedikt, Boris Motik, and Efthymia Tsamoura. 2018. Goal-Driven Query Answering for Existential Rules With Equality. In AAAI. AAAI Press, New Orleans, LA, USA, 1761--1770."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2009.07.002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2949689.2949698"},{"key":"e_1_2_1_15_1","volume-title":"W3C recommendation 25","author":"Brickley Dan","year":"2014","unstructured":"Dan Brickley , Ramanathan V Guha , and Brian McBride . 2014. RDF Schema 1.1. W3C recommendation 25 ( 2014 ), 2004--2014. Dan Brickley, Ramanathan V Guha, and Brian McBride. 2014. RDF Schema 1.1. W3C recommendation 25 (2014), 2004--2014."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.03.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-160217"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_19_1","volume-title":"Yedalog: Exploring Knowledge at Scale. In SNAPL. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik","author":"Chin Brian","year":"2015","unstructured":"Brian Chin , Daniel von Dincklage , Vuk Ercegovac , Peter Hawkins , Mark S. Miller , Franz Och , Chris Olston , and Fernando Pereira . 2015 . Yedalog: Exploring Knowledge at Scale. In SNAPL. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , Asilomar, CA, USA , 63--78. Brian Chin, Daniel von Dincklage, Vuk Ercegovac, Peter Hawkins, Mark S. Miller, Franz Och, Chris Olston, and Fernando Pereira. 2015. Yedalog: Exploring Knowledge at Scale. In SNAPL. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Asilomar, CA, USA, 63--78."},{"key":"e_1_2_1_20_1","volume-title":"Robin Haw, Marija Milacic, Joel Weiser, Guanming Wu, Michael Caudy, Phani Garapati, Marc Gillespie, Maulik R Kamdar, et al.","author":"Croft David","year":"2013","unstructured":"David Croft , Antonio Fabregat Mundo , Robin Haw, Marija Milacic, Joel Weiser, Guanming Wu, Michael Caudy, Phani Garapati, Marc Gillespie, Maulik R Kamdar, et al. 2013 . The Reactome pathway knowledge base. Nucleic acids research 42, D1 (2013), D472--D477. David Croft, Antonio Fabregat Mundo, Robin Haw, Marija Milacic, Joel Weiser, Guanming Wu, Michael Caudy, Phani Garapati, Marc Gillespie, Maulik R Kamdar, et al. 2013. The Reactome pathway knowledge base. Nucleic acids research 42, D1 (2013), D472--D477."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/579666"},{"key":"e_1_2_1_22_1","volume-title":"RuleML+RR","author":"Delivorias Stathis","unstructured":"Stathis Delivorias , Michel Lecl\u00e8re , Marie-Laure Mugnier , and Federico Ulliana . 2018. On the k-Boundedness for Existential Rules . In RuleML+RR . Springer , Luxembourg, Luxembourg , 48--64. Stathis Delivorias, Michel Lecl\u00e8re, Marie-Laure Mugnier, and Federico Ulliana. 2018. On the k-Boundedness for Existential Rules. In RuleML+RR. Springer, Luxembourg, Luxembourg, 48--64."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1085304.1085309"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733031"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2638546"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.06.005"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.06.001"},{"key":"e_1_2_1_29_1","volume-title":"Sabrina Kirrane, Sebastian Neumaier, Axel Polleres, Roberto Navigli, Axel-Cyrille Ngonga Ngomo, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann.","author":"Hogan Aidan","year":"2020","unstructured":"Aidan Hogan , Eva Blomqvist , Michael Cochez , Claudia d' Amato , Gerard de Melo , Claudio Gutierrez , Jos\u00e9 Emilio Labra Gayo , Sabrina Kirrane, Sebastian Neumaier, Axel Polleres, Roberto Navigli, Axel-Cyrille Ngonga Ngomo, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann. 2020 . Knowledge Graphs . arXiv:2003.02320 [cs] (2020). http:\/\/arxiv.org\/abs\/2003.02320 arXiv: 2003.02320. Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d'Amato, Gerard de Melo, Claudio Gutierrez, Jos\u00e9 Emilio Labra Gayo, Sabrina Kirrane, Sebastian Neumaier, Axel Polleres, Roberto Navigli, Axel-Cyrille Ngonga Ngomo, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann. 2020. Knowledge Graphs. arXiv:2003.02320 [cs] (2020). http:\/\/arxiv.org\/abs\/2003.02320 arXiv: 2003.02320."},{"key":"e_1_2_1_30_1","volume-title":"Modular Materialisation of Datalog Programs","author":"Hu Pan","unstructured":"Pan Hu , Boris Motik , and Ian Horrocks . 2019. Modular Materialisation of Datalog Programs . In AAAI. AAAI Press , Honolulu, HI, USA , 2859--2866. Pan Hu, Boris Motik, and Ian Horrocks. 2019. Modular Materialisation of Datalog Programs. In AAAI. AAAI Press, Honolulu, HI, USA, 2859--2866."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358147"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3058730"},{"key":"e_1_2_1_33_1","volume-title":"Virtual Conference, 364--381","author":"Kruit Benno","year":"2019","unstructured":"Benno Kruit , Peter A. Boncz , and Jacopo Urbani . 2019 . Extracting Novel Facts from Tables for Knowledge Graph Completion. In ISWC. Springer , Virtual Conference, 364--381 . Benno Kruit, Peter A. Boncz, and Jacopo Urbani. 2019. Extracting Novel Facts from Tables for Knowledge Graph Completion. In ISWC. Springer, Virtual Conference, 364--381."},{"key":"e_1_2_1_34_1","volume-title":"Virtual Conference, 349--365","author":"Kruit Benno","year":"2020","unstructured":"Benno Kruit , Hongyu He , and Jacopo Urbani . 2020 . Tab2Know: Building a Knowledge Base from Tables in Scientific Papers. In ISWC. Springer, Springer , Virtual Conference, 349--365 . Benno Kruit, Hongyu He, and Jacopo Urbani. 2020. Tab2Know: Building a Knowledge Base from Tables in Scientific Papers. In ISWC. Springer, Springer, Virtual Conference, 349--365."},{"key":"e_1_2_1_35_1","volume-title":"DL","volume":"1577","author":"Lecl\u00e8re Michel","year":"2016","unstructured":"Michel Lecl\u00e8re , Marie-Laure Mugnier , and Federico Ulliana . 2016 . On Bounded Positive Existential Rules . In DL , Vol. 1577 . CEUR-WS.org, Cape Town, South Africa. Michel Lecl\u00e8re, Marie-Laure Mugnier, and Federico Ulliana. 2016. On Bounded Positive Existential Rules. In DL, Vol. 1577. CEUR-WS.org, Cape Town, South Africa."},{"key":"e_1_2_1_36_1","volume-title":"Virtual Conference, 380--382","author":"Lee Jaehun","year":"2020","unstructured":"Jaehun Lee , Taeho Hwang , Jungho Park , Yunsu Lee , Boris Motik , and Ian Horrocks . 2020 . A Context-Aware Recommendation System for Mobile Devices. In ISWC. CEUR-WS.org , Virtual Conference, 380--382 . Jaehun Lee, Taeho Hwang, Jungho Park, Yunsu Lee, Boris Motik, and Ian Horrocks. 2020. A Context-Aware Recommendation System for Mobile Devices. In ISWC. CEUR-WS.org, Virtual Conference, 380--382."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11762256_12"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0333-y"},{"key":"e_1_2_1_40_1","volume-title":"Ian Horrocks, Zhe Wu, Achille Fokoue, Carsten Lutz, et al.","author":"Motik Boris","year":"2009","unstructured":"Boris Motik , Bernardo Cuenca Grau , Ian Horrocks, Zhe Wu, Achille Fokoue, Carsten Lutz, et al. 2009 . OWL 2 web ontology language profiles. W3C recommendation 27 (2009), 61. Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, Zhe Wu, Achille Fokoue, Carsten Lutz, et al. 2009. OWL 2 web ontology language profiles. W3C recommendation 27 (2009), 61."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2893873.2893896"},{"key":"e_1_2_1_42_1","volume-title":"IEEE International Conference on Big Data. IEEE Computer Society, Washington DC, DC, USA, 56--65","author":"Moustafa W. E.","unstructured":"W. E. Moustafa , V. Papavasileiou , K. Yocum , and A. Deutsch . 2016. Datalography: Scaling datalog graph analytics on graph processing systems . In IEEE International Conference on Big Data. IEEE Computer Society, Washington DC, DC, USA, 56--65 . W. E. Moustafa, V. Papavasileiou, K. Yocum, and A. Deutsch. 2016. Datalography: Scaling datalog graph analytics on graph processing systems. In IEEE International Conference on Big Data. IEEE Computer Society, Washington DC, DC, USA, 56--65."},{"key":"e_1_2_1_43_1","volume-title":"RDFox: A Highly-Scalable RDF Store","author":"Nenov Yavor","unstructured":"Yavor Nenov , Robert Piro , Boris Motik , Ian Horrocks , Zhe Wu , and Jay Banerjee . 2015. RDFox: A Highly-Scalable RDF Store . In ISWC. Springer , Bethlehem, PA, USA , 3--20. Yavor Nenov, Robert Piro, Boris Motik, Ian Horrocks, Zhe Wu, and Jay Banerjee. 2015. RDFox: A Highly-Scalable RDF Store. In ISWC. Springer, Bethlehem, PA, USA, 3--20."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331166"},{"key":"e_1_2_1_45_1","unstructured":"A. Onet. 2013. The Chase Procedure and its Applications in Data Exchange. In DEIS. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik Quebec City QUE Canada 1--37.  A. Onet. 2013. The Chase Procedure and its Applications in Data Exchange. In DEIS. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik Quebec City QUE Canada 1--37."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687603"},{"key":"e_1_2_1_47_1","volume-title":"CLAROS---Collaborating on Delivering the Future of the Past","author":"Rahtz Sebastian","unstructured":"Sebastian Rahtz , Alexander Dutton , Donna Kurtz , Graham Klyne , Andrew Zisserman , and Relja Arandjelovic . 2011. CLAROS---Collaborating on Delivering the Future of the Past . In DH. Stanford University Library , Stanford, CA, USA , 355--357. Sebastian Rahtz, Alexander Dutton, Donna Kurtz, Graham Klyne, Andrew Zisserman, and Relja Arandjelovic. 2011. CLAROS---Collaborating on Delivering the Future of the Past. In DH. Stanford University Library, Stanford, CA, USA, 355--357."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376673"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904121.2904123"},{"key":"e_1_2_1_50_1","unstructured":"RDFox's team. 2020. RDFox public release. https:\/\/github.com\/dbunibas\/chasebench\/tree\/master\/tools\/rdfox. Accessed: 2020-11-10.  RDFox's team. 2020. RDFox public release. https:\/\/github.com\/dbunibas\/chasebench\/tree\/master\/tools\/rdfox. Accessed: 2020-11-10."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989393"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447699"},{"key":"e_1_2_1_53_1","volume-title":"Beyond the Grounding Bottleneck: Datalog Techniques for Inference in Probabilistic Logic Programs","author":"Tsamoura Efthymia","unstructured":"Efthymia Tsamoura , V\u00edctor Guti\u00e9rrez-Basulto , and Angelika Kimmig . 2020. Beyond the Grounding Bottleneck: Datalog Techniques for Inference in Probabilistic Logic Programs . In AAAI. AAAI Press , New York, NY, USA , 10284--10291. Efthymia Tsamoura, V\u00edctor Guti\u00e9rrez-Basulto, and Angelika Kimmig. 2020. Beyond the Grounding Bottleneck: Datalog Techniques for Inference in Probabilistic Logic Programs. In AAAI. AAAI Press, New York, NY, USA, 10284--10291."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380246"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/3015812.3015850"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13486-9_15"},{"key":"e_1_2_1_57_1","volume-title":"Efficient Model Construction for Horn Logic with VLog","author":"Urbani Jacopo","unstructured":"Jacopo Urbani , Markus Kr\u00f6tzsch , Ceriel Jacobs , Irina Dragoste , and David Carral . 2018. Efficient Model Construction for Horn Logic with VLog . In IJCAR. Springer , Oxford, UK , 680--688. Jacopo Urbani, Markus Kr\u00f6tzsch, Ceriel Jacobs, Irina Dragoste, and David Carral. 2018. Efficient Model Construction for Horn Logic with VLog. In IJCAR. Springer, Oxford, UK, 680--688."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488525"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3447689.3447699","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:17:58Z","timestamp":1672226278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3447689.3447699"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":58,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.14778\/3447689.3447699"],"URL":"https:\/\/doi.org\/10.14778\/3447689.3447699","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2]]}}}