A Feasibility and Performance Study of Dependency Inference

Abstract

We investigate the feasibility of inferring functional dependencies from an example relation. The problem occurs in the context of automatic database design, when a tool is needed to assist the database designer in the process of specifying logical dependencies. The complexity of the dependency inference problem is inherently exponential. However, algorithms could be developed that perform well when the input relation has certain characteristics. We have implemented and optimized two recently proposed algorithms for dependency inference. An extensive set of experiments is presented, where dependencies were inferred from example relations with different cardinalities, number of attributes, and degree of normalization. We conclude that for practical example relations an adequate implementation of a dependency inference function leads to acceptable interactive response times.