# How can I prove / disprove If A ↠ BC and A → B then A → C

/ From GATE 2007 IT:

Consider the following implications relating to functional and multi valued dependencies given below, which may or may not be correct.

``````A) If A ↠ B and A ↠ C then A → BC
B) If A → B and A → C then A ↠ BC
C) If A ↠ BC and A → B then A → C
D) If A → BC and A → B then A ↠ C
``````

Exactly how many of the above implications are valid?

A) 0 B) 1 C) 2 D) 3

I've just studied 4th Normal Form & Multi Valued Dependencies & I'm struggling to apply inference rules for multi Valued dependencies.

I tried:

A) `If A ↠ B and A ↠ C then A → BC`. This is incorrect. It is very obvious to see.

B) `If A → B and A → C then A ↠ BC`. This can be proved by using Augmentation rule of FD. A ->B & A-> C. Then we get A->BC. Using Replication rule we get ↠ BC.

D) `If A → BC and A → B then A ↠ C`. This is true, because A->BC. From which we can get A->C. From which using Replication rule we can get A ↠ C.

C) `If A ↠ BC and A → B then A → C`. Here using Coalescence rule I'm getting A->B back. I'm not able to prove/disprove A → C.

2. What does it means to have a multi valued dependency on two attributes like A ↠ BC? All examples I've seen in books are like Employee ↠ Project | Dependent, where Employee simultaneously determines two attributes. So we end up storing duplicated. But I have never encountered a multi valued dependency with two attributes on the right hand side. Please give an example of such a dependency.

• If you came across a design with edept(e,dept) "employee e works in department dept" and edepn(e,depn) "employee e has dependent depn" you would never use etn(e,dept,depn) "employee e works in department dept and has dependent depn" instead because the originals are independent and etn = edept * edepn. In other words join dependencies are so intuitively obvious that we avoid them, and that's why we don't come across them. If we understand the predicates. – philipxy Dec 11 '15 at 11:09

A,B and C are sets of attributes.

All examples I've seen in books are like Employee ↠ Project | Dependent, where Employee simultaneously determines two attributes.

A ↠ B | C is a special notation different from A ↠ BC. It's useful because MVDs always come in pairs. It says that both A ↠ B and A ↠ C hold. This implies that the relation equals AB JOIN AC. Ie the relation satisfies join dependency *{AB,AC}.

1. What does it means to have a multi valued dependency on two attributes like A ↠ BC?

Please give an example of such a dependency.

Just think of values for subrows the way you would think of values for one attribute. Suppose {W} ↠ {X}. Then whenever W appears it's with all of some set of X values. Suppose each X has a numerator N and denominator D. Then we could have a relation {W} ↠ {N,D}. Whenever W appears it's with all of some set of < N, D > subrow values.

C) If A ↠ BC and A → B then A → C. Here using Coalescence rule I'm getting A->B back. I'm not able to prove/disprove A → C.

Hint: In my last paragraph if {W} → {N} then the variation must come from D.

Hint: If you are permitted to prove by counterexample then it's good to try to disprove things via guessing at one or more trivial examples. Eg with {W} ↠ {N,D} and {W} → {N} (A={W}, B={N}, C={D}):

``````  V   W   N   D
=================
| v | w | n | 1 |
-----------------
| v | w | n | 2 |
-----------------
``````
• I can only suggest that you memorize/practise the syllabus tested on your exam(s). In practice MVDs are not particularly important. What matters is FDs and JDs. An FD "is" a functional MVD and an MVD "is" a binary & completely axiomatized JD. – philipxy Dec 12 '15 at 8:54