Search

Although the relational model for databases provides a great range of advantages over other data models, it lacks a comprehensive way to handle incomplete and uncertain data. Uncertainty in data values, however, is pervasive in all real-world environments and has received much attention in the literature. Several methods have been proposed for incorporating uncertain data into relational databases. However, the current approaches have many shortcomings and have not established an acceptable extension of the relational model. In this paper, we propose a consistent extension of the relational model. We present a revised relational structure and extend the relational algebra. The extended algebra is shown to be closed, a consistent extension of the conventional relational algebra, and reducible to the latter.

Database relations which possibly contain maybe-tuples and null values of type “value at present unknown” are studied. Maybe-tuples and null values are formally interpreted by our notion of representation , which uses classical notions of predicate logic, elaborates Codd's proposal of maybe-tuples, and adopts Reiter's concept of a closed world. Precise notions of information content and redundancy , associated with our notion of representation, are investigated. Extensions of the relational algebra to relations with maybe-tuples and null values are proposed. Our extensions are essentially Codd's, with some modifications. It is proved that these extensions have natural properties which are formally stated as being adequate and restricted . By the treatment of difference and division, our formal framework can be used even for operations that require “negative information.” Finally, extensions of update operations are discussed.

During the last three or four years several investigators have been exploring “semantic models” for formatted databases. The intent is to capture (in a more or less formal way) more of the meaning of the data so that database design can become more systematic and the database system itself can behave more intelligently. Two major thrusts are clear. (1) the search for meaningful units that are as small as possible—atomic semantics; (2) the search for meaningful units that are larger than the usual n-ary relation—molecular semantics. In this paper we propose extensions to the relational model to support certain atomic and molecular semantics. These extensions represent a synthesis of many ideas from the published work in semantic modeling plus the introduction of new rules for insertion, update, and deletion, as well as new algebraic operators.