Page 28 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Unit 2: Database Relational Model

6. Completion: The completion of a finite set of attributes X under a finite set of FDs S, Notes
+
written as X , is the smallest superset of X such that: Y Z S Y X Z X.
The completion of an attribute set can be used to compute if a certain dependency is in the
closure of a set of FDs.
Theorem: Given a set S of FDs X Y S , if and only if Y X

7. Irreducible Cover: An irreducible cover of a set S of FDs is a set T of FDs such that:
+
(a) S = T +
+
(b) there exists U T no such that S = U +
(c) X Y T Y is a singleton set and
(d) X Y T Z X Z Y S

Algorithm to Derive Candidate Keys from Functional Dependencies

INPUT: A set S of FDs that contain only subsets of a header H
OUTPUT: The set C of superkeys that hold as candidate keys in all relation universes over H in
which all FDs in S hold begin

C := ; // found candidate keys
Q := { H }; // superkeys that contain candidate keys

while Q <> do
let K be some element from Q;

Q := Q - { K };
minimal := true;
for each X->Y in S do
K’ := (K - Y) X; // derive new superkey

if K’ K then
minimal := false;
Q := Q { K’ };
end if

end for
if minimal and there is not a subset of K in C then remove all supersets of K from C;
C := C { K };
end if

end while
end

LOVELY PROFESSIONAL UNIVERSITY 21