Functional Dependencies in Relational Model

Contents Components of Relational Model Functional Dependencies Redundant Relations and Anomalies Normalization 1

Main Components of Relational Model Structure (Tables/ Relations) Manipulation Language (SQL) Integrity Constraints 2

Relation Scheme Map all the Entity Types in ERD to Relational scheme as below: STUDENT(StdtId, StdtName, StdtCity, StdtState, Stdtphone_no) Define the domain and data types in the relational model (domain and data type are interdependent) 3

A Few Mapping Considerations One-to-Many If Minimum cardinality is compulsory then make FK Not Null otherwise set it Null. One-to-One PK of compulsory side is included in the optional side 4

Difference Between ERD and Relational Model s Core Concept Normalization An ERD is a top-down approach of analysing user requirements and data requirement of any organization Normalization is a bottom-up analysis of Relational Data Model In Normalization we analyze association between attributes and based on those analysis group the attribute in tables to form tables and relationships 5

Functional Dependency It is an important concept that describes the relationship among attributes (Maier, 1983) Definition of FD: Describes the relationship between attributes in a relation. For example, if a and B are attributes of relation R, B is functionally dependent on a (denoted A B), if each value of A is associated with exactly one value of B. (A and B may each consist of one or more attributes.) OR For any valid instance of A, the value uniquely determines the value of B Its not mathematical, B cannot be computed from A. It may depend on more than one attribute. 6

Functional Dependency It is the property of semantics of attributes in a relation, it defines how the attribute relate to each other If we know the value of A attribute in any tuple we can find the value of B. A determines the value B Determinant: The attribute on the left hand side of arrow. 7

Functional Dependency - Example staffNo Functionally determines position but opposite is not true, position does not determine staffNo, there may be many staff members working as Managers 8

Functional Dependency - Example Functional dependency that holds for all time:staffNo sName 9

Redundant Relations - Problem A partial dependency exists when there is a functional dependence determinant is only part of the primary key (remember we are assuming there is only one candidate key). For example, if (A, B) (C,D), B C, and (A, B) is the primary key, then the functional dependence B C is a partial dependency because only part of the primary key (B) is needed to determine the value of C. Partial dependencies tend to be rather straightforward and easy to identify. in which the 10

Redundant Relations - Problem Redundant Relations have problems called update anomalies which is classified as Insertion Anomaly Deletion Anomaly Modification Anomaly 11

Redundant Relations - Example We will proceed with this example in defining the concept of anomalies 12

Insertion Anomaly Insertion anomaly has two main types: To insert the name of new staff member, we need to enter the correct, valid and consistent branch number, in case of failure we may have inconsistent data To insert the detail of new branch that has no staff till now, we need to insert NULLs in the staff detail attributes, however, if the staffNO is PK then we cannot enter NULL in the Primary Key field which will prevent us to enter any data for branch. 13

Deletion Anomaly If we delete the record of all the members of a branch for re- recruitment then the record of branch is also lost This is an anomaly, since the branch data must be separately handles 14

Modification Anomaly If we want to change one attribute of any particular branch, we must update all the tuples of staff located at that branch, failure which the data will become inconsistent and it would have different address of branch suppose for different staff 15

Another Example of Redundant Data with Anomalies The database is designed keeping in view all the constraints. A Student can have one major A student may have many courses A single course is taught by only one professor Name Course Phone_no Major Professor Grade Kashif CS-203 1234567Comp Sc Ali A Imtiaz CS-303 5464364Chemistry Javed B Kashif CS-328 1234567Comp Sc Tousef B Naveed CS-303 7654657Physics Adnan A Naveed CS-503 7654657Physics Imran In Kashif CS-492 1234567Comp Sc Atif In Saad CS-379 4575435English Shahzeb C 16

Problem Redundancy Phone_no, Major & Professor teaching course is repeating many times All three anomalies (Insertion, Deletion, Modification) 17

