Functional Dependency

The Relational Model topic built the schema but left one question unanswered: which column belongs in which relation? In the loan.csv file from the course’s first lesson, the member name repeated across three rows, and an email change required a correction in three places. This lesson’s question is: where does that repetition come from, and how is it named formally?

The answer lies in a single concept. If the value of one set of columns determines the value of another set of columns, a dependency exists between them; repetition arises when that dependency is placed in the wrong location.

Definition and Notation

Let $H$ be the attribute set of relation $R$, and let $X, Y \subseteq H$. If, in every valid value of $R$, two rows carrying the same values on $X$ also carry the same values on $Y$, the attributes of $Y$ are said to be functionally dependent on $X$, written:

$$X \to Y$$

Read as “$X$ determines $Y$.” A few examples from the library domain:

• $\text{member no} \to \text{member name}, \text{member email}$ — once the member number is known, the member’s name and address are known.
• $\text{ISBN} \to \text{book title}, \text{book author}$
• $\text{branch code} \to \text{branch name}$
• $\text{loan no} \to$ every other attribute.

The last line is the superkey definition from the previous topic, restated in the language of dependency: $K$ is a superkey if and only if $K \to H$. A candidate key is the smallest set with this property. The concept of a key is a special case of the concept of dependency.

Dependency Comes From Meaning

The critical point is this: a functional dependency is not read off today’s data. Today’s data can only refute a dependency; it cannot confirm one. Dependency comes from the rule of the domain.

Counting the difference on an example is the fastest way to eliminate dependency candidates:

const headers = "loan_no member_no member_name isbn book_title branch_code branch_name".split(" ");
const data = [
  "1001 41 Alice_Kane 975-01 Lost_Time CEN Central",
  "1002 52 Marcus_Reyes 975-01 Lost_Time CEN Central",
  "1003 41 Alice_Kane 975-02 Sea_Lighthouses BHC Bahcelievler",
  "1004 41 Alice_Kane 975-01 Lost_Time CEN Central",
  "1005 63 Alice_Kane 975-02 Sea_Lighthouses CEN Central",
  "1006 52 Marcus_Reyes 975-03 Silent_Garden BHC Bahcelievler",
].map((s) => Object.fromEntries(s.split(" ").map((v, i) => [headers[i], v])));

function countViolations(left, right) {
  const groups = new Map();
  for (const row of data) {
    const key = left.map((a) => row[a]).join("|");
    const value = right.map((a) => row[a]).join("|");
    if (groups.has(key)) groups.get(key).add(value);
    else groups.set(key, new Set([value]));
  }
  return [...groups.values()].filter((d) => d.size > 1).length;
}

const candidates = [
  [["loan_no"], ["member_no"]],
  [["member_no"], ["member_name"]],
  [["member_name"], ["member_no"]],
  [["isbn"], ["book_title"]],
  [["book_title"], ["isbn"]],
  [["branch_code"], ["branch_name"]],
  [["member_no"], ["isbn"]],
];

for (const [left, right] of candidates) {
  const violations = countViolations(left, right);
  const status = violations === 0 ? "consistent with the data" : `violated in ${violations} group${violations === 1 ? "" : "s"}`;
  console.log(`${left.join(",")} -> ${right.join(",")}`.padEnd(30), status);
}

loan_no -> member_no           consistent with the data
member_no -> member_name       consistent with the data
member_name -> member_no       violated in 1 group
isbn -> book_title             consistent with the data
book_title -> isbn             consistent with the data
branch_code -> branch_name     consistent with the data
member_no -> isbn              violated in 2 groups

The checker groups rows by their left-side values and counts a violation whenever a group holds more than one right-side value. member_name -> member_no shows one violation: two different members share the same name. member_no -> isbn shows two violations: the same member has borrowed more than one book.

The real lesson lies in the rows marked “consistent with the data.” The dependency book_title -> isbn is not refuted across these six rows, but it does not hold — two different books can carry the same title, and the schema breaks the day that record is entered. A checker is an elimination tool: finding a violation means the dependency definitely does not hold; finding none means it has only not yet been refuted. The rule of the domain decides.

Types of Dependency

Four distinctions will be used in defining the normal forms.

Trivial dependency: when $Y \subseteq X$, $X \to Y$ always holds. $\text{member no}, \text{member name} \to \text{member name}$ carries no information.

Full dependency: if $X \to Y$ holds and no proper subset of $X$ determines $Y$, the dependency is full.

Partial dependency: if $X$ is a composite key and $Y$ depends on a proper subset of $X$, the dependency is partial. If the loan record’s key were $(\text{member no}, \text{ISBN})$, then $\text{member no} \to \text{member name}$ would be a partial dependency: the member name depends on half the key, not on the whole of it.

Transitive dependency: when $X \to Y$ and $Y \to Z$ hold, $Z$ depends on $X$ through $Y$. In the loan record this is the chain $\text{loan no} \to \text{branch code} \to \text{branch name}$; the branch name does not depend on the loan directly, but through the branch code.

Partial and transitive dependencies both cause the same fact to repeat across multiple rows — the branch name is rewritten in every loan made from that branch. The next lesson’s topic is removing these two dependencies.

Armstrong’s Axioms

Dependencies can be derived from one another. Three axioms suffice to produce every dependency that follows from a known set of dependencies.

• Reflexivity: if $Y \subseteq X$, then $X \to Y$.
• Augmentation: if $X \to Y$, then for every $Z$, $X \cup Z \to Y \cup Z$.
• Transitivity: if $X \to Y$ and $Y \to Z$, then $X \to Z$.

Three useful rules follow from these: union (if $X \to Y$ and $X \to Z$, then $X \to Y \cup Z$), decomposition (if $X \to Y \cup Z$, then $X \to Y$ and $X \to Z$), and pseudotransitivity. The decomposition rule licenses splitting a dependency with several attributes on the right side into single-attribute pieces; analysis is usually carried out this way.

The axiom set has two properties: it is sound (every derived dependency actually holds) and complete (every dependency that holds can be derived). This is why normal-form checks can be carried out mechanically rather than by hand intuition.

Attribute Closure

Instead of deriving by hand, a set is computed. The attribute closure of a set $X$, written $X^+$, is the set of all attributes that can be determined from $X$ using the given dependencies. The computation is iterative: the right side of every dependency whose left side already lies within $X^+$ is added to the set, and this continues until the set stops growing.

Closure answers two questions in a single step. Does $X \to Y$ hold? Yes, if $Y \subseteq X^+$. Is $X$ a superkey? Yes, if $X^+$ covers every attribute.

const attributes = "loan_no member_no member_name isbn book_title branch_code branch_name".split(" ");
const dependencies = [
  [["loan_no"], ["member_no", "isbn", "branch_code"]],
  [["member_no"], ["member_name"]],
  [["isbn"], ["book_title"]],
  [["branch_code"], ["branch_name"]],
];

function closure(start) {
  const result = new Set(start);
  let grew = true;
  while (grew) {
    grew = false;
    for (const [left, right] of dependencies) {
      if (left.every((a) => result.has(a))) {
        for (const a of right) if (result.has(a) === false) { result.add(a); grew = true; }
      }
    }
  }
  return [...result];
}

for (const set of [["loan_no"], ["member_no"], ["member_no", "isbn"]]) {
  const k = closure(set);
  console.log(`{${set.join(",")}}+ = {${k.join(",")}}`);
  console.log(`  -> ${k.length === attributes.length ? "superkey" : "not a superkey"}`);
}

{loan_no}+ = {loan_no,member_no,isbn,branch_code,member_name,book_title,branch_name}
  -> superkey
{member_no}+ = {member_no,member_name}
  -> not a superkey
{member_no,isbn}+ = {member_no,isbn,member_name,book_title}
  -> not a superkey

The loan number alone reaches every attribute, so it is a superkey; since no proper subset of it has this property, it is also a candidate key. The member number and the ISBN together still cannot reach the branch information — because the branch depends on the loan, not on the pair of member and book.

Closure computation is the transitive-closure idea from the Data Structures course, applied to dependencies instead of graphs: instead of the set of nodes reachable from a node, it finds the set of attributes that can be determined from a set of attributes.

What a Dependency Looks Like in the Schema

A dependency shows up in the schema in one of two ways. If its left side is a candidate key, the dependency is already enforced by the key constraint — because the key is unique, each value occurs once, and the right side is written once for that row. If the left side is not a key, the dependency cannot be written into the schema; the engine has no way of knowing about it, and no constraint can be built to prevent it from being violated.

From this comes normalization’s one-sentence justification: splitting relations so that the left side of every functional dependency is a key ensures dependencies are enforced by the schema. The next lesson defines this splitting process step by step.

Summary

• $X \to Y$ is the rule that two rows matching on $X$ also match on $Y$; a superkey is the left side of a dependency whose right side is every attribute.
• Dependency comes from the rule of the domain; a data sample can only refute it, never confirm it.
• Partial dependency is built on part of a composite key, transitive dependency through an intermediate attribute; both cause rows to repeat.
• Armstrong’s axioms are sound and complete, so dependency inference can be carried out mechanically.
• Attribute closure answers, in a single computation, both whether a dependency holds and whether a set is a superkey.

Next Step

This lesson named the source of repetition: dependencies whose left side is not a key. The next lesson defines the steps for removing them. First normal form requires the indivisibility of values, second normal form requires removing partial dependency, third normal form requires removing transitive dependency. At each step the same question will be asked: which update anomaly does this split eliminate?