Functional Dependencies (FDs)

Why Functional Dependencies Are Introduced

Earlier, we discussed informal design guidelines (like avoiding redundancy and anomalies).

Now, we introduce a formal tool to:

• Analyze relational schemas precisely

• Detect redundancy problems

• Define normal forms (later in normalization)

👉 The most important concept in relational schema design theory is the Functional Dependency (FD).

---

Universal Relation Assumption

To develop the theory formally:

We assume the whole database is represented as a single:

$$R=\{A_1,A_2,\mathrm{.}\mathrm{.}\mathrm{.},A_n\}$$

This is called the Universal Relation Schema.

⚠️ Important:

• This is only for theory

• We do NOT actually store the database as one big table

• It helps define dependencies mathematically

---

Formal Definition of Functional Dependency

Definition

A functional dependency is a constraint between two sets of attributes.

It is written as:

$$X\to Y$$

Where:

• X = Left-hand side (LHS)

• Y = Right-hand side (RHS)

Meaning

For any two tuples $t_{\mathrm{1 }}$and $t_2$ in a relation state:

If:

$$t_1[X]=t_2[X]$$

Then it must be true that:

$$t_1[Y]=t_2[Y]$$

---

Simple Meaning in Words

If two rows agree on X, they must also agree on Y.

OR

X functionally determines Y.

OR

Y is functionally dependent on X.

---

Intuitive Understanding

If:

$$X\to Y$$

Then:

• Knowing X uniquely determines Y

• X determines Y

• Given X, there is only one possible Y value

---

Important Notes About FDs

---

🔹 1. If X is a Candidate Key

If X is a candidate key, then:

$$X\to Y$$

for every subset Y of R

Because:

• A key uniquely identifies tuples

• No two tuples can have the same X

So:

$$X\to R$$

---

🔹 2. FDs Are Not Symmetric

If:

$$X\to Y$$

It does NOT mean:

$$Y\to X$$

Functional dependency works in one direction only unless proven otherwise.

---

Functional Dependencies Depend on Meaning (Semantics)

FDs are based on:

• Real-world meaning of attributes

• Logical relationships between attributes

They are:

✅ A property of the schema
❌ Not just a property of a specific table instance

---

Example from Real World

$$\{State,Driver\mathrm{\_}license\mathrm{\_}number\}\to Ssn$$

This generally holds because:

• A driver’s license number in a state uniquely identifies a person

BUT it might not hold in cases of fraud.

---

Example of Changing Reality

Earlier:

$$Zip\mathrm{\_}code\to Area\mathrm{\_}code$$

Used to be true in the U.S.

Now:

• Due to many new phone area codes

• It no longer holds

👉 FDs depend on real-world rules.

---

Example: EMP_PROJ Relation

Given relation:

EMP_PROJ(Ssn, Ename, Pnumber, Pname, Plocation, Hours)

From semantics:

a)

$$Ssn\to Ename$$

Meaning:

• Social Security number uniquely determines employee name

---

b)

$$Pnumber\to \{Pname,Plocation\}$$

Meaning:

• Project number uniquely determines project name and location

---

c)

$$\{Ssn,Pnumber\}\to Hours$$

• Combination of employee and project determines weekly hours worked

---

FDs Are Schema Properties — Not Instance Properties

Important concept:

An FD:

• Cannot be guaranteed by looking at just one table instance

• Must hold for all possible legal states

---

Example: TEACH Relation

Suppose current table suggests:

$$Text\to Course$$

But we cannot confirm it unless:

• It holds in all possible future states

However:

If we find a counterexample once, then:

❌ The FD does NOT hold

Example:
If “Smith” teaches two different courses:

Then:

$$Teacher\nrightarrow Course$$

Because one teacher does not determine one course.

---

Verifying FDs from a Table

From a given table:

We can say:

• A  FD may hold if no violation appears

But we cannot say:

• It definitely holds for all time

However:

If we see even one violation:

Then the FD definitely does NOT hold.

---

 Example of Violations

Suppose table shows:

Violations:

• A → B violated if two tuples have same A but different B

• B → A violated if same B but different A

• D → C violated similarly

But if no violation exists for:

• B → C

• C → B

• {A,B} → C

Then these may hold (but not guaranteed universally).

---

Notation for FDs

Graphical representation:

• Horizontal line represents FD

• LHS attributes connect on left

• RHS attributes have arrows pointing to them

Example:

---

Set of Functional Dependencies (F)

Let:

$$F=\text{set of all specified FDs on relation R}$$

From F:

• Many other FDs can be logically derived

• These are called implied dependencies

Inference rules for deriving them are studied later.

---

Why Functional Dependencies Are Important

FDs help to:

• Detect redundancy

• Detect partial dependencies

• Detect transitive dependencies

• Define:

  • 2NF

  • 3NF

  • BCNF

They form the foundation of normalization theory.

---

Summary

A Functional Dependency (FD):

• Is a constraint between two sets of attributes

• Is written as:

  $$X\to Y$$

• Means:
  If two tuples agree on X, they must agree on Y

• Is based on real-world meaning (semantics)

• Is a property of the schema, not just one table instance

• Is the core concept used in relational normalization