CoderFunda
  • Home
  • About us
    • Contact Us
    • Disclaimer
    • Privacy Policy
    • About us
  • Home
  • Php
  • HTML
  • CSS
  • JavaScript
    • JavaScript
    • Jquery
    • JqueryUI
    • Stock
  • SQL
  • Vue.Js
  • Python
  • Wordpress
  • C++
    • C++
    • C
  • Laravel
    • Laravel
      • Overview
      • Namespaces
      • Middleware
      • Routing
      • Configuration
      • Application Structure
      • Installation
    • Overview
  • DBMS
    • DBMS
      • PL/SQL
      • SQLite
      • MongoDB
      • Cassandra
      • MySQL
      • Oracle
      • CouchDB
      • Neo4j
      • DB2
      • Quiz
    • Overview
  • Entertainment
    • TV Series Update
    • Movie Review
    • Movie Review
  • More
    • Vue. Js
    • Php Question
    • Php Interview Question
    • Laravel Interview Question
    • SQL Interview Question
    • IAS Interview Question
    • PCS Interview Question
    • Technology
    • Other

08 April, 2022

Canonical Cover

 Programing Coderfunda     April 08, 2022     DBMS     No comments   

 

Canonical Cover

In the case of updating the database, the responsibility of the system is to check whether the existing functional dependencies are getting violated during the process of updating. In case of a violation of functional dependencies in the new database state, the rollback of the system must take place.

A canonical cover or irreducible set of functional dependencies FD is a simplified set of FD that has a similar closure as the original set FD.

Extraneous attributes

An attribute of an FD is said to be extraneous if we can remove it without changing the closure of the set of FD.

Example: Given a relational Schema R( A, B, C, D) and set of Function Dependency FD = { B → A, AD → BC, C → ABD }. Find the canonical cover?

Solution: Given FD = { B → A, AD → BC, C → ABD }, now decompose the FD using decomposition rule( Armstrong Axiom ).

  1. B → A
  2. AD → B ( using decomposition inference rule on AD → BC)
  3. AD → C ( using decomposition inference rule on AD → BC)
  4. C → A ( using decomposition inference rule on C → ABD)
  5. C → B ( using decomposition inference rule on C → ABD)
  6. C → D ( using decomposition inference rule on C → ABD)

Now set of FD = { B → A, AD → B, AD → C, C → A, C → B, C → D }

The next step is to find closure of the left side of each of the given FD by including that FD and excluding that FD, if closure in both cases are same then that FD is redundant and we remove that FD from the given set, otherwise if both the closures are different then we do not exclude that FD.

Calculating closure of all FD { B → A, AD → B, AD → C, C → A, C → B, C → D }

1a. Closure B+ = BA using FD = { B → A, AD → B, AD → C, C → A, C → B, C → D }

1b. Closure B+ = B using FD = { AD → B, AD → C, C → A, C → B, C → D }

From 1 a and 1 b, we found that both the Closure( by including B → A and excluding B → A ) are not equivalent, hence FD B → A is important and cannot be removed from the set of FD.

2 a. Closure AD+ = ADBC using FD = { B →A, AD → B, AD → C, C → A, C → B, C → D }

2 b. Closure AD+ = ADCB using FD = { B → A, AD → C, C → A, C → B, C → D }

From 2 a and 2 b, we found that both the Closure (by including AD → B and excluding AD → B) are equivalent, hence FD AD → B is not important and can be removed from the set of FD.

Hence resultant FD = { B → A, AD → C, C → A, C → B, C → D }

3 a. Closure AD+ = ADCB using FD = { B →A, AD → C, C → A, C → B, C → D }

3 b. Closure AD+ = AD using FD = { B → A, C → A, C → B, C → D }

From 3 a and 3 b, we found that both the Closure (by including AD → C and excluding AD → C ) are not equivalent, hence FD AD → C is important and cannot be removed from the set of FD.

Hence resultant FD = { B → A, AD → C, C → A, C → B, C → D }

4 a. Closure C+ = CABD using FD = { B →A, AD → C, C → A, C → B, C → D }

4 b. Closure C+ = CBDA using FD = { B → A, AD → C, C → B, C → D }

