Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] |

Implementing the Division Operation on a

Database Containing Uncertain Data

**Frank S. C. Tseng, Arbee L. P. Chen ^{#} and Wei-Pang Yang^{**} **

Yuan-Ze Institute of Technology

Chungli, Taiwan 320, R.O.C.

National Tsing Hua University

Hsinchu, Taiwan 300, R.O.C.

National Chiao Tung University

Hisinchu, Taiwan 300, R.O.C.

Uncertain data in databases were originally denoted as *null values*, which were later generalized to partial values. Based on the concept of partial values, we have further generalized the notion to *probabilistic partial values*. In this paper, an important operation, division, is fully studied to handle partial values and probabilistic partial values. Due to the uncertainty of partial values and probabilistic partial values, the corresponding extended division may produce *maybe tuples* and *maybe tuples with degrees of uncertainty*, respectively.

To process this extended division, we decompose a relation consisting of partial values or probabilistic partial values into a set of relations containing only definite values. Bipartite graph matching techniques are then applied to develop efficient algorithms for the extended division that handles partial values. The refinement of the maybe result is also discussed. Finally, we study the extended division which handles probabilistic partial values.

Keywords: partial values, probabilistic partial values, graph matching, uncertain data

Received March 24, 1993; revised July 14, 1995.

Communicated by Y. S. Kuo.
^{*}This work was partially supported by the Republic of China National Science Council under Contract No. NSC 84-2213-E-007-007.