Given FDs X, Y and Y X hold for two attributes X and Y, then the relationship between X and Y is

COMP3311 20T3 ♢ Functional Dependency ♢ [0/12]

Most texts adopt the following terminology:

COMP3311 20T3 ♢ Functional Dependency ♢ [1/12]

A relation instance r(R) satisfies a dependency X → Y  if

• for any t, u ∈ r,   t[X] = u[X]   ⇒   t[Y] = u[Y]

We say that "Y  is functionally dependent on X ".

Attribute sets X and Y may overlap;   it is trivially true that X → X.

Notes:

• X → Y can also be read as "X determines Y"
• the single arrow → denotes functional dependency
• the double arrow ⇒ denotes logical implication

COMP3311 20T3 ♢ Functional Dependency ♢ [2/12]

Consider the following (redundancy-laden) relation:

Some functional dependencies in this relation

• Title Year → Len,     Title Year → Studio

COMP3311 20T3 ♢ Functional Dependency ♢ [3/12]

Consider an instance r(R) of the relation schema R(ABCDE):

Since A  values are unique, the definition of fd  gives:

• A → B,    A → C,    A → D,    A → E,     or    A → BCDE

• A → E,    B → E,    C → E,    D → E

COMP3311 20T3 ♢ Functional Dependency ♢ [4/12]

Other observations:

• combinations of BC are unique, therefore   BC → ADE
• combinations of BD are unique, therefore   BD → ACE
• if C values match, so do D values, therefore   C → D
• however, D values don't determine C values, so   !(D → C)

In practice, choose a minimal set of fds (basis)

• from which all other fds can be derived
• which captures useful problem-domain information

COMP3311 20T3 ♢ Functional Dependency ♢ [5/12]

Real estate agents conduct visits to rental properties

• need to record which property, who went, when, results
• each property is assigned a unique code (P#, e.g. P4)
• each staff member has a staff number (S#, e.g. S43)
• staff members use company cars to conduct visits
• a visit occurs at a specific time on a given day
• notes are made on the state of the property after each visit

COMP3311 20T3 ♢ Functional Dependency ♢ [6/12]

The spreadsheet ...

Functional dependencies:   P → A,    A → P,     S → m,    S → C

COMP3311 20T3 ♢ Functional Dependency ♢ [7/12]

Above examples consider dependency within a relation instance r(R).

More important for design  is dependency across all possible instances of the relation (i.e. a schema-based dependency).

This is a simple generalisation of the previous definition:

• for any t, u ∈ any r(R),   t[X] = u[X]   ⇒   t[Y] = u[Y]

E.g. real estate example

• P → A suggests a property entity,   S → N,    S → C suggest a staff entity
• Property(P#,addr),   Staff(S#,name,car),   Inspection(P#,S#,when,notes)

COMP3311 20T3 ♢ Functional Dependency ♢ [8/12]

Can we generalise some ideas about functional dependency?

E.g. are there dependencies that hold for any relation?

• yes, but they're generally trivial, e.g. Y ⊂ X   ⇒   X → Y

• yes, rules of inference allow us to derive dependencies
• allow us to reason about sets of functional dependencies

COMP3311 20T3 ♢ Functional Dependency ♢ [9/12]

Armstrong's rules are general rules of inference on fds.

F1. Reflexivity   e.g.   X → X

• a formal statement of trivial dependencies; useful for derivations

• if a dependency holds, then we can expand its left hand side (along with RHS)

• the "most powerful" inference rule; useful in multi-step derivations

COMP3311 20T3 ♢ Functional Dependency ♢ [10/12]

Armstrong's rules are complete, but other useful rules exist:

F4. Additivity   e.g.   X → Y, X → Z   ⇒   X → YZ

• useful for constructing new right hand sides of fds (also called union)

• useful for reducing right hand sides of fds (also called decomposition)

• shorthand for a common transitivity derivation

COMP3311 20T3 ♢ Functional Dependency ♢ [11/12]

Example: determining validity of AB → GH, given:

R = ABCDEFGHIJ

F = { AB → E,   AG → J,   BE → I,   E → G,   GI → H }

COMP3311 20T3 ♢ Functional Dependency ♢ [12/12]

Produced: 5 Nov 2020