A note on the equivalence of a set of egds to a set of FDs (Q1318738)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note on the equivalence of a set of egds to a set of FDs |
scientific article; zbMATH DE number 540882
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the equivalence of a set of egds to a set of FDs |
scientific article; zbMATH DE number 540882 |
Statements
A note on the equivalence of a set of egds to a set of FDs (English)
0 references
5 April 1994
0 references
\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.
0 references
databases
0 references
data dependencies
0 references
analysis of algorithms
0 references
0.9533378
0 references
0.8061192
0 references
0.79403436
0 references
0 references
0 references
