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
Distinguish:
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
(a) and (b), integrity constraint
only (a)
Usually interested in (b)
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:
e.g. for P: PID → {PID, NAME, COLOR, WEIGHT, CITY}
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;
Some FDs imply others, e.g.
{SID, PID} → {CITY, QTY}
imply
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.
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
Example 2: bc → a, de → c, a → bcde
Show that bc → d