Approximate Top-K Answering under Uncertain Schema Mappings

Longzhuang Li, Feng Tian, Yonghuai Liu, Shanxian Mao

Research output: Contribution to journalArticle (journal)peer-review

24 Downloads (Pure)


Data integration techniques provide a communication bridge between isolated sources and offer a platform for information exchange. When the schemas of heterogeneous data sources map to the centralized schema in a mediated data integration system or a source schema maps to a target schema in a peer-to-peer system, multiple schema mappings may exist due to the ambiguities in the attribute matching. The obscure schema mappings lead to the uncertainty in query answering, and frequently people are only interested in retrieving the best k answers (top-k) with the biggest probabilities. Retrieving the top-k answers efficiently has become a research issue. For uncertain queries, two semantics, by-table and by-tuple, have been developed to capture top-k answers based on the schema mapping probabilities. However, although the existing algorithms support certain features to capture the accurate top-k answers and avoid accessing all data from sources, they cannot effectively reduce the number of processed tuples in most cases. In this paper, new algorithms based on the histogram approximation and heuristic are proposed to efficiently identify the top-k answers for the data integration systems under uncertain schema mappings. In the experiments, the Histogram algorithm in the by-table semantics and the expected approach in the by-tuple semantics are shown to significantly reduce the number of processed tuples while maintaining high accuracy with the estimated probabilistic confidence.
Original languageEnglish
Pages (from-to)71-91
Number of pages21
JournalData & Knowledge Engineering
Early online date17 Oct 2018
Publication statusPublished - 1 Nov 2018


  • Database integration
  • Histogram-based approximation
  • Top-k query
  • Uncertain schema mappings


Dive into the research topics of 'Approximate Top-K Answering under Uncertain Schema Mappings'. Together they form a unique fingerprint.

Cite this