An extension of conflict-free multivalued dependency sets

Reviewer: Udo Walter Lipeck

The author extends some results of Beeri et al. [1] about characterizations of acyclic database schemes by including Functional Dependencies (FDs). In [1], an acyclic Join Dependency (JD) was shown to be equivalent to a conflict-free set of Multivalued Dependencies (MVDs). Thus, the desirable property of acyclicity can be checked in terms of dependencies typically given in a scheme, namely MVDs. Here, the main theorem says that an “extended conflict-free” set of MVDs and FDs is equivalent to the union of an acycic JD and a set of FDs “compatible” with that JD. A set of MVDs and FDs is called extended conflict-free iff a “degenerate” set of MVDs derived from the given dependencies is conflict-free. Furth, a decomposition into third normalform (with lossless join and preservatio of dependencies) exists for each such scheme. This paper generalizes the theory of [1] on acyclic JDs in the direction of the hypothesis of [2] that “every plausible world . . . can be described by one JD and some FDs.” The new constructions of extended conflict-freedom and compatibility are based upon some insight into how far FDs may interfere with MVDs or JDs. The paper gives only a little motivation and hardly any examples, so the reader should be familiar with [1] in advance in order to appreciate the results. Since two-thirds of the paper consist of detailed proofs, it will mainly appeal to specialists in the field of dependency theory.