Problem Update Phone_no has to be changed at many places Insertion CS-500 is offered by Prof. Atif, but the information can not be inserted in this table as no student has taken that course so far. 18

Problem Deletion CS-503 delete, the Professor teaching that course will also be deleted 19

Role of KEYS in Normalization Candidate Key: An attribute or combination of attribute that uniquely identify a row in a table. Candidate key also becomes Primary key, however, if a table holds more than one candidate keys, one of them is the primary key while others are called secondary keys. 20

Solutions to Redundancy and Anomalies Normalization, however, consider these facts in mind Lossless Join After joining the relations the resulting relation shall be of original one Dependency Preservation Functional dependency holds 21

Normalization Normalization: A step by step process for producing a set of relations with desirable attributes, given the data requirements of an organization Purpose of Normalization: Minimal number of attributes to support data requirements of organization Attribute with close logical relationship (FD) are found in the same relation Minimal redundancy of attribute, with the exception of FK Advantages of Normalization: Update is achieved with minimal number of operations Reduce Data inconsistency Reduction in the file storage space 22

1st Normal Form Also called 1NF There are no Multi-valued attributes and describes atomic value for each tuple / also called removing the repeating groups A Database is in 1NF iff every relation in the database is in 1NF. Steps for 1NF 1. There are no repeating groups in the relation (thus, there is a single fact at the intersection of each row and column of the table). 2. A primary key has been defined, which uniquely identifies each row in the relation. 23

1st Normal Form - Example 24

1st Normal Form - Example Invoice Table 25

1st Normal Form - Example Select Functional Dependencies and then Primary Key on the basis of organization rules. All possible FDs in given table... Now Look for a suitable primary key OrderID, ProductID is the most suitable PK, as the combination of these keys identify each row uniquely --- But it the table still holds Redundancy and Anomalies 26

2nd Normal Form Based on the Concept of Fully Functional Dependency A functional dependency X removal of any attribute A from X, and the FD doesn t hold anymore. A functional dependency X Y is partial dependency if removal of any attribute A from X, and the FD still holds A relation is said to be in 2NF if it is in 1NF and every non-key attribute is fully functionally dependent on key attribute(s) In other words, the relation is in 1NF and does not hold any 2ndNF is particularly applicable when FD s left hand are composite key, and part of PK, if PK is made up of single attribute 2nd is not applicable Y is fully functional dependency if 27

2nd Normal Form Steps for 2NF 1. Create a new relation for each primary key attribute (or combination of attributes) that is a determinant in a partial dependency. That attribute is the primary key in the new relation. 2. Move the non-key attributes that are dependent on this primary key attribute (or attributes) from the old relation to the new relation. 28

2nd Normal Form - Example 29

2nd Normal Form - Example 30

2nd Normal Form - Example The table is in 1NF Following Partial FD exist in the table. OrderID ProductID is the most suitable Pk for these relations --- But the table still holds Redundancy and Anomalies (Removed in 3NF) 31

2nd Normal Form - Example 32

2nd Normal Form - Example EMPLOYEE EmployeeID EmpSkill EmpWorkPlace Kashif Java Lahore Kashif C# Lahore Haris PHP Karachi Hassan C++ Multan Hassan Perl Multan Hassan Ruby on Rails Multan 33

2nd Normal Form - Example EMPLOYEE_SKILL EmployeeID EmpSkill Kashif Java Kashif C# Haris PHP Hassan C++ Hassan Perl Hassan Ruby on Rails EMPLOYEE_WORKPLACE EmployeeID EmpWorkPlace Kashif Lahore Haris Karachi Hassan Multan 34

3rd Normal Form Transitive Dependency: A functional dependency between Primary Key and other non-key attribute(s) that are dependent on PK via another non-key attribute A relation is said to be in 3NF if it is in 2NF and every non-key attribute is functionally dependent on only Primary Key attribute(s) 35

