Functional dependencies, closure and keys

Part of the free LogicWiz SQL & Databases course, Module 10: Normalization. The queries and practice run in the app on real Postgres.

An exam question gives you R(A, B, C, D, E) and four arrows, and asks for every candidate key. Guessing takes ages. There is a 30-second method, and SQL can check the arrows against real data.

You'll learn to

• Read and check a functional dependency X → Y
• Compute an attribute closure X⁺ step by step
• Find all candidate keys and count superkeys
• Test whether an FD holds in data with GROUP BY … HAVING

Learn

Functional dependency: X decides Y

A functional dependency (FD) X → Y says: any two rows that have the same X must have the same Y. "X determines Y."

• student_id → student_name: one student id, one name.
• dept → hod: one department, one HOD.
• course_id → course_title, credits.
• (student_id, course_id) → marks.

But student_name → student_id does not hold: two students can both be called Riya.

An FD is trivial when Y is part of X, like (student_id, course_id) → course_id. It is always true and tells you nothing.

Does dept → hod hold? Ask SQL

-- A department with more than one HOD breaks dept → hod
SELECT dept, COUNT(DISTINCT hod) AS hods
FROM marks_sheet
GROUP BY dept
HAVING COUNT(DISTINCT hod) > 1;

No rows means no department breaks the rule in this data. Add UPDATE marks_sheet SET hod = 'Dr. Mehta' WHERE student_id = 101; at the top and run it again: now CSE shows up.

A rule that does not hold: city → dept_id

SELECT city, COUNT(DISTINCT dept_id) AS depts
FROM students
GROUP BY city
HAVING COUNT(DISTINCT dept_id) > 1
ORDER BY city;

The template for any FD X → Y is GROUP BY X HAVING COUNT(DISTINCT Y) > 1. Each row returned is a value of X with more than one Y: proof that the FD is false. Note that COUNT(DISTINCT …) skips NULLs.

Armstrong's axioms: deriving new FDs

From the given FDs you can derive others with three rules (Armstrong's axioms):

• Reflexivity: if Y ⊆ X, then X → Y (trivial FDs).
• Augmentation: if X → Y, then XZ → YZ (add the same thing to both sides).
• Transitivity: if X → Y and Y → Z, then X → Z.

Useful results that follow: union (X → Y and X → Z give X → YZ), decomposition (X → YZ gives X → Y and X → Z) and pseudo-transitivity (X → Y and WY → Z give WX → Z).

Example: student_id → dept and dept → hod give student_id → hod by transitivity.

Attribute closure: everything X decides

R(A, B, C, D, E) with F = {A → B, B → C, CD → E}. The closure X⁺ is every attribute X determines. Start with X, then keep adding the right side of any FD whose whole left side is already in the set, until nothing changes. Since {A, D}⁺ is all of R, AD is a superkey.

Superkey, candidate key, primary key

• A superkey is any set of attributes whose closure is the whole relation.
• A candidate key is a minimal superkey: remove any attribute and it stops being one.
• The primary key is the one candidate key you pick.
• Prime attributes are those in at least one candidate key.

The fast method: an attribute that never appears on a right side can't be derived, so it must be in every key. Start from those. Above, A and D never appear on the right; {A, D}⁺ is everything, so AD is the only candidate key. Check minimality: A⁺ = {A, B, C} and D⁺ = {D}.

Data can disprove an FD but never prove it. Zero rows from the HAVING check means "this data doesn't break it yet". Whether student_id → name is an FD comes from the meaning of the data (the rules of the college), not from today's rows.

Counting superkeys: if R has n attributes and one candidate key with k attributes, every set containing the key is a superkey, so there are 2^(n−k) superkeys. With two keys, use inclusion–exclusion: |contains K1| + |contains K2| − |contains both|. For R(A, B, C, D) with keys A and B: 8 + 8 − 4 = 12.

In one line

X → Y: same X, same Y. Closure X⁺ finds what X decides; a minimal X with X⁺ = R is a candidate key. Check an FD in data with GROUP BY X HAVING COUNT(DISTINCT Y) > 1.

Interview corner

What is a functional dependency?

X → Y means any two rows with the same X value must have the same Y value, for example emp_id → salary. FDs come from business rules, and they are what normalization uses to decide how to split tables.

Superkey vs candidate key vs primary key?

A superkey is any set of columns that uniquely identifies a row. A candidate key is a minimal superkey: no column can be removed. The primary key is the candidate key you choose; the others usually get UNIQUE constraints.

How do you find all candidate keys from a set of FDs?

Attributes that appear on no right-hand side must be in every key, so start with them and compute their closure. If it is not everything, try adding one attribute at a time (then two), keep each set whose closure is all attributes, and drop any that contain a smaller key.

How would you check in SQL whether a column determines another?

SELECT x FROM t GROUP BY x HAVING COUNT(DISTINCT y) > 1; lists every x with more than one y. An empty result means the data does not violate x → y (it doesn't prove the rule).