A characterization of multivalued dependencies equivalent to a join dependency

It is known that a join dependency (jd) is equivalent to a set of multivalued dependencies (mvds) if and only if the database schema for the jd is acyclic. Conversely, a set of mvds is equivalent to a jd if and only if the set has a conflict-free cover. The new characterization is as follows: A set of mvds is equivalent to a jd if and only if it has a cover with the subset property, where a set M of mvds is said to have the subset property if, for every pair of mvds \(| \times |(R,S)\), \(| \times |(R',S')\) in M, one of the following is true: \((i) R\subseteq R'\) and S'\(\subseteq S\), (ii) \(R\subseteq S'\) and R'\(\subseteq S\), (iii) \(S\subseteq R'\) and S'\(\subseteq R\), or \((iv) S\subseteq S'\) and R'\(\subseteq R\). The subset property follows naturally from the fact that an acyclic database schema can be represented by a tree, and it is earlier to check for than conflict-freedom. Mvds with the subset property are conflict-free, but the converse is not always true. A polynomial algorithm is also given to construct an equivalent acyclic database schema from a set of mvds with the subset property.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: A characterization of multivalued dependencies equivalent to a join dependency

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q797316)