Incompleteness in information integration

Evgeny Kharlamov, Werner NuttPVLDB 2008 · DOI · OpenReview

TL;DR

This paper tackles the critical challenge of information integration when the data sources themselves are incomplete (e.g., contain null values). It proposes a formal framework for "Incomplete Information Integration" (III) that extends existing methods to handle various forms of data incompleteness at the source, integrated database, and query levels, aiming to provide more robust and realistic data integration solutions.

What Problem Does This Paper Address?

Information integration (II) is essential for making sense of the ever-growing volume of data from diverse sources. Traditional II approaches often assume that the data sources are complete and "null-free." However, in reality, data is frequently incomplete due to various reasons like communication errors, privacy concerns, or simply missing information. This incompleteness can manifest as SQL NULLs, missing values in relational wrappers, or even incomplete knowledge about relationships between data. Existing II techniques, particularly in virtual integration (where a global schema is presented over distributed sources), struggle to handle this inherent incompleteness at the source level. This paper aims to bridge this gap by developing a theory and algorithms for integrating incomplete information, going beyond just handling incompleteness in the integrated view.

Methods

The paper introduces the concept of "Incomplete Information Integration" (III) and proposes a formal framework to address it. Key methodological contributions include:

  • Semantics for III: Defining how to interpret and combine data from incomplete sources. This involves extending existing notions of compatibility between source and global schemas to account for various types of nulls (SQL NULLs, Codd tables, v-tables, c-tables).
  • Query Answering Semantics: Developing semantics for answering queries over incomplete integrated databases. This includes distinguishing between "certain answers" (always true) and "incomplete answers" (which can reflect the source incompleteness).
  • Representation Formalisms: Investigating how to compactly represent incomplete integrated databases. The paper shows that v-multi-tables can be used to represent the global database even when sources contain SQL NULLs.
  • Query Rewriting and Computation: Proposing techniques to compute answers efficiently. This involves adapting query rewriting techniques and chase algorithms to handle the presence of nulls, ensuring that the computed answers are semantically correct with respect to the incomplete sources.

The paper distinguishes between two main approaches for handling incompleteness in sources: "Open-World Compatibility" (OWA) and "Closed-World Compatibility" (CWA), drawing parallels to data exchange literature.

Datasets

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

Key Insights and Ideas

  • Real-world data is inherently incomplete: The paper strongly emphasizes that assuming null-free sources is a significant limitation for practical information integration.
  • Incompleteness needs to be handled at multiple levels: The framework addresses incompleteness in sources, the integrated database, and even in the query answers themselves.
  • SQL NULLs pose unique challenges: The paper highlights that SQL NULLs, being constants, behave differently from existential variables and impact integration significantly, particularly in join operations.
  • V-multi-tables are a powerful representation: The research demonstrates that v-multi-tables can effectively represent integrated databases derived from sources with SQL NULLs, enabling further processing.
  • "Incomplete Answers" are valuable: Beyond certain answers, the paper argues for the utility of "incomplete answers" that can directly reflect the uncertainty inherited from the sources.

Key Results

  • Consistency of integration settings: The paper provides a theorem (Theorem 5.1) showing that checking the consistency of integration settings with SQL NULLs and sound conjunctive LAV mappings is computationally efficient (LOGSPACE in source size, LINEAR in mapping size).
  • Representation of global databases: Theorems 5.2 and 7.1 establish that global databases resulting from integration with SQL NULLs and v-tables can be represented by v-multi-tables, which can be computed using chase mechanisms.
  • Computation of certain answers: Theorems 5.3 and 7.1 provide methods for computing certain answers over incomplete sources, showing that for CWA semantics with SQL NULLs, certain answers can be computed similarly to null-free cases, but for OWA, more sophisticated techniques are needed. For v-tables, certain answers can be derived from the chase of the v-multi-table.
  • Incomplete answers defined: The paper formally defines incomplete answers (Inc(q, I, M)) as the direct output of queries on the representation of the integrated database (e.g., q(T_M(I))).

Limitations and Future Work

  • Focus on specific mapping types: The current work primarily focuses on sound conjunctive LAV mappings. Future work aims to extend results to other mapping types (e.g., non-sound, non-conjunctive).
  • Representation systems: The paper has explored SQL NULLs, Codd tables, and v-tables. Future work includes extending the results to c-tables and world-set decompositions (WSDs).
  • Efficient computation of incomplete answers: While incomplete answers are defined, the paper acknowledges that computing them efficiently (e.g., via rewriting techniques) is an ongoing research challenge, with current approaches potentially leading to exponential complexity.
  • Probabilistic databases: The paper mentions probabilistic databases as another area for future exploration.
  • Implementation: The authors plan to develop implementation techniques to efficiently compute different types of answers.

Summary updated

BibTeX
@article{kharlamov2008incompleteness,
  author = {Evgeny Kharlamov and Werner Nutt},
  title = {{Incompleteness in information integration}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  doi = {10.14778/1454159.1454242},
}

Loading related content...

Figure