Piotr Ostropolski-Nalewaja
Uniwersytet Wroclawski
Friday June 20th, 2025, 14:00
Amphitheatre F107, Montbonnot
entrée libre
Abstract
This tutorial will discuss Existential Rules.
Existential rules (also called Tuple-Generating Dependencies, Conceptual Graph Rules, Datalog+-, and ∀∃-rules) are an extension of Datalog - the foundation of virtually every logic programming language - and are primarily discussed within boundaries of "knowledge representation via means of various logics" or more formally, the field of Ontology-Mediated Knowledge Representation. Due to their simple formulation and the constructive nature of the setting, existential rules and the accompanying algorithm called "the chase" also appear in various other, seemingly disconnected contexts.
On the theory side, existential rules and the chase procedure are utilized to tackle a range of problems. A short and non-comprehensive list includes query entailment problems over ontologies constructed from existential rules, querying over probabilistic databases, and querying under database views. Moreover, the chase is used in the context of checking query containment under TGDs, computing data-exchange solutions, query rewritability under database views, and query determinacy problems.
From a practical standpoint, existential rules are gaining prominence as a formalism for driving data-centric analytic computations, knowledge graphs, and large ontologies (up to 10^8 input facts). Extending Datalog, they serve as a link between rule-based systems and databases, effectively meeting the growing demands for data analytics and declarative management.
Despite all the complicated terminology mentioned above, the tutorial is meant to be introductory in nature - meaning we will introduce the formalism, the problems usually discussed in this setting, and walk through lots of examples. In short, little to no prior knowledge is required, and all are welcome.