Database Management Systems (DBMS) Module 6 – Functional dependencies

Canonical cover and equivalence of FD sets

Compute a canonical cover by removing extraneous attributes and redundant dependencies, and test whether two sets of dependencies are equivalent with closures.

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

Free: Two sets of dependencies are equivalent when each implies the other · A canonical cover takes three steps, each decided by a closure · Practise: two canonical covers. With a pass: 2 in-depth parts and 3 interview answers, about 9 minutes.

What you will learn

Test whether two sets of functional dependencies are equivalent, with one closure per dependency
Compute a canonical cover by splitting, then removing extraneous attributes, then redundant dependencies
Explain why canonical covers are not unique, and grade any valid cover by its properties
Distinguish a minimal cover from a minimum one, and predict how the cover changes a 3NF schema

Before you start

Attribute closure and finding candidate keys

What you’ll learn · Before you start

What you will learn

Test whether two sets of functional dependencies are equivalent, with one closure per dependency
Compute a canonical cover by splitting, then removing extraneous attributes, then redundant dependencies
Explain why canonical covers are not unique, and grade any valid cover by its properties
Distinguish a minimal cover from a minimum one, and predict how the cover changes a 3NF schema

Before you start

Attribute closure and finding candidate keys

On this page

Two teams write down the rules of the same course table, one with three dependencies and one with two. Do they say the same thing? Two sets F and G are equivalent sets of dependencies: Two sets of functional dependencies that each imply every dependency of the other, so they allow exactly the same tables. when each implies every dependency of the other, so they allow exactly the same tables, and the equivalence of FD sets is tested with one closure per dependency.

A canonical cover: A set of functional dependencies equivalent to F that has no extraneous attribute and no redundant dependency. of F is a cleaned-up set that says exactly the same thing: every right-hand side holds one attribute, no left-hand side has an attribute it can do without, and no dependency follows from the others. It is computed in three steps, split, remove extraneous attributes and remove redundant dependencies, and each decision is one closure. Canonical covers state a schema’s rules with nothing to spare and are the input of the 3NF synthesis algorithm.

Two sets of dependencies are equivalent when each implies the other

F implies X -> Y exactly when Y lies inside X+ computed under F. So F and G are equivalent when every dependency of G passes that test under F, and every dependency of F passes it under G. Three ways of writing the rules of a course table show both outcomes. Step through the test of G against H first:

Interactive · step by step G against H, tested both ways Step through the five tests. Each one computes the closure of a left-hand side under the other set.

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

Every step as text

Two sets. G has three rules and H has two. They look alike, so the test asks whether each set implies every rule of the other.
G gives H1. Under G, the closure of course is course, title, instructor and office. It contains title and instructor, so G implies H1.
G gives H2. Under G, the closure of course and instructor holds office too, so G implies H2. A one-way test would stop here and call the sets equal.
H gives G1 and G2. Now the other way. Under H, the closure of course is course, title, instructor and office, so H implies G1 and G2.
H misses G3. Under H, the closure of instructor is instructor alone. H says where the office is only for a course and its instructor together, so instructor -> office is not implied.
Not equivalent. One rule of G does not follow from H, so the sets are not equivalent. H is weaker, and it allows tables that G forbids.

The program runs both comparisons, F against G and G against H, and prints every test:

One program · 14 languages Three sets of dependencies, compared both ways

Python 3.14 · main.py

# Sets of attributes are bit masks: bit i stands for R[i].
R = ["course", "title", "instructor", "office"]
SETS = {
    "F": ["course -> title instructor", "instructor -> office", "course -> office"],
    "G": ["course -> title", "course -> instructor", "instructor -> office"],
    "H": ["course -> title instructor", "course instructor -> office"],
}


def mask(names: str) -> int:
    return sum(1 << R.index(name) for name in names.split())


def sides(fd: str) -> tuple[int, int]:
    lhs, rhs = fd.split("->")
    return mask(lhs), mask(rhs)


def closure(x: int, fds: list[str]) -> int:
    grew = True
    while grew:
        grew = False
        for lhs, rhs in map(sides, fds):
            if lhs & ~x == 0 and rhs & ~x:
                x, grew = x | rhs, True
    return x


def implies(f: str, g: str) -> bool:
    """Whether f implies every dependency of g: Y inside X+ under f."""
    every = True
    for fd in SETS[g]:
        lhs, rhs = sides(fd)
        ok = rhs & ~closure(lhs, SETS[f]) == 0
        every = every and ok
        print(f"  {fd:<28} {'implied' if ok else 'NOT implied'} by {f}")
    return every


for f, g in [("F", "G"), ("G", "H")]:
    print(f"{f} against {g}:")
    both = [implies(f, g), implies(g, f)]  # both directions, always
    print(f"  {f} and {g} are {'equivalent' if all(both) else 'not equivalent'}\n")

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: bit i stands for R[i].
const R = ["course", "title", "instructor", "office"];
const SETS = {
  F: ["course -> title instructor", "instructor -> office", "course -> office"],
  G: ["course -> title", "course -> instructor", "instructor -> office"],
  H: ["course -> title instructor", "course instructor -> office"],
};

const mask = (names) =>
  names
    .trim()
    .split(" ")
    .reduce((x, name) => x | (1 << R.indexOf(name)), 0);
const sides = (fd) => fd.split("->").map(mask);

function closure(x, fds) {
  for (let grew = true; grew;) {
    grew = false;
    for (const [lhs, rhs] of fds.map(sides)) {
      if ((lhs & ~x) === 0 && rhs & ~x) [x, grew] = [x | rhs, true];
    }
  }
  return x;
}

// Whether f implies every dependency of g: Y inside X+ under f.
function implies(f, g) {
  let every = true;
  for (const fd of SETS[g]) {
    const [lhs, rhs] = sides(fd);
    const ok = (rhs & ~closure(lhs, SETS[f])) === 0;
    every = every && ok;
    console.log(`  ${fd.padEnd(28)} ${ok ? "implied" : "NOT implied"} by ${f}`);
  }
  return every;
}

for (const [f, g] of [
  ["F", "G"],
  ["G", "H"],
]) {
  console.log(`${f} against ${g}:`);
  const both = [implies(f, g), implies(g, f)]; // both directions, always
  console.log(`  ${f} and ${g} are ${both.every(Boolean) ? "equivalent" : "not equivalent"}\n`);
}

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.List;
import java.util.Map;

public class Main {
  // Sets of attributes are bit masks: bit i stands for R[i].
  static final List<String> R = List.of("course", "title", "instructor", "office");
  static final Map<String, List<String>> SETS =
      Map.of(
          "F", List.of("course -> title instructor", "instructor -> office", "course -> office"),
          "G", List.of("course -> title", "course -> instructor", "instructor -> office"),
          "H", List.of("course -> title instructor", "course instructor -> office"));

  static int mask(String names) {
    int x = 0;
    for (String name : names.strip().split(" ")) {
      x |= 1 << R.indexOf(name);
    }
    return x;
  }

  static int[] sides(String fd) {
    String[] parts = fd.split("->");
    return new int[] {mask(parts[0]), mask(parts[1])};
  }

  static int closure(int x, List<String> fds) {
    for (boolean grew = true; grew; ) {
      grew = false;
      for (String fd : fds) {
        int[] s = sides(fd);
        if ((s[0] & ~x) == 0 && (s[1] & ~x) != 0) {
          x |= s[1];
          grew = true;
        }
      }
    }
    return x;
  }

  /** Whether f implies every dependency of g: Y inside X+ under f. */
  static boolean implies(String f, String g) {
    boolean every = true;
    for (String fd : SETS.get(g)) {
      int[] s = sides(fd);
      boolean ok = (s[1] & ~closure(s[0], SETS.get(f))) == 0;
      every = every && ok;
      String padded = fd + " ".repeat(Math.max(0, 28 - fd.length()));
      System.out.println("  " + padded + " " + (ok ? "implied" : "NOT implied") + " by " + f);
    }
    return every;
  }

  public static void main(String[] args) {
    for (String[] pair : new String[][] {{"F", "G"}, {"G", "H"}}) {
      String f = pair[0], g = pair[1];
      System.out.println(f + " against " + g + ":");
      boolean first = implies(f, g), second = implies(g, f); // both directions, always
      String verdict = first && second ? "equivalent" : "not equivalent";
      System.out.println("  " + f + " and " + g + " are " + verdict + "\n");
    }
  }
}

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 <map>
#include <print>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// Sets of attributes are bit masks: bit i stands for R[i].
const std::vector<std::string> R = {"course", "title", "instructor", "office"};
const std::map<std::string, std::vector<std::string>> SETS = {
    {"F",
     {"course -> title instructor", "instructor -> office",
      "course -> office"}},
    {"G", {"course -> title", "course -> instructor", "instructor -> office"}},
    {"H", {"course -> title instructor", "course instructor -> office"}},
};

unsigned mask(const std::string &names) {
  std::istringstream in(names);
  unsigned x = 0;
  for (std::string name; in >> name;)
    for (std::size_t i = 0; i < R.size(); i++)
      if (R[i] == name)
        x |= 1u << i;
  return x;
}

std::pair<unsigned, unsigned> sides(const std::string &fd) {
  const auto arrow = fd.find("->");
  return {mask(fd.substr(0, arrow)), mask(fd.substr(arrow + 2))};
}

unsigned closure(unsigned x, const std::vector<std::string> &fds) {
  for (bool grew = true; grew;) {
    grew = false;
    for (const auto &fd : fds) {
      const auto [lhs, rhs] = sides(fd);
      if ((lhs & ~x) == 0 && (rhs & ~x)) {
        x |= rhs;
        grew = true;
      }
    }
  }
  return x;
}

// Whether f implies every dependency of g: Y inside X+ under f.
bool implies(const std::string &f, const std::string &g) {
  bool every = true;
  for (const auto &fd : SETS.at(g)) {
    const auto [lhs, rhs] = sides(fd);
    const bool ok = (rhs & ~closure(lhs, SETS.at(f))) == 0;
    every = every && ok;
    std::println("  {:<28} {} by {}", fd, ok ? "implied" : "NOT implied", f);
  }
  return every;
}

int main() {
  for (const auto &[f, g] : {std::pair{"F", "G"}, std::pair{"G", "H"}}) {
    std::println("{} against {}:", f, g);
    const bool first = implies(f, g), second = implies(g, f); // both, always
    std::println("  {} and {} are {}\n", f, g,
                 first && second ? "equivalent" : "not equivalent");
  }
}

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

// Sets of attributes are bit masks: bit i stands for R[i].
string[] r = ["course", "title", "instructor", "office"];
var sets = new Dictionary<string, string[]>
{
    ["F"] = ["course -> title instructor", "instructor -> office", "course -> office"],
    ["G"] = ["course -> title", "course -> instructor", "instructor -> office"],
    ["H"] = ["course -> title instructor", "course instructor -> office"],
};

foreach (var (f, g) in new[] { ("F", "G"), ("G", "H") })
{
    Console.WriteLine($"{f} against {g}:");
    bool[] both = [Implies(f, g, sets, r), Implies(g, f, sets, r)]; // both directions, always
    string verdict = both.All(ok => ok) ? "equivalent" : "not equivalent";
    Console.WriteLine($"  {f} and {g} are {verdict}\n");
}

// Whether f implies every dependency of g: Y inside X+ under f.
static bool Implies(string f, string g, Dictionary<string, string[]> sets, string[] r)
{
    bool every = true;
    foreach (string fd in sets[g])
    {
        var (lhs, rhs) = Sides(fd, r);
        bool ok = (rhs & ~Closure(lhs, sets[f], r)) == 0;
        every = every && ok;
        Console.WriteLine($"  {fd,-28} {(ok ? "implied" : "NOT implied")} by {f}");
    }
    return every;
}

static int Mask(string names, string[] r) =>
    names.Trim().Split(' ').Aggregate(0, (x, name) => x | 1 << Array.IndexOf(r, name));

static (int Lhs, int Rhs) Sides(string fd, string[] r) =>
    fd.Split("->") is [var lhs, var rhs] ? (Mask(lhs, r), Mask(rhs, r)) : (0, 0);

static int Closure(int x, string[] fds, string[] r)
{
    for (bool grew = true; grew;)
    {
        grew = false;
        foreach (string fd in fds)
        {
            var (lhs, rhs) = Sides(fd, r);
            if ((lhs & ~x) == 0 && (rhs & ~x) != 0)
            {
                x |= rhs;
                grew = true;
            }
        }
    }
    return x;
}

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: bit i stands for R[i].
enum { N = 4, TEXT = 64 };
static const char *const R[N] = {"course", "title", "instructor", "office"};
typedef struct {
  const char *name;
  const char *fds[4]; // ends with a null pointer
} Set;
static const Set SETS[] = {
    {"F",
     {"course -> title instructor", "instructor -> office",
      "course -> office"}},
    {"G", {"course -> title", "course -> instructor", "instructor -> office"}},
    {"H", {"course -> title instructor", "course instructor -> office"}},
};

static unsigned mask(const char *names, size_t length) {
  char copy[TEXT] = "";
  unsigned x = 0;
  strncat(copy, names, length);
  for (char *name = strtok(copy, " "); name; name = strtok(nullptr, " "))
    for (int i = 0; i < N; i++)
      if (strcmp(R[i], name) == 0)
        x |= 1u << i;
  return x;
}

static void sides(const char *fd, unsigned *lhs, unsigned *rhs) {
  const char *arrow = strstr(fd, "->");
  *lhs = mask(fd, (size_t)(arrow - fd));
  *rhs = mask(arrow + 2, strlen(arrow + 2));
}

static unsigned closure(unsigned x, const Set *f) {
  for (bool grew = true; grew;) {
    grew = false;
    for (int k = 0; f->fds[k]; k++) {
      unsigned lhs, rhs;
      sides(f->fds[k], &lhs, &rhs);
      if ((lhs & ~x) == 0 && (rhs & ~x)) {
        x |= rhs;
        grew = true;
      }
    }
  }
  return x;
}

// Whether f implies every dependency of g: Y inside X+ under f.
static bool implies(const Set *f, const Set *g) {
  bool every = true;
  for (int k = 0; g->fds[k]; k++) {
    unsigned lhs, rhs;
    sides(g->fds[k], &lhs, &rhs);
    const bool ok = (rhs & ~closure(lhs, f)) == 0;
    every = every && ok;
    printf("  %-28s %s by %s\n", g->fds[k], ok ? "implied" : "NOT implied",
           f->name);
  }
  return every;
}

int main(void) {
  for (int p = 0; p < 2; p++) {
    const Set *f = &SETS[p], *g = &SETS[p + 1];
    printf("%s against %s:\n", f->name, g->name);
    const bool first = implies(f, g), second = implies(g, f); // both, always
    printf("  %s and %s are %s\n\n", f->name, g->name,
           first && second ? "equivalent" : "not equivalent");
  }
  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);

// Sets of attributes are bit masks: bit i stands for R[i].
const R = ['course', 'title', 'instructor', 'office'];
const SETS = [
    'F' => ['course -> title instructor', 'instructor -> office', 'course -> office'],
    'G' => ['course -> title', 'course -> instructor', 'instructor -> office'],
    'H' => ['course -> title instructor', 'course instructor -> office'],
];

function mask(string $names): int
{
    $x = 0;
    foreach (explode(' ', trim($names)) as $name) {
        $x |= 1 << array_search($name, R, true);
    }
    return $x;
}

/** @return array{int, int} */
function sides(string $fd): array
{
    return array_map(mask(...), explode('->', $fd));
}

/** @param list<string> $fds */
function closure(int $x, array $fds): int
{
    do {
        $grew = false;
        foreach (array_map(sides(...), $fds) as [$lhs, $rhs]) {
            if (($lhs & ~$x) === 0 && ($rhs & ~$x) !== 0) {
                $x |= $rhs;
                $grew = true;
            }
        }
    } while ($grew);
    return $x;
}

// Whether f implies every dependency of g: Y inside X+ under f.
function implies(string $f, string $g): bool
{
    $every = true;
    foreach (SETS[$g] as $fd) {
        [$lhs, $rhs] = sides($fd);
        $ok = ($rhs & ~closure($lhs, SETS[$f])) === 0;
        $every = $every && $ok;
        printf("  %-28s %s by %s\n", $fd, $ok ? 'implied' : 'NOT implied', $f);
    }
    return $every;
}

foreach ([['F', 'G'], ['G', 'H']] as [$f, $g]) {
    echo "{$f} against {$g}:\n";
    $both = [implies($f, $g), implies($g, $f)]; // both directions, always
    $verdict = $both === [true, true] ? 'equivalent' : 'not equivalent';
    echo "  {$f} and {$g} are {$verdict}\n\n";
}

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: bit i stands for R[i].
const R: [&str; 4] = ["course", "title", "instructor", "office"];
const SETS: [(&str, &[&str]); 3] = [
    (
        "F",
        &[
            "course -> title instructor",
            "instructor -> office",
            "course -> office",
        ],
    ),
    (
        "G",
        &[
            "course -> title",
            "course -> instructor",
            "instructor -> office",
        ],
    ),
    (
        "H",
        &["course -> title instructor", "course instructor -> office"],
    ),
];

fn mask(names: &str) -> u32 {
    names
        .split_whitespace()
        .filter_map(|name| R.iter().position(|r| *r == name))
        .fold(0, |x, i| x | 1 << i)
}

fn sides(fd: &str) -> (u32, u32) {
    let (lhs, rhs) = fd.split_once("->").unwrap_or((fd, ""));
    (mask(lhs), mask(rhs))
}

fn closure(mut x: u32, fds: &[&str]) -> u32 {
    let mut grew = true;
    while grew {
        grew = false;
        for (lhs, rhs) in fds.iter().map(|fd| sides(fd)) {
            if lhs & !x == 0 && rhs & !x != 0 {
                (x, grew) = (x | rhs, true);
            }
        }
    }
    x
}

fn set(name: &str) -> &'static [&'static str] {
    SETS.iter()
        .find(|(n, _)| *n == name)
        .map_or(&[], |(_, fds)| fds)
}

/// Whether f implies every dependency of g: Y inside X+ under f.
fn implies(f: &str, g: &str) -> bool {
    let mut every = true;
    for fd in set(g) {
        let (lhs, rhs) = sides(fd);
        let ok = rhs & !closure(lhs, set(f)) == 0;
        every = every && ok;
        let verdict = if ok { "implied" } else { "NOT implied" };
        println!("  {fd:<28} {verdict} by {f}");
    }
    every
}

fn main() {
    for (f, g) in [("F", "G"), ("G", "H")] {
        println!("{f} against {g}:");
        let both = implies(f, g) & implies(g, f); // both directions, always
        let verdict = if both { "equivalent" } else { "not equivalent" };
        println!("  {f} and {g} are {verdict}\n");
    }
}

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

// Sets of attributes are bit masks: bit i stands for R[i].
const R = ["course", "title", "instructor", "office"];
const SETS: Record<string, string[]> = {
  F: ["course -> title instructor", "instructor -> office", "course -> office"],
  G: ["course -> title", "course -> instructor", "instructor -> office"],
  H: ["course -> title instructor", "course instructor -> office"],
};

const mask = (names: string): number =>
  names
    .trim()
    .split(" ")
    .reduce((x, name) => x | (1 << R.indexOf(name)), 0);
const sides = (fd: string): number[] => fd.split("->").map(mask);

function closure(x: number, fds: string[]): number {
  for (let grew = true; grew;) {
    grew = false;
    for (const [lhs, rhs] of fds.map(sides)) {
      if ((lhs & ~x) === 0 && rhs & ~x) [x, grew] = [x | rhs, true];
    }
  }
  return x;
}

// Whether f implies every dependency of g: Y inside X+ under f.
function implies(f: string, g: string): boolean {
  let every = true;
  for (const fd of SETS[g]) {
    const [lhs, rhs] = sides(fd);
    const ok = (rhs & ~closure(lhs, SETS[f])) === 0;
    every = every && ok;
    console.log(`  ${fd.padEnd(28)} ${ok ? "implied" : "NOT implied"} by ${f}`);
  }
  return every;
}

for (const [f, g] of [
  ["F", "G"],
  ["G", "H"],
]) {
  console.log(`${f} against ${g}:`);
  const both = [implies(f, g), implies(g, f)]; // both directions, always
  console.log(`  ${f} and ${g} are ${both.every(Boolean) ? "equivalent" : "not equivalent"}\n`);
}

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"
)

// Sets of attributes are bit masks: bit i stands for r[i].
var r = []string{"course", "title", "instructor", "office"}

var sets = map[string][]string{
	"F": {"course -> title instructor", "instructor -> office", "course -> office"},
	"G": {"course -> title", "course -> instructor", "instructor -> office"},
	"H": {"course -> title instructor", "course instructor -> office"},
}

func mask(names string) uint {
	var x uint
	for _, name := range strings.Fields(names) {
		x |= 1 << slices.Index(r, name)
	}
	return x
}

func sides(fd string) (uint, uint) {
	lhs, rhs, _ := strings.Cut(fd, "->")
	return mask(lhs), mask(rhs)
}

func closure(x uint, fds []string) uint {
	for grew := true; grew; {
		grew = false
		for _, fd := range fds {
			if lhs, rhs := sides(fd); lhs&^x == 0 && rhs&^x != 0 {
				x, grew = x|rhs, true
			}
		}
	}
	return x
}

// implies reports whether f implies every dependency of g: Y inside X+ under f.
func implies(f, g string) bool {
	every := true
	for _, fd := range sets[g] {
		lhs, rhs := sides(fd)
		ok := rhs&^closure(lhs, sets[f]) == 0
		every = every && ok
		verdict := "NOT implied"
		if ok {
			verdict = "implied"
		}
		fmt.Printf("  %-28s %s by %s\n", fd, verdict, f)
	}
	return every
}

