0
$\begingroup$

Is there an algorithm to test whether the decomposition of relation $R$ into relations $R_1,\dots,R_n$ is dependency-preserving?

In more detail, I am given a relation $R(x_1,\dots,x_m)$ on $m$ variables. I am given a decomposition of $R$ into relations $R_1,\dots,R_n$, where each relation $R_i$ refers to a subset of the variables $\{x_1,\dots,x_m\}$. I am also given a set of functional dependencies $F$ for $R$. I would like to know whether this decomposition is dependency-preserving. Is there an efficient algorithm to answer this question?

Recall the definition of "dependency-preserving" from database theory: the decomposition of $R$ into $R_1,\dots,R_n$ is dependency-preserving if $F^+=G^+$, where $G=G_1 \cup \dots \cup G_n$ and $G_i$ is the restriction of $F$ to the variables of $R_i$ (so $G_i$ is a set of functional dependencies for $R_i$).

$\endgroup$
4
  • $\begingroup$ This is an attempt to write a general reference question that can be useful to other users in the future (something that generalizes beyond any one exercise problem). $\endgroup$
    – D.W.
    Apr 30, 2015 at 23:43
  • $\begingroup$ should I delete my question now? $\endgroup$ Apr 30, 2015 at 23:44
  • $\begingroup$ @amalsom, nope, don't delete your question. It can still be useful to others to help them find a good resource. Thank you for asking! $\endgroup$
    – D.W.
    Apr 30, 2015 at 23:45
  • $\begingroup$ :Question is quite interesting. The algos I can find are not clear. In Navathe's book there is no such reference to this also. Thx. $\endgroup$ Apr 30, 2015 at 23:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.