On the complexity of inferring functional dependencies

This work shows that this problem is solvable by a brute-force algorithm in Θ( n 2 2 n p log p ) time for a relation with p rows and n attributes, and proves two exponential lower bounds that hold even for the case where no explicit representation of the dependency set is needed.

Abstract

The dependency inference problem is to find a cover for the set of functional dependencies that hold in a given relation. The problem has applications in relational database design and in query optimization. We show that this problem is solvable by a brute-force algorithm in Θ(n22np log p) time for a relation with p rows and n attributes. We show that for fixed n, time Ω(p log p) is a lower bound. We also show that the exponentially of the time bound with respect to n is unavoidable. We prove this by showing that there are small relations where an exponential number of nontrivial dependencies hold. We also prove two exponential lower bounds that hold even for the case where no explicit representation of the dependency set is needed.