FD definition; trivial vs non-trivial; checking whether an FD holds on an instance

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Name the three anomalies. from Lesson 4.1.1
2. Can a table instance prove that an attribute set is a key? from Lesson 2.2.1
3. What is p → q equivalent to? from Lesson 0.2.3

1 · The Hook

"roll determines name": two rows with the same roll always have the same name. That sentence is a functional dependency, written roll → name. Every normal form, every key calculation and every decomposition test in this phase is built on it. GATE often starts simple: here is a table instance; which FDs hold?

2 · Predict First

Does A → B hold in this instance? Does A → C? Does C → A?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

A → B: the two rows with A = 1 both have B = x → holds. A → C: A = 1 gives p and q → fails. C → A: C = p gives A = 1 and A = 2 → fails.

Definition

For attribute sets X and Y of R, the functional dependency X → Y holds on R if, in every valid state of R, any two tuples that agree on X also agree on Y:

for all t₁, t₂: t₁[X] = t₂[X] ⇒ t₁[Y] = t₂[Y].

Read "X determines Y" or "Y is functionally dependent on X". X is the left-hand side (determinant), Y the right-hand side.

FDs come from the meaning of the data ("each student has one name"), declared by the designer. A key is a special case: K is a superkey exactly when K → R (K determines all attributes).

Checking an FD on an instance

Group the rows by their X-values. The FD X → Y fails if some group contains two different Y-values. Otherwise it holds in this instance.

• An instance can disprove an FD (one counter-example) but never prove it holds on the schema.
• If no two rows share an X-value (X unique in the instance), then X → Y holds in that instance for every Y.
• If all rows have the same Y-value, then X → Y holds in that instance for every X.

Trivial and non-trivial FDs

• Trivial: Y ⊆ X (AB → A). Always holds, says nothing.
• Non-trivial: Y ⊄ X (AB → C, or AB → BC).
• Completely non-trivial: X ∩ Y = ∅ (AB → C).

Notation

Attribute sets are written without braces: AB means {A, B}; AB → CD means {A, B} → {C, D}. A set of FDs is called F.

FDs of the college tables

roll → name, roll → dept, dept → hod, cid → title, roll cid → grade. Also derived ones such as roll → hod (through dept): the next lesson shows how to derive them.

4 · Visual

Check  A -> C  on the instance:

group by A      C values in the group     verdict
A = 1           { p, q }                  two different C's -> A -> C FAILS
A = 2           { p }

Check  A -> B:
A = 1           { x }                     one value per group
A = 2           { y }                     -> A -> B holds (in this instance)

5 · Worked Examples

Example 1 Easy

Which are trivial: (a) AB → B; (b) A → A; (c) AB → BC; (d) A → B?

Solution

(a) and (b) are trivial (right side inside left side). (c) is non-trivial (C ∉ AB) but not completely non-trivial (B is shared). (d) is completely non-trivial.

Example 2 Medium

Which of P → R, Q → R, R → P, PQ → R hold in this instance?

Solution

P → R: P = a gives x, x → holds. Q → R: Q = 1 gives x, y → fails. R → P: R = x gives a, a; R = y gives b, c → fails. PQ → R: all PQ pairs are different → holds.

Example 3 GATE

On R(A, B, C) the instance has 4 rows and every row has C = 5. Which FDs with C on the right hold in this instance?

Solution

All of them: A → C, B → C, AB → C, even ∅ → C. Any two rows agree on C. (This tells nothing about the schema.)

8 · Connect the Dots

Lesson 4.1.1 said each fact is "determined" by some attributes; this lesson made "determines" precise. Next: from a few given FDs, many others follow logically. Armstrong's axioms are the rules for deriving them.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MSQ · 2 mark(s) — Instance check

Instance of R(A, B, C): (1, 2, 3), (1, 2, 4), (2, 2, 3), (3, 1, 3). Which FDs hold in this instance?

1. (A) C → B
2. (B) B → C
3. (C) A → B
4. (D) AC → B

Q2 · MCQ · 1 mark(s) — Trivial

Which FD is trivial?

1. (A) A → B
2. (B) AB → A
3. (C) AB → C
4. (D) A → AB

Q3 · MCQ · 1 mark(s) — Keys

K is a superkey of R exactly when:

1. (A) K → K
2. (B) K → R (all attributes)
3. (C) K is a single attribute
4. (D) R → K

Q4 · MCQ · 2 mark(s) — Proof

In a given instance, no two rows share a value of X. What can you conclude?

1. (A) X is a key of the schema
2. (B) X → Y holds in this instance for every Y
3. (C) Nothing at all
4. (D) X → Y holds on the schema for every Y

Q5 · NAT · 1 mark(s) — Counting

Instance of R(A, B): (1, x), (2, x), (3, y), (1, x). (Treat it as a list.) How many of the FDs A → B, B → A hold in this instance?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

functional dependency (FD)determinant (left-hand side)trivial FDnon-trivial FDcompletely non-trivial FDFD set Fchecking an FD on an instance