Handout 13

Functional Dependencies and Normalization*

What is relational database design?

• The grouping of attributes to form "good" relational schemas

The formal concepts of functional dependencies and normal forms

• 1NF (First Normal Form)
• 2NF (Second Normal Form)
• 3NF (Third Normal Form)
• BCNF (Boyce-Codd Normal Form)

1.1 Semantics of the Relation Attributes

Informally , each tuple should represent one entity or relationship instance.

• Attributes of different entities(EMPLOYEEs, DEPARTMENTs, PROJECTs ) should not be mixed in the same relation.
• Only foreign keys should be used to refer to other entities.

1.2 Redundant information in Tuples And Update Anomalies

Mixing attributes of multiple entities may cause problems

• Information is stored redundantly wasting storage
• Problems with update anomalies:
• Insertion anomalies
• Deletion anomalies
• Modification anomalies

Anomaly Examples

Relational database theory is interested in eliminating update anomalies from a database.

For example,

Student_Activity

SID       Activity       Fee

100       Skiing         200

150       Swimming       50

175       Squash         50

200       Swimming       50

Insertion Anomalies

Assume we would like to add a new activity: Softball costs $25. The problem is that in the above database we cannot add softball until someone signs up for softball. This is called an insertion anomaly.

Deletion Anomalies

Now assume that SID=175 drops out of the university so this row is deleted from the database. The problem is that we have now lost information about squash, also. This is called a deletion anomaly.

Modification Anomalies

Finally, assume that the price of swimming increases to $60. In this case, two tuples must be updated. It is possible to accidentally update only one tuple; then we would have inconsistency in the database. This is called a modification anomaly.

Better Representation

A better representation is:

Student

SID       Activity
100       Skiing
150       Swimming
175       Squash
200       Swimming

ActivityFees

Activity  Fee
Skiing    200
Swimming  50
Squash    50

We can do a natural join to get the original table back, plus we don't have the insertion, deletion and modification anomalies.

1.3 Null Values in Tuples

• Relation should be designed such that their tuples will have a few NULL values if possible
• Attributes that are NULL frequently could be placed in separate relations(with the primary key)

1.4 Spurious Tuples

• Bad designs for a relational database may result in erroneous results for certain JOIN operations
• The "lossless join" property is used to guarantee meaningful results for join operations
• The relations should be designed to satisfy the lossless join condition.

2 Functional Dependencies

• Functional dependencies(FDs) are used to specify formal measures of the "goodness" of relation designs
• FDs and keys are used to define normal forms for the relations
• FDs are constraints that are derived from the meaning and the interrelationships of the data attributes.

2.1 Definition of FD

• A set of attributes X functionally determines a set of attributes Y if the value of X determines a unique value for Y
• Specifies a constraint on all relation instances r(R)
• X -> Y holds if whenever two tuples have the same value for X , they must have the same value for Y
• FDs are derived from the real world constraints of the attributes.

Examples of FD constraints:

• 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 employee works on that project.

{SSN , PNUMBER} -> HOURS

An FD is a property of the attributes in the schema R

The constraint must hold on every relation instance r(R)

3.1 Introduction to Normalization

• Normalization: Process of decomposing unsatisfactory "bad" relations by breaking up their attributes into smaller relations
• Normal Form: Condition using keys and FDs of a relation to certify whether a relation schema is in a particular normal form
• 2NF, 3NF, BCNF based on keys and FDs of a relation schema.
• 4NF based on keys, MVDs; 5NF based on keys, JDs.
• Additional properties may be needed to ensure a good relational design( lossless join, dependency preservation)

3.2 First Normal Form

• Disallows composite attributes, multivalued attributes, and nested relations; attributes whose values for an individual tuple are non-atomic
• Considered to be part of the definition of relation

An Informal definition - First normal form requires that every datum (Table/Row/Column entry) must be "atomic". That is, as far as the database is concerned, it must not be a collection of items. The fact that the datum might have structure in some context outside the database is irrelevant. It can sometimes be tough to decide if a particular database design violate first normal form. Consider a database of literature references. An obvious decision is to have one field to contain the title of the reference. It is likely that you will want to search the database for individual words in that title. Does that mean that this is not an atomic value, because you are interested in parts of the title (words)? Most people would say "no", but why this is true is difficult to justify.

