ANSWERING HETEROGENEOUS DATABASE QUERIES WITH DEGREES OF UNCERTAINTY

Abstract

In heterogeneous database systems, partial values have been used to resolve some schema integration problems. Performing operations on partial values may produce maybe tuples in the query result which cannot be compared. Thus, users have no way to distinguish which maybe tuple is the most possible answer. In this paper, the concept of partial values is generalized to probabilistic partial values. We propose an approach to resolve the schema integration problems using probabilistic partial values and develop a full set of extended relational operators for manipulating relations containing probabilistic partial values. With this approach, the uncertain answer tuples of a query are associated with degrees of uncertainty (represented by probabilities). That provides users a comparison among maybe tuples and a better understanding on the query results. Besides, extended selection and join are generalized to alpha-selection and alpha-join, respectively, which can be used to filter out maybe tuples with low probabilities-those which have probabilities smaller than alpha.