Week 8. Functional Dependencies and Normalisation 1

Informal Design Guidelines

We want to develop measures for quality in database design, such as why is one grouping of attributes better than another.

There are two levels of relational schemas: logical “user view” and storage “base relation” level; we are mainly concerned with base relations.

1. Semantics of Relation Attributes

Semantics: how to interpret the attribute values stored in a tuple of the relation, i.e. how the attribute values in a tuple relate to one another.

The ease with which we can explain relational attributes is an informal measure of relation design quality.

Guideline 1: informally, each tuple in a relation should represent one entity or relationship instance.

• attributes of different entities should not be mixed in the same relation
• only foreign keys should be used to refer to other entities
• entity and relationship attributes should be kept apart

2. Redundant Information in Tuples and Update Anomalies

When information is stored redundantly:

• we waste storage
• we cause problems with update anomalies (insertion, deletion, modification)

Anomalies may occur on:

• Insertion: we may have consistency problems; consider the relation: EMP_PROJ (Emp#, Proj#, Hours Ename, Pname, Plocation) We cannot insert a new project unless an employee is assigned to it, but conversely we cannot insert an employee unless they are assigned to a project.
• Deletion: we may lose data; consider the relation: EMP_PROJ (Emp#, Proj#, Hours Ename, Pname, Plocation) When a project is deleted, it will result in deleting all the employees who work on the project. Alternatively, if a sole employee is deleted then the project would be too.
• Update: inconsistencies may be introduced; consider the relation: EMP_PROJ (Emp#, Proj#, Hours Ename, Pname, Plocation) Changing the name of project number P1 (e.g from “Billing” to “Customer-Accounting”) may cause this update to be made for all 100 employees working on project P1.

Guideline 2: Design a schema that does not suffer from these anomalies. If there are any anomalies present, then note them so that applications are made to take them into account.

3. Null Values in Tuples

When grouping attributes in an enlarged relation:

• we may end up with many nulls
• we may waste storage
• can introduce problems in understanding meanings of attributes
• problems with aggregate functions

Typical reasons for using null include:

• attribute is not applicable or invalid
• attribute value is unknown
• value is known to exists but unavailable

Guideline 3: Relations should be designed such their tuples will have as few NULL values as possible. Attributes that are NULL frequently could be placed in separate relations with the primary key.

4. Spurious Tuples

Bad designs for a relational database may result in erroneous results for certain JOIN operations.

Guideline 4: Design relation schemas that can be joined with equality conditions on attributes that are either primary or foreign keys in a way that guarantees that no spurious tuples will be generated. Avoid relations that contain matching attributes that are not (foreign key, primary key) combinations, as joining on such attributes will produce spurious tuples.

Functional Dependencies

Functional Dependencies (FDs) are used to specify formal measures of how good a relational database design is. Keys are used to define normal forms for relations. Constraints are derived from the meaning and inter-relationships 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$.”

Functional Dependency

A functional dependency between attributes $x$ and $y$ of relation $R$:

• $x\to y$ if whenever two tuples have the same value for $x$, they must have the same value for $y$
• for any two tuples $t_1$ and $t_2$ in any relation instance $r(R):$ if $t_1[x]=t_2[x]$ then we also know that $t_1[y]=t_2[y]$.
• $x\to y$ specifies a constraint on all relational instances $r(R)$.

Examples:

• Social security number determines employee name; $\text{SSN}\to \text{ENAME}$.
• Project number determines project name + location: $\text{PNO}\to \{\text{PNAME},\text{PLOC}\}$.
• Employee SSN and project number determine the hours per week that the employee works on the project: $\{\text{SSN},\text{PNO}\}\to \text{HOURS}$.

Link to original

Functional dependencies are a property of the meaning of data and hold at all times.

Inference Rules for FDs

Armstrong's Inference Rules

Given a set of FDs $F$, we can infer additional FDs that hold whenever the FDs in $F$ hold. Armstrong’s inference rules:

1. (reflexive) if $y$ is a subset of $x$, then $x\to y$
2. (augmentation) if $x\to y$, then $xz\to yz$
3. (transitive) if $x\to y$ and $y\to z$, then $x\to z$

All 3 rules form a sound and complete set of inference rules.

Link to original