Inclusion dependencies and their interaction with functional dependencies

Abstract

Inclusion dependencies, or INDs (which can say, for example, that every manager is an employee) are studied, including their interaction with functional dependencies, or FDs. A simple complete axiomatization for INDs is presented, and the decision problem for INDs is shown to be PSPACE-complete. (The decision problem for INDs is the problem of determining whether or not Σ logically implies a, given a set Σ of INDs and a single IND a). It is shown that finite implication (implication over databases with a finite number of tuples) is the same as unrestricted implications for INDs, although finite implication and unrestricted implication are distinct for FDs and INDs taken together. It is shown that, although there are simple complete axiomatizations for FDs alone and for INDs alone, there is no complete axiomatization for FDs and INDs taken together, in which every rule is k-mary for some fixed k (and in particular, there is no finite complete axiomatization.) Thus, no k-mary axiomatization can fully describe the interaction between FDs and INDs. This is true whether we consider finite implication or unrestricted implication. In the case of finite implication, this result holds, even if no relation scheme has more than two attributes, and if all of the dependencies are unary (a dependency is unary if the left-hand side and right-hand side each contain only one attribute). In the case of unrestricted implication, the result holds, even if no relation scheme has more than three attributes, each FD is unary, and each IND is binary. © 1984.