Weakly independent database schemes

Abstract

Independent database schemes are best known to have constraints enforced globally by enforcing them locally in individual relations, and therefore are highly desirable in an updates-busy and distributed environment. However, independence excludes all database schemes with interrelational functional dependencies and therefore is too strong a condition. In this paper, a natural generalization of independent schemes along this line, called weakly independent schemes, is defined. A database scheme is weakly independent with respect to a set of embedded functional dependencies if the constraints can be enforced globally by enforcing local as well as interrelational functional dependencies. (a) A characterization of the weak independence and an exponential time test (in the number of functional dependencies) are presented. (b) Two polynomial time conditions are also presented, one is necessary and the other is sufficient for a database scheme to be weakly independent. (c) It is shown that a certain acyclicity of the database scheme implies weak independence. Extension to the case of embedded functional dependencies plus the joir dependency times sign closed R is also considered.