Conservative Extensions for Existential Rules

2022/02/11 by Jean Christoph Jung, Jung, Jean Christoph, Carsten Lutz +3
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Databases (cs.DB) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.48550/arxiv.2202.05689

openalex publication_date 2022/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Model-theoretic Characterizations of Existential Rule Languages
• Capturing Homomorphism-Closed Decidable Queries with Existential Rules
• A Single Approach to Decide Chase Termination on Linear Existential Rules
• Loop Restricted Existential Rules and First-order Rewritability for Query Answering
• Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets