Paper ID: 2401.05743

Consistent Query Answering for Existential Rules with Closed Predicates

Lorenzo Marconi, Riccardo Rosati

Consistent Query Answering (CQA) is an inconsistency-tolerant approach to data access in knowledge bases and databases. The goal of CQA is to provide meaningful (consistent) answers to queries even in the presence of inconsistent information, e.g. a database whose data conflict with meta-data (typically the database integrity constraints). The semantics of CQA is based on the notion of repair, that is, a consistent version of the initial, inconsistent database that is obtained through minimal modifications. We study CQA in databases with data dependencies expressed by existential rules. More specifically, we focus on the broad class of disjunctive embedded dependencies with inequalities (DEDs), which extend both tuple-generating dependencies and equality-generated dependencies. We first focus on the case when the database predicates are closed, i.e. the database is assumed to have complete knowledge about such predicates, thus no tuple addition is possible to repair the database. In such a scenario, we provide a detailed analysis of the data complexity of CQA and associated tasks (repair checking) under different semantics (AR and IAR) and for different classes of existential rules. In particular, we consider the classes of acyclic, linear, full, sticky and guarded DEDs, and their combinations.

Submitted: Jan 11, 2024