Summary of Normal Forms:

Key Distinction (3NF vs BCNF):
3NF permits $X \to Y$ if $Y$ is part of any candidate key (a prime attribute), even if $X$ is not a superkey. BCNF eliminates this exception entirely: $X$ must be a superkey without exception.

Definition:
A decomposition of relation $R$ into $R_1$ and $R_2$ is lossless if joining $R_1$ and $R_2$ reproduces the exact original relation $R$ without creating bogus spurious tuples:

R1 ⋈ R2 = R

The Formal Test:
A decomposition into two relations $R_1$ and $R_2$ is lossless if and only if the shared attribute set $(R_1 \cap R_2)$ forms a superkey for at least one of the decomposed relations:

(R1 ∩ R2) -> R1   OR   (R1 ∩ R2) -> R2

Armstrong's Axioms (Sound and Complete):

1. Reflexivity: If $Y \subseteq X$, then $X \to Y$.
2. Augmentation: If $X \to Y$, then $XZ \to YZ$ for any $Z$.
3. Transitivity: If $X \to Y$ and $Y \to Z$, then $X \to Z$.

Secondary Derived Rules:

• Union: If $X \to Y$ and $X \to Z$, then $X \to YZ$.
• Decomposition: If $X \to YZ$, then $X \to Y$ and $X \to Z$.
• Pseudo-transitivity: If $X \to Y$ and $WY \to Z$, then $WX \to Z$.

Why Not Binary Search Trees (AVL / Red-Black)?

1. Disk Block Alignment & Tree Height: A standard BST has a fanout of only 2. For 10,000,000 rows, a balanced BST requires $\log_2(10^7) \approx 24$ levels. If each node is on disk, traversing 24 levels requires 24 random disk I/O operations (taking ~240ms on HDDs or ~2.4ms on SSDs).
2. B+ Tree High Fanout: A B+ tree node matches the operating system / database page size (typically 4KB to 16KB). A node can store 200 to 500 keys (fanout $B \approx 300$). A B+ tree with 10,000,000 keys has a height of only $\log_300(10^7) \approx 3$ to 4 levels!
3. The root and upper intermediate nodes fit permanently in RAM buffer pool cache, requiring only 1 single disk I/O to fetch any record!

Why Not Hash Tables?

• Hash tables provide $O(1)$ point lookups (WHERE id = 500), but cannot perform range queries (WHERE age BETWEEN 25 AND 35 or ORDER BY salary).
• B+ Trees link all leaf nodes into a doubly linked list, enabling lightning-fast contiguous sequential scans for range queries.

Concept:
An index that contains all the columns requested by a query in its index keys.

-- If an index exists on: (dept_name, salary, name)
SELECT name, salary FROM instructor WHERE dept_name = 'Comp. Sci.';

Execution Advantage:
The database engine satisfies the entire query exclusively by reading the B+ tree index pages without ever touching or fetching the underlying table heap pages on disk! This produces an Index-Only Scan, cutting disk I/O by 80–95%.

• Schedule: A sequence of operations (reads, writes, commits) from a set of concurrent transactions.
• Conflict Serializability: A schedule $S$ is conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting adjacent operations.
• Two operations conflict if they belong to different transactions, access the exact same data item $Q$, and at least one of them is a write (write(Q)).

Testing Conflict Serializability with Precedence Graphs:

1. Create a node for each active transaction $T_i$.
2. Draw a directed edge $T_i \to T_j$ if $T_i$ performs an operation that conflicts with an operation performed later by $T_j$.
3. Theorem: A schedule is conflict serializable if and only if its precedence graph contains no directed cycles! If a cycle exists, the schedule is non-serializable and can cause data corruption.

1. Basic Two-Phase Locking (2PL)

• Growing Phase: Transaction may acquire locks, but cannot release any lock.
• Shrinking Phase: Transaction may release locks, but cannot acquire any new lock.
• Guarantee: Guarantees conflict serializability, but does NOT prevent deadlocks or cascading aborts.

2. Strict 2PL (Production Standard)

• All exclusive (write) locks must be held until the transaction commits or aborts.
• Guarantee: Guarantees conflict serializability AND prevents cascading aborts!

3. Rigorous 2PL

• All locks (both shared and exclusive) must be held until transaction termination.
• Guarantee: Serializes transactions in the exact order in which they commit.

The Two Fundamental WAL Rules:

1. Rule 1 (Before Page Write): Before an updated database data page is written from RAM buffer pool to non-volatile disk, the corresponding log record describing the update must already be flushed to the Write-Ahead Log on disk.
2. Rule 2 (Before Commit): Before a transaction is reported as committed to the client, all log records generated by that transaction (including the COMMIT log record) must be flushed to non-volatile disk.

Why?

• Writing random table pages to disk is extraordinarily slow.
• WAL writes sequentially to an append-only log file. This enables fast in-memory transactions with 100% ACID durability and crash recovery!

When a database recovers from an unexpected power loss or server crash, ARIES executes three distinct phases:

Crash Point
     |
[ Phase 1: Analysis ] ---> Scan log forward from last checkpoint to determine:
                             - Active uncommitted transactions at crash time.
                             - Dirty pages in buffer pool at crash time.
     |
[ Phase 2: Redo ]     ---> Scan log forward from earliest unwritten dirty page.
                             - Repeat history: replay all actions (committed & uncommitted).
                             - Brings the database to the exact state right before the crash.
     |
[ Phase 3: Undo ]     ---> Scan log backward.
                             - Roll back and reverse every operation belonging to
                               transactions that never committed prior to the crash.
                             - Write Compensation Log Records (CLRs) to prevent infinite loops.

When profiling slow queries:

• Seq Scan: Reading every disk page of the table sequentially (slow on big tables).
• Index Scan: Traversing B+ tree to find row pointers, then reading each row from heap.
• Bitmap Index Scan: Collects matching heap block pointers in a bitmap, then reads blocks in physical disk order to minimize disk arm movement!