Iztok Savnik, Peter A.Flach
Abstract.
Discovery of multivalued dependencies from database relations is viewed as
a search in a hypothesis space defined according to the
generalisation relationship among multivalued dependencies. Two
algorithms for the discovery of multivalued dependencies from
relations are presented. The top-down algorithm enumerates the
hypotheses from the most general to more specific hypotheses which are
checked on the input relation. The bottom-up algorithm first computes
the invalid multivalued dependencies. Starting with the most general
dependencies, the algorithm iteratively refines the set of
dependencies to conform with each particular invalid dependency. The
implementation of the algorithms is analysed and some empirical results
are presented.