Database theory — Computer Science

In this lesson you will learn

Distinguish superkeys, candidate, primary and foreign keys
Normalise a table up to 3NF using functional dependencies
Explain the ACID properties and calculate what an index gains

If an online shop wrote every order as one spreadsheet row, then when Anar moved from Baku to Ganja his address would have to be changed in hundreds of rows — miss one and the database holds two different cities. Database theory removes such problems with mathematical precision: it splits data into the right tables, protects it from hundreds of simultaneous users and brings searches among billions of rows down to milliseconds.

The relational model and keys

In the relational model, proposed by Edgar Codd in 1970, data is stored in relations (tables). A relation is a set of tuples (rows) sharing the same attributes; each attribute has a domain (the set of allowed values). Being a set, a relation has no row order and no duplicate rows. Queries are expressed in relational algebra, and SQL is its practical language.

π[first_name](σ[city = 'Bakı'](students)) ≡ SELECT first_name FROM students WHERE city = 'Bakı'

where:

σselection: rows meeting a condition — WHERE
πprojection: the needed columns — the SELECT list
⋈join: combining two relations on a common attribute — JOIN

Key	Definition	Example (students)
Superkey	any set of attributes that identifies a row uniquely	{id}, {id, city}
Candidate key	a minimal superkey (no attribute can be removed)	{id}
Primary key	the chosen candidate key: unique and never NULL	id
Foreign key	a reference to another table's primary key (referential integrity)	enrollments.student_id → students.id

SQL· Edit the code and run it again

SELECT COUNT(*)              AS students,
       COUNT(email)          AS with_email,
       COUNT(DISTINCT email) AS distinct_emails,
       COUNT(DISTINCT city)  AS distinct_cities
FROM students;

▸ Expected output

students | with_email | distinct_emails | distinct_cities
12 | 10 | 10 | 7

We test key candidates against the data: city cannot be a key (only 7 distinct cities in 12 rows). email is unique where filled in (10 = 10) but NULL for 2 students — so it cannot be the primary key. Note: current data never proves a key; a key is a business rule.

Normalisation: 1NF, 2NF, 3NF

A badly designed table produces three kinds of anomaly. An update anomaly: the same fact is repeated in many rows, and if one is not updated the data contradicts itself. An insertion anomaly: a new product with no orders yet cannot be stored because part of the key would be empty. A deletion anomaly: delete a customer's only order and all information about the customer is lost too. Normalisation removes these anomalies by splitting the table into pieces without losing information: every fact is stored in one place.

Definition

Functional dependency X → Y

Any two rows that agree on attributes X must also agree on attributes Y. For example customer_id → customer_city: know the customer and you know the city. Normalisation is built on exactly these dependencies.

Form	Requirement	What it removes
1NF	one atomic value per cell, no repeating groups	list cells like “Laptop, Headphones”
2NF	1NF + no non-key attribute depends on part of a composite key	partial dependencies
3NF	2NF + non-key attributes depend only on the key, not on each other	transitive dependencies

A memorable summary of 3NF: every non-key attribute must depend on “the key, the whole key and nothing but the key”.

Example 1: bringing an orders table to 3NF

A shop table: order_id, order_date, customer_id, customer_name, customer_city, products, where the products cell holds a list like “Laptop ×1, Headphones ×2”, with prices and categories inside. Bring it to 1NF, 2NF and 3NF.

Show solution

1NF: unpack the list — one row per (order, product):
(order_id, product_id, order_date, customer_id, customer_name, customer_city, product_name, category, price, quantity), key (order_id, product_id).
Dependencies: order_id → order_date, customer_id; customer_id → customer_name, customer_city; product_id → product_name, category, price; (order_id, product_id) → quantity.
2NF: split off what depends on part of the key:
order_items(order_id, product_id, quantity)
orders(order_id, order_date, customer_id, customer_name, customer_city)
products(product_id, product_name, category, price)
3NF: in orders, order_id → customer_id → customer_city is transitive, so split:
orders(order_id, order_date, customer_id) + customers(customer_id, customer_name, customer_city).
Result: 4 tables. Now Anar's city changes in a single cell.

SQL· Edit the code and run it again

SELECT s.first_name, s.city, c.title, c.teacher, e.score
FROM enrollments AS e
JOIN students AS s ON s.id = e.student_id
JOIN courses AS c ON c.id = e.course_id
WHERE c.teacher = 'Ramin Səfərov'
ORDER BY c.title, s.first_name;

▸ Expected output

first_name | city | title | teacher | score
Aysel | Bakı | Algebra | Ramin Səfərov | 92
Fidan | Naxçıvan | Algebra | Ramin Səfərov | 97
Murad | Gəncə | Algebra | Ramin Səfərov | 75
Nigar | Şəki | Algebra | Ramin Səfərov | 85
Leyla | Bakı | Geometry | Ramin Səfərov | 95
Orxan | Sumqayıt | Geometry | Ramin Səfərov | 70
Səbinə | Quba | Geometry | Ramin Səfərov | 79

The sample database is normalised: students, courses, enrollments. A JOIN rebuilds the “flat” table only when needed — here the teacher's name repeats 7 times. Had it been stored like this, changing the teacher would mean updating 7 rows (an update anomaly).

Transactions and ACID

Property	Meaning	How it is provided
Atomicity (A)	all or nothing	ROLLBACK, undo log
Consistency (C)	the database moves from one valid state to another	constraints: keys, CHECK, foreign keys
Isolation (I)	concurrent transactions do not see each other's unfinished work	locks, multiversion concurrency (MVCC)
Durability (D)	after COMMIT data survives even a power failure	write-ahead log (WAL)

SQL· Edit the code and run it again

BEGIN;
UPDATE products SET stock = stock - 2 WHERE name = 'Laptop';
INSERT INTO orders (customer_id, product_id, quantity, order_date)
VALUES (2, 1, 2, '2025-08-01');
ROLLBACK;

SELECT name, stock,
       (SELECT COUNT(*) FROM orders) AS orders_total
FROM products
WHERE name = 'Laptop';

▸ Expected output

name | stock | orders_total
Laptop | 8 | 12

Atomicity in practice: the transaction took 2 laptops out of stock and wrote an order, then was cancelled (ROLLBACK). Both changes vanished: the stock is 8 again and there are still 12 orders. With COMMIT both would have been kept together.

Full isolation is expensive, so SQL offers four isolation levels. READ UNCOMMITTED allows “dirty reads” (seeing someone's uncommitted change), READ COMMITTED allows “non-repeatable reads” (the same row differs between two reads), REPEATABLE READ allows “phantoms” (new rows appearing), and SERIALIZABLE guarantees the same result as running the transactions one after another.

Indexes, SQL and NoSQL

h = ⌈log N / log f⌉h = ⌈log N / log f⌉

where:

hheight of the B-tree index (pages read per lookup)
Nnumber of rows in the table
ffan-out: keys that fit in one page

Example 2: what an index gains

A table has N = 10⁷ rows, with 100 rows per disk page. How many pages does a WHERE email = … query read without an index, and with a B-tree index of fan-out f = 100?

Show solution

Without an index — a full scan: 10⁷ / 100 = 10⁵ pages.
With the index: h = ⌈log 10⁷ / log 100⌉ = ⌈7/2⌉ = ⌈3.5⌉ = 4 levels + 1 page for the row itself = ≈ 5 pages.
A gain of ≈ 20,000 times: O(log N) instead of O(N). The price: the index takes space, and every INSERT/UPDATE must maintain it.

Criterion	SQL (relational)	NoSQL
model	tables and relations	document, key–value, wide-column, graph
schema	strict, defined in advance	flexible
transactions	full ACID	often limited, “eventual consistency”
scaling	mostly vertical (a bigger server)	horizontal (many servers)
examples	PostgreSQL, MySQL, SQLite, SQL Server	MongoDB, Redis, Cassandra, Neo4j

The choice depends on the task: bank accounts — SQL, a session cache — Redis, social connections — a graph database. Many projects use both.

Key points

A relation is a set of tuples; a candidate key is a minimal superkey, a primary key is unique and NOT NULL, a foreign key protects integrity.
1NF — atomic values; 2NF — no partial dependencies; 3NF — no transitive dependencies.
Normalisation removes update, insertion and deletion anomalies.
ACID: atomicity, consistency, isolation, durability; ROLLBACK undoes the whole transaction.
A B-tree index cuts lookups from O(N) to O(log N) but slows down writes.

Check yourself

10 questions. Every correct answer earns XP.

1 / 10

grades(student_id, course_id, student_name, score), key (student_id, course_id), and student_id → student_name. Which normal form does the table violate?