Decidable Fragments of Horn First-Order Logic
Seminar Organised by the Action Transverse Logique at the LIRMM

In this seminar, we present recent results about Existential Rules, an undecidable Horn fragment of first-order logic that is widely used in ontological modelling. Namely, we discuss the main approaches devised to retrieve decidability as well as efficient implementations to solve complex reasoning tasks.

1. When and Where


2. Program

  • 9:30 to 10:15: "Introduction to Existential Rules" by David Carral
    • Abstract: David Carral will first introduce the syntax and semantics of existential rules. Then, he will show that reasoning over this expressive fragment of first-order logic is undecidable. Finally, he will present two of the main approaches that are used to retrieve decidability. The first one is based on termination of the chase, a bottom-up materialisation procedure that aims to compute universal models. The second one is based on resolution, a backward-chaining algorithm that can be used to rewrite queries so as to incorporate the semantic information in an existential rule theory.
    • Bio: David Carral is a local Inria researcher at the GraphIK team at the University of Montpellier. Broadly speaking, he is interested in the study of logical languages (mostly first-order logic, existential rules, and Description Logics) and their theoretical/computational properties.
    • Dates in Montpellier: Local researcher
  • 10:15 to 10:45: "Reasoning with Guarded Existential Rules" by Michaël Thomazo
    • Abstract: TBA
    • Bio: Michaël Thomazo is an Inria researcher at the Valda research team. He is broadly interested in knowledge representation and its interactions with database theory and database systems, often seen through a logical and/or graph based formalism. He started in this field by getting a Ph.D from the University of Montpellier, supervised by J.-F. Baget and M.-L. Mugnier in the Inria team GraphIK. Then, he joined the group of Sebastian Rudolph at TU Dresden and partially funded through an Alexander von Humboldt fellowship. Afterwards, he was recruited in the Oak/Cedar team of Inria Saclay, before joining Valda in April 2018.
    • Dates in Montpellier: From the 14/11 (Sunday) to the 18/11 (Thursday)
  • 10:45 to 11:15: Coffee Break
  • 11:15 to 12:00: "Compressing Rule-based Reasoning" by Jacopo Urbani
    • Abstract: Rule-based reasoning on large Knowledge Bases (KBs) is a problem that received significant attention from the AI research community. One of the key reasoning tasks is materialization, i.e., the exhaustive derivation of all facts that can be implied by a set of rules. Many approaches have been proposed to improve the performance of materialization. Most of them focus on parallelism as a means to decrease the runtime. This talk will focus instead on a relatively unexplored way to improve the performance, that is via compression. First, I will present VLog, a leading rule-based reasoner that exploits a column-based representation to compress the derivations. This allows VLog to reason more efficiently, both in terms of runtime and memory consumption. Then, I will present more sophisticated forms of compression which further improve the performance of reasoning.
    • Bio: Jacopo Urbani is an professor in Computer Science at the Vrije Universiteit Amsterdam (VUA). He is also a guest researcher at the Centrum Wiskunde & Informatica in Amsterdam. He wrote a PhD thesis on distributed reasoning algorithms for very large Knowledge Graphs. The thesis was nominated by the Royal Netherlands Academy of Arts and Sciences as one of the best PhD theses in Computer Science in the country. After spending part of his postdoc in USA (Stanford) and Germany (MPII), he joined the faculty of the VUA. He recently started a research unit on knowledge extraction and inference from large Web corpora which has developed tools that are considered among the state-of-the-art in the respective fields.
    • Dates in Montpellier: From the 16/11 to the 18/11
  • 12:00 to 13:30: Lunch Break (to register for lunch please use the online form under the "5. Registration" section)
  • 13:30 to 14:15: "Capturing Homomorphism-Closed Decidable Queries with Existential Rules" by Sebastian Rudolph
    • Abstract: Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms. In this paper, we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalisation argument that this is unavoidable.
    • Bio: Sebastian Rudolph is full professor for computational logic and head of the AI Institute at TU Dresden. His scientific interests revolve around artificial intelligence, with a particular focus on logical formalisms and methods for knowledge representation and reasoning, ranging from theoretical foundations (such as semantic and computational properties) to practical deployment (including ontological modeling and interactive knowledge acquisition). In the course of an ongoing ERC Consolidator Grant, his team currently investigates general principles of decidability in logic-based knowledge representation.
    • Dates in Montpellier: From the 14/11 (Sunday) to the 29/11 (Monday)
  • 14:15 to 15:00: "Answering Counting Queries over Lightweight Ontologies" by Michaël Thomazo
    • Abstract: Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unexplored. I'll introduce a general form of counting query, relate it to previous proposals, and present come complexity results and associated techniques to answer such counting queries. This is joint work with Meghyn Bienvenu and Quentin Manière.
    • Bio: Michaël Thomazo is an Inria researcher at the Valda research team. He is broadly interested in knowledge representation and its interactions with database theory and database systems, often seen through a logical and/or graph based formalism. He started in this field by getting a Ph.D from the University of Montpellier, supervised by J.-F. Baget and M.-L. Mugnier in the Inria team GraphIK. Then, he joined the group of Sebastian Rudolph at TU Dresden and partially funded through an Alexander von Humboldt fellowship. Afterwards, he was recruited in the Oak/Cedar team of Inria Saclay, before joining Valda in April 2018.
    • Dates in Montpellier: From the 14/11 (Sunday) to the 18/11 (Thursday)
  • 15:00 to 15:30: Coffee Break
  • 15:30 to 16:15: "Derivation Graphs, Greediness, and Bounded-treewidth in the Context of Existential Rules" by Timothy Stephen Lyon
    • Abstract: This talk will discuss decidable classes of existential rules subsumed by the class of bounded-treewidth sets and interrelationships thereof. We will look at classes of existential rules defined on the basis of "derivation graphs," that is, directed acyclic graphs which record how facts are derived from a given knowledge base. Such objects have been used to identify decidable sets of existential rules given that such graphs can be reduced to a forest via certain reduction operations. Moreover, we will look at classes of existential rules that rely on the concept of a "greedy derivation," i.e. derivations where if a rule is applied, then all frontier variables not mapped to terms from the given data set must be mapped to terms provided by a single, previous rule application. We will conclude the talk by mapping out which classes subsume or identify with one another.
    • Bio: Tim Lyon is a postdoctoral researcher in the Computational Logic group at Technische Universität Dresden. He currently works within the ERC project DeciGUT, and his research interests concern the construction and application of proof systems for fragments of first-order logic, non-classical logics, and modal logics. Prior to joining TU Dresden, he was a PhD student at Technische Universität Wien, where he worked on the TICAMORE (Translating and Discovering Calculi for Modal and Related Logics) project under the supervision of Prof. Agata Ciabattoni.
    • Dates in Montpellier: From the 14/11 (Monday) to the 19/11 (Friday)
  • 16:15 to 17:00: "Existential rules: Intersecting FO-Rewritability and Core Termination" by Piotr Ostropolski-Nalewaja
    • Abstract: At the beginning of the talk, we will introduce two essential classes of existential rules that admit decidable query entailment. First - known as FUS or BDD - achieves this by ensuring the existence of the first-order query rewritings. Second - known as FES or the class of rulesets that are Core Terminating - achieves decidability of query entailment by ensuring the existence of finite universal models. Later, we will explore the intersection of those classes in the context of the FUS/FES conjecture. This talk will be based on the joint work with Jerzy Marcinkowski, David Carral, and Sebastian Rudolph.
    • Bio: Piotr Ostropolski-Nalewaja recently started working as a postdoc researcher in the group of Prof. Sebastian Rudolph on the ERC project DeciGUT. Before that Piotr was a PhD student at the University of Wrocław, where he was (mostly) focusing on existential rules.
    • Dates in Montpellier: From the 14/11 (Sunday) to the 19/11 (Friday)

