A probabilistic approach to disjunctive information in relational databases

The authors present a novel approach to disjunctive information in relational databases. They focus on the exclusive disjunction representation of incomplete information with some quantitative measurement. Weighted disjunctive subtuples are introduced to represent disjunctive values with an attached probability distribution. Maybe tuples can also be represented by introducing a dummy tuple to indicate nonexistence. A general relation structure is defined for irregular tables. Then, the basic relational operators are extended. Query evaluation in the extended model is shown to be correct in the sense that the set of probabilistic possible worlds (PPOSS) of a result table is the same as the PPOSS obtained by applying the operator to the corresponding relation(s) in each of the PPOSS of the operand relation. The Selection, Projection, Union, Difference, and Natural Key-join operations on extended relations run in polynomial time. The model allows more accurate calculation of aggregate functions such as COUNT and SUM. The features of the model make it practical for non-traditional applications where data is stochastic in nature