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. The authors show that this problem is solvable by a brute-force algorithm in ¦](n22nplogp) time for a relation with p rows and n attributes. They show that for fixed n, time ¦[(plogp) is a lower bound. The authors also show that the exponentiality of the time bound with respect to n is unavoidable. They prove this by showing that there are small relations where an exponential number of nontrivial dependencies hold. The authors also prove two exponential lower bounds that hold even for the case where no explicit representation of the dependency set is needed.
