Null Values in Deductive Databases

A particular kind of incomplete information, called null values, often emerges in relational database applications. These represent the information "entity exists but value at present unknown". For example, if we know that Joe has a father but we do not know who he is, then Joe's father can be represented by a null value, say x, in a father-son relation. If we further know that D is the set of all male names, then we know that Joe's father must be one of them, i.e., x is a member of D.

A null value could also result from a view update to a relational database. For instance, in a father-son database, we might have a view definition that models the gradfather-grandson relation, where X is Y's grandfather if there is some Z in the father-son database such that X is Z's father and Z is Y's father. Suppose we want to update the database with the information that John is Jake's grandfather, i.e., X=John and Y=Jake in the above schema, and we do not know who Z is, then we could record this fact as two new tuples, (John, x') and (x', Jake), in the database. The first tuple states that John is the father of some unknown person, represented by x', and the second states that this same unknown person is Jake's father.

In addition, if the database contains a fact such as George is Albert's father, then we would like to answer the question "Are Albert and Jake brothers?" with the reply "Yes, provided the unknown person x' is George".

We achieve this by introducing null values into a more general context, namely, logic programs and deductive databases, which, in the simplest form, can be thought of as relational databases with recursive views.


Papers available on-line: