A note on the equivalence of a set of egds to a set of FDs (Q1318738): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| (One intermediate revision by one other user not shown) | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0020-0190(94)90009-4 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2005372857 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the equivalence of an Egd to a set of Fd's / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3668890 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4092988 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3347338 / rank | |||
Normal rank | |||
Latest revision as of 14:22, 22 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the equivalence of a set of egds to a set of FDs |
scientific article |
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