Unlike Second and Higher Normal Forms, which rest on formal analysis of a schema, enforcement of First Normal Form ought to be built in to a DBMS package. When it isn't, the enforcement must come from self-discipline on the part of the Database Designer. In this sense, First Normal Form is similar to the rules that require Primary Keys to be Unique and Not Null, and Secondary Keys to have a non-Null value in the Table to which they refer.

1-NF Example

3.3 Second Normal Form

• Uses the concepts of FDs, primary key

Definition:

• Prime Attribute: attribute that is a member of primary key K
• Full Functional Dependency: A FD Y -> Z , where removal of any attribute from Y means the FD does not hold any more.

Examples:

• {SSN, PNUMBER} -> HOURS is a full FD since neither SSN -> HOURS nor PNUMBER -> HOURS hold
• {SSN, PNUMBER} -> ENAME is not a full FD (it is called a partial dependency) since SSN -> ENAME also holds
• A relation schema R is in second normal form (2NF) if every non-prime attribute A in R is fully functionally dependent on the primary key
• R can be decomposed into 2NF relations via the process of 2NF normalization

An Informal definition - Consider a table with a compound primary key; e.g. a primary key that is made up by a comination of two or more columns. A database is in second normal form if no (non-key) column depends on part of the primary key; that you always need all of the primary key to specify the contents of all other columns.

Example 2-NF

Definition:

• Transitive Functional Dependency: a FD Y -> Z that can be derived from two FDs

Y -> X and X -> Z

Examples:

• SSN -> DMGRSSN is a transitive FD since

  SSN -> DNUMBER and DNUMBER -> DMGRSSN hold

• SSN -> ENAME is non-transitive since there is no set of attributes X where SSN -> X and X -> ENAME
• A relation schema R is in third normal form (3NF) if it is in 2NF and no non-prime attribute A in R is transitively dependent on the primary key
• R can be decomposed into 3NF relations via the process of 3NF normalization

An Informal definition - A database is in the third normal form if no column depends on any non-key column.

Example 3-NF

BCNF ( Boyce-Codd Normal Form)

• A relation schema R is in ( Boyce-Codd Normal Form) BCNF if whenever a FD X -> A holds in R, then X is a superkey of R

Relations are in third normal form and there are no Boyce-Codd dependencies. A Boyce-Codd dependency is where a (part of the) key is dependent on a non-key attribute.

Example - BCNF

Suppose we want to keep track of our inventory based on location and product and we also want to keep track of which salespeople are selling which products and where they are located. Consider the following table:

Is the table in Third Normal Form? Yes, it is. All of the non-key attributes are dependent on the entire primary key. Are there any data anomalies associated with this table?

• All three data anomalies are present. If I want to move salesperson 111 from the North region to the South region I have to make the change in two rows. This is an example of a modification anomaly.
• I cannot add a new salesperson without a product or product without a salesperson. This is an example of an addition anomaly.
• Finally, if I delete salesperson 222 I lose the inventory information for product B1 in the North region.

In order to solve the problems associated with this table we need to break it up. Begin by performing a dependency analysis. This analysis shows the following dependencies:

LOCATION, PRODUCT # -> SALESPERSON, QTY_REMAINING

SALESPERSON -> LOCATION

We therefore break up the table into two tables where every determinant (an attribute that determines the value of another attribute) in the new tables is a candidate key. By doing this we achieve Boyce-Codd Normal Form (BCNF).

Here are the results. Notice that the anomalies have been resolved.

Informal definition - Violations of Fourth Normal Form can be recognized by columns that "don't go together". It adheres to the rules of BNCF plus there are no multivalued dependencies.

Example - 4NF

Suppose we want to keep track of the classes a student takes that satisfy major requirements and elective requirements. We might build the following table:

Are there any problems associated with building a table in this manner? This table might actually work; however, it leaves many null values. These "empty" spaces take up room on our storage media and are therefore not desirable.

In order to eliminate these spaces we need to break up the table. The table above actually represents multiple sets of multivalued dependencies. That is MAJOR and ELECTIVE may have multiple values for every student. By eliminating these multiple sets of multivalued dependencies we can achieve Fourth Normal Form (4NF).

Review the results below. Why do we need to change the primary key? Click here for the answer.

Fifth, Higher, and Domain-Key Normal Forms

In the words of Elmasri and Navathe in "Fundamentals of Database Systems":

The practical utility of normal forms becomes questionable when the constraints on which they are based are hard to understand or to detect by the database designers and users who must discover these constraints.