On Querying Incomplete Information in Databases under Bag Semantics

Marco Console, Paolo Guagliardo, Leonid LibkinIJCAI 2017 · DOI

TL;DR

This paper bridges the gap between theoretical database query answering and real-world SQL databases by introducing bag semantics to incomplete information querying. It reveals that while finding "certain" answers for simple queries is efficient, determining the maximum occurrences of answers becomes computationally intractable, impacting approximation schemes.

What Problem Does This Paper Address?

Many AI applications and data management tasks, like data integration and ontology-based querying, rely on querying databases. These databases are often "incomplete," meaning they might contain null values or represent multiple possible states. Traditionally, theoretical work on querying incomplete data has assumed "set semantics," where each piece of information is either present or absent. However, real-world SQL databases use "bag semantics" (or multisets), where data can appear multiple times, and the number of occurrences matters. This mismatch between set-based theory and bag-based practice creates a challenge: how do we accurately query incomplete data in a way that respects the nuances of bag semantics, especially when dealing with duplicate information? This paper aims to understand this problem, particularly for positive queries (unions of conjunctive queries), and its implications for approximating answers.

Methods

The paper introduces the concept of querying incomplete databases under bag semantics. It defines how standard relational algebra operations (selection, projection, Cartesian product, union) behave with bags, including the addition of intersection and duplicate elimination. The core of the methodology involves analyzing the minimum and maximum number of occurrences of a query result tuple across all possible complete databases derived from an incomplete one.

Key techniques include:

  • Defining Bag Semantics for Relational Algebra: Adapting standard operations to account for tuple multiplicities.
  • Analyzing Minimum and Maximum Occurrences: For a query result tuple ē and an incomplete database D, the paper defines minē(D, ē) (minimum occurrences across all possible worlds) and maxē(D, ē) (maximum occurrences).
  • Complexity Analysis: Investigating the computational complexity of computing minē and maxē for different query types, particularly focusing on data complexity (query fixed, database as input).
  • Approximation Schemes: Examining how existing approximation schemes for set semantics can be adapted to bag semantics, and identifying which ones remain tractable.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and complexity rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bag Semantics Matters for Incompleteness: The paper demonstrates that even for simple "positive" queries, the distinction between set and bag semantics significantly impacts how we query incomplete data. What's certain in sets might have a range of occurrences in bags.
  • Minimum Occurrences are Efficiently Computable: For positive queries, finding the minimum number of occurrences (minē) can be done efficiently (in DLOGSPACE). This is a crucial result, as it means we can still guarantee a lower bound on how many times a tuple will appear in query results, even with incomplete data and bag semantics.
  • Maximum Occurrences are Intractable: The paper's most striking finding is that computing the maximum number of occurrences (maxē) for positive queries is computationally intractable (NP-complete for a related problem, leading to coNP-completeness for checking if maxē < m). This intractability extends even to very simple queries like selecting from a single relation.
  • Implications for Approximation Schemes: The intractability of maxē directly impacts approximation strategies for query answering. Schemes that rely on computing maxē become infeasible for bag semantics, while those that only depend on minē can be adapted efficiently. This provides a theoretical explanation for why some approximation methods work well in practice with real-world databases (which use bag semantics) while others don't.

Key Results

  • Theorem 1: For positive relational algebra queries (RA+), computing minē(D, ē) under bag semantics is efficient (DLOGSPACE with respect to data complexity).
  • Theorem 2: The problem of checking if a tuple occurs at least m times in a relation under bag semantics (related to maxē) is NP-complete. This implies that computing maxē for queries is generally intractable.
  • Proposition 2: For RA+ queries with duplicate elimination as the outermost operation (e.g., SELECT DISTINCT ...), maxē(D, ē) can be computed efficiently.
  • Adaptation of Approximation Schemes: The paper shows that one existing approximation scheme for set semantics (which relies on maxē) cannot be adapted to bags due to intractability, while another scheme (which relies on minē) can be efficiently adapted.

Limitations and Future Work

  • Focus on Positive Queries: The paper primarily addresses positive relational algebra queries (unions of conjunctive queries). The behavior of more complex queries (involving negation or full relational algebra) under bag semantics with incomplete data is not fully explored.
  • Theoretical Focus: The work is theoretical, focusing on complexity classes. While it provides justification for practical observations, it doesn't present new algorithms or empirical evaluations on real-world systems.
  • Future Work: The authors suggest several avenues:
  • Understanding incompleteness in real-life databases more deeply.
  • Developing and optimizing approximation schemes for bag semantics.
  • Extending results to the open-world assumption.
  • Investigating querying inconsistent data and schema mappings.
  • Exploring new applications that combine data with knowledge and meta-information.

Summary updated

BibTeX
@inproceedings{console2017querying,
  author = {Marco Console and Paolo Guagliardo and Leonid Libkin},
  title = {{On Querying Incomplete Information in Databases under Bag Semantics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/138},
}
Figure