Entity and referential integrity are the most fundamental constraints that
any relational database should satisfy. We re-examine these fundamental con
straints in the context of incomplete relations, which may have null values
of the types "value exists but is unknown" and "value does not exist". We
argue that in practice the restrictions that these constraints impose on th
e occurrences of null values in relations are too strict. We justify a gene
ralisation of the said constraints wherein we use key families, which are c
ollections of attribute sets of a relation schema, rather than keys, and fo
reign key families which are collections of pairs of attribute sets of two
relation schemas, rather than foreign keys. Intuitively, a key family is sa
tisfied in an incomplete relation if each one of its tuples is uniquely ide
ntifiable on the union of the attribute sets of the key family, in all poss
ible worlds of the incomplete relation, and, in addition, is distinguishabl
e from all the other tuples in the incomplete relation by its nonnull value
s on some element in the key family. Our proposal can be viewed as an exten
sion of Thalheim's key set, which only deals with null values of type "valu
e exists but is unknown". The intuition behind the satisfaction of a foreig
n key family in an incomplete database is that each pair (Fi;Ki) of attribu
te sets in the foreign key family takes the foreign key attribute values ov
er Fi of a tuple in one incomplete relation referencing the key attribute v
alues over Ki of a tuple in another incomplete relation. Such referencing i
s defined only in the case when the foreign key attribute values do not hav
e any null values of the type "value does not exist"; we insist that the re
ferencing be defined for at least one such pair. We also investigate some c
ombinatorial properties of key families, and show that they are comparable
to the standard combinatorial properties of keys.