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

Journal of Inforamtion Science and Engineering, Vol.12 No.1, pp.51-78 (March 1996)
Implementing the Division Operation on a
Database Containing Uncertain Data*

Frank S. C. Tseng, Arbee L. P. Chen# and Wei-Pang Yang**
Department of Information Management
Yuan-Ze Institute of Technology
Chungli, Taiwan 320, R.O.C.
#Department of Computer Science
National Tsing Hua University
Hsinchu, Taiwan 300, R.O.C.
**Department of Computer Science and Information Engineering
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.