This paper reports our first set of results on managing un-
certainty in data integration. We posit that data-integration
systems need to handle uncertainty at three levels, and do
so in a principled fashion. First, the semantic mappings be-
tween the data sources and the mediated schema may be
approximate because there may be too many of them to be
created and maintained or because in some domains (e.g.,
bioinformatics) it is not clear what the mappings should be.
Second, queries to the system may be posed with keywords
rather than in a structured form. Third, the data from the
sources may be extracted using information extraction tech-
niques and so may yield imprecise data.
As a first step to building such a system, we introduce the
concept of probabilistic schema mappings and analyze their
formal foundations. We show that there are two possible
semantics for such mappings: by-table semantics assumes
that there exists a correct mapping but we don’t know what
it is; by-tuple semantics assumes that the correct mapping
may depend on the particular tuple in the source data. We
present the query complexity and algorithms for answering
queries in the presence of approximate schema mappings,
and we describe an algorithm for efficiently computing the
top-k answers to queries in such a setting.