KR2022Proceedings of the 19th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning

Haifa, Israel. July 31–August 5, 2022.

Edited by
  1. Gabriele Kern-Isberner
  2. Gerhard Lakemeyer
  3. Thomas Meyer

ISSN: 2334-1033
ISBN: 978-1-956792-01-0

Sponsored by
Published by

Copyright © 2022 International Joint Conferences on Artificial Intelligence Organization

Conservative Extensions for Existential Rules

  1. Jean Christoph Jung(University of Hildesheim)
  2. Carsten Lutz(University of Leipzig)
  3. Jerzy Marcinkowski(University of Wroclaw)
PDF
BibTeX
https://doi.org/10.24963/kr.2022/20

Keywords

  1. Ontology-based data access, integration, and exchange
  2. Computational aspects of knowledge representation
  3. Applications of KR in databases
  4. Ontology formalisms and models

Abstract

We study the problem to decide, given sets T1, T2 of tuple-generating dependencies (TGDs), also called existential rules, whether T2 is a conservative extension of T1. We consider two natural notions of conservative extension, one pertaining to answers to conjunctive queries over databases and one to homomorphisms between chased databases. Our main results are that these problems are undecidable for linear TGDs, undecidable for guarded TGDs even when T1 is empty, and decidable for frontier-one TGDs.