The additivity problem for functional dependencies in incomplete relations (Q1920225)

Incomplete relations are relations which contain null values, whose meaning is ``value is at present unknown''. A functional dependency (FD) is weakly satisfied in an incomplete relation if there exists a possible world of this relation in which the FD is satisfied in the standard way. Additivity is the property of equivalence of weak satisfaction on a set of FDs, say \(F\), in an incomplete relation with the individual weak satisfaction of each member of \(F\) in the said relation. It is well known that satisfaction of FDs is not additive. The problem that arises is: under what conditions is weak satisfaction of FDs additive. We solve this problem by introducing a syntactic subclass of FDs, called monodependent FDs, which informally means that for each attribute, say \(A\), there is a unique FD that functionally determines \(A\), and in addition only trivial cycles involving \(A\) arise between any two FDs one of which functionally determines \(A\). We show that weak satisfaction of FDs is additive if and only if the set \(F\) of FDs is monodependent and that monodependence can be checked in time polynomial in the size of \(F\).