Database relations with null values (Q1067417)

A new formalism for null values is developed, based on the semantics that a null value conveys no information; that it is less informative then either an ''exists but unknown'' or a ''no value'' null. What results is a theory of ''heterogeneous relations'': relations with tuples over different schemes. The concept is essentially that of \textit{E. Sciore}'s relations with objects [''The universal instance and database design'', Ph. D. Thesis, Princeton University (1980)] although the paper contains results that Sciore's work does not. After outlining previous approaches to null value semantics and their deficiencies, the author motivates his semantics and defines various orderings on the information content of tuples and relations. The key concept is an equivalence class, termed an x-relation, of information- equivalent heterogeneous relations. Boolean operations on x-relations are given, and it is shown how these operations can be realized efficiently through computations on minimal representatives of x-relations. The paper next considers query evaluation in the presence of nulls, introducing selection, join and projection for x-relations, and also a quotient operator that is the basis for defining universal quantification in the presence of incomplete information. The author concludes by showing that the operations defined for x-relations are a consistent extension of relational algebra for total relations and that the extension is maximal in the sense that all operations are defined for all arguments (unlike the standard model in which arguments are constrained to have certain scheme compatibilities).