All the attributes that are derivable from dependency.
For example if E -> G and G -> S then we can say that The closure of E is G and S.
We show the closure by this notation: X +
HOW TO COMPUTE THE CLOSURE :
- let Y = X
- whenever there is FD we should do the following:
- V -> W such that
- V is the subset of Y
W -> Y and W minus Y it is not empty, so we add it to Y.
- at the end, Y =X +
EXAMPLE1:
Find the closure of E, when E -> G and G -> S .
- Y = {E}
- when E ->G and if G minus Y is not empty we can add G to Y, therefore we have Y = {E, G}. Then we repeate this for thenext functionality dependencies.
- G minus S is not empty then we add it to Y, we will have Y = {E,G,S}.
EXAMPLE 2
- Lets consider this example
- (P)ilot, (F)light, (D)ate, (T)ime
- In this example the FDs are: F -> T, PDT -> F and FD -> P
- They are all potential keys.
In this case (1 attribute) :
- P + = P
- F + = F, T
- D + = D
- T + = T
and finally with 3 attributes:
- PDT + = PDTF
- EXAMPLE02:
we have : (E)mployee, (T)ool, (P)roject, (H)as, (L)ocation, (S)kill, (R)oom
- Em -> To
- Em -> Pr
- To -> Pr
- EmTo -> H
- SkLo -> Ro
- Ro -> Lo
EmToHT --> EmToHPr
- ToPr + = ToPr
- SkLoRoT = SkLoRo
- But there are 2 problems here :
1.Store the global key
2. to discover what key should be.
- Minimal Cover in this example:
- EmToH
- ToPr
- SkLoRo
Find the minimal cover
- X --> Y
- "X forces Y"
- Notes: some FDs are stronger than others
- H --> G
- H --> GE
- The second is at least as strong as H --> G. It is also going to satisfy the first.
- A --> C
- AB --> C This is more restrictive.
We will see more in details about Minimal cover and its algorithm in the next lecture.