What is a Multivalued Dependency ?
To understand the concept of MVD, let us consider a schema denoted as MPD (Man, Phones, Dog_Like),
| Person : |
|
Meaning of the tuples |
| Man(M) |
Phones(P) |
Dogs_Like(D) |
⇒ |
Man M have phones P, and likes the dogs D. |
| M1 |
P1/P2 |
D1/D2 |
⇒ |
M1 have phones P1 and P2, and likes the dogs D1 and D2. |
| M2 |
P3 |
D2 |
⇒ |
M2 have phones P3, and likes the dog D2. |
| Key : MPD |
There are no non trivial FDs because all attributes are combined forming Candidate Key i.e. MDP. The multivalued dependency is shown by
“→→”. So, in the above relation, two multivalued dependencies exists –
- Man →→ Phones
- Man →→ Dogs_Like
A man’s phone are independent of the dogs they like. But after converting the above relation in Single Valued Attribute, Each of a man’s phones appears with each of the dogs they like in all combinations.
| Man(M) |
Phones(P) |
Dogs_Likes(D) |
| M1 |
P1 |
D1 |
| M1 |
P2 |
D2 |
| M2 |
P3 |
D2 |
| M1 |
P1 |
D2 |
| M1 |
P2 |
D1 |
Some Points to note here about relation Person :
- Some unwanted(shaded) tuples will also exist in the relation while converting it into single valued attributes.
- However, We can see that the relation is in BCNF, and thus we would not consider decomposing if further if we looked only at the FDs that hold over the relation Person.
- The redundancy exists in BCNF relation because of MVD.
Where MVD occurs ?
- If two or more independent relations are kept in a single relation, then Multivalued Dependency is possible.
For example, Let there are two relations :
- Student(SID, Sname) where (SID → Sname)
- Course(CID, Cname) where (CID → Cname),
There is no relation defined between Student and Course.
If we kept them in a single relation named Student_Course, then MVD will exists because of m:n Cardinality.
| Student : |
| SID |
Sname |
| S1 |
A |
| S2 |
B |
|
| Course : |
| CID |
Cname |
| C1 |
C |
| C2 |
B |
|
| Merging using Cross Product –
As Student and Course do not have any relation, So taking
all the possible combinations by using Cross product |
| SID |
Sname |
CID |
Cname |
| S1 |
A |
C1 |
C |
| S1 |
A |
C2 |
B |
| S2 |
B |
C1 |
C |
| S2 |
B |
C2 |
B |
| 2 Multivalued Dependency exists :
1. SID →→ CID
2. SID →→ Cname |
|
- If two or more multivalued attributes exists in a relation, then while converting into single valued attributes, MVD exists. The relation “Person” is such type of example.
Definition of MVD :
Let
R be the relational schema,
X,Y be the attribute sets over
R. A MVD
(X→→Y) exists on a relation
R :
If two tuples
t1 and
t2 exists in
R, such that
t1[X] = t2[Y] then two tuples
t3 and
t4 should also exist in
R with the following properties where
Z = R – {X ∪ Y}:
- t3[X] = t4[X] = t1[X] = t2[X]
- t3[Y] = t1[Y] and t4[Y] = t2[Y]
- t3[Z] = t2[Z] and t4[Z] = t1[Z]
The tuples
t1, t2, t3, t4 are not necessarily distinct.
Inference Rules of MVD (Five Rules)
Three of the additional rules involve only MVDs :
| C- |
Complementation |
: |
If X →→ Y, then
X →→ {R − (X∪Y)} . |
| A- |
Augmentation |
: |
If X →→ Y and W ⊇ Z, then
WX →→ YZ. |
| T- |
Transitivity |
: |
If X →→ Y and Y →→ Z, then
X →→ (Z − Y ). |
The remaining two rules relate FDs and MVDs :
- Replication : If X → Y, then X →→ Y but the reverse is not true.
- Coalescence : If X →→ Y and there is a W such that W ∩ Y is empty, W → Z, and Y ⊇ Z, then X → Z.
Trivial and Non Trivial MVD :
A MVD
X →→ Y in
R is called a trivial MVD is
- Y is a subset of X (X ⊇ Y) or
- X ∪ Y = R. Otherwise, it is a non trivial MVD and we have to repeat values redundantly in the tuples.
Removal of MVD :
Solution : Fourth Normal Form (4NF) – Click for removal of MVD.]]>