Functional dependence describes a relationship between attributes of a relation. If the attribute Y is functionally dependent on X (X Y) it holds that for every pair of tuples with attributes X and Y, if the X values are equal then the Y values must also be equal.

For example consider a relation with the attributes PostalCode, City, and Province. If PostalCode City, Province, then for all tuples in the relation, if they have equal PostalCode values, they must have the same City and Province.

The symbol can be read as determines. For example X Y can be read as either X functionally determines Y or X determines Y.

Functional dependence can indicate to us that we're storing redundant data and can help us decompose relations without losing information.

Deriving Additional Functional Dependences

Given a set of functional dependences for a relation we can derive additional functional dependences through the following methods:

Axioms

The following axioms (known as Armstrong's Axioms) are sound and complete — they can derive all and only the functional dependencies that are logically implied by a given set. A set of axioms can be used to transform functional dependences

1. Reflexivity: If Y X, then X Y (ie. City, Major City).
2. Augmentation: If X Y, then X, Z Y, Z for any Z (ie.SID City, then SID, Major City, Major).
3. Transivity: If X Y and Y Z, then X Z (ie. SID City and City AreaCode, then SID AreaCode)

These axioms can then be used to derive a few additional rules for ease of use

1. Union: If X Y, and X Z then X Y, Z (eg. SID AreaCode and SID City, then SID AreaCode, City)
2. Decomposition: If X Y, Z then X Y and X Z (eg. SID AreaCode, City then SID AreaCode and SID City)

Closure Method

Alternatively we can use the "closure method", given a set of attributes X we denote the closure of it as X. If X is a super key X contains all attributes of the schema.

The algorithm is expressed as

Let Closure = X Until Closure doesn't change do if a, ..., a C is a functional dependence and {a, ..., } Closure then add C to Closure

Example

Consider the schema SupplierPart(supplierName, city, status, partNumber, partName, quantity) and the functional dependences

• supplierName city
• city status
• partNumber partName
• supplierName, partNumber quantity

Find the closure of supplierName, partNumber, supplierName, and partNumber.

(supplierName, partNumber) = {supplierName, partNumber}

supplierName city is a functional dependence and {supplierName} is a subset of (supplierName, partNumber) so we add city to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city}

city status is a functional dependence and {city} is a subset of (supplierName, partNumber) so we add status to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city, status}

partNumber partName is a functional dependence and {partNumber} is a subset of (supplierName, partNumber) so we add partName to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city, status, partName}

supplierName, partNumber quantity is a functional dependence and {supplierName, partNumber} is a subset of (supplierName, partNumber) so we add quantity to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city, status, partName, quantity}

We've exhausted all function dependences so this is our final closure. This final closure contains all attributes of the schema so we know (supplierName, partNumber) is a super key.

supplierName = {supplierName}

supplierName city is a functional dependence and {supplierName} is a subset of supplierName so we add city to supplierName.

supplierName = {supplierName, city}

city status is a functional dependence and {city} is a subset of supplierName so we add status to supplierName.

supplierName = {supplierName, city, status}

We've exhausted all functional dependencies which are contained in the closure so this is our final closure.

partNumber = {partNumber}

partNumber partName is a functional dependence and {partNumber} is a subset of partNumber so we add partName to partNumber.

partNumber = {partNumber, partName}

We've exhausted all functional dependencies which are contained in the closure so this is our final closure.

Using those three closures we can see that supplierName, partNumber is a candidate key as reducing either supplierName or partNumber means the key is no longer a super key.