From 4 a and 4 b, we found that both the Closure (by including C → A and excluding C → A) are equivalent, hence FD C → A is not important and can be removed from the set of FD.

Hence resultant FD = { B → A, AD → C, C → B, C → D }

5 a. Closure C+ = CBDA using FD = { B →A, AD → C, C → B, C → D }

5 b. Closure C+ = CD using FD = { B → A, AD → C, C → D }

From 5 a and 5 b, we found that both the Closure (by including C → B and excluding C → B) are not equivalent, hence FD C → B is important and cannot be removed from the set of FD.

Hence resultant FD = { B → A, AD → C, C → B, C → D }

6 a. Closure C+ = CDBA using FD = { B →A, AD → C, C → B, C → D }

6 b. Closure C+ = CBA using FD = { B → A, AD → C, C → B }

From 6 a and 6 b, we found that both the Closure( by including C → D and excluding C → D) are not equivalent, hence FD C → D is important and cannot be removed from the set of FD.

Hence resultant FD = { B → A, AD → C, C → B, C → D }

  • Since FD = { B → A, AD → C, C → B, C → D } is the resultant FD, now we have checked the redundancy of the attribute, since the left side of FD AD → C has two attributes, let's check their importance, i.e. whether they both are important or only one.

Closure AD+ = ADCB using FD = { B →A, AD → C, C → B, C → D }

Closure A+ = A using FD = { B →A, AD → C, C → B, C → D }

Closure D+ = D using FD = { B →A, AD → C, C → B, C → D }

Since the closure of AD+, A+, D+ that we found are not all equivalent, hence in FD AD → C, both A and D are important attributes and cannot be removed.

Hence resultant FD = { B → A, AD → C, C → B, C → D } and we can rewrite it as

FD = { B → A, AD → C, C → BD } is Canonical Cover of FD = { B → A, AD → BC, C → ABD }.

Example 2: Given a relational Schema R( W, X, Y, Z) and set of Function Dependency FD = { W → X, Y → X, Z → WXY, WY → Z }. Find the canonical cover?

Solution: Given FD = { W → X, Y → X, Z → WXY, WY → Z }, now decompose the FD using decomposition rule( Armstrong Axiom ).

  1. W → X
  2. Y → X
  3. Z → W ( using decomposition inference rule on Z → WXY )
  4. Z → X ( using decomposition inference rule on Z → WXY )
  5. Z → Y ( using decomposition inference rule on Z → WXY )
  6. WY → Z

Now set of FD = { W → X, Y → X, WY → Z, Z → W, Z → X, Z → Y }

The next step is to find closure of the left side of each of the given FD by including that FD and excluding that FD, if closure in both cases are same then that FD is redundant and we remove that FD from the given set, otherwise if both the closures are different then we do not exclude that FD.