func main() {
	for _, pair := range [][2]string{{"F", "G"}, {"G", "H"}} {
		f, g := pair[0], pair[1]
		fmt.Printf("%s against %s:\n", f, g)
		first, second := implies(f, g), implies(g, f) // both directions, always
		verdict := "not equivalent"
		if first && second {
			verdict = "equivalent"
		}
		fmt.Printf("  %s and %s are %s\n\n", f, g, 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: bit i stands for r[i].
let r = ["course", "title", "instructor", "office"]
let sets = [
  "F": ["course -> title instructor", "instructor -> office", "course -> office"],
  "G": ["course -> title", "course -> instructor", "instructor -> office"],
  "H": ["course -> title instructor", "course instructor -> office"],
]

func mask(_ names: Substring) -> Int {
  names.split(separator: " ").compactMap { r.firstIndex(of: String($0)) }.reduce(0) { $0 | 1 << $1 }
}

func sides(_ fd: String) -> (lhs: Int, rhs: Int) {
  let arrow = fd.firstIndex(of: "-") ?? fd.endIndex
  return (mask(fd[..<arrow]), mask(fd[arrow...].dropFirst(2)))
}

func closure(_ start: Int, _ fds: [String]) -> Int {
  var (x, grew) = (start, true)
  while grew {
    grew = false
    for (lhs, rhs) in fds.map(sides) where lhs & ~x == 0 && rhs & ~x != 0 {
      (x, grew) = (x | rhs, true)
    }
  }
  return x
}

/// Whether f implies every dependency of g: Y inside X+ under f.
func implies(_ f: String, _ g: String) -> Bool {
  var every = true
  for fd in sets[g, default: []] {
    let (lhs, rhs) = sides(fd)
    let ok = rhs & ~closure(lhs, sets[f, default: []]) == 0
    every = every && ok
    let padded = fd + String(repeating: " ", count: max(0, 28 - fd.count))
    print("  \(padded) \(ok ? "implied" : "NOT implied") by \(f)")
  }
  return every
}

for (f, g) in [("F", "G"), ("G", "H")] {
  print("\(f) against \(g):")
  let both = [implies(f, g), implies(g, f)]  // both directions, always
  print("  \(f) and \(g) are \(both.allSatisfy { $0 } ? "equivalent" : "not equivalent")\n")
}

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

# Sets of attributes are bit masks: bit i stands for R[i].
R = %w[course title instructor office].freeze
SETS = {
  'F' => ['course -> title instructor', 'instructor -> office', 'course -> office'],
  'G' => ['course -> title', 'course -> instructor', 'instructor -> office'],
  'H' => ['course -> title instructor', 'course instructor -> office']
}.freeze

def mask(names)
  names.split.sum { |name| 1 << R.index(name) }
end

def sides(text)
  text.split('->').map { |side| mask(side) }
end

def closure(set, fds)
  loop do
    grown = fds.map { |fd| sides(fd) }
               .reduce(set) { |x, (lhs, rhs)| (lhs & ~x).zero? ? x | rhs : x }
    return set if grown == set

    set = grown
  end
end

# Whether f implies every dependency of g: Y inside X+ under f.
def implies(first, second)
  SETS[second].map do |fd|
    lhs, rhs = sides(fd)
    ok = (rhs & ~closure(lhs, SETS[first])).zero?
    puts "  #{fd.ljust(28)} #{ok ? 'implied' : 'NOT implied'} by #{first}"
    ok
  end.all?
end

[%w[F G], %w[G H]].each do |f, g|
  puts "#{f} against #{g}:"
  both = [implies(f, g), implies(g, f)] # both directions, always
  puts "  #{f} and #{g} are #{both.all? ? 'equivalent' : 'not equivalent'}\n\n"
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: bit i stands for r[i].
val r = listOf("course", "title", "instructor", "office")
val sets =
    mapOf(
        "F" to listOf("course -> title instructor", "instructor -> office", "course -> office"),
        "G" to listOf("course -> title", "course -> instructor", "instructor -> office"),
        "H" to listOf("course -> title instructor", "course instructor -> office"),
    )

fun mask(names: String) = names.trim().split(" ").sumOf { 1 shl r.indexOf(it) }

fun sides(fd: String): Pair<Int, Int> {
    val (lhs, rhs) = fd.split("->")
    return mask(lhs) to mask(rhs)
}

fun closure(
    start: Int,
    fds: List<String>,
): Int {
    var x = start
    var grew = true
    while (grew) {
        grew = false
        for ((lhs, rhs) in fds.map(::sides)) {
            if (lhs and x.inv() == 0 && rhs and x.inv() != 0) {
                x = x or rhs
                grew = true
            }
        }
    }
    return x
}

// Whether f implies every dependency of g: Y inside X+ under f.
fun implies(
    f: String,
    g: String,
): Boolean {
    var every = true
    for (fd in sets.getValue(g)) {
        val (lhs, rhs) = sides(fd)
        val ok = rhs and closure(lhs, sets.getValue(f)).inv() == 0
        every = every && ok
        println("  ${fd.padEnd(28)} ${if (ok) "implied" else "NOT implied"} by $f")
    }
    return every
}

fun main() {
    for ((f, g) in listOf("F" to "G", "G" to "H")) {
        println("$f against $g:")
        val both = listOf(implies(f, g), implies(g, f)) // both directions, always
        println("  $f and $g are ${if (both.all { it }) "equivalent" else "not equivalent"}\n")
    }
}

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

// Sets of attributes are bit masks: bit i stands for r[i].
const r = ['course', 'title', 'instructor', 'office'];
const sets = {
  'F': [
    'course -> title instructor',
    'instructor -> office',
    'course -> office',
  ],
  'G': ['course -> title', 'course -> instructor', 'instructor -> office'],
  'H': ['course -> title instructor', 'course instructor -> office'],
};

int mask(String names) =>
    names.trim().split(' ').fold(0, (x, name) => x | 1 << r.indexOf(name));

(int, int) sides(String fd) {
  final [lhs, rhs] = fd.split('->');
  return (mask(lhs), mask(rhs));
}

int closure(int x, List<String> fds) {
  for (var grew = true; grew;) {
    grew = false;
    for (final (lhs, rhs) in fds.map(sides)) {
      if (lhs & ~x == 0 && rhs & ~x != 0) {
        (x, grew) = (x | rhs, true);
      }
    }
  }
  return x;
}

/// Whether f implies every dependency of g: Y inside X+ under f.
bool implies(String f, String g) {
  var every = true;
  for (final fd in sets[g] ?? const []) {
    final (lhs, rhs) = sides(fd);
    final ok = rhs & ~closure(lhs, sets[f] ?? const []) == 0;
    every = every && ok;
    print('  ${fd.padRight(28)} ${ok ? 'implied' : 'NOT implied'} by $f');
  }
  return every;
}

void main() {
  for (final (f, g) in [('F', 'G'), ('G', 'H')]) {
    print('$f against $g:');
    final both = [implies(f, g), implies(g, f)]; // both directions, always
    final verdict = both.every((ok) => ok) ? 'equivalent' : 'not equivalent';
    print('  $f and $g are $verdict\n');
  }
}

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

F against G:
  course -> title              implied by F
  course -> instructor         implied by F
  instructor -> office         implied by F
  course -> title instructor   implied by G
  instructor -> office         implied by G
  course -> office             implied by G
  F and G are equivalent

G against H:
  course -> title instructor   implied by G
  course instructor -> office  implied by G
  course -> title              implied by H
  course -> instructor         implied by H
  instructor -> office         NOT implied by H
  G and H are not equivalent

F and G are equivalent: the extra line of F, course -> office, follows from G through the instructor. H looks similar and is weaker. It says the office follows from the course and the instructor together, so it says nothing about an instructor without a course, and instructor -> office fails under H. The equivalence of FD sets is a two-way test: checking only that G implies H would have called them the same.

Checkpoint

Check: Equivalence of FD sets

Question 1 of 2 G implies both dependencies of H. What does that prove about G and H?
Choose one answer.

Only that H follows from G; H may still miss a rule of G That H is stronger than G That G and H are equivalent That H implies G as well, since H has fewer dependencies

Show the answer: Question 1 of 2

Answer: Only that H follows from G; H may still miss a rule of G

One direction shows that H says nothing beyond G. Only the other direction, which fails on instructor -> office, decides whether they say the same thing.
Question 2 of 2 Why does G imply course -> office, the extra line of F?
Choose one answer.

G lists course -> office among its dependencies course -> office is a trivial dependency Under G, the closure of course holds instructor and then office Because F implies every dependency of G

Show the answer: Question 2 of 2

Answer: Under G, the closure of course holds instructor and then office

X -> Y follows from G exactly when Y lies inside X+ computed under G. course+ is course, title, instructor and office, so G implies course -> office.

A canonical cover takes three steps, each decided by a closure

Each step keeps the set equivalent to F and removes one kind of waste:

Split the right-hand sides. X -> AB becomes X -> A and X -> B; decomposition and union show that nothing is lost.
Remove extraneous attributes. An attribute A is extraneous attribute: An attribute A on the left-hand side of XA -> B that can be dropped, because X alone already determines B. in XA -> B when X alone determines B, that is when B lies inside X+ under the current set.
Remove redundant dependencies. X -> B is redundant dependency: A dependency that the other dependencies of its set already imply, so removing it leaves an equivalent set. when the others already imply it: B lies inside X+ computed without that dependency.

Step	How to decide it
Split	No test: X -> AB becomes X -> A and X -> B
Extraneous attribute A in XA -> B	Compute X+ under the current set: A goes when B lies inside it
Redundant dependency X -> B	Compute X+ without X -> B: the dependency goes when B still lies inside it

Do the steps in this order, attributes before dependencies. Step through them on the rules of a course table:

Interactive · stage by stage A canonical cover of the course table, step by step Step through the three steps. Each stage shows what it does to the course table's dependencies.

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

Every step as text

Four rules. F says course -> title instructor, instructor -> office dept, course instructor -> office and office -> dept.
Split. Every right-hand side gets one attribute, which gives six dependencies. Union and decomposition show that nothing is lost.
An extraneous attribute. In course instructor -> office, the closure of instructor alone already holds office, so course is extraneous. The dependency becomes instructor -> office, which is now listed twice.
Two redundant ones. One copy of instructor -> office follows from the other, so it goes. instructor -> dept follows from instructor -> office and office -> dept, so it goes too.
The cover. Four dependencies are left, course -> title, course -> instructor, instructor -> office and office -> dept, one for each real rule of the table.

The program runs steps 2 and 3 on the split set, with every decision printed:

One program · 14 languages A canonical cover of the course table, every decision printed

Python 3.14 · main.py

# Sets of attributes are bit masks.
COURSE, TITLE, INSTRUCTOR, OFFICE, DEPT = 1, 2, 4, 8, 16
NAMES = ["course", "title", "instructor", "office", "dept"]
F = [  # step 1, the split, is done
    (COURSE, TITLE),
    (COURSE, INSTRUCTOR),
    (INSTRUCTOR, OFFICE),
    (INSTRUCTOR, DEPT),
    (COURSE | INSTRUCTOR, OFFICE),
    (OFFICE, DEPT),
]


def show(fd: tuple[int, int]) -> str:
    return " -> ".join(
        " ".join(n for i, n in enumerate(NAMES) if x >> i & 1) for x in fd
    )


def closure(x: int, fds: list[tuple[int, int]]) -> int:
    grew = True
    while grew:
        grew = False
        for lhs, rhs in fds:
            if lhs & ~x == 0 and rhs & ~x:
                x, grew = x | rhs, True
    return x


cover = list(F)
for k, (lhs, rhs) in enumerate(cover):  # step 2: extraneous attributes
    for i, name in enumerate(NAMES):
        rest = lhs & ~(1 << i)
        if rest != lhs and rest and rhs & ~closure(rest, cover) == 0:
            print(f"step 2: {name} is extraneous in {show((lhs, rhs))}")
            lhs = rest
    cover[k] = (lhs, rhs)
k = 0
while k < len(cover):  # step 3: redundant dependencies
    others = cover[:k] + cover[k + 1 :]
    if cover[k][1] & ~closure(cover[k][0], others) == 0:
        print(f"step 3: {show(cover[k])} is redundant")
        cover = others
    else:
        k += 1
print("cover:", ", ".join(map(show, cover)))

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 [COURSE, TITLE, INSTRUCTOR, OFFICE, DEPT] = [1, 2, 4, 8, 16];
const NAMES = ["course", "title", "instructor", "office", "dept"];
// Step 1, the split, is done.
const F = [
  [COURSE, TITLE],
  [COURSE, INSTRUCTOR],
  [INSTRUCTOR, OFFICE],
  [INSTRUCTOR, DEPT],
  [COURSE | INSTRUCTOR, OFFICE],
  [OFFICE, DEPT],
];

const names = (x) => NAMES.filter((_, i) => (x >> i) & 1).join(" ");
const show = ([lhs, rhs]) => `${names(lhs)} -> ${names(rhs)}`;

function closure(x, fds) {
  for (let grew = true; grew;) {
    grew = false;
    for (const [lhs, rhs] of fds) {
      if ((lhs & ~x) === 0 && rhs & ~x) [x, grew] = [x | rhs, true];
    }
  }
  return x;
}

let cover = F.map((fd) => [...fd]);
for (const [k, [lhs, rhs]] of cover.entries()) {
  // Step 2: extraneous attributes.
  let left = lhs;
  for (const [i, name] of NAMES.entries()) {
    const rest = left & ~(1 << i);
    if (rest !== left && rest && (rhs & ~closure(rest, cover)) === 0) {
      console.log(`step 2: ${name} is extraneous in ${show([left, rhs])}`);
      left = rest;
    }
  }
  cover[k] = [left, rhs];
}
for (let k = 0; k < cover.length;) {
  // Step 3: redundant dependencies.
  const others = cover.filter((_, j) => j !== k);
  if ((cover[k][1] & ~closure(cover[k][0], others)) === 0) {
    console.log(`step 3: ${show(cover[k])} is redundant`);
    cover = others;
  } else {
    k++;
  }
}
console.log(`cover: ${cover.map(show).join(", ")}`);

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.stream.IntStream;

public class Main {
  // Sets of attributes are bit masks.
  static final int COURSE = 1, TITLE = 2, INSTRUCTOR = 4, OFFICE = 8, DEPT = 16;
  static final List<String> NAMES = List.of("course", "title", "instructor", "office", "dept");

  record Fd(int lhs, int rhs) {}

  // Step 1, the split, is done.
  static final List<Fd> F =
      List.of(
          new Fd(COURSE, TITLE),
          new Fd(COURSE, INSTRUCTOR),
          new Fd(INSTRUCTOR, OFFICE),
          new Fd(INSTRUCTOR, DEPT),
          new Fd(COURSE | INSTRUCTOR, OFFICE),
          new Fd(OFFICE, DEPT));

  static String names(int x) {
    return String.join(
        " ",
        IntStream.range(0, NAMES.size())
            .filter(i -> (x >> i & 1) == 1)
            .mapToObj(NAMES::get)
            .toList());
  }

  static String show(Fd fd) {
    return names(fd.lhs()) + " -> " + names(fd.rhs());
  }

  static int closure(int x, List<Fd> fds) {
    for (boolean grew = true; grew; ) {
      grew = false;
      for (Fd fd : fds) {
        if ((fd.lhs() & ~x) == 0 && (fd.rhs() & ~x) != 0) {
          x |= fd.rhs();
          grew = true;
        }
      }
    }
    return x;
  }

  public static void main(String[] args) {
    List<Fd> cover = new ArrayList<>(F);
    for (int k = 0; k < cover.size(); k++) { // step 2: extraneous attributes
      Fd fd = cover.get(k);
      for (int i = 0; i < NAMES.size(); i++) {
        int rest = fd.lhs() & ~(1 << i);
        if (rest != fd.lhs() && rest != 0 && (fd.rhs() & ~closure(rest, cover)) == 0) {
          System.out.println("step 2: " + NAMES.get(i) + " is extraneous in " + show(fd));
          fd = new Fd(rest, fd.rhs());
        }
      }
      cover.set(k, fd);
    }
    for (int k = 0; k < cover.size(); ) { // step 3: redundant dependencies
      List<Fd> others = new ArrayList<>(cover);
      others.remove(k);
      if ((cover.get(k).rhs() & ~closure(cover.get(k).lhs(), others)) == 0) {
        System.out.println("step 3: " + show(cover.get(k)) + " is redundant");
        cover = others;
      } else {
        k++;
      }
    }
    List<String> shown = cover.stream().map(Main::show).toList();
    System.out.println("cover: " + String.join(", ", shown));
  }
}

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 <print>
#include <string>
#include <utility>
#include <vector>

// Sets of attributes are bit masks.
enum : unsigned {
  COURSE = 1,
  TITLE = 2,
  INSTRUCTOR = 4,
  OFFICE = 8,
  DEPT = 16
};
const std::vector<std::string> NAMES = {"course", "title", "instructor",
                                        "office", "dept"};
using Fd = std::pair<unsigned, unsigned>;
// Step 1, the split, is done.
const std::vector<Fd> F = {
    {COURSE, TITLE},    {COURSE, INSTRUCTOR},          {INSTRUCTOR, OFFICE},
    {INSTRUCTOR, DEPT}, {COURSE | INSTRUCTOR, OFFICE}, {OFFICE, DEPT}};

std::string names(unsigned x) {
  std::string out;
  for (std::size_t i = 0; i < NAMES.size(); i++)
    if (x >> i & 1)
      out += (out.empty() ? "" : " ") + NAMES[i];
  return out;
}

std::string show(const Fd &fd) {
  return names(fd.first) + " -> " + names(fd.second);
}

unsigned closure(unsigned x, const std::vector<Fd> &fds) {
  for (bool grew = true; grew;) {
    grew = false;
    for (const auto &[lhs, rhs] : fds)
      if ((lhs & ~x) == 0 && (rhs & ~x)) {
        x |= rhs;
        grew = true;
      }
  }
  return x;
}

int main() {
  std::vector<Fd> cover = F;
  for (auto &fd : cover) { // step 2: extraneous attributes
    Fd step = fd;
    for (std::size_t i = 0; i < NAMES.size(); i++) {
      const unsigned rest = step.first & ~(1u << i);
      if (rest != step.first && rest &&
          (step.second & ~closure(rest, cover)) == 0) {
        std::println("step 2: {} is extraneous in {}", NAMES[i], show(step));
        step.first = rest;
      }
    }
    fd = step;
  }
  for (std::size_t k = 0; k < cover.size();) { // step 3: redundant ones
    std::vector<Fd> others = cover;
    others.erase(others.begin() + static_cast<std::ptrdiff_t>(k));
    if ((cover[k].second & ~closure(cover[k].first, others)) == 0) {
      std::println("step 3: {} is redundant", show(cover[k]));
      cover = others;
    } else {
      k++;
    }
  }
  std::string listed;
  for (const auto &fd : cover)
    listed += (listed.empty() ? "" : ", ") + show(fd);
  std::println("cover: {}", listed);
}

C# 14 · .NET 10 · app.cs

// Sets of attributes are bit masks.
const int Course = 1, Title = 2, Instructor = 4, Office = 8, Dept = 16;
string[] names = ["course", "title", "instructor", "office", "dept"];
// Step 1, the split, is done.
List<(int Lhs, int Rhs)> cover =
[
    (Course, Title),
    (Course, Instructor),
    (Instructor, Office),
    (Instructor, Dept),
    (Course | Instructor, Office),
    (Office, Dept),
];

for (int k = 0; k < cover.Count; k++) // step 2: extraneous attributes
{
    var (lhs, rhs) = cover[k];
    for (int i = 0; i < names.Length; i++)
    {
        int rest = lhs & ~(1 << i);
        if (rest != lhs && rest != 0 && (rhs & ~Closure(rest, cover)) == 0)
        {
            Console.WriteLine($"step 2: {names[i]} is extraneous in {Show((lhs, rhs), names)}");
            lhs = rest;
        }
    }
    cover[k] = (lhs, rhs);
}
for (int k = 0; k < cover.Count;) // step 3: redundant dependencies
{
    var others = new List<(int Lhs, int Rhs)>(cover);
    others.RemoveAt(k);
    if ((cover[k].Rhs & ~Closure(cover[k].Lhs, others)) == 0)
    {
        Console.WriteLine($"step 3: {Show(cover[k], names)} is redundant");
        cover = others;
    }
    else
    {
        k++;
    }
}
Console.WriteLine($"cover: {string.Join(", ", cover.Select(fd => Show(fd, names)))}");

static string Show((int Lhs, int Rhs) fd, string[] names)
{
    string Side(int x) => string.Join(" ", names.Where((_, i) => (x >> i & 1) == 1));
    return $"{Side(fd.Lhs)} -> {Side(fd.Rhs)}";
}

static int Closure(int x, List<(int Lhs, int Rhs)> fds)
{
    for (bool grew = true; grew;)
    {
        grew = false;
        foreach (var (lhs, rhs) in fds)
        {
            if ((lhs & ~x) == 0 && (rhs & ~x) != 0)
            {
                x |= rhs;
                grew = true;
            }
        }
    }
    return x;
}

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 { COURSE = 1, TITLE = 2, INSTRUCTOR = 4, OFFICE = 8, DEPT = 16 };
enum { N = 5, TEXT = 64 };
static const char *const NAMES[N] = {"course", "title", "instructor", "office",
                                     "dept"};
static char *names(unsigned x, char *out) {
  out[0] = '\0';
  for (int i = 0; i < N; i++)
    if (x >> i & 1)
      strcat(strcat(out, out[0] ? " " : ""), NAMES[i]);
  return out;
}

static char *show(const unsigned *fd, char *out) {
  char lhs[TEXT], rhs[TEXT];
  snprintf(out, 3 * TEXT, "%s -> %s", names(fd[0], lhs), names(fd[1], rhs));
  return out;
}

// X+ under fds, without fds[skip].
static unsigned closure(unsigned x, unsigned fds[][2], int n, int skip) {
  for (bool grew = true; grew;) {
    grew = false;
    for (int k = 0; k < n; k++)
      if (k != skip && (fds[k][0] & ~x) == 0 && (fds[k][1] & ~x)) {
        x |= fds[k][1];
        grew = true;
      }
  }
  return x;
}

int main(void) {
  // Step 1, the split, is done.
  unsigned cover[][2] = {
      {COURSE, TITLE},    {COURSE, INSTRUCTOR},          {INSTRUCTOR, OFFICE},
      {INSTRUCTOR, DEPT}, {COURSE | INSTRUCTOR, OFFICE}, {OFFICE, DEPT}};
  int n = sizeof cover / sizeof cover[0];
  char text[3 * TEXT];
  for (int k = 0; k < n; k++) { // step 2: extraneous attributes
    unsigned lhs = cover[k][0];
    for (int i = 0; i < N; i++) {
      const unsigned rest = lhs & ~(1u << i);
      if (rest != lhs && rest &&
          (cover[k][1] & ~closure(rest, cover, n, -1)) == 0) {
        const unsigned step[2] = {lhs, cover[k][1]};
        printf("step 2: %s is extraneous in %s\n", NAMES[i], show(step, text));
        lhs = rest;
      }
    }
    cover[k][0] = lhs;
  }
  for (int k = 0; k < n;) { // step 3: redundant dependencies
    if ((cover[k][1] & ~closure(cover[k][0], cover, n, k)) == 0) {
      printf("step 3: %s is redundant\n", show(cover[k], text));
      memmove(cover[k], cover[k + 1], (size_t)(n - k - 1) * sizeof cover[0]);
      n--;
    } else {
      k++;
    }
  }
  for (int k = 0; k < n; k++)
    printf("%s%s", k ? ", " : "cover: ", show(cover[k], text));
  printf("\n");
  return 0;
}

PHP 8.5 · main.php

<?php

declare(strict_types=1);

// Sets of attributes are bit masks.
const COURSE = 1, TITLE = 2, INSTRUCTOR = 4, OFFICE = 8, DEPT = 16;
const NAMES = ['course', 'title', 'instructor', 'office', 'dept'];
// Step 1, the split, is done.
const F = [
    [COURSE, TITLE],
    [COURSE, INSTRUCTOR],
    [INSTRUCTOR, OFFICE],
    [INSTRUCTOR, DEPT],
    [COURSE | INSTRUCTOR, OFFICE],
    [OFFICE, DEPT],
];

/** @param array{int, int} $fd */
function show(array $fd): string
{
    $side = fn(int $x): string => implode(' ', array_filter(
        NAMES,
        fn(int $i): bool => ($x >> $i & 1) === 1,
        ARRAY_FILTER_USE_KEY,
    ));
    return $side($fd[0]) . ' -> ' . $side($fd[1]);
}

/** @param list<array{int, int}> $fds */
function closure(int $x, array $fds): int
{
    do {
        $grew = false;
        foreach ($fds as [$lhs, $rhs]) {
            if (($lhs & ~$x) === 0 && ($rhs & ~$x) !== 0) {
                $x |= $rhs;
                $grew = true;
            }
        }
    } while ($grew);
    return $x;
}

$cover = F;
foreach ($cover as $k => [$lhs, $rhs]) { // step 2: extraneous attributes
    foreach (NAMES as $i => $name) {
        $rest = $lhs & ~(1 << $i);
        if ($rest !== $lhs && $rest !== 0 && ($rhs & ~closure($rest, $cover)) === 0) {
            echo "step 2: {$name} is extraneous in " . show([$lhs, $rhs]) . "\n";
            $lhs = $rest;
        }
    }
    $cover[$k] = [$lhs, $rhs];
}
for ($k = 0; $k < count($cover);) { // step 3: redundant dependencies
    $others = $cover;
    array_splice($others, $k, 1);
    if (($cover[$k][1] & ~closure($cover[$k][0], $others)) === 0) {
        echo 'step 3: ' . show($cover[$k]) . " is redundant\n";
        $cover = $others;
    } else {
        $k++;
    }
}
echo 'cover: ' . implode(', ', array_map(show(...), $cover)) . "\n";

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 COURSE: u32 = 1;
const TITLE: u32 = 2;
const INSTRUCTOR: u32 = 4;
const OFFICE: u32 = 8;
const DEPT: u32 = 16;
const NAMES: [&str; 5] = ["course", "title", "instructor", "office", "dept"];
// Step 1, the split, is done.
const F: [(u32, u32); 6] = [
    (COURSE, TITLE),
    (COURSE, INSTRUCTOR),
    (INSTRUCTOR, OFFICE),
    (INSTRUCTOR, DEPT),
    (COURSE | INSTRUCTOR, OFFICE),
    (OFFICE, DEPT),
];

fn show((lhs, rhs): (u32, u32)) -> String {
    let side = |x: u32| {
        let picked: Vec<&str> = (0..NAMES.len())
            .filter(|i| x >> i & 1 == 1)
            .map(|i| NAMES[i])
            .collect();
        picked.join(" ")
    };
    format!("{} -> {}", side(lhs), side(rhs))
}

fn closure(mut x: u32, fds: &[(u32, u32)]) -> u32 {
    let mut grew = true;
    while grew {
        grew = false;
        for &(lhs, rhs) in fds {
            if lhs & !x == 0 && rhs & !x != 0 {
                (x, grew) = (x | rhs, true);
            }
        }
    }
    x
}

fn main() {
    let mut cover = F.to_vec();
    for k in 0..cover.len() {
        // Step 2: extraneous attributes.
        let (mut lhs, rhs) = cover[k];
        for (i, name) in NAMES.iter().enumerate() {
            let rest = lhs & !(1 << i);
            if rest != lhs && rest != 0 && rhs & !closure(rest, &cover) == 0 {
                println!("step 2: {name} is extraneous in {}", show((lhs, rhs)));
                lhs = rest;
            }
        }
        cover[k] = (lhs, rhs);
    }
    let mut k = 0;
    while k < cover.len() {
        // Step 3: redundant dependencies.
        let mut others = cover.clone();
        let (lhs, rhs) = others.remove(k);
        if rhs & !closure(lhs, &others) == 0 {
            println!("step 3: {} is redundant", show((lhs, rhs)));
            cover = others;
        } else {
            k += 1;
        }
    }
    let shown: Vec<String> = cover.into_iter().map(show).collect();
    println!("cover: {}", shown.join(", "));
}

TypeScript 6.0 · main.ts

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

const [COURSE, TITLE, INSTRUCTOR, OFFICE, DEPT] = [1, 2, 4, 8, 16];
const NAMES = ["course", "title", "instructor", "office", "dept"];
// Step 1, the split, is done.
const F: Fd[] = [
  [COURSE, TITLE],
  [COURSE, INSTRUCTOR],
  [INSTRUCTOR, OFFICE],
  [INSTRUCTOR, DEPT],
  [COURSE | INSTRUCTOR, OFFICE],
  [OFFICE, DEPT],
];

const names = (x: number): string => NAMES.filter((_, i) => (x >> i) & 1).join(" ");
const show = ([lhs, rhs]: Fd): string => `${names(lhs)} -> ${names(rhs)}`;

function closure(x: number, fds: Fd[]): number {
  for (let grew = true; grew;) {
    grew = false;
    for (const [lhs, rhs] of fds) {
      if ((lhs & ~x) === 0 && rhs & ~x) [x, grew] = [x | rhs, true];
    }
  }
  return x;
}

let cover = F.map((fd): Fd => [...fd]);
for (const [k, [lhs, rhs]] of cover.entries()) {
  // Step 2: extraneous attributes.
  let left = lhs;
  for (const [i, name] of NAMES.entries()) {
    const rest = left & ~(1 << i);
    if (rest !== left && rest && (rhs & ~closure(rest, cover)) === 0) {
      console.log(`step 2: ${name} is extraneous in ${show([left, rhs])}`);
      left = rest;
    }
  }
  cover[k] = [left, rhs];
}
for (let k = 0; k < cover.length;) {
  // Step 3: redundant dependencies.
  const others = cover.filter((_, j) => j !== k);
  if ((cover[k][1] & ~closure(cover[k][0], others)) === 0) {
    console.log(`step 3: ${show(cover[k])} is redundant`);
    cover = others;
  } else {
    k++;
  }
}
console.log(`cover: ${cover.map(show).join(", ")}`);

Go 1.27 · main.go

package main

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

// Sets of attributes are bit masks.
const Course, Title, Instructor, Office, Dept = 1, 2, 4, 8, 16

var names = []string{"course", "title", "instructor", "office", "dept"}

// Step 1, the split, is done.
var f = [][2]uint{
	{Course, Title},
	{Course, Instructor},
	{Instructor, Office},
	{Instructor, Dept},
	{Course | Instructor, Office},
	{Office, Dept},
}

func show(fd [2]uint) string {
	sides := make([]string, 2)
	for s, x := range fd {
		var picked []string
		for i, name := range names {
			if x>>i&1 == 1 {
				picked = append(picked, name)
			}
		}
		sides[s] = strings.Join(picked, " ")
	}
	return sides[0] + " -> " + sides[1]
}

func closure(x uint, fds [][2]uint) uint {
	for grew := true; grew; {
		grew = false
		for _, fd := range fds {
			if fd[0]&^x == 0 && fd[1]&^x != 0 {
				x, grew = x|fd[1], true
			}
		}
	}
	return x
}

func main() {
	cover := slices.Clone(f)
	for k, fd := range cover { // step 2: extraneous attributes
		for i, name := range names {
			rest := fd[0] &^ (1 << i)
			if rest != fd[0] && rest != 0 && fd[1]&^closure(rest, cover) == 0 {
				fmt.Printf("step 2: %s is extraneous in %s\n", name, show(fd))
				fd[0] = rest
			}
		}
		cover[k] = fd
	}
	for k := 0; k < len(cover); { // step 3: redundant dependencies
		others := slices.Delete(slices.Clone(cover), k, k+1)
		if cover[k][1]&^closure(cover[k][0], others) == 0 {
			fmt.Printf("step 3: %s is redundant\n", show(cover[k]))
			cover = others
		} else {
			k++
		}
	}
	shown := make([]string, len(cover))
	for k, fd := range cover {
		shown[k] = show(fd)
	}
	fmt.Println("cover:", strings.Join(shown, ", "))
}

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 (course, title, instructor, office, dept) = (1, 2, 4, 8, 16)
let names = ["course", "title", "instructor", "office", "dept"]
// Step 1, the split, is done.
let f = [
  (course, title),
  (course, instructor),
  (instructor, office),
  (instructor, dept),
  (course | instructor, office),
  (office, dept),
]

func show(_ fd: (Int, Int)) -> String {
  func side(_ x: Int) -> String {
    names.indices.filter { x >> $0 & 1 == 1 }.map { names[$0] }.joined(separator: " ")
  }
  return "\(side(fd.0)) -> \(side(fd.1))"
}

func closure(_ start: Int, _ fds: [(Int, Int)]) -> Int {
  var (x, grew) = (start, true)
  while grew {
    grew = false
    for (lhs, rhs) in fds where lhs & ~x == 0 && rhs & ~x != 0 {
      (x, grew) = (x | rhs, true)
    }
  }
  return x
}

var cover = f
for k in cover.indices {  // step 2: extraneous attributes
  var (lhs, rhs) = cover[k]
  for (i, name) in names.enumerated() {
    let rest = lhs & ~(1 << i)
    if rest != lhs && rest != 0 && rhs & ~closure(rest, cover) == 0 {
      print("step 2: \(name) is extraneous in \(show((lhs, rhs)))")
      lhs = rest
    }
  }
  cover[k] = (lhs, rhs)
}
var k = 0
while k < cover.count {  // step 3: redundant dependencies
  var others = cover
  others.remove(at: k)
  if cover[k].1 & ~closure(cover[k].0, others) == 0 {
    print("step 3: \(show(cover[k])) is redundant")
    cover = others
  } else {
    k += 1
  }
}
print("cover: \(cover.map(show).joined(separator: ", "))")

Ruby 4.0 · main.rb

# frozen_string_literal: true

# Sets of attributes are bit masks.
COURSE = 1
TITLE = 2
INSTRUCTOR = 4
OFFICE = 8
DEPT = 16
NAMES = %w[course title instructor office dept].freeze
# Step 1, the split, is done.
F = [
  [COURSE, TITLE],
  [COURSE, INSTRUCTOR],
  [INSTRUCTOR, OFFICE],
  [INSTRUCTOR, DEPT],
  [COURSE | INSTRUCTOR, OFFICE],
  [OFFICE, DEPT]
].freeze

def show(dep)
  dep.map { |x| NAMES.select.with_index { |_, i| x[i] == 1 }.join(' ') }.join(' -> ')
end

def closure(set, fds)
  loop do
    grown = fds.reduce(set) { |x, (lhs, rhs)| (lhs & ~x).zero? ? x | rhs : x }
    return set if grown == set

    set = grown
  end
end

cover = F.map(&:dup)
cover.each do |dep| # step 2: extraneous attributes
  lhs, rhs = dep
  NAMES.each_with_index do |name, i|
    rest = lhs & ~(1 << i)
    next unless rest != lhs && rest.positive? && (rhs & ~closure(rest, cover)).zero?

    puts "step 2: #{name} is extraneous in #{show([lhs, rhs])}"
    lhs = rest
  end
  dep[0] = lhs
end
k = 0
while k < cover.size # step 3: redundant dependencies
  others = cover.reject.with_index { |_, j| j == k }
  if (cover[k][1] & ~closure(cover[k][0], others)).zero?
    puts "step 3: #{show(cover[k])} is redundant"
    cover = others
  else
    k += 1
  end
end
puts "cover: #{cover.map { |dep| show(dep) }.join(', ')}"

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 COURSE = 1
const val TITLE = 2
const val INSTRUCTOR = 4
const val OFFICE = 8
const val DEPT = 16
val names = listOf("course", "title", "instructor", "office", "dept")

// Step 1, the split, is done.
val f =
    listOf(
        COURSE to TITLE,
        COURSE to INSTRUCTOR,
        INSTRUCTOR to OFFICE,
        INSTRUCTOR to DEPT,
        (COURSE or INSTRUCTOR) to OFFICE,
        OFFICE to DEPT,
    )

fun show(fd: Pair<Int, Int>): String {
    fun side(x: Int) = names.filterIndexed { i, _ -> x shr i and 1 == 1 }.joinToString(" ")
    return "${side(fd.first)} -> ${side(fd.second)}"
}

fun List<Pair<Int, Int>>.closure(start: Int): Int {
    var x = start
    var grew = true
    while (grew) {
        grew = false
        for ((lhs, rhs) in this) {
            if (lhs and x.inv() == 0 && rhs and x.inv() != 0) {
                x = x or rhs
                grew = true
            }
        }
    }
    return x
}

fun main() {
    var cover = f.toMutableList()
    for (k in cover.indices) { // step 2: extraneous attributes
        var (lhs, rhs) = cover[k]
        for ((i, name) in names.withIndex()) {
            val rest = lhs and (1 shl i).inv()
            if (rest != lhs && rest != 0 && rhs and cover.closure(rest).inv() == 0) {
                println("step 2: $name is extraneous in ${show(lhs to rhs)}")
                lhs = rest
            }
        }
        cover[k] = lhs to rhs
    }
    var k = 0
    while (k < cover.size) { // step 3: redundant dependencies
        val others = cover.filterIndexed { j, _ -> j != k }.toMutableList()
        if (cover[k].second and others.closure(cover[k].first).inv() == 0) {
            println("step 3: ${show(cover[k])} is redundant")
            cover = others
        } else {
            k++
        }
    }
    println("cover: ${cover.joinToString(", ") { show(it) }}")
}

Dart 3.13 · main.dart

// Sets of attributes are bit masks.
const course = 1, title = 2, instructor = 4, office = 8, dept = 16;
const names = ['course', 'title', 'instructor', 'office', 'dept'];
// Step 1, the split, is done.
const f = [
  (course, title),
  (course, instructor),
  (instructor, office),
  (instructor, dept),
  (course | instructor, office),
  (office, dept),
];

String show((int, int) fd) {
  String side(int x) => [
    for (var i = 0; i < names.length; i++)
      if (x >> i & 1 == 1) names[i],
  ].join(' ');
  return '${side(fd.$1)} -> ${side(fd.$2)}';
}

int closure(int x, List<(int, int)> fds) {
  for (var grew = true; grew;) {
    grew = false;
    for (final (lhs, rhs) in fds) {
      if (lhs & ~x == 0 && rhs & ~x != 0) {
        (x, grew) = (x | rhs, true);
      }
    }
  }
  return x;
}

void main() {
  var cover = [...f];
  for (var k = 0; k < cover.length; k++) {
    // Step 2: extraneous attributes.
    var (lhs, rhs) = cover[k];
    for (final (i, name) in names.indexed) {
      final rest = lhs & ~(1 << i);
      if (rest != lhs && rest != 0 && rhs & ~closure(rest, cover) == 0) {
        print('step 2: $name is extraneous in ${show((lhs, rhs))}');
        lhs = rest;
      }
    }
    cover[k] = (lhs, rhs);
  }
  for (var k = 0; k < cover.length;) {
    // Step 3: redundant dependencies.
    final others = [...cover]..removeAt(k);
    if (cover[k].$2 & ~closure(cover[k].$1, others) == 0) {
      print('step 3: ${show(cover[k])} is redundant');
      cover = others;
    } else {
      k++;
    }
  }
  print('cover: ${cover.map(show).join(', ')}');
}

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

step 2: course is extraneous in course instructor -> office
step 3: instructor -> office is redundant
step 3: instructor -> dept is redundant
cover: course -> title, course -> instructor, instructor -> office, office -> dept

Step 2 tried course first in course instructor -> office and found that instructor+ already contains office, so course goes, and the dependency becomes instructor -> office, which is already in the set. Step 3 then removes one copy of instructor -> office, which the other copy implies, and instructor -> dept, which follows from instructor -> office and office -> dept. Four dependencies remain, one for each real rule of the table. This lesson keeps one attribute per right-hand side, so that every test is a single closure.

Canonical covers are not unique. When two attributes or two dependencies could each be removed, the one tested first goes, and different orders give different covers that are all valid, so an answer is judged by equivalence and minimality, never by an exact match.

Key idea

Split first, then drop extraneous attributes, then redundant dependencies: every decision is one closure, and the result says exactly what F says with nothing to spare.

Checkpoint

Check: The three steps of a canonical cover

Question 1 of 2 F = {AB -> C, B -> C}. Which attribute is extraneous in AB -> C?
Choose one answer.

A Both A and B Neither B

Show the answer: Question 1 of 2

Answer: A

Test each attribute of the left-hand side with one closure: drop it, compute the closure of the rest under F, and see whether the right-hand side is still inside. Dropping A leaves B -> C, already in F, which step 3 then removes as a copy.
Question 2 of 2 After step 2 on the course table, instructor -> office is listed twice. What does step 3 do with the two copies?
Choose one answer.

It keeps both, because neither has an extraneous attribute It merges them into instructor -> office office It removes one copy, because the other one implies it It removes both copies

Show the answer: Question 2 of 2

Answer: It removes one copy, because the other one implies it

The redundancy test removes copies without a special rule: a copy always follows from its twin. The program printed it as the first redundant dependency.

Practise: two canonical covers

The exercise asks for canonical covers of two sets, and its sample tests accept any cover that is equivalent and minimal, in any order.

Exercise · Medium · Python

Write two canonical covers that a checker accepts

Write a canonical cover of each set in covers.py, as a list of pairs of strings: ("AB", "C") means AB -> C.

COVER_1: a canonical cover of F1 = {AB -> C, A -> B, B -> D, D -> C}.
COVER_2: a canonical cover of F2 = {A -> BC, B -> A, C -> D, AB -> D}.

Give every dependency a single attribute on its right-hand side. The sample tests accept any cover that is equivalent to the original set, has no extraneous attribute on a left-hand side and no redundant dependency, in any order, so two different answers can both be right. When a test fails, its message names the first problem it found.

Starter code · covers.py

"""Your canonical covers. A dependency is a pair of strings of single-letter
attributes: ("AB", "C") means AB -> C. Give every dependency one attribute on its
right-hand side; any valid cover is accepted, in any order.
"""

# Task 1: a canonical cover of F1 = {AB -> C, A -> B, B -> D, D -> C}.
COVER_1 = [
    ("AB", "C"),
]

# Task 2: a canonical cover of F2 = {A -> BC, B -> A, C -> D, AB -> D}.
COVER_2 = []

The sample tests · test_covers.py

from covers import COVER_1, COVER_2

F1 = [("AB", "C"), ("A", "B"), ("B", "D"), ("D", "C")]
F2 = [("A", "BC"), ("B", "A"), ("C", "D"), ("AB", "D")]


def closure(attrs, fds):
    result = set(attrs)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if set(lhs) <= result and not set(rhs) <= result:
                result |= set(rhs)
                changed = True
    return result


def problem(f, cover):
    """The first reason the cover is not a canonical cover of f, or None."""
    if not cover:
        return "the cover is empty"
    for lhs, rhs in cover:
        if len(rhs) != 1:
            return f"{lhs} -> {rhs}: give each dependency one attribute on the right"
    for lhs, rhs in f:
        if not set(rhs) <= closure(lhs, cover):
            return f"the cover does not imply {lhs} -> {rhs}"
    for lhs, rhs in cover:
        if not set(rhs) <= closure(lhs, f):
            return f"{lhs} -> {rhs} does not follow from the original set"
    for lhs, rhs in cover:
        for a in lhs:
            rest = lhs.replace(a, "")
            if rest and set(rhs) <= closure(rest, cover):
                return f"{a} is extraneous in {lhs} -> {rhs}"
    for i, (lhs, rhs) in enumerate(cover):
        if set(rhs) <= closure(lhs, cover[:i] + cover[i + 1:]):
            return f"{lhs} -> {rhs} is redundant"
    return None


def test_cover_1():
    """COVER_1 is equivalent to F1, with no extraneous attribute and no redundant dependency"""
    assert problem(F1, COVER_1) is None


def test_cover_2():
    """COVER_2 is equivalent to F2, with no extraneous attribute and no redundant dependency"""
    assert problem(F2, COVER_2) is None

A hint

Follow the three steps in order. Split A -> BC into A -> B and A -> C. For AB -> C, compute A+ and B+ under the whole set: if either one already contains C, the other attribute is extraneous. Only then test each dependency for redundancy, by computing the closure of its left-hand side without it.

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 try equivalence and the three steps of a cover, starting from the one you are least sure of.

Why covers differ: removal order reproduced, and a checker that is fair Pro: opens with a Pro, Premium or Ultimate pass

A canonical cover depends on the order of the tests, and on the order of the steps themselves. This part reproduces both effects in code and builds a checker that accepts every valid answer and nothing else.

In this part:

One set, three valid covers, reproduced
Steps in the wrong order: a failure reproduced
Grading any valid answer: what a fair checker tests

3 runnable examples (Python) · about 4 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).

Covers at work: minimum covers, the cost of an equivalence test and 3NF synthesis Pro: opens with a Pro, Premium or Ultimate pass

A canonical cover is minimal, which is weaker than minimum, and the difference shows up in the schemas built from it. This part compares cover sizes, counts what an equivalence test costs, and shows the choice of cover changing the tables that 3NF synthesis produces.

In this part:

Minimal is not minimum, counted
The cost of an equivalence test, with numbers
Why the cover changes the 3NF schema

1 runnable example (Python) · 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 makes an attribute extraneous in a functional dependency, and how do you test for it?

An attribute A on the left-hand side of XA -> B is extraneous when X alone already determines B, so the dependency says the same thing without A. Test it with one closure: compute X+ under the current set of dependencies, XA -> B included, and check whether B lies inside it. In F = {AB -> C, A -> B}, A+ is {A, B, C}, so B is extraneous in AB -> C, and the dependency becomes A -> C. When you compute a canonical cover, remove extraneous attributes before you remove redundant dependencies.
Fresher to mid

Compute a canonical cover of F = {A -> BC, B -> C, AB -> D, D -> BC}, justifying each removal. The interviewer then shows the cover {A -> D, D -> B, D -> C, B -> C}. Is it also correct?

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

Two teams wrote down the rules of the same orders table as sets of functional dependencies, 12 in one set and 9 in the other. How do you check whether the two sets say the same thing, and what do you do with a rule that only one of them implies?

Model answer, Pro. First step and follow-ups
Senior to staff

Your schema script runs 3NF synthesis on a canonical cover. One run produced three tables and another run one table, from the same dependencies. Which output is right, and how do you make the script deterministic?

Model answer, Pro. First step and follow-ups

Key takeaways

Two sets of dependencies are equivalent when each implies every dependency of the other; testing one direction only, as G against H showed, can accept a weaker set.
A canonical cover has one attribute per right-hand side, no extraneous attribute and no redundant dependency, and it is equivalent to F.
Remove extraneous attributes before redundant dependencies, and decide each removal with one closure.
Canonical covers are not unique, so answers are checked for equivalence and minimality, not matched.

Terms in this lesson

canonical cover: A set of functional dependencies equivalent to F that has no extraneous attribute and no redundant dependency.
equivalent sets of dependencies: Two sets of functional dependencies that each imply every dependency of the other, so they allow exactly the same tables.
extraneous attribute: An attribute A on the left-hand side of XA -> B that can be dropped, because X alone already determines B.
redundant dependency: A dependency that the other dependencies of its set already imply, so removing it leaves an equivalent set.

References

P. A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies (ACM Transactions on Database Systems)
D. Maier: Minimum Covers in the Relational Database Model (Journal of the ACM)
C. Beeri and P. A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas (ACM Transactions on Database Systems)

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

Canonical cover and equivalence of FD sets

What you will learn

Before you start

What you will learn

Before you start

Two sets of dependencies are equivalent when each implies the other

A canonical cover takes three steps, each decided by a closure

Practise: two canonical covers

Write two canonical covers that a checker accepts

Results of the sample tests

Why covers differ: removal order reproduced, and a checker that is fair Pro: opens with a Pro, Premium or Ultimate pass

Covers at work: minimum covers, the cost of an equivalence test and 3NF synthesis Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What makes an attribute extraneous in a functional dependency, and how do you test for it?

Compute a canonical cover of F = {A -> BC, B -> C, AB -> D, D -> BC}, justifying each removal. The interviewer then shows the cover {A -> D, D -> B, D -> C, B -> C}. Is it also correct?

Two teams wrote down the rules of the same orders table as sets of functional dependencies, 12 in one set and 9 in the other. How do you check whether the two sets say the same thing, and what do you do with a rule that only one of them implies?

Your schema script runs 3NF synthesis on a canonical cover. One run produced three tables and another run one table, from the same dependencies. Which output is right, and how do you make the script deterministic?

Key takeaways

References