Return to Seminars

September 26, 2019, 2:00 PM, Stathis Delivorias (Graphik)

Soutenance de thèse :  “Chase Variants & Boundedness

La soutenance se déroulera le Jeudi 26 Septembre 2019 à 14h00 en salle 2.22, au deuxième étage du bâtiment 5 du LIRMM.

Le jury sera composé de :

Mme Marie-laure MUGNIER Université de Montpellier Directeur de thèse
Mme Sophie TISON Université Lille 1- Sciences et Technologies Rapporteur
M. Chan LE DUC Université Paris 8 (IUT de Montreuil) Rapporteur
M. Federico ULLIANA Université de Montpellier Co-encadrant de thèse
M. Michel LECLèRE Université de Montpellier Co-encadrant de thèse
Mme Meghyn BIENVENU Université de Bordeaux Examinateur
M. Sebastian RUDOLPH Université de Dresde, Allemagne Examinateur
M. David DELAHAYE Université de Montpellier Examinateur


The chase is a family of algorithms designed to infer data with the use of ontological knowledge, which is encoded in existential rules, a sub-language of first-order logic. A considerable literature has been devoted to its analysis, approaching it from a variety of presupposed terminological and notational background. We define a unifying framework for the specification and study of chase algorithms. We utilize it to compare and clarify the properties that discern the different variants of the chase. We particularly focus on studying whether there is a bound to the maximum length of a chain of interdependent rule applications (where interdependency means that the output of a rule application is contributing to triggering the next rule application). This is the problem of boundedness, or k-boundedness, when the bound k is given. By investigating a number of intermediate properties, we find that k-boundedness is decidable for several chase variants. In addition to other secondary results, we define two new chase variants with the aim of reducing redundant rule applications without heavily increasing the computation cost.

Permanent link to this article: