Yet another paper dealing with null values? Yes and no--the main point of the paper is not so much the null values issue itself, but rather an example of application of first-order logic to databases. In order to make the semantics clear, precise logical specifications are provided of the notions of interest, i.e., of null values and answers to queries. The author deals with only one kind of nulls--“value existing but unknown,” and the only difference between a null value (Skolem constant) and an “ordinary” constant is the absence of (some) unique name axioms for a null value. On the other hand, nulls are “indexed”; i.e., for each new null value, a new distinct name is introduced.
Though the paper under review is (to a great extent) self-contained, the author defines all the necessary notions and provides some motivation. For better understanding and for a very interesting and stimulating discussion of the merits of this proof-theoretic approach, the reader is referred to [1] and [2]. Actually, the reviewed paper is a further development of the ideas set forth in [1], in one of the directions already mentioned there. It appears that the “extended relational theories” developed by Reiter are a very good means for extending the semantics of the “basic” relational model, in particular because they provide the possibility of expressing rather subtle facts not always representable using more traditional and prevailing approaches (including the model-theoretic one). Moreover, the formal semantics of these relational model extensions (including null values) are simple and intuitively correct, and do not use multivalued logics.
The query evaluation algorithm provided in the paper recursively decomposes complex queries into algebraic operations on primitive queries, in particular, stripping off leading typed universal and existential quantifiers. In two of the cases, the decomposition presents problems which may lead to incomplete answers; these difficulties are known from the literature and deal with disjunction and leading typed existential quantifiers. After decomposition, algebraic operators are determined for evaluating primitive queries. The author shows that for some cases (universally quantified conjunctive queries; “positive” queries (without negation); and relational databases without nulls), the query evaluation algorithm is complete.
As the author correctly remarks in his Conclusion, after the abstract specification has been provided for the notions of interest, “the rest was more or less routine” (and consisted mainly of technicalities). It is interesting (and probably fruitful) to compare the use of logic for defining semantics in the database setting with the use of logic in programming (for precise and explicit definition of program semantics, see, e.g., [3]). However, it seems that in the database area (unlike programming), the results still tend to be more theoretical than practical, and more developments are needed--probably in the directions set forth by [1] and [2]--in order to be able to handle “more practical” problems.