A Single Approach to Decide Chase Termination on Linear Existential Rules

Vortrag von Michaël Thomazo

Veranstaltungsort: APB 3027
Beginn: 9. August 2018 um 13:00
Ende: 9. August 2018 um 14:30
Forschungsgruppe: Computational Logic
Forschungsgruppe: Wissensbasierte Systeme
Event series: KBS Seminar
iCal

Abstract: Existential rules are a knowledge representation and reasoning formalism that extends both positive rules a la Datalog and most description logics used in ontology-based query answering. The chase is a fundamental tool for reasoning on knowledge bases composed of an instance and a set of existential rules. It is well-known that deciding, given a chase variant and a set of existential rules, whether the chase will halt for any instance is an undecidable problem. Hence, a crucial issue is whether it becomes decidable for known classes of existential rules. We focus on three main chase variants, namely semi-oblivious, restricted and core chase, and consider linear existential rules, a simple yet important subclass of existential rules. We show that the termination problem is decidable in these three variants with a novel unified approach based on a single graph and a single notion of forbidden pattern.

Joint work with M. Leclère, M.-L. Mugnier and F. Ulliana.

Speaker Bio: Michaël Thomazo is an INRIA researcher (CEDAR team), currently working on ontology-based query answering, and especially efficient evaluation of reformulated queries. He had been a post-doc at TU Dresden, working with S. Rudolph, and got his Ph.D from the University of Montpellier, supervised by J.-F. Baget and M.-L. Mugnier. You can find more details at http://pages.saclay.inria.fr/michael.thomazo/.