Conservative Extensions for Existential Rules
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Chasing Streams with Existential Rules
We study reasoning with existential rules to perform query answering over streams of data. On static databases, this problem has been widely studied, but its extension to rapidly changing data has not yet been considered…
Complexity of Arithmetic in Warded Datalog+-
Warded Datalog+- extends the logic-based language Datalog with existential quantifiers in rule heads. Existential rules are needed for advanced reasoning tasks, e.g., ontological reasoning. The theoretical efficiency gua…
DescriptiveKnowledge GraphsOpen-Ended Question AnsweringParallelisable Existential Rules: a Story of Pieces
In this paper, we consider existential rules, an expressive formalism well suited to the representation of ontological knowledge and data-to-ontology mappings in the context of ontology-based data integration. The chase …
Data IntegrationExtending Acyclicity Notions for Existential Rules (\emph{long version})
Existential rules have been proposed for representing ontological knowledge, specifically in the context of Ontology-Based Query Answering. Entailment with existential rules is undecidable. We focus in this paper on cond…
NegationQuery Answering with Inconsistent Existential Rules under Stable Model Semantics
Traditional inconsistency-tolerent query answering in ontology-based data access relies on selecting maximal components of an ABox/database which are consistent with the ontology. However, some rules in ontologies might …