Need Help in Finding Minimal Keys in Relationship Schemas

Question

Am new to database systems and am looking for help in regards to finding minimal keys in a relationship schema. I hope that those reading this post can perhaps help break down the various questions shown below.
In the following questions, I am required to list all minimal keys valid within a schema as well as list all derivations of functional dependencies that lead to the identification of minimal superkeys.

R(A, B, C, D, E)

i) A -> B, C -> D, E -> A
For this question I am able to discern that:
if A -> B and E -> A then through union rule, A -> BE.
But this alone is not enough as from what I understand, a minimal superkey must cover an entire relationship schema. I am unsure on how I can find the link between C -> D and A -> BE. Am suspecting that union rule have to be used but am not sure on how.

ii) A -> B, B -> CD, C -> E, E -> AC
For this question, I can only discern that:
if A -> B and B -> CD then through transitivity rule, A -> CD

Any help will be appreciated.

Answer 1

i) A -> BE is not right.

Maybe it helps to draw all five letters on a piece of paper and then draw the arrows between them.

If E -> A and A -> B, then in fact E -> AB since you can put your finger on E and then follow the arrows all the way to B. (transitivity, you said it yourself)

How to find the minimal super key?

E is a good guess because from it we get ABE. Now once we get CD we derived the entire schema. Since we have C -> D, we can derive CD from only C.

So, CE gives us all of ABCDE and unless you can find a shorter key then this will be a minimal superkey. (Spoiler: Not possible, CE is also the only minimal superkey)

Answer 2

ii) Through transitivity and union, not only A -> CD but A -> BCD.

You also know that E -> A so through transitivity, E -> ABCDE so E is your key.

C -> E, so C can also be a key.

Others aswell.

Answer 3

For i) May I know in more detail how you connected E with C -> D. To be honest, this was the first time I saw a question that consisted of attributes that were only connected to one another and not to the other attributes.

Is it possible that you break down ii) into more detail as perhaps sharing your thought process in breaking down the question can help me better understand the process.

Answer 4

Sorry for the late reply as I have been busy in the past few days. In the meantime I have been working on the questions myself based on the explanation you have given.

May I check for i), is it possible for AC to be a minimal superkey too?
If A -> E and A -> B then through union rule A -> ABE
Since C -> CD as shown in [3] and A -> ABE then through augmentation axiom AC -> ABCDE.
Therefore, AC can also serve as a minimal superkey as it covers the entire relationship schema.

Answer 5

Wow I'm sorry I completely missed your reply!

Just enumerate all the candidate keys and find the smallest!

For ii) we know that E is a superkey and since it's only one symbol it is minimal.

If you already know the minimal length is 1 then you can just check, by hand: Which attributes can you derive from, say, C?

C gives you E which gives you ABCDE.
B gived you C which gives you ABCDE.
A gives you B which gives you ABCDE.

D alone gives you nothing as there are no rules that look like `D -> x`.

That means we have A, B, C, and E as minimal superkeys.

Answer 6

If you don't know the length of your minimal key just start writing down all possible keys.

I mean if we have a schema like A -> B, C -> D, E -> A we can quickly check by hand that no single symbol gives you the entire schema. So next, there are 20 possible two-symbol combinations so just work through them. If you draw the arrows on a piece of paper you check one combination in like 5 seconds.

And with a bit of practice you can just see what works and what doesn't. Writing down the proof is just mechanical work.

Answer 7

I think drawing a graph with arrow really helps in this case.

This is our dependency graph:

https://i.imgur.com/0Px08p8.png

It quite naturally splits into two components:

https://i.imgur.com/rG15MR8.png

This tells us that we will need to add attributes from both components if we want to derive the whole schema.

Properties E and C are the "most initial" and everything flows away from them:

https://i.imgur.com/R0Gc2pj.png

Therefor CE must be a minimal superkey. Now that's not a proof, but just how I approach the problem.

I can spell it out, university-style, if you want:

I) E -> E (trivial)
II) E -> A (given)
III) A -> B (given)

IV) E -> B (transitivity, II & III)
V) E -> ABE (union, I & II & IV)

VI) C -> C (trivial)
VII) C -> D (given)
VIII) C -> CD (union, VI & VII)

IX) CE -> ABCDE (union, V & VIII)

Hence CE is a superkey, to prove that it is minimal you need to spell out all the other superkeys.

Answer 8

Maybe it's more obvious if you don't pick single letters for attribute names but more concrete examples.

Your schema R = People and Adresses

A = Zip Code
B = City
C = Full Name
D = Last Name
E = Street Name

From the Street Name we can derive the Zip Code, from the Zip Code we can derive the City. From the Full Name we can derive the Last Name.

So, {Full Name, Street Name} is a superkey since we can derive all the other attributes from those.

Answer 9

I encourage you to do ii) yourself, it's the same process. Remember that you can split functional dependencies like B -> CD into B -> C and B -> D.

Answer 10

A -> E is not given, otherwise your argumentation would be correct.

(from E -> A we cannot infer A -> E)

Answer 11

May I know how do you know when you have found all the minimal superkeys? When working on such questions, I often feel that there are still some minimal superkeys that I have not found yet.