3. Is this seminar for you?

The morning sessions of the program are intended to provide you with a general introduction to Existential Rules. If you are familiar with the syntax and semantics of first-order logic, you should be able to fully understand these presentations. In the afternoon, the talks will be a bit more specific/technical. Hence, if you would like to attend the event (and you are not so familiar with the topic at hand), we strongly suggest that you attend the morning sessions. After that, you can probably decide by yourself if you also want to stay for the rest of the day.

4. Why should you attend this event?

Wondering if you should come? Our impressive list of international speakers may convince you to do so: Besides, in the afternoon, Sebastian Rudolph will present the paper "Capturing Homomorphism-Closed Decidable Queries with Existential Rules", which has been awarded the 2021 Ray Reiter Best Paper Prize. That is, the best paper award at the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR 2021).

5. Registration

We need to keep attendance because of COVID restrictions! Therefore, we ask all participants to register for the event using this online form. Also, please indicate in the form if you will be joining us for lunch.

6. Contact

David Carral (david.carral@inria.fr) and Mégane Miquel (megane.miquel@lirmm.fr)

7. Slides

Click here to download the slides used during the presentations.

8. Acknowledgements

This seminar is organised within the "Action Transverse Logique", which is funded by the LIRMM. Additional funds have been provided by the GraphIK team and the Chair of Computational Logic at TU Dresden.