4NF Decomposition

Description

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

Parameters

$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

Space Complexity Graph

Time-Space Tradeoff