Database Management Systems (DBMS) Module 7 – Normal forms and decomposition
First, second and third normal forms
Test a relation for 1NF, 2NF and 3NF against every candidate key, spot partial and transitive dependencies, and find its highest normal form step by step.
What you will learn
- Test a relation for 1NF and explain what a list in one column hides from keys and constraints
- Identify prime attributes and partial and transitive dependencies against every candidate key
- Split a relation into 2NF and then 3NF tables keyed by the left sides of their dependencies
- Find every candidate key before testing, and show how a missed key changes the verdict
- Find the highest normal form of a relation with a reliable procedure
Before you start
What you’ll learn · Before you start
What you will learn
- Test a relation for 1NF and explain what a list in one column hides from keys and constraints
- Identify prime attributes and partial and transitive dependencies against every candidate key
- Split a relation into 2NF and then 3NF tables keyed by the left sides of their dependencies
- Find every candidate key before testing, and show how a missed key changes the verdict
- Find the highest normal form of a relation with a reliable procedure
Before you start
On this page
The enrolment sheet of this module stores Iyer’s office in five rows and each student’s name once per course, and the first, second and third normal forms are the three tests that find such repeats. 1NF asks for one atomic value in every cell, never a list. 2NF forbids a non-prime attribute that depends on part of a candidate key, the way a student’s name depends on the roll number alone in a table keyed by roll number and course. 3NF asks that, for every non-trivial dependency X -> A, X be a superkey or A be prime, which means part of some candidate key.
Each form implies the ones before it, and all three tests are only as good as the list of candidate keys behind them. This lesson takes the sheet to 3NF, catches a seating plan that a check against its primary key misjudges, and ends with a procedure that finds the highest normal form of any relation, run in 14 languages.
A list in one cell hides its values from the database
A relation is in first normal form (1NF): Every cell of the relation holds a single atomic value from its domain, never a list, a set or a nested table. when every attribute holds atomic values: each cell has one value from its domain, never a list, a set or a table. Codd’s paper that introduced the relational model calls this the normal form. It turns relations whose domains are “nonsimple”, with values that are relations themselves, into flat relations, a step it names normalization (A Relational Model of Data for Large Shared Data Banks). Every later normal form assumes 1NF, because the dependencies it tests compare whole values.
A list in a column is the usual way 1NF breaks in practice. Here a college keeps each student’s courses as one comma-separated string, then stores the same facts with one value in each cell:
-- The courses of each student kept as a list in one column.
CREATE TABLE registrations (roll_no INTEGER PRIMARY KEY, student TEXT, courses TEXT);
INSERT INTO registrations VALUES
(101, 'Aarav', 'CS301,CS302'),
(102, 'Diya', 'CS303,CS301L'),
(103, 'Kabir', 'CS302,CS301'),
(104, 'Meera', 'CS304,CS3O1');
-- Who takes CS301? The pattern also matches the lab course CS301L,
-- and it misses Meera, whose entry was typed with a letter O.
SELECT roll_no, student FROM registrations WHERE courses LIKE '%CS301%';
-- The same facts with one value per cell: a row per student and course.
CREATE TABLE courses (course TEXT PRIMARY KEY, title TEXT);
INSERT INTO courses VALUES ('CS301', 'Databases'), ('CS301L', 'Databases lab'),
('CS302', 'Systems'), ('CS303', 'Networks'), ('CS304', 'Compilers');
PRAGMA foreign_keys = ON;
CREATE TABLE enrolments (
roll_no INTEGER REFERENCES registrations,
course TEXT REFERENCES courses,
PRIMARY KEY (roll_no, course));
INSERT INTO enrolments VALUES (101, 'CS301'), (101, 'CS302'), (102, 'CS303'),
(102, 'CS301L'), (103, 'CS302'), (103, 'CS301'), (104, 'CS304');
INSERT INTO enrolments VALUES (104, 'CS3O1');
SELECT roll_no FROM enrolments WHERE course = 'CS301';
SELECT course, count(*) AS students FROM enrolments GROUP BY course ORDER BY course;Output (exit status 1)
┌─────────┬─────────┐ │ roll_no │ student │ ├─────────┼─────────┤ │ 101 │ Aarav │ │ 102 │ Diya │ │ 103 │ Kabir │ └─────────┴─────────┘ ┌─────────┐ │ roll_no │ ├─────────┤ │ 101 │ │ 103 │ └─────────┘ ┌────────┬──────────┐ │ course │ students │ ├────────┼──────────┤ │ CS301 │ 2 │ │ CS301L │ 1 │ │ CS302 │ 2 │ │ CS303 │ 1 │ │ CS304 │ 1 │ └────────┴──────────┘
Printed as an error (standard error)
Runtime error near line 24: FOREIGN KEY constraint failed
Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < lists_in_a_cell.sql
Runs on this device, in your browser. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs.
Your run, in this browser
The pattern search for CS301 returns Diya, who takes only the lab course CS301L, and misses Meera, whose list was typed with the letter O. Neither mistake raises an error: the database sees one string per student and cannot check what is inside it. With one course per row, the same questions become ordinary SQL, and the foreign key refuses CS3O1 as soon as someone types it, which is the error at the end of the output:
| Question | Courses as a list in one cell | One course per row |
|---|---|---|
| Who takes CS301? | LIKE '%CS301%' also finds CS301L and misses CS3O1 |
course = 'CS301' finds exactly 101 and 103 |
| How many students per course? | Every string has to be split first | GROUP BY course |
| A mistyped course code | Stored without a word | Refused by the foreign key |
SQLite checks foreign keys only after PRAGMA foreign_keys = ON
(SQLite: foreign keys), which is why the example turns them on. Engines can
store lists all the same. SQLite reads a JSON array as rows with json_each
(SQLite: JSON functions), and PostgreSQL has array columns, whose manual points out
that arrays are not sets and suggests a separate table with a row per element when you search for elements
(PostgreSQL 18: arrays). Neither feature changes the design
question, because a key, a foreign key or a unique constraint cannot reach inside a list. Atomic is relative to use: a
date or a phone number is one value as long as nothing queries its parts.
Each dependency is fine, partial or transitive
2NF and 3NF are stated with three terms, each defined against the candidate keys:
- an attribute is a prime attribute: An attribute that belongs to at least one candidate key of the relation. An attribute in no candidate key is non-prime. when it belongs to at least one candidate key, and non-prime otherwise;
- a partial dependency: A dependency X -> A in which A is non-prime and X is a proper part of a candidate key. It breaks second normal form. is X -> A where A is non-prime and X is a proper part of some candidate key;
- a transitive dependency: A dependency X -> A in which A is non-prime and X is neither a superkey nor part of a candidate key, so A depends on a key only through X. is X -> A where A is non-prime and X is neither a superkey nor contained in a candidate key: a key determines X, and X determines A, so A depends on the key only through X.
Three questions, asked in order, put each dependency into one of these boxes. Step through three dependencies of the enrolment sheet:
The drawing shows the whole scene; its 4 steps are listed below.
Every step as text
- The sheet's key. The sheet has one candidate key, (roll_no, course), so roll_no and course are its only prime attributes. Every other attribute is non-prime.
- roll_no -> student. roll_no alone reaches only roll_no and student, so it is not a superkey. student is non-prime. roll_no is half of the key, so the dependency is partial.
- instructor -> office. instructor determines only office, and office is non-prime. instructor is part of no candidate key, so the office depends on the key only through it. Transitive.
- roll_no course -> grade. The left side is the key itself, so the first question already says yes. The grade is the one fact about the whole key.
The program finds the sheet’s candidate keys and labels every dependency, one attribute on the right at a time:
"""The enrolment sheet's dependencies, each classified against its candidate keys."""
from itertools import combinations
SHEET = ["roll_no", "student", "course", "title", "instructor", "office", "grade"]
FDS = [
({"roll_no"}, {"student"}),
({"course"}, {"title", "instructor"}),
({"instructor"}, {"office"}),
({"roll_no", "course"}, {"grade"}),
]
def closure(attrs, fds):
"""Every attribute that attrs determine: keep firing dependencies until nothing is added."""
result = set(attrs)
grew = True
while grew:
grew = False
for lhs, rhs in fds:
if lhs <= result and not rhs <= result:
result |= rhs
grew = True
return result
def candidate_keys(relation, fds):
"""The minimal sets of attributes whose closure is the whole relation (smallest first)."""
keys = []
for size in range(1, len(relation) + 1):
for combo in combinations(relation, size):
if not any(k <= set(combo) for k in keys) and closure(combo, fds) >= set(relation):
keys.append(set(combo))
return keys
def show(attrs):
return ", ".join(a for a in SHEET if a in attrs)
keys = candidate_keys(SHEET, FDS)
prime = set().union(*keys)
print("candidate keys:", " | ".join("{" + show(k) + "}" for k in keys))
print("prime:", show(prime), " non-prime:", show(set(SHEET) - prime))
print()
for lhs, rhs in FDS:
for a in sorted(rhs - lhs, key=SHEET.index):
if closure(lhs, FDS) >= set(SHEET):
kind = "fine: the left side is a superkey"
elif a in prime:
kind = "fine for 3NF: the right side is prime"
elif any(lhs < k for k in keys):
kind = "PARTIAL: depends on part of a key, breaks 2NF"
else:
kind = "TRANSITIVE: depends on a non-key, breaks 3NF"
print(f"{show(lhs):>15} -> {a:<10} {kind}")Output
candidate keys: {roll_no, course}
prime: roll_no, course non-prime: student, title, instructor, office, grade
roll_no -> student PARTIAL: depends on part of a key, breaks 2NF
course -> title PARTIAL: depends on part of a key, breaks 2NF
course -> instructor PARTIAL: depends on part of a key, breaks 2NF
instructor -> office TRANSITIVE: depends on a non-key, breaks 3NF
roll_no, course -> grade fine: the left side is a superkey
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 sheet_dependencies.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The only candidate key is (roll_no, course), so only those two attributes are prime. Three dependencies are partial:
a student’s name depends on the roll number alone, and a course’s title and instructor on the course alone.
instructor -> office is transitive: the key determines the course, the course determines the instructor, and the
instructor, who is not a key of the sheet, determines the office. Only the grade is a fact about the whole key.
Checkpoint
Check: First normal form and lists in a cell · Prime attributes, partial and transitive dependencies
Second normal form moves facts about part of a key
A relation is in second normal form (2NF): First normal form with no partial dependency, so every non-prime attribute depends on whole candidate keys. when it is in 1NF and has no partial dependency: every non-prime attribute depends on whole candidate keys, never on a part of one. 2NF can only fail when some candidate key has two or more attributes, because a key of one attribute has no smaller part that could determine anything.
The fix moves each fact about part of a key into a table keyed by that part. Step through the split of the sheet:
The drawing shows the whole scene; its 4 steps are listed below.
Every step as text
- Two partial dependencies. In the sheet, roll_no determines student and course determines title and instructor, and through the instructor the office. Both left sides are halves of the key.
- Students. The fact about roll_no alone moves to students, keyed by roll_no. Each name is now stored once per student, not once per enrolment.
- Courses. Everything course determines moves to courses, keyed by course. The office comes along, because course determines it through the instructor.
- Enrolments. What is left is the key and the one fact about the whole key, the grade. Each new table is keyed by the left side of the facts it took, so the join is lossless.
The split gives three tables: students(roll_no, student), courses(course, title, instructor, office) and enrolments(roll_no, course, grade). Each new table is keyed by the left-hand side of the dependencies it took, so joining the tables on those keys returns the original rows and no others: the lossless split of the first lesson of the previous module.
Third normal form moves facts about a non-key
A relation is in third normal form (3NF): For every non-trivial functional dependency X -> A that holds in the relation, X is a superkey or A is a prime attribute. when, for every non-trivial dependency X -> A that holds in it, X is a superkey or A is prime. This one-line test is the form of the definition given by Carlo Zaniolo in A New Normal Form for the Design of Relational Database Schemata. It says the same as the older wording, “in 2NF, and no non-prime attribute depends transitively on a key”, without needing the word transitive.
The courses table of the 2NF split fails it: instructor is not a superkey of courses, and office is not prime. Splitting off offices(instructor, office) leaves four tables, each with one key that is the left-hand side of every dependency in it. The figure shows both steps, from the sheet to the four tables:
The enrolment sheet taken to 3NF in two steps
Text description of the diagram
The diagram shows the two steps that take the enrolment sheet from first to third normal form.
- The sheet has the key (roll_no, course) and the attributes student, title, instructor, office and grade. It is in 1NF only, because student depends on roll_no alone and title and instructor depend on course alone.
- The 2NF step moves each fact about part of the key into a table keyed by that part. It gives students (key roll_no, with student), enrolments (key roll_no and course, with grade) and courses (key course, with title, instructor and office). students and enrolments are in BCNF; courses is in 2NF.
- courses is not in 3NF, because instructor, which is not a key, determines office. The 3NF step moves that fact into offices (key instructor, with office) and leaves courses with title and instructor.
The result is four tables, each in BCNF: students, enrolments, courses and offices.
Each of the four tables is in 3NF, and also in the stricter Boyce-Codd normal form of the next lesson. The clause “or A is prime” is what separates 3NF from Boyce-Codd normal form, and it is deliberate: it lets every schema have a 3NF design that keeps each dependency checkable inside one table, which the stricter form cannot always do. The next lesson builds a relation where that difference decides the design.
Checkpoint
Check: Second normal form · Third normal form
A missed candidate key gives the wrong verdict
Each test above speaks of candidate keys, and the declared primary key is only one of them. Testing against the primary key alone is an easy way to misjudge a relation. Take the seating plan of an exam held in several sessions, seating(roll_no, session, seat, hall), with three rules:
- a candidate has one seat in a session:
roll_no session -> seat; - a seat holds one candidate in a session:
session seat -> roll_no; - a seat label such as H2-17 names its hall:
seat -> hall.
The exam office keys the table on (roll_no, session). But the closure of session and seat reaches every attribute too. Step through it:
The drawing shows the whole scene; its 5 steps are listed below.
Every step as text
- Start. The closure starts from the two attributes, session and seat. The declared key, roll_no with session, is not involved yet.
- Who sits there. A seat holds one candidate in a session, so session seat -> roll_no fires and adds roll_no.
- Which hall. The seat label names its hall, so seat -> hall fires and adds hall. The closure now holds all four attributes.
- A second key. Neither session nor seat alone reaches the rest, so (session, seat) is a candidate key, and seat is prime.
- The verdict moves. seat -> hall now has part of a key on its left and a non-prime attribute on its right. It is partial, so the seating plan is in 1NF, not 2NF.
The program judges the table twice, with the primary key alone and with every candidate key, in each of 14 languages:
Python 3.14 · main.py
# Sets of attributes are bit masks.
ROLL_NO, SESSION, SEAT, HALL = 1, 2, 4, 8
NAMES = ["roll_no", "session", "seat", "hall"]
ALL = ROLL_NO | SESSION | SEAT | HALL
FDS = [(ROLL_NO | SESSION, SEAT), (SESSION | SEAT, ROLL_NO), (SEAT, HALL)]
def closure(x: int) -> int:
grew = True
while grew:
grew = False
for lhs, rhs in FDS:
if lhs & x == lhs and rhs & ~x:
x |= rhs
grew = True
return x
def show(x: int) -> str:
return " ".join(name for i, name in enumerate(NAMES) if x >> i & 1)
def judge(keys: list[int]) -> None:
prime = 0
for key in keys:
prime |= key
print(" keys: " + ", ".join("{" + show(key) + "}" for key in keys))
for lhs, rhs in FDS:
if closure(lhs) == ALL:
verdict = "superkey, fine"
elif rhs & prime:
verdict = "prime, fine for 3NF"
elif any(lhs & key == lhs for key in keys):
verdict = "partial, breaks 2NF"
else:
verdict = "transitive, breaks 3NF"
print(f" {show(lhs)} -> {show(rhs)}: {verdict}")
# A key reaches ALL, and none of its attributes can be dropped.
bits = [1 << i for i in range(len(NAMES))]
keys = [
x
for x in range(1, ALL + 1)
if closure(x) == ALL and all(closure(x & ~bit) != ALL for bit in bits if x & bit)
]
print("with the primary key only")
judge([ROLL_NO | SESSION])
print("with every candidate key")
judge(keys)In Python: & binds tighter than == in Python, so lhs & x == lhs needs no parentheses. C, C++, Java, C#, JavaScript, TypeScript and PHP write the same test as (lhs & x) == lhs.
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 [ROLL_NO, SESSION, SEAT, HALL] = [1, 2, 4, 8];
const NAMES = ["roll_no", "session", "seat", "hall"];
const ALL = ROLL_NO | SESSION | SEAT | HALL;
const FDS = [
[ROLL_NO | SESSION, SEAT],
[SESSION | SEAT, ROLL_NO],
[SEAT, HALL],
];
function closure(x) {
let grew = true;
while (grew) {
grew = false;
for (const [lhs, rhs] of FDS) {
if ((lhs & x) === lhs && rhs & ~x) {
x |= rhs;
grew = true;
}
}
}
return x;
}
const show = (x) => NAMES.filter((_, i) => (x >> i) & 1).join(" ");
function judge(keys) {
const prime = keys.reduce((p, key) => p | key, 0);
console.log(" keys: " + keys.map((key) => `{${show(key)}}`).join(", "));
for (const [lhs, rhs] of FDS) {
let verdict;
if (closure(lhs) === ALL) verdict = "superkey, fine";
else if (rhs & prime) verdict = "prime, fine for 3NF";
else if (keys.some((key) => (lhs & key) === lhs)) verdict = "partial, breaks 2NF";
else verdict = "transitive, breaks 3NF";
console.log(` ${show(lhs)} -> ${show(rhs)}: ${verdict}`);
}
}
// A key reaches ALL, and none of its attributes can be dropped.
const keys = [];
for (let x = 1; x <= ALL; x++) {
let key = closure(x) === ALL;
for (let bit = 1; bit <= x; bit <<= 1) key &&= (x & bit) === 0 || closure(x & ~bit) !== ALL;
if (key) keys.push(x);
}
console.log("with the primary key only");
judge([ROLL_NO | SESSION]);
console.log("with every candidate key");
judge(keys);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.
static final int ROLL_NO = 1;
static final int SESSION = 2;
static final int SEAT = 4;
static final int HALL = 8;
static final String[] NAMES = {"roll_no", "session", "seat", "hall"};
static final int ALL = ROLL_NO | SESSION | SEAT | HALL;
static final int[][] FDS = {{ROLL_NO | SESSION, SEAT}, {SESSION | SEAT, ROLL_NO}, {SEAT, HALL}};
static int closure(int x) {
boolean grew = true;
while (grew) {
grew = false;
for (int[] fd : FDS) {
if ((fd[0] & x) == fd[0] && (fd[1] & ~x) != 0) {
x |= fd[1];
grew = true;
}
}
}
return x;
}
static String show(int x) {
List<String> out = new ArrayList<>();
for (int i = 0; i < NAMES.length; i++) {
if ((x >> i & 1) == 1) {
out.add(NAMES[i]);
}
}
return String.join(" ", out);
}
static void judge(List<Integer> keys) {
int prime = 0;
List<String> shown = new ArrayList<>();
for (int key : keys) {
prime |= key;
shown.add("{" + show(key) + "}");
}
System.out.println(" keys: " + String.join(", ", shown));
for (int[] fd : FDS) {
int lhs = fd[0];
int rhs = fd[1];
String verdict;
if (closure(lhs) == ALL) {
verdict = "superkey, fine";
} else if ((rhs & prime) != 0) {
verdict = "prime, fine for 3NF";
} else if (keys.stream().anyMatch(key -> (lhs & key) == lhs)) {
verdict = "partial, breaks 2NF";
} else {
verdict = "transitive, breaks 3NF";
}
System.out.println(" " + show(lhs) + " -> " + show(rhs) + ": " + verdict);
}
}
public static void main(String[] args) {
// A key reaches ALL, and none of its attributes can be dropped.
List<Integer> keys = new ArrayList<>();
for (int x = 1; x <= ALL; x++) {
boolean key = closure(x) == ALL;
for (int bit = 1; bit <= x; bit <<= 1) {
key = key && ((x & bit) == 0 || closure(x & ~bit) != ALL);
}
if (key) {
keys.add(x);
}
}
System.out.println("with the primary key only");
judge(List.of(ROLL_NO | SESSION));
System.out.println("with every candidate key");
judge(keys);
}
}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 <array>
#include <print>
#include <string>
#include <utility>
#include <vector>
// Sets of attributes are bit masks.
enum : unsigned { ROLL_NO = 1, SESSION = 2, SEAT = 4, HALL = 8 };
constexpr unsigned ALL = ROLL_NO | SESSION | SEAT | HALL;
constexpr std::array<const char *, 4> NAMES = {"roll_no", "session", "seat",
"hall"};
constexpr std::array<std::pair<unsigned, unsigned>, 3> FDS = {
{{ROLL_NO | SESSION, SEAT}, {SESSION | SEAT, ROLL_NO}, {SEAT, HALL}}};
unsigned closure(unsigned x) {
for (bool grew = true; grew;) {
grew = false;
for (const auto &[lhs, rhs] : FDS) {
if ((lhs & x) == lhs && (rhs & ~x) != 0) {
x |= rhs;
grew = true;
}
}
}
return x;
}
std::string show(unsigned x) {
std::string out;
for (std::size_t i = 0; i < NAMES.size(); i++) {
if (x >> i & 1) {
out += (out.empty() ? "" : " ") + std::string(NAMES[i]);
}
}
return out;
}
void judge(const std::vector<unsigned> &keys) {
unsigned prime = 0;
std::string line;
for (unsigned key : keys) {
prime |= key;
line += (line.empty() ? "{" : ", {") + show(key) + "}";
}
std::println(" keys: {}", line);
for (const auto &[lhs, rhs] : FDS) {
const bool partial = std::ranges::any_of(
keys, [lhs](unsigned key) { return (lhs & key) == lhs; });
const char *verdict = closure(lhs) == ALL ? "superkey, fine"
: (rhs & prime) != 0 ? "prime, fine for 3NF"
: partial ? "partial, breaks 2NF"
: "transitive, breaks 3NF";
std::println(" {} -> {}: {}", show(lhs), show(rhs), verdict);
}
}
int main() {
// A key reaches ALL, and none of its attributes can be dropped.
std::vector<unsigned> keys;
for (unsigned x = 1; x <= ALL; x++) {
bool key = closure(x) == ALL;
for (unsigned bit = 1; bit <= x; bit <<= 1) {
key = key && ((x & bit) == 0 || closure(x & ~bit) != ALL);
}
if (key) {
keys.push_back(x);
}
}
std::println("with the primary key only");
judge({ROLL_NO | SESSION});
std::println("with every candidate key");
judge(keys);
}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.
const int RollNo = 1;
const int Session = 2;
const int Seat = 4;
const int Hall = 8;
const int All = RollNo | Session | Seat | Hall;
string[] names = ["roll_no", "session", "seat", "hall"];
(int Lhs, int Rhs)[] fds = [(RollNo | Session, Seat), (Session | Seat, RollNo), (Seat, Hall)];
int Closure(int x)
{
for (bool grew = true; grew;)
{
grew = false;
foreach (var (lhs, rhs) in fds)
{
if ((lhs & x) == lhs && (rhs & ~x) != 0)
{
x |= rhs;
grew = true;
}
}
}
return x;
}
string Show(int x) => string.Join(" ", names.Where((_, i) => (x >> i & 1) == 1));
void Judge(List<int> keys)
{
int prime = keys.Aggregate(0, (p, key) => p | key);
Console.WriteLine(" keys: " + string.Join(", ", keys.Select(key => "{" + Show(key) + "}")));
foreach (var (lhs, rhs) in fds)
{
string verdict =
Closure(lhs) == All ? "superkey, fine"
: (rhs & prime) != 0 ? "prime, fine for 3NF"
: keys.Any(key => (lhs & key) == lhs) ? "partial, breaks 2NF"
: "transitive, breaks 3NF";
Console.WriteLine($" {Show(lhs)} -> {Show(rhs)}: {verdict}");
}
}
// A key reaches All, and none of its attributes can be dropped.
var keys = new List<int>();
for (int x = 1; x <= All; x++)
{
bool key = Closure(x) == All;
for (int bit = 1; bit <= x; bit <<= 1)
{
key = key && ((x & bit) == 0 || Closure(x & ~bit) != All);
}
if (key)
{
keys.Add(x);
}
}
Console.WriteLine("with the primary key only");
Judge([RollNo | Session]);
Console.WriteLine("with every candidate key");
Judge(keys);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 { ROLL_NO = 1, SESSION = 2, SEAT = 4, HALL = 8 };
enum { ALL = ROLL_NO | SESSION | SEAT | HALL };
static const char *const NAMES[] = {"roll_no", "session", "seat", "hall"};
static const unsigned FDS[][2] = {
{ROLL_NO | SESSION, SEAT}, {SESSION | SEAT, ROLL_NO}, {SEAT, HALL}};
static unsigned closure(unsigned x) {
for (int grew = 1; grew;) {
grew = 0;
for (int i = 0; i < 3; i++)
if ((FDS[i][0] & x) == FDS[i][0] && (FDS[i][1] & ~x)) {
x |= FDS[i][1];
grew = 1;
}
}
return x;
}
static char *show(unsigned x, char *out) {
out[0] = '\0';
for (int i = 0; i < 4; i++)
if (x >> i & 1)
strcat(strcat(out, out[0] ? " " : ""), NAMES[i]);
return out;
}
static void judge(const unsigned *keys, int count) {
char a[64], b[64];
unsigned prime = 0;
printf(" keys: ");
for (int k = 0; k < count; k++) {
prime |= keys[k];
printf("%s{%s}", k ? ", " : "", show(keys[k], a));
}
printf("\n");
for (int i = 0; i < 3; i++) {
unsigned lhs = FDS[i][0], rhs = FDS[i][1];
int partial = 0;
for (int k = 0; k < count; k++)
partial |= (lhs & keys[k]) == lhs;
const char *verdict = closure(lhs) == ALL ? "superkey, fine"
: rhs & prime ? "prime, fine for 3NF"
: partial ? "partial, breaks 2NF"
: "transitive, breaks 3NF";
printf(" %s -> %s: %s\n", show(lhs, a), show(rhs, b), verdict);
}
}
int main(void) {
// A key reaches ALL, and none of its attributes can be dropped.
unsigned keys[ALL];
int count = 0;
for (unsigned x = 1; x <= ALL; x++) {
int key = closure(x) == ALL;
for (unsigned bit = 1; bit <= x; bit <<= 1)
key = key && ((x & bit) == 0 || closure(x & ~bit) != ALL);
if (key)
keys[count++] = x;
}
printf("with the primary key only\n");
judge((const unsigned[]){ROLL_NO | SESSION}, 1);
printf("with every candidate key\n");
judge(keys, count);
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.
const ROLL_NO = 1;
const SESSION = 2;
const SEAT = 4;
const HALL = 8;
const ALL = ROLL_NO | SESSION | SEAT | HALL;
const NAMES = ['roll_no', 'session', 'seat', 'hall'];
const FDS = [[ROLL_NO | SESSION, SEAT], [SESSION | SEAT, ROLL_NO], [SEAT, HALL]];
function closure(int $x): int
{
do {
$grew = false;
foreach (FDS as [$lhs, $rhs]) {
if (($lhs & $x) === $lhs && ($rhs & ~$x) !== 0) {
$x |= $rhs;
$grew = true;
}
}
} while ($grew);
return $x;
}
function show(int $x): string
{
$names = array_filter(NAMES, fn(int $i): bool => ($x >> $i & 1) === 1, ARRAY_FILTER_USE_KEY);
return implode(' ', $names);
}
/** @param list<int> $keys */
function judge(array $keys): void
{
$prime = array_reduce($keys, fn(int $p, int $key): int => $p | $key, 0);
$shown = array_map(fn(int $key): string => '{' . show($key) . '}', $keys);
echo ' keys: ' . implode(', ', $shown) . "\n";
foreach (FDS as [$lhs, $rhs]) {
$partial = array_filter($keys, fn(int $key): bool => ($lhs & $key) === $lhs) !== [];
$verdict = match (true) {
closure($lhs) === ALL => 'superkey, fine',
($rhs & $prime) !== 0 => 'prime, fine for 3NF',
$partial => 'partial, breaks 2NF',
default => 'transitive, breaks 3NF',
};
echo ' ' . show($lhs) . ' -> ' . show($rhs) . ": {$verdict}\n";
}
}
// A key reaches ALL, and none of its attributes can be dropped.
$keys = [];
for ($x = 1; $x <= ALL; $x++) {
$key = closure($x) === ALL;
for ($bit = 1; $bit <= $x; $bit <<= 1) {
$key = $key && (($x & $bit) === 0 || closure($x & ~$bit) !== ALL);
}
if ($key) {
$keys[] = $x;
}
}
echo "with the primary key only\n";
judge([ROLL_NO | SESSION]);
echo "with every candidate key\n";
judge($keys);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 ROLL_NO: u32 = 1;
const SESSION: u32 = 2;
const SEAT: u32 = 4;
const HALL: u32 = 8;
const ALL: u32 = ROLL_NO | SESSION | SEAT | HALL;
const NAMES: [&str; 4] = ["roll_no", "session", "seat", "hall"];
const FDS: [(u32, u32); 3] = [
(ROLL_NO | SESSION, SEAT),
(SESSION | SEAT, ROLL_NO),
(SEAT, HALL),
];
fn closure(mut x: u32) -> u32 {
let mut grew = true;
while grew {
grew = false;
for (lhs, rhs) in FDS {
if lhs & x == lhs && rhs & !x != 0 {
x |= rhs;
grew = true;
}
}
}
x
}
fn show(x: u32) -> String {
let names: Vec<&str> = (0..NAMES.len())
.filter(|i| x >> i & 1 == 1)
.map(|i| NAMES[i])
.collect();
names.join(" ")
}
fn judge(keys: &[u32]) {
let prime = keys.iter().fold(0, |p, key| p | key);
let shown: Vec<String> = keys
.iter()
.map(|&key| format!("{{{}}}", show(key)))
.collect();
println!(" keys: {}", shown.join(", "));
for (lhs, rhs) in FDS {
let verdict = if closure(lhs) == ALL {
"superkey, fine"
} else if rhs & prime != 0 {
"prime, fine for 3NF"
} else if keys.iter().any(|&key| lhs & key == lhs) {
"partial, breaks 2NF"
} else {
"transitive, breaks 3NF"
};
println!(" {} -> {}: {verdict}", show(lhs), show(rhs));
}
}
fn main() {
// A key reaches ALL, and none of its attributes can be dropped.
let keys: Vec<u32> = (1..=ALL)
.filter(|&x| closure(x) == ALL)
.filter(|&x| (0..NAMES.len()).all(|i| x >> i & 1 == 0 || closure(x & !(1 << i)) != ALL))
.collect();
println!("with the primary key only");
judge(&[ROLL_NO | SESSION]);
println!("with every candidate key");
judge(&keys);
}In Rust: Rust has no ~ operator: ! flips every bit of an integer, so x & !(1 << i) drops attribute i from the set.
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.
const [ROLL_NO, SESSION, SEAT, HALL] = [1, 2, 4, 8];
const NAMES = ["roll_no", "session", "seat", "hall"];
const ALL = ROLL_NO | SESSION | SEAT | HALL;
const FDS: [number, number][] = [
[ROLL_NO | SESSION, SEAT],
[SESSION | SEAT, ROLL_NO],
[SEAT, HALL],
];
function closure(x: number): number {
let grew = true;
while (grew) {
grew = false;
for (const [lhs, rhs] of FDS) {
if ((lhs & x) === lhs && (rhs & ~x) !== 0) {
x |= rhs;
grew = true;
}
}
}
return x;
}
const show = (x: number): string => NAMES.filter((_, i) => (x >> i) & 1).join(" ");
function judge(keys: number[]): void {
const prime = keys.reduce((p, key) => p | key, 0);
console.log(" keys: " + keys.map((key) => `{${show(key)}}`).join(", "));
for (const [lhs, rhs] of FDS) {
let verdict: string;
if (closure(lhs) === ALL) verdict = "superkey, fine";
else if ((rhs & prime) !== 0) verdict = "prime, fine for 3NF";
else if (keys.some((key) => (lhs & key) === lhs)) verdict = "partial, breaks 2NF";
else verdict = "transitive, breaks 3NF";
console.log(` ${show(lhs)} -> ${show(rhs)}: ${verdict}`);
}
}
// A key reaches ALL, and none of its attributes can be dropped.
const keys: number[] = [];
for (let x = 1; x <= ALL; x++) {
let key = closure(x) === ALL;
for (let bit = 1; bit <= x; bit <<= 1) key &&= (x & bit) === 0 || closure(x & ~bit) !== ALL;
if (key) keys.push(x);
}
console.log("with the primary key only");
judge([ROLL_NO | SESSION]);
console.log("with every candidate key");
judge(keys);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"
"strings"
)
// Sets of attributes are bit masks.
const RollNo, Session, Seat, Hall = 1, 2, 4, 8
const All = RollNo | Session | Seat | Hall
var names = []string{"roll_no", "session", "seat", "hall"}
var fds = [][2]int{{RollNo | Session, Seat}, {Session | Seat, RollNo}, {Seat, Hall}}
func closure(x int) int {
for grew := true; grew; {
grew = false
for _, fd := range fds {
if fd[0]&x == fd[0] && fd[1]&^x != 0 {
x |= fd[1]
grew = true
}
}
}
return x
}
func show(x int) string {
var out []string
for i, name := range names {
if x>>i&1 == 1 {
out = append(out, name)
}
}
return strings.Join(out, " ")
}
func judge(keys []int) {
prime, shown := 0, []string{}
for _, key := range keys {
prime |= key
shown = append(shown, "{"+show(key)+"}")
}
fmt.Println(" keys: " + strings.Join(shown, ", "))
for _, fd := range fds {
lhs, rhs := fd[0], fd[1]
partial := false
for _, key := range keys {
partial = partial || lhs&key == lhs
}
verdict := "transitive, breaks 3NF"
switch {
case closure(lhs) == All:
verdict = "superkey, fine"
case rhs&prime != 0:
verdict = "prime, fine for 3NF"
case partial:
verdict = "partial, breaks 2NF"
}
fmt.Printf(" %s -> %s: %s\n", show(lhs), show(rhs), verdict)
}
}
func main() {
// A key reaches All, and none of its attributes can be dropped.
var keys []int
for x := 1; x <= All; x++ {
key := closure(x) == All
for bit := 1; bit <= x; bit <<= 1 {
key = key && (x&bit == 0 || closure(x&^bit) != All)
}
if key {
keys = append(keys, x)
}
}
fmt.Println("with the primary key only")
judge([]int{RollNo | Session})
fmt.Println("with every candidate key")
judge(keys)
}In Go: x&^bit is Go's AND NOT, so closure(x&^bit) is the closure of x with one attribute dropped.
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 rollNo = 1
let session = 2
let seat = 4
let hall = 8
let all = rollNo | session | seat | hall
let names = ["roll_no", "session", "seat", "hall"]
let fds = [(rollNo | session, seat), (session | seat, rollNo), (seat, hall)]
func closure(_ start: Int) -> Int {
var x = start
var grew = true
while grew {
grew = false
for (lhs, rhs) in fds where lhs & x == lhs && rhs & ~x != 0 {
x |= rhs
grew = true
}
}
return x
}
func show(_ x: Int) -> String {
names.indices.filter { x >> $0 & 1 == 1 }.map { names[$0] }.joined(separator: " ")
}
func judge(_ keys: [Int]) {
let prime = keys.reduce(0, |)
print(" keys: " + keys.map { "{" + show($0) + "}" }.joined(separator: ", "))
for (lhs, rhs) in fds {
let verdict: String
if closure(lhs) == all {
verdict = "superkey, fine"
} else if rhs & prime != 0 {
verdict = "prime, fine for 3NF"
} else if keys.contains(where: { lhs & $0 == lhs }) {
verdict = "partial, breaks 2NF"
} else {
verdict = "transitive, breaks 3NF"
}
print(" \(show(lhs)) -> \(show(rhs)): \(verdict)")
}
}
// A key reaches all, and none of its attributes can be dropped.
let keys = (1...all).filter { x in
closure(x) == all
&& names.indices.allSatisfy { x >> $0 & 1 == 0 || closure(x & ~(1 << $0)) != all }
}
print("with the primary key only")
judge([rollNo | session])
print("with every candidate key")
judge(keys)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.
ROLL_NO = 1
SESSION = 2
SEAT = 4
HALL = 8
ALL = ROLL_NO | SESSION | SEAT | HALL
NAMES = %w[roll_no session seat hall].freeze
FDS = [[ROLL_NO | SESSION, SEAT], [SESSION | SEAT, ROLL_NO], [SEAT, HALL]].freeze
def closure(start)
x = start
loop do
grown = FDS.reduce(x) { |acc, (lhs, rhs)| lhs & acc == lhs ? acc | rhs : acc }
return x if grown == x
x = grown
end
end
def show(set)
NAMES.each_index.select { |i| set[i] == 1 }.map { |i| NAMES[i] }.join(' ')
end
def verdict(lhs, rhs, keys, prime)
return 'superkey, fine' if closure(lhs) == ALL
return 'prime, fine for 3NF' if rhs & prime != 0
return 'partial, breaks 2NF' if keys.any? { |key| lhs & key == lhs }
'transitive, breaks 3NF'
end
def judge(keys)
prime = keys.reduce(0, :|)
puts " keys: #{keys.map { |key| "{#{show(key)}}" }.join(', ')}"
FDS.each { |lhs, rhs| puts " #{show(lhs)} -> #{show(rhs)}: #{verdict(lhs, rhs, keys, prime)}" }
end
# A key reaches ALL, and none of its attributes can be dropped.
keys = (1..ALL).select do |x|
closure(x) == ALL && NAMES.each_index.all? { |i| x[i].zero? || closure(x & ~(1 << i)) != ALL }
end
puts 'with the primary key only'
judge([ROLL_NO | SESSION])
puts 'with every candidate key'
judge(keys)In Ruby: Integer#[] reads one bit, so x[i].zero? asks whether attribute i is missing from the set x.
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 ROLL_NO = 1
const val SESSION = 2
const val SEAT = 4
const val HALL = 8
const val ALL = ROLL_NO or SESSION or SEAT or HALL
val names = listOf("roll_no", "session", "seat", "hall")
val fds = listOf(ROLL_NO or SESSION to SEAT, SESSION or SEAT to ROLL_NO, SEAT to HALL)
fun closure(start: Int): Int {
var x = start
var grew = true
while (grew) {
grew = false
for ((lhs, rhs) in fds) {
if (lhs and x == lhs && rhs and x.inv() != 0) {
x = x or rhs
grew = true
}
}
}
return x
}
fun show(x: Int) = names.indices.filter { x shr it and 1 == 1 }.joinToString(" ") { names[it] }
fun judge(keys: List<Int>) {
val prime = keys.fold(0) { p, key -> p or key }
println(" keys: " + keys.joinToString(", ") { "{" + show(it) + "}" })
for ((lhs, rhs) in fds) {
val verdict =
when {
closure(lhs) == ALL -> "superkey, fine"
rhs and prime != 0 -> "prime, fine for 3NF"
keys.any { lhs and it == lhs } -> "partial, breaks 2NF"
else -> "transitive, breaks 3NF"
}
println(" ${show(lhs)} -> ${show(rhs)}: $verdict")
}
}
fun main() {
// A key reaches ALL, and none of its attributes can be dropped.
val keys =
(1..ALL).filter { x ->
closure(x) == ALL &&
names.indices.all { x shr it and 1 == 0 || closure(x and (1 shl it).inv()) != ALL }
}
println("with the primary key only")
judge(listOf(ROLL_NO or SESSION))
println("with every candidate key")
judge(keys)
}In Kotlin: and, or and shr are infix functions, which bind tighter than ==, so the mask tests need no parentheses; inv() is a plain call that flips every bit.
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.
const rollNo = 1, session = 2, seat = 4, hall = 8;
const all = rollNo | session | seat | hall;
const names = ['roll_no', 'session', 'seat', 'hall'];
const fds = [(rollNo | session, seat), (session | seat, rollNo), (seat, hall)];
int closure(int x) {
for (var grew = true; grew;) {
grew = false;
for (final (lhs, rhs) in fds) {
if (lhs & x == lhs && rhs & ~x != 0) {
x |= rhs;
grew = true;
}
}
}
return x;
}
String show(int x) => [
for (var i = 0; i < names.length; i++)
if (x >> i & 1 == 1) names[i],
].join(' ');
void judge(List<int> keys) {
final prime = keys.fold(0, (p, key) => p | key);
print(' keys: ${keys.map((key) => '{${show(key)}}').join(', ')}');
for (final (lhs, rhs) in fds) {
final verdict = closure(lhs) == all
? 'superkey, fine'
: rhs & prime != 0
? 'prime, fine for 3NF'
: keys.any((key) => lhs & key == lhs)
? 'partial, breaks 2NF'
: 'transitive, breaks 3NF';
print(' ${show(lhs)} -> ${show(rhs)}: $verdict');
}
}
void main() {
// A key reaches all, and none of its attributes can be dropped.
final bits = [for (var i = 0; i < names.length; i++) 1 << i];
final keys = [
for (var x = 1; x <= all; x++)
if (closure(x) == all &&
bits.every((bit) => x & bit == 0 || closure(x & ~bit) != all))
x,
];
print('with the primary key only');
judge([rollNo | session]);
print('with every candidate key');
judge(keys);
}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
with the primary key only
keys: {roll_no session}
roll_no session -> seat: superkey, fine
session seat -> roll_no: superkey, fine
seat -> hall: transitive, breaks 3NF
with every candidate key
keys: {roll_no session}, {session seat}
roll_no session -> seat: superkey, fine
session seat -> roll_no: superkey, fine
seat -> hall: partial, breaks 2NF
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. Runs on this device: a JavaScript build of this program (about 12 KB), made when the page was built. The first run also downloads the JavaScript runner (about 0.6 MB), which is kept for the next runs. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 152 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a .NET build of this program (about 3 KB), made when the page was built. The first run also downloads .NET (about 3.6 MB), which is kept for the next runs. Edit runs your changes in the browser: the first edited run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 9 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads PHP (about 4.3 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 21 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads the JavaScript runner (about 0.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 719 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 1.7 MB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads Ruby (about 10.2 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 183 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 11 KB), made when the page was built. To change the code, copy it and run it with the command below.Your run, in this browser
With the primary key alone, seat looks like a non-key, so seat -> hall passes for a transitive dependency and the
verdict is 2NF. But (session, seat) is a second candidate key, which makes seat part of a key. The hall, which belongs
to no key, then depends on part of a key: a partial dependency, so the relation is not even in 2NF. The data shows the
cost. The hall of a seat is stored again for every session in which the seat is used, the redundancy that 2NF exists
to remove, and seats(seat, hall) is the table where that fact belongs. What went wrong was the first step: find every
candidate key before running any test.
A second key can move a verdict up as well. When every attribute belongs to some key, as in R2 of the next section’s program, no dependency can break 3NF, whatever its left-hand side.
Key idea
Find every candidate key before any normal-form test: an attribute in a second key is prime, and that alone can turn a transitive dependency into a partial one.
Checkpoint
Check: Testing against every candidate key
The highest normal form in seven steps
The forms nest: BCNF implies 3NF, 3NF implies 2NF and 2NF implies 1NF. So one procedure finds the highest normal form of a relation:
- Check that every value is atomic. The rest assumes 1NF.
- Find every candidate key with attribute closures, and list the prime attributes.
- Split every right-hand side into single attributes and drop the trivial dependencies.
- BCNF holds when the left-hand side of every dependency is a superkey.
- Otherwise, 3NF holds when every dependency that breaks BCNF has a prime right-hand side.
- Otherwise, 2NF holds when no proper part of a candidate key has a non-prime attribute in its closure.
- Otherwise, the relation is in 1NF only.
Steps 4 and 5 may read only the dependencies written in F. If a derived dependency broke BCNF or 3NF, the closure computation that derives it would pass through a written dependency that breaks the same form. Step 6 is different: it needs the closures, because a written set of dependencies can hide a partial one. Step through the seven steps on a relation built to show the difference:
The drawing shows the whole scene; its 7 steps are listed below.
Every step as text
- Atomic. Every value of R3 is a single value, so the procedure starts from 1NF.
- Three keys. AB, AD and CD each reach all five attributes, and no single attribute does. So A, B, C and D are prime, and E is the only non-prime attribute.
- Single right sides. CD -> AB becomes CD -> A and CD -> B. The other three dependencies already have one attribute on the right.
- BCNF fails. A -> C has a left side that is no superkey, since the closure of A is only A, C and E. BCNF fails.
- 3NF fails. A -> C passes for 3NF, because C is prime, but AC -> E does not. AC is no superkey and E is not prime.
- 2NF needs closures. No written dependency has part of a key on its left and E on its right. The closure of A, part of the key AB, is A, C and E, so A -> E holds and is partial.
- 1NF only. R3 is in 1NF only. A check that read only the written dependencies would have called it 2NF.
The program runs the same procedure on three relations written the way exam questions write them, with single letters. R1(A, B, C, D) has A -> BC and C -> D, the shape of the courses table; R2(A, B, C) has AB -> C and C -> B, so every attribute is prime; and R3 is the relation of the figure:
Python 3.14 · main.py
# Sets of attributes are bit masks.
A, B, C, D, E = 1, 2, 4, 8, 16
def show(x: int) -> str:
return "".join(letter for i, letter in enumerate("ABCDE") if x >> i & 1)
def closure(x: int, fds: list[tuple[int, int]]) -> int:
grew = True
while grew:
grew = False
for lhs, rhs in fds:
if lhs & x == lhs and rhs & ~x:
x |= rhs
grew = True
return x
def highest(fds: list[tuple[int, int]]) -> str:
full = 0
for lhs, rhs in fds:
full |= lhs | rhs
keys = [x for x in range(1, full + 1) if closure(x, fds) == full]
keys = [
x
for x in keys
if all(closure(x & ~b, fds) != full for b in (A, B, C, D, E) if x & b)
]
prime = 0
for key in keys:
prime |= key
if all(closure(lhs, fds) == full for lhs, rhs in fds if rhs & ~lhs):
return "BCNF"
if all(closure(lhs, fds) == full or not rhs & ~lhs & ~prime for lhs, rhs in fds):
return "3NF"
for key in keys: # closures catch derived ones
for part in range(1, key):
extra = closure(part, fds) & ~part & ~prime
if part & key == part and extra:
return f"1NF, as {show(part)} -> {show(extra)} breaks 2NF"
return "2NF"
print("R1:", highest([(A, B | C), (C, D)]))
print("R2:", highest([(A | B, C), (C, B)]))
print("R3:", highest([(A, C), (A | C, E), (A | B, D), (C | D, A | B)]))Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py
JavaScript Node 24 · main.mjs
// Sets of attributes are bit masks.
const [A, B, C, D, E] = [1, 2, 4, 8, 16];
const show = (x) => [..."ABCDE"].filter((_, i) => (x >> i) & 1).join("");
function closure(x, fds) {
let grew = true;
while (grew) {
grew = false;
for (const [lhs, rhs] of fds) {
if ((lhs & x) === lhs && rhs & ~x) {
x |= rhs;
grew = true;
}
}
}
return x;
}
function highest(fds) {
const full = fds.reduce((all, [lhs, rhs]) => all | lhs | rhs, 0);
const keys = [];
for (let x = 1; x <= full; x++) {
let key = closure(x, fds) === full;
for (const b of [A, B, C, D, E]) key &&= !(x & b) || closure(x & ~b, fds) !== full;
if (key) keys.push(x);
}
const prime = keys.reduce((p, key) => p | key, 0);
if (fds.every(([lhs, rhs]) => !(rhs & ~lhs) || closure(lhs, fds) === full)) return "BCNF";
if (fds.every(([lhs, rhs]) => closure(lhs, fds) === full || !(rhs & ~lhs & ~prime))) {
return "3NF";
}
for (const key of keys) {
// closures catch derived ones
for (let part = 1; part < key; part++) {
const extra = closure(part, fds) & ~part & ~prime;
if ((part & key) === part && extra) {
return `1NF, as ${show(part)} -> ${show(extra)} breaks 2NF`;
}
}
}
return "2NF";
}
console.log(
"R1:",
highest([
[A, B | C],
[C, D],
]),
);
console.log(
"R2:",
highest([
[A | B, C],
[C, B],
]),
);
console.log(
"R3:",
highest([
[A, C],
[A | C, E],
[A | B, D],
[C | D, A | B],
]),
);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.
static final int A = 1;
static final int B = 2;
static final int C = 4;
static final int D = 8;
static final int E = 16;
record Fd(int lhs, int rhs) {}
static String show(int x) {
StringBuilder out = new StringBuilder();
for (int i = 0; i < 5; i++) {
if ((x >> i & 1) == 1) {
out.append("ABCDE".charAt(i));
}
}
return out.toString();
}
static int closure(int x, List<Fd> fds) {
boolean grew = true;
while (grew) {
grew = false;
for (Fd fd : fds) {
if ((fd.lhs() & x) == fd.lhs() && (fd.rhs() & ~x) != 0) {
x |= fd.rhs();
grew = true;
}
}
}
return x;
}
static String highest(List<Fd> fds) {
int full = fds.stream().mapToInt(fd -> fd.lhs() | fd.rhs()).reduce(0, (a, b) -> a | b);
List<Integer> keys = new ArrayList<>();
for (int x = 1; x <= full; x++) {
boolean key = closure(x, fds) == full;
for (int bit = A; bit <= E; bit <<= 1) {
key = key && ((x & bit) == 0 || closure(x & ~bit, fds) != full);
}
if (key) {
keys.add(x);
}
}
int prime = keys.stream().reduce(0, (a, b) -> a | b);
if (fds.stream()
.allMatch(fd -> (fd.rhs() & ~fd.lhs()) == 0 || closure(fd.lhs(), fds) == full)) {
return "BCNF";
}
if (fds.stream()
.allMatch(fd -> closure(fd.lhs(), fds) == full || (fd.rhs() & ~fd.lhs() & ~prime) == 0)) {
return "3NF";
}
for (int key : keys) { // closures catch derived ones
for (int part = 1; part < key; part++) {
int extra = closure(part, fds) & ~part & ~prime;
if ((part & key) == part && extra != 0) {
return "1NF, as " + show(part) + " -> " + show(extra) + " breaks 2NF";
}
}
}
return "2NF";
}
public static void main(String[] args) {
System.out.println("R1: " + highest(List.of(new Fd(A, B | C), new Fd(C, D))));
System.out.println("R2: " + highest(List.of(new Fd(A | B, C), new Fd(C, B))));
System.out.println(
"R3: "
+ highest(
List.of(new Fd(A, C), new Fd(A | C, E), new Fd(A | B, D), new Fd(C | D, A | B))));
}
}In Java: full is the OR of every dependency's attributes, computed in one line with mapToInt and reduce on a stream.
Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java
C++23 · main.cpp
#include <algorithm>
#include <print>
#include <string>
#include <utility>
#include <vector>
// Sets of attributes are bit masks.
enum : unsigned { A = 1, B = 2, C = 4, D = 8, E = 16 };
using Fds = std::vector<std::pair<unsigned, unsigned>>;
std::string show(unsigned x) {
std::string out;
for (int i = 0; i < 5; i++) {
if (x >> i & 1) {
out += "ABCDE"[i];
}
}
return out;
}
unsigned closure(unsigned x, const Fds &fds) {
for (bool grew = true; grew;) {
grew = false;
for (const auto &[lhs, rhs] : fds) {
if ((lhs & x) == lhs && (rhs & ~x) != 0) {
x |= rhs;
grew = true;
}
}
}
return x;
}
std::string highest(const Fds &fds) {
unsigned full = 0, prime = 0;
std::vector<unsigned> keys;
for (const auto &[lhs, rhs] : fds) {
full |= lhs | rhs;
}
for (unsigned x = 1; x <= full; x++) {
bool key = closure(x, fds) == full;
for (unsigned bit = A; bit <= E; bit <<= 1) {
key = key && ((x & bit) == 0 || closure(x & ~bit, fds) != full);
}
if (key) {
keys.push_back(x);
prime |= x;
}
}
auto holds = [&](auto test) { return std::ranges::all_of(fds, test); };
if (holds([&](auto fd) {
return (fd.second & ~fd.first) == 0 || closure(fd.first, fds) == full;
})) {
return "BCNF";
}
if (holds([&](auto fd) {
return closure(fd.first, fds) == full ||
(fd.second & ~fd.first & ~prime) == 0;
})) {
return "3NF";
}
for (unsigned key : keys) { // closures catch derived ones
for (unsigned part = 1; part < key; part++) {
const unsigned extra = closure(part, fds) & ~part & ~prime;
if ((part & key) == part && extra != 0) {
return "1NF, as " + show(part) + " -> " + show(extra) + " breaks 2NF";
}
}
}
return "2NF";
}
int main() {
std::println("R1: {}", highest({{A, B | C}, {C, D}}));
std::println("R2: {}", highest({{A | B, C}, {C, B}}));
std::println("R3: {}",
highest({{A, C}, {A | C, E}, {A | B, D}, {C | D, A | B}}));
}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.
const int A = 1;
const int B = 2;
const int C = 4;
const int D = 8;
const int E = 16;
Console.WriteLine("R1: " + Highest([(A, B | C), (C, D)]));
Console.WriteLine("R2: " + Highest([(A | B, C), (C, B)]));
Console.WriteLine("R3: " + Highest([(A, C), (A | C, E), (A | B, D), (C | D, A | B)]));
static string Show(int x) => string.Concat("ABCDE".Where((_, i) => (x >> i & 1) == 1));
static int Closure(int x, (int Lhs, int Rhs)[] fds)
{
for (bool grew = true; grew;)
{
grew = false;
foreach (var (lhs, rhs) in fds)
{
if ((lhs & x) == lhs && (rhs & ~x) != 0)
{
x |= rhs;
grew = true;
}
}
}
return x;
}
static string Highest((int Lhs, int Rhs)[] fds)
{
int full = fds.Aggregate(0, (all, fd) => all | fd.Lhs | fd.Rhs);
var keys = new List<int>();
for (int x = 1; x <= full; x++)
{
bool key = Closure(x, fds) == full;
for (int bit = A; bit <= E; bit <<= 1)
{
key = key && ((x & bit) == 0 || Closure(x & ~bit, fds) != full);
}
if (key)
{
keys.Add(x);
}
}
int prime = keys.Aggregate(0, (p, key) => p | key);
if (fds.All(fd => (fd.Rhs & ~fd.Lhs) == 0 || Closure(fd.Lhs, fds) == full))
{
return "BCNF";
}
if (fds.All(fd => Closure(fd.Lhs, fds) == full || (fd.Rhs & ~fd.Lhs & ~prime) == 0))
{
return "3NF";
}
foreach (int key in keys) // closures catch derived ones
{
for (int part = 1; part < key; part++)
{
int extra = Closure(part, fds) & ~part & ~prime;
if ((part & key) == part && extra != 0)
{
return $"1NF, as {Show(part)} -> {Show(extra)} breaks 2NF";
}
}
}
return "2NF";
}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>
// Sets of attributes are bit masks.
enum { A = 1, B = 2, C = 4, D = 8, E = 16 };
typedef struct {
unsigned lhs, rhs;
} Fd;
static char *show(unsigned x, char *out) {
char *p = out;
for (int i = 0; i < 5; i++)
if (x >> i & 1)
*p++ = "ABCDE"[i];
*p = '\0';
return out;
}
static unsigned closure(unsigned x, const Fd *fds, int n) {
for (int grew = 1; grew;) {
grew = 0;
for (int i = 0; i < n; i++)
if ((fds[i].lhs & x) == fds[i].lhs && (fds[i].rhs & ~x)) {
x |= fds[i].rhs;
grew = 1;
}
}
return x;
}
static void highest(const char *name, const Fd *fds, int n) {
char a[6], b[6];
unsigned full = 0, prime = 0, keys[32];
int count = 0, bcnf = 1, nf3 = 1;
for (int i = 0; i < n; i++)
full |= fds[i].lhs | fds[i].rhs;
for (unsigned x = 1; x <= full; x++) {
int key = closure(x, fds, n) == full;
for (unsigned bit = A; bit <= E; bit <<= 1)
key = key && (!(x & bit) || closure(x & ~bit, fds, n) != full);
if (key)
prime |= keys[count++] = x;
}
for (int i = 0; i < n; i++) {
unsigned extra = fds[i].rhs & ~fds[i].lhs;
if (closure(fds[i].lhs, fds, n) != full) {
bcnf = bcnf && !extra;
nf3 = nf3 && !(extra & ~prime);
}
}
if (bcnf || nf3) {
printf("%s: %s\n", name, bcnf ? "BCNF" : "3NF");
return;
}
for (int k = 0; k < count; k++) // closures catch derived ones
for (unsigned part = 1; part < keys[k]; part++) {
unsigned extra = closure(part, fds, n) & ~part & ~prime;
if ((part & keys[k]) == part && extra) {
printf("%s: 1NF, as %s -> %s breaks 2NF\n", name, show(part, a),
show(extra, b));
return;
}
}
printf("%s: 2NF\n", name);
}
int main(void) {
highest("R1", (const Fd[]){{A, B | C}, {C, D}}, 2);
highest("R2", (const Fd[]){{A | B, C}, {C, B}}, 2);
highest("R3", (const Fd[]){{A, C}, {A | C, E}, {A | B, D}, {C | D, A | B}},
4);
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.
const A = 1;
const B = 2;
const C = 4;
const D = 8;
const E = 16;
function show(int $x): string
{
$keep = fn(int $i): bool => ($x >> $i & 1) === 1;
return implode('', array_filter(str_split('ABCDE'), $keep, ARRAY_FILTER_USE_KEY));
}
/** @param list<array{int, int}> $fds */
function closure(int $x, array $fds): int
{
do {
$grew = false;
foreach ($fds as [$lhs, $rhs]) {
if (($lhs & $x) === $lhs && ($rhs & ~$x) !== 0) {
$x |= $rhs;
$grew = true;
}
}
} while ($grew);
return $x;
}
/** @param list<array{int, int}> $fds */
function highest(array $fds): string
{
$full = array_reduce($fds, fn(int $all, array $fd): int => $all | $fd[0] | $fd[1], 0);
$keys = [];
for ($x = 1; $x <= $full; $x++) {
$key = closure($x, $fds) === $full;
for ($bit = A; $bit <= E; $bit <<= 1) {
$key = $key && (($x & $bit) === 0 || closure($x & ~$bit, $fds) !== $full);
}
if ($key) {
$keys[] = $x;
}
}
$prime = array_reduce($keys, fn(int $p, int $key): int => $p | $key, 0);
$all = fn(callable $test): bool => count(array_filter($fds, $test)) === count($fds);
$superkey = fn(int $lhs): bool => closure($lhs, $fds) === $full;
if ($all(fn(array $fd): bool => ($fd[1] & ~$fd[0]) === 0 || $superkey($fd[0]))) {
return 'BCNF';
}
if ($all(fn(array $fd): bool => $superkey($fd[0]) || ($fd[1] & ~$fd[0] & ~$prime) === 0)) {
return '3NF';
}
foreach ($keys as $key) { // closures catch derived ones
for ($part = 1; $part < $key; $part++) {
$extra = closure($part, $fds) & ~$part & ~$prime;
if (($part & $key) === $part && $extra !== 0) {
return '1NF, as ' . show($part) . ' -> ' . show($extra) . ' breaks 2NF';
}
}
}
return '2NF';
}
echo 'R1: ' . highest([[A, B | C], [C, D]]) . "\n";
echo 'R2: ' . highest([[A | B, C], [C, B]]) . "\n";
echo 'R3: ' . highest([[A, C], [A | C, E], [A | B, D], [C | D, A | B]]) . "\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 A: u32 = 1;
const B: u32 = 2;
const C: u32 = 4;
const D: u32 = 8;
const E: u32 = 16;
fn show(x: u32) -> String {
"ABCDE"
.chars()
.enumerate()
.filter(|(i, _)| x >> i & 1 == 1)
.map(|(_, c)| c)
.collect()
}
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 == lhs && rhs & !x != 0 {
x |= rhs;
grew = true;
}
}
}
x
}
fn highest(fds: &[(u32, u32)]) -> String {
let full = fds.iter().fold(0, |all, &(lhs, rhs)| all | lhs | rhs);
let keys: Vec<u32> = (1..=full)
.filter(|&x| closure(x, fds) == full)
.filter(|&x| {
[A, B, C, D, E]
.iter()
.all(|&b| x & b == 0 || closure(x & !b, fds) != full)
})
.collect();
let prime = keys.iter().fold(0, |p, key| p | key);
if fds
.iter()
.all(|&(lhs, rhs)| rhs & !lhs == 0 || closure(lhs, fds) == full)
{
return "BCNF".to_string();
}
if fds
.iter()
.all(|&(lhs, rhs)| closure(lhs, fds) == full || rhs & !lhs & !prime == 0)
{
return "3NF".to_string();
}
for &key in &keys {
// closures catch derived ones
for part in 1..key {
let extra = closure(part, fds) & !part & !prime;
if part & key == part && extra != 0 {
return format!("1NF, as {} -> {} breaks 2NF", show(part), show(extra));
}
}
}
"2NF".to_string()
}
fn main() {
println!("R1: {}", highest(&[(A, B | C), (C, D)]));
println!("R2: {}", highest(&[(A | B, C), (C, B)]));
println!(
"R3: {}",
highest(&[(A, C), (A | C, E), (A | B, D), (C | D, A | B)])
);
}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.
const [A, B, C, D, E] = [1, 2, 4, 8, 16];
type Fd = [number, number];
const show = (x: number): string => [..."ABCDE"].filter((_, i) => (x >> i) & 1).join("");
function closure(x: number, fds: Fd[]): number {
let grew = true;
while (grew) {
grew = false;
for (const [lhs, rhs] of fds) {
if ((lhs & x) === lhs && (rhs & ~x) !== 0) {
x |= rhs;
grew = true;
}
}
}
return x;
}
function highest(fds: Fd[]): string {
const full = fds.reduce((all, [lhs, rhs]) => all | lhs | rhs, 0);
const keys: number[] = [];
for (let x = 1; x <= full; x++) {
let key = closure(x, fds) === full;
for (const b of [A, B, C, D, E]) key &&= (x & b) === 0 || closure(x & ~b, fds) !== full;
if (key) keys.push(x);
}
const prime = keys.reduce((p, key) => p | key, 0);
if (fds.every(([lhs, rhs]) => (rhs & ~lhs) === 0 || closure(lhs, fds) === full)) return "BCNF";
if (fds.every(([lhs, rhs]) => closure(lhs, fds) === full || (rhs & ~lhs & ~prime) === 0)) {
return "3NF";
}
for (const key of keys) {
// closures catch derived ones
for (let part = 1; part < key; part++) {
const extra = closure(part, fds) & ~part & ~prime;
if ((part & key) === part && extra !== 0) {
return `1NF, as ${show(part)} -> ${show(extra)} breaks 2NF`;
}
}
}
return "2NF";
}
console.log(
"R1:",
highest([
[A, B | C],
[C, D],
]),
);
console.log(
"R2:",
highest([
[A | B, C],
[C, B],
]),
);
console.log(
"R3:",
highest([
[A, C],
[A | C, E],
[A | B, D],
[C | D, A | B],
]),
);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"
// Sets of attributes are bit masks.
const A, B, C, D, E = 1, 2, 4, 8, 16
func show(x int) string {
out := ""
for i, letter := range "ABCDE" {
if x>>i&1 == 1 {
out += string(letter)
}
}
return out
}
func closure(x int, fds [][2]int) int {
for grew := true; grew; {
grew = false
for _, fd := range fds {
if fd[0]&x == fd[0] && fd[1]&^x != 0 {
x |= fd[1]
grew = true
}
}
}
return x
}
func highest(fds [][2]int) string {
full, prime, bcnf, nf3 := 0, 0, true, true
for _, fd := range fds {
full |= fd[0] | fd[1]
}
var keys []int
for x := 1; x <= full; x++ {
key := closure(x, fds) == full
for bit := A; bit <= E; bit <<= 1 {
key = key && (x&bit == 0 || closure(x&^bit, fds) != full)
}
if key {
keys = append(keys, x)
prime |= x
}
}
for _, fd := range fds {
if closure(fd[0], fds) != full {
bcnf = bcnf && fd[1]&^fd[0] == 0
nf3 = nf3 && fd[1]&^fd[0]&^prime == 0
}
}
if bcnf {
return "BCNF"
}
if nf3 {
return "3NF"
}
for _, key := range keys { // closures catch derived ones
for part := 1; part < key; part++ {
extra := closure(part, fds) &^ part &^ prime
if part&key == part && extra != 0 {
return fmt.Sprintf("1NF, as %s -> %s breaks 2NF", show(part), show(extra))
}
}
}
return "2NF"
}
func main() {
fmt.Println("R1:", highest([][2]int{{A, B | C}, {C, D}}))
fmt.Println("R2:", highest([][2]int{{A | B, C}, {C, B}}))
fmt.Println("R3:", highest([][2]int{{A, C}, {A | C, E}, {A | B, D}, {C | D, A | B}}))
}Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go
Swift 6.4 · main.swift
// Sets of attributes are bit masks.
let a = 1
let b = 2
let c = 4
let d = 8
let e = 16
func show(_ x: Int) -> String {
String("ABCDE".enumerated().filter { x >> $0.offset & 1 == 1 }.map(\.element))
}
func closure(_ start: Int, _ fds: [(Int, Int)]) -> Int {
var x = start
var grew = true
while grew {
grew = false
for (lhs, rhs) in fds where lhs & x == lhs && rhs & ~x != 0 {
x |= rhs
grew = true
}
}
return x
}
func highest(_ fds: [(Int, Int)]) -> String {
let full = fds.reduce(0) { $0 | $1.0 | $1.1 }
let keys = (1...full).filter { x in
closure(x, fds) == full
&& [a, b, c, d, e].allSatisfy { x & $0 == 0 || closure(x & ~$0, fds) != full }
}
let prime = keys.reduce(0, |)
if fds.allSatisfy({ $0.1 & ~$0.0 == 0 || closure($0.0, fds) == full }) {
return "BCNF"
}
if fds.allSatisfy({ closure($0.0, fds) == full || $0.1 & ~$0.0 & ~prime == 0 }) {
return "3NF"
}
for key in keys { // closures catch derived ones
for part in 1..<key {
let extra = closure(part, fds) & ~part & ~prime
if part & key == part && extra != 0 {
return "1NF, as \(show(part)) -> \(show(extra)) breaks 2NF"
}
}
}
return "2NF"
}
print("R1:", highest([(a, b | c), (c, d)]))
print("R2:", highest([(a | b, c), (c, b)]))
print("R3:", highest([(a, c), (a | c, e), (a | b, d), (c | d, a | b)]))In Swift: keys.reduce(0, |) passes the | operator itself as the function that combines the keys into the prime attributes.
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.
A = 1
B = 2
C = 4
D = 8
E = 16
def show(set)
'ABCDE'.chars.select.with_index { |_, i| set[i] == 1 }.join
end
def closure(start, fds)
x = start
loop do
grown = fds.reduce(x) { |acc, (lhs, rhs)| lhs & acc == lhs ? acc | rhs : acc }
return x if grown == x
x = grown
end
end
def keys_of(fds, full)
(1..full).select do |x|
closure(x, fds) == full &&
[A, B, C, D, E].all? { |bit| (x & bit).zero? || closure(x & ~bit, fds) != full }
end
end
# closures catch derived ones
def partial(fds, keys, prime)
keys.each do |key|
(1...key).each do |part|
extra = closure(part, fds) & ~part & ~prime
return "#{show(part)} -> #{show(extra)}" if part & key == part && extra != 0
end
end
nil
end
def written_form(fds, full, prime)
return 'BCNF' if fds.all? { |lhs, rhs| (rhs & ~lhs).zero? || closure(lhs, fds) == full }
'3NF' if fds.all? { |lhs, rhs| closure(lhs, fds) == full || (rhs & ~lhs & ~prime).zero? }
end
def highest(fds)
full = fds.reduce(0) { |all, (lhs, rhs)| all | lhs | rhs }
keys = keys_of(fds, full)
prime = keys.reduce(0, :|)
form = written_form(fds, full, prime)
return form if form
found = partial(fds, keys, prime)
found ? "1NF, as #{found} breaks 2NF" : '2NF'
end
puts "R1: #{highest([[A, B | C], [C, D]])}"
puts "R2: #{highest([[A | B, C], [C, B]])}"
puts "R3: #{highest([[A, C], [A | C, E], [A | B, D], [C | D, A | B]])}"In Ruby: keys.reduce(0, :|) does the same with the symbol of the | method, so the prime attributes take one call.
Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb
Kotlin 2.4 · Main.kt
// Sets of attributes are bit masks.
const val A = 1
const val B = 2
const val C = 4
const val D = 8
const val E = 16
fun show(x: Int) = "ABCDE".filterIndexed { i, _ -> x shr i and 1 == 1 }
fun closure(
start: Int,
fds: List<Pair<Int, Int>>,
): Int {
var x = start
var grew = true
while (grew) {
grew = false
for ((lhs, rhs) in fds) {
if (lhs and x == lhs && rhs and x.inv() != 0) {
x = x or rhs
grew = true
}
}
}
return x
}
fun highest(fds: List<Pair<Int, Int>>): String {
val full = fds.fold(0) { all, (lhs, rhs) -> all or lhs or rhs }
val keys =
(1..full).filter { x ->
closure(x, fds) == full &&
listOf(A, B, C, D, E).all { x and it == 0 || closure(x and it.inv(), fds) != full }
}
val prime = keys.fold(0) { p, key -> p or key }
if (fds.all { (lhs, rhs) -> rhs and lhs.inv() == 0 || closure(lhs, fds) == full }) return "BCNF"
if (fds.all { (lhs, rhs) -> closure(lhs, fds) == full || rhs and (lhs or prime).inv() == 0 }) {
return "3NF"
}
for (key in keys) { // closures catch derived ones
for (part in 1 until key) {
val extra = closure(part, fds) and part.inv() and prime.inv()
if (part and key == part && extra != 0) {
return "1NF, as ${show(part)} -> ${show(extra)} breaks 2NF"
}
}
}
return "2NF"
}
fun main() {
println("R1: " + highest(listOf(A to (B or C), C to D)))
println("R2: " + highest(listOf((A or B) to C, C to B)))
println("R3: " + highest(listOf(A to C, (A or C) to E, (A or B) to D, (C or D) to (A or B))))
}In Kotlin: "ABCDE".filterIndexed keeps the letters whose bit is set, so show needs no loop of its own.
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.
const a = 1, b = 2, c = 4, d = 8, e = 16;
String show(int x) => [
for (var i = 0; i < 5; i++)
if (x >> i & 1 == 1) 'ABCDE'[i],
].join();
int closure(int x, List<(int, int)> fds) {
for (var grew = true; grew;) {
grew = false;
for (final (lhs, rhs) in fds) {
if (lhs & x == lhs && rhs & ~x != 0) {
x |= rhs;
grew = true;
}
}
}
return x;
}
String highest(List<(int, int)> fds) {
final full = fds.fold(0, (all, fd) => all | fd.$1 | fd.$2);
final keys = [
for (var x = 1; x <= full; x++)
if (closure(x, fds) == full &&
[
a,
b,
c,
d,
e,
].every((bit) => x & bit == 0 || closure(x & ~bit, fds) != full))
x,
];
final prime = keys.fold(0, (p, key) => p | key);
if (fds.every((fd) => fd.$2 & ~fd.$1 == 0 || closure(fd.$1, fds) == full)) {
return 'BCNF';
}
if (fds.every(
(fd) => closure(fd.$1, fds) == full || fd.$2 & ~fd.$1 & ~prime == 0,
)) {
return '3NF';
}
for (final key in keys) {
// closures catch derived ones
for (var part = 1; part < key; part++) {
final extra = closure(part, fds) & ~part & ~prime;
if (part & key == part && extra != 0) {
return '1NF, as ${show(part)} -> ${show(extra)} breaks 2NF';
}
}
}
return '2NF';
}
void main() {
print('R1: ${highest([(a, b | c), (c, d)])}');
print('R2: ${highest([(a | b, c), (c, b)])}');
print('R3: ${highest([(a, c), (a | c, e), (a | b, d), (c | d, a | b)])}');
}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
R1: 2NF R2: 3NF R3: 1NF, as A -> E breaks 2NF
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. Runs on this device: a JavaScript build of this program (about 12 KB), made when the page was built. The first run also downloads the JavaScript runner (about 0.6 MB), which is kept for the next runs. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 152 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a .NET build of this program (about 3 KB), made when the page was built. The first run also downloads .NET (about 3.6 MB), which is kept for the next runs. Edit runs your changes in the browser: the first edited run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 8 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads PHP (about 4.3 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 21 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads the JavaScript runner (about 0.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 718 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 1.7 MB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads Ruby (about 10.2 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 182 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 11 KB), made when the page was built. To change the code, copy it and run it with the command below.Your run, in this browser
R1 reaches 2NF and stops there, because C -> D has a non-key on its left and a non-prime attribute on its right. R2 is
in 3NF but not in BCNF: C -> B has a left side that is no superkey, but B is prime. R3 is the trap. No written
dependency has part of a key on its left and a non-prime attribute on its right, yet A -> C and AC -> E together
give A -> E, and A is part of the key AB. A check that reads only F would call R3 2NF; the closure of A shows that it
is in 1NF.
GATE CS
The GATE 2027 syllabus for computer science lists normal forms among its database topics (GATE 2027 CS syllabus). An item that asks for the highest normal form of a relation is answered by exactly this procedure, and its second step, finding every candidate key, is the one to do with the most care.
To see a split as tables and their links, paste the CREATE TABLE statements of the four tables into an ER diagram.
SQL to ER Diagram Draw students, enrolments, courses and offices from their CREATE TABLE statements.Checkpoint
Check: The highest normal form procedure
Practise: name the highest normal form
The exercise lists three relations from a college: a hostel, exam results and sports squads. For each, give the highest normal form and a dependency that keeps it from the next one. The sample tests run the procedure of this lesson on your answers in the browser:
Exercise · Medium · Python
Name the highest normal form and the dependency that stops the next
answers.py lists three relations with their dependencies. For each one, replace the placeholder with a pair:
- the highest normal form of the relation:
"1NF","2NF","3NF"or"BCNF"; - a dependency that keeps it from the next normal form, as a string such as
"room -> block"(attribute names separated by spaces), orNonewhen the relation is in BCNF.
Any dependency that follows from the listed ones and blocks the next form is accepted, so "room -> warden" counts as well as "room -> block" when it blocks the same step. Each relation is in first normal form: every value is atomic. The sample tests compute the answer with the method of the lesson and check both parts of each pair.
Starter code · answers.py
"""For each relation: its highest normal form ("1NF", "2NF", "3NF" or "BCNF"), and a dependency that keeps it from
the next normal form, written "left -> right" with attribute names separated by spaces (None for BCNF)."""
# hostel(roll_no, room, block, warden)
# roll_no -> room; room -> block; block -> warden
HOSTEL = ("BCNF", None)
# results(roll_no, paper, attempt, marks, paper_title)
# roll_no paper attempt -> marks; paper -> paper_title
RESULTS = ("BCNF", None)
# squads(player, sport, coach)
# player sport -> coach; coach -> sport
SQUADS = ("BCNF", None)The sample tests · test_answers.py
from itertools import combinations
from answers import HOSTEL, RESULTS, SQUADS
ORDER = ["1NF", "2NF", "3NF", "BCNF"]
NEXT = {"1NF": "2NF", "2NF": "3NF", "3NF": "BCNF"}
def closure(attrs, fds):
result = set(attrs)
grew = True
while grew:
grew = False
for lhs, rhs in fds:
if lhs <= result and not rhs <= result:
result |= rhs
grew = True
return result
def parse(text):
lhs, rhs = text.split("->")
return set(lhs.split()), set(rhs.split())
def keys_of(relation, fds):
keys = []
for size in range(1, len(relation) + 1):
for combo in combinations(relation, size):
if not any(k <= set(combo) for k in keys) and closure(combo, fds) >= set(relation):
keys.append(set(combo))
return keys
def blocks(level, relation, fds, lhs, rhs):
"""Whether lhs -> rhs follows from fds and breaks the normal form after `level`."""
keys = keys_of(relation, fds)
prime = set().union(*keys)
if not rhs or rhs & lhs or not rhs <= closure(lhs, fds):
return False
superkey = closure(lhs, fds) >= set(relation)
if level == "3NF": # it must break BCNF
return not superkey
if level == "2NF": # it must break 3NF
return not superkey and not rhs & prime
if level == "1NF": # it must break 2NF: part of a key, non-prime right side
return any(lhs < k for k in keys) and not rhs & prime
return False
def highest(relation, fds):
keys = keys_of(relation, fds)
prime = set().union(*keys)
single = [(lhs, {a}) for lhs, rhs in fds for a in rhs - lhs]
if all(closure(lhs, fds) >= set(relation) for lhs, _ in single):
return "BCNF"
if all(closure(lhs, fds) >= set(relation) or rhs <= prime for lhs, rhs in single):
return "3NF"
for k in keys:
for size in range(1, len(k)):
for part in combinations(sorted(k), size):
if closure(part, fds) - set(part) - prime:
return "1NF"
return "2NF"
def check(answer, relation, texts):
fds = [parse(t) for t in texts]
level, witness = answer
assert level in ORDER, f"{level!r} is not one of {ORDER}"
want = highest(relation.split(), fds)
assert level == want, f"{level} is not the highest normal form of this relation"
if level == "BCNF":
assert witness is None, "a relation in BCNF has no dependency that blocks the next form"
return
assert isinstance(witness, str) and "->" in witness, 'name the blocking dependency as "left -> right"'
lhs, rhs = parse(witness)
assert blocks(level, relation.split(), fds, lhs, rhs), f"{witness} does not keep the relation out of {NEXT[level]}"
def test_hostel():
"""hostel(roll_no, room, block, warden)"""
check(HOSTEL, "roll_no room block warden", ["roll_no -> room", "room -> block", "block -> warden"])
def test_results():
"""results(roll_no, paper, attempt, marks, paper_title)"""
check(RESULTS, "roll_no paper attempt marks paper_title", ["roll_no paper attempt -> marks", "paper -> paper_title"])
def test_squads():
"""squads(player, sport, coach)"""
check(SQUADS, "player sport coach", ["player sport -> coach", "coach -> sport"])A hint
Start every item by finding all its candidate keys, then mark the prime attributes. In squads, ask whether {player, coach} determines sport: if it does, it is a second key, and sport is prime. Then test BCNF, 3NF and 2NF in that order, and the first test that fails gives you both the answer and the dependency to name.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
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.
The self-check below covers the six ideas of the lesson, from atomic values to the procedure, and opens where your answers have been weakest so far:
Practice that adapts to you
Practise this lesson
12 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Interview questions
Fresher to mid · What is the difference between a partial and a transitive dependency, and which normal form does each break?
Both are dependencies X -> A in which A is non-prime, that is, part of no candidate key, and X is not a superkey. They differ in X. In a partial dependency, X is a proper part of a candidate key: in enrolments keyed by (roll_no, course), roll_no -> student says the name depends on half the key. A partial dependency breaks 2NF. In a transitive dependency, X is contained in no candidate key: in courses keyed by course, instructor -> office says the office depends on the key only through the instructor. A transitive dependency breaks 3NF but not 2NF. Both are removed the same way, by moving A into a table keyed by X, and both must be judged against every candidate key, because an attribute that looks like a non-key may belong to a second key.
Two follow-ups an interviewer may add to that answer are below, each with four replies to weigh before you look at the explanation:
Checkpoint
Interview round: two follow-up questions
Two design questions of this module start from this lesson:
Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.
-
Fresher to mid
An exam seating table, seating(roll_no, session, seat, hall), is keyed by (roll_no, session) and also has session seat -> roll_no and seat -> hall. Your check says 2NF; a colleague says 1NF. Who is right, and which step decides it?
-
Mid to senior
A posts table of 5 million rows keeps each post's tags as one comma-separated string. A search for the tag "go" also returns posts tagged "golang", and counting posts per tag scans the whole table. What is wrong with the design, and how do you change it without stopping the service?
Key takeaways
- 1NF means one atomic value in each cell; a list in a column hides its values from keys, foreign keys and equality tests.
- Against every candidate key, a dependency X -> A with a non-prime A is partial when X is part of a key and transitive when X is in no key at all.
- 2NF forbids a non-prime attribute that depends on part of a candidate key, so it can fail only when some key has two or more attributes.
- 3NF asks, for every non-trivial X -> A, that X be a superkey or A be prime, and the sheet reaches it as four tables.
- Find every candidate key first: with its second key found, the seating plan is in 1NF, not 2NF.
- BCNF and 3NF can be tested on the written dependencies, but 2NF needs the closure of every proper part of every key.
Terms in this lesson
- first normal form (1NF)
- Every cell of the relation holds a single atomic value from its domain, never a list, a set or a nested table.
- partial dependency
- A dependency X -> A in which A is non-prime and X is a proper part of a candidate key. It breaks second normal form.
- prime attribute
- An attribute that belongs to at least one candidate key of the relation. An attribute in no candidate key is non-prime.
- second normal form (2NF)
- First normal form with no partial dependency, so every non-prime attribute depends on whole candidate keys.
- third normal form (3NF)
- For every non-trivial functional dependency X -> A that holds in the relation, X is a superkey or A is a prime attribute.
- transitive dependency
- A dependency X -> A in which A is non-prime and X is neither a superkey nor part of a candidate key, so A depends on a key only through X.
References
- E. F. Codd: A Relational Model of Data for Large Shared Data Banks (section 1.4, normal form) (Communications of the ACM)
- C. Zaniolo: A New Normal Form for the Design of Relational Database Schemata (ACM Transactions on Database Systems)
- W. Kent: A Simple Guide to Five Normal Forms in Relational Database Theory (Communications of the ACM)
- PostgreSQL 18 Documentation: Arrays (searching in arrays) (The PostgreSQL Global Development Group)
- SQLite: SQLite Foreign Key Support (SQLite)
- SQLite: JSON Functions and Operators (json_each) (SQLite)
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress