Database Management Systems (DBMS) Module 6 – Functional dependencies

Functional dependencies and Armstrong's axioms

What X -> Y means, how one pair of rows refutes a dependency, and how Armstrong's axioms derive every implied dependency, with a checker that tests each step.

Intermediate
20 minutes
Examples run with sql.js 1.14.2, Python 3.14.8 and Pyodide 314.0.7
By MySmartCoPilot

Free: A dependency says that rows which agree on X agree on Y · One pair of rows refutes a dependency, and no rows prove one · Armstrong's three axioms derive every implied dependency · Practise: derive with the axioms. With a pass: 2 in-depth parts and 3 interview answers, about 12 minutes.

What you will learn

Decide whether the rows of a table refute a functional dependency X -> Y
Explain why a dependency is decided by what the data means, not by the rows a table holds
Derive dependencies line by line with Armstrong's axioms and the union, decomposition and pseudotransitivity rules
Prove that the axioms are sound and complete with two-row tables
Determine whether a set of dependencies implies another one, with a closure or a counterexample

Before you start

Redundancy and update, insert, delete anomalies

What you’ll learn · Before you start

What you will learn

Decide whether the rows of a table refute a functional dependency X -> Y
Explain why a dependency is decided by what the data means, not by the rows a table holds
Derive dependencies line by line with Armstrong's axioms and the union, decomposition and pseudotransitivity rules
Prove that the axioms are sound and complete with two-row tables
Determine whether a set of dependencies implies another one, with a closure or a counterexample

Before you start

Redundancy and update, insert, delete anomalies

On this page

The enrolment sheet of the previous lesson writes Iyer’s office, B-204, into five rows, because an instructor sits in one office: instructor -> office. That arrow is a functional dependency: A rule X -> Y on a relation: any two rows that have the same values for the attributes X also have the same values for Y., X -> Y: any two rows that agree on the attributes X also agree on Y. Functional dependencies come from what the data means, so the sheet’s 8 rows can refute one with a single pair of rows, but no number of rows can prove one.

Known dependencies imply others. Armstrong's axioms: Reflexivity, augmentation and transitivity: three rules that derive every functional dependency implied by a set of known ones, and never a false one., three rules called reflexivity, augmentation and transitivity, derive every dependency that a set of known ones implies, and never a false one. This lesson tests six candidate dependencies on the sheet and checks a derivation line by line, each in 14 languages.

A dependency says that rows which agree on X agree on Y

X -> Y, read “X determines Y”, is a rule about every legal state of a table R: for any two rows t and u of R, if t and u agree on X, they agree on Y. X is the determinant: The left-hand side X of a functional dependency X -> Y: the attributes whose values fix the values of Y.. X and Y are sets of attributes, written without braces, so AB -> C means {A, B} -> {C}. A dependency is trivial dependency: A dependency X -> Y whose right-hand side is part of its left-hand side, such as AB -> A. It holds in every table, so it says nothing about the data. when Y is part of X, as in AB -> A: it holds in every table, so it says nothing about the data. Keys are dependencies too: K is a superkey: A set of attributes whose values identify a row: no two rows of the relation can agree on all of them. More in “Keys: super, candidate, primary, alternate, foreign” of R exactly when K determines every attribute of R. The dependencies of the enrolment sheet are drawn below. Only the pair (roll_no, course) determines the grade, and with it every other attribute, which is why the pair is the key.

The functional dependencies of the enrolment sheet

Text description of the diagram

Each arrow starts at a determinant and ends at an attribute it determines.

roll_no determines student: one roll number belongs to one student.
course determines title and course determines instructor: a course has one title and one instructor.
instructor determines office: an instructor sits in one office.
The pair roll_no and course, shown as one box, determines grade: a student gets one grade in a course.

Only grade depends on the whole key of the sheet; the other attributes depend on part of the key or on the instructor, which is why the sheet repeats them.

Read the figure from the key down: only the grade hangs on the whole key.

Checkpoint

Check: What X -> Y says

One question In R(A, B, C) the dependencies A -> B and A -> C hold. Which statement follows?
Choose one answer.

A -> B is trivial B -> A holds as well No two rows share a value of B A is a superkey of R

Show the answer: One question

Answer: A is a superkey of R

K is a superkey of R exactly when K determines every attribute of R. Here A -> B and A -> C, with A itself, cover all three attributes, just as (roll_no, course) determines every attribute of the sheet.

One pair of rows refutes a dependency, and no rows prove one

A table’s rows are one state of it. To test a candidate dependency, look for two rows that agree on its left-hand side and differ on its right. Step through three tests on the 8 rows of the sheet, and then a ninth row:

Interactive · step by step Testing three dependencies on the 8 rows of the sheet Step through the tests. Each row shows the two columns that the current test compares.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

instructor -> course. The first test is instructor -> course. Each row shows its instructor and its course, and the test keeps the first course it meets for each instructor.
Rows 1 and 4 refute it. Row 3 agrees with row 1, Iyer with CS301. Row 4 has Iyer with CS303, so it agrees with row 1 on the instructor and differs on the course. One such pair is enough, so instructor -> course is false.
course -> grade. The next test is course -> grade. Rows 1 and 5 agree on CS301 and differ on the grade, A against B, so course -> grade is false too.
student -> roll_no survives. The last test is student -> roll_no. Each name appears with one roll number, so no pair of these 8 rows refutes it. Surviving the rows proves nothing, though.
A ninth row. A second student called Diya enrols, with roll number 105. Rows 3 and 9 agree on the name and differ on the roll number, so student -> roll_no breaks, and nothing about names forbade her.
Decide from meaning. Rows can only find counterexamples. Whether a dependency holds is decided by what the attributes mean. A roll number names one student; a name can belong to many students.

The program runs the same test on six candidates, over the five columns they mention, and stops at the first row that disagrees with an earlier one:

One program · 14 languages Six candidate dependencies tested on the rows of the sheet

Python 3.14 · main.py

# Two rows that agree on X and differ on Y refute X -> Y.
COLUMNS = ["roll_no", "student", "course", "instructor", "grade"]
ROWS = [
    ["101", "Aarav", "CS301", "Iyer", "A"],
    ["101", "Aarav", "CS302", "Sen", "B"],
    ["102", "Diya", "CS301", "Iyer", "A"],
    ["102", "Diya", "CS303", "Iyer", "B"],
    ["103", "Kabir", "CS301", "Iyer", "B"],
    ["103", "Kabir", "CS302", "Sen", "C"],
    ["104", "Meera", "CS303", "Iyer", "A"],
    ["104", "Meera", "CS304", "Khan", "A"],
]
CANDIDATES = [
    "roll_no -> student",
    "course -> instructor",
    "instructor -> course",
    "student -> roll_no",
    "course -> grade",
    "roll_no course -> grade",
]


def values(row: list[str], names: list[str]) -> str:
    return " ".join(row[COLUMNS.index(name)] for name in names)


for fd in CANDIDATES:
    lhs, rhs = (side.split() for side in fd.split("->"))
    verdict = f"not refuted by these {len(ROWS)} rows"
    # The first row seen for each value of X.
    first: dict[str, tuple[int, str]] = {}
    for number, row in enumerate(ROWS, start=1):
        key, value = values(row, lhs), values(row, rhs)
        seen, before = first.setdefault(key, (number, value))
        if before != value:
            verdict = (
                f"refuted by rows {seen} and {number}: {key} gives {before} and {value}"
            )
            break
    print(f"{fd:<24} {verdict}")

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

// Two rows that agree on X and differ on Y refute X -> Y.
const COLUMNS = ["roll_no", "student", "course", "instructor", "grade"];
const ROWS = [
  ["101", "Aarav", "CS301", "Iyer", "A"],
  ["101", "Aarav", "CS302", "Sen", "B"],
  ["102", "Diya", "CS301", "Iyer", "A"],
  ["102", "Diya", "CS303", "Iyer", "B"],
  ["103", "Kabir", "CS301", "Iyer", "B"],
  ["103", "Kabir", "CS302", "Sen", "C"],
  ["104", "Meera", "CS303", "Iyer", "A"],
  ["104", "Meera", "CS304", "Khan", "A"],
];
const CANDIDATES = [
  "roll_no -> student",
  "course -> instructor",
  "instructor -> course",
  "student -> roll_no",
  "course -> grade",
  "roll_no course -> grade",
];

const values = (row, names) => names.map((name) => row[COLUMNS.indexOf(name)]).join(" ");

for (const fd of CANDIDATES) {
  const [lhs, rhs] = fd.split("->").map((side) => side.trim().split(" "));
  let verdict = `not refuted by these ${ROWS.length} rows`;
  // The first row seen for each value of X.
  const first = new Map();
  for (const [index, row] of ROWS.entries()) {
    const [key, value] = [values(row, lhs), values(row, rhs)];
    if (!first.has(key)) first.set(key, [index + 1, value]);
    const [seen, before] = first.get(key);
    if (before !== value) {
      verdict = `refuted by rows ${seen} and ${index + 1}: ${key} gives ${before} and ${value}`;
      break;
    }
  }
  console.log(`${fd.padEnd(24)} ${verdict}`);
}

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;

public class Main {
  // Two rows that agree on X and differ on Y refute X -> Y.
  static final List<String> COLUMNS =
      List.of("roll_no", "student", "course", "instructor", "grade");
  static final String[][] ROWS = {
    {"101", "Aarav", "CS301", "Iyer", "A"},
    {"101", "Aarav", "CS302", "Sen", "B"},
    {"102", "Diya", "CS301", "Iyer", "A"},
    {"102", "Diya", "CS303", "Iyer", "B"},
    {"103", "Kabir", "CS301", "Iyer", "B"},
    {"103", "Kabir", "CS302", "Sen", "C"},
    {"104", "Meera", "CS303", "Iyer", "A"},
    {"104", "Meera", "CS304", "Khan", "A"},
  };
  static final List<String> CANDIDATES =
      List.of(
          "roll_no -> student",
          "course -> instructor",
          "instructor -> course",
          "student -> roll_no",
          "course -> grade",
          "roll_no course -> grade");

  record Seen(int number, String value) {}

  static String values(String[] row, String[] names) {
    StringBuilder out = new StringBuilder();
    for (String name : names) {
      out.append(out.isEmpty() ? "" : " ").append(row[COLUMNS.indexOf(name)]);
    }
    return out.toString();
  }

  public static void main(String[] args) {
    Locale.setDefault(Locale.ROOT);
    for (String fd : CANDIDATES) {
      String[] sides = fd.split("->");
      String[] lhs = sides[0].strip().split(" ");
      String[] rhs = sides[1].strip().split(" ");
      String verdict = "not refuted by these " + ROWS.length + " rows";
      // The first row seen for each value of X.
      Map<String, Seen> first = new HashMap<>();
      for (int number = 1; number <= ROWS.length; number++) {
        String key = values(ROWS[number - 1], lhs);
        String value = values(ROWS[number - 1], rhs);
        first.putIfAbsent(key, new Seen(number, value));
        Seen seen = first.get(key);
        if (!seen.value().equals(value)) {
          verdict =
              "refuted by rows %d and %d: %s gives %s and %s"
                  .formatted(seen.number(), number, key, seen.value(), value);
          break;
        }
      }
      System.out.println(String.format("%-24s", fd) + " " + verdict);
    }
  }
}

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <format>
#include <map>
#include <print>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// Two rows that agree on X and differ on Y refute X -> Y.
using Names = std::vector<std::string>;
const Names COLUMNS = {"roll_no", "student", "course", "instructor", "grade"};
const std::vector<Names> ROWS = {
    {"101", "Aarav", "CS301", "Iyer", "A"},
    {"101", "Aarav", "CS302", "Sen", "B"},
    {"102", "Diya", "CS301", "Iyer", "A"},
    {"102", "Diya", "CS303", "Iyer", "B"},
    {"103", "Kabir", "CS301", "Iyer", "B"},
    {"103", "Kabir", "CS302", "Sen", "C"},
    {"104", "Meera", "CS303", "Iyer", "A"},
    {"104", "Meera", "CS304", "Khan", "A"},
};
const Names CANDIDATES = {"roll_no -> student",   "course -> instructor",
                          "instructor -> course", "student -> roll_no",
                          "course -> grade",      "roll_no course -> grade"};

Names words(const std::string &text) {
  std::istringstream in(text);
  Names out;
  for (std::string word; in >> word;)
    out.push_back(word);
  return out;
}

std::string values(const Names &row, const Names &names) {
  std::string out;
  for (const auto &name : names)
    out += (out.empty() ? "" : " ") +
           row[std::ranges::find(COLUMNS, name) - COLUMNS.begin()];
  return out;
}

int main() {
  for (const auto &fd : CANDIDATES) {
    const auto arrow = fd.find("->");
    const Names lhs = words(fd.substr(0, arrow)),
                rhs = words(fd.substr(arrow + 2));
    std::string verdict =
        std::format("not refuted by these {} rows", ROWS.size());
    // The first row seen for each value of X.
    std::map<std::string, std::pair<int, std::string>> first;
    for (int number = 1; number <= static_cast<int>(ROWS.size()); number++) {
      const auto key = values(ROWS[number - 1], lhs);
      const auto value = values(ROWS[number - 1], rhs);
      const auto &[seen, before] =
          first.try_emplace(key, number, value).first->second;
      if (before != value) {
        verdict = std::format("refuted by rows {} and {}: {} gives {} and {}",
                              seen, number, key, before, value);
        break;
      }
    }
    std::println("{:<24} {}", fd, verdict);
  }
}

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

// Two rows that agree on X and differ on Y refute X -> Y.
string[] columns = ["roll_no", "student", "course", "instructor", "grade"];
string[][] rows =
[
    ["101", "Aarav", "CS301", "Iyer", "A"],
    ["101", "Aarav", "CS302", "Sen", "B"],
    ["102", "Diya", "CS301", "Iyer", "A"],
    ["102", "Diya", "CS303", "Iyer", "B"],
    ["103", "Kabir", "CS301", "Iyer", "B"],
    ["103", "Kabir", "CS302", "Sen", "C"],
    ["104", "Meera", "CS303", "Iyer", "A"],
    ["104", "Meera", "CS304", "Khan", "A"],
];
string[] candidates =
[
    "roll_no -> student",
    "course -> instructor",
    "instructor -> course",
    "student -> roll_no",
    "course -> grade",
    "roll_no course -> grade",
];

foreach (string fd in candidates)
{
    string[] sides = fd.Split("->");
    string[] lhs = Words(sides[0]), rhs = Words(sides[1]);
    string verdict = FormattableString.Invariant($"not refuted by these {rows.Length} rows");
    // The first row seen for each value of X.
    var first = new Dictionary<string, (int Number, string Value)>();
    for (int number = 1; number <= rows.Length; number++)
    {
        string key = Values(columns, rows[number - 1], lhs);
        string value = Values(columns, rows[number - 1], rhs);
        first.TryAdd(key, (number, value));
        var (seen, before) = first[key];
        if (before != value)
        {
            verdict = FormattableString.Invariant(
                $"refuted by rows {seen} and {number}: {key} gives {before} and {value}"
            );
            break;
        }
    }
    Console.WriteLine($"{fd,-24} {verdict}");
}

static string[] Words(string text) => text.Split(' ', StringSplitOptions.RemoveEmptyEntries);

static string Values(string[] columns, string[] row, string[] names) =>
    string.Join(" ", names.Select(name => row[Array.IndexOf(columns, name)]));

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>
#include <string.h>

// Two rows that agree on X and differ on Y refute X -> Y.
enum { NCOLS = 5, NROWS = 8, TEXT = 64 };
static const char *const COLUMNS[NCOLS] = {"roll_no", "student", "course",
                                           "instructor", "grade"};
static const char *const ROWS[NROWS][NCOLS] = {
    {"101", "Aarav", "CS301", "Iyer", "A"},
    {"101", "Aarav", "CS302", "Sen", "B"},
    {"102", "Diya", "CS301", "Iyer", "A"},
    {"102", "Diya", "CS303", "Iyer", "B"},
    {"103", "Kabir", "CS301", "Iyer", "B"},
    {"103", "Kabir", "CS302", "Sen", "C"},
    {"104", "Meera", "CS303", "Iyer", "A"},
    {"104", "Meera", "CS304", "Khan", "A"},
};
static const char *const CANDIDATES[] = {
    "roll_no -> student", "course -> instructor", "instructor -> course",
    "student -> roll_no", "course -> grade",      "roll_no course -> grade"};

// Writes the row's values of the named columns ("roll_no course") to out.
static char *values(const char *const *row, const char *names, char *out) {
  char copy[TEXT];
  strcpy(copy, names);
  out[0] = '\0';
  for (char *name = strtok(copy, " "); name; name = strtok(nullptr, " "))
    for (int c = 0; c < NCOLS; c++)
      if (strcmp(COLUMNS[c], name) == 0)
        strcat(strcat(out, out[0] ? " " : ""), row[c]);
  return out;
}

int main(void) {
  for (size_t f = 0; f < sizeof CANDIDATES / sizeof CANDIDATES[0]; f++) {
    char lhs[TEXT], verdict[4 * TEXT], key[TEXT], value[TEXT];
    const char *arrow = strstr(CANDIDATES[f], "->");
    snprintf(lhs, sizeof lhs, "%.*s", (int)(arrow - CANDIDATES[f]),
             CANDIDATES[f]);
    snprintf(verdict, sizeof verdict, "not refuted by these %d rows", NROWS);
    // The first row seen for each value of X.
    struct {
      char key[TEXT], value[TEXT];
      int number;
    } first[NROWS];
    int seen = 0;
    for (int number = 1; number <= NROWS; number++) {
      values(ROWS[number - 1], lhs, key);
      values(ROWS[number - 1], arrow + 2, value);
      int k = 0;
      while (k < seen && strcmp(first[k].key, key) != 0)
        k++;
      if (k == seen) {
        strcpy(first[k].key, key);
        strcpy(first[k].value, value);
        first[seen++].number = number;
      } else if (strcmp(first[k].value, value) != 0) {
        snprintf(verdict, sizeof verdict,
                 "refuted by rows %d and %d: %s gives %s and %s",
                 first[k].number, number, key, first[k].value, value);
        break;
      }
    }
    printf("%-24s %s\n", CANDIDATES[f], verdict);
  }
  return 0;
}

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

// Two rows that agree on X and differ on Y refute X -> Y.
const COLUMNS = ['roll_no', 'student', 'course', 'instructor', 'grade'];
const ROWS = [
    ['101', 'Aarav', 'CS301', 'Iyer', 'A'],
    ['101', 'Aarav', 'CS302', 'Sen', 'B'],
    ['102', 'Diya', 'CS301', 'Iyer', 'A'],
    ['102', 'Diya', 'CS303', 'Iyer', 'B'],
    ['103', 'Kabir', 'CS301', 'Iyer', 'B'],
    ['103', 'Kabir', 'CS302', 'Sen', 'C'],
    ['104', 'Meera', 'CS303', 'Iyer', 'A'],
    ['104', 'Meera', 'CS304', 'Khan', 'A'],
];
const CANDIDATES = [
    'roll_no -> student',
    'course -> instructor',
    'instructor -> course',
    'student -> roll_no',
    'course -> grade',
    'roll_no course -> grade',
];

/**
 * @param list<string> $row
 * @param list<string> $names
 */
function values(array $row, array $names): string
{
    $cell = fn(string $name): string => $row[array_search($name, COLUMNS, true)];
    return implode(' ', array_map($cell, $names));
}

foreach (CANDIDATES as $fd) {
    [$lhs, $rhs] = array_map(fn(string $side) => explode(' ', trim($side)), explode('->', $fd));
    $verdict = 'not refuted by these ' . count(ROWS) . ' rows';
    $first = []; // The first row seen for each value of X.
    foreach (ROWS as $index => $row) {
        $key = values($row, $lhs);
        $value = values($row, $rhs);
        $first[$key] ??= [$index + 1, $value];
        [$seen, $before] = $first[$key];
        if ($before !== $value) {
            $number = $index + 1;
            $verdict = "refuted by rows {$seen} and {$number}: {$key} gives {$before} and {$value}";
            break;
        }
    }
    printf("%-24s %s\n", $fd, $verdict);
}

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

use std::collections::HashMap;

// Two rows that agree on X and differ on Y refute X -> Y.
const COLUMNS: [&str; 5] = ["roll_no", "student", "course", "instructor", "grade"];
const ROWS: [[&str; 5]; 8] = [
    ["101", "Aarav", "CS301", "Iyer", "A"],
    ["101", "Aarav", "CS302", "Sen", "B"],
    ["102", "Diya", "CS301", "Iyer", "A"],
    ["102", "Diya", "CS303", "Iyer", "B"],
    ["103", "Kabir", "CS301", "Iyer", "B"],
    ["103", "Kabir", "CS302", "Sen", "C"],
    ["104", "Meera", "CS303", "Iyer", "A"],
    ["104", "Meera", "CS304", "Khan", "A"],
];
const CANDIDATES: [&str; 6] = [
    "roll_no -> student",
    "course -> instructor",
    "instructor -> course",
    "student -> roll_no",
    "course -> grade",
    "roll_no course -> grade",
];

fn values(row: &[&str], names: &str) -> String {
    let picked: Vec<&str> = names
        .split_whitespace()
        .filter_map(|name| COLUMNS.iter().position(|c| *c == name).map(|i| row[i]))
        .collect();
    picked.join(" ")
}

fn main() {
    for fd in CANDIDATES {
        let (lhs, rhs) = fd.split_once("->").unwrap_or((fd, ""));
        let mut verdict = format!("not refuted by these {} rows", ROWS.len());
        // The first row seen for each value of X.
        let mut first: HashMap<String, (usize, String)> = HashMap::new();
        for (index, row) in ROWS.iter().enumerate() {
            let (key, value) = (values(row, lhs), values(row, rhs));
            let (seen, before) = first
                .entry(key.clone())
                .or_insert((index + 1, value.clone()));
            if *before != value {
                verdict = format!(
                    "refuted by rows {seen} and {}: {key} gives {before} and {value}",
                    index + 1
                );
                break;
            }
        }
        println!("{fd:<24} {verdict}");
    }
}

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

// Two rows that agree on X and differ on Y refute X -> Y.
const COLUMNS = ["roll_no", "student", "course", "instructor", "grade"];
const ROWS: string[][] = [
  ["101", "Aarav", "CS301", "Iyer", "A"],
  ["101", "Aarav", "CS302", "Sen", "B"],
  ["102", "Diya", "CS301", "Iyer", "A"],
  ["102", "Diya", "CS303", "Iyer", "B"],
  ["103", "Kabir", "CS301", "Iyer", "B"],
  ["103", "Kabir", "CS302", "Sen", "C"],
  ["104", "Meera", "CS303", "Iyer", "A"],
  ["104", "Meera", "CS304", "Khan", "A"],
];
const CANDIDATES = [
  "roll_no -> student",
  "course -> instructor",
  "instructor -> course",
  "student -> roll_no",
  "course -> grade",
  "roll_no course -> grade",
];

const values = (row: string[], names: string[]): string =>
  names.map((name) => row[COLUMNS.indexOf(name)]).join(" ");

for (const fd of CANDIDATES) {
  const [lhs, rhs] = fd.split("->").map((side) => side.trim().split(" "));
  let verdict = `not refuted by these ${ROWS.length} rows`;
  // The first row seen for each value of X.
  const first = new Map<string, [number, string]>();
  for (const [index, row] of ROWS.entries()) {
    const [key, value] = [values(row, lhs), values(row, rhs)];
    if (!first.has(key)) first.set(key, [index + 1, value]);
    const [seen, before] = first.get(key) ?? [index + 1, value];
    if (before !== value) {
      verdict = `refuted by rows ${seen} and ${index + 1}: ${key} gives ${before} and ${value}`;
      break;
    }
  }
  console.log(`${fd.padEnd(24)} ${verdict}`);
}

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"slices"
	"strings"
)

// Two rows that agree on X and differ on Y refute X -> Y.
var columns = []string{"roll_no", "student", "course", "instructor", "grade"}

var rows = [][]string{
	{"101", "Aarav", "CS301", "Iyer", "A"},
	{"101", "Aarav", "CS302", "Sen", "B"},
	{"102", "Diya", "CS301", "Iyer", "A"},
	{"102", "Diya", "CS303", "Iyer", "B"},
	{"103", "Kabir", "CS301", "Iyer", "B"},
	{"103", "Kabir", "CS302", "Sen", "C"},
	{"104", "Meera", "CS303", "Iyer", "A"},
	{"104", "Meera", "CS304", "Khan", "A"},
}

var candidates = []string{
	"roll_no -> student",
	"course -> instructor",
	"instructor -> course",
	"student -> roll_no",
	"course -> grade",
	"roll_no course -> grade",
}

func values(row []string, names string) string {
	var picked []string
	for _, name := range strings.Fields(names) {
		picked = append(picked, row[slices.Index(columns, name)])
	}
	return strings.Join(picked, " ")
}

type seen struct {
	number int
	value  string
}

func main() {
	for _, fd := range candidates {
		lhs, rhs, _ := strings.Cut(fd, "->")
		verdict := fmt.Sprintf("not refuted by these %d rows", len(rows))
		// The first row seen for each value of X.
		first := map[string]seen{}
		for index, row := range rows {
			key, value := values(row, lhs), values(row, rhs)
			if _, ok := first[key]; !ok {
				first[key] = seen{index + 1, value}
			}
			if s := first[key]; s.value != value {
				verdict = fmt.Sprintf("refuted by rows %d and %d: %s gives %s and %s",
					s.number, index+1, key, s.value, value)
				break
			}
		}
		fmt.Printf("%-24s %s\n", fd, verdict)
	}
}

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

// Two rows that agree on X and differ on Y refute X -> Y.
let columns = ["roll_no", "student", "course", "instructor", "grade"]
let rows = [
  ["101", "Aarav", "CS301", "Iyer", "A"],
  ["101", "Aarav", "CS302", "Sen", "B"],
  ["102", "Diya", "CS301", "Iyer", "A"],
  ["102", "Diya", "CS303", "Iyer", "B"],
  ["103", "Kabir", "CS301", "Iyer", "B"],
  ["103", "Kabir", "CS302", "Sen", "C"],
  ["104", "Meera", "CS303", "Iyer", "A"],
  ["104", "Meera", "CS304", "Khan", "A"],
]
let candidates = [
  "roll_no -> student",
  "course -> instructor",
  "instructor -> course",
  "student -> roll_no",
  "course -> grade",
  "roll_no course -> grade",
]

func values(_ row: [String], _ names: Substring) -> String {
  names.split(separator: " ").compactMap { name in
    columns.firstIndex(of: String(name)).map { row[$0] }
  }.joined(separator: " ")
}

for fd in candidates {
  let arrow = fd.firstIndex(of: "-") ?? fd.endIndex
  let sides = [fd[..<arrow], fd[arrow...].dropFirst(2)]
  var verdict = "not refuted by these \(rows.count) rows"
  // The first row seen for each value of X.
  var firstRows: [(key: String, number: Int, value: String)] = []
  for (index, row) in rows.enumerated() {
    let key = values(row, sides[0])
    let value = values(row, sides[1])
    guard let seen = firstRows.first(where: { $0.key == key }) else {
      firstRows.append((key, index + 1, value))
      continue
    }
    if seen.value != value {
      verdict =
        "refuted by rows \(seen.number) and \(index + 1): \(key) gives \(seen.value) and \(value)"
      break
    }
  }
  print(fd + String(repeating: " ", count: max(0, 24 - fd.count)) + " " + verdict)
}

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

# Two rows that agree on X and differ on Y refute X -> Y.
COLUMNS = %w[roll_no student course instructor grade].freeze
ROWS = [
  %w[101 Aarav CS301 Iyer A],
  %w[101 Aarav CS302 Sen B],
  %w[102 Diya CS301 Iyer A],
  %w[102 Diya CS303 Iyer B],
  %w[103 Kabir CS301 Iyer B],
  %w[103 Kabir CS302 Sen C],
  %w[104 Meera CS303 Iyer A],
  %w[104 Meera CS304 Khan A]
].freeze
CANDIDATES = [
  'roll_no -> student',
  'course -> instructor',
  'instructor -> course',
  'student -> roll_no',
  'course -> grade',
  'roll_no course -> grade'
].freeze

def values(row, names)
  names.split.map { |name| row[COLUMNS.index(name)] }.join(' ')
end

def verdict(lhs, rhs)
  first = {} # The first row seen for each value of X.
  ROWS.each.with_index(1) do |row, number|
    key = values(row, lhs)
    value = values(row, rhs)
    seen, before = first[key] ||= [number, value]
    next if before == value

    return "refuted by rows #{seen} and #{number}: #{key} gives #{before} and #{value}"
  end
  "not refuted by these #{ROWS.size} rows"
end

CANDIDATES.each do |fd|
  puts "#{fd.ljust(24)} #{verdict(*fd.split('->'))}"
end

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

// Two rows that agree on X and differ on Y refute X -> Y.
val columns = listOf("roll_no", "student", "course", "instructor", "grade")
val rows =
    listOf(
        listOf("101", "Aarav", "CS301", "Iyer", "A"),
        listOf("101", "Aarav", "CS302", "Sen", "B"),
        listOf("102", "Diya", "CS301", "Iyer", "A"),
        listOf("102", "Diya", "CS303", "Iyer", "B"),
        listOf("103", "Kabir", "CS301", "Iyer", "B"),
        listOf("103", "Kabir", "CS302", "Sen", "C"),
        listOf("104", "Meera", "CS303", "Iyer", "A"),
        listOf("104", "Meera", "CS304", "Khan", "A"),
    )
val candidates =
    listOf(
        "roll_no -> student",
        "course -> instructor",
        "instructor -> course",
        "student -> roll_no",
        "course -> grade",
        "roll_no course -> grade",
    )

fun values(
    row: List<String>,
    names: String,
) = names.trim().split(" ").joinToString(" ") { row[columns.indexOf(it)] }

fun main() {
    for (fd in candidates) {
        val (lhs, rhs) = fd.split("->")
        var verdict = "not refuted by these ${rows.size} rows"
        // The first row seen for each value of X.
        val first = mutableMapOf<String, Pair<Int, String>>()
        for ((index, row) in rows.withIndex()) {
            val key = values(row, lhs)
            val value = values(row, rhs)
            val (seen, before) = first.getOrPut(key) { (index + 1) to value }
            if (before != value) {
                verdict = "refuted by rows $seen and ${index + 1}: $key gives $before and $value"
                break
            }
        }
        println("${fd.padEnd(24)} $verdict")
    }
}

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

// Two rows that agree on X and differ on Y refute X -> Y.
const columns = ['roll_no', 'student', 'course', 'instructor', 'grade'];
const rows = [
  ['101', 'Aarav', 'CS301', 'Iyer', 'A'],
  ['101', 'Aarav', 'CS302', 'Sen', 'B'],
  ['102', 'Diya', 'CS301', 'Iyer', 'A'],
  ['102', 'Diya', 'CS303', 'Iyer', 'B'],
  ['103', 'Kabir', 'CS301', 'Iyer', 'B'],
  ['103', 'Kabir', 'CS302', 'Sen', 'C'],
  ['104', 'Meera', 'CS303', 'Iyer', 'A'],
  ['104', 'Meera', 'CS304', 'Khan', 'A'],
];
const candidates = [
  'roll_no -> student',
  'course -> instructor',
  'instructor -> course',
  'student -> roll_no',
  'course -> grade',
  'roll_no course -> grade',
];

String values(List<String> row, String names) =>
    names.trim().split(' ').map((name) => row[columns.indexOf(name)]).join(' ');

void main() {
  for (final fd in candidates) {
    final [lhs, rhs] = fd.split('->');
    var verdict = 'not refuted by these ${rows.length} rows';
    // The first row seen for each value of X.
    final first = <String, (int, String)>{};
    for (final (index, row) in rows.indexed) {
      final key = values(row, lhs);
      final value = values(row, rhs);
      final (seen, before) = first.putIfAbsent(key, () => (index + 1, value));
      if (before != value) {
        verdict =
            'refuted by rows $seen and ${index + 1}: '
            '$key gives $before and $value';
        break;
      }
    }
    print('${fd.padRight(24)} $verdict');
  }
}

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

roll_no -> student       not refuted by these 8 rows
course -> instructor     not refuted by these 8 rows
instructor -> course     refuted by rows 1 and 4: Iyer gives CS301 and CS303
student -> roll_no       not refuted by these 8 rows
course -> grade          refuted by rows 1 and 5: CS301 gives A and B
roll_no course -> grade  not refuted by these 8 rows

Two candidates fail. Iyer teaches two courses, so instructor -> course is false, and CS301 has the grades A and B, so course -> grade is false. The other four survive, but surviving proves nothing. student -> roll_no holds on these rows only because no two students here share a name: a ninth student called Diya would break it, and nothing about names forbids her. Whether a dependency holds is a question about the application. Decide it from what the attributes mean, and use the rows only to hunt for counterexamples.

Codes that carry a dependency

Some identifiers are built to determine something. An Indian Financial System Code (IFSC) has 11 characters, and the Reserve Bank of India’s guidance on NEFT says that the first four letters represent the bank and the last six the branch (RBI: NEFT FAQ). So ifsc -> bank holds by design, in every legal table.

Checkpoint

Check: Refuting a dependency with rows

Question 1 of 2 Rows 2 and 6 of the sheet are (101, Aarav, CS302, Sen, B) and (103, Kabir, CS302, Sen, C) over (roll_no, student, course, instructor, grade). Which candidate do they refute?
Choose one answer.

instructor -> course roll_no course -> grade student -> roll_no course -> grade

Show the answer: Question 1 of 2

Answer: course -> grade

A pair refutes X -> Y only when it agrees on all of X and differs on Y. Rows 2 and 6 agree on the course and the instructor and differ on the grade, so they refute course -> grade, as rows 1 and 5 did.
Question 2 of 2 A ninth row (105, Diya, CS304, Khan, B) joins the 8 rows of the sheet. Which of the four candidates that survived the 8 rows does it break?
Choose one answer.

student -> roll_no roll_no -> student None, because a dependency that survived 8 rows is proved course -> instructor

Show the answer: Question 2 of 2

Answer: student -> roll_no

The four survivors were roll_no -> student, course -> instructor, student -> roll_no and roll_no course -> grade. Only student -> roll_no meets a pair that agrees on its left-hand side and differs on its right: a second Diya.

Armstrong’s three axioms derive every implied dependency

Known dependencies imply others: from roll_no -> student and student -> hostel, roll_no -> hostel must hold too. Armstrong’s axioms, named after W. W. Armstrong, who stated them for database relations, derive such consequences with three rules:

Reflexivity. If Y is part of X, then X -> Y.
Augmentation. From X -> Y, conclude XZ -> YZ, for any attributes Z.
Transitivity. From X -> Y and Y -> Z, conclude X -> Z.

The rules are sound: everything they derive holds in every table that satisfies the known dependencies. They are also complete: every dependency that holds in all such tables can be derived. Three more rules follow from the axioms and save steps. Union combines X -> Y and X -> Z into X -> YZ. Decomposition splits X -> YZ into X -> Y. Pseudotransitivity turns X -> Y and WY -> Z into WX -> Z.

A derivation is a list of lines, each one a known dependency or the result of one rule applied to earlier lines. Step through a derivation of AD -> E from F = {A -> B, B -> C, CD -> E}, and a seventh line that tempts:

Interactive · step by step Deriving AD -> E from F, one rule per line Step through the seven lines. Each arrow goes from a line to a line that one rule derives from it.

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text

Three given rules. F gives A -> B, B -> C and CD -> E, and the target is AD -> E. Every new line must follow from earlier lines by one named rule.
Transitivity. Lines 1 and 2 chain. A fixes B and B fixes C, so line 3, A -> C, follows by transitivity.
Augmentation. Augmenting line 3 with D adds D to both sides, which gives line 4, AD -> CD.
The target. Lines 4 and 5 chain, AD -> CD and CD -> E, into line 6, AD -> E. Every line passed its check, so the target is proved.
A step that fails. Line 7 tries to drop D from CD -> E. Augmentation only adds the same attributes to both sides, so no rule turns CD -> E into C -> E. Knowing C alone need not fix E.

The checker below tests every line of the same derivation, so a wrong step is caught where it happens:

One program · 14 languages A derivation checked line by line, and a step that fails

Python 3.14 · main.py

# Sets of attributes are bit masks.
A, B, C, D, E = 1, 2, 4, 8, 16
F = [(A, B), (B, C), (C | D, E)]
PROOF = [
    ((A, B), "given", []),
    ((B, C), "given", []),
    ((A, C), "transitivity", [1, 2]),
    ((A | D, C | D), "augmentation", [3]),
    ((C | D, E), "given", []),
    ((A | D, E), "transitivity", [4, 5]),
    ((C, E), "augmentation", [5]),
]


def letters(mask: int) -> str:
    return "".join(name for i, name in enumerate("ABCDE") if mask >> i & 1)


def follows(dep: tuple[int, int], rule: str, refs: list[tuple[int, int]]) -> bool:
    x, y = dep
    if rule == "given":
        return not refs and dep in F
    if rule == "augmentation" and len(refs) == 1:
        a, b = refs[0]
        return a & x == a and b & y == b and x & ~a & ~y == 0 and y & ~b & ~x == 0
    if rule == "transitivity" and len(refs) == 2:
        (a, b), (c, d) = refs
        return a == x and b == c and d == y
    return False


proved: list[bool] = []
for number, (dep, rule, refs) in enumerate(PROOF, start=1):
    cited = [PROOF[r - 1][0] for r in refs if r < number and proved[r - 1]]
    ok = len(cited) == len(refs) and follows(dep, rule, cited)
    proved.append(ok)
    shown = f"{letters(dep[0])} -> {letters(dep[1])}"
    where = f"{rule} {', '.join(map(str, refs))}".strip()
    print(f"  {number}. {shown:<9} {where:<18} {'ok' if ok else 'does not follow'}")

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

// Sets of attributes are bit masks.
const [A, B, C, D, E] = [1, 2, 4, 8, 16];
const F = [
  [A, B],
  [B, C],
  [C | D, E],
];
const PROOF = [
  [[A, B], "given", []],
  [[B, C], "given", []],
  [[A, C], "transitivity", [1, 2]],
  [[A | D, C | D], "augmentation", [3]],
  [[C | D, E], "given", []],
  [[A | D, E], "transitivity", [4, 5]],
  [[C, E], "augmentation", [5]],
];

const letters = (mask) => [..."ABCDE"].filter((_, i) => (mask >> i) & 1).join("");

function follows([x, y], rule, refs) {
  if (rule === "given") return refs.length === 0 && F.some(([a, b]) => a === x && b === y);
  if (rule === "augmentation" && refs.length === 1) {
    const [[a, b]] = refs;
    return (a & x) === a && (b & y) === b && (x & ~a & ~y) === 0 && (y & ~b & ~x) === 0;
  }
  if (rule === "transitivity" && refs.length === 2) {
    const [[a, b], [c, d]] = refs;
    return a === x && b === c && d === y;
  }
  return false;
}

const proved = [];
for (const [index, [dep, rule, refs]] of PROOF.entries()) {
  const cited = refs.filter((r) => r <= index && proved[r - 1]).map((r) => PROOF[r - 1][0]);
  const ok = cited.length === refs.length && follows(dep, rule, cited);
  proved.push(ok);
  const shown = `${letters(dep[0])} -> ${letters(dep[1])}`;
  const where = `${rule} ${refs.join(", ")}`.trim();
  console.log(
    `  ${index + 1}. ${shown.padEnd(9)} ${where.padEnd(18)} ${ok ? "ok" : "does not follow"}`,
  );
}

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

public class Main {
  // Sets of attributes are bit masks.
  static final int A = 1, B = 2, C = 4, D = 8, E = 16;

  record Fd(int lhs, int rhs) {}

  record Line(Fd dep, String rule, int... refs) {}

  static final List<Fd> F = List.of(new Fd(A, B), new Fd(B, C), new Fd(C | D, E));
  static final List<Line> PROOF =
      List.of(
          new Line(new Fd(A, B), "given"),
          new Line(new Fd(B, C), "given"),
          new Line(new Fd(A, C), "transitivity", 1, 2),
          new Line(new Fd(A | D, C | D), "augmentation", 3),
          new Line(new Fd(C | D, E), "given"),
          new Line(new Fd(A | D, E), "transitivity", 4, 5),
          new Line(new Fd(C, E), "augmentation", 5));

  static String letters(int mask) {
    var out = new StringBuilder();
    for (int i = 0; i < 5; i++) {
      if ((mask >> i & 1) == 1) {
        out.append("ABCDE".charAt(i));
      }
    }
    return out.toString();
  }

  static boolean follows(Fd dep, String rule, List<Fd> refs) {
    int x = dep.lhs(), y = dep.rhs();
    if (rule.equals("given")) {
      return refs.isEmpty() && F.contains(dep);
    }
    if (rule.equals("augmentation") && refs.size() == 1) {
      int a = refs.get(0).lhs(), b = refs.get(0).rhs();
      return (a & x) == a && (b & y) == b && (x & ~a & ~y) == 0 && (y & ~b & ~x) == 0;
    }
    if (rule.equals("transitivity") && refs.size() == 2) {
      Fd p = refs.get(0), q = refs.get(1);
      return p.lhs() == x && p.rhs() == q.lhs() && q.rhs() == y;
    }
    return false;
  }

  public static void main(String[] args) {
    Locale.setDefault(Locale.ROOT);
    var proved = new ArrayList<Boolean>();
    for (int n = 1; n <= PROOF.size(); n++) {
      Line line = PROOF.get(n - 1);
      var cited = new ArrayList<Fd>();
      var where = new StringBuilder(line.rule());
      for (int k = 0; k < line.refs().length; k++) {
        int r = line.refs()[k];
        if (r < n && proved.get(r - 1)) {
          cited.add(PROOF.get(r - 1).dep());
        }
        where.append(k == 0 ? " " : ", ").append(r);
      }
      boolean ok = cited.size() == line.refs().length && follows(line.dep(), line.rule(), cited);
      proved.add(ok);
      String shown = letters(line.dep().lhs()) + " -> " + letters(line.dep().rhs());
      System.out.printf("  %d. %-9s %-18s %s%n", n, shown, where, ok ? "ok" : "does not follow");
    }
  }
}

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <print>
#include <string>
#include <utility>
#include <vector>

// Sets of attributes are bit masks.
enum : unsigned { A = 1, B = 2, C = 4, D = 8, E = 16 };
using Fd = std::pair<unsigned, unsigned>;

struct Line {
  Fd dep;
  std::string rule;
  std::vector<int> refs;
};

const std::vector<Fd> F = {{A, B}, {B, C}, {C | D, E}};
const std::vector<Line> PROOF = {
    {{A, B}, "given", {}},
    {{B, C}, "given", {}},
    {{A, C}, "transitivity", {1, 2}},
    {{A | D, C | D}, "augmentation", {3}},
    {{C | D, E}, "given", {}},
    {{A | D, E}, "transitivity", {4, 5}},
    {{C, E}, "augmentation", {5}},
};

std::string letters(unsigned mask) {
  std::string out;
  for (int i = 0; i < 5; i++)
    if (mask >> i & 1)
      out += "ABCDE"[i];
  return out;
}

bool follows(Fd dep, const std::string &rule, const std::vector<Fd> &refs) {
  const auto [x, y] = dep;
  if (rule == "given")
    return refs.empty() && std::ranges::contains(F, dep);
  if (rule == "augmentation" && refs.size() == 1) {
    const auto [a, b] = refs[0];
    return (a & x) == a && (b & y) == b && (x & ~a & ~y) == 0 &&
           (y & ~b & ~x) == 0;
  }
  if (rule == "transitivity" && refs.size() == 2)
    return refs[0].first == x && refs[0].second == refs[1].first &&
           refs[1].second == y;
  return false;
}

int main() {
  std::vector<bool> proved;
  for (std::size_t i = 0; i < PROOF.size(); i++) {
    const auto &[dep, rule, refs] = PROOF[i];
    std::vector<Fd> cited;
    std::string where = rule;
    for (std::size_t k = 0; k < refs.size(); k++) {
      const auto r = static_cast<std::size_t>(refs[k]);
      if (r <= i && proved[r - 1])
        cited.push_back(PROOF[r - 1].dep);
      where += (k ? ", " : " ") + std::to_string(r);
    }
    proved.push_back(cited.size() == refs.size() && follows(dep, rule, cited));
    std::println("  {}. {:<9} {:<18} {}", i + 1,
                 letters(dep.first) + " -> " + letters(dep.second), where,
                 proved.back() ? "ok" : "does not follow");
  }
}

C# 14 · .NET 10 · app.cs

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

// Sets of attributes are bit masks.
const int A = 1, B = 2, C = 4, D = 8, E = 16;
Fd[] f = [new(A, B), new(B, C), new(C | D, E)];
Line[] proof =
[
    new(new(A, B), "given", []),
    new(new(B, C), "given", []),
    new(new(A, C), "transitivity", [1, 2]),
    new(new(A | D, C | D), "augmentation", [3]),
    new(new(C | D, E), "given", []),
    new(new(A | D, E), "transitivity", [4, 5]),
    new(new(C, E), "augmentation", [5]),
];

var proved = new List<bool>();
for (int number = 1; number <= proof.Length; number++)
{
    var (dep, rule, refs) = proof[number - 1];
    Fd[] cited = [.. refs.Where(r => r < number && proved[r - 1]).Select(r => proof[r - 1].Dep)];
    bool ok = cited.Length == refs.Length && Follows(dep, rule, cited, f);
    proved.Add(ok);
    string shown = $"{Letters(dep.Lhs)} -> {Letters(dep.Rhs)}";
    string where = $"{rule} {string.Join(", ", refs)}".Trim();
    Console.WriteLine($"  {number}. {shown,-9} {where,-18} {(ok ? "ok" : "does not follow")}");
}

static string Letters(int mask) =>
    string.Concat("ABCDE".Where((_, i) => (mask >> i & 1) == 1));

static bool Follows(Fd dep, string rule, Fd[] refs, Fd[] given)
{
    var (x, y) = dep;
    return (rule, refs) switch
    {
        ("given", []) => given.Contains(dep),
        ("augmentation", [var (a, b)]) =>
            (a & x) == a && (b & y) == b && (x & ~a & ~y) == 0 && (y & ~b & ~x) == 0,
        ("transitivity", [var (a, b), var (c, d)]) => a == x && b == c && d == y,
        _ => false,
    };
}

record Fd(int Lhs, int Rhs);

record Line(Fd Dep, string Rule, int[] Refs);

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>
#include <string.h>

// Sets of attributes are bit masks.
enum { A = 1, B = 2, C = 4, D = 8, E = 16 };

typedef struct {
  unsigned lhs, rhs;
} Fd;
typedef struct {
  Fd dep;
  const char *rule;
  int refs[3]; // the earlier lines it cites; 0 ends the list
} Line;

static const Fd F[] = {{A, B}, {B, C}, {C | D, E}};
static const Line PROOF[] = {
    {{A, B}, "given", {0}},           {{B, C}, "given", {0}},
    {{A, C}, "transitivity", {1, 2}}, {{A | D, C | D}, "augmentation", {3}},
    {{C | D, E}, "given", {0}},       {{A | D, E}, "transitivity", {4, 5}},
    {{C, E}, "augmentation", {5}},
};

static void letters(unsigned mask, char *out) {
  for (int i = 0; i < 5; i++)
    if (mask >> i & 1)
      *out++ = "ABCDE"[i];
  *out = '\0';
}

static bool follows(Fd dep, const char *rule, const Fd *refs, int n) {
  const unsigned x = dep.lhs, y = dep.rhs;
  if (strcmp(rule, "given") == 0 && n == 0) {
    for (int i = 0; i < 3; i++)
      if (F[i].lhs == x && F[i].rhs == y)
        return true;
  } else if (strcmp(rule, "augmentation") == 0 && n == 1) {
    const unsigned a = refs[0].lhs, b = refs[0].rhs;
    return (a & x) == a && (b & y) == b && (x & ~a & ~y) == 0 &&
           (y & ~b & ~x) == 0;
  } else if (strcmp(rule, "transitivity") == 0 && n == 2) {
    return refs[0].lhs == x && refs[0].rhs == refs[1].lhs && refs[1].rhs == y;
  }
  return false;
}

int main(void) {
  bool proved[7];
  for (int i = 0; i < 7; i++) {
    const Line *line = &PROOF[i];
    Fd cited[2];
    int k = 0, n = 0;
    char where[32], shown[16], rhs[8];
    int at = snprintf(where, sizeof where, "%s", line->rule);
    for (; line->refs[k] != 0; k++) {
      const int r = line->refs[k];
      if (r <= i && proved[r - 1])
        cited[n++] = PROOF[r - 1].dep;
      at += snprintf(where + at, sizeof where - at, "%s%d", k ? ", " : " ", r);
    }
    proved[i] = n == k && follows(line->dep, line->rule, cited, n);
    letters(line->dep.lhs, shown);
    letters(line->dep.rhs, rhs);
    printf("  %d. %-9s %-18s %s\n", i + 1, strcat(strcat(shown, " -> "), rhs),
           where, proved[i] ? "ok" : "does not follow");
  }
  return 0;
}

PHP 8.5 · main.php

<?php

declare(strict_types=1);

// Sets of attributes are bit masks.
const A = 1, B = 2, C = 4, D = 8, E = 16;
const F = [[A, B], [B, C], [C | D, E]];
const PROOF = [
    [[A, B], 'given', []],
    [[B, C], 'given', []],
    [[A, C], 'transitivity', [1, 2]],
    [[A | D, C | D], 'augmentation', [3]],
    [[C | D, E], 'given', []],
    [[A | D, E], 'transitivity', [4, 5]],
    [[C, E], 'augmentation', [5]],
];

function letters(int $mask): string
{
    $out = '';
    foreach (str_split('ABCDE') as $i => $name) {
        $out .= ($mask >> $i & 1) === 1 ? $name : '';
    }
    return $out;
}

/**
 * @param array{int, int} $dep
 * @param list<array{int, int}> $refs
 */
function follows(array $dep, string $rule, array $refs): bool
{
    [$x, $y] = $dep;
    [$a, $b] = $refs[0] ?? [0, 0];
    [$c, $d] = $refs[1] ?? [0, 0];
    return match ([$rule, count($refs)]) {
        ['given', 0] => in_array($dep, F, true),
        ['augmentation', 1] => ($a & $x) === $a && ($b & $y) === $b
            && ($x & ~$a & ~$y) === 0 && ($y & ~$b & ~$x) === 0,
        ['transitivity', 2] => $a === $x && $b === $c && $d === $y,
        default => false,
    };
}

$proved = [];
foreach (PROOF as $index => [$dep, $rule, $refs]) {
    $cited = [];
    foreach ($refs as $r) {
        if ($r <= $index && $proved[$r - 1]) {
            $cited[] = PROOF[$r - 1][0];
        }
    }
    $ok = count($cited) === count($refs) && follows($dep, $rule, $cited);
    $proved[] = $ok;
    $shown = letters($dep[0]) . ' -> ' . letters($dep[1]);
    $where = trim($rule . ' ' . implode(', ', $refs));
    $verdict = $ok ? 'ok' : 'does not follow';
    printf("  %d. %-9s %-18s %s\n", $index + 1, $shown, $where, $verdict);
}

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

// Sets of attributes are bit masks.
const A: u32 = 1;
const B: u32 = 2;
const C: u32 = 4;
const D: u32 = 8;
const E: u32 = 16;
type Fd = (u32, u32);

const F: [Fd; 3] = [(A, B), (B, C), (C | D, E)];
const PROOF: [(Fd, &str, &[usize]); 7] = [
    ((A, B), "given", &[]),
    ((B, C), "given", &[]),
    ((A, C), "transitivity", &[1, 2]),
    ((A | D, C | D), "augmentation", &[3]),
    ((C | D, E), "given", &[]),
    ((A | D, E), "transitivity", &[4, 5]),
    ((C, E), "augmentation", &[5]),
];

fn letters(mask: u32) -> String {
    "ABCDE"
        .chars()
        .enumerate()
        .filter(|&(i, _)| mask >> i & 1 == 1)
        .map(|(_, name)| name)
        .collect()
}

fn follows((x, y): Fd, rule: &str, refs: &[Fd]) -> bool {
    match (rule, refs) {
        ("given", []) => F.contains(&(x, y)),
        ("augmentation", &[(a, b)]) => {
            a & x == a && b & y == b && x & !a & !y == 0 && y & !b & !x == 0
        }
        ("transitivity", &[(a, b), (c, d)]) => a == x && b == c && d == y,
        _ => false,
    }
}

fn main() {
    let mut proved: Vec<bool> = Vec::new();
    for (index, &(dep, rule, refs)) in PROOF.iter().enumerate() {
        let cited: Vec<Fd> = refs
            .iter()
            .filter(|&&r| r <= index && proved[r - 1])
            .map(|&r| PROOF[r - 1].0)
            .collect();
        let ok = cited.len() == refs.len() && follows(dep, rule, &cited);
        proved.push(ok);
        let shown = format!("{} -> {}", letters(dep.0), letters(dep.1));
        let numbers: Vec<String> = refs.iter().map(|r| r.to_string()).collect();
        let place = format!("{rule} {}", numbers.join(", "));
        let verdict = if ok { "ok" } else { "does not follow" };
        println!("  {}. {shown:<9} {:<18} {verdict}", index + 1, place.trim());
    }
}

TypeScript 6.0 · main.ts

// Sets of attributes are bit masks.
type Fd = [number, number];

const [A, B, C, D, E] = [1, 2, 4, 8, 16];
const F: Fd[] = [
  [A, B],
  [B, C],
  [C | D, E],
];
const PROOF: [Fd, string, number[]][] = [
  [[A, B], "given", []],
  [[B, C], "given", []],
  [[A, C], "transitivity", [1, 2]],
  [[A | D, C | D], "augmentation", [3]],
  [[C | D, E], "given", []],
  [[A | D, E], "transitivity", [4, 5]],
  [[C, E], "augmentation", [5]],
];

const letters = (mask: number): string => [..."ABCDE"].filter((_, i) => (mask >> i) & 1).join("");

function follows([x, y]: Fd, rule: string, refs: Fd[]): boolean {
  if (rule === "given") return refs.length === 0 && F.some(([a, b]) => a === x && b === y);
  if (rule === "augmentation" && refs.length === 1) {
    const [[a, b]] = refs;
    return (a & x) === a && (b & y) === b && (x & ~a & ~y) === 0 && (y & ~b & ~x) === 0;
  }
  if (rule === "transitivity" && refs.length === 2) {
    const [[a, b], [c, d]] = refs;
    return a === x && b === c && d === y;
  }
  return false;
}

const proved: boolean[] = [];
for (const [index, [dep, rule, refs]] of PROOF.entries()) {
  const cited = refs.filter((r) => r <= index && proved[r - 1]).map((r) => PROOF[r - 1][0]);
  const ok = cited.length === refs.length && follows(dep, rule, cited);
  proved.push(ok);
  const shown = `${letters(dep[0])} -> ${letters(dep[1])}`;
  const where = `${rule} ${refs.join(", ")}`.trim();
  console.log(
    `  ${index + 1}. ${shown.padEnd(9)} ${where.padEnd(18)} ${ok ? "ok" : "does not follow"}`,
  );
}

Go 1.27 · main.go

package main

import (
	"fmt"
	"slices"
	"strconv"
	"strings"
)

// Sets of attributes are bit masks.
const A, B, C, D, E = 1, 2, 4, 8, 16

type fd struct{ lhs, rhs int }

var f = []fd{{A, B}, {B, C}, {C | D, E}}

var proof = []struct {
	dep  fd
	rule string
	refs []int
}{
	{fd{A, B}, "given", nil},
	{fd{B, C}, "given", nil},
	{fd{A, C}, "transitivity", []int{1, 2}},
	{fd{A | D, C | D}, "augmentation", []int{3}},
	{fd{C | D, E}, "given", nil},
	{fd{A | D, E}, "transitivity", []int{4, 5}},
	{fd{C, E}, "augmentation", []int{5}},
}

func letters(mask int) string {
	var out strings.Builder
	for i, name := range "ABCDE" {
		if mask>>i&1 == 1 {
			out.WriteRune(name)
		}
	}
	return out.String()
}

func follows(d fd, rule string, refs []fd) bool {
	x, y := d.lhs, d.rhs
	switch {
	case rule == "given" && len(refs) == 0:
		return slices.Contains(f, d)
	case rule == "augmentation" && len(refs) == 1:
		a, b := refs[0].lhs, refs[0].rhs
		return a&x == a && b&y == b && x&^a&^y == 0 && y&^b&^x == 0
	case rule == "transitivity" && len(refs) == 2:
		return refs[0].lhs == x && refs[0].rhs == refs[1].lhs && refs[1].rhs == y
	}
	return false
}

func main() {
	var proved []bool
	for i, l := range proof {
		var cited []fd
		numbers := make([]string, len(l.refs))
		for k, r := range l.refs {
			if r <= i && proved[r-1] {
				cited = append(cited, proof[r-1].dep)
			}
			numbers[k] = strconv.Itoa(r)
		}
		ok := len(cited) == len(l.refs) && follows(l.dep, l.rule, cited)
		proved = append(proved, ok)
		shown := letters(l.dep.lhs) + " -> " + letters(l.dep.rhs)
		where := strings.TrimSpace(l.rule + " " + strings.Join(numbers, ", "))
		verdict := "does not follow"
		if ok {
			verdict = "ok"
		}
		fmt.Printf("  %d. %-9s %-18s %s\n", i+1, shown, where, verdict)
	}
}

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

// Sets of attributes are bit masks.
let (a, b, c, d, e) = (1, 2, 4, 8, 16)

struct Fd: Equatable {
  let lhs: Int
  let rhs: Int
}

let f = [Fd(lhs: a, rhs: b), Fd(lhs: b, rhs: c), Fd(lhs: c | d, rhs: e)]
let proof: [(dep: Fd, rule: String, refs: [Int])] = [
  (Fd(lhs: a, rhs: b), "given", []),
  (Fd(lhs: b, rhs: c), "given", []),
  (Fd(lhs: a, rhs: c), "transitivity", [1, 2]),
  (Fd(lhs: a | d, rhs: c | d), "augmentation", [3]),
  (Fd(lhs: c | d, rhs: e), "given", []),
  (Fd(lhs: a | d, rhs: e), "transitivity", [4, 5]),
  (Fd(lhs: c, rhs: e), "augmentation", [5]),
]

func letters(_ mask: Int) -> String {
  String(Array("ABCDE").enumerated().filter { mask >> $0.offset & 1 == 1 }.map(\.element))
}

func padded(_ text: String, _ width: Int) -> String {
  text + String(repeating: " ", count: max(0, width - text.count))
}

func follows(_ dep: Fd, _ rule: String, _ refs: [Fd]) -> Bool {
  let (x, y) = (dep.lhs, dep.rhs)
  switch (rule, refs.count) {
  case ("given", 0):
    return f.contains(dep)
  case ("augmentation", 1):
    let (p, q) = (refs[0].lhs, refs[0].rhs)
    return p & x == p && q & y == q && x & ~p & ~y == 0 && y & ~q & ~x == 0
  case ("transitivity", 2):
    return refs[0].lhs == x && refs[0].rhs == refs[1].lhs && refs[1].rhs == y
  default:
    return false
  }
}

var proved: [Bool] = []
for (index, line) in proof.enumerated() {
  let cited = line.refs.filter { $0 <= index && proved[$0 - 1] }.map { proof[$0 - 1].dep }
  let ok = cited.count == line.refs.count && follows(line.dep, line.rule, cited)
  proved.append(ok)
  let shown = "\(letters(line.dep.lhs)) -> \(letters(line.dep.rhs))"
  let refs = line.refs.map(String.init).joined(separator: ", ")
  let place = refs.isEmpty ? line.rule : "\(line.rule) \(refs)"
  print("  \(index + 1). \(padded(shown, 9)) \(padded(place, 18)) \(ok ? "ok" : "does not follow")")
}

Ruby 4.0 · main.rb

# frozen_string_literal: true

# Sets of attributes are bit masks.
A = 1
B = 2
C = 4
D = 8
E = 16
F = [[A, B], [B, C], [C | D, E]].freeze
PROOF = [
  [[A, B], 'given', []],
  [[B, C], 'given', []],
  [[A, C], 'transitivity', [1, 2]],
  [[A | D, C | D], 'augmentation', [3]],
  [[C | D, E], 'given', []],
  [[A | D, E], 'transitivity', [4, 5]],
  [[C, E], 'augmentation', [5]]
].freeze

# How each rule checks the dependency [x, y] against the dependencies it cites.
RULES = {
  'given' => ->(dep, refs) { refs.empty? && F.include?(dep) },
  'augmentation' => lambda do |(x, y), refs|
    a, b = refs.first
    refs.size == 1 && a & x == a && b & y == b && (x & ~a & ~y).zero? && (y & ~b & ~x).zero?
  end,
  'transitivity' => lambda do |(x, y), refs|
    (a, b), (c, d) = refs
    refs.size == 2 && a == x && b == c && d == y
  end
}.freeze

def letters(mask)
  'ABCDE'.chars.select.with_index { |_, i| mask[i] == 1 }.join
end

proved = []
PROOF.each.with_index(1) do |(dep, rule, refs), number|
  cited = refs.select { |r| r < number && proved[r - 1] }.map { |r| PROOF[r - 1][0] }
  ok = cited.size == refs.size && RULES.fetch(rule).call(dep, cited)
  proved << ok
  where = "#{rule} #{refs.join(', ')}".strip
  puts "  #{number}. #{dep.map { |m| letters(m) }.join(' -> ').ljust(9)} #{where.ljust(18)} " \
       "#{ok ? 'ok' : 'does not follow'}"
end

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

// Sets of attributes are bit masks.
const val A = 1
const val B = 2
const val C = 4
const val D = 8
const val E = 16

typealias Fd = Pair<Int, Int>

data class Line(
    val dep: Fd,
    val rule: String,
    val refs: List<Int> = listOf(),
)

val f = listOf(A to B, B to C, (C or D) to E)
val proof =
    listOf(
        Line(A to B, "given"),
        Line(B to C, "given"),
        Line(A to C, "transitivity", listOf(1, 2)),
        Line((A or D) to (C or D), "augmentation", listOf(3)),
        Line((C or D) to E, "given"),
        Line((A or D) to E, "transitivity", listOf(4, 5)),
        Line(C to E, "augmentation", listOf(5)),
    )

fun letters(mask: Int) = "ABCDE".filterIndexed { i, _ -> mask shr i and 1 == 1 }

fun follows(
    dep: Fd,
    rule: String,
    refs: List<Fd>,
): Boolean {
    val (x, y) = dep
    return when {
        rule == "given" && refs.isEmpty() -> {
            dep in f
        }

        rule == "augmentation" && refs.size == 1 -> {
            val (a, b) = refs[0]
            a and x == a && b and y == b && x and a.inv() and y.inv() == 0 &&
                y and b.inv() and x.inv() == 0
        }

        rule == "transitivity" && refs.size == 2 -> {
            refs[0].first == x && refs[0].second == refs[1].first && refs[1].second == y
        }

        else -> {
            false
        }
    }
}

fun main() {
    val proved = mutableListOf<Boolean>()
    for ((index, line) in proof.withIndex()) {
        val cited = line.refs.filter { it <= index && proved[it - 1] }.map { proof[it - 1].dep }
        val ok = cited.size == line.refs.size && follows(line.dep, line.rule, cited)
        proved += ok
        val shown = "${letters(line.dep.first)} -> ${letters(line.dep.second)}"
        val where = "${line.rule} ${line.refs.joinToString(", ")}".trim()
        val verdict = if (ok) "ok" else "does not follow"
        println("  ${index + 1}. ${shown.padEnd(9)} ${where.padEnd(18)} $verdict")
    }
}

Dart 3.13 · main.dart

// Sets of attributes are bit masks.
const a = 1, b = 2, c = 4, d = 8, e = 16;
typedef Fd = (int, int);

const List<Fd> f = [(a, b), (b, c), (c | d, e)];
const List<(Fd, String, List<int>)> proof = [
  ((a, b), 'given', []),
  ((b, c), 'given', []),
  ((a, c), 'transitivity', [1, 2]),
  ((a | d, c | d), 'augmentation', [3]),
  ((c | d, e), 'given', []),
  ((a | d, e), 'transitivity', [4, 5]),
  ((c, e), 'augmentation', [5]),
];

String letters(int mask) => [
  for (var i = 0; i < 5; i++)
    if (mask >> i & 1 == 1) 'ABCDE'[i],
].join();

bool follows(Fd dep, String rule, List<Fd> refs) {
  final (x, y) = dep;
  return switch ((rule, refs)) {
    ('given', []) => f.contains(dep),
    ('augmentation', [(final p, final q)]) =>
      p & x == p && q & y == q && x & ~p & ~y == 0 && y & ~q & ~x == 0,
    ('transitivity', [(final p, final q), (final r, final s)]) =>
      p == x && q == r && s == y,
    _ => false,
  };
}

void main() {
  final proved = <bool>[];
  for (final (index, (dep, rule, refs)) in proof.indexed) {
    final cited = [
      for (final r in refs)
        if (r <= index && proved[r - 1]) proof[r - 1].$1,
    ];
    final ok = cited.length == refs.length && follows(dep, rule, cited);
    proved.add(ok);
    final shown = '${letters(dep.$1)} -> ${letters(dep.$2)}';
    final where = '$rule ${refs.join(', ')}'.trim();
    final verdict = ok ? 'ok' : 'does not follow';
    print(
      '  ${index + 1}. ${shown.padRight(9)} ${where.padRight(18)} $verdict',
    );
  }
}

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

  1. A -> B    given              ok
  2. B -> C    given              ok
  3. A -> C    transitivity 1, 2  ok
  4. AD -> CD  augmentation 3     ok
  5. CD -> E   given              ok
  6. AD -> E   transitivity 4, 5  ok
  7. C -> E    augmentation 5     does not follow

Lines 1 to 6 reach AD -> E. Line 7 tries to drop D from the left-hand side of CD -> E, and no rule allows that: knowing C alone need not fix E.

Key idea

A derivation is only as good as its weakest line: each line must be given or follow from earlier lines by one named rule, and no rule ever removes an attribute from a left-hand side.

Checkpoint

Check: Armstrong's axioms and derivations

Question 1 of 2 Which rule turns A -> B and BC -> D into AC -> D in one step?
Choose one answer.

Transitivity Union Augmentation Pseudotransitivity

Show the answer: Question 1 of 2

Answer: Pseudotransitivity

Pseudotransitivity is a shortcut for two axiom steps: augment A -> B with C to get AC -> BC, then chain AC -> BC and BC -> D by transitivity.
Question 2 of 2 Which line follows from CD -> E by augmentation alone?
Choose one answer.

ACD -> AE D -> E C -> E CD -> AE

Show the answer: Question 2 of 2

Answer: ACD -> AE

From X -> Y, augmentation gives XZ -> YZ for any Z. It can only grow both sides together, which is why no rule shrinks a left-hand side.

Practise: derive with the axioms

The exercise asks for three derivations, each line a dependency, a rule and the earlier lines it cites, and its sample tests check every line in your browser:

Exercise · Medium · Python

Write three derivations that a checker accepts line by line

Write three derivations in derivations.py. Each one is a list of steps, and each step is a tuple (dependency, rule, earlier step numbers), such as ("AD -> CD", "augmentation", [3]). Attributes are single letters, steps are numbered from 1, and a step may cite only steps before it.

