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)

Show: AD → F

1. A → BC
2. A → C (decomposition)
3. AD → CD (augmentation)
4. CD → EF
5. AD → EF (transitivity)
6. AD → F (decomposition)

Example 2: bc → a, de → c, a → bcde
Show that bc → d