DBMS

Database Design

Functional Dependencies

Start with a badly designed table, so the theory has something to explain.

JrCodex·7 min read

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Chapter 2: From ER to Relational Schema Time to complete: ~20 minutes

Table of Contents

  1. The Three Anomalies
  2. What a Functional Dependency Is
  3. Kinds of Dependency
  4. Armstrong's Axioms and Closure
  5. Finding Keys with Closure
  6. Why Anomalies Happen
  7. Summary & Next Steps

1. The Three Anomalies

Start with a badly designed table, so the theory has something to explain.

One Table Holding Everything
─────────────────────────────────────────
  enrollments_bad
  ┌──────┬────────┬────────┬───────────┬─────────┬───────┐
  │ s_id │ s_name │ c_id   │ c_title   │ c_dept  │ grade │
  ├──────┼────────┼────────┼───────────┼─────────┼───────┤
  │  1   │ Asha   │  10    │ Databases │ CS      │  A    │
  │  1   │ Asha   │  11    │ Networks  │ CS      │  B    │
  │  2   │ Ravi   │  10    │ Databases │ CS      │  C    │
  │  3   │ Meera  │  12    │ Statistics│ Math    │  A    │
  └──────┴────────┴────────┴───────────┴─────────┴───────┘
─────────────────────────────────────────

UPDATE ANOMALY
─────────────────────────────────────────
  "Databases" is renamed to "Database Systems".

  It appears on TWO rows. Update one and miss the
  other, and the table now disagrees with itself
  about the name of course 10.

  The database cannot detect this — both rows are
  individually valid.

INSERTION ANOMALY
─────────────────────────────────────────
  A new course, "Compilers", is created. Nobody has
  enrolled yet.

  You cannot record it. Every row needs a s_id and
  a grade. The course exists in the world and has
  nowhere to live in the schema — unless you invent
  a fake student, which is worse.

DELETION ANOMALY
─────────────────────────────────────────
  Meera drops Statistics — delete her row.

  Course 12 has now vanished entirely. It was the
  only row mentioning it, so deleting an ENROLMENT
  destroyed a COURSE.
─────────────────────────────────────────

The Shared Cause
─────────────────────────────────────────
  This table stores facts about THREE different
  things — students, courses, and enrolments — in
  one place.

  Functional dependencies are the tool that makes
  "three different things" precise, and
  normalisation (Chapter 4) is the procedure that
  separates them.
─────────────────────────────────────────

2. What a Functional Dependency Is

The Definition
─────────────────────────────────────────
  X → Y     "X functionally determines Y"

  Means: any two rows agreeing on X must agree on Y.

  Equivalently: if you know X, then Y is fixed.
─────────────────────────────────────────

In Our Bad Table
─────────────────────────────────────────
  s_id → s_name          knowing the student id
                         fixes the name

  c_id → c_title, c_dept knowing the course id
                         fixes title and department

  s_id, c_id → grade     you need BOTH to know the
                         grade
─────────────────────────────────────────

An FD Is About the DOMAIN, Not the Data
─────────────────────────────────────────
  You cannot read FDs off a sample. If every
  student in your test data happens to live in a
  different city, `s_name → city` LOOKS true — and
  is false the moment two people share a name.

  An FD is a business rule that must hold for
  every possible instance (Module 2, Chapter 1's
  schema-vs-instance distinction).

  So FDs come from asking the domain expert, never
  from inspecting rows.
─────────────────────────────────────────

3. Kinds of Dependency

The Classification
─────────────────────────────────────────
  TRIVIAL
    X → Y where Y ⊆ X
    {s_id, s_name} → s_name
    Always true, tells you nothing.

  FULL FUNCTIONAL
    X → Y, and no proper subset of X determines Y.
    {s_id, c_id} → grade
    Neither column alone determines the grade.

  PARTIAL
    Part of a composite key determines a non-key
    attribute.
    {s_id, c_id} → s_name, but s_id → s_name alone
    ── causes 2NF violations (Chapter 4)

  TRANSITIVE
    X → Y and Y → Z, so X → Z indirectly.
    c_id → dept_id → dept_name
    ── causes 3NF violations (Chapter 4)
─────────────────────────────────────────

Why These Two Are Named
─────────────────────────────────────────
  PARTIAL and TRANSITIVE dependencies are exactly
  what normal forms 2 and 3 eliminate.

  Recognising them by shape is most of the skill in
  Chapter 4:
    - part of the key determines something ──► 2NF
    - a non-key column determines something ──► 3NF
─────────────────────────────────────────

4. Armstrong's Axioms and Closure

Three rules from which all other FDs follow.

The Axioms
─────────────────────────────────────────
  REFLEXIVITY    if Y ⊆ X, then X → Y
  AUGMENTATION   if X → Y, then XZ → YZ
  TRANSITIVITY   if X → Y and Y → Z, then X → Z

  Derived, and more useful day to day:
  UNION          X → Y and X → Z  ⟹  X → YZ
  DECOMPOSITION  X → YZ           ⟹  X → Y and X → Z
─────────────────────────────────────────

ATTRIBUTE CLOSURE  X⁺
─────────────────────────────────────────
  The set of ALL attributes determined by X.

  ALGORITHM
    1. start with X⁺ = X
    2. repeat: if some FD A → B has A ⊆ X⁺,
       add B to X⁺
    3. stop when nothing more can be added
─────────────────────────────────────────

def closure(attrs, fds):
    """attrs: set of attribute names. fds: list of (set_lhs, set_rhs)."""
    result = set(attrs)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:     # LHS satisfied, RHS adds something
                result |= rhs
                changed = True
    return result
 
FDS = [
    ({"s_id"},          {"s_name"}),
    ({"c_id"},          {"c_title", "dept_id"}),
    ({"dept_id"},       {"dept_name"}),
    ({"s_id", "c_id"},  {"grade"}),
]
 
print(closure({"s_id"}, FDS))            # {'s_id', 's_name'}
print(closure({"c_id"}, FDS))            # {'c_id','c_title','dept_id','dept_name'}
print(closure({"s_id","c_id"}, FDS))     # everything ──► it is a KEY

5. Finding Keys with Closure

The Test
─────────────────────────────────────────
  X is a SUPER KEY  ⟺  X⁺ = all attributes

  X is a CANDIDATE KEY  ⟺  X is a super key AND
                            no proper subset of X is

  This turns key-finding from intuition into a
  mechanical check — which is exactly what you want
  in an exam and when reviewing someone's schema.
─────────────────────────────────────────

from itertools import combinations
 
def candidate_keys(all_attrs, fds):
    keys = []
    for size in range(1, len(all_attrs) + 1):
        for combo in combinations(sorted(all_attrs), size):
            s = set(combo)
            if any(set(k) <= s for k in keys):        # a subset is already a key ──► not minimal
                continue
            if closure(s, fds) == all_attrs:
                keys.append(combo)
    return keys
 
ALL = {"s_id","s_name","c_id","c_title","dept_id","dept_name","grade"}
print(candidate_keys(ALL, FDS))          # [('c_id','s_id')]  — the only candidate key
Reading the Result
─────────────────────────────────────────
  The only candidate key is {s_id, c_id}.

  So s_name, c_title, dept_id and dept_name are all
  NON-KEY attributes determined by only PART of the
  key, or by another non-key attribute.

  That is a precise statement of what is wrong with
  the table — and Chapter 4 fixes exactly those two
  patterns.
─────────────────────────────────────────

6. Why Anomalies Happen

The Connection, Stated Directly
─────────────────────────────────────────
  An anomaly occurs when a table stores a fact
  whose determinant is NOT a key of that table.

  s_id → s_name
    s_id is not the key of enrollments_bad, so
    s_name is repeated once per enrolment ──►
    UPDATE anomaly

  c_id → c_title
    c_id is not the key, so course facts only
    exist where an enrolment exists ──► INSERTION
    and DELETION anomalies
─────────────────────────────────────────

The Rule Everything Reduces To
─────────────────────────────────────────
  Every non-trivial FD in a table should have a
  SUPER KEY on its left-hand side.

  "The key, the whole key, and nothing but the
   key."

  If a determinant is not a key, that fact belongs
  in a different table — one where it IS the key.

  That single sentence is BCNF, and Chapter 4
  builds up to it in stages.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • Update, insertion and deletion anomalies all come from one cause: storing facts about several different things in one table.
  • X → Y means any two rows agreeing on X must agree on Y — and it is a rule about the domain, never something you can read off sample data.
  • Attribute closure is a mechanical procedure that finds every attribute a set determines, which turns key-finding into a check rather than an intuition.
  • An anomaly occurs exactly when a fact's determinant is not a key of its table, which is why "every determinant must be a super key" resolves all of them.

Concept Check

  1. Why can you not infer functional dependencies by inspecting a table's current rows?
  2. Compute the closure of {c_id} given the FDs in Section 4, and say whether c_id is a key.
  3. Explain the insertion anomaly for a new course in terms of determinants and keys.

Next Chapter

→ Chapter 4: Normalisation

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index