Database Management Systems (DBMS) Module 6 – Functional dependencies

Attribute closure and finding candidate keys

Compute the closure X+ of a set of attributes, use it to test superkeys and implied dependencies, and find every candidate key of a relation.

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

Free: A closure grows until a pass adds nothing · One closure answers three questions · Every candidate key grows from the attributes no rule produces · Practise: closures and keys. With a pass: 2 in-depth parts and 3 interview answers, about 9 minutes.

What you will learn

Compute X+ with the closure algorithm, pass by pass
Use one closure to test a superkey, a candidate key or an implied dependency
Find every candidate key of a relation from its core and list the prime attributes
Prove that the key search finds every key, and count superkeys from the keys
Measure the key search against brute force and recognise relations whose keys explode

Before you start

Functional dependencies and Armstrong's axioms

What you’ll learn · Before you start

What you will learn

Compute X+ with the closure algorithm, pass by pass
Use one closure to test a superkey, a candidate key or an implied dependency
Find every candidate key of a relation from its core and list the prime attributes
Prove that the key search finds every key, and count superkeys from the keys
Measure the key search against brute force and recognise relations whose keys explode

Before you start

Functional dependencies and Armstrong's axioms

On this page

Which sets of a timetable’s 7 attributes identify a row? Trying all 128 subsets works, but one short loop answers faster. The attribute closure: X+, the set of all attributes that the attributes X determine through the functional dependencies, X itself included. X+ of a set of attributes X under the dependencies F is every attribute that X determines: start with X, keep adding the right-hand side of every dependency whose left-hand side is already inside the set, and stop when a whole pass adds nothing.

One closure answers two common questions. X 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” exactly when X+ holds every attribute of the relation, and X -> Y follows from F exactly when Y lies inside X+. A candidate key: A minimal superkey: a set of attributes that identifies every row, from which no attribute can be removed. More in “Keys: super, candidate, primary, alternate, foreign” is a superkey with no attribute to spare. Finding candidate keys needs one more idea: the keys grow from the attributes that appear on no right-hand side. This lesson runs both on a college timetable, in 14 languages.

A closure grows until a pass adds nothing

The timetable records, term by term, which section of a course meets in which room and slot and who teaches it. Its dependencies come from the rules of the college: a section of a course has one instructor, room and slot in a term; a room at a slot holds one section; an instructor at a slot is in one room; and each room is in one building. Step through the closure of {term, instructor, slot}:

Interactive · step by step The closure of {term, instructor, slot}, pass by pass Step through the passes. An attribute with a tick is in the closure; the rule that adds it is in the narration.

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

Every step as text

Start. The closure starts as the attributes themselves, term, instructor and slot. The other four are not in it yet.
Pass 1: two rules wait. term course section -> instructor room slot cannot fire, because course and section are missing. term room slot -> course section cannot fire either, because room is missing.
Pass 1: room. term instructor slot -> room fires, since all three of its attributes are in the set, and it adds room.
Pass 1: building. room -> building comes next in the same pass. room is in now, so it fires and adds building.
Pass 2: course, section. The second pass tries every rule again. term room slot -> course section can fire now that room is in, and it adds course and section.
Pass 3: nothing new. A third pass adds nothing, so the loop stops. The closure holds all 7 attributes, so {term, instructor, slot} is a superkey of the timetable.

The program computes that closure and two more, printing every attribute each pass adds:

One program · 14 languages Three closures of the timetable, computed pass by pass

Python 3.14 · main.py

# Sets of attributes are bit masks: bit i stands for R[i].
R = ["term", "course", "section", "instructor", "room", "slot", "building"]
F = [
    ("term course section", "instructor room slot"),
    ("term room slot", "course section"),
    ("term instructor slot", "room"),
    ("room", "building"),
]


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


def names(x: int) -> str:
    return ", ".join(name for i, name in enumerate(R) if x >> i & 1)


def closure(start: str) -> int:
    x = mask(start)
    print(f"Closure of {{{names(x)}}}")
    number, grew = 0, True
    while grew:  # each pass that goes on adds at least one attribute
        number, grew = number + 1, False
        for lhs, rhs in F:
            new = mask(rhs) & ~x
            if mask(lhs) & ~x == 0 and new:
                x, grew = x | new, True
                print(f"  pass {number}: {lhs} -> {rhs} adds {names(new)}")
    print(f"  pass {number}: nothing new, so the closure is complete")
    verdict = "a superkey" if x == (1 << len(R)) - 1 else "not a superkey"
    print(f"  = {{{names(x)}}}: {x.bit_count()} of {len(R)} attributes, {verdict}")
    return x


closure("term instructor slot")
print()
closure("course section")
print()
plus = closure("term room slot")
implied = "yes" if mask("instructor") & ~plus == 0 else "no"
print(f"Is term room slot -> instructor implied? {implied}")

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 = ["term", "course", "section", "instructor", "room", "slot", "building"];
const F = [
  ["term course section", "instructor room slot"],
  ["term room slot", "course section"],
  ["term instructor slot", "room"],
  ["room", "building"],
];

const mask = (names) => names.split(" ").reduce((x, name) => x | (1 << R.indexOf(name)), 0);
const names = (x) => R.filter((_, i) => (x >> i) & 1).join(", ");
const count = (x) => R.filter((_, i) => (x >> i) & 1).length;

function closure(start) {
  let x = mask(start);
  console.log(`Closure of {${names(x)}}`);
  let [number, grew] = [0, true];
  while (grew) {
    // each pass that goes on adds at least one attribute
    [number, grew] = [number + 1, false];
    for (const [lhs, rhs] of F) {
      const added = mask(rhs) & ~x;
      if ((mask(lhs) & ~x) === 0 && added) {
        [x, grew] = [x | added, true];
        console.log(`  pass ${number}: ${lhs} -> ${rhs} adds ${names(added)}`);
      }
    }
  }
  console.log(`  pass ${number}: nothing new, so the closure is complete`);
  const verdict = x === (1 << R.length) - 1 ? "a superkey" : "not a superkey";
  console.log(`  = {${names(x)}}: ${count(x)} of ${R.length} attributes, ${verdict}`);
  return x;
}

closure("term instructor slot");
console.log();
closure("course section");
console.log();
const plus = closure("term room slot");
console.log(
  `Is term room slot -> instructor implied? ${mask("instructor") & ~plus ? "no" : "yes"}`,
);

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;

public class Main {
  // Sets of attributes are bit masks: bit i stands for R[i].
  static final List<String> R =
      List.of("term", "course", "section", "instructor", "room", "slot", "building");
  static final String[][] F = {
    {"term course section", "instructor room slot"},
    {"term room slot", "course section"},
    {"term instructor slot", "room"},
    {"room", "building"},
  };

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

  static String names(int x) {
    List<String> out = new ArrayList<>();
    for (int i = 0; i < R.size(); i++) {
      if ((x >> i & 1) == 1) {
        out.add(R.get(i));
      }
    }
    return String.join(", ", out);
  }

  static int closure(String start) {
    int x = mask(start);
    System.out.println("Closure of {" + names(x) + "}");
    int number = 0;
    boolean grew = true;
    while (grew) { // each pass that goes on adds at least one attribute
      number++;
      grew = false;
      for (String[] fd : F) {
        int added = mask(fd[1]) & ~x;
        if ((mask(fd[0]) & ~x) == 0 && added != 0) {
          x |= added;
          grew = true;
          System.out.println(
              "  pass " + number + ": " + fd[0] + " -> " + fd[1] + " adds " + names(added));
        }
      }
    }
    System.out.println("  pass " + number + ": nothing new, so the closure is complete");
    String verdict = x == (1 << R.size()) - 1 ? "a superkey" : "not a superkey";
    System.out.println(
        "  = {"
            + names(x)
            + "}: "
            + Integer.bitCount(x)
            + " of "
            + R.size()
            + " attributes, "
            + verdict);
    return x;
  }