Calculating closure of all FD { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

1 a. Closure W+ = WX using FD = { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

1 b. Closure W+ = W using FD = { Y → X, Z → W, Z → X, Z → Y, WY → Z }

From 1 a and 1 b, we found that both the Closure (by including W → X and excluding W → X ) are not equivalent, hence FD W → X is important and cannot be removed from the set of FD.

Hence resultant FD = { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

2 a. Closure Y+ = YX using FD = { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

2 b. Closure Y+ = Y using FD = { W → X, Z → W, Z → X, Z → Y, WY → Z }

From 2 a and 2 b we found that both the Closure (by including Y → X and excluding Y → X ) are not equivalent, hence FD Y → X is important and cannot be removed from the set of FD.

Hence resultant FD = { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

3 a. Closure Z+ = ZWXY using FD = { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

3 b. Closure Z+ = ZYX using FD = { W → X, Y → X, Z → X, Z → Y, WY → Z }

From 3 a and 3 b, we found that both the Closure (by including Z → W and excluding Z → W ) are not equivalent, hence FD Z → W is important and cannot be removed from the set of FD.

Hence resultant FD = { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

4 a. Closure Z+ = ZXWY using FD = { W → X, Y → X, Z → W, Z → X, Z → Y, WY → Z }

4 b. Closure Z+ = ZWYX using FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

From 4 a and 4 b, we found that both the Closure (by including Z → X and excluding Z → X ) are equivalent, hence FD Z → X is not important and can be removed from the set of FD.

Hence resultant FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

5 a. Closure Z+ = ZYWX using FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

5 b. Closure Z+ = ZWX using FD = { W → X, Y → X, Z → W, WY → Z }

From 5 a and 5 b, we found that both the Closure (by including Z → Y and excluding Z → Y ) are not equivalent, hence FD Z → X is important and cannot be removed from the set of FD.

Hence resultant FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

6 a. Closure WY+ = WYZX using FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

6 b. Closure WY+ = WYX using FD = { W → X, Y → X, Z → W, Z → Y }

From 6 a and 6 b, we found that both the Closure (by including WY → Z and excluding WY → Z) are not equivalent, hence FD WY → Z is important and cannot be removed from the set of FD.

Hence resultant FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

Since FD = { W → X, Y → X, Z → W, Z → Y, WY → Z } is the resultant FD now, we have checked the redundancy of the attribute, since the left side of FD WY → Z has two attributes at its left, let's check their importance, i.e. whether they both are important or only one.

Closure WY+ = WYZX using FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

Closure W+ = WX using FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

Closure Y+ = YX using FD = { W → X, Y → X, Z → W, Z → Y, WY → Z }

Since the closure of WY+, W+, Y+ that we found are not all equivalent, hence in FD WY → Z, both W and Y are important attributes and cannot be removed.

Hence resultant FD = { W → X, Y → X, Z → W, Z → Y, WY → Z } and we can rewrite it as:

FD = { W → X, Y → X, Z → WY, WY → Z } is Canonical Cover of FD = { W → X, Y → X, Z → WXY, WY → Z }.

Example 3: Given a relational Schema R( V, W, X, Y, Z) and set of Function Dependency FD = { V → W, VW → X, Y → VXZ }. Find the canonical cover?

Solution: Given FD = { V → W, VW → X, Y → VXZ }. now decompose the FD using the decomposition rule (Armstrong Axiom).

  1. V → W
  2. VW → X
  3. Y → V ( using decomposition inference rule on Y → VXZ )
  4. Y → X ( using decomposition inference rule on Y → VXZ )
  5. Y → Z ( using decomposition inference rule on Y → VXZ )

Now set of FD = { V → W, VW → X, Y → V, Y → X, Y → Z }.

The next step is to find closure of the left side of each of the given FD by including that FD and excluding that FD, if closure in both cases are same then that FD is redundant and we remove that FD from the given set, otherwise if both the closures are different then we do not exclude that FD.

Calculating closure of all FD { V → W, VW → X, Y → V, Y → X, Y → Z }.

1 a. Closure V+ = VWX using FD = {V → W, VW → X, Y → V, Y → X, Y → Z}

1 b. Closure V+ = V using FD = {VW → X, Y → V, Y → X, Y → Z }

From 1 a and 1 b, we found that both the Closure( by including V → W and excluding V → W ) are not equivalent, hence FD V → W is important and cannot be removed from the set of FD.

Hence resultant FD = { V → W, VW → X, Y → V, Y → X, Y → Z }.

2 a. Closure VW+ = VWX using FD = { V → W, VW → X, Y → V, Y → X, Y → Z }

2 b. Closure VW+ = VW using FD = { V → W, Y → V, Y → X, Y → Z }

From 2 a and 2 b, we found that both the Closure( by including VW → X and excluding VW → X ) are not equivalent, hence FD VW → X is important and cannot be removed from the set of FD.

Hence resultant FD = { V → W, VW → X, Y → V, Y → X, Y → Z }.

3 a. Closure Y+ = YVXZW using FD = { V → W, VW → X, Y → V, Y → X, Y → Z }

3 b. Closure Y+ = YXZ using FD = { V → W, VW → X, Y → X, Y → Z }

From 3 a and 3 b, we found that both the Closure( by including Y → V and excluding Y → V ) are not equivalent, hence FD Y → V is important and cannot be removed from the set of FD.

Hence resultant FD = { V → W, VW → X, Y → V, Y → X, Y → Z }.

4 a. Closure Y+ = YXVZW using FD = { V → W, VW → X, Y → V, Y → X, Y → Z }

4 b. Closure Y+ = YVZWX using FD = { V → W, VW → X, Y → V, Y → Z }

From 4 a and 4 b, we found that both the Closure( by including Y → X and excluding Y → X ) are equivalent, hence FD Y → X is not important and can be removed from the set of FD.

Hence resultant FD = { V → W, VW → X, Y → V, Y → Z }.

5 a. Closure Y+ = YZVWX using FD = { V → W, VW → X, Y → V, Y → Z }

5 b. Closure Y+ = YVWX using FD = { V → W, VW → X, Y → V }

From 5 a and 5 b, we found that both the Closure( by including Y → Z and excluding Y → Z ) are not equivalent, hence FD Y → Z is important and cannot be removed from the set of FD.

Hence resultant FD = { V → W, VW → X, Y → V, Y → Z }.

Since FD = { V → W, VW → X, Y → V, Y → Z } is the resultant FD now, we have checked the redundancy of the attribute, since the left side of FD VW → X has two attributes at its left, let's check their importance, i.e. whether they both are important or only one.

Closure VW+ = VWX using FD = { V → W, VW → X, Y → V, Y → Z }

Closure V+ = VWX using FD = { V → W, VW → X, Y → V, Y → Z }

Closure W+ = W using FD = { V → W, VW → X, Y → V, Y → Z }

Since the closure of VW+, V+, W+ we found that all the Closures of VW and V are equivalent, hence in FD VW → X, W is not at all an important attribute and can be removed.

Hence resultant FD = { V → W, V → X, Y → V, Y → Z } and we can rewrite asit 

FD = { V → WX, Y → VZ } is Canonical Cover of FD = { V → W, VW → X, Y → VXZ }.

CONCLUSION: From the above three examples we conclude that canonical cover / irreducible set of functional dependency follows the following steps, which we need to follow while calculating Canonical Cover.

STEP 1: For a given set of FD, decompose each FD using the decomposition rule (Armstrong Axiom) if the right side of any FD has more than one attribute.

STEP 2: Now make a new set of FD having all decomposed FD.

STEP 3: Find closure of the left side of each of the given FD by including that FD and excluding that FD, if closure in both cases are same then that FD is redundant and we remove that FD from the given set, otherwise if both the closures are different then we do not exclude that FD.

STEP 4: Repeat step 4 till all the FDs in FD set are complete.

STEP 5: After STEP 4, find resultant FD = { B → A, AD → C, C → B, C → D } which are not redundant.

STEP 6: Check redundancy of attribute, by selecting those FDs from FD sets which are having more than one attribute on its left, let's an FD AD → C has two attributes at its left, let's check their importance, i.e. whether they both are important or only one.

STEP 6 a: Find Closure AD+

STEP 6 b: Find Closure A+

STEP 6 c: Find Closure D+

Compare Closure of STEP (6a, 6b, 6c) if the closure of AD+, A+, D+ are not equivalent, hence in FD AD → C, both A and D are important attributes and cannot be removed, otherwise, we remove the redundant attribute.

  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
Email ThisBlogThis!Share to XShare to Facebook

Related Posts:

  • Third Normal Form (3NF) Third Normal Form (3NF)A relation will be in 3NF if it is in 2NF and not contain any transitive partial dependency.3NF is used to reduce the dat… Read More
  • Normalization NormalizationNormalization is the process of organizing the data in the database.Normalization is used to minimize the redundancy from a relatio… Read More
  • First Normal FormFirst Normal Form (1NF)A relation will be 1NF if it contains an atomic value.It states that an attribute of a table cannot hold multiple values. It mu… Read More
  • Second Normal Form (2NF) Second Normal Form (2NF)In the 2NF, relational must be in 1NF.In the second normal form, all non-key attributes are fully functional dependent o… Read More
  • Boyce Codd normal formBoyce Codd normal form (BCNF)BCNF is the advance version of 3NF. It is stricter than 3NF.A table is in BCNF if every functional dependency X → Y, X is… Read More
Newer Post Older Post Home

0 comments:

Post a Comment

Thanks

Meta

Popular Posts

  • Write API Integrations in Laravel and PHP Projects with Saloon
    Write API Integrations in Laravel and PHP Projects with Saloon Saloon  is a Laravel/PHP package that allows you to write your API integratio...
  • Credit card validation in laravel
      Validation rules for credit card using laravel-validation-rules/credit-card package in laravel Install package laravel-validation-rules/cr...
  • iOS 17 Force Screen Rotation not working on iPAD only
    I have followed all the links on Google and StackOverFlow, unfortunately, I could not find any reliable solution Specifically for iPad devic...
  • Fast Excel Package for Laravel
      Fast Excel is a Laravel package for importing and exporting spreadsheets. It provides an elegant wrapper around Spout —a PHP package to ...
  • C++ in Hindi Introduction
    C ++ का परिचय C ++ एक ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग लैंग्वेज है। C ++ को Bjarne Stroustrup द्वारा विकसित किया गया था। C ++ में आने से पह...

Categories

  • Ajax (26)
  • Bootstrap (30)
  • DBMS (42)
  • HTML (12)
  • HTML5 (45)
  • JavaScript (10)
  • Jquery (34)
  • Jquery UI (2)
  • JqueryUI (32)
  • Laravel (1017)
  • Laravel Tutorials (23)
  • Laravel-Question (6)
  • Magento (9)
  • Magento 2 (95)
  • MariaDB (1)
  • MySql Tutorial (2)
  • PHP-Interview-Questions (3)
  • Php Question (13)
  • Python (36)
  • RDBMS (13)
  • SQL Tutorial (79)
  • Vue.js Tutorial (68)
  • Wordpress (150)
  • Wordpress Theme (3)
  • codeigniter (108)
  • oops (4)
  • php (853)

Social Media Links

  • Follow on Twitter
  • Like on Facebook
  • Subscribe on Youtube
  • Follow on Instagram

Pages

  • Home
  • Contact Us
  • Privacy Policy
  • About us

Blog Archive

  • September (100)
  • August (50)
  • July (56)
  • June (46)
  • May (59)
  • April (50)
  • March (60)
  • February (42)
  • January (53)
  • December (58)
  • November (61)
  • October (39)
  • September (36)
  • August (36)
  • July (34)
  • June (34)
  • May (36)
  • April (29)
  • March (82)
  • February (1)
  • January (8)
  • December (14)
  • November (41)
  • October (13)
  • September (5)
  • August (48)
  • July (9)
  • June (6)
  • May (119)
  • April (259)
  • March (122)
  • February (368)
  • January (33)
  • October (2)
  • July (11)
  • June (29)
  • May (25)
  • April (168)
  • March (93)
  • February (60)
  • January (28)
  • December (195)
  • November (24)
  • October (40)
  • September (55)
  • August (6)
  • July (48)
  • May (2)
  • January (2)
  • July (6)
  • June (6)
  • February (17)
  • January (69)
  • December (122)
  • November (56)
  • October (92)
  • September (76)
  • August (6)

  • Failed to install 'cordova-plugin-firebase': CordovaError: Uh oh - 9/21/2024
  • pyspark XPath Query Returns Lists Omitting Missing Values Instead of Including None - 9/20/2024
  • SQL REPL from within Python/Sqlalchemy/Psychopg2 - 9/20/2024
  • MySql Explain with Tobias Petry - 9/20/2024
  • How to combine information from different devices into one common abstract virtual disk? [closed] - 9/20/2024

Laravel News

  • Generate awesome open graph images with Open Graphy - 6/25/2025
  • Defining a Dedicated Query Builder in Laravel 12 With PHP Attributes - 6/25/2025
  • Tracking Cache Activity with Laravel Events - 6/21/2025
  • Building a Task Reminder With Laravel and MongoDB - 6/24/2025
  • Generate Eloquent Models from Database Markup Language Files - 6/24/2025

Copyright © 2025 CoderFunda | Powered by Blogger
Design by Coderfunda | Blogger Theme by Coderfunda | Distributed By Coderfunda