View source for Functional Dependency Inference Problem

{{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 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 == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Brute force algorithm (Functional Dependency Inference Problem Dependency Inference Problem)|Brute force algorithm]] || 1967 || $O(n^{2} {2}^n p log p)$ || $O(n2^n)$? || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0166218X92900315 Time]
|-
| [[Schlimmer (Functional Dependency Inference Problem Dependency Inference Problem)|Schlimmer]] || 1993 || $O(n {2}^n p)$ || $O({2}^n)$ || Exact || Deterministic || [https://www.aaai.org/Papers/Workshops/1993/WS-93-02/WS93-02-017.pdf Time]
|-
|}

== Time Complexity Graph == 

[[File:Dependency Inference Problem - Functional Dependency Inference Problem - Time.png|1000px]]

== Space Complexity Graph == 

[[File:Dependency Inference Problem - Functional Dependency Inference Problem - Space.png|1000px]]

== Time-Space Tradeoff == 

[[File:Dependency Inference Problem - Functional Dependency Inference Problem - Pareto Frontier.png|1000px]]

== References/Citation == 

https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0166218X92900315