Friday, 20 May 2022

Multivalued Dependencies in DBMS

 

  • Multivalued dependency occurs when two attributes in a table are independent of each other but, both depend on a third attribute.
  • A multivalued dependency consists of at least two attributes that are dependent on a third attribute that's why it always requires at least three attributes

  1. Functional dependencies rule out certain tuples from appearing in a relation.

    If A tex2html_wrap_inline1526 B, then we cannot have two tuples with the same A value but different B values.

  2. Multivalued dependencies do not rule out the existence of certain tuples.

    Instead, they require that other tuples of a certain form be present in the relation.

  3. Let R be a relation schema, and let tex2html_wrap_inline1732 and tex2html_wrap_inline1734 .

    The multivalued dependency

    displaymath1886

    holds on R if in any legal relation r(R), for all pairs of tuples tex2html_wrap_inline1906 and tex2html_wrap_inline1908 in r such that tex2html_wrap_inline1912 , there exist tuples tex2html_wrap_inline1914 and tex2html_wrap_inline1916 in r such that:

      tex2html_wrap_inline1920 
    

    tex2html_wrap_inline1922

    tex2html_wrap_inline1924

    tex2html_wrap_inline1926

    tex2html_wrap_inline1928

 

Theory of Multivalued Dependencies

  1. We will need to compute all the multivalued dependencies that are logically implied by a given set of multivalued dependencies.

    • Let D denote a set of functional and multivalued dependencies.
    • The closure tex2html_wrap_inline2010 of D is the set of all functional and multivalued dependencies logically implied by D.
    • We can compute tex2html_wrap_inline2010 from D using the formal definitions, but it is easier to use a set of inference rules.
  2. The following set of inference rules is sound and complete. The first three rules are Armstrong's axioms from Chapter 5.
    1. Reflexivity rule: if tex2html_wrap_inline1740 is a set of attributes and tex2html_wrap_inline1738 , then tex2html_wrap_inline1730 holds.
    2. Augmentation rule: if tex2html_wrap_inline1730 holds, and tex2html_wrap_inline2028 is a set of attributes, then tex2html_wrap_inline2030 holds.
    3. Transitivity rule: if tex2html_wrap_inline1730 holds, and tex2html_wrap_inline2034 holds, then tex2html_wrap_inline2036 holds.
    4. Complementation rule: if tex2html_wrap_inline1970 holds, then tex2html_wrap_inline2040 holds.
    5. Multivalued augmentation rule: if tex2html_wrap_inline1970 holds, and tex2html_wrap_inline2044 and tex2html_wrap_inline2046 , then tex2html_wrap_inline2048 holds.
    6. Multivalued transitivity rule: if tex2html_wrap_inline1970 holds, and tex2html_wrap_inline2052 holds, then tex2html_wrap_inline2054 holds.
    7. Replication rule: if tex2html_wrap_inline1730 holds, then tex2html_wrap_inline1970 .
    8. Coalescence rule: if tex2html_wrap_inline1970 holds, and tex2html_wrap_inline2062 , and there is a tex2html_wrap_inline2064 such that tex2html_wrap_inline2066 and tex2html_wrap_inline2068 and tex2html_wrap_inline2070 , then tex2html_wrap_inline2036 holds.
  3. An example of multivalued transitivity rule is as follows. tex2html_wrap_inline2074 and tex2html_wrap_inline2076 . Thus we have tex2html_wrap_inline2078 , where tex2html_wrap_inline2080 .

    An example of coalescence rule is as follows. If we have tex2html_wrap_inline2082 , and tex2html_wrap_inline2084 , then we have tex2html_wrap_inline2086 .

  4. Let's do an example:
    • Let R=(A,B,C,G,H,I) be a relation schema.
    • Suppose tex2html_wrap_inline2090 holds.
    • The definition of multivalued dependencies implies that if tex2html_wrap_inline2092 , then there exists tuples tex2html_wrap_inline1914 and tex2html_wrap_inline1916 such that:

        tex2html_wrap_inline2098 
      

      tex2html_wrap_inline2100

      tex2html_wrap_inline2102

      tex2html_wrap_inline2104

      tex2html_wrap_inline2106

    • The complementation rule states that if tex2html_wrap_inline2090 then tex2html_wrap_inline2110 .
    • Tuples tex2html_wrap_inline1914 and tex2html_wrap_inline1916 satisfy tex2html_wrap_inline2110 if we simply change the subscripts.
  5. We can simplify calculating tex2html_wrap_inline2010 , the closure of D by using the following rules, derivable from the previous ones:
    • Multivalued union rule: if tex2html_wrap_inline1970 holds and tex2html_wrap_inline2124 holds, then tex2html_wrap_inline2126 holds.
    • Intersection rule: if tex2html_wrap_inline1970 holds and tex2html_wrap_inline2124 holds, then tex2html_wrap_inline2132 holds.
    • Difference rule: if tex2html_wrap_inline1970 holds and tex2html_wrap_inline2124 holds, then tex2html_wrap_inline2138 holds and tex2html_wrap_inline2054 holds.
  6. An example will help:

    Let R=(A,B,C,G,H,I) with the set of dependencies:

      tex2html_wrap_inline2144 
    

    tex2html_wrap_inline2146

    tex2html_wrap_inline2148

    We list some members of tex2html_wrap_inline2010 :

    • tex2html_wrap_inline2152 : since tex2html_wrap_inline2144 , complementation rule implies that tex2html_wrap_inline2156 , and R - B - A = CGHI.
    • tex2html_wrap_inline2160 : Since tex2html_wrap_inline2144 and tex2html_wrap_inline2146 , multivalued transitivity rule implies that tex2html_wrap_inline2166 .

    • tex2html_wrap_inline2168 : coalescence rule can be applied. tex2html_wrap_inline2146 holds, tex2html_wrap_inline2172 and tex2html_wrap_inline2174 and tex2html_wrap_inline2176 , so we can satisfy the coalescence rule with tex2html_wrap_inline1740 being B, tex2html_wrap_inline1982 being HI, tex2html_wrap_inline2064 being CG, and tex2html_wrap_inline2028 being H. We conclude that tex2html_wrap_inline2168 .

    • tex2html_wrap_inline2196 : now we know that tex2html_wrap_inline2152 and tex2html_wrap_inline2160 . By the difference rule, tex2html_wrap_inline2202 .

Find Us On Facebook

Computer Basics

More

C Programming

More

Java Tutorial

More

Data Structures

More

MS Office

More

Database Management

More
Top