Functional Dependencies and Attribute Closure

In one line

A functional dependency X → Y means rows that agree on X must agree on Y. Dependencies are the business rules behind normalization: computing the closure of an attribute set tells you what it determines, which finds candidate keys and exposes partial and transitive dependencies.

0/5 · 0%

Think of it like this

A PIN code determines the city. If two addresses have the same PIN code but different cities, one is wrong. That rule (pin → city) is a functional dependency, and storing the city next to every address is what lets the contradiction happen.

Key ideas

01
Notation: order_id → customer_id, order_date (an order has one customer and date); (order_id, product_id) → quantity; product_id → product_name, price.
02
Full functional dependency: Y depends on all of a composite X, not on a part. Partial dependency: Y depends on part of a composite key ((order_id, product_id) → product_name is really product_id → product_name). Transitive dependency: X → Y → Z where Y is not a key (order_id → customer_id → customer_city).
03
Attribute closure X⁺: start with X, repeatedly add any Y for which a dependency A → Y has A ⊆ current set. If X⁺ contains all attributes, X is a super key; if no proper subset has that property, it's a candidate key.
04
Dependencies come from the business, not the data: a sample where every customer happens to live in a different city doesn't prove customer → city. Ask domain experts, and write the rules down.

Code & diagrams

closure-worked-example.txttext

R(order_id, product_id, customer_id, customer_city, order_date, product_name, qty)

F:  order_id              -> customer_id, order_date
    customer_id           -> customer_city
    product_id            -> product_name
    order_id, product_id  -> qty

{order_id}+             = {order_id, customer_id, order_date, customer_city}
{order_id, product_id}+ = everything  -> candidate key (neither part alone works)

Partial:     product_id -> product_name        (part of the key)
             order_id   -> customer_id, order_date
Transitive:  order_id -> customer_id -> customer_city

Interview problem

The problem

Find the keys and problem dependencies

enrolment(student_id, course_id, student_name, course_title, instructor_id, instructor_name, grade) with rules: student_id → student_name; course_id → course_title, instructor_id; instructor_id → instructor_name; (student_id, course_id) → grade. Find the candidate key and classify each dependency.

When it breaks

Inferring dependencies from current data

What you see

The team assumes email → user because it's unique today, builds on it, then shared family emails appear and merges corrupt accounts.

Fix & prevent

Derive dependencies from confirmed business rules and encode them as constraints (UNIQUE, FK) so violations are caught.

Explain it without notes

What is the difference between a partial and a transitive dependency?

Practice

Compute {A}⁺ for R(A,B,C,D,E) with A → B, B → C, CD → E.

Trade-offs

↔
Rigorous FD analysis takes time; skipping it produces redundancy you pay for with anomalies later.

Done when you can

I can list dependencies, compute closures and find candidate keys.

Command Palette