Existential Rules

From International Center for Computational Logic
Toggle side column

Existential Rules

Existential Rules are a knowledge representation formalism used in artificial intelligence and database theory. Their syntactic flexibility enables an easy integration of both semantic knowledge and databases. Syntactically close to Datalog rules, an important distinguishing feature is the possibility to describe individuals whose existence was not originally known, which is of great help for modeling purposes. All these features have motivated an intense research effort on how to query data under such rules. Questions typically tackled with this respect are the following: which query language achieve a good tradeoff between expressivity and complexity? What ensures the decidability of the query answering problem? What is the complexity of specific classes of rules? How to build efficient reasoners?

Journal Articles

Despoina Magka, Markus Krötzsch, Ian Horrocks
A rule-based ontological framework for the classification of molecules
J. Biomedical Semantics, 5:17, 2014
Details Download
Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
J. Artif. Intell. Res. (JAIR), 47:741-808, 2013
Details Download

Proceedings Articles

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph
Bounded Treewidth and the Infinite Core Chase – Complications and Workarounds toward Decidable Querying
In Floris Geerts, Hung Q. Ngo, Stavros Sintos, eds., Proceedings of the 42nd Symposium on Principles of Database Systems (PODS'23), 291-302, 2023. ACM
Details Download
Lukas Gerlach, David Carral
General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase (Extended Abstract)
In Oliver Kutz, Carsten Lutz, Ana Ozaki, eds., Proceedings of the 36th International Workshop on Description Logics (DL 2023) co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning and the 21st International Workshop on Non-Monotonic Reasoning (KR 2023 and NMR 2023), volume 3515 of CEUR Workshop Proceedings, October 2023. CEUR-WS.org
Details Download
Lukas Gerlach, David Carral
General Acyclicity and Cyclicity Notions for the Disjunctive Skolem Chase (Extended Technical Report)
In Brian Williams, Yiling Chen, Jennifer Neville, eds., Proceedings of the 37th AAAI Conference on Artificial Intelligence, volume 37 of Proceedings of the AAAI Conference on Artificial Intelligence, 6372-6379, June 2023. AAAI Press
Details Download
Lukas Gerlach, David Carral
Do Repeat Yourself: Understanding Sufficient Conditions for Restricted Chase Non-Termination (Technical Report)
In Pierre Marquis,Tran Cao Son,Gabriele Kern-Isberner, eds., Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023), volume 20 of Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, 301–310, September 2023. International Joint Conferences on Artificial Intelligence Organization
Details Download
Alex Ivliev, Stefan Ellmauthaler, Lukas Gerlach, Maximilian Marx, Matthias Meißner, Simon Meusel, Markus Krötzsch
Nemo: First Glimpse of a New Rule Engine
In Enrico Pontelli, Stefania Costantini, Carmine Dodaro, Sarah Gaggl, Roberta Calegari, Artur D'Avila Garcez, Francesco Fabiano, Alessandra Mileo, Alessandra Russo, Francesca Toni, eds., Proceedings 39th International Conference on Logic Programming (ICLP 2023), volume 385 of EPTCS, 333--335, September 2023
Details Download
Tim Lyon, Piotr Ostropolski-Nalewaja
Connecting Proof Theory and Knowledge Representation: Sequent Calculi and the Chase with Existential Rules
Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, 769-773, 2023. IJCAI Inc
Details Download
Ali Elhalawati, Markus Krötzsch, Stephan Mennicke
An Existential Rule Framework for Computing Why-Provenance On-Demand for Datalog
In Guido Governatori, Anni-Yasmin Turhan, eds., Proceddings of the 6th International Joint Conference on Rules and Reasoning (RuleML+RR 2022), volume 13752 of LNCS, 146--163, 2022. Springer
Details Download
Stefan Ellmauthaler, Markus Krötzsch, Stephan Mennicke
Answering Queries with Negation over Existential Rules
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), 5626-5633, 2022. AAAI Press
Details Download
Sarah Alice Gaggl, Philipp Hanisch, Markus Krötzsch
Simulating Sets in Answer Set Programming
In Luc De Raedt, eds., Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022), 2634--2640, 2022. ijcai.org
Details Download
Larry González, Alex Ivliev, Markus Krötzsch, Stephan Mennicke
Efficient Dependency Analysis for Rule-Based Ontologies
In Ulrike Sattler, Aidan Hogan, Maria Keet, Valentina Presutti, João Paulo A. Almeida, Hideaki Takeda, Pierre Monnin, Giuseppe Pirrò, Claudia d’Amato, eds., Proc. 21st International Semantic Web Conference (ISWC 2022), volume 13489 of LNCS, 267-283, October 2022. Springer
Details Download
Maximilian Marx, Markus Krötzsch
Tuple-Generating Dependencies Capture Complex Values (extended abstract)
In Mario Alviano, Andreas Pieris, eds., Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry, volume 3203 of CEUR Workshop Proceedings, 97--103, September 2022. CEUR-WS.org
Details Download
Maximilian Marx, Markus Krötzsch
Tuple-Generating Dependencies Capture Complex Values
In Dan Olteanu, Nils Vortmeier, eds., Proceedings of the 25th International Conference on Database Theory (ICDT 2022), volume 220 of LIPIcs, 13:1--13:20, March 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Details Download
Piotr Ostropolski-Nalewaja, Jerzy Marcinkowski, David Carral, Sebastian Rudolph
A Journey to the Frontiers of Query Rewritability
In Leonid Libkin, Pablo Barceló, eds., Proceedings of the 41st Symposium on Principles of Database Systems (PODS'22), 359-367, June 2022. ACM
Details Download
Jacopo Urbani, Markus Krötzsch, Thomas Eiter
Chasing Streams with Existential Rules
In Gabriele Kern-Isberner, Gerhard Lakemeyer, Thomas Meyer, eds., Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning (KR 2022), 2022
Details Download
Camille Bourgaux, David Carral, Markus Krötzsch, Sebastian Rudolph, Michaël Thomazo
Capturing Homomorphism-Closed Decidable Queries with Existential Rules
In Meghyn Bienvenu, Gerhard Lakemeyer, Esra Erdem, eds., Proc. 18th International Conference on Principles of Knowledge Representation and Reasoning (KR'21), 141--150, 2021
Details Download
Efthymia Tsamoura, David Carral, Enrico Malizia, Jacopo Urbani
Materializing Knowledge Bases via Trigger Graphs
Proceedings of the 47th International Conference on Very Large Databases, VLDB 2021, volume 14, 943-956, 2021
Details Download
Bartosz Bednarczyk, Robert Ferens, Piotr Ostropolski-Nalewaja
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
In Christian Bessiere, eds., Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), ijcai.org, 1719--1725, July 2020. International Joint Conferences on Artificial Intelligence
Details Download
David Carral, Markus Krötzsch
Rewriting the Description Logic ALCHIQ to Disjunctive Existential Rules
In Christian Bessiere, eds., Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020, 1777-1783, 2020. ijcai.org
Details Download
Markus Krötzsch
Computing Cores for Existential Rules with the Standard Chase and ASP
In Diego Calvanese, Esra Erdem, Michael Thielscher, eds., Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020), 603-613, 2020. IJCAI
Details Download
David Carral, Irina Dragoste, Markus Krötzsch, Christian Lewe
Chasing Sets: How to Use Existential Rules for Expressive Reasoning
Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI'19), August 2019. International Joint Conferences on Artificial Intelligence
Details Download
David Carral, Irina Dragoste, Larry González, Ceriel Jacobs, Markus Krötzsch, Jacopo Urbani
VLog: A Rule Engine for Knowledge Graphs
In Chiara Ghidini, Olaf Hartig, Maria Maleshkova, Vojtěch Svátek, Isabel F. Cruz, Aidan Hogan, Jie Song, Maxime Lefrançois, Fabien Gandon, eds., Proceedings of the 18th International Semantic Web Conference (ISWC'19) Part II, volume 11779 of LNCS, 2019. Springer
Details Download
Markus Krötzsch
Too Much Information: Can AI Cope With Modern Knowledge Graphs?
In Diana Cristea, Florence Le Ber, Baris Sertkaya, eds., Proceedings of the 15th International Conference on Formal Concept Analysis (ICFCA 2019), volume 11511 of LNCS, 17--31, 2019. Springer
Details Download
Markus Krötzsch, Maximilian Marx, Sebastian Rudolph
The Power of the Terminating Chase
In Pablo Barceló, Marco Calautti, eds., Proceedings of the 22nd International Conference on Database Theory (ICDT 2019), volume 127 of LIPIcs, 3:1--3:17, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Details Download
Jacopo Urbani, Markus Krötzsch, Ceriel Jacobs, Irina Dragoste, David Carral
Efficient Model Construction for Horn Logic with VLog
In Didier Galmiche, Stephan Schulz, Roberto Sebastiani, eds., Proceedings of the 8th International Joint Conference on Automated Reasoning (IJCAR 2018), volume 10900 of LNCS, 680--688, 2018. Springer
Details Download
Jacopo Urbani, Markus Krötzsch, Ceriel Jacobs, Irina Dragoste, David Carral
Efficient Model Construction for Horn Logic with VLog: Extended Abstract
In Magdalena Ortiz, Thomas Schneider, eds., Proceedings of the 31st International Workshop on Description Logics (DL 2018), volume 2211 of CEUR Workshop Proceedings, October 2018. CEUR-WS.org
Details Download
David Carral, Irina Dragoste, Markus Krötzsch
Tractable Query Answering for Expressive Ontologies and Existential Rules
In Claudia d'Amato, Miriam Fernández, Valentina A. M. Tamma, Freddy Lécué, Philippe Cudré-Mauroux, Juan F. Sequeda, Christoph Lange, Jeff Heflin, eds., Proceedings of the 16th International Semantic Web Conference (ISWC'17), volume 10587 of LNCS, 2017. Springer
Details Download
David Carral, Irina Dragoste, Markus Krötzsch
Restricted chase (non)termination for existential rules with disjunctions
In Carles Sierra, eds., Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI'17), 922-928, 2017. International Joint Conferences on Artificial Intelligence
Details Download
David Carral, Irina Dragoste, Markus Krötzsch
Answering Conjunctive Queries for Expressive DLs with the Restricted Chase: Extended Abstract
In Alessandro Artale, Birte Glimm, Roman Kontchakov, eds., Proceedings of the 30st International Workshop on Description Logics (DL 2017), volume 1879 of CEUR Workshop Proceedings, July 2017. CEUR-WS.org
Details Download
Markus Krötzsch
Ontologies for Knowledge Graphs?
In Alessandro Artale, Birte Glimm, Roman Kontchakov, eds., Proceedings of the 30th International Workshop on Description Logics (DL 2017), volume 1879 of CEUR Workshop Proceedings, July 2017. CEUR-WS.org
Details Download
David Carral, Cristina Feier, Pascal Hitzler
A Practical Acyclicity Notion for Query Answering Over Horn-SRIQ Ontologies
In Paul Groth, Elena Simperl, Alasdair Gray, Marta Sabou, Markus Krötzsch, Freddy Lecue, Fabian Flock, Yolanda Gil, eds., The Semantic Web - ISWC 2016 - 15th International Semantic Web Conference, Kobe, Japan. Proceedings, Part I, volume 9981 of LNCS, 70-85, October 2016. Springer
Details Download
Markus Krötzsch, Veronika Thost
Ontologies for Knowledge Graphs: Breaking the Rules
In Yolanda Gil, Elena Simperl, Paul Groth, Freddy Lecue, Markus Krötzsch, Alasdair Gray, Marta Sabou, Fabian Flöck, Hideaki Takeda, eds., Proceedings of the 15th International Semantic Web Conference (ISWC 2016), volume 9981 of LNCS, 376-392, 2016. Springer
Details Download
Sebastian Rudolph, Michaël Thomazo
Characterization of the Expressivity of Existential Rule Queries
In Qiang Yang, Michael Wooldridge, eds., Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15), 3193-3199, 2015. AAAI Press
Details Download
Georg Gottlob, Sebastian Rudolph, Mantas Simkus
Expressiveness of guarded existential rule languages
In Richard Hull, Martin Grohe, eds., Proc. 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'14), 27-38, June 2014. ACM
Details Download
Marie-Laure Mugnier, Michaël Thomazo
An Introduction to Ontology-Based Query Answering with Existential Rules
Reasoning Web Summer School, 245-278, 2014. Springer
Details Download
Sebastian Rudolph
The Two Views on Ontological Query Answering
In Georg Gottlob, Jorge Pérez, eds., Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management, volume 1189 of CEUR Workshop Proceedings, June 2014. CEUR
Details Download
Michaël Thomazo, Sebastian Rudolph
Mixing Materialization and Query Rewriting for Existential Rules
Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14), 897-902, 2014. IOS Press
Details Download
Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo
Sound, Complete, and Minimal Query Rewriting for Existential Rules
Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), 3017-3025, 2013
Details
Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo
On the Exploration of the Query Rewriting Space with Existential Rules
Proceedings of the 7th International Conference on Web Reasoning and Rule Systems (RR 2013), 123-137, 2013. Springer
Details Download
Despoina Magka, Markus Krötzsch, Ian Horrocks
Nonmonotonic Existential Rules for Non-Tree-Shaped Ontological Modelling
Proc. 26th International Workshop on Description Logics (DL'13), 390-402, July 2013. CEUR Workshop Proceedings
Details Download
Despoina Magka, Markus Krötzsch, Ian Horrocks
Computing Stable Models for Nonmonotonic Existential Rules
Proc. 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), 1031-1038, August 2013. AAAI Press
Details Download
Michaël Thomazo
Compact Rewritings for Existential Rules
Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), 1125-1131, 2013
Details
Michaël Thomazo
Ontology Based Query Answering with Existential Rules
Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), 3245-3246, 2013
Details Download
Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang
Acyclicity Conditions and their Application to Query Answering in Description Logics
Proc. 13th International Conference on Principles of Knowledge Representation and Reasoning (KR'12), 243–253, June 2012. AAAI Press
Details Download
Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo
A Sound and Complete Backward Chaining Algorithm for Existential Rules
Proceedings of the 6th International Conference on Web Reasoning and Rule Systems (RR 2012), 122-138, 2012. Springer
Details Download
Michaël Thomazo, Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph
A Generic Querying Algorithm for Greedy Sets of Existential Rules
Proceedings of the 13th International Conference on the Principles of Knowledge Representation and Reasoning (KR'12), 2012. AAAI
Details Download
Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, Michaël Thomazo
Walking the Complexity Lines for Generalized Guarded Existential Rules
In Toby Walsh, eds., Proceedings of the 22nd International Joint Conference on Artificial Intelligence, 712-717, July 2011. IJCAI/AAAI
Details Download
Jean-François Baget, Marie-Laure Mugnier, Michaël Thomazo
Towards Farsighted Dependencies for Existential Rules
Proceedings of the 5th International Conference on Web Reasoning and Rule Systems (RR 2011), 30-45, 2011. Springer
Details Download
Markus Krötzsch, Sebastian Rudolph
Extending Decidable Existential Rules by Joining Acyclicity and Guardedness
In Toby Walsh, eds., Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), 963-968, July 2011. IJCAI/AAAI
Details Download

Edited Proceedings

Markus Krötzsch, Daria Stepanova
Explainable Artificial Intelligence. Proceedings of the 15th Reasoning Web Summer School
Volume 11810 of LNCS, 2019. Springer
Details
Thomas Eiter, Birte Glimm, Yevgeny Kazakov, Markus Krötzsch
Informal Proceedings of the 26th International Workshop on Description Logics, Ulm, Germany, July 23 - 26, 201
Volume 1014 of CEUR Workshop Proceedings, 2013. CEUR-WS.org
Details
Markus Krötzsch, Umberto Straccia
Web Reasoning and Rule Systems - 6th International Conference, RR 2012, Vienna, Austria, September 10-12, 2012. Proceeding
Volume 7497 of Lecture Notes in Computer Science, 2012. Springer
Details

Doctoral Theses

Markus Krötzsch
Description Logic Rules
Phd thesis, KIT, 2010/09/11
Details Download

Technical Reports

Sebastian Rudolph, Michaël Thomazo
Characterization of the Expressivity of Existential Rule Queries
Technical Report, TU Dresden, volume IJCAI-15-RT-RR, May 2015
Details Download
Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo
Sound, Complete and Minimal UCQ-Rewriting for Existential Rules
Technical Report, University of Montpellier 2, 2013
Details Download
Markus Krötzsch, Sebastian Rudolph
Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules
Technical Report, Institut AIFB, KIT, volume 3011, January 2011
Details Download

Talks and Miscellaneous

Markus Krötzsch
Data, Ontologies, Rules, and the Return of the Blank Node
Keynote at the 21st International Semantic Web Conference, 2022
Details Download
Lukas Gerlach
Chase-Based Computation of Cores for Existential Rules
Diploma Thesis, TU Dresden, September 2021
Details Download
Markus Krötzsch
Working with Knowledge Graphs
Course at EDBT Summer School 2019, Lyon, France, 2019
Details Download
Markus Krötzsch
Recent Advances in Reasoning with Existential Rules
Presentation at the 2018 Workshop of the European Master in Computational Logic (EMCL), 2018
Details Download
Cfaed-logo.png

cfaed
CENTER FOR ADVANCING ELECTRONICS DRESDEN

CPEC-logo.png

CPEC
Center for Perspicuous Computing

DeciGUT-logo-final.png

DeciGUT
A Grand Unified Theory of Decidability in Logic-Based Knowledge Representation

InnoSale Logo original.png

InnoSale
Innovating Sales and Planning of Complex Industrial Products Exploiting Artificial Intelligence

Nemo
A fast, scalable, and reliable rule engine

SECAI-SQUARE-SHORT.pdf

SECAI
School of Embedded Composite Artificial Intelligence

Scads-logo.png

ScaDS.AI
Center for Scalable Data Analytics and Artificial Intelligence