Database Systems

1. Introduction to Database Systems

1.1 What is a Database

A database is an organised collection of structured data, managed by a database management System (DBMS). A DBMS provides:

• Data definition (schema creation and modification).
• Data manipulation (query, insert, update, delete).
• Concurrency control (multiple users accessing data simultaneously).
• Recovery (restoring data after failures).
• Security and access control.

1.2 Database Architecture

Three-schema architecture (ANSI-SPARC):

The ANSI-SPARC (American National Standards Institute, Standards Planning and Requirements Committee) Architecture defines three levels of abstraction:

1. External schema (view level): How different users/applications see the data. Each user group may have a different view. A view may hide or rename columns, join tables, or aggregate data.
2. Conceptual schema (logical level): The logical structure of the entire database (tables, relationships, constraints). Describes entities, attributes, relationships, integrity constraints, and security information. This level is database-wide and is designed by the DBA.
3. Internal schema (physical level): How data is stored on disk (indexes, file organisation, compression, encryption). Includes data structures, access paths, and storage allocation.

The DBMS maps between levels via the external/conceptual mapping (translates external views to The conceptual schema) and the conceptual/internal mapping (translates the conceptual schema to Internal storage).

Data independence:

• Logical data independence: The conceptual schema can change without affecting external views. Example: adding a new column to a table does not require modifying existing views that do not reference it.
• Physical data independence: The internal schema can change without affecting the conceptual schema. Example: changing from a B+ tree index to a hash index does not require modifying queries or table definitions.

1.3 Data Models

• Relational model: Data organised into tables (relations) with rows (tuples) and columns (attributes). Based on relational algebra and calculus.
• Entity-Relationship (ER) model: Conceptual design tool using entities, relationships, and attributes.
• Object-relational model: Extends the relational model with object-oriented features (inheritance, complex types, methods). Example: PostgreSQL supports table inheritance and array types.
• NoSQL models: Document, key-value, graph, column-family (covered in Section 8).

1.4 Comparison of Data Models

Choosing a model. Relational databases remain the default for structured data with complex Queries and strong consistency requirements. NoSQL databases excel when horizontal scalability or Flexible schemas are paramount. The choice depends on the workload, not on a blanket preference.

2. Relational Model

2.1 Relations, Tuples, Attributes

A relation $R$ over attributes $A_1, \ldots, A_n$ is a set of tuples $(a_1, \ldots, a_n)$ where Each $a_i$ is drawn from the domain of $A_i$. A relation is a subset of $D_1 \times D_2 \times \cdots \times D_n$.

Properties of relations:

• Each relation has a unique name.
• Each attribute has a unique name within a relation.
• Tuples are unordered (a relation is a set).
• All tuples are distinct (no duplicates in a mathematical relation, though SQL tables allow them).
• Attributes are unordered.

2.2 Keys

Let $R$ be a relation schema.

• Superkey: A set of attributes $K \subseteq R$ such that no two distinct tuples agree on all attributes in $K$.
• Candidate key: A minimal superkey (no proper subset is also a superkey).
• Primary key: One of the candidate keys, chosen by the designer.
• Foreign key: An attribute (or set) $FK$ in relation $R_1$ that references the primary key $PK$ of relation $R_2$. Enforces referential integrity: every value of $FK$ must appear as a value of $PK$ in $R_2$Or be NULL.

Example. Student(ID, Name, Email). ID is a candidate key (unique). If Email is also unique, It is another candidate key. One is chosen as the primary key.

Theorem 2.1. Every relation has at least one candidate key (possibly the entire set of attributes).

2.3 Relational Algebra

Relational algebra provides a formal query language based on operations on relations.

Selection $\sigma_{\theta}(R)$: Return tuples from $R$ satisfying condition $\theta$.

$\sigma_{\mathrm{dept} = \mathrm{"CS'}(\mathrm{Student})}$

Projection $\pi_{A_1, \ldots, A_k}(R)$: Return a relation containing only attributes $A_1, \ldots, A_k$.

$\pi_{\mathrm{name}, \mathrm{gpa}(\mathrm{Student})}$

Union $R \cup S$: All tuples in $R$ or $S$ (both must be union-compatible: same arity and Attribute domains).

Difference $R - S$: Tuples in $R$ but not in $S$.

Cartesian product $R \times S$: All pairs $(r, s)$ where $r \in R$ and $s \in S$.

Rename $\rho_{x}(R)$: Rename relation $R$ to $x$.

Natural join $R \bowtie S$: Combine tuples from $R$ and $S$ that agree on all common attributes.

$R \bowtie S = \pi_{R \cup S}(\sigma_{R.\mathrm{common} = S.\mathrm{common}(R \times S))}$

Theta join $R \bowtie_{\theta} S$: $\sigma_{\theta}(R \times S)$.

Equi-join $R \bowtie_{R.A = S.B} S$: A theta join where $\theta$ is an equality on specific Attributes. Keeps both join columns.

Left outer join $R \bowtie_{\mathrm{left} S}$: All tuples from $R$Matched with $S$ where possible; NULL-padded otherwise.

Right outer join $R \bowtie_{\mathrm{right} S}$: All tuples from $S$Matched with $R$.

Full outer join $R \bowtie_{\mathrm{full} S}$: All tuples from both $R$ and $S$.

Division $R \div S$: Tuples $t$ in $\pi_{R-S}(R)$ such that for every tuple $s \in S$, $(t, s) \in R$.

$R \div S = \pi_{R-S}(R) - \pi_{R-S}\Bigl(\bigl(\pi_{R-S}(R) \times S\bigr) - R\Bigr)$

Example. Find students who have taken all courses:

$\pi_{\mathrm{sid}, \mathrm{cid}(\mathrm{Takes}) \div \pi_{\mathrm{cid}(\mathrm{Course})}}$

SELECT S.sid, S.name, COUNT(E.cid) AS num_cs_courses
FROM Student S
LEFT JOIN Takes T ON S.sid = T.sid
LEFT JOIN Course C ON T.cid = C.cid AND C.dept = 'CS'
GROUP BY S.sid, S.name;

2.4 Relational Calculus

Tuple relational calculus. A query has the form $\\{t \mid P(t)\\}$ where $t$ is a tuple variable And $P$ is a well-formed formula. The formula is built from:

• Atoms: $t \in R$ (tuple $t$ is in relation $R$), $t[A] \mathbin{\mathrm{op} s[A]}$ (comparison), $t[A] \mathbin{\mathrm{op} c}$ (comparison with constant), where $\mathrm{op} \in \\{=, \neq, \lt, \gt, \le, \ge\\}$.
• Logical connectives: $\land$ (and), $\lor$ (or), $\lnot$ (not).
• Quantifiers: $\exists t$ (there exists), $\forall t$ (for all).

$\{t \mid \exists s \in \mathrm{Takes}(t[\mathrm{name}] = s[\mathrm{name}] \land s[\mathrm{grade}] = \mathrm{'A'})\}$

Domain relational calculus. Variables range over individual attribute domains (not entire tuples). A query has the form $\\{\langle x_1, \ldots, x_k \rangle \mid P(x_1, \ldots, x_k)\\}$.

$\{ \langle n \rangle \mid \exists s, g \;(\mathrm{Takes}(s, \mathrm{'CS101'}, g) \land \mathrm{Student}(s, n, \ldots) \land g = \mathrm{'A'})\}$

Safety. A calculus expression is safe if it yields a finite relation. The expression $\\{t \mid \lnot(t \in R)\\}$ is unsafe (it includes every tuple not in $R$An infinite set). We Restrict variables to domains of the relations appearing in the query.

Theorem 2.2 (Codd). Relational algebra and relational calculus (both tuple and domain) are Equally expressive: every query expressible in one is expressible in the other.

2.5 Equivalence Rules for Relational Algebra

The following rules allow the optimiser to transform queries without changing their meaning. Each rule States that two expressions produce the same relation for any input relations.

Rule 1 (Cascade of selections). $\sigma_{\theta_1 \land \theta_2}(R) \equiv \sigma_{\theta_1}(\sigma_{\theta_2}(R))$.

Proof. A tuple satisfies $\theta_1 \land \theta_2$ if and only if it satisfies both $\theta_1$ and $\theta_2$. Applying $\sigma_{\theta_2}$ first removes tuples failing $\theta_2$; then $\sigma_{\theta_1}$ removes tuples failing $\theta_1$ among the remainder. The result is exactly the Tuples satisfying both conditions. $\blacksquare$

Rule 2 (Commutativity of selections). $\sigma_{\theta_1}(\sigma_{\theta_2}(R)) \equiv \sigma_{\theta_2}(\sigma_{\theta_1}(R))$.

Proof. Immediate from the commutativity of logical conjunction ($\theta_1 \land \theta_2 \equiv \theta_2 \land \theta_1$). $\blacksquare$

Rule 3 (Selection pushdown through cross product). If $\theta$ involves only attributes of $R$ Then $\sigma_{\theta}(R \times S) \equiv \sigma_{\theta}(R) \times S$.

Proof. For each pair $(r, s)$ with $r \in R$ and $s \in S$The condition $\theta$ depends only on $r$. Filtering $(r, s)$ by $\theta$ on $R \times S$ is equivalent to first filtering $R$ by $\theta$ And then forming the cross product, since $s$ does not affect the result of $\theta$. $\blacksquare$

Rule 4 (Selection pushdown through join). If $\theta$ involves only attributes of $R$Then $\sigma_{\theta}(R \bowtie S) \equiv \sigma_{\theta}(R) \bowtie S$.

Proof. The join $R \bowtie S$ combines matching pairs from $R$ and $S$. Applying $\sigma_{\theta}$ After the join filters these pairs by $\theta$ on $R$‘s attributes. Filtering $R$ first removes Non-matching $R$-tuples before the join, yielding the same final set of pairs. $\blacksquare$

Rule 5 (Commutativity of joins). $R \bowtie S \equiv S \bowtie R$.

Proof. The natural join combines tuples agreeing on common attributes. This relation is symmetric In $R$ and $S$. $\blacksquare$

Rule 6 (Associativity of joins). $(R \bowtie S) \bowtie T \equiv R \bowtie (S \bowtie T)$.

Proof. Both expressions produce tuples from $R \times S \times T$ that agree on all attributes Shared by any pair of the three relations. $\blacksquare$

Rule 7 (Projection pushdown). If $L_1 \subseteq L_2$ and $L_2$ includes all attributes used in Join conditions, then $\pi_{L_1}(R \bowtie S) \equiv \pi_{L_1}(\pi_{L_2}(R) \bowtie \pi_{L_2}(S))$.

Proof. Projecting after the join retains only attributes in $L_1$. Since $L_2$ includes all Attributes needed for the join, performing the join on projected versions of $R$ and $S$ yields the Same join result, from which $L_1$ is then projected. $\blacksquare$

These rules form the foundation of heuristic query optimisation (see Section 7).

3. SQL

3.1 Data Definition Language (DDL)

CREATE TABLE Student (
    ID      INT PRIMARY KEY,
    Name    VARCHAR(100) NOT NULL,
    Email   VARCHAR(255) UNIQUE,
    GPA     DECIMAL(3,2) CHECK (GPA >= 0.0 AND GPA <= 4.0),
    Dept    VARCHAR(50) DEFAULT 'Undeclared'
);

CREATE TABLE Enrolment (
    StudentID  INT REFERENCES Student(ID) ON DELETE CASCADE,
    CourseID   VARCHAR(10) REFERENCES Course(CourseID),
    Grade      CHAR(2),
    Semester   VARCHAR(6),
    PRIMARY KEY (StudentID, CourseID, Semester)
);

CREATE INDEX idx_student_dept ON Student(Dept);
CREATE INDEX idx_enrolment_student ON Enrolment(StudentID);

Constraints:

3.2 Data Manipulation Language (DML)

INSERT INTO Student (ID, Name, Email, GPA)
VALUES (1, 'Alice', 'alice@univ.edu', 3.9);

UPDATE Student SET GPA = 3.95 WHERE ID = 1;

DELETE FROM Student WHERE GPA < 1.0;

3.3 Queries

SELECT S.Name, S.GPA, C.Title
FROM Student S
JOIN Enrolment E ON S.ID = E.StudentID
JOIN Course C ON E.CourseID = C.CourseID
WHERE E.Grade IN ('A', 'A-')
  AND C.Dept = 'CS'
  AND S.GPA > 3.5
ORDER BY S.GPA DESC;

Aggregate functions: COUNT``SUM``AVG``MIN``MAX.

SELECT Dept, COUNT(*) AS NumStudents, AVG(GPA) AS AvgGPA
FROM Student
GROUP BY Dept
HAVING COUNT(*) > 10
ORDER BY AvgGPA DESC;

WHERE vs. HAVING: WHERE filters rows before grouping; HAVING filters groups after.

3.4 Joins

-- Inner join: only matching rows
SELECT * FROM Student S JOIN Enrolment E ON S.ID = E.StudentID;

-- Left join: all students, with enrolment data where available
SELECT * FROM Student S LEFT JOIN Enrolment E ON S.ID = E.StudentID;

-- Self-join: find students with the same name
SELECT S1.Name, S1.ID, S2.ID
FROM Student S1 JOIN Student S2 ON S1.Name = S2.Name AND S1.ID < S2.ID;

-- Cross join: Cartesian product
SELECT * FROM Student CROSS JOIN Course;

3.5 Subqueries

-- Scalar subquery
SELECT Name FROM Student
WHERE GPA > (SELECT AVG(GPA) FROM Student);

-- Correlated subquery
SELECT S.Name, S.Dept
FROM Student S
WHERE GPA = (
    SELECT MAX(GPA) FROM Student S2 WHERE S2.Dept = S.Dept
);

-- EXISTS / NOT EXISTS
SELECT Name FROM Student S
WHERE EXISTS (
    SELECT 1 FROM Enrolment E
    WHERE E.StudentID = S.ID AND E.Grade = 'A+'
);

-- IN subquery
SELECT Name FROM Student
WHERE ID IN (SELECT StudentID FROM Enrolment WHERE CourseID = 'CS101');

-- WITH (Common Table Expression)
WITH DeptAvg AS (
    SELECT Dept, AVG(GPA) AS AvgGPA FROM Student GROUP BY Dept
)
SELECT S.Name, S.GPA, D.AvgGPA
FROM Student S JOIN DeptAvg D ON S.Dept = D.Dept
WHERE S.GPA > D.AvgGPA;

3.6 Window Functions

Window functions compute values across a set of rows related to the current row, without collapsing Rows (unlike GROUP BY).

SELECT Name, Dept, GPA,
    RANK() OVER (PARTITION BY Dept ORDER BY GPA DESC) AS DeptRank,
    DENSE_RANK() OVER (ORDER BY GPA DESC) AS OverallRank,
    AVG(GPA) OVER (PARTITION BY Dept) AS DeptAvgGPA,
    LAG(GPA, 1) OVER (PARTITION BY Dept ORDER BY GPA DESC) AS PrevGPA
FROM Student;

RANK() vs. DENSE_RANK(): RANK() leaves gaps after ties; DENSE_RANK() does not.

Other window functions: ROW_NUMBER()``LEAD()``FIRST_VALUE()``LAST_VALUE() NTILE(n)``SUM() OVER(...)``COUNT() OVER(...).

SELECT Dept, Semester, COUNT(*) AS Enrolments,
    SUM(COUNT(*)) OVER (PARTITION BY Dept ORDER BY Semester
        ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS RunningTotal
FROM Enrolment E JOIN Course C ON E.CourseID = C.CourseID
GROUP BY Dept, Semester
ORDER BY Dept, Semester;

SELECT Name, Dept, GPA,
    PERCENT_RANK() OVER (PARTITION BY Dept ORDER BY GPA) AS Percentile,
    NTILE(4) OVER (PARTITION BY Dept ORDER BY GPA) AS Quartile
FROM Student;

3.7 Views

CREATE VIEW CSStudents AS
SELECT ID, Name, GPA FROM Student WHERE Dept = 'CS';

CREATE VIEW DeptStats AS
SELECT Dept, COUNT(*) AS N, AVG(GPA) AS AvgGPA
FROM Student GROUP BY Dept;

Views are virtual tables. Updatable views (single-table, no aggregation) allow INSERT UPDATE``DELETE through the view. Materialised views store the result physically and must be Refreshed.

3.8 Recursive Common Table Expressions

Recursive CTEs allow queries on hierarchical or graph-structured data. A recursive CTE consists of A base case (non-recursive term) and a recursive step (referencing the CTE itself), joined By UNION ALL.

WITH RECURSIVE OrgChart AS (
    SELECT emp_id, name, manager_id, 1 AS level
    FROM Employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.emp_id, e.name, e.manager_id, o.level + 1
    FROM Employee e
    JOIN OrgChart o ON e.manager_id = o.emp_id
)
SELECT level, name, emp_id
FROM OrgChart
ORDER BY level, name;

WITH RECURSIVE PartsList AS (
    SELECT component_id AS part_id, quantity
    FROM BOM
    WHERE assembly_id = 'A100'

    UNION ALL

    SELECT b.component_id, p.quantity * b.quantity
    FROM PartsList p
    JOIN BOM b ON p.part_id = b.assembly_id
)
SELECT part_id, SUM(quantity) AS total_qty
FROM PartsList
GROUP BY part_id
ORDER BY total_qty DESC;

3.9 SQL Injection Prevention

SQL injection occurs when user input is concatenated directly into a SQL string, allowing an Attacker to manipulate the query structure.

Vulnerable code (Python):

cursor.execute(f"SELECT * FROM Student WHERE name = '{user_input}'")

If user_input is ' OR '1'='1The query becomes SELECT * FROM Student WHERE name = '' OR '1'='1' Returning all rows.

Types of SQL injection:

Prevention:

1. Parameterised queries (prepared statements): The DBMS treats parameters as data, never as SQL code.

cursor.execute("SELECT * FROM Student WHERE name = %s", (user_input,))

2. Input validation: Reject or sanitise input that does not match expected patterns (e.g., email format, numeric ID).
3. Least privilege: Application accounts should have only the permissions they need.
4. ORM frameworks: Use an ORM (e.g., SQLAlchemy, Django ORM) that generates parameterised queries by default.

:::caution Common Pitfall Even if you escape single quotes in user input, this is not a reliable defence against SQL injection. Use parameterised queries instead. Escape-based defences are fragile and have been bypassed by Encoding tricks (e.g., multibyte character exploits). :::

3.10 Query Optimisation Basics

The SQL query optimiser automatically selects an execution plan, but understanding the basics helps Developers write efficient queries.

Using EXPLAIN:

EXPLAIN ANALYZE
SELECT S.Name FROM Student S
JOIN Enrolment E ON S.ID = E.StudentID
WHERE E.CourseID = 'CS101';

EXPLAIN shows the estimated plan; EXPLAIN ANALYZE also runs the query and shows actual timings. Key information: sequential scan vs. Index scan, join algorithm used, estimated vs. Actual row counts, And execution time.

Common optimisation guidelines:

• Create appropriate indexes on columns used in WHERE``JOIN``ORDER BYAnd GROUP BY clauses.
• Avoid SELECT *; retrieve only the columns needed.
• Avoid N+1 queries: Fetching related data row-by-row instead of with a single join or batch query.
• Use LIMIT during development and testing to avoid processing large result sets.
• Prefer EXISTS over IN for subqueries when checking for existence (often more efficient).
• Keep statistics updated: ANALYZE (PostgreSQL) or ANALYZE TABLE (MySQL) updates the statistics the optimiser uses for cost estimation.

SELECT S.Name, S.Dept, C.Title
FROM Student S, Enrolment E, Course C
WHERE S.ID = E.StudentID
  AND E.CourseID = C.CourseID
  AND C.Dept = 'CS'
  AND S.GPA > 3.5
ORDER BY S.Name;

SELECT S.Name, S.Dept, C.Title
FROM Student S
JOIN Enrolment E ON S.ID = E.StudentID
JOIN Course C ON E.CourseID = C.CourseID
WHERE C.Dept = 'CS' AND S.GPA > 3.5
ORDER BY S.Name;

CREATE INDEX idx_course_dept ON Course(Dept);
CREATE INDEX idx_enrolment_student ON Enrolment(StudentID);
CREATE INDEX idx_enrolment_course ON Enrolment(CourseID);

4. Normalisation

4.1 Functional Dependencies

A functional dependency $X \to Y$ holds on relation $R$ if for any two tuples $t_1, t_2$ in $R$ $t_1[X] = t_2[X]$ implies $t_1[Y] = t_2[Y]$.

Armstrong’s axioms:

1. Reflexivity: If $Y \subseteq X$Then $X \to Y$.
2. Augmentation: If $X \to Y$Then $XZ \to YZ$.
3. Transitivity: If $X \to Y$ and $Y \to Z$Then $X \to Z$.

Derived rules:

4. Union: If $X \to Y$ and $X \to Z$Then $X \to YZ$.
5. Decomposition: If $X \to YZ$Then $X \to Y$ and $X \to Z$.
6. Pseudotransitivity: If $X \to Y$ and $YW \to Z$Then $XW \to Z$.

Attribute closure. $X^+$ is the set of all attributes functionally determined by $X$. Computed By starting with $X$ and repeatedly applying Armstrong’s axioms until no new attributes can be added.

Theorem 4.1. $X \to Y$ holds if and only if $Y \subseteq X^+$.

4.2 Normal Forms

First Normal Form (1NF). All attribute values are atomic (indivisible). No repeating groups or Nested relations.

Second Normal Form (2NF). In 1NF, and no non-prime attribute is partially dependent on any Candidate key. Equivalently: every non-prime attribute is fully functionally dependent on every Candidate key.

A partial dependency is $A \to B$ where $A$ is a proper subset of a candidate key and $B$ is Non-prime.

Third Normal Form (3NF). In 2NF, and for every non-trivial FD $X \to A$ in $R$Either $X$ is a Superkey or $A$ is a prime attribute.

A prime attribute is an attribute that belongs to some candidate key.

Boyce-Codd Normal Form (BCNF). For every non-trivial FD $X \to A$ in $R$, $X$ is a superkey.

Theorem 4.2. Every relation in BCNF is in 3NF, but the converse does not hold.

Proof. BCNF requires $X$ to be a superkey for every non-trivial FD $X \to A$. 3NF allows $X$ to be A superkey or $A$ to be prime. Since the BCNF condition is stricter, every BCNF relation is in 3NF. For the converse, consider $R(A, B, C)$ with FDs $AB \to C$ and $C \to B$. Candidate keys: $\\{AB\\}$, $\\{AC\\}$. $C \to B$ does not violate 3NF ($B$ is prime) but violates BCNF ($C$ is not a Superkey). $\blacksquare$

4.3 Decomposition

A decomposition of $R$ into $R_1, R_2, \ldots, R_k$ must satisfy:

1. Lossless-join: $R = R_1 \bowtie R_2 \bowtie \cdots \bowtie R_k$. No information is lost.
2. Dependency preservation: Every FD in the original schema is implied by the FDs in the decomposed schemas.

Theorem 4.3 (Lossless-join test). A decomposition of $R$ into $R_1, R_2$ is lossless if and Only if $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$.

Proof. Let $r$ be an instance of $R$ and let $r_1 = \pi_{R_1}(r)$, $r_2 = \pi_{R_2}(r)$. We must Show $r = r_1 \bowtie r_2$ under the given condition. Since $r_1$ and $r_2$ are projections of $r$ Every tuple in $r_1 \bowtie r_2$ agrees with some tuple of $r$ on every attribute. It suffices to show That no spurious tuple is produced. Suppose $(t_1, t_2) \in r_1 \bowtie r_2$ where $t_1 \in r_1$ and $t_2 \in r_2$. Since $t_1$ and $t_2$ agree on $R_1 \cap R_2$And by the condition $R_1 \cap R_2 \to R_1$ (WLOG), there exists $T' \in r$ with $T'[R_1 \cap R_2] = t_1[R_1 \cap R_2] = t_2[R_1 \cap R_2]$. Since $T'[R_1 \cap R_2] = t_1[R_1 \cap R_2]$ and $R_1 \cap R_2 \to R_1$, we have $t'[R_1] = t_1[R_1]$. Similarly $t'[R_2] = t_2[R_2]$. Thus $(t_1, t_2)$ corresponds to a real tuple $t' \in r$So no spurious tuple exists. $\blacksquare$

Dependency preservation. Let $F$ be the set of FDs for $R$. The decomposition $R_1, \ldots, R_k$ Preserves dependencies if the closure of $\bigcup_{i=1}^{k} F_i^+$ (where $F_i$ is the restriction Of $F$ to $R_i$) equals $F^+$. In practice, we check that every FD in a minimal cover of $F$ can be Tested within a single $R_i$.

Dependency preservation is important for efficient constraint checking: when updating $R_i$The DBMS can verify relevant FDs locally without joining all decomposed relations.

4.4 Normalisation Examples

Example 1. Enrolment(StudentID, CourseID, StudentName, Dept, Grade) with FDs: $\mathrm{StudentID} \to \mathrm{StudentName}$, $\mathrm{StudentID} \to \mathrm{Dept}$ $\\{\mathrm{StudentID}, \mathrm{CourseID}\\} \to \mathrm{Grade}$.

• Candidate key: $\\{\mathrm{StudentID}, \mathrm{CourseID}\\}$.
• 1NF: satisfied (atomic values).
• 2NF violation: $\mathrm{StudentID} \to \mathrm{StudentName}$ is a partial dependency (StudentID is a proper subset of the key).
• Decompose: Student(StudentID, StudentName, Dept) and Enrolment(StudentID, CourseID, Grade). Both are in 3NF and BCNF.

Example 2 (3NF but not BCNF). CourseOffering(Course, Instructor, Room, Time) with FDs: $\\{\mathrm{Course}, \mathrm{Time}\\} \to \\{\mathrm{Instructor}, \mathrm{Room}\\}$ $\mathrm{Instructor} \to \mathrm{Room}$.

• Candidate key: $\\{\mathrm{Course}, \mathrm{Time}\\}$.
• 3NF: $\mathrm{Instructor} \to \mathrm{Room}$ — Instructor is not a superkey, but Room is not prime. Wait — Room is not prime (not in any candidate key). So this actually violates 3NF too.

Let us correct: CourseOffering(Course, Instructor, Textbook) with FDs: $\mathrm{Course} \to \mathrm{Instructor}$ $\mathrm{Instructor} \to \mathrm{Textbook}$.

• Candidate key: $\\{\mathrm{Course}\\}$ (since Course determines everything transitively).
• 3NF: $\mathrm{Instructor} \to \mathrm{Textbook}$. Instructor is not a superkey. Textbook is not prime. Violates 3NF.

Better example. Class(Course, Instructor, Student) with FDs: $\\{\mathrm{Course}, \mathrm{Student}\\} \to \mathrm{Instructor}$ $\mathrm{Instructor} \to \mathrm{Course}$.

• Candidate keys: $\\{\mathrm{Course}, \mathrm{Student}\\}$, $\\{\mathrm{Instructor}, \mathrm{Student}\\}$.
• 3NF check for $\mathrm{Instructor} \to \mathrm{Course}$: Instructor is not a superkey. But Course is prime (in candidate key $\\{\mathrm{Course}, \mathrm{Student}\\}$). So 3NF is satisfied.
• BCNF check: $\mathrm{Instructor} \to \mathrm{Course}$ violates BCNF (Instructor is not a superkey).

Decompose: Teaches(Instructor, Course) and Attends(Instructor, Student). This is lossless ($\mathrm{Instructor}$ is common and $\mathrm{Instructor} \to \mathrm{Course}$ holds in Teaches). But the dependency $\\{\mathrm{Course}, \mathrm{Student}\\} \to \mathrm{Instructor}$ is Not preserved.

Theorem 4.4. Not every relation can be decomposed into BCNF while preserving dependencies. 3NF Is the strongest normal form guaranteeing dependency-preserving, lossless-join decomposition.

:::caution Common Pitfall Do not confuse partial dependency (2NF violation) with transitive dependency (3NF violation). A Partial dependency involves a proper subset of a candidate key determining a non-prime attribute. A transitive dependency involves a non-key attribute determining another non-prime attribute. :::

4.5 Multivalued Dependencies and 4NF

A multivalued dependency (MVD) $X \twoheadrightarrow Y$ holds on relation $R$ if for any two Tuples $t_1, t_2 \in R$ with $t_1[X] = t_2[X]$There exists a tuple $t_3 \in R$ such that:

• $t_3[X] = t_1[X]$
• $t_3[Y] = t_1[Y]$
• $t_3[R - X - Y] = t_2[R - X - Y]$

: $X$ determines $Y$ independently of $R - X - Y$.

Trivial MVDs: $X \twoheadrightarrow Y$ where $Y \subseteq X$ or $X \cup Y = R$.

Fourth Normal Form (4NF). $R$ is in 4NF if for every non-trivial MVD $X \twoheadrightarrow Y$ That holds on $R$, $X$ is a superkey.

Theorem 4.5. Every relation in 4NF is in BCNF.

Proof. Every FD $X \to Y$ implies the MVD $X \twoheadrightarrow Y$. In 4NF, every non-trivial MVD $X \twoheadrightarrow Y$ requires $X$ to be a superkey. Therefore, every non-trivial FD $X \to Y$ Also requires $X$ to be a superkey, which is the BCNF condition. $\blacksquare$

4NF decomposition. Given $R$ with MVD $X \twoheadrightarrow Y$ where $X$ is not a superkey, Decompose into $R_1 = X \cup Y$ and $R_2 = R - Y$. The decomposition is lossless-join.

5. Indexing

5.1 B-Trees and B+ Trees

B-Tree of order $m$. A balanced search tree where each internal node has between $\lceil m/2 \rceil$ and $M$ children. All leaves are at the same depth.

Properties:

• Root: at least 2 children (unless it is a leaf).
• Internal node with $k$ children has $k - 1$ keys.
• All leaves at the same depth $h$.
• Height: $h = O(\log_m n)$.

Operations:

• Search: $O(\log_m n)$. At each node, binary search the keys and follow the appropriate child pointer.
• Insert: Find the correct leaf. If the leaf has room, insert. If full, split the leaf and propagate the median key up. May cascade splits to the root.
• Delete: Find the key. If in an internal node, replace with predecessor/successor and delete from the leaf. If a node underflows (fewer than $\lceil m/2 \rceil - 1$ keys), redistribute from a sibling or merge with a sibling.

B+ Tree. Variant where:

• All data records are stored only in leaf nodes (internal nodes store only keys for routing).
• Leaf nodes are linked in a linked list for efficient range queries.

This makes B+ trees the standard for database indexing. The linked leaf list allows range scans in $O(\log_m n + k)$ where $k$ is the number of records in the range.

B+ Tree insert pseudocode:

def bplus_insert(root, key, value):
    leaf = find_leaf(root, key)
    insert_into_leaf(leaf, key, value)
    if len(leaf.keys) > MAX_KEYS:
        new_leaf, median = split_leaf(leaf)
        insert_into_parent(leaf.parent, median, new_leaf)