A Single Approach to Decide Chase Termination on Linear Existential Rules
| Autor: | Michel Leclère, Marie-laure Mugnier, Michaël Thomazo, Federico Ulliana |
|---|---|
| Přispěvatelé: | Wagner, Michael, Graphs for Inferences on Knowledge (GRAPHIK), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, arXiv:1810.02132, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science 000 Computer science knowledge general works InformationSystems_DATABASEMANAGEMENT 0102 computer and information sciences 02 engineering and technology Chase Decidability 16. Peace & justice 01 natural sciences Logic in Computer Science (cs.LO) [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Computer Science 0202 electrical engineering electronic engineering information engineering Existential rules 020201 artificial intelligence & image processing Tuple Generating Dependencies |
| Zdroj: | ICDT 2019-22nd International Conference on Database Theory ICDT 2019-22nd International Conference on Database Theory, Mar 2019, Lisbonne, Portugal. pp.18:1--18:19, ⟨10.4230/LIPIcs.ICDT.2019.18⟩ [Research Report] arXiv:1810.02132. 2018 Proceedings of the 31st International Workshop on Description Logicsco-located with 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018) 31st International Workshop on Description Logics (DL) 31st International Workshop on Description Logics (DL), Oct 2018, Tempe, United States Scopus-Elsevier HAL |
| DOI: | 10.4230/lipics.icdt.2019.18 |
| Popis: | 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, a simple yet important subclass of existential rules that generalizes inclusion dependencies. We show the decidability of the all instance chase termination problem on linear 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, we provide the first positive decidability results concerning the termination of the restricted chase, proving that chase termination on linear existential rules is decidable for both versions of the problem: Does every fair chase sequence terminate? Does some fair chase sequence terminate? Comment: 28 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|