Canonical cover
Database management system
I was revising database management system, but was unable to understand canonical cover with the example my lecturer gave us. So, after watching a few articles and YouTube videos here I am explaining the same example for you. Hope it helps.
Usage:
Suppose we have some functional dependencies and an update happens on data then we should make sure that the existing functional dependencies are not violating, because if it does then the system must roll back consuming more time. This is where canonical cover comes into picture. It has 4 steps to follow:
- Make the RHS of the dependency singleton
- Check for extraneous attributes
- Remove redundancy
- Check for union of functional dependencies if possible
Let us understand this with an example.
Example:
Initial Functional dependencies: F={ AC → G, D →EG, BC →D, CG →BD, ACD →B, CE →AG}
STEP1: Make the RHS singleton
FDS = { AC →G, D →E, D →G, BC →D, CG →B, CG →D, ACD →B, CE →A, CE →G }
STEP2: Check for extraneous attributes
{ D →E, D →G } passed this step as there is only one attribute in LHS
{ ACD →B }
A+ : A
C+ : C
AC+ : ACGD [ AC →AC, AC →G, CG →D]
D+ : DEG
As the AC closure has D, Changes to : { AC →B }
FDS = { AC →G , D →E , D →G , BC →D, CG →B, CG →D, AC →B, CE →A, CE →G}
{ AC →G }
A+ : A
C+ : C
No changes
{ BC →D }
B+ : B
C+ : C
No changes
And similarly no more changes in step-2
STEP3: Check for redundancy
{ D →E, D →G } passed this step
{ AC →G }
AC+ : ACBDEG [ AC →AC, AC →B, BC →D, D →E, D →G]
As AC closure contains G , The functional dependency can be eliminated.
FDS = {D →E, D →G, BC →D, CG →B, CG →D, AC →B, CE →A, CE →G}
{ BC →D }
BC+ : BC [ BC →BC]
No changes
{ CG →B }
CG+ : CGDEAB [CG →CG, CG →D, D →E, CE →A, AC →B]
After changes
FDS = {D →E, D →G, BC →D, CG →D, AC →B, CE →A, CE →G}
And Similarly CEG is also eliminated
FDS = {D →E, D →G, BC →D, CG →D, AC →B, CE →A}
STEP4: Union if needed
{D →E, D →G} can be merged to {D →EG}
FDS = {D →EG, BC →D, CG →D, AC →B, CE →A}
Hence the functional dependency becomes : {DE →G , BC →D , CG →D , AC →B, CE →A }
Tschuss!!
