# Functional Dependencies

Many-to-one relationship from one set of attributes to another

E.g. in SP there is a functional dependency from (SID,PID) to QTY

• for any given value of SID and PID, there is just one value for QTY
• distinctive values of SID, PID can have the same value for QTY

Distinguish:

• (a) the value of a relation at some point in time
• (b) the set of all possible values of a relation

Example: add city to SP. Note that every supplier has exactly one city.

```> create table SCP (SID char(5), CITY char(15), PID char(6), QTY numeric(9,0));

insert into SCP (sid, city, pid, qty ) values ('S1', 'London', 'P1', 100);
insert into SCP (sid, city, pid, qty ) values ('S1', 'London', 'P2', 100);
insert into SCP (sid, city, pid, qty ) values ('S2', 'Paris',  'P1', 200);
insert into SCP (sid, city, pid, qty ) values ('S2', 'Paris',  'P2', 200);
insert into SCP (sid, city, pid, qty ) values ('S3', 'Paris',  'P2', 300);
insert into SCP (sid, city, pid, qty ) values ('S4', 'London', 'P2', 400);
insert into SCP (sid, city, pid, qty ) values ('S4', 'London', 'P4', 400);
insert into SCP (sid, city, pid, qty ) values ('S4', 'London', 'P5', 400);

> select * from SCP;

sid  |      city       |  pid   | qty
-------+-----------------+--------+-----
S1    | London          | P1     | 100
S1    | London          | P2     | 100
S2    | Paris           | P1     | 200
S2    | Paris           | P2     | 200
S3    | Paris           | P2     | 300
S4    | London          | P2     | 400
S4    | London          | P4     | 400
S4    | London          | P5     | 400
```
• SID → CITY

(a) and (b), integrity constraint

• QTY → SID
• SID → QTY

only (a)

Usually interested in (b)

• {SID, PID} → QTY
• {SID, PID} → CITY
• {SID, PID} → {CITY, QTY}
• SID → CITY
• {SID, PID} → SID
• {SID, PID} → {SID, PID, CITY, QTY}
• ...

Trivial Dependencies: e.g. {SID, PID} → PID

A FD is trivial iff the right-hand side is a subset of the left-hand side.

For arbitrary subsets X and Y of relation R:

• If X is a candidate key of R, then Y must be functionally dependent on X

e.g. for P: PID → {PID, NAME, COLOR, WEIGHT, CITY}

• If A → B and A is not a candidate key,
• and the FD is not trivial
• and A is not a superkey
• and R contains at least 2 tuples

then R contains redundancies

e.g. for SCP: SID → CITY
the fact that a given supplier is located in a particular city appears many times

FDs are integrity constraints;

• DBMS must enforce them
• set of all FDs can be very large
• Therefore, for a given set of FDs S, find set T that is
• smaller than S, and
• all FDs in S are implied by the FDs in T

## Closure of a Set of Dependencies

Some FDs imply others, e.g.

{SID, PID} → {CITY, QTY}

imply

• {SID, PID} → CITY
• {SID, PID} → QTY

Closure S+ of a set S of FDs: all FDs that are implied by S

Armstrong Axioms:

Let A, B, C arbitrary subsets of attributes of relation R, and denote AB the union of A and B.

1. Reflexivity: if B is a subset of A, then A → B 2. Augmentation: if A → B, then AC → BC 3. Transitivity: if A → B and B → C, then A → C • First rule = definition of trivial FD
• Rules are complete: all implied FDs can be derived
• Rules are sound: no additional FDs (not implied by S) can be so derived
• In other words, rules can be used to derive precisely S+

Several more rules can be derived to simplify the practical task of computing S+

Decomposition: if A → BC, then A → B and A → C Union: if A → B and A → C, then A → BC Composition: if A → B and C → D, then AC → BD Self-determination: A → A Example: A → BC, B → E, CD → EF (e.g. A EMPID, B DEPID, C MGR, D PROJID, E DEPNAME, F PERCTIME)