1 Search Results for "Mugnier, Marie-Laure"

Document
DOI: 10.4230/LIPIcs.ICDT.2019.18
A Single Approach to Decide Chase Termination on Linear Existential Rules

Authors: Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
Existential rules, long known as tuple-generating dependencies in database theory, have been intensively studied in the last decade as a powerful formalism to represent ontological knowledge in the context of ontology-based query answering. A knowledge base is then composed of an instance that contains incomplete data and a set of existential rules, and answers to queries are logically entailed from the knowledge base. This brought again to light the fundamental chase tool, and its different variants that have been proposed in the literature. It is well-known that the problem of determining, given a chase variant and a set of existential rules, whether the chase will halt on any instance, is undecidable. Hence, a crucial issue is whether it becomes decidable for known subclasses of existential rules. In this work, we consider linear existential rules with atomic head, a simple yet important subclass of existential rules that generalizes inclusion dependencies. We show the decidability of the all-instance chase termination problem on these rules for three main chase variants, namely semi-oblivious, restricted and core chase. To obtain these results, we introduce a novel approach based on so-called derivation trees and a single notion of forbidden pattern. Besides the theoretical interest of a unified approach and new proofs for the semi-oblivious and core chase variants, we provide the first positive decidability results concerning the termination of the restricted chase, proving that chase termination on linear existential rules with atomic head is decidable for both versions of the problem: Does every chase sequence terminate? Does some chase sequence terminate?
Cite as

Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana. A Single Approach to Decide Chase Termination on Linear Existential Rules. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{leclere_et_al:LIPIcs.ICDT.2019.18,
  author =	{Lecl\`{e}re, Michel and Mugnier, Marie-Laure and Thomazo, Micha\"{e}l and Ulliana, Federico},
  title =	{{A Single Approach to Decide Chase Termination on Linear Existential Rules}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.18},
  URN =		{urn:nbn:de:0030-drops-103200},
  doi =		{10.4230/LIPIcs.ICDT.2019.18},
  annote =	{Keywords: Chase, Tuple Generating Dependencies, Existential rules, Decidability}
}
  • Refine by Author
  • 1 Leclère, Michel
  • 1 Mugnier, Marie-Laure
  • 1 Thomazo, Michaël
  • 1 Ulliana, Federico

  • Refine by Classification
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Theory of computation → Logic

  • Refine by Keyword
  • 1 Chase
  • 1 Decidability
  • 1 Existential rules
  • 1 Tuple Generating Dependencies

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact