Abstract
In heterogeneous databases, the user may issue a query to joint two relations in different databases on the keys. However, the keys may be incompatible. The authors extend results on probabilistic query processing to consider joining two relations with incompatible keys. A new approach to identify the 'same' entities in different relations is proposed. Various data and schema conflicts such as missing data, inconsistent data and domain mismatch are considered in the identification process. Probabilistic techniques are used to estimate the sameness of two entities, to process queries, and to estimate the degree of uncertainty for the query results.