Functional Dependency Inference Problem: Difference between revisions
(Created page with "{{DISPLAYTITLE:Functional Dependency Inference Problem (Dependency Inference Problem)}} == Description == The functional dependency inference problem is to find a cover for the set of functional dependencies that hold in a given relation. A functional dependency (abbr. FD), $f$, is a statement $f: X \rightarrow Y$ where $X$ and $Y$ are sets of attributes. If $R(X, Y, \ldots)$ is a relation on a set of attributes that contains $X$ and $Y$, then $R$ obeys the FD $f$ if...") |
No edit summary |
||
| Line 28: | Line 28: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Dependency Inference Problem - Functional Dependency Inference Problem - Time.png|1000px]] | [[File:Dependency Inference Problem - Functional Dependency Inference Problem - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Dependency Inference Problem - Functional Dependency Inference Problem - Space.png|1000px]] | [[File:Dependency Inference Problem - Functional Dependency Inference Problem - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Dependency Inference Problem - Functional Dependency Inference Problem - Pareto Frontier.png|1000px]] | [[File:Dependency Inference Problem - Functional Dependency Inference Problem - Pareto Frontier.png|1000px]] | ||
Revision as of 13:04, 15 February 2023
Description
The functional dependency inference problem is to find a cover for the set of functional dependencies that hold in a given relation.
A functional dependency (abbr. FD), $f$, is a statement $f: X \rightarrow Y$ where $X$ and $Y$ are sets of attributes. If $R(X, Y, \ldots)$ is a relation on a set of attributes that contains $X$ and $Y$, then $R$ obeys the FD $f$ if every two tuples of $R$ which have the same projection on $X$ also have the same projection on $Y$. Given $f: X \rightarrow Y$, we say that $f$ is a functional dependency from $X$ to $Y$, that $Y$ is functionally dependent on $X$ or that $X$ functionally determines $Y$. From the definition it follows that for each pair of sets $X$ and $Y$ there is at most one functional dependency from $X$ to $Y$. Therefore, we usually omit the name of the FD and write $X \rightarrow Y$.
Related Problems
Related: Multivalued Dependency Inference Problem
Parameters
No parameters found.
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Brute force algorithm | 1967 | $O(n^{2} {2}^n p log p)$ | $O(n2^n)$? | Exact | Deterministic | Time |
| Schlimmer | 1993 | $O(n {2}^n p)$ | $O({2}^n)$ | Exact | Deterministic | Time |
Time Complexity Graph
Space Complexity Graph
Pareto Frontier Improvements Graph
References/Citation
https://www.sciencedirect.com/science/article/pii/0166218X92900315