---
title: 'Functional Dependency'
source: 'https://academia.sh/en/courses/relational-theory/functional-dependency'
course: 'Data Modeling and Relational Theory'
language: en
updated: '2026-08-23T07:00:47+00:00'
license: 'CC BY-SA 4.0'
---

# Functional Dependency

The definition and notation of functional dependency, dependency arising from meaning rather than from data, the types of dependency, Armstrong's axioms, and finding keys through attribute closure.

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:

```js
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.

```js
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?