Database Management Systems

ER modelling through to recovery: keys, relational algebra, the SQL that gets asked, normalisation up to BCNF, indexing, ACID, concurrency control and the NoSQL contrast.

If you remember nothing else

A primary key is unique and never null; a candidate key is any minimal set that could serve as one; a foreign key references another relation's key.
1NF removes repeating groups, 2NF removes partial dependencies, 3NF removes transitive dependencies, BCNF requires every determinant to be a superkey.
ACID: Atomicity (all or nothing), Consistency (valid states only), Isolation (concurrent looks serial), Durability (committed survives a crash).
Two-phase locking guarantees serialisability but not freedom from deadlock - strict 2PL additionally prevents cascading rollback.
An index makes reads faster and writes slower; it is a trade, never a free win.
The isolation anomalies in order of severity: dirty read, non-repeatable read, phantom read - each removed by a higher isolation level.

9 chapters

1Why a DBMS, and the three-schema architecture
2The ER model
3The relational model and keys
4SQL that actually gets asked
5Functional dependencies and normalisation
6Indexing and storage
7Transactions and ACID
8Concurrency control and recovery
9NoSQL and the CAP theorem

Why a DBMS, and the three-schema architecture

Problem with plain files	What a DBMS provides
Data redundancy and inconsistency	Normalisation and a single source of truth
No enforced structure	Schemas, types and integrity constraints
Difficult ad-hoc queries	A declarative query language with an optimiser
No concurrency handling	Transactions, locking, isolation levels
Partial updates on crash	Atomicity and recovery from a write-ahead log
No access control	Users, roles, privileges

The ER model

Element	Meaning	Notation
Entity	A distinguishable real-world object	Rectangle
Weak entity	Cannot be identified without an owner entity	Double rectangle
Attribute	A property of an entity	Ellipse
Key attribute	Uniquely identifies an entity	Underlined ellipse
Multivalued attribute	May hold several values (phone numbers)	Double ellipse
Derived attribute	Computed from others (age from date of birth)	Dashed ellipse
Composite attribute	Decomposes further (address → street, city)	Ellipse with sub-ellipses
Relationship	An association between entities	Diamond

The relational model and keys

Key	Definition	Nulls?	How many per table
Super key	Any attribute set that uniquely identifies a row	-	Many
Candidate key	A minimal super key - no attribute can be removed	No	One or more
Primary key	The chosen candidate key	Never null	Exactly one
Alternate key	A candidate key not chosen as primary	No	Zero or more
Composite key	A key made of two or more attributes	No	-
Foreign key	References a candidate key of another (or the same) relation	May be null	Zero or more
Surrogate key	An artificial identifier with no business meaning	No	Usually one

Relational algebra

Operation	Symbol	Does	SQL equivalent
Selection	$σ$	Picks rows matching a predicate	`WHERE`
Projection	$π$	Picks columns	`SELECT` list
Union	$\cup$	All rows in either (must be union-compatible)	`UNION`
Set difference	$-$	Rows in the first but not the second	`EXCEPT`
Cartesian product	$\times$	Every pairing of rows	`CROSS JOIN`
Rename	$ρ$	Renames a relation or attribute	`AS`
Natural join	$⋈$	Join on all common attributes	`NATURAL JOIN`
Division	$\div$	"Find rows related to all of a set"	No direct equivalent

The first six are the primitive operators; join and division are derived from them.

SQL that actually gets asked

Sub-language	Commands	Purpose
DDL	`CREATE`, `ALTER`, `DROP`, `TRUNCATE`	Define structure
DML	`SELECT`, `INSERT`, `UPDATE`, `DELETE`	Manipulate data
DCL	`GRANT`, `REVOKE`	Control access
TCL	`COMMIT`, `ROLLBACK`, `SAVEPOINT`	Manage transactions

Join	Returns
INNER JOIN	Only rows with a match on both sides
LEFT OUTER JOIN	All left rows; nulls where the right has no match
RIGHT OUTER JOIN	All right rows; nulls where the left has no match
FULL OUTER JOIN	All rows from both sides, nulls where unmatched
CROSS JOIN	Cartesian product - every combination
SELF JOIN	A table joined to itself, e.g. employee to manager

