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

$n$: number of attributes

$p$: number of tuples/rows/data points

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

References/Citation

https://www.sciencedirect.com/science/article/pii/0166218X92900315