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.
%0 Journal Article
%1 Jung2022-jv
%A Jung, Jean Christoph
%A Lutz, Carsten
%A Marcinkowski, Jerzy
%D 2022
%I arXiv
%K
%T Conservative extensions for existential rules
%X 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.
@article{Jung2022-jv,
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.},
added-at = {2024-09-10T11:56:37.000+0200},
author = {Jung, Jean Christoph and Lutz, Carsten and Marcinkowski, Jerzy},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/27d0991371f4e030c951a0c3178f86a5b/scadsfct},
interhash = {b5863a1285fd625fa4ac272d60114330},
intrahash = {7d0991371f4e030c951a0c3178f86a5b},
keywords = {},
publisher = {arXiv},
timestamp = {2024-09-10T15:15:57.000+0200},
title = {Conservative extensions for existential rules},
year = 2022
}