  public static void main(String[] args) {
    closure("term instructor slot");
    System.out.println();
    closure("course section");
    System.out.println();
    int plus = closure("term room slot");
    String implied = (mask("instructor") & ~plus) == 0 ? "yes" : "no";
    System.out.println("Is term room slot -> instructor implied? " + implied);
  }
}

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 <bit>
#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 = {"term", "course", "section", "instructor",
                                    "room", "slot",   "building"};
const std::vector<std::pair<std::string, std::string>> F = {
    {"term course section", "instructor room slot"},
    {"term room slot", "course section"},
    {"term instructor slot", "room"},
    {"room", "building"},
};

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::string names(unsigned x) {
  std::string out;
  for (std::size_t i = 0; i < R.size(); i++)
    if (x >> i & 1)
      out += (out.empty() ? "" : ", ") + R[i];
  return out;
}

unsigned closure(const std::string &start) {
  unsigned x = mask(start);
  std::println("Closure of {{{}}}", names(x));
  int number = 0;
  for (bool grew = true; grew;) { // each pass that goes on adds an attribute
    number++;
    grew = false;
    for (const auto &[lhs, rhs] : F) {
      const unsigned added = mask(rhs) & ~x;
      if ((mask(lhs) & ~x) == 0 && added) {
        x |= added;
        grew = true;
        std::println("  pass {}: {} -> {} adds {}", number, lhs, rhs,
                     names(added));
      }
    }
  }
  std::println("  pass {}: nothing new, so the closure is complete", number);
  const bool all = x == (1u << R.size()) - 1;
  std::println("  = {{{}}}: {} of {} attributes, {}", names(x),
               std::popcount(x), R.size(),
               all ? "a superkey" : "not a superkey");
  return x;
}

int main() {
  closure("term instructor slot");
  std::println();
  closure("course section");
  std::println();
  const unsigned plus = closure("term room slot");
  std::println("Is term room slot -> instructor implied? {}",
               (mask("instructor") & ~plus) == 0 ? "yes" : "no");
}

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

using System.Numerics;

// Sets of attributes are bit masks: bit i stands for R[i].
string[] r = ["term", "course", "section", "instructor", "room", "slot", "building"];
(string Lhs, string Rhs)[] f =
[
    ("term course section", "instructor room slot"),
    ("term room slot", "course section"),
    ("term instructor slot", "room"),
    ("room", "building"),
];

Closure("term instructor slot", r, f);
Console.WriteLine();
Closure("course section", r, f);
Console.WriteLine();
int plus = Closure("term room slot", r, f);
string implied = (Mask("instructor", r) & ~plus) == 0 ? "yes" : "no";
Console.WriteLine($"Is term room slot -> instructor implied? {implied}");

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

static string Names(int x, string[] r) => string.Join(", ", r.Where((_, i) => (x >> i & 1) == 1));

static int Closure(string start, string[] r, (string Lhs, string Rhs)[] f)
{
    int x = Mask(start, r);
    Console.WriteLine($"Closure of {{{Names(x, r)}}}");
    int number = 0;
    for (bool grew = true; grew;) // each pass that goes on adds at least one attribute
    {
        number++;
        grew = false;
        foreach (var (lhs, rhs) in f)
        {
            int added = Mask(rhs, r) & ~x;
            if ((Mask(lhs, r) & ~x) == 0 && added != 0)
            {
                x |= added;
                grew = true;
                Console.WriteLine($"  pass {number}: {lhs} -> {rhs} adds {Names(added, r)}");
            }
        }
    }
    Console.WriteLine($"  pass {number}: nothing new, so the closure is complete");
    string verdict = x == (1 << r.Length) - 1 ? "a superkey" : "not a superkey";
    int count = BitOperations.PopCount((uint)x);
    Console.WriteLine($"  = {{{Names(x, r)}}}: {count} of {r.Length} attributes, {verdict}");
    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 = 7, TEXT = 96 };
static const char *const R[N] = {"term", "course", "section", "instructor",
                                 "room", "slot",   "building"};
static const char *const F[][2] = {
    {"term course section", "instructor room slot"},
    {"term room slot", "course section"},
    {"term instructor slot", "room"},
    {"room", "building"},
};

static unsigned mask(const char *names) {
  char copy[TEXT];
  unsigned x = 0;
  strcpy(copy, names);
  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 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] ? ", " : ""), R[i]);
  return out;
}

static unsigned closure(const char *start) {
  unsigned x = mask(start);
  char text[TEXT];
  printf("Closure of {%s}\n", names(x, text));
  int number = 0, count = 0;
  for (bool grew = true; grew;) { // each pass that goes on adds an attribute
    number++;
    grew = false;
    for (size_t k = 0; k < sizeof F / sizeof F[0]; k++) {
      const unsigned added = mask(F[k][1]) & ~x;
      if ((mask(F[k][0]) & ~x) == 0 && added) {
        x |= added;
        grew = true;
        printf("  pass %d: %s -> %s adds %s\n", number, F[k][0], F[k][1],
               names(added, text));
      }
    }
  }
  printf("  pass %d: nothing new, so the closure is complete\n", number);
  for (int i = 0; i < N; i++)
    count += x >> i & 1;
  printf("  = {%s}: %d of %d attributes, %s\n", names(x, text), count, N,
         x == (1u << N) - 1 ? "a superkey" : "not a superkey");
  return x;
}

int main(void) {
  closure("term instructor slot");
  printf("\n");
  closure("course section");
  printf("\n");
  const unsigned plus = closure("term room slot");
  printf("Is term room slot -> instructor implied? %s\n",
         (mask("instructor") & ~plus) == 0 ? "yes" : "no");
  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 = ['term', 'course', 'section', 'instructor', 'room', 'slot', 'building'];
const F = [
    ['term course section', 'instructor room slot'],
    ['term room slot', 'course section'],
    ['term instructor slot', 'room'],
    ['room', 'building'],
];

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

function names(int $x): string
{
    $in = fn(int $i): bool => ($x >> $i & 1) === 1;
    return implode(', ', array_filter(R, $in, ARRAY_FILTER_USE_KEY));
}

function closure(string $start): int
{
    $x = mask($start);
    echo 'Closure of {' . names($x) . "}\n";
    $number = 0;
    do { // each pass that goes on adds at least one attribute
        $number++;
        $grew = false;
        foreach (F as [$lhs, $rhs]) {
            $added = mask($rhs) & ~$x;
            if ((mask($lhs) & ~$x) === 0 && $added !== 0) {
                $x |= $added;
                $grew = true;
                echo "  pass {$number}: {$lhs} -> {$rhs} adds " . names($added) . "\n";
            }
        }
    } while ($grew);
    echo "  pass {$number}: nothing new, so the closure is complete\n";
    $verdict = $x === (1 << count(R)) - 1 ? 'a superkey' : 'not a superkey';
    $count = substr_count(decbin($x), '1');
    echo '  = {' . names($x) . "}: {$count} of " . count(R) . " attributes, {$verdict}\n";
    return $x;
}

closure('term instructor slot');
echo "\n";
closure('course section');
echo "\n";
$plus = closure('term room slot');
$implied = (mask('instructor') & ~$plus) === 0 ? 'yes' : 'no';
echo "Is term room slot -> instructor implied? {$implied}\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; 7] = [
    "term",
    "course",
    "section",
    "instructor",
    "room",
    "slot",
    "building",
];
const F: [(&str, &str); 4] = [
    ("term course section", "instructor room slot"),
    ("term room slot", "course section"),
    ("term instructor slot", "room"),
    ("room", "building"),
];

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 names(x: u32) -> String {
    let picked: Vec<&str> = (0..R.len())
        .filter(|i| x >> i & 1 == 1)
        .map(|i| R[i])
        .collect();
    picked.join(", ")
}

