Practical Uses of Existential Rules in Knowledge Representation

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Practical Uses of Existential Rules in Knowledge Representation

This webpage contains all of the materials and relevant information for our tutorial at the 24th European Conference on Artificial Intelligence (ECAI 2020).

Reasoning with existential rules is a well-established research area in KR that has increasingly become more relevant in recent years [1,2,3,4,8,11,12]. In this tutorial, we thoroughly discuss the terminating fragment of existential rules. That is, the fragment of this language for which the chase algorithm is guaranteed to terminate. We propose the use of terminating rule languages to encode complex reasoning algorithms in a declarative way [7]. This approach, which follows the classical slogan "Algorithm = Logic + Control", promises to turn high-level specifications of logical calculi as systems of inference rules into declarative rule-based models that can be executed on state-of-the-art rule engines. Finally, we present VLog [5,13], an efficient implementation of the chase and show, in a hands-on session, how to use this tool to implement simple reasoning calculi.

The tutorial consists of two different parts where we (A) formally introduce the terminating fragment of existential rules and (B) show how to use VLog to implement reasoning algorithms in a hands-on session.

A. Introduction to Existential Rules.

In this part of the tutorial, which will take around two hours, we introduce existential rules and some prominent decidable fragments of this language. Namely, we present the following topics.

  • We start with a general introduction of the syntax and semantics of the existential rule fragment.
  • We show that reasoning with existential rules is undecidable.
  • We present different variants of the chase algorithm, which is a sound and complete, albeit non-terminating, reasoning procedure for existential rules.
  • We show that we cannot decide chase termination.
  • We present some acyclicity notions; that is, some sufficient conditions that guarantee termination of the chase. For instance, we present model-faithful acyclicity (MFA) [8] and restricted model-faithful acyclicity (RMFA) [6].
  • We discuss the complexity of reasoning with acyclicity notions. That is, we discuss the complexity of checking whether a rule set is (R)MFA and the complexity of reasoning with (R)MFA rule sets.
  • We discuss the complexity of reasoning with Datalog rule sets; that is, existential rule sets that do not contain any existential quantifiers.
  • We present and study the complexity of Datalog(S), which is an extension of Datalog that allows for the use of set constructors.
  • We discuss some results that show how Datalog(S) rule sets can be translated into existential rule sets with a terminating chase that preserve fact-entailment.


B. The Rule-Engine VLog.

In this part of the tutorial, which will take around one hour, we show how to encode logical calculi using rule-based languages and how to implement these using VLog. Namely, we discuss the following topics.

  • We briefly present the DL languages EL and ALC.
  • We discuss how to encode an existing consequence-based procedure for EL [10] using a fixed Datalog rule set.
  • We present different variants of the chase algorithm, which a sound and complete, albeit non-terminating, reasoning procedure for existential rules.
  • We discuss why we cannot encode such a procedure for ALC using a fixed Datalog rule set. Indeed, this is the cases because of the complexity properties of these two languages.
  • We discuss how to encode an existing consequence-based procedure for ALC [9] using a fixed Datalog(S) rule set.
  • In a hands-on session, we discuss how to implement the previuosly presented encodings the rule engine VLog.
  • We informally discuss how we can implement other existing reasoning algorithms using our approach.


References

  1. On Rules with existential Variables: Walking the Decidability Line
  2. The Vadalog System: Datalog-Based Reasoning for Knowledge Graphs
  3. Benchmarking the Chase
  4. Chase Termination for Guarded Existential Rules
  5. VLog: A Rule Engine for Knowledge for Knowledge Graphs
  6. Restricted Chase (Non)Termination for Existential Rules with Disjunctions
  7. Chasing Sets: How to Use Existential Rules for Expressive Reasoning
  8. Acyclicity Notions for Existential Rules and their application to Query Answering in Ontologies
  9. Consequence-driven Reasoning for Horn-SHIQ Ontologies
  10. The Incredible ELK - From Polynomial Procedures to Efficient Reasoning with EL Ontologies
  11. Extending Decidable Existential Rules by Joining Acyclicity and Guardedness
  12. Parallel Materialisation of Datalog Programs in Centralised, Main-memory RDF Systems
  13. Column-Oriented Datalog Materialization for Large Knowledge Graphs

David Carral

David Carral is a postdoctoral scholar at the chair for Knowledge-Based Systems at the Faculty of Computer Science of TU Dresden. He completed his master's and doctor's degrees at Wright State University, both under the supervision of Prof. Dr. Pascal Hitzler, in 2012 and 2016, respectively. For several months during his Ph.D., he was an exchange student at the University of Oxford, working under the supervision of Prof. Dr. Bernardo Cuenca Grau. His research interests include symbolic artificial intelligence and knowledge representation related topics. More precisely, David studies the theoretical properties of logical languages such as Description Logics and existential rules, and the implementation of reasoning algorithms.

Markus Krötzsch

Markus Krötzsch is a full professor at the Faculty of Computer Science of TU Dresden, where he is holding the chair for Knowledge-Based Systems. He obtained his Ph.D. from the Institute of Applied Informatics and Formal Description Methods (AIFB) of Karlsruhe Institute of Technology (KIT) in 2010, and thereafter worked as a researcher and departmental lecturer at the Department of Computer Science of the University of Oxford until October 2013. Krötzsch's extensive research activities in the area of rule-based knowledge representation and reasoning have contributed to the development and analysis of rule languages, rule-based inference methods, and rule reasoners. His wider research interests also include ontology languages, query answering, reasoning complexity, knowledge graphs, and content management and integration platforms for the Web of Data. He has published many works in leading journals and conferences, and two textbooks on semantic technologies. He has given tutorials and invited lectures at various events, including ESSLLI, IJCAI, and ICDT, and he has co-organised numerous scientific and educational events, most recently the Reasoning Web Summer School 2019.

Jacopo Urbani

Jacopo Urbani is an assistant professor at the Department of Computer Science of the Vrije Universiteit Amsterdam (VUA). He is also a guest researcher at the Centrum Wiskunde & Informatica and at the Max Planck Institute in Informatics. 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 and Germany, he joined the faculty of the VUA and has been tenured in 2018. He is one of the main developers of VLog and has published extensively on rule-based reasoning on Knowledge Graphs (KGs) at venues like AAAI, WWW, ISWC, etc. His recent interests include the application of rule-based reasoning for fact-checking and to perform KG completion using information extracted from unstructured sources.
The materials for the tutorial will eventually be posted here.