A note on the equivalence of a set of egds to a set of FDs (Q1318738): Difference between revisions

\textit{M. H. Graham} and \textit{K. Wang} [J. Assoc. Comput. Math. 37, No. 3, 474-490 (1990; Zbl 0699.68117)] have shown that the question ``Is a given equality-generating dependency (egd) equivalent to a set of functional dependencies (FDs)?'' can be decided in polynomial time. The complexity of deciding whether a given set of egds is equivalent to a set of FDs was stated as an open problem. In this paper, the authors settle this question by giving a polynomial time algorithm for the more general problem.