From A -> B, B -> C and C -> D, derive A -> D with the three axioms only.
From A -> C and BC -> D, derive AB -> D with the three axioms only.
From A -> BC, CD -> E and E -> F, derive AD -> F. Here you may also use "union", "decomposition" and "pseudotransitivity".

A given dependency enters with the rule "given" and no earlier steps. The sample tests check every line the way the lesson's checker does: the rule must be allowed, the line must follow from the steps it cites, and the last line must be the target.

Starter code · derivations.py

"""Each derivation is a list of steps: (dependency, rule, earlier step numbers).

Attributes are single letters, so "AB -> D" means {A, B} -> {D}. Steps are numbered
from 1. Rules: "given", "reflexivity", "augmentation" and "transitivity"; derivation 3
may also use "union", "decomposition" and "pseudotransitivity".
"""

# 1. From A -> B, B -> C and C -> D, derive A -> D with the three axioms only.
DERIVATION_1 = [
    ("A -> B", "given", []),
]

# 2. From A -> C and BC -> D, derive AB -> D with the three axioms only.
DERIVATION_2 = []

# 3. From A -> BC, CD -> E and E -> F, derive AD -> F with any of the seven rules.
DERIVATION_3 = []

The sample tests · test_derivations.py

from derivations import DERIVATION_1, DERIVATION_2, DERIVATION_3

AXIOMS = {"given", "reflexivity", "augmentation", "transitivity"}
ALL_RULES = AXIOMS | {"union", "decomposition", "pseudotransitivity"}


def fd(text):
    lhs, rhs = text.split("->")
    return frozenset(lhs.strip()), frozenset(rhs.strip())


def follows(rule, new, refs, given):
    """Whether `new` follows by `rule` from the dependencies `refs`."""
    x, y = new
    one, two = len(refs) == 1, len(refs) == 2
    if rule == "given":
        return not refs and new in given
    if rule == "reflexivity":
        return not refs and y <= x
    if rule == "augmentation" and one:          # X -> Y gives XZ -> YZ
        (a, b), = refs
        return a <= x and b <= y and (x - a) <= y and (y - b) <= x
    if rule == "transitivity" and two:          # X -> Y, Y -> Z give X -> Z
        (a, b), (c, d) = refs
        return a == x and b == c and d == y
    if rule == "union" and two:                 # X -> Y, X -> Z give X -> YZ
        (a, b), (c, d) = refs
        return a == x and c == x and (b | d) == y
    if rule == "decomposition" and one:         # X -> YZ gives X -> Y
        (a, b), = refs
        return a == x and y <= b
    if rule == "pseudotransitivity" and two:    # X -> Y, WY -> Z give WX -> Z
        (a, b), (c, d) = refs
        w = (c - b) | (x - a)
        return b <= c and a <= x and w <= (c & x) and d == y
    return False


def problem(given_texts, target, steps, rules):
    """The first problem of a derivation, or None when it proves the target."""
    given = {fd(t) for t in given_texts}
    proved = []
    for number, step in enumerate(steps, start=1):
        text, rule, refs = step
        if rule not in rules:
            return f"step {number}: the rule {rule!r} is not allowed here"
        if any(not 1 <= r < number for r in refs):
            return f"step {number}: it may cite only earlier steps, 1 to {number - 1}"
        if not follows(rule, fd(text), [proved[r - 1] for r in refs], given):
            return f"step {number}: {text} does not follow by {rule} from steps {refs}"
        proved.append(fd(text))
    if not proved or proved[-1] != fd(target):
        return f"the last step must be the target, {target}"
    return None


def test_derivation_1():
    """A -> D from A -> B, B -> C and C -> D, with the axioms only"""
    assert problem(["A -> B", "B -> C", "C -> D"], "A -> D", DERIVATION_1, AXIOMS) is None


def test_derivation_2():
    """AB -> D from A -> C and BC -> D, with the axioms only"""
    assert problem(["A -> C", "BC -> D"], "AB -> D", DERIVATION_2, AXIOMS) is None


def test_derivation_3():
    """AD -> F from A -> BC, CD -> E and E -> F, with any rule"""
    assert problem(["A -> BC", "CD -> E", "E -> F"], "AD -> F", DERIVATION_3, ALL_RULES) is None

A hint

Work backwards from each target. For AB -> D you are given BC -> D, so first get a line whose right-hand side is exactly BC: which given dependency, with which attribute added to both sides, produces it? For AD -> F, aim for AD -> E first; the last step is then a transitivity with E -> F.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Then check what you know about dependencies, refuting rows and the axioms; the questions open with the one you know least.

Why the axioms are sound and complete, with proofs that run Pro: opens with a Pro, Premium or Ultimate pass

Sound and complete are strong claims: no false dependency can ever be derived, and no true one is out of reach. This part proves both, the second by building the very table that refutes any dependency the axioms cannot derive.

In this part:

Soundness, checked rule by rule on two rows
The three extra rules, each derived from the axioms alone
Completeness, by building the table that refutes

2 runnable examples (Python) · about 5 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Implied or not: six traps, the size of F+ and dependencies in SQL engines Pro: opens with a Pro, Premium or Ultimate pass

Most mistakes with dependencies are claims that sound like rules and are not. This part settles six of them with the closure test and a counterexample, counts how fast the set of implied dependencies grows, and shows two database engines relying on dependencies when they group rows.

In this part:

Six claims settled, with two rows for every false one
How large F+ grows, with numbers
A worked exam item, option by option
Dependencies inside SQL engines

3 runnable examples (Python, SQL) · about 5 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher to mid · Warm-up

What does the functional dependency X -> Y mean, and why can a table's rows refute it but never prove it?

X -> Y means that in every legal state of the table, any two rows with the same values on the attributes X also have the same values on Y. It is a rule about what the data means: a course has one title, so course -> title. The rows can refute it, because two rows that agree on X and differ on Y break it, and one such pair is enough. They cannot prove it, because they are only the table's current state: the next insert may add the pair that breaks it, as a second student with an existing name would break student -> roll_no. So dependencies are decided from the meaning of the attributes, and the data is searched for counterexamples.
Mid to senior

In a customer table of 2 million rows, every postal code appears with exactly one city. A teammate wants to declare postal_code -> city as a rule, move city into a postal_codes table and drop it from customers. What do you check before you agree?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Fresher to mid

Given F = {A -> B, BC -> D, D -> E}, does AC -> E follow? Does A -> E? Prove one and refute the other in a way an interviewer can check line by line.

Model answer, Pro. First step and follow-ups
Mid to senior

Armstrong's axioms are called sound and complete. Explain what each word means, and sketch the completeness proof an interviewer expects.

Model answer, Pro. First step and follow-ups

Key takeaways

X -> Y means that rows which agree on X agree on Y. Functional dependencies are rules about meaning, not about today’s rows.
One pair of rows refutes a dependency, as rows 1 and 4 refuted instructor -> course; no rows prove one.
Armstrong’s axioms derive every implied dependency and nothing false, and union, decomposition and pseudotransitivity follow from them.
Each line of a derivation is given or follows from earlier lines by one rule; no rule drops an attribute from a left-hand side.

Terms in this lesson

Armstrong's axioms: Reflexivity, augmentation and transitivity: three rules that derive every functional dependency implied by a set of known ones, and never a false one.
determinant: The left-hand side X of a functional dependency X -> Y: the attributes whose values fix the values of Y.
functional dependency: A rule X -> Y on a relation: any two rows that have the same values for the attributes X also have the same values for Y.
trivial dependency: A dependency X -> Y whose right-hand side is part of its left-hand side, such as AB -> A. It holds in every table, so it says nothing about the data.

References

P. A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies (ACM Transactions on Database Systems)
C. Beeri and P. A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas (ACM Transactions on Database Systems)
A. V. Aho, C. Beeri and J. D. Ullman: The Theory of Joins in Relational Databases (ACM Transactions on Database Systems)
PostgreSQL 18 Documentation: SELECT (the GROUP BY clause and functional dependencies) (The PostgreSQL Global Development Group)
SQLite: SELECT (bare columns in an aggregate query) (SQLite)
Reserve Bank of India: Frequently Asked Questions, NEFT System (the IFSC) (Reserve Bank of India)
GATE 2027 question paper pattern (MCQ, MSQ and NAT) (Indian Institute of Technology Madras (GATE 2027))

Report a problem with this lesson

In this module: Functional dependencies

Redundancy and update, insert, delete anomalies Free lesson, Pro answers: 20 minutes
Functional dependencies and Armstrong's axioms Free core, Pro depth: 8 of 20 minutes free
Attribute closure and finding candidate keys Free core, Pro depth: 6 of 15 minutes free
Canonical cover and equivalence of FD sets Free core, Pro depth: 6 of 15 minutes free

Your country

Functional dependencies and Armstrong's axioms

What you will learn

Before you start

What you will learn

Before you start

A dependency says that rows which agree on X agree on Y

One pair of rows refutes a dependency, and no rows prove one

Armstrong’s three axioms derive every implied dependency

Practise: derive with the axioms

Write three derivations that a checker accepts line by line

Results of the sample tests

Why the axioms are sound and complete, with proofs that run Pro: opens with a Pro, Premium or Ultimate pass

Implied or not: six traps, the size of F+ and dependencies in SQL engines Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What does the functional dependency X -> Y mean, and why can a table's rows refute it but never prove it?

In a customer table of 2 million rows, every postal code appears with exactly one city. A teammate wants to declare postal_code -> city as a rule, move city into a postal_codes table and drop it from customers. What do you check before you agree?

Given F = {A -> B, BC -> D, D -> E}, does AC -> E follow? Does A -> E? Prove one and refute the other in a way an interviewer can check line by line.

Armstrong's axioms are called sound and complete. Explain what each word means, and sketch the completeness proof an interviewer expects.

Key takeaways

References

Related tools