4NF Decomposition (4NF Decomposition)

From Algorithm Wiki
Jump to navigation Jump to search


4NF Decomposition is the problem of decomposing a relation schema into fourth normal form (4NF).

A relation schema $R^*$ is in fourth normal form (4NF) if, whenever a nontrivial multivalued dependency $X \rightarrow \rightarrow Y$ holds for $R^*$, then so does the functiunal dependency $X \rightarrow A$ for every column name $A$ of $R^*$. Intuitively all dependencies are the result of keys. In particular a 4NF relation schema can have no nontrivial multivalued dependencies that are not functional dependencies.

Related Problems

Subproblem: 4NF Decomposition for Functional and Multivalued Dependency Sets, 4NF Decomposition for Conflict-Free Dependency Sets

Related: 4NF Decomposition for Conflict-Free Dependency Sets


$n$: size of database?

$k$: number of functional dependencies

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Tradu; Mirc 1967 $O({2}^n)$ Exact Deterministic
Xu; Renio 1972 $O({2}^n)$ Exact Deterministic
Derek's Algorithm 1983 $O({2}^n)$ Exact Deterministic
Russell et. al. 1989 $O({2}^n)$ Exact Deterministic
Maxwell 2000 $O({2}^n)$ Exact Deterministic
Derek's + Maxwell 2001 $O({2}^n)$ Exact Deterministic
Naive 1956 $O({2}^n)$ Exact Deterministic
Trino 2004 $O({2}^n)$ Exact Deterministic
Grahne and Räihä 1983 exponential exponential Exact Deterministic Time & Space
Lien 1982 $O(k^{2} n^{2})$ $O(k^{2})$ Exact Deterministic Time
Sciore 1981 poly-time Exact Deterministic Time
Fagin 1977 exponential exponential Exact Deterministic Time & Space

Time Complexity Graph

4NF Decomposition - Time.png

Space Complexity Graph

4NF Decomposition - Space.png

Time-Space Tradeoff

4NF Decomposition - Pareto Frontier.png