Search code examples
databasedatabase-normalization

Multi-Valued Dependencies?

I am having some trouble understanding Multi-Valued Dependencies. The definition being: A multivalued dependency exists when there are at least 3 attributes (like X,Y and Z) in a relation and for value of X there is a well defined set of values of Y and a well defined set of values of Z. However, the set of values of Y is independent of set Z and vice versa.

Suppose we have a relation R(A,B,C,D,E) that satisfies the MVD's
A →→ B and B →→ D

How does MVD play into A->B and B->D here? Honestly I'm not sure I really understand the definition after looking at example problems.

If R contains the tuples (0,1,2,3,4) and (0,5,6,7,8), what other tuples must 
necessarily be in R? Identify one such tuple in the list below.


     a)     (0,5,2,3,8)
     b)     (0,5,6,3,8)
     c)     (0,5,6,7,4)
     d)     (0,1,6,3,4)

I would have thought AB is 0,1 and 0,5 and BD is 1,3 and 5,7. None of the answers have 0,1,3,5,7.

Solution

  • MVDs (multi-valued dependencies) have nothing to do with "at least 3 attributes". (You seem to be quoting the Wikipedia article but that informal definition is partly wrong and partly unintelligible.) You need to read and think through a clear, precise and correct definition. (Which you were probably given.)

    MVD X ↠ Y mentions two subsets of the set S of all attributes, X & Y. There are lots of ways to define when a MVD holds in a relation but the simplest to state & envisage is probably that the two projections XY and X(S-Y) join to the original relation. Which also mentions a third subset, S-Y. Which is what the (binary) JD (join dependency) {XY, X(S-Y)} says.

    Wikipedia (although that article is a mess):

    • A decomposition of R into (X, Y) and (X, R−Y) is a lossless-join decomposition if and only if X ↠ Y holds in R.

    From this answer:

    MVDs always come in pairs. Suppose MVD X ↠ Y holds in a relation with attributes S, normalized to components XY & X(S-Y). Notice that S-XY is the set of non-X non-Y attributes, and X(S-Y) = X(S-XY). Then there is also an MVD X ↠ S-XY, normalized to components X(S-XY) & X(S-(S-XY)), ie X(S-XY) & XY, ie X(S-Y) & XY. Why? Notice that both MVDs give the same component pair. Ie both MVDs describe the same condition, that S = XY JOIN X(S-XY). So when an MVD holds, that partner holds too. We can write the condition expressed by each of the MVDs using the special explicit & symmetrical notation X ↠ Y | S-XY.

    For R =

    A,B,C,D,E
0,1,2,3,4
0,5,6,7,8
...

    A ↠ B tells us that the following join to R:

    A,B  A,C,D,E
0,1  0,2,3,4
0,5  0,6,7,8
...  ...

    so R has at least

    A,B,C,D,E
0,1,2,3,4
0,1,6,7,8
0,5,2,3,4
0,5,6,7,8

    of which two are given and two are new but not choices.

    B ↠ D tells us that the following join to R:

    B,D  A,B,C,E
1,3  0,1,2,4
5,7  0,5,6,8
...  ...

    so R has at least

    A,B,C,D,E
0,1,2,3,4
0,5,6,7,8

    which we already know.

    So we don't yet know whether any of the choices are in R. But we do now know R is

    A,B,C,D,E
0,1,2,3,4
0,1,6,7,8
0,5,2,3,4
0,5,6,7,8
...

    Repeating, A ↠ B adds no new tuples but B ↠ D now gives this join:

    B,D  A,B,C,E
1,3  0,1,2,4
1,7  0,1,6,8
5,3  0,5,2,4
5,7  0,5,6,8
...  ...

    And one of the tuples in that join is choice b) (0,5,6,3,8).

    The way the question is phrased, they are probably expecting you to use a definition that they will have given you that is like another two in Wikipedia. One says that α ↠ β holds in R when

    • [...] if we denote by (x, y, z) the tuple having values for α, β, R − α − β collectively equal to x, y, z, then whenever the tuples (a, b, c) and (a, d, e) exist in r, the tuples (a, b, e) and (a, d, c) should also exist in r.

    (The only sense in which this gives the "formal" definition "in more simple words" is that this is also a definition. Because this isn't actually paraphrasing it, because this uses R − α − β whereas it uses R − β.)

    By applying this rule to repeatedly generate further tuples for R starting from the given ones, we end up generating b) (0,5,6,3,8) much as we did above.

    PS I would normally suggest that you review the (unsound) reasoning that led you to expect "AB is 0,1 and 0,5 and BD is 1,3 and 5,7" (whatever that means) or "0,1,3,5,7". But the "definition" you give (from Wikipedia) doesn't make any sense. So I suggest that you consider what you were doing with it.