View source for 4NF Decomposition

{{DISPLAYTITLE:4NF Decomposition (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 == 

No parameters found.

== Table of Algorithms == 

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

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

|-

| [[Tradu; Mirc ( 4NF Decomposition)|Tradu; Mirc]] || 1967 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Xu; Renio ( 4NF Decomposition)|Xu; Renio]] || 1972 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Derek's Algorithm ( 4NF Decomposition)|Derek's Algorithm]] || 1983 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Russell et. al. ( 4NF Decomposition)|Russell et. al.]] || 1989 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Maxwell ( 4NF Decomposition)|Maxwell]] || 2000 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Derek's + Maxwell ( 4NF Decomposition)|Derek's + Maxwell]] || 2001 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Naive ( 4NF Decomposition)|Naive]] || 1956 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Trino ( 4NF Decomposition)|Trino]] || 2004 || $O({2}^n)$ ||  || Exact || Deterministic ||  
|-
| [[Grahne and Räihä (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition)|Grahne and Räihä]] || 1983 || exponential || exponential || Exact || Deterministic || [https://www.vldb.org/conf/1983/P186.PDF Time] & [https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF01934180 Space]
|-
| [[Lien (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition)|Lien]] || 1982 || $O(k^{2} n^{2})$ || $O(k^{2})$ || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/319540.319546 Time]
|-
| [[Sciore (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition)|Sciore]] || 1981 || poly-time ||  || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/582318.582337 Time]
|-
| [[Fagin (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition)|Fagin]] || 1977 || exponential || exponential || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/320557.320571 Time] & [https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF01934180 Space]
|-
|}

== Time Complexity Graph == 

[[File:4NF Decomposition - Time.png|1000px]]

== Space Complexity Graph == 

[[File:4NF Decomposition - Space.png|1000px]]

== Pareto Frontier Improvements Graph == 

[[File:4NF Decomposition - Pareto Frontier.png|1000px]]