fn closure(start: &str) -> u32 {
    let mut x = mask(start);
    println!("Closure of {{{}}}", names(x));
    let (mut number, mut grew) = (0, true);
    while grew {
        // each pass that goes on adds at least one attribute
        (number, grew) = (number + 1, false);
        for (lhs, rhs) in F {
            let added = mask(rhs) & !x;
            if mask(lhs) & !x == 0 && added != 0 {
                (x, grew) = (x | added, true);
                println!("  pass {number}: {lhs} -> {rhs} adds {}", names(added));
            }
        }
    }
    println!("  pass {number}: nothing new, so the closure is complete");
    let verdict = if x == (1 << R.len()) - 1 {
        "a superkey"
    } else {
        "not a superkey"
    };
    println!(
        "  = {{{}}}: {} of {} attributes, {verdict}",
        names(x),
        x.count_ones(),
        R.len()
    );
    x
}

fn main() {
    closure("term instructor slot");
    println!();
    closure("course section");
    println!();
    let plus = closure("term room slot");
    let implied = if mask("instructor") & !plus == 0 {
        "yes"
    } else {
        "no"
    };
    println!("Is term room slot -> instructor implied? {implied}");
}

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 = ["term", "course", "section", "instructor", "room", "slot", "building"];
const F: [string, string][] = [
  ["term course section", "instructor room slot"],
  ["term room slot", "course section"],
  ["term instructor slot", "room"],
  ["room", "building"],
];

const mask = (names: string): number =>
  names.split(" ").reduce((x, name) => x | (1 << R.indexOf(name)), 0);
const names = (x: number): string => R.filter((_, i) => (x >> i) & 1).join(", ");
const count = (x: number): number => R.filter((_, i) => (x >> i) & 1).length;

function closure(start: string): number {
  let x = mask(start);
  console.log(`Closure of {${names(x)}}`);
  let [number, grew] = [0, true];
  while (grew) {
    // each pass that goes on adds at least one attribute
    [number, grew] = [number + 1, false];
    for (const [lhs, rhs] of F) {
      const added = mask(rhs) & ~x;
      if ((mask(lhs) & ~x) === 0 && added) {
        [x, grew] = [x | added, true];
        console.log(`  pass ${number}: ${lhs} -> ${rhs} adds ${names(added)}`);
      }
    }
  }
  console.log(`  pass ${number}: nothing new, so the closure is complete`);
  const verdict = x === (1 << R.length) - 1 ? "a superkey" : "not a superkey";
  console.log(`  = {${names(x)}}: ${count(x)} of ${R.length} attributes, ${verdict}`);
  return x;
}

closure("term instructor slot");
console.log();
closure("course section");
console.log();
const plus = closure("term room slot");
console.log(
  `Is term room slot -> instructor implied? ${mask("instructor") & ~plus ? "no" : "yes"}`,
);

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"
	"math/bits"
	"slices"
	"strings"
)

// Sets of attributes are bit masks: bit i stands for r[i].
var r = []string{"term", "course", "section", "instructor", "room", "slot", "building"}

var f = [][2]string{
	{"term course section", "instructor room slot"},
	{"term room slot", "course section"},
	{"term instructor slot", "room"},
	{"room", "building"},
}

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

func names(x uint) string {
	var picked []string
	for i, name := range r {
		if x>>i&1 == 1 {
			picked = append(picked, name)
		}
	}
	return strings.Join(picked, ", ")
}

func closure(start string) uint {
	x := mask(start)
	fmt.Printf("Closure of {%s}\n", names(x))
	number := 0
	for grew := true; grew; { // each pass that goes on adds at least one attribute
		number, grew = number+1, false
		for _, fd := range f {
			added := mask(fd[1]) &^ x
			if mask(fd[0])&^x == 0 && added != 0 {
				x, grew = x|added, true
				fmt.Printf("  pass %d: %s -> %s adds %s\n", number, fd[0], fd[1], names(added))
			}
		}
	}
	fmt.Printf("  pass %d: nothing new, so the closure is complete\n", number)
	verdict := "not a superkey"
	if x == 1<<len(r)-1 {
		verdict = "a superkey"
	}
	fmt.Printf("  = {%s}: %d of %d attributes, %s\n", names(x), bits.OnesCount(x), len(r), verdict)
	return x
}

func main() {
	closure("term instructor slot")
	fmt.Println()
	closure("course section")
	fmt.Println()
	plus := closure("term room slot")
	implied := "no"
	if mask("instructor")&^plus == 0 {
		implied = "yes"
	}
	fmt.Println("Is term room slot -> instructor implied?", implied)
}

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 = ["term", "course", "section", "instructor", "room", "slot", "building"]
let f = [
  ("term course section", "instructor room slot"),
  ("term room slot", "course section"),
  ("term instructor slot", "room"),
  ("room", "building"),
]

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

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

@discardableResult
func closure(_ start: String) -> Int {
  var x = mask(start)
  print("Closure of {\(names(x))}")
  var (number, grew) = (0, true)
  while grew {  // each pass that goes on adds at least one attribute
    (number, grew) = (number + 1, false)
    for (lhs, rhs) in f where mask(lhs) & ~x == 0 && mask(rhs) & ~x != 0 {
      let added = mask(rhs) & ~x
      (x, grew) = (x | added, true)
      print("  pass \(number): \(lhs) -> \(rhs) adds \(names(added))")
    }
  }
  print("  pass \(number): nothing new, so the closure is complete")
  let verdict = x == (1 << r.count) - 1 ? "a superkey" : "not a superkey"
  print("  = {\(names(x))}: \(x.nonzeroBitCount) of \(r.count) attributes, \(verdict)")
  return x
}

closure("term instructor slot")
print()
closure("course section")
print()
let plus = closure("term room slot")
print("Is term room slot -> instructor implied? \(mask("instructor") & ~plus == 0 ? "yes" : "no")")

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[term course section instructor room slot building].freeze
F = [
  ['term course section', 'instructor room slot'],
  ['term room slot', 'course section'],
  ['term instructor slot', 'room'],
  %w[room building]
].freeze

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

def names(set)
  R.select.with_index { |_, i| set[i] == 1 }.join(', ')
end

# One pass over F: returns the closure after it, printing what each dependency adds.
def pass(set, number)
  F.reduce(set) do |x, (lhs, rhs)|
    added = mask(rhs) & ~x
    next x unless (mask(lhs) & ~x).zero? && added.positive?

    puts "  pass #{number}: #{lhs} -> #{rhs} adds #{names(added)}"
    x | added
  end
end

# Passes until one adds nothing: each pass that goes on adds at least one attribute.
def grow(set)
  (1..).each do |number|
    grown = pass(set, number)
    return [set, number] if grown == set

    set = grown
  end
end

def closure(start)
  puts "Closure of {#{names(mask(start))}}"
  x, number = grow(mask(start))
  puts "  pass #{number}: nothing new, so the closure is complete"
  verdict = x == (1 << R.size) - 1 ? 'a superkey' : 'not a superkey'
  puts "  = {#{names(x)}}: #{x.digits(2).sum} of #{R.size} attributes, #{verdict}"
  x
end

closure('term instructor slot')
puts
closure('course section')
puts
plus = closure('term room slot')
puts "Is term room slot -> instructor implied? #{(mask('instructor') & ~plus).zero? ? 'yes' : 'no'}"

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("term", "course", "section", "instructor", "room", "slot", "building")
val f =
    listOf(
        "term course section" to "instructor room slot",
        "term room slot" to "course section",
        "term instructor slot" to "room",
        "room" to "building",
    )

