Functional Dependencies & Normalization for Relational DBs Chapter 7 Contents 1 Introduction 2 Functional dependencies 3 Normalization 2 Contents 1 Introduction 2 Functional dependencies 3 Normalization 3 Overview of Database Miniworld Design Process REQUIREMENTS - COLLECTION & ANALYSIS Functional requirements Data requirements DBMS–independent FUNCTIONAL ANALYSIS CONCEPTUAL DESIGN High-level transaction Conceptual schema specification LOGICAL DESIGN (DATA MODEL MAPPING) DBMS–specific APPLICATION PROGRAM Database schema DESIGN PHYSICAL DESIGN TRANSACTION Internal schema IMPLEMENTATION Application program 4 Application Design Database Design Introduction Each relation schema consists of a number of attributes and the relational database schema consists of a number of relation schemas Attributes are grouped to form a relation schema Need some formal measure of why one grouping of attributes into a relation schema may be better than another 5 Introduction “Goodness” measures: Redundant information in tuples Update anomalies: modification, deletion, insertion Reducing the NULL values in tuples Disallowing the possibility of generating spurious tuples 6 Introduction Redundant information in tuples: the attribute values pertaining to a particular department (DNUMBER, DNAME, DMGRSSN) are repeated for every employee who works for that department. 7 Introduction Update anomalies: modification, deletion, insertion Modification As the manager of a dept. changes we have to update many values according to employees working for that dept. Easy to make the DB inconsistent 8 Introduction Deletion: if Borg James E.
leaves, we delete his tuple and lose the existing of dept. 1, the name of dept. 1, and who is the manager of dept. 1 Introduction Insertion: How can we create a department before any employees are assigned to it ?? Introduction Reducing the NULL values in tuples Employees not assigned to any dept.: waste the storage space Other difficulties: aggregation operations (e., COUNT, SUM) and joins 11 Introduction Disallowing the possibility of generating spurious tuples EMP_PROJ (SSN, PNumber, Hours, EName, PName, PLocation) EMP_LOCS (EName, PLocation) EMP_PROJ1 (SSN, PNumber, Hours, PName, PLocation) Generation of invalid and spurious data during JOINS: PLocation is the attribute that relates EMP_LOCS and EMP_PROJ1, and PLocation is neither a primary key nor a foreign key in either EMP_LOCS or EMP_PROJ1 12 Introduction Disallowing the possibility of generating spurious tuples 13 Introduction Disallowing the possibility of generating spurious tuples 14 Introduction “Goodness” measures: Redundant information in tuples Update anomalies: modification, deletion, insertion Reducing the NULL values in tuples Disallowing the possibility of generating spurious tuples Normalization 15 Introduction Normalization helps DB designers determine the best relation schemas A formal framework for analyzing relation schemas based on their keys and on the functional dependencies among their attributes A series of normal form tests that can be carried out on individual relation schemas so that the relational database can be normalized to any desired degree It is based on the concept of normal form 1NF, 2NF, 3NF, BCNF, 4NF, 5NF It is a process which ensures that the data is structured in such a way that attributes are grouped with the PK.
Attributes that do not directly depend on PK may be extracted to form a new relation 16 Introduction There are two important properties of decompositions: 1) non-additive or losslessness of the corresponding join 2) preservation of the functional dependencies Note that property (1) is extremely important and cannot be sacrificed. Property (2) is less stringent and may be sacrificed 17 Contents 1 Introduction 2 Functional dependencies 3 Normalization 18 Functional Dependencies (FDs) Definition of FDs Direct, indirect, partial dependencies Inference Rules for FDs Equivalence of Sets of FDs Minimal Sets of FDs 19 Functional Dependencies (FDs) Functional dependencies (FDs) are used to specify formal measures of the "goodness" of relational designs FDs and keys are used to define normal forms for relations FDs are constraints that are derived from the meaning and interrelationships of the data attributes A set of attributes X functionally determines a set of attributes Y if the value of X determines a unique value for Y XY 20 Functional Dependencies (FDs) X Y holds if whenever two tuples have the same value for X, they must have the same value for Y For any two tuples t1 and t2 in any relation instance r(R): If t1[X]=t2[X], then t1[Y]=t2[Y] X Y in R specifies a constraint on all relation instances r(R) Examples: social security number determines employee name: SSN EName project number determines project name and location: PNumber {PName, PLocation} employee ssn and project number determines the hours per week that the employee works on the project: {SSN, PNumber} Hours 21 Functional Dependencies (FDs) If K is a key of R, then K functionally determines all attributes in R (since we never have two distinct tuples with t1[K]=t2[K]) 22 Functional Dependencies (FDs) Definition of FDs Direct, indirect, partial dependencies Inference Rules for FDs Equivalence of Sets of FDs Minimal Sets of FDs 23 Functional Dependencies (FDs) Direct dependency (fully functional dependency): All attributes in a R must be fully functionally dependent on the primary key (or the PK is a determinant of all attributes in R) SSN {Name, BDate, Address, DNO} EMPLOYEE SSN Name BDate Address DNO 24 Functional Dependencies (FDs) Indirect dependency (transitive dependency): Value of an attribute is not determined directly by the primary key DNO DName EMP_DEPT SSN Name BDate Address DNO DName 25 Functional Dependencies (FDs) Partial dependency Composite determinant - more than one value is required to determine the value of another attribute, the combination of values is called a composite determinant {SSN, PNumber} in EMP_PROJ Partial dependency - if the value of an attribute does not depend on an entire composite determinant, but only part of it, the relationship is known as the partial dependency SSN EName , Pnumber {PName, PLocation} EMP_PROJ SSN PNumber Hours EName PName PLocation 26 Functional Dependencies (FDs) Definition of FD Direct, indirect, partial dependencies Inference Rules for FDs Equivalence of Sets of FDs Minimal Sets of FDs 27 Functional Dependencies (FDs) Given a set of FDs F, we can infer additional FDs that hold whenever the FDs in F hold Armstrong's inference rules: IR1. (Reflexive) If Y ⊆ X, then X Y IR2. (Transitive) If X Y and Y Z, then X Z Functional Dependencies (FDs) Some additional inference rules that are useful: Decomposition: If X -> YZ, then X -> Y and X -> Z Union: If X -> Y and X -> Z, then X -> YZ Psuedotransitivity: If X -> Y and WY -> Z, then WX -> Z The last three inference rules, as well as any other inference rules, can be deduced from IR1, IR2, and IR3 (completeness property) Functional Dependencies (FDs) Closure of a set F of FDs is the set F+ of all FDs that can be inferred from F Closure of a set of attributes X with respect to F is the set X+ of all attributes that are functionally determined by X X+ can be calculated by repeatedly applying IR1, IR2, IR3 using the FDs in F Exercise Consider a relation R(A, B, C, D, E) with the following dependencies F: (1) AB C, (2) CD E, (3) DE B Find {A, B}+ , {A, B, D}+ Find F+ 31 Functional Dependencies (FDs) Definition of FD Direct, indirect, partial dependencies Inference Rules for FDs Equivalence of Sets of FDs Minimal Sets of FDs 32 Functional Dependencies (FDs) Two sets of FDs F and G are equivalent if F+ = G+ Definition: F covers G if G+ ⊆ F+ F and G are equivalent if F covers G and G covers F There is an algorithm for checking equivalence of sets of FDs 33 Functional Dependencies (FDs) A set of FDs is minimal if it satisfies the following conditions: Every dependency in F has a single attribute for its RHS.
We cannot remove any dependency from F and have a set of dependencies that is equivalent to F. We cannot replace any dependency X A in F with a dependency Y A, where Y proper-subset-of X ( Y subset-of X) and still have a set of dependencies that is equivalent to F Functional Dependencies (FDs) Every set of FDs has an equivalent minimal set There can be several equivalent minimal sets There is no simple algorithm for computing a minimal set of FDs that is equivalent to a set F of FDs To synthesize a set of relations, we assume that we start with a set of dependencies that is a minimal set Contents 1 Introduction 2 Functional dependencies 3 Normalization 36 Normalization Normalization: The process of decomposing unsatisfactory "bad" relations by breaking up their attributes into smaller relations Normal form: Using keys and FDs of a relation to certify whether a relation schema is in a particular normal form Normalization is carried out in practice so that the resulting designs are of high quality and meet the desirable properties The database designers need not normalize to the highest possible normal form (3NF, BCNF or 4NF) 37 Normalization Two new concepts: A Prime attribute must be a member of some candidate key A Nonprime attribute is not a prime attribute: it is not a member of any candidate key 38 Normalization 1NF and dependency problems 2NF – solves partial dependency 3NF – solves indirect dependency BCNF – well-normalized relations 39 Normalization First normal form (1NF): there is only one value at the intersection of each row and column of a relation - no set valued attributes in 1NF Disallows composite attributes, multivalued attributes, and nested relations To be part of the formal definition of a relation in the basic (flat) relational model 40 1NF 41 1NF 42 1NF 43 1NF EMP_PROJ (SSN, PNumber, Hours, EName, PName, PLocation) 1. SSN, PNumber Hours 2. PNumber PName, PLocation 44 1NF EMP_PROJ (SSN, PNumber, Hours) EMP (SSN, EName) PROJ (PNumber, PName, PLocation) 1.
SSN, PNUMBER HOURS 2. PNUMBER PNAME, PLOCATION 45 Normalization 1NF and dependency problems 2NF – solves partial dependency 3NF – solves indirect dependency BCNF – well-normalized relations 46 Normalization Second normal form (2NF) - all attributes must be fully functionally dependent on the primary key 2NF solves partial dependency problem in 1NF Method: identify primary keys and group attributes that relate to the key together to form separate new relations 47 2NF 48 2NF Problem with 2NF 49 Normalization 1NF and dependency problems 2NF – solves partial dependency 3NF – solves indirect dependency BCNF – well-normalized relations 50