SQLThe query-clause execution order

SELECT   d.name, COUNT(*) AS headcount, AVG(e.salary) AS avg_salary
FROM     employees e
JOIN     departments d ON d.id = e.dept_id
WHERE    e.hired_at >= '2020-01-01'      -- filters ROWS, before grouping
GROUP BY d.name
HAVING   COUNT(*) > 5                    -- filters GROUPS, after aggregation
ORDER BY avg_salary DESC
LIMIT    10;

-- Logical evaluation order (NOT the written order):
--   FROM -> JOIN -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY -> LIMIT
--
-- This is why a SELECT alias cannot be used in WHERE (SELECT has not run yet)
-- but CAN be used in ORDER BY (it has).

SQLThe two classic query questions

-- 1. Second-highest salary (correlated subquery version)
SELECT MAX(salary) FROM employees
WHERE salary < (SELECT MAX(salary) FROM employees);

-- The general N-th highest, using a window function:
SELECT DISTINCT salary FROM (
    SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
    FROM employees
) t WHERE rnk = 2;

-- 2. Find and remove duplicates, keeping the lowest id
DELETE FROM employees
WHERE id NOT IN (SELECT MIN(id) FROM employees GROUP BY email);

Functional dependencies and normalisation

Normalisation exists to remove update, insertion and deletion anomalies - the situations where redundant storage lets the database contradict itself.

Form	Requirement	Removes
1NF	All attributes atomic; no repeating groups or multivalued fields	Repeating groups
2NF	1NF, and every non-key attribute fully depends on the whole primary key	Partial dependencies (only relevant with a composite key)
3NF	2NF, and no non-key attribute depends on another non-key attribute	Transitive dependencies
BCNF	For every dependency $X \to Y$ , X is a superkey	Anomalies from overlapping candidate keys
4NF	BCNF, and no non-trivial multivalued dependencies	Independent multivalued facts in one table
5NF	4NF, and no join dependency not implied by candidate keys	Remaining join anomalies

Plain textWorking the normal forms on one example

UNNORMALISED
StudentID | Name  | Courses          | Dept   | DeptHead
   1      | Rina  | DB, OS, Networks | CSE    | Dr. Khan

1NF - make values atomic (one course per row):
StudentID | Name | Course   | Dept | DeptHead
   1      | Rina | DB       | CSE  | Dr. Khan
   1      | Rina | OS       | CSE  | Dr. Khan
Primary key is now (StudentID, Course).

2NF - Name, Dept and DeptHead depend only on StudentID, which is PART
of the composite key. That is a partial dependency. Split:
   STUDENT(StudentID, Name, Dept, DeptHead)
   ENROLMENT(StudentID, Course)

3NF - in STUDENT, StudentID -> Dept -> DeptHead. DeptHead depends on a
non-key attribute, so it is transitive. Split again:
   STUDENT(StudentID, Name, Dept)
   DEPARTMENT(Dept, DeptHead)
   ENROLMENT(StudentID, Course)

Now: changing the head of CSE is ONE update, not one per student.

Indexing and storage

	Clustered index	Non-clustered index
Determines physical row order	Yes	No
Number per table	At most one	Many
Leaf level contains	The actual data rows	Key plus a pointer or the clustering key
Range query speed	Excellent - rows are already adjacent	Slower - each hit may need a separate lookup
Extra lookup needed	No	Yes, unless the index covers the query

Index type	Good for	Poor for
B+ tree	Equality, ranges, ordering, prefix matches	Very low-cardinality columns
Hash	Exact equality only	Any range query - hashing destroys ordering
Bitmap	Low-cardinality columns in analytics (gender, status)	High-update OLTP tables
Full-text	Word and phrase search inside documents	Structured comparisons

Transactions and ACID

Atomicity
All operations commit or none do. A transfer that debits one account and fails before crediting the other must leave no trace. Implemented by the undo log.
Consistency
A transaction moves the database from one valid state to another, respecting every declared constraint. This one is partly the application's responsibility, not purely the DBMS's.
Isolation
Concurrent transactions produce the same result as some serial execution. Implemented by locking or by multi-version concurrency control.
Durability
Once committed, the effect survives a crash. Implemented by forcing the write-ahead log to stable storage before acknowledging the commit.

Transaction state	Meaning
Active	Executing
Partially committed	Final statement executed; changes still in buffers
Committed	Successfully completed and durable
Failed	Normal execution can no longer proceed
Aborted	Rolled back; the database is restored to its prior state

Schedules and serialisability

Two operations conflict if they belong to different transactions, act on the same data item, and at least one is a write. Read-read never conflicts.

Anomaly	What happens	Prevented from
Dirty read	T2 reads a value T1 wrote but has not committed; T1 then aborts	Read Committed
Non-repeatable read	T2 reads the same row twice and gets different values, because T1 updated it in between	Repeatable Read
Phantom read	T2 re-runs a range query and finds new rows, because T1 inserted matching rows	Serializable
Lost update	Two transactions read then write the same item; one overwrites the other	Repeatable Read and above

Isolation level	Dirty read	Non-repeatable read	Phantom read
Read Uncommitted	Possible	Possible	Possible
Read Committed	Prevented	Possible	Possible
Repeatable Read	Prevented	Prevented	Possible
Serializable	Prevented	Prevented	Prevented

Higher isolation means less concurrency. Most systems default to Read Committed; the correct level is a deliberate trade, not an oversight.

Concurrency control and recovery

Approach	Mechanism	Best when
Pessimistic (locking)	Acquire a lock before access; block conflicting transactions	Conflicts are common - the lock cost is worth it
Optimistic (validation)	Execute freely, then validate at commit and abort on conflict	Conflicts are rare - most transactions never pay a cost
Timestamp ordering	Each transaction gets a timestamp; conflicting operations must respect that order or abort	Deadlock-free by construction, but more aborts
MVCC	Writers create a new version; readers see a consistent snapshot	Read-heavy workloads - readers never block writers. Used by PostgreSQL and Oracle

Recovery

Analysis
Scan forward from the last checkpoint to determine which transactions were active at the crash.
Redo
Replay every logged change from the checkpoint forward, restoring the exact state at the moment of the crash - including changes made by transactions that had not committed.
Undo
Roll back every transaction that had not committed, walking their log records backwards. What remains is exactly the committed state.

NoSQL and the CAP theorem

Family	Model	Good at	Examples
Key-value	Opaque value under a key	Caching, sessions - the simplest and fastest	Redis, DynamoDB
Document	Self-describing JSON-like documents	Varying schemas, nested data	MongoDB, CouchDB
Column-family	Rows with sparse, grouped columns	Huge write volumes, time series	Cassandra, HBase
Graph	Nodes and edges as first-class objects	Traversals - social graphs, fraud, recommendations	Neo4j, Neptune

	SQL (relational)	NoSQL
Schema	Fixed, enforced up front	Flexible or absent
Scaling	Primarily vertical; sharding is manual work	Horizontal by design
Consistency model	Strong (ACID)	Often eventual (BASE)
Joins	First-class	Limited or absent - denormalise instead
Best for	Complex relationships, transactional integrity	Huge volume, simple access patterns, evolving schemas

Database Management Systems

ER modelling through to recovery: keys, relational algebra, the SQL that gets asked, normalisation up to BCNF, indexing, ACID, concurrency control and the NoSQL contrast.

If you remember nothing else

A primary key is unique and never null; a candidate key is any minimal set that could serve as one; a foreign key references another relation's key.
1NF removes repeating groups, 2NF removes partial dependencies, 3NF removes transitive dependencies, BCNF requires every determinant to be a superkey.
ACID: Atomicity (all or nothing), Consistency (valid states only), Isolation (concurrent looks serial), Durability (committed survives a crash).
Two-phase locking guarantees serialisability but not freedom from deadlock - strict 2PL additionally prevents cascading rollback.
An index makes reads faster and writes slower; it is a trade, never a free win.
The isolation anomalies in order of severity: dirty read, non-repeatable read, phantom read - each removed by a higher isolation level.

9 chapters

1Why a DBMS, and the three-schema architecture
2The ER model
3The relational model and keys
4SQL that actually gets asked
5Functional dependencies and normalisation
6Indexing and storage
7Transactions and ACID
8Concurrency control and recovery
9NoSQL and the CAP theorem

Why a DBMS, and the three-schema architecture

Problem with plain files	What a DBMS provides
Data redundancy and inconsistency	Normalisation and a single source of truth
No enforced structure	Schemas, types and integrity constraints
Difficult ad-hoc queries	A declarative query language with an optimiser
No concurrency handling	Transactions, locking, isolation levels
Partial updates on crash	Atomicity and recovery from a write-ahead log
No access control	Users, roles, privileges

The ER model

Element	Meaning	Notation
Entity	A distinguishable real-world object	Rectangle
Weak entity	Cannot be identified without an owner entity	Double rectangle
Attribute	A property of an entity	Ellipse
Key attribute	Uniquely identifies an entity	Underlined ellipse
Multivalued attribute	May hold several values (phone numbers)	Double ellipse
Derived attribute	Computed from others (age from date of birth)	Dashed ellipse
Composite attribute	Decomposes further (address → street, city)	Ellipse with sub-ellipses
Relationship	An association between entities	Diamond

The relational model and keys

Key	Definition	Nulls?	How many per table
Super key	Any attribute set that uniquely identifies a row	-	Many
Candidate key	A minimal super key - no attribute can be removed	No	One or more
Primary key	The chosen candidate key	Never null	Exactly one
Alternate key	A candidate key not chosen as primary	No	Zero or more
Composite key	A key made of two or more attributes	No	-
Foreign key	References a candidate key of another (or the same) relation	May be null	Zero or more
Surrogate key	An artificial identifier with no business meaning	No	Usually one

Relational algebra

Operation	Symbol	Does	SQL equivalent
Selection	$σ$	Picks rows matching a predicate	`WHERE`
Projection	$π$	Picks columns	`SELECT` list
Union	$\cup$	All rows in either (must be union-compatible)	`UNION`
Set difference	$-$	Rows in the first but not the second	`EXCEPT`
Cartesian product	$\times$	Every pairing of rows	`CROSS JOIN`
Rename	$ρ$	Renames a relation or attribute	`AS`
Natural join	$⋈$	Join on all common attributes	`NATURAL JOIN`
Division	$\div$	"Find rows related to all of a set"	No direct equivalent

The first six are the primitive operators; join and division are derived from them.

SQL that actually gets asked

Sub-language	Commands	Purpose
DDL	`CREATE`, `ALTER`, `DROP`, `TRUNCATE`	Define structure
DML	`SELECT`, `INSERT`, `UPDATE`, `DELETE`	Manipulate data
DCL	`GRANT`, `REVOKE`	Control access
TCL	`COMMIT`, `ROLLBACK`, `SAVEPOINT`	Manage transactions

Join	Returns
INNER JOIN	Only rows with a match on both sides
LEFT OUTER JOIN	All left rows; nulls where the right has no match
RIGHT OUTER JOIN	All right rows; nulls where the left has no match
FULL OUTER JOIN	All rows from both sides, nulls where unmatched
CROSS JOIN	Cartesian product - every combination
SELF JOIN	A table joined to itself, e.g. employee to manager

SQLThe query-clause execution order

SELECT   d.name, COUNT(*) AS headcount, AVG(e.salary) AS avg_salary
FROM     employees e
JOIN     departments d ON d.id = e.dept_id
WHERE    e.hired_at >= '2020-01-01'      -- filters ROWS, before grouping
GROUP BY d.name
HAVING   COUNT(*) > 5                    -- filters GROUPS, after aggregation
ORDER BY avg_salary DESC
LIMIT    10;

-- Logical evaluation order (NOT the written order):
--   FROM -> JOIN -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY -> LIMIT
--
-- This is why a SELECT alias cannot be used in WHERE (SELECT has not run yet)
-- but CAN be used in ORDER BY (it has).

SQLThe two classic query questions

-- 1. Second-highest salary (correlated subquery version)
SELECT MAX(salary) FROM employees
WHERE salary < (SELECT MAX(salary) FROM employees);

-- The general N-th highest, using a window function:
SELECT DISTINCT salary FROM (
    SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
    FROM employees
) t WHERE rnk = 2;

-- 2. Find and remove duplicates, keeping the lowest id
DELETE FROM employees
WHERE id NOT IN (SELECT MIN(id) FROM employees GROUP BY email);

Functional dependencies and normalisation

Normalisation exists to remove update, insertion and deletion anomalies - the situations where redundant storage lets the database contradict itself.

Form	Requirement	Removes
1NF	All attributes atomic; no repeating groups or multivalued fields	Repeating groups
2NF	1NF, and every non-key attribute fully depends on the whole primary key	Partial dependencies (only relevant with a composite key)
3NF	2NF, and no non-key attribute depends on another non-key attribute	Transitive dependencies
BCNF	For every dependency $X \to Y$ , X is a superkey	Anomalies from overlapping candidate keys
4NF	BCNF, and no non-trivial multivalued dependencies	Independent multivalued facts in one table
5NF	4NF, and no join dependency not implied by candidate keys	Remaining join anomalies

Plain textWorking the normal forms on one example

UNNORMALISED
StudentID | Name  | Courses          | Dept   | DeptHead
   1      | Rina  | DB, OS, Networks | CSE    | Dr. Khan

1NF - make values atomic (one course per row):
StudentID | Name | Course   | Dept | DeptHead
   1      | Rina | DB       | CSE  | Dr. Khan
   1      | Rina | OS       | CSE  | Dr. Khan
Primary key is now (StudentID, Course).

2NF - Name, Dept and DeptHead depend only on StudentID, which is PART
of the composite key. That is a partial dependency. Split:
   STUDENT(StudentID, Name, Dept, DeptHead)
   ENROLMENT(StudentID, Course)

3NF - in STUDENT, StudentID -> Dept -> DeptHead. DeptHead depends on a
non-key attribute, so it is transitive. Split again:
   STUDENT(StudentID, Name, Dept)
   DEPARTMENT(Dept, DeptHead)
   ENROLMENT(StudentID, Course)

Now: changing the head of CSE is ONE update, not one per student.

Indexing and storage

	Clustered index	Non-clustered index
Determines physical row order	Yes	No
Number per table	At most one	Many
Leaf level contains	The actual data rows	Key plus a pointer or the clustering key
Range query speed	Excellent - rows are already adjacent	Slower - each hit may need a separate lookup
Extra lookup needed	No	Yes, unless the index covers the query

Index type	Good for	Poor for
B+ tree	Equality, ranges, ordering, prefix matches	Very low-cardinality columns
Hash	Exact equality only	Any range query - hashing destroys ordering
Bitmap	Low-cardinality columns in analytics (gender, status)	High-update OLTP tables
Full-text	Word and phrase search inside documents	Structured comparisons

Transactions and ACID

Atomicity
All operations commit or none do. A transfer that debits one account and fails before crediting the other must leave no trace. Implemented by the undo log.
Consistency
A transaction moves the database from one valid state to another, respecting every declared constraint. This one is partly the application's responsibility, not purely the DBMS's.
Isolation
Concurrent transactions produce the same result as some serial execution. Implemented by locking or by multi-version concurrency control.
Durability
Once committed, the effect survives a crash. Implemented by forcing the write-ahead log to stable storage before acknowledging the commit.

Transaction state	Meaning
Active	Executing
Partially committed	Final statement executed; changes still in buffers
Committed	Successfully completed and durable
Failed	Normal execution can no longer proceed
Aborted	Rolled back; the database is restored to its prior state

Schedules and serialisability

Two operations conflict if they belong to different transactions, act on the same data item, and at least one is a write. Read-read never conflicts.

Anomaly	What happens	Prevented from
Dirty read	T2 reads a value T1 wrote but has not committed; T1 then aborts	Read Committed
Non-repeatable read	T2 reads the same row twice and gets different values, because T1 updated it in between	Repeatable Read
Phantom read	T2 re-runs a range query and finds new rows, because T1 inserted matching rows	Serializable
Lost update	Two transactions read then write the same item; one overwrites the other	Repeatable Read and above

Isolation level	Dirty read	Non-repeatable read	Phantom read
Read Uncommitted	Possible	Possible	Possible
Read Committed	Prevented	Possible	Possible
Repeatable Read	Prevented	Prevented	Possible
Serializable	Prevented	Prevented	Prevented

Higher isolation means less concurrency. Most systems default to Read Committed; the correct level is a deliberate trade, not an oversight.

Concurrency control and recovery

Approach	Mechanism	Best when
Pessimistic (locking)	Acquire a lock before access; block conflicting transactions	Conflicts are common - the lock cost is worth it
Optimistic (validation)	Execute freely, then validate at commit and abort on conflict	Conflicts are rare - most transactions never pay a cost
Timestamp ordering	Each transaction gets a timestamp; conflicting operations must respect that order or abort	Deadlock-free by construction, but more aborts
MVCC	Writers create a new version; readers see a consistent snapshot	Read-heavy workloads - readers never block writers. Used by PostgreSQL and Oracle

Recovery

Analysis
Scan forward from the last checkpoint to determine which transactions were active at the crash.
Redo
Replay every logged change from the checkpoint forward, restoring the exact state at the moment of the crash - including changes made by transactions that had not committed.
Undo
Roll back every transaction that had not committed, walking their log records backwards. What remains is exactly the committed state.

NoSQL and the CAP theorem

Family	Model	Good at	Examples
Key-value	Opaque value under a key	Caching, sessions - the simplest and fastest	Redis, DynamoDB
Document	Self-describing JSON-like documents	Varying schemas, nested data	MongoDB, CouchDB
Column-family	Rows with sparse, grouped columns	Huge write volumes, time series	Cassandra, HBase
Graph	Nodes and edges as first-class objects	Traversals - social graphs, fraud, recommendations	Neo4j, Neptune

	SQL (relational)	NoSQL
Schema	Fixed, enforced up front	Flexible or absent
Scaling	Primarily vertical; sharding is manual work	Horizontal by design
Consistency model	Strong (ACID)	Often eventual (BASE)
Joins	First-class	Limited or absent - denormalise instead
Best for	Complex relationships, transactional integrity	Huge volume, simple access patterns, evolving schemas

Database Management Systems

If you remember nothing else

Why a DBMS, and the three-schema architecture

The ER model

The relational model and keys

Relational algebra

SQL that actually gets asked

Functional dependencies and normalisation

Indexing and storage

Transactions and ACID

Schedules and serialisability

Concurrency control and recovery

Recovery

NoSQL and the CAP theorem

Self-check

Database Management Systems

If you remember nothing else

Why a DBMS, and the three-schema architecture

The ER model

The relational model and keys

Relational algebra

SQL that actually gets asked

Functional dependencies and normalisation

Indexing and storage

Transactions and ACID

Schedules and serialisability

Concurrency control and recovery

Recovery

NoSQL and the CAP theorem

Self-check

Database Management Systems

If you remember nothing else

1Why a DBMS, and the three-schema architecture

2The ER model

3The relational model and keys

Relational algebra

4SQL that actually gets asked

5Functional dependencies and normalisation

6Indexing and storage

7Transactions and ACID

Schedules and serialisability

8Concurrency control and recovery

Recovery

9NoSQL and the CAP theorem

Database Management Systems

If you remember nothing else

1Why a DBMS, and the three-schema architecture

2The ER model

3The relational model and keys

Relational algebra

4SQL that actually gets asked

5Functional dependencies and normalisation

6Indexing and storage

7Transactions and ACID

Schedules and serialisability

8Concurrency control and recovery

Recovery

9NoSQL and the CAP theorem

Why a DBMS, and the three-schema architecture

The ER model

The relational model and keys

SQL that actually gets asked

Functional dependencies and normalisation

Indexing and storage

Transactions and ACID

Concurrency control and recovery

NoSQL and the CAP theorem

Why a DBMS, and the three-schema architecture

The ER model

The relational model and keys

SQL that actually gets asked

Functional dependencies and normalisation

Indexing and storage

Transactions and ACID

Concurrency control and recovery

NoSQL and the CAP theorem