Week 11 Normal Forms PDF

Normal Forms CMPS 342 Database Systems Spring 2022 Database Systems 1 Guidelines Measure the quality of a relation schema design by 1. Making sure semantics of attributes is clear...

Normal Forms CMPS 342 Database Systems Spring 2022 Database Systems 1 Guidelines Measure the quality of a relation schema design by 1. Making sure semantics of attributes is clear 2. Reducing the redundant information 3. Reducing the null values 4. Disallowing possibility of spurious tuples Database Systems 2 Functional Dependency A functional dependency (FD) is a form of constraint between two sets of attributes 𝑋 → 𝑌 functionally define The values of 𝑋 functionally define the values of 𝑌 The values of 𝑌 depend on the values of 𝑋 Database Systems 3 Functional Dependency 𝑿 𝒀 Formal Definition 1 AA For any two tuples 𝑡1 and 𝑡2 with 2 BB 𝑡1 𝑋 = 𝑡2 𝑋 ⇒ 𝑡1 𝑌 = 𝑡2 ,𝑌- 1 AA In other words, if two tuples (𝑡1 , 𝑡2 ) agree on 3 BB the 𝑋 attribute value, then they must agree on 4 CC the 𝑌 attribute too. Database Systems 4 Normalization database design technique that organizes tables reduces redundancy Avoids anomalies dependency of data Uses functional dependencies Make sure relations are in high order normal forms Database Systems 5 Normal Forms 4NF BCNF 3NF 2NF 1NF Database Systems 6 First Normal Form (1NF) Each cell of a table should contain 4NF atomic values. BCNF There should be no duplicate 3NF values 2NF All tuple values of an attribute should have the same domain 1NF Database Systems 7 1NF Example Database Systems 8 Second Normal From (2NF) The table should be in the 4NF first normal form. BCNF 3NF Every non-key attribute is 2NF fully functionally dependent on the primary key (no partial dependency) 1NF Database Systems 9 2NF Example Database Systems 10 Third Normal Form (3NF) The table should be in the 4NF second normal form. BCNF 3NF There should not be any non-key dependency for 2NF non-key attributes (no transitive functional 1NF dependency). Database Systems 11 3NF Example Database Systems 12 So Help Me Codd ‘a non-key field must provide a fact about 1NF the key, 2NF the whole key, and 3NF nothing but the key ’ Database Systems 13 So Help Me Codd The Key Atomic Vlues, No Duplicates The Whole Key Full Functional Dependency, No Partial FD Nothing but the Key Only depend on key, No Transitive DP Database Systems 14 Boyce Codd Normal Form (BCNF) The table should be in the 4NF 3rd normal form. BCNF There should not be any 3NF dependency for non-key 2NF attributes All existing dependencies 1NF are based on key attributes Database Systems 15 BCNF Example Database Systems 16 Fourth Normal Form (4NF) The table should be in the 4NF BCNF normal form. BCNF 3NF The table does not contain independent multivalued 2NF facts about an entity (no multivalued FD) 1NF Database Systems 17 4NF Example Database Systems 18 Functional Dependencies FDs allow us to decide whether a database design is correct. Given A → B: Several tuples could have the same A value, and if so, they’ll all have the same B value – redundancy – if A is not a key 𝑋 → 𝑌 functionally define Database Systems 19 Partial Functional Dependency Full functional dependency insures that removal of any attribute from left side means that dependency doesn’t hold Given 𝐴, 𝐵 → 𝐶 𝐴 → 𝐶  partial dependency 𝐵 → 𝐶  partial dependency  Not allowed in 2NF Database Systems 20 Transitive Functional Dependency 𝑋 → 𝑍 and 𝑍 → 𝑌  Not allowed in 3NF Database Systems 21 Multivalued Functional Dependency multiple independent multivalued attributes in a single table 𝑋↠𝑌  Not allowed in 4NF Database Systems 22 Identify Primary Columns Database Systems 23 Decompose to remove redundancy Database Systems 24 Remove Partial Dependencies Database Systems 25 Remove Transitive Dependency Database Systems 26 Decompose Multivalued Dependency Database Systems 27  Unnormalized Schema Sporting Goods Company Selling Baseball, Basketball, and Golf Equipment Customer Customer Product Total Customer Email Mail Mail Product Manufacturer Product Product Line Order Customer Customer Address Subscriptions Catalogs 1 Catalogs 2 Product Manufacturer Address Details Cost Quantity Amount Order Date Total 123 Broadway Dr; Bob Smith [email protected] Baseball, Basketball Basketball Golf Basketball Spaulding 1 Spaulding Drive 29.5 Inch $25 1 $25 8/9/2018 $70 123 Broadway Dr; Louisville 345 Slugger Bob Smith [email protected] Baseball, Basketball Basketball Golf Bat Slugger Avenue 33 Inch $35 1 $35 8/9/2018 $70 123 Broadway Dr; Bob Smith [email protected] Baseball, Basketball Basketball Golf Basketball Spaulding 1 Spaulding Drive 29.5 Inch $23 1 $23 8/12/2018 $23 12 Kellogg Ave; 23 Rawlings Jill Thomas [email protected] Baseball Baseball Softball Rawlings Court 4 Pack $6 2 $12 8/10/2018 $57 12 Kellogg Ave; 23 Rawlings Jill Thomas [email protected] Baseball Baseball Bat Rawlings Court 32 Inch $45 1 $45 8/10/2018 $57 5 Maple Street; 1234 Titleist Bob Smith [email protected] Golf Golf Baseball Golf Balls Titleist Road 1 Dozen $44 2 $88 8/12/2018 $88 5 Maple Street; 1234 Titleist Bob Smith [email protected] Golf Golf Baseball Basketball Titleist Road 1 Dozen $44 2 $88 8/12/2018 $88 https://www.youtube.com/watch?v=l5DCnCzDb8g Database Systems 28 1NF Violation – Domain Customer Customer Address 123 Broadway Dr; Bob Smith [email protected] 12 Kellogg Ave; Jill Thomas [email protected] 5 Maple Street; Bill Smith [email protected] Customer Customer Address Customer Email Address Bob Smith 123 Broadway Dr [email protected] Jill Thomas 12 Kellogg Ave [email protected] Bill Smith 5 Maple Street [email protected] Database Systems 29 1NF Violation – Multivalued Attributes Customer Email Customer Subscriptions Bob Smith Baseball, Basketball Jill Thomas Baseball Bill Smith Golf, Basketball Customer Customer Email Subscriptions Bob Smith Baseball Bob Smith Basketball Jill Thomas Baseball Bill Smith Golf Bill Smith Basketball Database Systems 30 2NF Violation – Partial Dependencies Product Customer Customer Address Product Manufacturer Quantity Order Date Bob Smith 123 Broadway Dr Basketball Spaulding 1 8/9/2018 Bob Smith 123 Broadway Dr Bat Louisville Slugger 2 8/9/2018 Jill Thomas 12 Kellogg Ave Bat Louisville Slugger 1 8/10/2018 Mark Smith 5 Maple Street Golf Balls Titleist 2 8/12/2018 Mark Smith 5 Maple Street Basketball Spaulding 2 8/12/2018 Database Systems 31  Product Customer Customer Address Product Manufacturer Quantity Order Date Bob Smith 123 Broadway Dr Basketball Spaulding 1 8/9/2018 Bob Smith 123 Broadway Dr Bat Louisville Slugger 2 8/9/2018 Jill Thomas 12 Kellogg Ave Bat Louisville Slugger 1 8/10/2018 Mark Smith 5 Maple Street Golf Balls Titleist 2 8/12/2018 Mark Smith 5 Maple Street Basketball Spaulding 2 8/12/2018 Customer Order Customer Product Order Date Quantity Bob Smith Basketball 8/9/2018 1 Bob Smith Bat 8/9/2018 2 Jill Thomas Bat 8/10/2018 1 Mark Smith Golf Balls 8/12/2018 2 Mark Smith Basketball 8/12/2018 2 Customer Table Product Table Customer Customer Address Product Product Manufacturer Bob Smith 123 Broadway Dr Basketball Spaulding Jill Thomas 12 Kellogg Ave Bat Louisville Slugger Mark Smith 5 Maple Street Golf Balls Titleist Database Systems 32 3NF Violation – Transitive Dependency Product Manufacturer Product Product Manufacturer Address Product Details Product Cost Basketball Spaulding 1 Spaulding Drive 29.5 Inch $25 Bat Rawlings 23 Rawlings Court 33 Inch $35 Softball Rawlings 23 Rawlings Court 4 Pack $6 Golf Balls Titleist 1234 Titleist Road 1 Dozen $44 Database Systems 33  Product Manufacturer Product Product Manufacturer Address Product Details Product Cost Basketball Spaulding 1 Spaulding Drive 29.5 Inch $25 Bat Rawlings 23 Rawlings Court 33 Inch $35 Softball Rawlings 23 Rawlings Court 4 Pack $6 Golf Balls Titleist 1234 Titleist Road 1 Dozen $44 Product Manufacturer Table Product Manufacturer Product Manufacturer Address Spaulding 1 Spaulding Drive Rawlings 23 Rawlings Court Titleist 1234 Titleist Road Product Product Manufacturer Product Details Product Cost Basketball Spaulding 29.5 Inch $25 Bat Rawlings 33 Inch $35 Softball Rawlings 4 Pack $6 Golf Balls Titleist 1 Dozen $44 Database Systems 34 4NF Violation – Multivalued FD Customer Email Customer Customer Address Customer Email Address Subscriptions Bob Smith 123 Broadway Dr [email protected] Baseball, Basketball Jill Thomas 12 Kellogg Ave [email protected] Baseball Bill Smith 5 Maple Street [email protected] Golf Customer Email Customer Customer Address Customer Email Address Subscriptions Bob Smith 123 Broadway Dr [email protected] Baseball Bob Smith 123 Broadway Dr [email protected] Basketball Jill Thomas 12 Kellogg Ave [email protected] Baseball Bill Smith 5 Maple Street [email protected] Golf Database Systems 35  Customer Email Customer Customer Address Customer Email Address Subscriptions Bob Smith 123 Broadway Dr [email protected] Baseball Bob Smith 123 Broadway Dr [email protected] Basketball Jill Thomas 12 Kellogg Ave [email protected] Baseball Bill Smith 5 Maple Street [email protected] Golf Customer Customer Address Customer Email Address Bob Smith 123 Broadway Dr [email protected] Jill Thomas 12 Kellogg Ave [email protected] Bill Smith 5 Maple Street [email protected] Customer Customer Email Subscriptions Bob Smith Baseball Bob Smith Basketball Jill Thomas Baseball Bill Smith Golf Database Systems 36  Unnormalized Schema Sporting Goods Company Selling Baseball, Basketball, and Golf Equipment Customer Customer Product Total Customer Email Mail Mail Product Manufacturer Product Product Line Order Customer Customer Address Subscriptions Catalogs 1 Catalogs 2 Product Manufacturer Address Details Cost Quantity Amount Order Date Total 123 Broadway Dr; Bob Smith [email protected] Baseball, Basketball Basketball Golf Basketball Spaulding 1 Spaulding Drive 29.5 Inch $25 1 $25 8/9/2018 $70 123 Broadway Dr; Louisville 345 Slugger Bob Smith [email protected] Baseball, Basketball Basketball Golf Bat Slugger Avenue 33 Inch $35 1 $35 8/9/2018 $70 123 Broadway Dr; Bob Smith [email protected] Baseball, Basketball Basketball Golf Basketball Spaulding 1 Spaulding Drive 29.5 Inch $23 1 $23 8/12/2018 $23 12 Kellogg Ave; 23 Rawlings Jill Thomas [email protected] Baseball Baseball Softball Rawlings Court 4 Pack $6 2 $12 8/10/2018 $57 12 Kellogg Ave; 23 Rawlings Jill Thomas [email protected] Baseball Baseball Bat Rawlings Court 32 Inch $45 1 $45 8/10/2018 $57 5 Maple Street; 1234 Titleist Bob Smith [email protected] Golf Golf Baseball Golf Balls Titleist Road 1 Dozen $44 2 $88 8/12/2018 $88 5 Maple Street; 1234 Titleist Bob Smith [email protected] Golf Golf Baseball Basketball Titleist Road 1 Dozen $44 2 $88 8/12/2018 $88 Identify the primary keys Database Systems 37 Identify the primary keys Add the primary keys if needed Database Systems 38 Add the primary keys if needed Product Customer Customer Manufact Customer Customer Email Mail Mail Product urer Product Product Total Line Customer Order Order ID Customer Customer Address Subscriptions Catalogs 1 Catalogs 2 Product ID Product Manufacturer Address Details Cost Quantity Amount Oder ID Date Total 1 123 Broadway Dr; Basketball- Spaulding bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf SP Basketball Spaulding Drive 29.5 Inch $25 1 $25 1 8/9/2018 $70 345 123 Broadway Dr; Slugger bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf Bat-L Bat Louisville Slugger Avenue 33 Inch $35 1 $35 1 8/9/2018 $70 1 123 Broadway Dr; Basketball- Spaulding bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf SP Basketball Spaulding Drive 29.5 Inch $23 1 $23 3 8/12/2018 $23 23 12 Kellogg Ave; Rawlings jthomas1 Jill Thomas [email protected] Baseball Baseball Softball-R Softball Rawlings Court 4 Pack $6 2 $12 2 8/10/2018 $57 23 12 Kellogg Ave; Rawlings jthomas1 Jill Thomas [email protected] Baseball Baseball BatR Bat Rawlings Court 32 Inch $45 1 $45 2 8/10/2018 $57 1234 5 Maple Street; Titleist bsmith2 Bob Smith [email protected] Golf Golf Baseball Golf Balls-T Golf Balls Titleist Road 1 Dozen $44 2 $88 4 8/12/2018 $88 1234 5 Maple Street; Titleist bsmith2 Bob Smith [email protected] Golf Golf Baseball Basketball-T Basketball Titleist Road 1 Dozen $44 2 $88 4 8/12/2018 $88 Look at Partial FDs Database Systems 39 Decompose the partial FDs Customer Customer ID Product ID Quantity Total Line Amount Oder ID Order Date Order Total Basketball- bsmith1 SP 1 #REF! 1 8/9/2018 $70 bsmith1 Bat-L 1 #REF! 1 8/9/2018 $70 Basketball- bsmith1 SP 1 #REF! 3 8/12/2018 $23 jthomas1 Softball-R 2 #REF! 2 8/10/2018 $57 jthomas1 BatR 1 #REF! 2 8/10/2018 $57 bsmith2 Golf Balls-T 2 #REF! 4 8/12/2018 $88 bsmith2 Basketball-T 2 #REF! 4 8/12/2018 $88 Product Customer Customer Manufact Customer Customer Email Mail Mail Product urer Product Product Total Li ID Customer Customer Address Subscriptions Catalogs 1 Catalogs 2 Product ID Product Manufacturer Address Details Cost Quantity Amoun 1 123 Broadway Dr; Basketball- Spaulding bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf SP Basketball Spaulding Drive 29.5 Inch $25 1 345 123 Broadway Dr; Slugger bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf Bat-L Bat Louisville Slugger Avenue 33 Inch $35 1 123 Broadway Dr; 1 bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf Basketball- Spaulding SP Basketball Spaulding Drive 29.5 Inch $23 1 12 Kellogg Ave; 23 jthomas1 Jill Thomas [email protected] Baseball Baseball Rawlings Database SystemsSoftball-R Softball Rawlings Court 4 Pack $640 2 12 Kellogg Ave; 23 Decompose the partial FDs Customer Customer ID Product ID Quantity Customer Oder ID Oder ID Order Date Order Total Basketball- bsmith1 SP 1 1 1 8/9/2018 $70 bsmith1 Bat-L 1 1 1 8/9/2018 $70 Basketball- 3 8/12/2018 $23 bsmith1 SP 1 3 2 8/10/2018 $57 jthomas1 Softball-R 2 2 2 8/10/2018 $57 jthomas1 BatR 1 2 4 8/12/2018 $88 bsmith2 Golf Balls-T 2 4 4 8/12/2018 $88 bsmith2 Basketball-T 2 4 Product Customer Customer Manufact Customer Customer Email Mail Mail Product urer Product Product Total Li ID Customer Customer Address Subscriptions Catalogs 1 Catalogs 2 Product ID Product Manufacturer Address Details Cost Quantity Amoun 1 123 Broadway Dr; Basketball- Spaulding bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf SP Basketball Spaulding Drive 29.5 Inch $25 1 345 123 Broadway Dr; Slugger bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf Bat-L Bat Louisville Slugger Avenue 33 Inch $35 1 123 Broadway Dr; 1 bsmith1 Bob Smith [email protected] Baseball, Basketball Basketball Golf Basketball- Spaulding SP Basketball Spaulding Drive 29.5 Inch $23 1 12 Kellogg Ave; 23 jthomas1 Jill Thomas [email protected] Baseball Baseball Rawlings Database SystemsSoftball-R Softball Rawlings Court 4 Pack $641 2 12 Kellogg Ave; 23 Decompose the partial FDs Customer Customer ID Product ID Quantity Customer Oder ID Oder ID Order Date Order Total Basketball- bsmith1 SP 1 1 1 8/9/2018 $70 bsmith1 Bat-L 1 1 1 8/9/2018 $70 Basketball- bsmith1 SP 1 3 3 8/12/2018 $23 jthomas1 Softball-R 2 2 2 8/10/2018 $57 jthomas1 BatR 1 2 2 8/10/2018 $57 bsmith2 Golf Balls-T 2 4 4 8/12/2018 $88 bsmith2 Basketball-T 2 4 4 8/12/2018 $88 Customer Product ID Quantity Customer Oder ID Customer Oder ID ID Order Date Order Total Basketball- SP 1 1 1 bsmith1 8/9/2018 $70 Bat-L 1 1 1 bsmith1 8/9/2018 $70 Basketball- SP 1 3 3 bsmith1 8/12/2018 $23 Softball-R 2 2 2 jthomas1 8/10/2018 $57 BatR 1 2 2 jthomas1 8/10/2018 $57 Golf Balls-T 2 4 4 bsmith2 8/12/2018 $88 Basketball-T 2 4 4 bsmith2 8/12/2018 $88 Database Systems 42 Decompose Transitive Dependency Product ID Product Product Manufacturer Product Manufacturer Address Product Details Product Cost Basketball-SP Basketball Spaulding 1 Spaulding Drive 29.5 Inch $25 Bat-L Bat Louisville Slugger 345 Slugger Avenue 33 Inch $35 Basketball-SP Basketball Spaulding 1 Spaulding Drive 29.5 Inch $23 Softball-R Softball Rawlings 23 Rawlings Court 4 Pack $6 BatR Bat Rawlings 23 Rawlings Court 32 Inch $45 Golf Balls-T Golf Balls Titleist 1234 Titleist Road 1 Dozen $44 Basketball-T Basketball Titleist 1234 Titleist Road 1 Dozen $44 Database Systems 43 Remove Duplicates Product ID Product Product Manufacturer Product Details Product Cost Product Manufacturer Product Manufacturer Address Basketball-SP Basketball Spaulding 29.5 Inch $25 Spaulding 1 Spaulding Drive Bat-L Bat Louisville Slugger 33 Inch $35 Louisville Slugger 345 Slugger Avenue Basketball-SP Basketball Spaulding 29.5 Inch $23 Spaulding 1 Spaulding Drive Softball-R Softball Rawlings 4 Pack $6 Rawlings 23 Rawlings Court Rawlings 23 Rawlings Court BatR Bat Rawlings 32 Inch $45 Titleist 1234 Titleist Road Golf Balls-T Golf Balls Titleist 1 Dozen $44 Titleist 1234 Titleist Road Basketball-T Basketball Titleist 1 Dozen $44 Database Systems 44 Remove Duplicates, wrong domains and decompose multivalued attributes Customer ID Customer Customer Address Customer Email Subscriptions Customer Mail Catalogs 1 Customer Mail Catalogs 2 bsmith1 Bob Smith 123 Broadway Dr; [email protected] Baseball, Basketball Basketball Golf bsmith1 Bob Smith 123 Broadway Dr; [email protected] Baseball, Basketball Basketball Golf bsmith1 Bob Smith 123 Broadway Dr; [email protected] Baseball, Basketball Basketball Golf jthomas1 Jill Thomas 12 Kellogg Ave; [email protected] Baseball Baseball jthomas1 Jill Thomas 12 Kellogg Ave; [email protected] Baseball Baseball bsmith2 Bob Smith 5 Maple Street; [email protected] Golf Golf Baseball bsmith2 Bob Smith 5 Maple Street; [email protected] Golf Golf Baseball Database Systems 45 Normalized Customer Table Customer ID Customer Customer Address Customer Email bsmith1 Bob Smith 123 Broadway Dr [email protected] jthomas1 Jill Thomas 12 Kellogg Ave [email protected] bsmith2 Bob Smith 5 Maple Street [email protected] Customer Email Customer ID Subscriptions Customer ID Customer Mail Catalogs bsmith1 Baseball bsmith1 Basketball bsmith1 Basketball jthomas1 Baseball jthomas1 Baseball bsmith2 Golf bsmith2 Golf bsmith1 Golf bsmith2 Baseball Database Systems 46 Normalized Order Table Customer Oder ID Order Date Order Total 1 8/9/2018 $70 1 8/9/2018 $70 3 8/12/2018 $23 2 8/10/2018 $57 2 8/10/2018 $57 4 8/12/2018 $88 4 8/12/2018 $88 Database Systems 47  Normalized Schema Customer Order Lines Customer Orders Product ID Customer Order ID Quantity Customer Order ID Customer ID Order Date Order Total Basketball-SP 1 1 1 bsmith1 8/9/2018 $70 Bat-L 1 1 2 jthomas1 8/10/2018 $57 Basketball-SP 3 1 3 bsmith1 8/12/2018 $23 Softball-R 2 2 4 bsmith2 8/12/2018 $88 Bat-R 2 1 Golf Balls - T 4 2 Basketball - T 4 2 Customers Products Customer ID Customer Customer Address Customer Email Product Product Product ID Product Manufacturer Product Details Cost bsmith1 Bob Smith 123 Broadway Dr [email protected] Basketball-SP Basketball Spaulding 29.5 Inch $25 jthomas1 Jill Thomas 12 Kellogg Ave [email protected] Bat-L Bat Louisville Slugger 33 Inch $35 bsmith2 Bob Smith 5 Maple Street [email protected] Basketball-SP Basketball Spaulding 29.5 Inch $23 Softball-R Softball Rawlings 4 Pack $6 Bat-R Bat Rawlings 32 Inch $45 Golf Balls - T Golf Balls Titleist 1 Dozen $44 Customer Email Subscriptions Customer Mail Catalogs Customer Email Customer Mail Basketball - T Basketball Titleist 1 Dozen $44 Customer ID Subscriptions Customer ID Catalogs bsmith1 Baseball bsmith1 Basketball Product Manufacturer bsmith1 Basketball bsmith1 Golf Product Manufacturer Product Manufacturer Address jthomas1 Baseball jthomas1 Baseball Spaulding 1 Spaulding Drive bsmith2 Golf bsmith2 Golf Louisville Slugger 345 Slugger Avenue bsmith2 Baseball Rawlings 23 Rawlings Court Titleist 1234 Titleist Road Database Systems 48 1NF, 2NF, 3NF, 4NF Normalization To normalize a relation, we must know whether a dependency is good or bad We need to identify the functional dependencies in the relation and Add Primary keys (natural functional dependencies) Decompose Partial functional dependencies Transitive functional dependencies Multivalued functional dependencies Database Systems 49  Finding Functional Dependencies Find all the keys of the relation R Find all the sets of attributes that are functionally dependent on any give set(s) of attributes Given some FDs? Can we infer all other FDs? Database Systems 50 Implied Dependencies Given a set 𝐹 of FDs *𝑓1 , … , 𝑓𝑛 + How can we decide whether FD 𝑔 holds? 𝒇𝟏 Given 𝑭 𝒇𝟐 Does it hold? 𝒈  Use inference rules (Armstrong’s Axioms) Database Systems 51 Armstrong’s Axioms Armstrong’s axioms constitute some proved inference rules Used to infer all functional dependencies on a relational database An inference rule is an assertion Applied on a set of functional dependencies Used to derived other functional dependencies Database Systems 52 IR1: Reflexivity Rule Given set of attributes 𝐴, 𝐵 Does 𝐴, 𝐵 → 𝐴 hold? Does 𝐴, 𝐵 → 𝐵 hold? But, 𝐴 ⊆ *𝐴, 𝐵+ and 𝐵 ⊆ *𝐴, 𝐵+ Given sets of attributes 𝑋 and 𝑌 if 𝑌 ⊆ 𝑋, then 𝑋 → 𝑌  Reflexivity Inference Rule Database Systems 53 IR1: Reflexivity Rule Database Systems 54 IR2: Augmentation Rule Given set of attributes 𝐴, 𝐵, 𝐶 If 𝐴 → 𝐵 holds Does 𝐴, 𝐶 → *𝐵, 𝐶+ hold? Database Systems 55 IR2: Augmentation Rule If 𝑋 → 𝑌, any set attributes 𝐶 added on both sides will lead to that the dependency 𝑋𝐶 → 𝑌𝐶 still holds 𝑋 → 𝑌 will ensure the correct mapping of the tuple values Thus if 𝑋 → 𝑌 then, 𝑋𝐶 → 𝑌𝐶  Augmentation Inference Rule Database Systems 56 IR3: Transitivity Rule Given set of attributes 𝐴, 𝐵, 𝐶 If 𝐴 → 𝐵 holds and 𝐵 → 𝐶 holds Does 𝐴 → 𝐶 hold? Database Systems 57 IR3: Transitivity Rule 𝑋 → 𝑌 if 𝑡1 ,𝑋- = 𝑡2 ,𝑋-, then 𝑡1 𝑌 = 𝑡2 ,𝑌- 𝑌 → 𝑍 if 𝑡1 ,𝑌- = 𝑡2 ,𝑌-, then 𝑡1 𝑍 = 𝑡2 ,𝑍- So, if 𝑡1 ,𝑋- = 𝑡2 ,𝑋-, then 𝑡1 𝑍 = 𝑡2 ,𝑍-  𝑋 → 𝑍 Then, If 𝑋 → 𝑌 and 𝑌 → 𝑍 then, 𝑋 → 𝑍  Transitivity Inference Rule Database Systems 58 IR4: Decomposition Rule Given set of attributes 𝐴, 𝐵, 𝐶 If 𝐴 → *𝐵, 𝐶+ holds Does 𝐴 → 𝐵 hold? What about 𝐴 → 𝐶 If: SSN  {fname,lname} Then also: SSN  fname SSN  lname Database Systems 59 IR4: Decomposition Rule Given set of attributes 𝐴, 𝐵, 𝐶 If 𝐴 → *𝐵, 𝐶+ holds Does 𝐴 → 𝐵 hold? What about 𝐴 → 𝐶 If: SSN  {fname,lname} Then also: SSN  fname SSN  lname Database Systems 60 IR4: Decomposition Rule If 𝑋 → 𝑌𝑍 then, 𝑋 → 𝑌 and 𝑋 → 𝑍  Decomposition Inference Rule Database Systems 61 IR5: Union Rule Decomposition Rule Union Rule If: If: SSN  {fname,lname} SSN  fname SSN  lname Then also: Then also: SSN  fname SSN  lname SSN  {fname,lname} Database Systems 62 IR5: Union Rule If𝑋 → 𝑌 and 𝑋 → 𝑍, then 𝑋 → 𝑌𝑍  Union Inference Rule Database Systems 63 IR6: Pseudotransitivity Rule If𝑋 → 𝑌 and W𝑌 → 𝑍, then 𝑋𝑊 → 𝑍  Pseudotransitivity Inference Rule Can you prove it using previous inference rules? Database Systems 64 IR6: Pseudotransitivity Rule Given 𝑿→𝒀 𝑾𝒀 → 𝒁 Augmentation rule: Give𝑛 𝑋 → 𝑌, 𝑡𝑕𝑒𝑛 𝑋𝑊 → 𝑌𝑊 Transitivity rule: Given 𝑋𝑊 → 𝑌𝑊 and 𝑊𝑌 → 𝑍 Then 𝑿 → 𝒁 Database Systems 65 Armstrong’s Axioms Database Systems 66 Finding Functional Dependencies Given 𝑭 Database Systems 67 Closure Given a set 𝐹 of FDs The closure 𝐹 + is the set of all implied FDs Given 𝑭 𝑪𝒍𝒐𝒔𝒖𝒓𝒆 𝑭+ Database Systems 68 Reading Reference Database Systems 69