Best Answers over Incomplete Data : Complexity and First-Order Rewritings

Amélie Gheerbrant, Cristina SirangeloIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of answering queries over incomplete databases, where traditional "certain answers" can be too restrictive. The authors introduce and analyze "best answers" – a more flexible notion that captures answers with the most support across possible complete databases. They characterize the complexity of finding these best answers and, crucially, develop a practical FO-rewriting technique for unions of conjunctive queries, enabling efficient computation using standard database engines.

What Problem Does This Paper Address?

In many real-world scenarios, databases are incomplete, meaning they contain missing information (represented by nulls). When querying such databases, we often want to find "certain answers" – those that hold true regardless of how the missing information is filled in. However, this strict requirement can lead to very few or no answers, making the process frustrating. This paper addresses this by proposing and analyzing "best answers." Best answers are defined as those that are true in the largest number of possible complete databases. This offers a more practical alternative when certain answers are scarce, while still providing a meaningful guarantee. The paper also investigates the computational complexity of finding both best and certain answers, particularly for first-order (FO) queries, and proposes a method to compute best answers for a common class of queries (unions of conjunctive queries) using query rewriting.

Methods

The paper introduces the concept of "best answers" as a relaxation of "certain answers." They define "support" for an answer as the set of valuations (ways to fill in nulls) that make the answer true. An answer is considered "better" if it has a larger support set. Best answers are then those for which no other answer is better.

A significant contribution is the development of a first-order (FO) rewriting technique for computing best answers for unions of conjunctive queries. This involves:

  1. Normalizing Conjunctive Queries: Rewriting conjunctive queries into a "non-repeating variable normal form" (NRV) to separate relational facts from equality constraints.
  2. Encoding Equivalence and Support Inclusion: Developing FO formulas (equiv, comp, imply) to capture the relationships between nulls, constants, and equality constraints, and to represent the inclusion of support sets.
  3. Constructing the Best Answer Rewriting: Combining these FO components to create a single FO query (bestq) that, when evaluated on the incomplete database, directly returns the best answers. This allows leveraging existing, highly optimized FO query evaluation engines.

The paper also analyzes the data complexity of decision problems related to best and certain answers, showing significant differences in their computational hardness.

Datasets

Not discussed in the paper. The focus is on theoretical analysis and algorithmic development for arbitrary incomplete databases.

Key Insights and Ideas

  • Best Answers as a Practical Alternative: When certain answers are too restrictive, best answers offer a valuable middle ground, providing answers with the strongest possible guarantee without demanding absolute certainty.
  • Complexity Differences: The paper highlights that the complexity of finding best answers and certain answers can differ significantly, especially when considering different formulations of the decision problem (e.g., "is this tuple a best answer?" vs. "is the set of best answers equal to this set?").
  • FO Rewriting for Tractability: The core innovation is demonstrating that best answers for unions of conjunctive queries can be computed by rewriting them into a single first-order query. This is a major practical advancement, as it allows using standard, efficient database query engines.
  • Bridging Theory and Practice: The work connects theoretical complexity analysis with practical query answering techniques, offering a path to implement more robust query answering systems for incomplete data.

Key Results

  • Complexity Characterization: The paper characterizes the data complexity of decision problems for best and certain answers for first-order queries. For best answers, problems like BESTANSWER= (is a given tuple a best answer?) and BESTANSWER= (is the set of best answers equal to a given set?) are shown to be PNP[log n]-complete. For certain answers, CERTAINANSWER= is DP-complete, and CERTAINANSWER= is PNP[log n]-complete.
  • FO Rewriting for Unions of Conjunctive Queries: A key result is Theorem 4.16, which states that for a union of conjunctive queries Q and an incomplete database D, a tuple t is a best answer if and only if D satisfies the rewritten FO query bestq(t).
  • Data Complexity for UCQs: Corollary 4.18 shows that for a fixed union of conjunctive queries Q, the data complexity of computing best answers is DLOGSPACE. This is a significant improvement over the general FO case.
  • Combined Complexity: The combined complexity (considering query and database as input) for unions of conjunctive queries is shown to be I-complete.

Limitations and Future Work

  • Combined Complexity vs. Rewriting Optimality: While the FO rewriting approach is practical, its combined complexity is PSPACE, and the problem itself is I-complete. The authors acknowledge that their rewriting approach is not optimal in terms of combined complexity but highlights its advantage in leveraging optimized FO evaluators.
  • Integrity Constraints: The paper suggests exploring how integrity constraints (like keys and functional dependencies) interact with best answer computation and rewriting techniques.
  • More Expressive Rewriting Languages: Future work could investigate using more expressive languages like Datalog or fixed-point logics for rewritings, potentially handling larger classes of queries.
  • Alternative Semantics of Incompleteness: The paper used closed-world semantics. Extending the techniques to other semantics, such as those for handling data inconsistencies, is a promising direction.
  • Rewritings for Certain Answers: The authors express interest in investigating how their rewriting techniques could be extended to study rewritings for certain answers.

Summary updated

BibTeX
@inproceedings{gheerbrant2019best,
  author = {Amélie Gheerbrant and Cristina Sirangelo},
  title = {{Best Answers over Incomplete Data : Complexity and First-Order Rewritings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/236},
}
Figure