Multivalued Dependency Inference Problem: Difference between revisions
(Created page with "{{DISPLAYTITLE:Multivalued Dependency Inference Problem (Dependency Inference Problem)}} == Description == The multivalued dependency inference problem is to find a cover for the set of multivalued dependencies that hold in a given relation. A multivalued dependency (abbr. MVD), $g$, on a set of attributes $U$ is a statement $g: X \rightarrow \rightarrow Y$, where $X$ and $Y$ are subsets of $U$. Let $Z$ be the complement of the union of $X$ and $Y$ in $U$. A relation...") |
No edit summary |
||
| Line 28: | Line 28: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Time.png|1000px]] | [[File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Space.png|1000px]] | [[File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Pareto Frontier.png|1000px]] | [[File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Pareto Frontier.png|1000px]] | ||
Revision as of 13:04, 15 February 2023
Description
The multivalued dependency inference problem is to find a cover for the set of multivalued dependencies that hold in a given relation.
A multivalued dependency (abbr. MVD), $g$, on a set of attributes $U$ is a statement $g: X \rightarrow \rightarrow Y$, where $X$ and $Y$ are subsets of $U$. Let $Z$ be the complement of the union of $X$ and $Y$ in $U$. A relation $R(U)$ obeys the MVD $g: X \rightarrow \rightarrow Y$ if for every $XZ$-value, $xz$, that appears in $R$, we have $Y_R(xz) = Y_R (x)$. In words, the MVD $g$ is valid in $R$ if the set of $Y$-values that appears in $R$ with a given $x$ appears with every combination of $x$ and $z$ in $R$. Thus, this set is a function of $x$ alone and does not depend on the $Z$-values that appear with $x$. Given $g: X \rightarrow \rightarrow Y$, we say that $g$ is a multivalued dependency from $X$ to $Y$ (in the set $U$). As we do for functional dependencies (FD's), here also we usually omit the name $g$ of the MVD and just write $X \rightarrow \rightarrow Y$.
Related Problems
Related: Functional Dependency Inference Problem
Parameters
No parameters found.
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Räihä; Manilla | 1992 | $O(n^{2} {2}^n p log p)$ | $O(n2^n)$? | Exact | Deterministic | Time |
| Catriel Beeri Ronald Fagin John H. Howard | 1977 | $O({4}^n)$ | Exact | Deterministic | Time |
Time Complexity Graph
Space Complexity Graph
Pareto Frontier Improvements Graph