fun mask(names: String) = names.split(" ").fold(0) { x, name -> x or (1 shl r.indexOf(name)) }

fun names(x: Int) = r.filterIndexed { i, _ -> x shr i and 1 == 1 }.joinToString(", ")

fun closure(start: String): Int {
    var x = mask(start)
    println("Closure of {${names(x)}}")
    var number = 0
    var grew = true
    while (grew) { // each pass that goes on adds at least one attribute
        number++
        grew = false
        for ((lhs, rhs) in f) {
            val added = mask(rhs) and x.inv()
            if (mask(lhs) and x.inv() == 0 && added != 0) {
                x = x or added
                grew = true
                println("  pass $number: $lhs -> $rhs adds ${names(added)}")
            }
        }
    }
    println("  pass $number: nothing new, so the closure is complete")
    val verdict = if (x == (1 shl r.size) - 1) "a superkey" else "not a superkey"
    println("  = {${names(x)}}: ${x.countOneBits()} of ${r.size} attributes, $verdict")
    return x
}

fun main() {
    closure("term instructor slot")
    println()
    closure("course section")
    println()
    val plus = closure("term room slot")
    val implied = if (mask("instructor") and plus.inv() == 0) "yes" else "no"
    println("Is term room slot -> instructor implied? $implied")
}

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 = [
  'term',
  'course',
  'section',
  'instructor',
  'room',
  'slot',
  'building',
];
const f = [
  ('term course section', 'instructor room slot'),
  ('term room slot', 'course section'),
  ('term instructor slot', 'room'),
  ('room', 'building'),
];

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

String names(int x) => [
  for (var i = 0; i < r.length; i++)
    if (x >> i & 1 == 1) r[i],
].join(', ');

int closure(String start) {
  var x = mask(start);
  print('Closure of {${names(x)}}');
  var number = 0;
  for (var grew = true; grew;) {
    // each pass that goes on adds at least one attribute
    (number, grew) = (number + 1, false);
    for (final (lhs, rhs) in f) {
      final added = mask(rhs) & ~x;
      if (mask(lhs) & ~x == 0 && added != 0) {
        (x, grew) = (x | added, true);
        print('  pass $number: $lhs -> $rhs adds ${names(added)}');
      }
    }
  }
  print('  pass $number: nothing new, so the closure is complete');
  final count = x.toRadixString(2).replaceAll('0', '').length;
  final verdict = x == (1 << r.length) - 1 ? 'a superkey' : 'not a superkey';
  print('  = {${names(x)}}: $count of ${r.length} attributes, $verdict');
  return x;
}

void main() {
  closure('term instructor slot');
  print('');
  closure('course section');
  print('');
  final plus = closure('term room slot');
  final implied = mask('instructor') & ~plus == 0 ? 'yes' : 'no';
  print('Is term room slot -> instructor implied? $implied');
}

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

Closure of {term, instructor, slot}
  pass 1: term instructor slot -> room adds room
  pass 1: room -> building adds building
  pass 2: term room slot -> course section adds course, section
  pass 3: nothing new, so the closure is complete
  = {term, course, section, instructor, room, slot, building}: 7 of 7 attributes, a superkey

Closure of {course, section}
  pass 1: nothing new, so the closure is complete
  = {course, section}: 2 of 7 attributes, not a superkey

Closure of {term, room, slot}
  pass 1: term room slot -> course section adds course, section
  pass 1: room -> building adds building
  pass 2: term course section -> instructor room slot adds instructor
  pass 3: nothing new, so the closure is complete
  = {term, course, section, instructor, room, slot, building}: 7 of 7 attributes, a superkey
Is term room slot -> instructor implied? yes

The loop always stops, because each pass that continues adds at least one attribute and a relation has finitely many. One pass is not enough: in the first closure, the second dependency had to wait for room, which pass 1 added. The order of the dependencies changes how many passes it takes, never the result.

Checkpoint

Check: Computing X+ pass by pass

Question 1 of 2 In the timetable, what is the closure of {term, course, section}?
Choose one answer.

term, course and section only term, course, section, instructor, room and slot term, course, section and building All 7 attributes

Show the answer: Question 1 of 2

Answer: All 7 attributes

The first dependency fires at once and brings instructor, room and slot; room -> building then brings building. {term, course, section} is one of the timetable's three candidate keys.
Question 2 of 2 Why does the closure loop make pass after pass over F, instead of reading F once?
Choose one answer.

Each pass adds exactly one attribute Repeating the passes catches dependencies that are wrong The order of F decides which attributes end up in the closure A dependency that could not fire early may fire once a later one adds what it needs

Show the answer: Question 2 of 2

Answer: A dependency that could not fire early may fire once a later one adds what it needs

One pass fires the dependencies whose left-hand sides are already inside the set. Another pass is needed whenever the first one added something that another dependency was waiting for.

One closure answers three questions

Each question is settled by one closure, or one per attribute for the last:

Question	Compute	Yes when	On the timetable
Is X a superkey of R?	X+	X+ holds every attribute of R	`{term, instructor, slot}`: yes
Does F imply X -> Y?	X+	Y lies inside X+	term room slot -> instructor: yes
Is X a candidate key?	X+, then X+ with each attribute left out	X is a superkey and none of the smaller sets is	`{course, section}`: no, not a superkey

The second question is the practical form of Armstrong’s axioms from the previous lesson: no derivation needs to be found, because implication and membership in the closure are the same thing. Attribute closure turns every question about implied dependencies into one computation.

Checkpoint

Check: What one closure answers

One question Under the timetable's dependencies, does term room slot -> instructor follow?
Choose one answer.

Yes, because instructor lies inside the closure of {term, room, slot} It cannot be decided without the rows of the timetable Only if {term, room, slot} is a candidate key No, because no dependency has term room slot on the left and instructor on the right

Show the answer: One question

Answer: Yes, because instructor lies inside the closure of {term, room, slot}

X -> Y follows from F exactly when Y lies inside X+. {term, room, slot}+ holds all 7 attributes, so it implies instructor and every other attribute.

Every candidate key grows from the attributes no rule produces

Testing every subset of the attributes works, but a relation of 7 attributes has 128 subsets. Finding candidate keys goes faster in three steps:

The core. An attribute on no right-hand side can only come from the key itself, so it is in every key.
The excluded. An attribute that appears only on right-hand sides is always determined by others, so it is in no key.
Grow. Add the remaining attributes to the core in groups of size 0, 1, 2 and so on, compute each closure, and skip every group that contains a key already found, since a superset of a key is never minimal.

Step through the search on the timetable, then run it:

Interactive · stage by stage Every candidate key of the timetable, step by step Step through the search. Each stage shows what it decides about the timetable's attributes.

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

Every step as text

The core. term is on no right-hand side, so no dependency can produce it. It must be in every key, and the search starts from it.
The excluded. building appears only on a right-hand side, so others always determine it. It is in no key.
Groups of 0 and 1. The other five, course, section, instructor, room and slot, are added to the core in groups of growing size. term alone and term with one more attribute are 6 closures, and none reaches all 7 attributes.
Groups of 2. Ten pairs are tried. Three reach every attribute, giving the keys {term, course, section}, {term, instructor, slot} and {term, room, slot}.
Groups of 3 and more. A group that contains a key found already is never minimal, so it is skipped without a closure. Only 2 of the 10 groups of three contain no key, and neither is a superkey. Every larger group contains a key.
18 closures, 3 keys. The search computed 18 closures instead of the 128 that every subset would need. Every attribute but building is in a key, so building is the only non-prime attribute.

One program · 14 languages Every candidate key of the timetable, from its core

Python 3.14 · main.py

