A probabilistic relational model and algebra

Reviewer: Edward Y. Lee

The authors summarize work to develop a more robust and complete relational database model, the probabilistic relational model (PRM), for handling uncertainty in the data values. The first section is an introduction. Section 2 examines previous research dealing with data uncertainty. Section 3 gives a description of the PRM that conforms to the first normal form (1nf) with a consistent extension of the traditional relational algebra and is reducible to the latter. Section 4 provides a more detailed discussion of the relational algebra for the PRM. Section 5 discusses some of the properties of the new relational algebra, and incompleteness in the joint probability of objects is treated in section 6. Section 7, the conclusion, suggests future directions for research. The main audience for this paper is relational database researchers who have dealt with related topics. More practical users of relational databases may wish to skip sections 4 through 6, reading the remaining sections for an overview of research on probabilistic relational models. The authors do not indicate that any practical applications have been developed using their PRM. The example they provide along with their explanation of the model sounds like a possible application to an employee database, but its practicality is not demonstrated. The summary of previous research into the PRM in section 2 is fairly complete. The authors point out some of the pitfalls of other models and some of the extensions others have attempted in order to obtain a closed model for the probabilistic relational algebra. One of the authors' main objections to the other models is that they cannot express the model in 1nf, so it becomes harder to prove the closure properties of the extension and relational algebraic operations. In section 3, the authors provide more details about their model and point out the major differences between it and other models. They do not allow two tuples with the same value for all nonprobability attributes to be present in a relation. In their representation, certainty about an object is a special case where the probabilities associated with the key value for that object add up to exactly one. The extension of the relational algebra is uni sorted, and the only valid object in the algebra is a relation. Sections 4 and 5 give a more detailed theoretical proof and verification of the extended probabilistic relational algebra. They also introduce the coalescence-PLUS and coalescence-MAX operations on value-equivalent tuples to satisfy the deterministic assumption. In section 6, to satisfy the incomplete distribution of the attributes of an object and the interpretation of the null value, the authors introduce the concepts of conditionalization and the n th moment as related to the selection and natural-joint operations, so that such extended operations can only be applied to matched tuples on non-null attribute values. With this additional extension to the PRM, the authors claim that the closure proof of their model is complete. As part of the summary of their PRM in section 7, the authors indicate that one of the restrictions on the model is that only discrete joint probability distributions are allowed. However, since most business data are collected in representations or in the forms of discrete distributions, and most continuous distributions can be converted to discrete distributions, the restriction is not a severe limitation. Issues that should be explored in future research include storage structure, access path and query optimization, the need to develop a nonprocedural query language, and the belief revision of probabilistic data. The authors are in the process of looking into these and other issues so that a prototype probabilistic database management system can be developed. The paper's 21 references represent a fairly complete sample of related work.