Query Answers

Title: Query Answers

Main Research Question: How can we efficiently determine consistent answers to queries from inconsistent databases?

Methodology: The study proposes a method for obtaining reliable, consistent information from inconsistent databases by defining and computing consistent query answers. This is achieved by considering the notion of repair - another consistent database that is minimally different from the original database. The paper focuses on first-order queries and generalizes the concept of functional dependencies to denial constraints, allowing for arbitrary built-in predicates and data types.

Results: The paper provides a complete classification of the computational complexity of computing consistent query answers for first-order queries and denial constraints. It identifies a class of restricted existentially quantified queries for which consistent query answers can be computed in PTIME, and demonstrates how the complexity depends on the type of constraints, their number, and the size of the query.

Implications: The research has practical implications for data integration scenarios where databases may not satisfy given integrity constraints. By providing a method to compute consistent query answers, it ensures that the information obtained is reliable and true, regardless of the way the database is fixed to remove constraint violations. This can significantly improve the accuracy and efficiency of decision-making processes that rely on integrated databases.

Link to Article: https://arxiv.org/abs/0204010v1 Authors: arXiv ID: 0204010v1