# Sets of attributes are bit masks.
R = ["term", "course", "section", "instructor", "room", "slot", "building"]
F = [
    ("term course section", "instructor room slot"),
    ("term room slot", "course section"),
    ("term instructor slot", "room"),
    ("room", "building"),
]
ALL = (1 << len(R)) - 1


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


def names(x: int) -> str:
    return ", ".join(name for i, name in enumerate(R) if x >> i & 1)


def closure(x: int) -> int:
    grew = True
    while grew:
        grew = False
        for lhs, rhs in F:
            if mask(lhs) & ~x == 0 and mask(rhs) & ~x:
                x, grew = x | mask(rhs), True
    return x


left = right = 0
for lhs, rhs in F:
    left, right = left | mask(lhs), right | mask(rhs)
core, middle = ALL & ~right, left & right
keys, tested = [], 0
for extra in sorted(range(ALL + 1), key=int.bit_count):  # smallest groups first
    group = core | extra
    # Groups of the middle only, never a superset of a key.
    if extra & ~middle == 0 and all(key & ~group for key in keys):
        tested += 1
        if closure(group) == ALL:
            keys.append(group)
            print(f"key: {{{names(group)}}}")
print(f"closures: {tested} of {ALL + 1} subsets")

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 R = ["term", "course", "section", "instructor", "room", "slot", "building"];
const F = [
  ["term course section", "instructor room slot"],
  ["term room slot", "course section"],
  ["term instructor slot", "room"],
  ["room", "building"],
];
const ALL = (1 << R.length) - 1;

const mask = (names) => names.split(" ").reduce((x, name) => x | (1 << R.indexOf(name)), 0);
const names = (x) => R.filter((_, i) => (x >> i) & 1).join(", ");
const count = (x) => R.filter((_, i) => (x >> i) & 1).length;

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

let [left, right] = [0, 0];
for (const [lhs, rhs] of F) [left, right] = [left | mask(lhs), right | mask(rhs)];
const [core, middle] = [ALL & ~right, left & right];
const keys = [];
let tested = 0;
// Smallest groups first.
for (const extra of [...Array(ALL + 1).keys()].sort((a, b) => count(a) - count(b) || a - b)) {
  const group = core | extra;
  // Groups of the middle only, never a superset of a key.
  if ((extra & ~middle) === 0 && keys.every((key) => key & ~group)) {
    tested++;
    if (closure(group) === ALL) {
      keys.push(group);
      console.log(`key: {${names(group)}}`);
    }
  }
}
console.log(`closures: ${tested} of ${ALL + 1} subsets`);

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.Comparator;
import java.util.List;
import java.util.stream.IntStream;

public class Main {
  // Sets of attributes are bit masks.
  static final List<String> R =
      List.of("term", "course", "section", "instructor", "room", "slot", "building");
  static final String[][] F = {
    {"term course section", "instructor room slot"},
    {"term room slot", "course section"},
    {"term instructor slot", "room"},
    {"room", "building"},
  };
  static final int ALL = (1 << R.size()) - 1;

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

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

  static int closure(int x) {
    for (boolean grew = true; grew; ) {
      grew = false;
      for (String[] fd : F) {
        if ((mask(fd[0]) & ~x) == 0 && (mask(fd[1]) & ~x) != 0) {
          x |= mask(fd[1]);
          grew = true;
        }
      }
    }
    return x;
  }

  public static void main(String[] args) {
    int left = 0, right = 0;
    for (String[] fd : F) {
      left |= mask(fd[0]);
      right |= mask(fd[1]);
    }
    int core = ALL & ~right, middle = left & right;
    List<Integer> keys = new ArrayList<>();
    int tested = 0;
    // Smallest groups first.
    var order = Comparator.comparingInt(Integer::bitCount).thenComparingInt(x -> x);
    for (int extra : IntStream.rangeClosed(0, ALL).boxed().sorted(order).toList()) {
      int group = core | extra;
      // Groups of the middle only, never a superset of a key.
      if ((extra & ~middle) == 0 && keys.stream().allMatch(key -> (key & ~group) != 0)) {
        tested++;
        if (closure(group) == ALL) {
          keys.add(group);
          System.out.println("key: {" + names(group) + "}");
        }
      }
    }
    System.out.println("closures: " + tested + " of " + (ALL + 1) + " subsets");
  }
}

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

// Sets of attributes are bit masks.
const std::vector<std::string> R = {"term", "course", "section", "instructor",
                                    "room", "slot",   "building"};
const std::vector<std::pair<std::string, std::string>> F = {
    {"term course section", "instructor room slot"},
    {"term room slot", "course section"},
    {"term instructor slot", "room"},
    {"room", "building"},
};
const unsigned ALL = (1u << R.size()) - 1;

unsigned mask(const std::string &names) {
  std::istringstream in(names);
  unsigned x = 0;
  for (std::string name; in >> name;)
    x |= 1u << (std::ranges::find(R, name) - R.begin());
  return x;
}

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

unsigned closure(unsigned x) {
  for (bool grew = true; grew;) {
    grew = false;
    for (const auto &[lhs, rhs] : F)
      if ((mask(lhs) & ~x) == 0 && (mask(rhs) & ~x)) {
        x |= mask(rhs);
        grew = true;
      }
  }
  return x;
}

int main() {
  unsigned left = 0, right = 0;
  for (const auto &[lhs, rhs] : F) {
    left |= mask(lhs);
    right |= mask(rhs);
  }
  const unsigned core = ALL & ~right, middle = left & right;
  std::vector<unsigned> order, keys;
  for (unsigned x = 0; x <= ALL; x++)
    order.push_back(x);
  // Smallest groups first.
  std::ranges::stable_sort(order, {},
                           [](unsigned x) { return std::popcount(x); });
  int tested = 0;
  for (const unsigned extra : order) {
    const unsigned group = core | extra;
    // Groups of the middle only, never a superset of a key.
    if ((extra & ~middle) == 0 &&
        std::ranges::all_of(keys, [&](unsigned key) { return key & ~group; })) {
      tested++;
      if (closure(group) == ALL) {
        keys.push_back(group);
        std::println("key: {{{}}}", names(group));
      }
    }
  }
  std::println("closures: {} of {} subsets", tested, ALL + 1);
}

C# 14 · .NET 10 · app.cs

using System.Numerics;

// Sets of attributes are bit masks.
string[] r = ["term", "course", "section", "instructor", "room", "slot", "building"];
(string Lhs, string Rhs)[] f =
[
    ("term course section", "instructor room slot"),
    ("term room slot", "course section"),
    ("term instructor slot", "room"),
    ("room", "building"),
];
int all = (1 << r.Length) - 1;

int left = 0, right = 0;
foreach (var (lhs, rhs) in f)
{
    left |= Mask(lhs, r);
    right |= Mask(rhs, r);
}
int core = all & ~right, middle = left & right;
var keys = new List<int>();
int tested = 0;
// Smallest groups first.
foreach (int extra in Enumerable.Range(0, all + 1).OrderBy(x => BitOperations.PopCount((uint)x)))
{
    int group = core | extra;
    // Groups of the middle only, never a superset of a key.
    if ((extra & ~middle) == 0 && keys.All(key => (key & ~group) != 0))
    {
        tested++;
        if (Closure(group, r, f) == all)
        {
            keys.Add(group);
            Console.WriteLine($"key: {{{Names(group, r)}}}");
        }
    }
}
Console.WriteLine(FormattableString.Invariant($"closures: {tested} of {all + 1} subsets"));

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

static string Names(int x, string[] r) => string.Join(", ", r.Where((_, i) => (x >> i & 1) == 1));

static int Closure(int x, string[] r, (string Lhs, string Rhs)[] f)
{
    for (bool grew = true; grew;)
    {
        grew = false;
        foreach (var (lhs, rhs) in f)
        {
            if ((Mask(lhs, r) & ~x) == 0 && (Mask(rhs, r) & ~x) != 0)
            {
                x |= Mask(rhs, r);
                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 { N = 7, ALL = (1 << N) - 1, TEXT = 96 };
static const char *const R[N] = {"term", "course", "section", "instructor",
                                 "room", "slot",   "building"};
static const char *const F[][2] = {
    {"term course section", "instructor room slot"},
    {"term room slot", "course section"},
    {"term instructor slot", "room"},
    {"room", "building"},
};
enum { NF = sizeof F / sizeof F[0] };

static unsigned mask(const char *names) {
  char copy[TEXT];
  unsigned x = 0;
  strcpy(copy, names);
  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 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] ? ", " : ""), R[i]);
  return out;
}

static unsigned closure(unsigned x) {
  for (bool grew = true; grew;) {
    grew = false;
    for (int k = 0; k < NF; k++)
      if ((mask(F[k][0]) & ~x) == 0 && (mask(F[k][1]) & ~x)) {
        x |= mask(F[k][1]);
        grew = true;
      }
  }
  return x;
}

static int ones(unsigned x) { return x ? (int)(x & 1) + ones(x >> 1) : 0; }

int main(void) {
  unsigned left = 0, right = 0, keys[ALL + 1];
  for (int k = 0; k < NF; k++) {
    left |= mask(F[k][0]);
    right |= mask(F[k][1]);
  }
  const unsigned core = ALL & ~right, middle = left & right;
  int nkeys = 0, tested = 0;
  char text[TEXT];
  for (int size = 0; size <= N; size++) // smallest groups first
    for (unsigned extra = 0; extra <= ALL; extra++) {
      const unsigned group = core | extra;
      // Groups of the middle only, never a superset of a key.
      bool fresh = (extra & ~middle) == 0 && ones(extra) == size;
      for (int j = 0; j < nkeys && fresh; j++)
        fresh = keys[j] & ~group;
      if (!fresh)
        continue;
      tested++;
      if (closure(group) == ALL) {
        keys[nkeys++] = group;
        printf("key: {%s}\n", names(group, text));
      }
    }
  printf("closures: %d of %d subsets\n", tested, ALL + 1);
  return 0;
}

PHP 8.5 · main.php

<?php

declare(strict_types=1);

// Sets of attributes are bit masks.
const R = ['term', 'course', 'section', 'instructor', 'room', 'slot', 'building'];
const F = [
    ['term course section', 'instructor room slot'],
    ['term room slot', 'course section'],
    ['term instructor slot', 'room'],
    ['room', 'building'],
];
const ALL = (1 << 7) - 1;

function mask(string $names): int
{
    $bit = fn(string $name): int => 1 << array_search($name, R, true);
    return array_sum(array_map($bit, explode(' ', $names)));
}

function names(int $x): string
{
    $in = fn(int $i): bool => ($x >> $i & 1) === 1;
    return implode(', ', array_filter(R, $in, ARRAY_FILTER_USE_KEY));
}

function closure(int $x): int
{
    do {
        $grew = false;
        foreach (F as [$lhs, $rhs]) {
            if ((mask($lhs) & ~$x) === 0 && (mask($rhs) & ~$x) !== 0) {
                $x |= mask($rhs);
                $grew = true;
            }
        }
    } while ($grew);
    return $x;
}

[$left, $right] = [0, 0];
foreach (F as [$lhs, $rhs]) {
    [$left, $right] = [$left | mask($lhs), $right | mask($rhs)];
}
[$core, $middle] = [ALL & ~$right, $left & $right];
$order = range(0, ALL);
$size = fn(int $x): int => substr_count(decbin($x), '1');
usort($order, fn(int $a, int $b): int => [$size($a), $a] <=> [$size($b), $b]);
[$keys, $tested] = [[], 0];
foreach ($order as $extra) { // smallest groups first
    $group = $core | $extra;
    // Groups of the middle only, never a superset of a key.
    $fresh = array_filter($keys, fn(int $key): bool => ($key & ~$group) === 0) === [];
    if (($extra & ~$middle) === 0 && $fresh) {
        $tested++;
        if (closure($group) === ALL) {
            $keys[] = $group;
            echo 'key: {' . names($group) . "}\n";
        }
    }
}
echo "closures: {$tested} of " . (ALL + 1) . " subsets\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 R: [&str; 7] = [
    "term",
    "course",
    "section",
    "instructor",
    "room",
    "slot",
    "building",
];
const F: [(&str, &str); 4] = [
    ("term course section", "instructor room slot"),
    ("term room slot", "course section"),
    ("term instructor slot", "room"),
    ("room", "building"),
];
const ALL: u32 = (1 << R.len()) - 1;

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 names(x: u32) -> String {
    let picked: Vec<&str> = (0..R.len())
        .filter(|i| x >> i & 1 == 1)
        .map(|i| R[i])
        .collect();
    picked.join(", ")
}

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

fn main() {
    let (left, right) = F
        .iter()
        .fold((0, 0), |(l, r), (lhs, rhs)| (l | mask(lhs), r | mask(rhs)));
    let (core, middle) = (ALL & !right, left & right);
    let mut order: Vec<u32> = (0..=ALL).collect();
    order.sort_by_key(|x| (x.count_ones(), *x)); // smallest groups first
    let (mut keys, mut tested) = (Vec::new(), 0);
    for extra in order {
        let group = core | extra;
        // Groups of the middle only, never a superset of a key.
        if extra & !middle == 0 && keys.iter().all(|key| key & !group != 0) {
            tested += 1;
            if closure(group) == ALL {
                keys.push(group);
                println!("key: {{{}}}", names(group));
            }
        }
    }
    println!("closures: {tested} of {} subsets", ALL + 1);
}

TypeScript 6.0 · main.ts

// Sets of attributes are bit masks.
const R = ["term", "course", "section", "instructor", "room", "slot", "building"];
const F: [string, string][] = [
  ["term course section", "instructor room slot"],
  ["term room slot", "course section"],
  ["term instructor slot", "room"],
  ["room", "building"],
];
const ALL = (1 << R.length) - 1;

const mask = (names: string): number =>
  names.split(" ").reduce((x, name) => x | (1 << R.indexOf(name)), 0);
const names = (x: number): string => R.filter((_, i) => (x >> i) & 1).join(", ");
const count = (x: number): number => R.filter((_, i) => (x >> i) & 1).length;

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

let [left, right] = [0, 0];
for (const [lhs, rhs] of F) [left, right] = [left | mask(lhs), right | mask(rhs)];
const [core, middle] = [ALL & ~right, left & right];
const keys: number[] = [];
let tested = 0;
// Smallest groups first.
for (const extra of [...Array(ALL + 1).keys()].sort((a, b) => count(a) - count(b) || a - b)) {
  const group = core | extra;
  // Groups of the middle only, never a superset of a key.
  if ((extra & ~middle) === 0 && keys.every((key) => key & ~group)) {
    tested++;
    if (closure(group) === ALL) {
      keys.push(group);
      console.log(`key: {${names(group)}}`);
    }
  }
}
console.log(`closures: ${tested} of ${ALL + 1} subsets`);

Go 1.27 · main.go

package main

import (
	"fmt"
	"math/bits"
	"slices"
	"strings"
)

// Sets of attributes are bit masks.
var r = []string{"term", "course", "section", "instructor", "room", "slot", "building"}

var f = [][2]string{
	{"term course section", "instructor room slot"},
	{"term room slot", "course section"},
	{"term instructor slot", "room"},
	{"room", "building"},
}

const all = 1<<7 - 1

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

func names(x uint) string {
	var picked []string
	for i, name := range r {
		if x>>i&1 == 1 {
			picked = append(picked, name)
		}
	}
	return strings.Join(picked, ", ")
}

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

func main() {
	var left, right uint
	for _, fd := range f {
		left, right = left|mask(fd[0]), right|mask(fd[1])
	}
	core, middle := all&^right, left&right
	order := make([]uint, all+1)
	for x := range order {
		order[x] = uint(x)
	}
	// Smallest groups first.
	bySize := func(a, b uint) int { return bits.OnesCount(a) - bits.OnesCount(b) }
	slices.SortStableFunc(order, bySize)
	var keys []uint
	tested := 0
	for _, extra := range order {
		group := core | extra
		// Groups of the middle only, never a superset of a key.
		inside := func(key uint) bool { return key&^group == 0 }
		if extra&^middle == 0 && !slices.ContainsFunc(keys, inside) {
			tested++
			if closure(group) == all {
				keys = append(keys, group)
				fmt.Printf("key: {%s}\n", names(group))
			}
		}
	}
	fmt.Printf("closures: %d of %d subsets\n", tested, all+1)
}

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 r = ["term", "course", "section", "instructor", "room", "slot", "building"]
let f = [
  ("term course section", "instructor room slot"),
  ("term room slot", "course section"),
  ("term instructor slot", "room"),
  ("room", "building"),
]
let all = (1 << r.count) - 1

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

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

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

let (left, right) = f.reduce((0, 0)) { ($0.0 | mask($1.0), $0.1 | mask($1.1)) }
let (core, middle) = (all & ~right, left & right)
// Smallest groups first.
let order = (0...all).sorted { ($0.nonzeroBitCount, $0) < ($1.nonzeroBitCount, $1) }
var (keys, tested) = ([Int](), 0)
for extra in order {
  let group = core | extra
  // Groups of the middle only, never a superset of a key.
  if extra & ~middle == 0 && keys.allSatisfy({ $0 & ~group != 0 }) {
    tested += 1
    if closure(group) == all {
      keys.append(group)
      print("key: {\(names(group))}")
    }
  }
}
print("closures: \(tested) of \(all + 1) subsets")

Ruby 4.0 · main.rb

# frozen_string_literal: true

# Sets of attributes are bit masks.
R = %w[term course section instructor room slot building].freeze
F = [
  ['term course section', 'instructor room slot'],
  ['term room slot', 'course section'],
  ['term instructor slot', 'room'],
  %w[room building]
].freeze
ALL = (1 << R.size) - 1

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

def names(set)
  R.select.with_index { |_, i| set[i] == 1 }.join(', ')
end

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

    set = grown
  end
end

left = F.reduce(0) { |x, (lhs, _)| x | mask(lhs) }
right = F.reduce(0) { |x, (_, rhs)| x | mask(rhs) }
core = ALL & ~right
middle = left & right
keys = []
tested = 0
# Smallest groups first.
(0..ALL).sort_by { |x| [x.digits(2).sum, x] }.each do |extra|
  group = core | extra
  # Groups of the middle only, never a superset of a key.
  next unless (extra & ~middle).zero? && keys.all? { |key| (key & ~group).positive? }

  tested += 1
  next unless closure(group) == ALL

  keys << group
  puts "key: {#{names(group)}}"
end
puts "closures: #{tested} of #{ALL + 1} subsets"

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.
val r = listOf("term", "course", "section", "instructor", "room", "slot", "building")
val f =
    listOf(
        "term course section" to "instructor room slot",
        "term room slot" to "course section",
        "term instructor slot" to "room",
        "room" to "building",
    )
val all = (1 shl r.size) - 1

fun mask(names: String) = names.split(" ").fold(0) { x, name -> x or (1 shl r.indexOf(name)) }

fun names(x: Int) = r.filterIndexed { i, _ -> x shr i and 1 == 1 }.joinToString(", ")

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

fun main() {
    val left = f.fold(0) { x, (lhs, _) -> x or mask(lhs) }
    val right = f.fold(0) { x, (_, rhs) -> x or mask(rhs) }
    val core = all and right.inv()
    val middle = left and right
    val keys = mutableListOf<Int>()
    var tested = 0
    // Smallest groups first.
    for (extra in (0..all).sortedBy { it.countOneBits() }) {
        val group = core or extra
        // Groups of the middle only, never a superset of a key.
        if (extra and middle.inv() == 0 && keys.all { it and group.inv() != 0 }) {
            tested++
            if (closure(group) == all) {
                keys += group
                println("key: {${names(group)}}")
            }
        }
    }
    println("closures: $tested of ${all + 1} subsets")
}

Dart 3.13 · main.dart

// Sets of attributes are bit masks.
const r = [
  'term',
  'course',
  'section',
  'instructor',
  'room',
  'slot',
  'building',
];
const f = [
  ('term course section', 'instructor room slot'),
  ('term room slot', 'course section'),
  ('term instructor slot', 'room'),
  ('room', 'building'),
];
const all = (1 << 7) - 1;

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

String names(int x) => [
  for (var i = 0; i < r.length; i++)
    if (x >> i & 1 == 1) r[i],
].join(', ');

int ones(int x) => x.toRadixString(2).replaceAll('0', '').length;

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

void main() {
  final left = f.fold(0, (x, fd) => x | mask(fd.$1));
  final right = f.fold(0, (x, fd) => x | mask(fd.$2));
  final (core, middle) = (all & ~right, left & right);
  // Smallest groups first.
  final order = [for (var x = 0; x <= all; x++) x]
    ..sort((a, b) => ones(a) != ones(b) ? ones(a) - ones(b) : a - b);
  final keys = <int>[];
  var tested = 0;
  for (final extra in order) {
    final group = core | extra;
    // Groups of the middle only, never a superset of a key.
    if (extra & ~middle == 0 && keys.every((key) => key & ~group != 0)) {
      tested++;
      if (closure(group) == all) {
        keys.add(group);
        print('key: {${names(group)}}');
      }
    }
  }
  print('closures: $tested of ${all + 1} subsets');
}

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

key: {term, course, section}
key: {term, instructor, slot}
key: {term, room, slot}
closures: 18 of 128 subsets

The timetable has three candidate keys, all built on term, and the search computed 18 closures instead of 128. An attribute that belongs to at least one candidate key is prime attribute: An attribute that belongs to at least one candidate key of the relation. An attribute in no candidate key is non-prime. More in “First, second and third normal forms”; the others are non-prime. Here only building is non-prime. The prime attributes decide the second and third normal forms in the next module, so missing a key gives a wrong answer there, not just an incomplete list.

Key idea

The core is in every key and the excluded attributes are in none, so the search only tries the middle attributes, smallest groups first, and never tests a superset of a key it has found.

Checkpoint

Check: Finding every candidate key

Question 1 of 2 R(P, Q, S, T) has P -> Q, Q -> P and S -> T. Which are its candidate keys?
Choose one answer.

PS and QS PS only PQS S alone

Show the answer: Question 1 of 2

Answer: PS and QS

The core is S, the excluded attribute is T, and the middle is P and Q. Groups of one from the middle complete the core twice, so the keys are PS and QS.
Question 2 of 2 The search has found the key {term, course, section}. Why does it never compute the closure of {term, course, section, room}?
Choose one answer.

Its closure is smaller than the key's Groups of three or more are never tested The group contains a key, so it cannot be minimal room is one of the excluded attributes

Show the answer: Question 2 of 2

Answer: The group contains a key, so it cannot be minimal

Skipping supersets of found keys is what cut the search to 18 closures. The search tries groups in growing size, so every key inside a group has been found before the group comes up.

Practise: closures and keys

The exercise asks for the closure function and the two key tests, and its sample tests run in your browser on three dependency sets, one with a cycle:

Exercise · Medium · Python

Compute a closure, then test superkeys and candidate keys

Write three functions in keys.py. Attributes are single letters, a set of attributes is a string such as "AB", and a dependency is a pair of strings, so ("AB", "C") means AB -> C.

closure(attrs, fds) returns the set of every attribute that attrs determines under fds, attrs included.
is_superkey(attrs, schema, fds) returns True when attrs determines every attribute of schema.
is_candidate_key(attrs, schema, fds) returns True when attrs is a superkey and leaving out any one of its attributes gives a set that is not a superkey.

The sample tests use three dependency sets, among them one where two attributes determine each other, so that a key can use either of them.

Starter code · keys.py

"""Attribute closure and key tests.

Attributes are single letters, a set of attributes is a string such as "AB", and a
dependency is a pair of strings: ("AB", "C") means AB -> C.
"""


def closure(attrs, fds):
    """The set of attributes that attrs determines under fds."""
    # Replace this line with your code.
    return set(attrs)


def is_superkey(attrs, schema, fds):
    """True when attrs determines every attribute of schema."""
    # Replace this line with your code.
    return False


def is_candidate_key(attrs, schema, fds):
    """True when attrs is a superkey and no attribute can be left out of it."""
    # Replace this line with your code.
    return False

The sample tests · test_keys.py

from keys import closure, is_candidate_key, is_superkey

CHAIN = [("A", "B"), ("B", "C"), ("CD", "E")]                 # over ABCDE
CYCLE = [("AB", "C"), ("C", "A"), ("BD", "E")]                # over ABCDE
PAIRS = [("A", "B"), ("B", "A"), ("C", "D"), ("D", "C")]     # over ABCD


def test_closure_follows_chains():
    """closure keeps adding right-hand sides until nothing changes, whatever the order of the dependencies"""
    assert closure("A", CHAIN) == {"A", "B", "C"}
    assert closure("AD", CHAIN) == {"A", "B", "C", "D", "E"}
    assert closure("AD", CHAIN[::-1]) == {"A", "B", "C", "D", "E"}
    assert closure("E", CHAIN) == {"E"}


def test_closure_needs_the_whole_left_side():
    """a dependency fires only when all of its left-hand side is in the closure"""
    assert closure("C", CHAIN) == {"C"}
    assert closure("BD", CYCLE) == {"B", "D", "E"}
    assert closure("CBD", CYCLE) == {"A", "B", "C", "D", "E"}


def test_superkeys():
    """a superkey determines every attribute; extra attributes do not stop that"""
    assert is_superkey("AD", "ABCDE", CHAIN) is True
    assert is_superkey("ABD", "ABCDE", CHAIN) is True
    assert is_superkey("A", "ABCDE", CHAIN) is False
    assert is_superkey("BCD", "ABCDE", CYCLE) is True


def test_candidate_keys_are_minimal():
    """a candidate key is a superkey with no attribute to spare"""
    assert is_candidate_key("AD", "ABCDE", CHAIN) is True
    assert is_candidate_key("ABD", "ABCDE", CHAIN) is False
    assert is_candidate_key("ABD", "ABCDE", CYCLE) is True
    assert is_candidate_key("BCD", "ABCDE", CYCLE) is True
    assert is_candidate_key("BD", "ABCDE", CYCLE) is False


def test_keys_through_a_cycle():
    """when A and B determine each other, either one can stand in a key"""
    assert is_candidate_key("AC", "ABCD", PAIRS) is True
    assert is_candidate_key("BD", "ABCD", PAIRS) is True
    assert is_candidate_key("ABC", "ABCD", PAIRS) is False

A hint

Start closure with the set of attrs and loop: for each dependency whose left-hand side is already inside the set, add its right-hand side. Stop after a pass that adds nothing. The two key tests can then be written with closure alone: a superkey's closure contains the whole schema, and a candidate key stops being a superkey when any single attribute is removed.

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 closures, their three uses and the key search; the practice opens on whichever you know least.

Every candidate key, found and counted, with the traps reproduced Pro: opens with a Pro, Premium or Ultimate pass

A method that finds one key is easy to write; one that finds every key and proves there are no others is what exams and normal-form tests need. This part proves the search correct, reproduces the mistake of stopping at the first key, and counts superkeys from the keys.

In this part:

Why the search finds every key and nothing else: the proof
Stopping at the first key: a failure reproduced
Counting superkeys from the keys, with numbers

2 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).

The key search measured against brute force, and when keys explode Pro: opens with a Pro, Premium or Ultimate pass

Shortcuts are worth trusting only once they have been checked. This part runs the key search and a brute force side by side on 500 random dependency sets, counts the work each one does, and shows relations whose number of keys grows exponentially.

In this part:

500 random dependency sets: the same keys, measured work
When keys explode: 2 to the power n keys from n pairs
A closure in linear time, counted

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

Interview questions

Fresher · Warm-up

What is the closure X+ of a set of attributes, and how does it tell you whether X is a superkey?

X+ is the set of every attribute that X determines under the given dependencies, X itself included. To compute it, start with X and keep adding the right-hand side of any dependency whose left-hand side is already inside the set, until a whole pass adds nothing. X is a superkey of R exactly when X+ contains every attribute of R. It is a candidate key when, in addition, leaving out any one of its attributes gives a set whose closure no longer covers R. The same closure tests implication too: X -> Y follows from the dependencies exactly when Y lies inside X+.
Fresher to mid

R(A, B, C, D, E, F) has the dependencies AB -> C, C -> D, D -> A and BE -> F. Find every candidate key and the prime attributes, and say how many superkeys R has. Explain your method so that an interviewer can follow it.

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

In accounts(customer, account_manager, product_line), a customer has one account manager for each product line, and a manager looks after a single product line. A colleague takes (customer, account_manager) as the key and concludes that the table is not in 3NF. Is the conclusion right? Show your working.

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

Why can a relation have exponentially many candidate keys? Give a family of examples, and say what that means for a tool that lists keys or checks normal forms automatically.

Model answer, Pro. First step and follow-ups

Key takeaways

X+ grows pass after pass until a pass adds nothing: {term, instructor, slot} reached all 7 attributes in two passes, and a third that added nothing ended the loop.
One closure tells whether X is a superkey and whether X -> Y follows from F.
Every key holds the attributes on no right-hand side and none of those only on right-hand sides; the rest are tried in growing groups, 18 closures for the timetable’s three keys.
Prime attributes belong to some candidate key, so every key must be found before a normal form is tested.

Terms in this lesson

attribute closure: X+, the set of all attributes that the attributes X determine through the functional dependencies, X itself included.

References

C. Beeri and P. A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas (ACM Transactions on Database Systems)
P. A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies (ACM Transactions on Database Systems)
C. L. Lucchesi and S. L. Osborn: Candidate Keys for Relations (Journal of Computer and System Sciences)
PostgreSQL 18 Documentation: Constraints (unique constraints and primary keys) (The PostgreSQL Global Development Group)
GATE 2027 syllabus for Computer Science and Information Technology (CS) (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

Attribute closure and finding candidate keys

What you will learn

Before you start

What you will learn

Before you start

A closure grows until a pass adds nothing

One closure answers three questions

Every candidate key grows from the attributes no rule produces

Practise: closures and keys

Compute a closure, then test superkeys and candidate keys

Results of the sample tests

Every candidate key, found and counted, with the traps reproduced Pro: opens with a Pro, Premium or Ultimate pass

The key search measured against brute force, and when keys explode Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What is the closure X+ of a set of attributes, and how does it tell you whether X is a superkey?

R(A, B, C, D, E, F) has the dependencies AB -> C, C -> D, D -> A and BE -> F. Find every candidate key and the prime attributes, and say how many superkeys R has. Explain your method so that an interviewer can follow it.

Why can a relation have exponentially many candidate keys? Give a family of examples, and say what that means for a tool that lists keys or checks normal forms automatically.

Key takeaways

References

Related tools