Complexity of finding minimal cover of FDs
It seems like this problem may be known as the dependency inference problem, as described in this extended abstract of the paper "Dependency Inference" by Mannila and Raiha in VLDB '87:


  Given a relation $r$, find a set of functional dependencies that logically determines all the functional dependencies holding in $r$.


Unfortunately, it seems that this problem is intractably super-polynomial. According to the same extended abstract:


  Theorem 1. For each $n$ there exists a relation over $R$ such that
  $n = |R|$, $|r| = O(n)$, and each cover of $dep(r)$ has $\Omega(2^{n/2})$ dependencies.


In other words, you cannot guarantee that the minimal cover is sub-exponential in the size of the input.

EDIT: However, the asker is asking whether or not an output-polynomial algorithm exists (i.e.: an algorithm that runs in time polynomial in the size of the input and output). The nearest reference I can find is in the paper "Identifying the Minimal Transversals of a Hypergraph and Related Problems", SIAM J. Computing, 1995 (24) by Eiter and Gottlob. 
They first define problems AP1 and AP2 where AP2 is the dependency inference problem. Then, they state the following:


  Note that problems AP1 and AP2, which are search problems in terms of complexity theory, are solvable by algorithms in output-polynomial time only if the following decision problem, which we call FD-RELATION EQUIVALENCE, is in P:
  
  
  Problem: FD-RELATION EQUIVALENCE
  Instance: A relation $R$ and a set $F$ of FD.
  Question: Does $F_R = F^+$ hold ?
  
  
  FD-RELATION EQUIVALENCE is in co-NP, but there is neither a polynomial time algorithm known for this problem nor is it proved co-NP-complete.