3rd Normal Form Steps in 3NF 1. For each non-key attribute (or set of attributes) that is a determinant in a relation, create a new relation. That attribute (or set of attributes) becomes the primary key of the new relation. 2. Move all of the attributes that are functionally dependent on the primary key of the new relation from the old to the new relation. 3. Leave the attribute that serves as a primary key in the new relation in the old relation to serve as a foreign key that allows you to associate the two relations. 36

3rd Normal Form - Example 3NF 3NF Transitive Dependency Not in 3NF as this relation has transitive dependency 37

3rd Normal Form - Example 38

3rd Normal Form A non-key attribute is defining another attribute Another Scenario Roll_No Name Department Year Hostel Quaid e Azam Hostel Quaid e Azam Hostel 1Nadeem Physics 1 2Imtiaz Chemistry 1 3Saad Mathematics 2Iqbal Hostel 4Rehan Botany 2Iqbal Hostel 5Mohsin Geography 3New Hostel 6Atif Zoology 3New Hostel Student_Dept ------------------------------------Year_hostel(year, Hostel) 39

BCNF A Relation is in BCNF if it is in 3NF and if every determinant is a candidate key There is a determinant which is not a candidate key OR A relation has more than one candidate keys, if there is only one candidate key then relation is in 3NF and BCNF Candidate keys overlap A stronger form of 3NF Also called 3.5 NF A Stronger Version of 3NF 40

BCNF Steps in BCNF In the first step, the relation is modified so that the determinant in the relation that is not a candidate key becomes a component of the primary key of the revised relation. The attribute that is functionally dependent on that determinant becomes a non-key attribute. This is a legitimate restructuring of the original relation because of the functional dependency. 41

BCNF - Example 1. 2. Rules determines that even if a student May have more than one major , there is Exactly one supervisor for each major, hence, Major is functionally dependent on Advisor, Each advisor advises exactly one major Functional Dependencies in BCNF: SID, Major Advisor, MajGPA Advisor Major 3. However, Advisor is not a candidate key, yet it determines Major Not a transitive dependency, as in the TD a non-key attribute is dependent upon another non-key Attribute, while in this case major is a part of key 42

BCNF - Example The relationship is in 3NF, however, it still has anomalies, Update: Advisor change, Insertion: Charles Advice CS, however, there must be CS student, Deletion: Deletion of SID 123 also delete the Advisor data. 43

BCNF - Example The Advisor which determines the Major is become part of the PK. While Major becomes Non-key, this is a legitimate restructuring. However, This does not solve the problem, as major is fully functionally dependent On Advisor only. This restructured relation has partial dependency. Thus this restructured Relation is in 2NF. 44

BCNF - Example Relation in BCNF 45

BCNF - Another Example Relation with overlapping candidate keys This relation has two candidate keys, {SID, CourseID} and {SName, CourseID} CourseID appears in both candidate keys, hence, candidate keys overlap We cannot enter Course Data untill SID and Sname is entered 46

BCNF - Another Example Solution 1: Solution 2: OR BCNF Relations 47

4th Normal Form A relation is said to be in 4NF if it is in 3NF and BCNF and all the Multi-Valued dependencies (MVD) are removed 48

4th Normal Form Multi-Valued dependencies (MVD) A multi-valued dependency in a Relation, where two sets of attributes are independent of each other. For example, A, B, and C) in a relation, such that for each value of A there is a set of values for B and a set of values for C. However, the set of values for B and C are independent of each other. Represented as. A >-> B A >-> C 49

4th Normal Form MVD X->-> is an assertion that if two tuples of a relation agree on all attribute of X then their components in the set of Y may be swapped and the result will be two tuples that are also in the relation. A multi-valued dependency can be further defined as being trivial or nontrivial. A MVD A >-> B in relation R is defined as being trivial if (a) B is a subset of A OR (b) A U B = R A MVD is defined as being nontrivial if neither (a) nor (b) are satisfied. A trivial MVD does not specify a constraint on a relation; a nontrivial MVD does specify a constraint. 50