4NF Decomposition: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{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 pa...") |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 14: | Line 14: | ||
== Parameters == | == Parameters == | ||
$n$: size of database? | |||
$k$: number of functional dependencies | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 39: | Line 41: | ||
|- | |- | ||
| [[Trino ( 4NF Decomposition)|Trino]] || 2004 || $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/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/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/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/doi/abs/10.1145/320557.320571 Time] & [https://link.springer.com/article/10.1007/BF01934180 Space] | |||
|- | |- | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:4NF Decomposition - Time.png|1000px]] | [[File:4NF Decomposition - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:4NF Decomposition - Space.png|1000px]] | [[File:4NF Decomposition - Space.png|1000px]] | ||
== | == Time-Space Tradeoff == | ||
[[File:4NF Decomposition - Pareto Frontier.png|1000px]] | [[File:4NF Decomposition - Pareto Frontier.png|1000px]] | ||
Latest revision as of 08:22, 10 April 2023
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
