Distance-Bounded Consistent Query Answering

Andreas Pfandler, Emanuel SallingerIJCAI 2015

Abstract

This paper introduces a "bounded" version of Consistent Query Answering (CQA), where the number of allowed changes to fix an inconsistent database is limited by a fixed constant $b$. By imposing this distance bound, the authors demonstrate that previously undecidable reasoning problems become decidable and, in many cases, significantly less computationally expensive. We provide a comprehensive complexity analysis for various integrity constraint classes, highlighting shifts in complexity and the restoration of decidability for powerful constraint languages.

Introduction

Real-world databases frequently contain data that violates integrity constraints (ICs), such as an employee assigned to a non-existent department. Consistent Query Answering (CQA) is the standard framework for querying such inconsistent data by evaluating queries across all possible "repairs"—consistent versions of the database that are minimally different from the original. However, for powerful constraint languages like tuple-generating dependencies (tgds), CQA is often undecidable or computationally prohibitive ($\\Pi^P_2$-complete). This stems from the fact that repairs might require an unbounded number of modifications. Furthermore, standard CQA may produce unintuitive results by treating massive deletions as equally valid to minor insertions.

Methods

The authors propose Distance-Bounded CQA (b-CQA) and Distance-Bounded Repair Checking (b-RC). These frameworks introduce a fixed integer $b$ representing the maximum allowed distance (number of changes) between the original database and a repair. The study focuses on the combined complexity of these problems across twelve classes of integrity constraints, ranging from simple keys to full First-Order (FO) logic.

Hierarchy of integrity constraint classes studied in the paper.

The complexity bounds are established through rigorous mathematical analysis and reductions to known problems in logic and complexity theory, such as SAT/UNSAT and Quantified Boolean Formula (QBF) satisfaction.

Key Results and Complexity Landscape

The primary contribution is a comprehensive mapping of the complexity landscape for bounded problems compared to their standard counterparts.

Complexity landscape for bounded (b-RC, b-CQA) and standard (RC*, CQA*) problems across various IC classes.

Several key insights emerge:

  1. Restored Decidability: By bounding the distance, all considered constraint classes—including general tgds and FO constraints, which are normally undecidable—become decidable. For instance, FO constraints move from undecidable to PSPACE-complete.
  2. Complexity Reductions: For many languages, complexity drops significantly. Functional dependencies (FDs) drop from $\\Pi^P_2$-complete to NP-complete.
  3. Complexity Increases: Counter-intuitively, for Local-As-View (LAV) tgds and inclusion dependencies (IDs), complexity increases from NP to $\\Pi^P_2$. In standard CQA, these constraints often allow for a single "unique" repair (e.g., deleting offending rows). In the bounded version, if that unique repair exceeds the bound $b$, the system must search through many other potential repair candidates, increasing the computational burden.

Discussion and Future Work

Bounding the distance aligns CQA more closely with practical database management, where data is assumed to be mostly correct and massive repairs are undesirable. However, this study assumes $b$ is a fixed constant. Future research should explore parameterized complexity (treating $b$ as an input parameter) and data complexity (where constraints are fixed and only the database size varies). Additionally, exploring fractional bounds (e.g., a percentage of the database) and developing optimized algorithms for practical implementation remain open challenges.

Summary updated

BibTeX
@inproceedings{pfandler2015distance,
  author = {Andreas Pfandler and Emanuel Sallinger},
  title = {{Distance-Bounded Consistent Query Answering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure