DBMS — Database Management Systems

1. Introduction

DBMS vs RDBMS Basic

A DBMS (Database Management System) is software that lets you create, store, retrieve, update, and manage data. It's a broad umbrella — it doesn't mandate any particular data model. Examples include flat-file systems, hierarchical DBs (IMS), network DBs, and even simple key-value stores.

An RDBMS (Relational DBMS) is a DBMS that specifically implements the relational model: data lives in tables (relations) made of rows (tuples) and columns (attributes), with formally defined relationships enforced through keys and constraints. Examples: PostgreSQL, MySQL, Oracle, SQL Server.

Three-Schema Architecture Intermediate

The ANSI-SPARC three-schema architecture separates how data is physically stored from how it's logically structured from how each user sees it. This separation is the theoretical basis for data independence.

Data Independence Intermediate

• Logical data independence: ability to change the conceptual schema (e.g., add a new table, add a column) without altering external schemas or application programs. Harder to achieve, because applications are logically tied to the conceptual structure.
• Physical data independence: ability to change the internal schema (storage structure, indexes, file organization) without changing the conceptual schema. Easier to achieve — e.g., adding an index doesn't change how you query the table.

Advantages of DBMS over File Systems Basic

• Data redundancy & inconsistency control — normalization avoids storing the same fact in multiple places.
• Data integrity — constraints (PK, FK, CHECK, NOT NULL) enforced centrally instead of in scattered application code.
• Concurrent access control — file systems have poor built-in support for safe concurrent read/write; DBMS provides locking/MVCC.
• Security — fine-grained access control (grants, roles, row-level security) vs. coarse file permissions.
• Crash recovery — write-ahead logging guarantees durability and consistent recovery after a crash.
• Data abstraction — via the three-schema architecture, users are shielded from storage details.
• Efficient querying — declarative SQL + query optimizer vs. hand-written file-scanning code.

2. ER Modeling

Entities & Attributes Basic

An entity is a real-world object or concept distinguishable from others (e.g., a specific Employee). An entity set is a collection of similar entities (all Employees). Attributes describe properties of an entity (name, age, salary).

Attribute Types Basic

Relationships & Cardinality Basic

A relationship is an association between two or more entities. Cardinality defines how many instances of one entity relate to instances of another.

Participation constraints add further nuance: total participation (double line — every entity must participate, e.g. every Employee must belong to a Department) vs. partial participation (single line — participation optional).

Keys Overview Intermediate

ER-to-Relational Mapping Rules Intermediate

1. Strong entity → its own table, with simple/single-valued attributes as columns and the key attribute as primary key.
2. Composite attribute → flatten into its component simple attributes as separate columns (e.g., first_name, last_name instead of a single "Name" column).
3. Multivalued attribute → becomes its own table with a foreign key back to the owning entity (can't be a single column, would violate 1NF).
4. 1:1 relationship → add the foreign key to either side (commonly the side with mandatory/total participation), or merge into one table.
5. 1:N relationship → add the foreign key on the "many" side, referencing the "one" side's primary key.
6. M:N relationship → create a new junction/bridge table containing foreign keys to both entities (and any relationship attributes). The junction table's primary key is typically the composite of both foreign keys.
7. Weak entity → becomes a table whose primary key is the composite of its own partial key plus the owning (identifying) entity's primary key, with a foreign key to that owner (usually with ON DELETE CASCADE).

-- M:N mapping example: Students <-> Courses via Enrollment junction table
CREATE TABLE Student (
    student_id INT PRIMARY KEY,
    name       VARCHAR(100) NOT NULL
);

CREATE TABLE Course (
    course_id  INT PRIMARY KEY,
    title      VARCHAR(100) NOT NULL
);

CREATE TABLE Enrollment (
    student_id INT NOT NULL,
    course_id  INT NOT NULL,
    enrolled_on DATE NOT NULL,
    grade      CHAR(2),
    PRIMARY KEY (student_id, course_id),
    FOREIGN KEY (student_id) REFERENCES Student(student_id),
    FOREIGN KEY (course_id)  REFERENCES Course(course_id)
);

Weak Entities Intermediate

A weak entity has no primary key of its own — it depends on a "strong"/owner entity for identification. It has a partial key (discriminator) that's unique only within the scope of one owner. Drawn with a double-bordered rectangle in ER diagrams; the identifying relationship is drawn with a double-bordered diamond.

Example: A Dependent (e.g., an employee's child) is weak — dependent_name is only unique per Employee, not globally. Its actual primary key becomes (employee_id, dependent_name).

3. Relational Model & Keys

Relations, Tuples, Domains Basic

• Relation — a table; formally a set of tuples (so, in pure theory, no duplicate rows and no ordering — real SQL relaxes this).
• Tuple — a row; a single record in the relation.
• Attribute — a column, with a name.
• Domain — the set of allowable atomic values for an attribute (e.g., domain of age is positive integers 0–150).
• Degree — number of attributes (columns) in a relation.
• Cardinality — number of tuples (rows) in a relation at a given time.

Integrity Constraints Basic

Relational Algebra Basics Intermediate

Relational algebra is the procedural formal language underlying SQL. Every SQL query is, conceptually, translated into a tree of these operators.

-- Relational algebra: π name, salary (σ dept = 'Engineering' (Employee))
-- Equivalent SQL:
SELECT name, salary
FROM Employee
WHERE dept = 'Engineering';

4. Normalization

Functional Dependencies Intermediate

A functional dependency X → Y means: given the value of attribute set X, the value of attribute set Y is uniquely determined. X is the determinant. FDs are the mathematical backbone that all normal forms are defined against.

Example: in Employee(emp_id, emp_name, dept_id, dept_name), emp_id → emp_name, dept_id and dept_id → dept_name both hold.

• Full functional dependency: Y depends on the whole of composite key X, not on any proper subset.
• Partial dependency: Y depends on only part of a composite key X.
• Transitive dependency: X → Y and Y → Z implies X → Z, where Y is not a candidate key (i.e., a non-key attribute determines another non-key attribute).

Armstrong's Axioms Advanced

A sound and complete set of inference rules for deriving all FDs implied by a given set (the "closure").

Derived rules built from these three: Union (X→Y, X→Z ⟹ X→YZ), Decomposition (X→YZ ⟹ X→Y and X→Z), Pseudotransitivity (X→Y, WY→Z ⟹ WX→Z).

1NF — First Normal Form Basic

A relation is in 1NF if every attribute holds only atomic (indivisible) values — no repeating groups, no multivalued or composite attributes stored as a single cell.

2NF — Second Normal Form Basic

A relation is in 2NF if it's in 1NF and has no partial dependency — every non-key attribute depends on the whole composite primary key, not just part of it. (2NF is automatically satisfied if the primary key is a single column.)

course_name depends only on course_id, and student_name only on student_id — both are partial dependencies. Fix: decompose into three relations.

3NF — Third Normal Form Intermediate

A relation is in 3NF if it's in 2NF and has no transitive dependency of a non-key attribute on the primary key (i.e., no non-key attribute depends on another non-key attribute).

emp_id → dept_id → dept_name is transitive (dept_name depends on dept_id, a non-key attribute). Also causes update anomalies: renaming the department requires updating every employee row.

BCNF — Boyce-Codd Normal Form Advanced

A relation is in BCNF if, for every non-trivial functional dependency X → Y, X is a super key. BCNF is stricter than 3NF — 3NF allows a specific exception (Y is part of some candidate key) that BCNF does not.

Decomposing into Teacher_Subject(teacher, subject) and Student_Teacher(student, teacher) achieves BCNF, but note it loses the ability to enforce "a student learns a subject from only one teacher" via simple FK/key constraints — this is BCNF's classic dependency-preservation trade-off.

4NF & 5NF (Briefly) Advanced

4NF deals with multivalued dependencies (MVDs). A relation violates 4NF when two or more independent multivalued facts about an entity are stored in one table, causing redundancy. Example: Employee(emp, skill, language) where skills and languages are independent of each other — storing all combinations is redundant. Fix: split into Employee_Skill(emp, skill) and Employee_Language(emp, language).

5NF (Project-Join Normal Form) deals with join dependencies — a relation is in 5NF if it cannot be decomposed into smaller relations without loss of information, and every join dependency is implied by the candidate keys. It's rarely tested for by hand in practice; interviewers mostly want you to recognize the name and the general idea ("no lossless decomposition possible beyond this point").

Decomposition Properties Intermediate

When you decompose a relation R into R1 and R2, two properties matter:

• Lossless-join decomposition: joining R1 and R2 back together (natural join) reproduces exactly R, with no spurious extra rows. Guaranteed when the common attribute(s) R1 ∩ R2 form a candidate key of at least one of R1 or R2.
• Dependency preservation: every functional dependency from the original set can still be checked/enforced without needing to join tables back together. BCNF decompositions can sometimes sacrifice this (see the Teaches example above); 3NF decompositions always preserve dependencies (via the synthesis algorithm) while guaranteeing losslessness too — which is why 3NF is sometimes chosen as a pragmatic compromise over BCNF.

Denormalization Intermediate

Denormalization intentionally introduces redundancy (merges tables, duplicates columns, pre-computes aggregates) to reduce the number of joins and speed up reads, at the cost of write complexity and potential inconsistency.

When it makes sense in practice:

• Read-heavy analytical/reporting workloads (data warehouses, OLAP) where join costs dominate and data is refreshed in batches.
• Caching a computed value (e.g., storing order_total on the Order row instead of recomputing SUM over OrderItems every read).
• High-traffic APIs where join latency is unacceptable and eventual consistency of the duplicated field is tolerable.
• Materialized views as a controlled, refreshable form of denormalization — best of both worlds when the DB supports them.

5. SQL Deep Dive

DDL / DML / DCL / TCL Basic

Join Types Basic

Sample tables used throughout this section:

-- INNER JOIN: only matching rows on both sides
SELECT e.name, d.dept_name
FROM Employee e
INNER JOIN Department d ON e.dept_id = d.dept_id;
-- Result: Asha | Engineering   (Ravi and Meera dropped - no match)

-- LEFT (OUTER) JOIN: all rows from Employee, NULLs where no match
SELECT e.name, d.dept_name
FROM Employee e
LEFT JOIN Department d ON e.dept_id = d.dept_id;
-- Result: Asha|Engineering, Ravi|NULL, Meera|NULL

-- RIGHT (OUTER) JOIN: all rows from Department, NULLs where no match
SELECT e.name, d.dept_name
FROM Employee e
RIGHT JOIN Department d ON e.dept_id = d.dept_id;
-- Result: Asha|Engineering, NULL|Sales

-- FULL OUTER JOIN: all rows from both sides, NULLs where no match
SELECT e.name, d.dept_name
FROM Employee e
FULL OUTER JOIN Department d ON e.dept_id = d.dept_id;
-- Result: Asha|Engineering, Ravi|NULL, Meera|NULL, NULL|Sales

-- CROSS JOIN: cartesian product (every row x every row)
SELECT e.name, d.dept_name
FROM Employee e
CROSS JOIN Department d;
-- Result: 3 x 2 = 6 rows

-- SELF JOIN: table joined with itself (e.g. employee-manager)
SELECT e.name AS employee, m.name AS manager
FROM Employee e
LEFT JOIN Employee m ON e.manager_id = m.emp_id;

Subqueries vs Joins vs CTEs Intermediate

-- Subquery in WHERE
SELECT name FROM Employee
WHERE dept_id IN (SELECT dept_id FROM Department WHERE dept_name = 'Engineering');

-- Equivalent JOIN (often more efficient - optimizer can pick better plans)
SELECT e.name FROM Employee e
JOIN Department d ON e.dept_id = d.dept_id
WHERE d.dept_name = 'Engineering';

-- CTE (Common Table Expression) - readable, can be recursive
WITH eng_depts AS (
    SELECT dept_id FROM Department WHERE dept_name = 'Engineering'
)
SELECT e.name FROM Employee e
JOIN eng_depts ed ON e.dept_id = ed.dept_id;

-- Recursive CTE: org chart traversal
WITH RECURSIVE org_chart 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, oc.level + 1
    FROM Employee e
    JOIN org_chart oc ON e.manager_id = oc.emp_id
)
SELECT * FROM org_chart ORDER BY level;

Rule of thumb: correlated subqueries (referencing the outer query per row) are usually the slowest; a good optimizer can rewrite an IN-subquery into a semi-join equivalent to a regular join, but this isn't guaranteed across all engines/versions. CTEs favor readability; in PostgreSQL < 12, CTEs were an "optimization fence" (materialized, not inlined) — this changed in PG12+, where non-recursive CTEs can be inlined like subqueries unless marked MATERIALIZED.

GROUP BY / HAVING vs WHERE Basic

WHERE filters rows before grouping; HAVING filters groups after aggregation. You cannot use aggregate functions in WHERE.

SELECT dept_id, COUNT(*) AS emp_count, AVG(salary) AS avg_salary
FROM Employee
WHERE status = 'active'          -- filters rows first
GROUP BY dept_id
HAVING COUNT(*) > 5              -- filters groups after aggregation
ORDER BY avg_salary DESC;

Logical order of execution (not the order you type it!): FROM → WHERE → GROUP BY → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT. This is why you can't reference a SELECT-aliased column in WHERE, but you often can in ORDER BY.

Window Functions Intermediate

Window functions compute a value across a set of rows ("window") related to the current row, without collapsing rows like GROUP BY does.

-- ROW_NUMBER: unique sequential number per partition, no ties
SELECT name, dept_id, salary,
       ROW_NUMBER() OVER (PARTITION BY dept_id ORDER BY salary DESC) AS rn
FROM Employee;

-- RANK: same rank for ties, but skips the next rank number(s)
SELECT name, dept_id, salary,
       RANK() OVER (PARTITION BY dept_id ORDER BY salary DESC) AS rnk
FROM Employee;
-- e.g. ranks: 1, 2, 2, 4 (rank 3 is skipped)

-- DENSE_RANK: same rank for ties, no gaps
SELECT name, dept_id, salary,
       DENSE_RANK() OVER (PARTITION BY dept_id ORDER BY salary DESC) AS drnk
FROM Employee;
-- e.g. ranks: 1, 2, 2, 3

-- LAG / LEAD: access previous / next row's value
SELECT name, salary,
       LAG(salary, 1) OVER (ORDER BY hire_date)  AS prev_salary,
       LEAD(salary, 1) OVER (ORDER BY hire_date) AS next_salary
FROM Employee;

-- Running total with SUM() OVER
SELECT name, hire_date, salary,
       SUM(salary) OVER (ORDER BY hire_date
                          ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS running_total
FROM Employee;

Views, Stored Procedures & Triggers Intermediate

-- View: a saved, named query - virtual table
CREATE VIEW engineering_employees AS
SELECT e.name, e.salary
FROM Employee e JOIN Department d ON e.dept_id = d.dept_id
WHERE d.dept_name = 'Engineering';

-- Stored procedure (PostgreSQL syntax)
CREATE OR REPLACE PROCEDURE give_raise(p_emp_id INT, p_pct NUMERIC)
LANGUAGE plpgsql AS $$
BEGIN
    UPDATE Employee
    SET salary = salary * (1 + p_pct / 100.0)
    WHERE emp_id = p_emp_id;
END;
$$;
CALL give_raise(1, 10);

-- Trigger: fires automatically on a table event
CREATE OR REPLACE FUNCTION log_salary_change() RETURNS TRIGGER AS $$
BEGIN
    IF NEW.salary <> OLD.salary THEN
        INSERT INTO SalaryAudit(emp_id, old_salary, new_salary, changed_at)
        VALUES (OLD.emp_id, OLD.salary, NEW.salary, NOW());
    END IF;
    RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER trg_salary_audit
AFTER UPDATE ON Employee
FOR EACH ROW
EXECUTE FUNCTION log_salary_change();

Materialized views differ from regular views: they physically store the query result and must be refreshed (REFRESH MATERIALIZED VIEW), trading staleness for read speed — regular views re-execute the underlying query on every access.

Trick Queries Interviewers Love Advanced

-- Nth highest salary (see also the full Practical SQL section below)
SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
LIMIT 1 OFFSET (3 - 1);   -- 3rd highest, 0-indexed OFFSET

-- Find duplicate emails
SELECT email, COUNT(*) AS cnt
FROM Users
GROUP BY email
HAVING COUNT(*) > 1;

-- Department-wise top 2 earners
SELECT name, dept_id, salary FROM (
    SELECT name, dept_id, salary,
           DENSE_RANK() OVER (PARTITION BY dept_id ORDER BY salary DESC) AS rnk
    FROM Employee
) ranked
WHERE rnk <= 2;

-- Delete duplicate rows, keeping the lowest ctid/id
DELETE FROM Employee e1
USING Employee e2
WHERE e1.emp_id > e2.emp_id
  AND e1.email = e2.email;

6. Transactions & ACID

ACID Properties Basic

Transaction States Basic

Active → Partially Committed → Committed, with two failure exits: Active/Partially Committed → Failed → Aborted.

• Active: the initial state, while the transaction is executing.
• Partially committed: after the final statement executes, but before all changes are guaranteed durably on disk.
• Committed: transaction completed successfully, changes are permanent.
• Failed: normal execution cannot proceed (constraint violation, deadlock victim, etc.).
• Aborted: the transaction has been rolled back and the database restored to its state prior to the transaction's start.

Schedules Intermediate

A schedule is an interleaved sequence of operations from multiple transactions.

• Serial schedule: transactions execute one completely after another, no interleaving. Always consistent, but no concurrency.
• Serializable schedule: an interleaved schedule whose effect is equivalent to some serial schedule. This is the actual goal — you want concurrency's throughput with serial execution's safety.
• Conflict-serializable: can be transformed into a serial schedule by swapping non-conflicting adjacent operations (two operations conflict if they're from different transactions, access the same data item, and at least one is a write). Checked via a precedence graph — if it's acyclic, the schedule is conflict-serializable.
• View-serializable: a weaker, more general condition — equivalent to some serial schedule in terms of what each transaction "reads" and the final writes. Every conflict-serializable schedule is view-serializable, but not vice versa (view-serializability allows "blind writes" that conflict-serializability would reject).

Recoverable & Cascadeless Schedules Advanced

• Recoverable schedule: if transaction T2 reads a data item written by T1, then T1 must commit before T2 commits. Otherwise, if T1 aborts after T2 already committed, T2's commit can never be undone — an unrecoverable state.
• Cascadeless (cascade-avoiding) schedule: T2 can only read a data item written by T1 after T1 has committed (not just before T2 commits). This avoids "cascading rollbacks," where aborting T1 forces T2, T3... (everyone who read T1's uncommitted data) to also abort.
• Strict schedule: even stronger — a transaction can neither read nor write a data item until the transaction that last wrote it has committed or aborted. Strict schedules are always cascadeless and recoverable. Strict 2PL guarantees strict schedules.

7. Concurrency Control

Lock-Based Protocols: 2PL Intermediate

Two-Phase Locking (2PL) requires every transaction to acquire all the locks it needs before releasing any — split into a growing phase (only acquiring locks) and a shrinking phase (only releasing locks). This guarantees conflict-serializability.

Basic 2PL can release locks any time after the last one is acquired (still allows non-recoverable schedules). Strict 2PL holds all exclusive (write) locks until the transaction commits or aborts — guarantees strict, recoverable, cascadeless schedules and is what virtually all production RDBMSs use. Rigorous 2PL holds both shared and exclusive locks until commit/abort — simpler to implement, used by many systems in practice.

Timestamp Ordering Protocol Advanced

Each transaction gets a unique timestamp at start (usually the start time). The protocol ensures the equivalent serial order matches timestamp order — no locks involved. Every data item tracks Read_TS (largest timestamp of any transaction that read it) and Write_TS (largest timestamp of any transaction that wrote it).

• If a transaction T tries to write an item last read/written by a younger transaction (higher timestamp), T is too late — rolled back and restarted with a new timestamp.
• If T tries to read an item written by a younger transaction, same thing — rolled back.

Guarantees conflict-serializability by construction, with no deadlocks (transactions never wait — they just get rolled back), but can cause more restarts under high contention than lock-based approaches.

Optimistic Concurrency Control (OCC) Advanced

OCC assumes conflicts are rare, so it skips locking during execution and instead validates at the end. Three phases:

1. Read phase: transaction reads data and computes writes in a private workspace, no locks taken.
2. Validation phase: before committing, check whether any other transaction that committed in the meantime conflicts with this one's read/write set.
3. Write phase: if validation passes, apply the writes; if it fails, abort and retry.

Best for low-contention workloads (few conflicts) — avoids lock overhead entirely. Poor for high-contention workloads, since transactions repeatedly abort and retry, wasting work.

MVCC — Multi-Version Concurrency Control Advanced

Instead of locking rows for reads, MVCC keeps multiple versions of each row, each tagged with the transaction/timestamp that created it. Readers see a consistent snapshot of the database as of when their transaction/statement began, without blocking writers, and writers don't block readers.

• PostgreSQL: every row has hidden system columns xmin (creating transaction ID) and xmax (deleting/updating transaction ID). An UPDATE doesn't modify a row in place — it inserts a new row version and marks the old one's xmax. Old ("dead") row versions are later reclaimed by VACUUM.
• MySQL InnoDB: keeps old versions in the undo log/rollback segment. Each row has hidden DB_TRX_ID and DB_ROLL_PTR (pointer to the undo log entry holding the previous version). Reads reconstruct older versions on demand by walking the undo chain, rather than storing full historical row copies in the table itself.

Isolation Levels & Anomalies Intermediate

• Dirty read: reading uncommitted changes from another transaction, which might later be rolled back.
• Non-repeatable read: re-reading the same row within a transaction gives a different value, because another transaction updated and committed it in between.
• Phantom read: re-running the same range query within a transaction returns a different set of rows, because another transaction inserted/deleted rows matching the predicate.

Default isolation level differs across engines: PostgreSQL and Oracle default to Read Committed; MySQL InnoDB defaults to Repeatable Read.

8. Indexing

B-Tree vs B+ Tree Intermediate

Both are balanced, multi-way (not binary) search trees designed to minimize disk I/O by keeping the tree shallow (high fan-out per node, sized to match a disk page).

Why B+ trees for disk-based databases specifically: the linked leaf list makes ordered range scans (BETWEEN, >, ORDER BY on the indexed column) sequential I/O instead of repeated random root-to-leaf traversals; and keeping internal nodes data-free maximizes fan-out per fixed-size disk page, which minimizes tree height and therefore the number of disk seeks per lookup (a B+ tree of height 3-4 can index billions of rows).

Clustered vs Non-Clustered Index Intermediate

• Clustered index: determines the actual physical storage order of table rows. There can be only one per table (you can't sort the same physical data two different ways at once). In InnoDB, the primary key is the clustered index — the whole table is stored as a B+ tree keyed on the PK, with actual row data in the leaves.
• Non-clustered (secondary) index: a separate structure that stores the indexed column(s) plus a pointer/reference back to the actual row. A table can have many non-clustered indexes. In InnoDB, a secondary index's leaf stores the primary key value (not a direct disk pointer) — so a secondary-index lookup means one traversal on the secondary index, then a second traversal on the clustered index using that PK (this extra hop is called a "bookmark lookup").

Composite Indexes & Column Order Intermediate

A composite (multi-column) index on (a, b, c) is sorted first by a, then by b within each a, then by c within each b — like a phone book sorted by (last_name, first_name). This is the leftmost-prefix rule.

CREATE INDEX idx_dept_salary ON Employee(dept_id, salary);

-- Uses the index fully (dept_id is the leftmost column)
SELECT * FROM Employee WHERE dept_id = 10 AND salary > 50000;

-- Uses the index (dept_id prefix only, salary ignored for lookup)
SELECT * FROM Employee WHERE dept_id = 10;

-- Cannot use this index efficiently - salary alone is not a leftmost prefix
SELECT * FROM Employee WHERE salary > 50000;

Covering Index Intermediate

A covering index contains all the columns a query needs (in the WHERE, SELECT, ORDER BY, GROUP BY clauses) so the engine can answer the query directly from the index itself, without a second lookup into the base table ("index-only scan"). This is a major performance win because it avoids the extra I/O of chasing row pointers.

-- Covering index for this exact query pattern
CREATE INDEX idx_covering ON Employee(dept_id, salary) INCLUDE (name);
-- or in engines without INCLUDE, just add name into the key itself:
CREATE INDEX idx_covering2 ON Employee(dept_id, salary, name);

SELECT name, salary FROM Employee WHERE dept_id = 10;
-- Can be fully answered from idx_covering / idx_covering2 alone

Hashing: Static, Dynamic, Extendible Advanced

• Static hashing: a fixed number of buckets determined up front by a hash function. Fast O(1) lookups while the data fits, but degrades badly (long overflow chains) as the table grows beyond the fixed bucket count — requires a full, expensive rehash to resize.
• Dynamic hashing: grows the hash structure incrementally as data grows, avoiding one giant rehash. Uses techniques like linear hashing, splitting one bucket at a time in a round-robin fashion as load increases.
• Extendible hashing: uses a directory of pointers to buckets, indexed by the first i bits of the hash value (the "global depth"). When a bucket overflows, only that bucket splits (its "local depth" increases); if local depth catches up to global depth, the directory itself doubles. This bounds the cost of growth to doubling a pointer directory, not rehashing all data.

Hash indexes vs B+ tree indexes: hash indexes give O(1) average-case equality lookups but cannot support range queries, sorting, or prefix matching (<, >, BETWEEN, LIKE 'abc%') at all — the hash destroys ordering. B+ trees support both equality and range/ordered access at O(log n), which is why B+ trees are the default index type in almost every RDBMS, with hash indexes offered only as a specialized option (e.g., PostgreSQL's USING HASH).

When an Index Hurts Write Performance Intermediate

Every index must be updated on every INSERT/UPDATE/DELETE that touches an indexed column — so more indexes means more write amplification. Symptoms:

• Each additional index roughly adds another B+ tree to maintain per write — more page splits, more WAL/log volume, more I/O.
• Indexes on high-churn columns (frequently updated values) cause frequent page splits/rebalancing.
• Bulk loads are often faster with indexes dropped, data loaded, then indexes rebuilt in bulk (which is more I/O-efficient than incremental maintenance).
• Over-indexing (adding an index for every possible query pattern "just in case") is a common real-world anti-pattern — always weigh read benefit against write cost for that table's actual workload.

EXPLAIN / EXPLAIN ANALYZE Basics Intermediate

-- EXPLAIN: shows the planned execution plan WITHOUT running the query
EXPLAIN SELECT * FROM Employee WHERE dept_id = 10;

-- EXPLAIN ANALYZE: actually RUNS the query and shows real timing/row counts
EXPLAIN ANALYZE SELECT * FROM Employee WHERE dept_id = 10;

/* Sample PostgreSQL output:
Index Scan using idx_dept_salary on employee
  (cost=0.29..8.31 rows=1 width=64)
  (actual time=0.02..0.03 rows=1 loops=1)
  Index Cond: (dept_id = 10)
Planning Time: 0.1 ms
Execution Time: 0.05 ms
*/

Key things to check in a plan: whether it's doing a Seq Scan (full table scan) when you expected an Index Scan; whether rows estimated vs actual diverge wildly (a sign of stale statistics); and where most of the total time is actually spent (nested loops over large row counts are a common culprit).

9. Query Processing & Optimization

Query Execution Plan Basics Intermediate

A SQL query goes through: Parsing (syntax check, build a parse tree) → Translation to an internal relational-algebra-like representation → Optimization (choose the cheapest equivalent execution plan) → Execution (actually run the chosen plan operator tree, typically pulling rows via an iterator/"Volcano" model where each operator calls next() on its children).

Cost-Based Optimization Advanced

Modern optimizers enumerate multiple equivalent logical plans (different join orders, different access paths) and estimate the cost of each (in abstract units combining estimated disk I/O, CPU, and memory), picking the cheapest. Cost estimation relies heavily on statistics: table row counts, column value distributions/histograms, index selectivity (fraction of rows a predicate is expected to match), and correlations between columns.

For queries with many joins, exhaustively trying every join order is factorial in the number of tables — real optimizers use dynamic programming (System R style, practical up to ~10-12 tables) or heuristics/genetic algorithms beyond that to keep planning time bounded.

Join Algorithms Advanced

Hash join is generally the fastest for large equi-joins when memory allows the build side to fit (or use a grace/partitioned hash join when it doesn't). It cannot be used for non-equi joins (e.g., <, BETWEEN) — those require nested loop or sort-merge.

How the Optimizer Chooses Advanced

• Small outer table / usable index on inner join column → (index) nested loop join, since the per-row lookup cost is low.
• Large unsorted tables, equi-join, enough memory → hash join, since it's near-linear and avoids a full sort.
• Inputs already sorted (e.g., both indexed on join key) or memory too limited for a hash table → sort-merge join.
• Non-equi join conditions → nested loop (sometimes block nested loop), since hash/sort-merge require equality predicates.
• The optimizer's choice depends entirely on cost estimates from statistics — this is why stale statistics (see Advanced Topics below) can cause a previously-fast query to suddenly pick a terrible plan after data grows or shifts in distribution.

10. NoSQL & CAP Theorem

SQL vs NoSQL Trade-offs Basic

CAP Theorem & PACELC Advanced

The CAP theorem (Brewer) states that a distributed data store can only guarantee two of the following three simultaneously during a network partition:

• Consistency (C): every read receives the most recent write or an error (linearizability) — all nodes see the same data at the same time.
• Availability (A): every request receives a (non-error) response, without guarantee it contains the most recent write.
• Partition tolerance (P): the system continues to operate despite network partitions (dropped/delayed messages between nodes).

Types of NoSQL Databases Basic

When to Choose NoSQL Over SQL Intermediate

• Schema changes frequently, or different records naturally have different shapes (e.g., product catalog with wildly varying attributes per category).
• You need massive horizontal write scale beyond what sharding an RDBMS comfortably gives you.
• Access patterns are simple key-based lookups or document retrieval rather than complex ad hoc joins/aggregations.
• Eventual consistency is acceptable for the use case (social feeds, product catalogs, analytics events) — vs. financial ledgers, where you'd stick with an RDBMS's strong consistency and ACID transactions.
• Relationships are graph-shaped and traversal-heavy (friend-of-friend, shortest path) — a native graph DB beats simulating this with SQL joins.

This is the same reasoning that motivates using MongoDB in a MERN/full-stack context — see the Full Stack page for MongoDB-specific patterns building on these NoSQL fundamentals.

11. Distributed Databases

Sharding Strategies Advanced

Sharding (horizontal partitioning) splits a large dataset across multiple independent database nodes, each holding a subset of the rows.

Replication Strategies Advanced

• Single-leader (master-slave / leader-follower): all writes go to one leader node, which propagates changes to follower/replica nodes. Reads can be served from followers (with possible staleness). Simple, avoids write conflicts by construction, but the leader is a single point of failure/bottleneck for writes.
• Multi-leader: writes accepted at more than one node (e.g., one leader per datacenter), with changes replicated between leaders. Better write availability across regions, but requires conflict resolution when the same data is modified concurrently at two leaders.
• Leaderless (Dynamo-style): any replica can accept a write; clients (or a coordinator) write to W replicas and read from R replicas, using quorums (W + R > total replicas N guarantees overlap) to balance consistency and availability. Used by Cassandra, DynamoDB, Riak. Conflicting concurrent writes are resolved via version vectors/last-write-wins or application-level merge logic.

Consistency Models Advanced

• Strong consistency (linearizability): any read after a write completes is guaranteed to see that write (and everything appears to happen in one global, real-time order). Expensive to guarantee across a distributed system — usually means coordinating through a single leader or a consensus protocol.
• Eventual consistency: if no new writes occur, all replicas will eventually converge to the same value — but there's no bound on how "stale" a read might be in the meantime. Common in leaderless/AP systems.
• Causal consistency: a middle ground — operations that are causally related (one happened-before another, e.g., a reply to a comment) are seen by everyone in the same order, but causally unrelated operations can be seen in different orders by different nodes. Cheaper to implement than strong consistency while avoiding some of eventual consistency's most confusing anomalies (like seeing a reply before the comment it replies to).

Two-Phase Commit (2PC) Advanced

2PC coordinates an atomic commit across multiple independent nodes/databases participating in one distributed transaction (e.g., a transaction touching two different shards).

1. Phase 1 — Prepare/Vote: the coordinator asks every participant "can you commit?" Each participant does as much work as needed to guarantee it can commit if told to (writes to its own log), then replies "yes" (ready) or "no" (abort).
2. Phase 2 — Commit/Abort: if all participants voted yes, the coordinator tells everyone to commit; if any voted no (or timed out), it tells everyone to abort. Participants then durably commit/abort and acknowledge.

12. Advanced & Rare Topics

These are the topics that separate "read the textbook" candidates from candidates who've actually looked under the hood of a real database engine. Many interviewers themselves won't probe this deep — bringing these up unprompted is a strong signal.

Write-Ahead Logging & ARIES Recovery Advanced

Write-Ahead Logging (WAL): before any data page modification is written to disk, a log record describing that change must first be written (and flushed) to the durable log. This is what makes atomicity and durability possible — after a crash, the log is the source of truth for what needs to be redone or undone.

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the industry-standard crash recovery algorithm (used, in spirit, by most production RDBMSs). It has three phases, run in this order after a crash/restart:

1. Analysis: scan the log forward from the last checkpoint to figure out which transactions were active (not yet committed/aborted) at crash time, and which data pages might be "dirty" (modified in memory but not yet flushed to disk).
2. Redo: replay every logged change since the relevant point — even for transactions that later aborted — to bring the database to the exact state it was in at the moment of the crash. ("Repeating history.")
3. Undo: roll back the changes of any transaction that was still active (not committed) at crash time, using the log's undo information, restoring the database to a state where only committed work remains.

Key optimization: ARIES uses checkpoints to bound how far back the Analysis phase must scan, and Compensation Log Records (CLRs) during Undo so that if a second crash happens mid-recovery, the algorithm doesn't redo/undo the same undo operation twice.

How B+ Tree Page Splits/Merges Actually Work Advanced

Each B+ tree node maps to one fixed-size disk page (e.g., 8KB in PostgreSQL, 16KB in InnoDB by default).

• Split (on insert): when inserting a key into a full leaf page, the page is split into two pages (roughly half the keys in each), and a copy of the smallest key of the new right page is inserted as a separator into the parent. If the parent is also full, the split propagates upward — in the worst case all the way to the root, which is how the tree grows in height (always from the root, keeping the tree perfectly balanced).
• Merge/redistribution (on delete): when a delete causes a page to fall below a minimum fill factor (commonly ~50%), the engine either borrows a key from an adjacent sibling page (redistribution) or merges the underfull page with a sibling, removing the now-unnecessary separator key from the parent — which can itself cascade upward and eventually shrink the tree's height.
• In practice, many production engines (InnoDB included) are somewhat lazy about merging on delete to avoid thrashing (repeated split/merge on alternating insert/delete near a boundary) — leaving pages under-full temporarily and relying on background/maintenance processes or later inserts to reclaim space.

Deadlock Detection via Wait-For Graphs Advanced

A wait-for graph has one node per active transaction; a directed edge Ti → Tj means Ti is waiting for a lock currently held by Tj. The database periodically (or on every new wait) checks this graph for a cycle — a cycle means deadlock (T1 waits for T2, which waits for T3, which waits for T1).

When a cycle is found, the DBMS picks a victim transaction to abort and roll back (releasing its locks so the others can proceed) — typically chosen by some heuristic: youngest transaction, transaction that's done the least work so far, or the one holding the fewest locks, to minimize wasted work.

MySQL InnoDB and PostgreSQL both use this approach in practice — InnoDB checks for cycles continuously as locks are requested; PostgreSQL runs deadlock detection on a timeout (checking only after a lock wait exceeds deadlock_timeout, default 1 second) to avoid the overhead of checking on every single lock wait.

Replication Lag & Read-Your-Writes Consistency Advanced

In leader-follower replication, followers apply the leader's write stream asynchronously — there's always some lag between "write committed on leader" and "write visible on follower." If an application reads from a follower right after writing to the leader, it may not see its own write yet — a jarring UX bug ("I just posted a comment and it disappeared!").

Read-your-writes consistency is a guarantee that a user always sees their own prior writes, even under asynchronous replication. Common techniques to achieve it:

• Route reads that follow a recent write by the same user to the leader (or a replica known to have caught up) for some time window.
• Track a version/timestamp with each write; when reading, only read from a replica whose replicated position is ≥ that version, waiting/retrying otherwise.
• Sticky sessions: pin a given user's session to one specific replica so they see a monotonically advancing view (solves monotonic-reads more directly, helps read-your-writes too if that replica is caught up).

MVCC Garbage Collection — PostgreSQL VACUUM Advanced

Because PostgreSQL's MVCC never overwrites a row in place on UPDATE/DELETE — it just marks the old version's xmax and inserts a new version — dead row versions accumulate over time ("bloat"). VACUUM is the background process that reclaims this space:

• Scans table pages for row versions no longer visible to any active transaction's snapshot (i.e., no ongoing transaction could still legitimately need to see that old version).
• Marks that space as reusable by future inserts/updates on the same page (plain VACUUM does not shrink the file on disk — it just makes space available for reuse; VACUUM FULL actually rewrites and shrinks the table, but takes an exclusive lock).
• Also updates the visibility map (helping index-only scans skip pages known to have no dead rows) and feeds the query planner's statistics (ANALYZE, often run together as VACUUM ANALYZE or via autovacuum).
• A long-running transaction can block VACUUM's progress by holding an old snapshot that "needs" old row versions to remain — this is the classic cause of severe table bloat in production incidents ("a transaction was left open for 3 days and now the table is 10x its normal size").

MySQL InnoDB has an analogous concept — the purge thread, which cleans up the undo log/rollback segment once no active transaction needs those old versions anymore, and a long-open transaction similarly blocks purge and grows the undo log.

Query Planner Statistics & Stale Stats Advanced

Cost-based optimizers rely on statistics — row counts, most-common-value lists, histograms of value distribution, null fraction, average row width — to estimate how many rows a predicate will match (selectivity) and thus which plan is cheapest.

• These statistics are snapshots, refreshed periodically (ANALYZE in Postgres, often via autovacuum's analyze component; ANALYZE TABLE in MySQL) — not updated on every single write.
• If actual data distribution has drifted significantly since the last stats refresh (e.g., a table grew from 1,000 to 10,000,000 rows, or a column that used to have 5 distinct values now has 500,000), the optimizer's row-count estimates can be wildly wrong.
• Bad estimates cause bad plan choices: e.g., the optimizer might pick a nested loop join expecting 10 rows on one side, when there are actually 10 million — turning what should be a hash join into a catastrophically slow query.
• This is a real, common production incident pattern: "the query was fast for months, then suddenly became slow after a big data load" — usually traced back to stale statistics (fix: manually run ANALYZE/ANALYZE TABLE after bulk loads) or a parameter-sniffing issue where a cached plan was optimized for atypical input values.

13. Practical SQL Coding

Sample schema used across this section:

CREATE TABLE Employee (
    emp_id     INT PRIMARY KEY,
    name       VARCHAR(100) NOT NULL,
    dept_id    INT,
    manager_id INT,
    salary     NUMERIC(10, 2) NOT NULL,
    hire_date  DATE NOT NULL,
    FOREIGN KEY (manager_id) REFERENCES Employee(emp_id)
);

INSERT INTO Employee (emp_id, name, dept_id, manager_id, salary, hire_date) VALUES
(1, 'Asha',  10, NULL, 95000, '2019-01-15'),
(2, 'Ravi',  10, 1,    72000, '2020-03-10'),
(3, 'Meera', 20, 1,    88000, '2021-07-01'),
(4, 'Karan', 20, 3,    91000, '2018-11-20'),
(5, 'Neha',  10, 1,    72000, '2022-05-05');

Nth Highest Salary Intermediate

-- Approach 1: DISTINCT + LIMIT/OFFSET (correctly handles ties)
SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
LIMIT 1 OFFSET 2;  -- N = 3, offset = N - 1

-- Approach 2: DENSE_RANK window function (most robust, handles ties cleanly)
SELECT salary FROM (
    SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
    FROM Employee
) ranked
WHERE rnk = 3;

-- Approach 3: correlated subquery (works everywhere, but O(n^2) without index)
SELECT DISTINCT salary
FROM Employee e1
WHERE 2 = (
    SELECT COUNT(DISTINCT salary)
    FROM Employee e2
    WHERE e2.salary > e1.salary
);  -- N = 3, count of strictly-greater distinct salaries = N - 1 = 2

-- Approach 4: standard SQL OFFSET/FETCH syntax
SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
OFFSET 2 ROWS FETCH NEXT 1 ROWS ONLY;

Find Duplicate Rows Basic

-- Find employees who share the exact same (name, salary) combination
SELECT name, salary, COUNT(*) AS occurrences
FROM Employee
GROUP BY name, salary
HAVING COUNT(*) > 1;

-- Return the actual duplicate rows (not just the grouped summary)
SELECT e.*
FROM Employee e
JOIN (
    SELECT name, salary
    FROM Employee
    GROUP BY name, salary
    HAVING COUNT(*) > 1
) dup ON e.name = dup.name AND e.salary = dup.salary;

-- Delete duplicates, keeping only the row with the smallest emp_id per group
DELETE FROM Employee e1
USING Employee e2
WHERE e1.emp_id > e2.emp_id
  AND e1.name = e2.name
  AND e1.salary = e2.salary;

Running Total with Window Function Intermediate

SELECT
    emp_id,
    name,
    hire_date,
    salary,
    SUM(salary) OVER (
        ORDER BY hire_date
        ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS running_total_salary
FROM Employee
ORDER BY hire_date;

-- Running total PER DEPARTMENT (partitioned window)
SELECT
    emp_id,
    name,
    dept_id,
    hire_date,
    salary,
    SUM(salary) OVER (
        PARTITION BY dept_id
        ORDER BY hire_date
        ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS dept_running_total
FROM Employee
ORDER BY dept_id, hire_date;

Employees Earning More Than Their Manager Intermediate

-- Self join: compare each employee's salary to their manager's salary
SELECT
    e.name   AS employee_name,
    e.salary AS employee_salary,
    m.name   AS manager_name,
    m.salary AS manager_salary
FROM Employee e
JOIN Employee m ON e.manager_id = m.emp_id
WHERE e.salary > m.salary;

-- Result with the sample data above:
-- Meera (88000) vs manager Asha (95000)  -> not included
-- Neha  (72000) vs manager Asha (95000)  -> not included
-- Karan (91000) vs manager Meera (88000) -> INCLUDED (91000 > 88000)

References & Further Reading

• PostgreSQL Official Documentation
• Use The Index, Luke! — SQL indexing and tuning guide
• GeeksforGeeks — DBMS Tutorials
• Database Internals (Alex Petrov) — deep dive into storage engines and distributed data systems
• MySQL 8.0 Reference Manual — The InnoDB Storage Engine
• PostgreSQL Docs — Concurrency Control (MVCC)
• PostgreSQL Docs — Routine Vacuuming
• ARIES Recovery Algorithm — Overview
• Martin Kleppmann — author of "Designing Data-Intensive Applications" (distributed systems, consistency models)
• W3Schools SQL Reference