Database Management Systems (DBMS) – Complete Notes

SELECT s.name, c.title
FROM Students s
JOIN Enrollments e ON s.id = e.student_id
JOIN Courses c     ON c.id = e.course_id
WHERE s.id = 42;

• Reduced redundancy: Store data once, reference by key.
• Consistency: Single source of truth; integrity constraints.
• Sharing: Multiple users and apps access the same data safely.
• Security: Authentication, authorisation (GRANT/REVOKE), views.
• Backup & recovery: Systematic logging and restoration.
• Concurrency: Transactions allow many users to work safely.
• Data independence: Physical/logical changes do not break apps.
• Query language: SQL makes data access simple and standard.

• Cost: DBMS software/licensing and hardware can be expensive.
• Complexity: Setup, tuning, and administration need skilled staff.
• Overhead: Higher storage and processing than raw files.
• Single point of failure: If the DBMS goes down, all apps suffer.
• Security is critical: Centralised data is a bigger target.
• Scalability challenges: Vertical scaling has limits; distributed setups are complex.

• Self-describing: The DBMS stores metadata (schema) in a system catalogue.
• Insulation between programs and data: Program-data independence.
• Support for multiple views: Different users see different views.
• Multi-user: Concurrent access with integrity.
• Data abstraction: Physical, logical, and view levels.
• Transaction management: ACID properties.

    Users / Applications
    ─────────────────────────────
    External Level  →  Views (View 1, View 2, ...)
    ─────────────────────────────
    Conceptual Level  →  Logical Schema (Tables, Constraints)
    ─────────────────────────────
    Internal Level  →  Physical Schema (Files, Indexes)
    ─────────────────────────────
             Storage / Disk
    ─────────────────────────────

    Mappings:
     External → Conceptual (View mapping)
     Conceptual → Internal (Storage mapping)

1. List five problems of file-based data management and explain how a DBMS solves each.
2. Differentiate between a database and a DBMS with an example.
3. Explain the three-schema architecture with a diagram.
4. Compare any three DBMS types in a short table.
5. Name three DBMSs and one real-world use case for each.

   Client (Web Browser / Mobile App)
             │  HTTP
             ▼
   Application Server (Business Logic)
             │  SQL / Driver
             ▼
   DBMS Server (MySQL / PostgreSQL)
             │  Reads/Writes
             ▼
   Physical Storage (Disks, Files)

A. DBMS Architectures:

B. Data Models:

• Clear responsibility: Each layer enforces specific rules.
• Scalability: App servers and DBMS can scale independently.
• Security: DBMS not directly exposed to the internet.
• Data independence: Change storage without changing apps.
• Reuse: Multiple apps can share the same DBMS.

• Latency: More layers = more hops = slower responses.
• Complexity: More components to configure and monitor.
• Cost: Application servers add infrastructure cost.
• Debugging difficulty: Problems can be in any layer.

• Three-schema architecture: External, conceptual, internal.
• Client-server: DBMS acts as a server; clients request services.
• Modularity: Query processor, storage manager, transaction manager.
• Data independence: Logical and physical.
• Layered communication: Well-defined protocols between layers.

        ┌────────────────────────────────────┐
        │       Query Processor              │
        │  Parser → Optimizer → Executor     │
        └─────────────┬──────────────────────┘
                      │
        ┌─────────────▼──────────────────────┐
        │        Transaction Manager         │
        │  Concurrency Control + Recovery    │
        └─────────────┬──────────────────────┘
                      │
        ┌─────────────▼──────────────────────┐
        │        Storage Manager             │
        │  Buffer Manager + File Manager     │
        └─────────────┬──────────────────────┘
                      │
        ┌─────────────▼──────────────────────┐
        │        Physical Storage            │
        │        (Disks, Files, Indexes)     │
        └────────────────────────────────────┘

1. Explain the difference between 1-tier, 2-tier, and 3-tier DBMS architectures.
2. Draw the ANSI/SPARC three-schema diagram and explain each level.
3. Compare relational and document (NoSQL) data models with examples.
4. List the modules inside a DBMS and describe their roles.
5. Give two real-world examples where 3-tier architecture is essential.

    ┌────────────┐    enrolls     ┌────────────┐
    │  Student   │◄──────────────►│   Course   │
    └────────────┘     (M:N)      └────────────┘
        │  id                          │  code
        │  name                        │  title
        │  dob                         │  credits
                                      ▲
                                      │ teaches (1:N)
                                      │
                              ┌──────────────┐
                              │  Instructor  │
                              └──────────────┘
                                 id, name, dept

A. Concepts in ER Model:

B. Cardinalities:

C. Participation constraints: Total vs partial; existence dependency.

• Visual and intuitive: Non-technical users can validate the design.
• DBMS-independent: Same diagram maps to any relational DBMS.
• Reduces mistakes: Catches missing entities/relationships early.
• Documents business rules: Cardinalities capture real-world rules.
• Direct mapping to tables: Systematic translation to relations.

• Limited for complex data: Handles simple structures better than graph-like ones.
• Large diagrams messy: Big systems need many pages.
• Does not capture timing: Temporal aspects not represented.
• No operations: ER is a static design tool, not a query model.
• Ambiguity in modeling choices: Attribute vs entity decisions vary.

• Conceptual level: Independent of physical storage.
• Entities have identity: Each instance is unique via key.
• Relationships have degree: Unary, binary, ternary.
• Participation: Total or partial.
• Weak entities: Depend on an owner entity.
• Enhanced ER (EER): Adds specialisation, generalisation, aggregation.

    Entity        ┌───────────┐
                  │  Student  │
                  └───────────┘

    Weak Entity   ╔═══════════╗
                  ║ Dependent ║
                  ╚═══════════╝

    Attribute           ( name )

    Key Attribute       ( id )   ← underlined

    Multivalued        (( phones ))

    Derived            ( age )   ← dashed

    Relationship        ◇ enrolls ◇

    Cardinality (1:N)  ─── 1 ───◇─── N ───

1. Draw an ER diagram for a library (Book, Member, Loan).
2. Draw an ER diagram for an online store (Customer, Order, Product).
3. Identify entities, attributes, and relationships for a hospital system.
4. Convert an M:N relationship into a junction table with sample data.
5. Distinguish between weak entity and strong entity with an example.

    Student ( student_id PK, name, email, dept_id FK )
    Department ( dept_id PK, dept_name )
    Enrollment ( student_id FK, course_id FK, grade,
                 PRIMARY KEY (student_id, course_id) )

    Sample row:
    Student(101, 'Amit', 'a@x.com', 3)
      └─ student_id is the primary key
      └─ dept_id refers to Department(dept_id)

A. Types of Keys:

B. Relational Integrity Constraints:

• Simple and mathematical: Based on set theory and first-order logic.
• Standard query language: SQL.
• Data independence: Logical view separated from storage.
• Integrity enforcement: Keys and constraints.
• Optimisable: Query optimisers use relational algebra.
• Mature tooling: Broad ecosystem of tools, ORMs, backups.

• Impedance mismatch: Objects in code vs rows in tables.
• Scaling: Vertical scaling is limited.
• Schema rigidity: Adding columns to huge tables is slow.
• Complex joins: Many-to-many joins can be expensive.
• Not ideal for all data: Graphs, documents, timeseries fit other models better.

• Relations are unordered sets of tuples.
• Attribute order is irrelevant.
• Atomic values: First normal form — no repeating groups.
• Declarative constraints: Keys, CHECK, NOT NULL, UNIQUE.
• Relational algebra: Selection, projection, join, union, etc.

    Department                       Student
    ┌──────────┬──────────────┐      ┌─────────┬────────┬───────────┬──────────┐
    │ dept_id  │ dept_name    │◄─────│ dept_id │  FK    │           │          │
    │ (PK)     │              │      │ student_id (PK)    │  name     │  email   │
    └──────────┴──────────────┘      └─────────┴────────┴───────────┴──────────┘
                                          │
                                          │  FK student_id
                                          ▼
                                     Enrollment
                                     ┌───────────┬───────────┬────────┐
                                     │ student_id│ course_id │ grade  │
                                     │ (PK part) │ (PK part) │        │
                                     └───────────┴───────────┴────────┘

    Legend:
      PK = Primary key
      FK = Foreign key  (enforces referential integrity)

1. Define each key type with an example from a Student table.
2. Write DDL for a Department and Employee tables with PK/FK.
3. Explain referential integrity with an example of a violation.
4. Convert an ER design of Library (Book, Member, Loan) into tables with keys.
5. Show how a composite key is used in an Enrollment table.

    StudentCourse(student_id, name, course_id, course_name, instructor)

    Problem: instructor depends on course, not student.
    Update instructor for a course → many rows must change.

    After 3NF:
    Student(student_id PK, name)
    Course(course_id PK, course_name, instructor)
    Enrollment(student_id FK, course_id FK, PK(student_id, course_id))

• Reduces redundancy: Same fact stored once.
• Prevents anomalies: Insert, update, delete are consistent.
• Improves data integrity: Constraints enforceable.
• Better storage: Smaller tables, better caching.
• Simpler queries: Smaller tables are easier to reason about.

• More tables: Requires more joins.
• Query complexity: Simple business questions need many joins.
• Performance: Many joins can slow reads.
• Over-normalization: Too fine-grained hurts usability.
• Denormalization tradeoff: Sometimes intentionally undone for speed.

• Based on functional dependencies: X → Y.
• Decomposition: Lossless join, dependency preserving.
• Each normal form is stricter: 3NF implies 2NF implies 1NF.
• BCNF sometimes trades dependency preservation for less redundancy.
• Denormalization is a deliberate, measured step for reporting or performance.

    Un-normalised Table
      │
      ▼  (remove repeating groups)
    1NF
      │
      ▼  (remove partial dependency on composite key)
    2NF
      │
      ▼  (remove transitive dependency: non-key → non-key)
    3NF
      │
      ▼  (every determinant is a candidate key)
    BCNF
      │
      ▼  (remove multivalued dependency)
    4NF
      │
      ▼  (remove join dependency)
    5NF

1. Given an un-normalised Sales table, convert it to 1NF, then 2NF, then 3NF.
2. Explain the difference between partial and transitive dependency with an example.
3. Show a relation that is in 3NF but not BCNF.
4. List the anomalies a bad schema can cause with a real example.
5. Describe when you would intentionally denormalize a table.

-- CREATE TABLE
CREATE TABLE Department (
  dept_id    INT PRIMARY KEY,
  dept_name  VARCHAR(50) NOT NULL UNIQUE
);

CREATE TABLE Student (
  student_id  INT PRIMARY KEY,
  name        VARCHAR(100) NOT NULL,
  email       VARCHAR(100) UNIQUE,
  age         INT CHECK (age >= 16),
  dept_id     INT,
  FOREIGN KEY (dept_id) REFERENCES Department(dept_id)
);

-- ALTER TABLE
ALTER TABLE Student ADD COLUMN phone VARCHAR(15);
ALTER TABLE Student MODIFY phone VARCHAR(20);
ALTER TABLE Student DROP COLUMN phone;

-- TRUNCATE vs DROP
TRUNCATE TABLE Student;  -- removes all rows, keeps structure
DROP TABLE Student;      -- removes table and structure

Common column types and constraints:

• Types: INT, VARCHAR, CHAR, TEXT, DATE, TIMESTAMP, DECIMAL, BOOLEAN.
• Constraints: PRIMARY KEY, FOREIGN KEY, UNIQUE, NOT NULL, CHECK, DEFAULT.

• Declarative schema: Easy to describe structure and rules.
• Portable: DDL syntax is similar across DBMSs.
• Enforces integrity: Constraints are enforced by the DBMS.
• Versionable: DDL can be stored in migration scripts.
• Fast: TRUNCATE removes all rows efficiently.

• Auto-commit: DROP, TRUNCATE cannot be rolled back easily.
• Locks: ALTER on huge tables can lock long.
• Vendor differences: Some types and syntax differ.
• Schema rigidity: Changing schema on live data is risky.
• Requires planning: Wrong decisions (types, keys) are costly later.

• Auto-commit: DDL statements commit immediately in most DBMSs.
• Metadata update: DDL updates the system catalogue.
• Locking: Some DDL acquires table-level locks.
• Idempotency: Use IF EXISTS / IF NOT EXISTS for safe scripts.
• Order matters: Drop child tables before parent tables (FK).

    CREATE → table exists (structure defined)
        │
        ▼
    ALTER  → add / change / drop columns and constraints
        │
        ▼
    TRUNCATE → remove all rows (structure remains)
        │
        ▼
    DROP → remove table and structure entirely

    Dependencies:
      Parent (Department)  ← referenced by FK
      Child  (Student)     → must DROP first

1. Write DDL for Department and Student tables with PK/FK.
2. Add a CHECK constraint that age must be between 16 and 100.
3. Alter the Student table to add an enrolled_on DATE column.
4. Demonstrate the difference between TRUNCATE and DROP with the same table.
5. Write a safe migration script using IF NOT EXISTS.

-- INSERT
INSERT INTO Department (dept_id, dept_name)
VALUES (1, 'Computer Science'), (2, 'Mathematics');

INSERT INTO Student (student_id, name, email, age, dept_id)
VALUES (101, 'Amit', 'a@x.com', 20, 1);

-- UPDATE
UPDATE Student
SET age = age + 1
WHERE dept_id = 1;

UPDATE Student
SET email = 'amit.new@x.com'
WHERE student_id = 101;

-- DELETE
DELETE FROM Student WHERE student_id = 101;

-- Transaction (rollback-safe)
BEGIN;
UPDATE Student SET age = 99 WHERE student_id = 101;
ROLLBACK;   -- age will not actually change

• Simple syntax: Easy to learn and read.
• Set-based: One statement can affect many rows.
• Transactional: Can be rolled back before commit.
• Constraints enforced: DBMS prevents bad data.
• Auditing possible: Triggers and change logs.

• Danger of missing WHERE: UPDATE or DELETE without WHERE affects all rows.
• Large transactions: Lock many rows and consume log space.
• Silent rowcount: "0 rows affected" is not an error.
• Referential integrity errors: Delete may fail if FK references exist.
• Bulk inserts: Row-by-row inserts are slow — use bulk forms.

• Transactional: Rollback possible before COMMIT.
• Rowcount returned: Number of affected rows.
• Triggers fire: BEFORE / AFTER triggers run.
• Cascading rules: ON DELETE CASCADE affects child rows.
• Atomic within a statement: Even a multi-row update succeeds or fails as a whole.

    BEGIN
      │
      ▼
    INSERT / UPDATE / DELETE
      │  (changes visible to this session)
      ▼
    More changes …
      │
      ├── COMMIT   → changes permanent, visible to all
      │
      └── ROLLBACK → changes undone

    Referential integrity:

      Parent (Department) ── FK ── Child (Student)
      DELETE parent → fails (or CASCADE deletes child rows
                              depending on FK rule)

1. Insert 5 students into a Student table with varied ages and departments.
2. Update all students in one department to a new department id, inside a transaction.
3. Delete a department and demonstrate the referential integrity error.
4. Demonstrate rollback by updating a row, then rolling back.
5. Write an INSERT ... SELECT to copy rows from one table to another.

-- INNER JOIN with aggregate
SELECT d.dept_name, COUNT(*) AS students
FROM Student s
JOIN Department d ON s.dept_id = d.dept_id
GROUP BY d.dept_name
HAVING COUNT(*) > 5
ORDER BY students DESC;

-- Subquery: students above average age
SELECT name, age
FROM Student
WHERE age > (SELECT AVG(age) FROM Student);

-- LEFT JOIN: departments with no students
SELECT d.dept_name
FROM Department d
LEFT JOIN Student s ON s.dept_id = d.dept_id
WHERE s.student_id IS NULL;

A. Joins:

B. Other DQL concepts:

• Aggregations: COUNT, SUM, AVG, MIN, MAX.
• Subqueries: Scalar, IN, EXISTS, correlated.
• Set operators: UNION, INTERSECT, EXCEPT.
• Window functions: ROW_NUMBER, RANK, SUM() OVER.
• CTEs: WITH clause for readable queries.

• Declarative: Say what you want, not how.
• Powerful: Complex analytics in one query.
• Optimisable: The DBMS chooses efficient plans.
• Portable: Similar syntax across DBMSs.
• Analytic support: Aggregations and window functions.

• Complex queries are hard to read: Deeply nested subqueries.
• Performance pitfalls: Missing indexes cause slow joins.
• NULL semantics: Tri-valued logic surprises beginners.
• Dialect differences: Window functions and LIMIT vary.
• Cartesian products: Missing join conditions blow up results.

• Logical order of execution: FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT.
• NULL handling: = NULL never matches; use IS NULL.
• Deterministic output: Only with ORDER BY.
• Set-based thinking: Operations apply to whole sets of rows.
• Optimiser freedom: Rewrites queries for performance.

    Logical order of execution:

      1. FROM / JOIN         → build the working set
      2. WHERE               → filter rows
      3. GROUP BY            → collapse into groups
      4. HAVING              → filter groups
      5. SELECT              → compute output columns
      6. DISTINCT            → remove duplicates
      7. ORDER BY            → sort
      8. LIMIT / OFFSET      → paginate

    Note: SELECT comes AFTER GROUP BY logically, even
    though we type it near the beginning.

1. List all students with their department names using INNER JOIN.
2. Find departments with zero students using LEFT JOIN.
3. Get the average age per department with GROUP BY and HAVING.
4. Write a subquery that finds students older than the average.
5. Use a CTE and a window function to rank students by age.

• DCL (Data Control Language): statements that manage permissions — GRANT and REVOKE. Roles group privileges for convenience.
• TCL (Transaction Control Language): statements that manage transactions — COMMIT, ROLLBACK, SAVEPOINT, SET TRANSACTION.

-- DCL: grant read-only access to a report user
CREATE ROLE analyst;
GRANT SELECT ON Student TO analyst;
GRANT SELECT ON Department TO analyst;
GRANT analyst TO alice;

-- Later, revoke one privilege
REVOKE SELECT ON Department FROM analyst;

-- TCL: transaction with savepoint
BEGIN;
UPDATE Student SET age = age + 1 WHERE dept_id = 1;
SAVEPOINT after_update;

DELETE FROM Student WHERE student_id = 999;
ROLLBACK TO SAVEPOINT after_update;  -- undo only the delete
COMMIT;                              -- keep the update

A. DCL statements:

B. TCL statements:

• Security: Least-privilege access enforced at the DBMS.
• Roles: Manage many users consistently.
• Safety: Transactions let you undo mistakes.
• Consistency: Multi-statement operations succeed or fail as a unit.
• Fine-grained control: Savepoints allow partial rollback.

• Complexity: Managing roles and grants across many tables.
• Privilege creep: Over time, users accumulate privileges.
• Long transactions: Hold locks and consume log space.
• Deadlocks: Long transactions are more likely to deadlock.
• Dialect differences: Role syntax varies (CREATE USER vs CREATE ROLE).

• Least privilege: Grant only what is needed.
• Granularity: Object-level and column-level grants.
• Auto-commit: DDL and DCL auto-commit; DML does not.
• Atomicity: Transactions are all-or-nothing.
• Isolation levels: READ COMMITTED, REPEATABLE READ, SERIALIZABLE.

    BEGIN
      │
      ▼
    INSERT / UPDATE  ← SAVEPOINT A
      │
      ▼
    DELETE           ← SAVEPOINT B
      │
      ▼
    ROLLBACK TO B    → undo DELETE only
      │
      ▼
    COMMIT           → keep INSERT / UPDATE

    DCL example:

      User alice
         │
         ▼
      GRANT SELECT ON Student → yes
      REVOKE SELECT ON Student → no longer

1. Create a role analyst with SELECT on Student only.
2. Grant the role to a user and revoke it. Observe the effect.
3. Demonstrate COMMIT and ROLLBACK with a simple UPDATE.
4. Use SAVEPOINT to undo only the second of three DML statements.
5. Explain how isolation levels affect concurrent transactions.

• View: A stored query that behaves like a virtual table.
• Index: A data structure (usually B-tree) that speeds up lookups and joins.
• Stored Procedure / Function: Named, precompiled blocks of SQL logic.
• Trigger: Code that fires automatically on INSERT/UPDATE/DELETE.

-- VIEW: hide sensitive columns
CREATE VIEW StudentPublic AS
SELECT student_id, name, dept_id
FROM Student;

-- INDEX: accelerate search by email
CREATE INDEX idx_student_email ON Student(email);

-- STORED PROCEDURE
CREATE PROCEDURE PromoteStudents(IN minAge INT)
BEGIN
  UPDATE Student SET dept_id = 2
  WHERE age >= minAge;
END;

-- TRIGGER: audit updates
CREATE TRIGGER trg_student_audit
AFTER UPDATE ON Student
FOR EACH ROW
INSERT INTO StudentAudit(student_id, changed_at)
VALUES (OLD.student_id, NOW());

A. Views:

• Simple view: One table, no aggregates; usually updatable.
• Complex view: Joins, aggregates, GROUP BY; usually read-only.
• Materialized view: Physically stored; needs refresh; fast reads.

B. Indexes:

C. Stored routines and triggers: Procedures (callable by name), functions (return a value), and triggers (fire on events).

• Views: Security, simplification, abstraction.
• Indexes: Massive speedups for reads and joins.
• Procedures: Reuse, precompilation, encapsulate logic.
• Triggers: Automatic audits, derived columns, integrity rules.
• Central logic: Business rules live in one place.

• Views: Complex views can be slow; updatable views have limits.
• Indexes: Slow down writes and take space.
• Procedures: Vendor-specific syntax; hard to version and test.
• Triggers: Hidden magic; hard to debug; can cascade unexpectedly.
• Over-engineering: Logic scattered between app and DB.

• Views are virtual: They run the underlying query each time (unless materialized).
• Indexes trade write for read: Faster SELECT, slower INSERT/UPDATE.
• Procedures are precompiled: Faster than ad-hoc SQL.
• Triggers run in the same transaction: Rollback undoes their effects.
• Naming conventions: v_, idx_, sp_, trg_ help maintainability.

    Application
        │  SELECT * FROM StudentPublic
        ▼
    ┌──────────────────────┐
    │  View: StudentPublic │  ← virtual table
    └─────────┬────────────┘
              │
              ▼
    ┌──────────────────────┐
    │  Base Table: Student │
    │  Index: idx_email    │  ← speeds lookups
    └──────────────────────┘

    Trigger flow (AFTER UPDATE):

      UPDATE Student …
           │
           ▼
      Trigger trg_student_audit fires
           │
           ▼
      INSERT INTO StudentAudit …

1. Create a view that hides salary from an Employee table.
2. Create an index on Student(email) and compare query plans before/after.
3. Write a stored procedure that raises salaries by a percentage.
4. Write an AFTER UPDATE trigger that logs changes to an audit table.
5. Explain when a materialized view is preferable to a regular view.

BEGIN;
UPDATE Account SET balance = balance - 100 WHERE id = 'A';
UPDATE Account SET balance = balance + 100 WHERE id = 'B';
COMMIT;

If the second UPDATE fails, the first must be undone,
otherwise ₹100 disappears. That's Atomicity.

If another session reads balance in between, it must
not see the intermediate state. That's Isolation.

After COMMIT, even if the system crashes, the new
balances must be recoverable. That's Durability.

The invariant "sum of balances = constant" must
hold before and after. That's Consistency.

A. ACID properties:

B. Transaction states:

C. Isolation levels:

• Reliability: Application can trust the data.
• Concurrency: Many users work simultaneously without corruption.
• Recovery: Crashes do not leave partial work.
• Simpler code: Applications do not need to fix partial writes.
• Correctness under failure: Well-understood guarantees.

• Contention: Stronger isolation = more locking = less concurrency.
• Deadlocks: Concurrent transactions can wait on each other.
• Overhead: Logging and locking consume resources.
• Long transactions: Increase lock contention and log growth.
• Isolation vs speed: Higher isolation levels slow reads.

• Begin / Commit / Rollback: Standard transaction boundaries.
• Savepoints: Partial rollback within a transaction.
• Auto-commit: Default for single statements.
• Anomalies: Dirty read, non-repeatable read, phantom read, lost update.
• MVCC: Many DBMSs use multi-version concurrency control to reduce blocking.

    Active  →  Partially Committed  →  Committed
        │                    │
        │                    │
        ▼                    ▼
      Failed  ──────────►  Aborted

    Anomalies:

      T1:   Read(A)  Write(A)  Commit
      T2:        Read(A)  →  dirty read (if T1 aborts)

      T1: Read(A)              Read(A)
      T2:          Update(A)                 ← non-repeatable

      T1: SELECT … WHERE age < 30
      T2: INSERT age=25  → phantom row seen next time

1. Write a transaction for a bank transfer with proper COMMIT/ROLLBACK.
2. Demonstrate a dirty read under READ UNCOMMITTED and its absence under READ COMMITTED.
3. Explain each ACID property with a real-world example.
4. Draw the state transition diagram for transactions.
5. Compare isolation levels with a table of anomalies.

-- Without locking, Lost Update:
T1: READ A (100)
T2: READ A (100)
T1: WRITE A = 110
T2: WRITE A = 120     ← T1's update lost

-- With 2PL, T2 waits until T1 commits:
T1: LOCK-X A → WRITE A = 110 → UNLOCK
T2:                 LOCK-X A → WRITE A = 120 → UNLOCK
Final A = 120 (correct)

A. Lock modes:

B. Protocols:

C. Anomalies prevented: lost update, dirty read, unrepeatable read, phantom read, write skew.

• Correctness: Ensures serialisable outcomes.
• Concurrency: S-locks let many readers proceed together.
• Choice of protocols: Pessimistic when conflicts common; optimistic when rare.
• MVCC: Readers never block writers and vice versa.
• Predictable: Standardised isolation levels.

• Deadlocks: Circular waits between transactions.
• Starvation: A transaction may wait indefinitely.
• Overhead: Lock manager consumes CPU and memory.
• Reduced parallelism: More locks = less throughput.
• Retry storms: Under OCC, many retries when conflicts spike.

• Serialisability: Gold standard for correctness.
• Two-phase rule: Once you release, you cannot acquire again.
• Deadlock detection: Wait-for graphs, timeouts.
• Deadlock prevention: Timestamp-based wound-wait, wait-die.
• Granularity: Row, page, table, database.

    2PL lifecycle:

      GROWING PHASE            SHRINKING PHASE
      Acquire locks →          → Release locks
      (no releases allowed)    (no new acquires)

    Deadlock cycle:

      T1 holds A, wants B
             │
             ▼
      T2 holds B, wants A
             │
             ▼
      Circular wait → deadlock

    Detection: build wait-for graph; if cycle, abort one T.

1. Show with a diagram how lost update occurs without locking.
2. Explain 2PL and why it guarantees serialisability.
3. Construct a wait-for graph with a deadlock cycle.
4. Compare strict 2PL with MVCC in a short table.
5. Describe two deadlock-prevention schemes (wound-wait, wait-die).

-- WAL rules:
-- 1. Undo entries flushed before any data page is written
-- 2. Redo entries flushed before COMMIT returns

Log records:
  LSN 1:  T1 BEGIN
  LSN 2:  T1 UPDATE A: 100 → 90 (old=100, new=90)
  LSN 3:  T1 UPDATE B: 200 → 210 (old=200, new=210)
  LSN 4:  T1 COMMIT

Crash → Recovery:
  Analysis : find last checkpoint
  Redo     : replay committed changes from log
  Undo     : roll back uncommitted changes

A. Failure types:

B. Log records: BEGIN, UPDATE (with old/new values), COMMIT, ABORT, CLR (compensation log record), CHECKPOINT.

C. Algorithms:

• Durability: Committed data survives crashes.
• Atomicity: Uncommitted work is rolled back.
• Consistency: Database returns to a valid state.
• Incremental: Only since last checkpoint is replayed.
• Industry standard: ARIES widely implemented.

• Log overhead: Every change is written twice (log + data).
• Checkpoint cost: Can pause the system briefly.
• Recovery time: Long transaction = longer undo.
• Complexity: Correct implementation is non-trivial.
• Storage: Logs must be retained for media recovery.

• WAL rule: Log first, then data.
• LSN: Log Sequence Number identifies each record.
• Idempotence: Redo can be applied repeatedly.
• CLR: Undo actions themselves are logged to prevent re-undo.
• Fuzzy checkpoints: Do not require quiescing transactions.

    Crash
      │
      ▼
    1. ANALYSIS
       - Read from last checkpoint
       - Build Dirty Page Table and Transaction Table
      │
      ▼
    2. REDO
       - Replay all updates (even of aborted T)
       - Idempotent, using LSN
      │
      ▼
    3. UNDO
       - Roll back uncommitted transactions
       - Write CLRs so crash during undo is safe

    WAL ordering:

      Log record flushed  ──►  Data page written  ──►  COMMIT returns

1. Write sample WAL records for a bank transfer.
2. Explain the WAL rule and why it is critical.
3. Describe the three passes of ARIES with a diagram.
4. Compare UNDO/REDO, NO-UNDO/REDO, and NO-UNDO/NO-REDO.
5. Explain how a fuzzy checkpoint works.

CREATE INDEX idx_student_email ON Student(email);

Query (uses index):
  SELECT * FROM Student WHERE email = 'a@x.com';
  → O(log n) instead of O(n)

Range query (uses index):
  SELECT * FROM Student WHERE email BETWEEN 'a' AND 'b';

Covering index (no table lookup needed):
  CREATE INDEX idx_dept_name ON Student(dept_id, name);
  SELECT dept_id, name FROM Student WHERE dept_id = 1;

A. Index types:

B. Hash-based structures: static hashing, extendible hashing, linear hashing. Used for in-memory and equality lookups.

• Massive speedups: SELECT, JOIN, ORDER BY, GROUP BY.
• Range scans: B+ trees give sorted order for free.
• Covering indexes: Eliminate table lookups.
• Unique enforcement: Unique indexes back PRIMARY KEY / UNIQUE.
• Flexible: Different indexes for different workloads.

• Write overhead: Every INSERT/UPDATE/DELETE updates indexes too.
• Storage: Indexes can be as large as the table.
• Maintenance: Fragmentation; rebuilds needed over time.
• Planner misuse: The wrong index can slow queries.
• Over-indexing: Too many indexes hurt write throughput.

• B+ trees: Balanced, all leaves at same depth, linked leaves for range scans.
• Clustered vs non-clustered: Clustered index orders the table itself; only one per table.
• Cardinality: Higher cardinality = better index efficiency.
• Selectivity: A highly selective filter is ideal for an index.
• Composite order: Leftmost prefix rule — index(a,b) can help WHERE a=? and WHERE a=? AND b=?, but not WHERE b=? alone.

    B+ Tree (order 3):

              [ 20 | 40 ]
             /     |     \
        [5|10]   [25|35]   [45|60]
        / | \     / | \     / | \
       5 10 15  20 25 35  40 45 60   ← leaves (linked)
       ◄────────────────────────────►  range scan

    Query access paths:

      WHERE id = 42         → index seek (O(log n))
      WHERE id BETWEEN 10 AND 40 → index range scan
      WHERE name LIKE '%a%' → full scan (index unusable)

    Clustered vs non-clustered:

      Clustered:   table rows physically sorted by index key
      Non-clustered: index stores pointers to rows

1. Create a B+ tree index on Student(email) and explain why equality and range queries both benefit.
2. Design a covering index for a report query and show that it eliminates table access.
3. Explain the leftmost prefix rule for composite indexes.
4. Compare clustered and non-clustered indexes with a diagram.
5. List three situations where an index would hurt more than help.

SELECT c.name
FROM Customer c JOIN Orders o ON c.id = o.cust_id
WHERE o.date >= '2025-01-01';

Plan A (bad): full scan Orders, full scan Customer,
              nested loop join
Plan B (good): use index on Orders(date),
               hash join with Customer

View plans in PostgreSQL / MySQL:
  EXPLAIN ANALYZE SELECT ...

A. Join algorithms:

B. Optimization phases:

C. Heuristics: Push selections down; project early; avoid Cartesian products; use indexes when selective; join smaller relations first.

• Performance: Orders of magnitude difference between plans.
• Declarative: Users write what, not how.
• Adaptive: Statistics drive current-data choices.
• Transparent: EXPLAIN lets you inspect and tune.
• Extensible: New algorithms and indexes plug in.

• Statistics drift: Stale stats cause bad plans.
• Cost model imperfect: Correlated columns, skewed data mislead.
• Planning time: Complex queries take milliseconds to plan.
• Hint dependence: Sometimes hints are needed to fix bad plans.
• Parameter sniffing: Plan tuned for one parameter can hurt another.

• Cost-based: Chooses plan with lowest estimated cost.
• Rules + cost: Heuristics narrow the search; cost picks the best.
• Statistics: Row counts, distinct values, histograms, index height.
• Search space pruning: Only promising join orders explored.
• Plan cache: Reuse plans for identical queries.

    SQL text
       │
       ▼
    Parser  →  Parse Tree
       │
       ▼
    Rewriter  →  Logical Plan (relational algebra)
       │
       ▼
    Optimizer
       │  ├── Statistics (table, columns, indexes)
       │  ├── Cost model  (I/O + CPU + network)
       │  ├── Search (join orders, algorithms, access paths)
       │  └── Choose lowest cost plan
       │
       ▼
    Physical Plan
       │
       ▼
    Executor  →  Results

    EXPLAIN output (simplified):

      Hash Join  (cost=… rows=…)
        ├─ Seq Scan on Customer
        └─ Index Scan on Orders (date >= …)

1. Run EXPLAIN on a simple join in your DBMS and identify the join algorithm.
2. Compare plans for the same query with and without an index.
3. Explain predicate pushdown with an example.
4. Describe when a hash join is preferred over a nested loop join.
5. List three reasons the optimizer might choose a bad plan.

-- Document (MongoDB): flexible JSON-like documents
db.users.insertOne({
  name: "Amit",
  emails: ["a@x.com", "amit@y.com"],
  address: { city: "Delhi" }
});

-- Key-Value (Redis):
SET session:123 "user_id=42"
GET session:123

-- Column-family (Cassandra):
CREATE TABLE events (user_id UUID, ts TIMESTAMP,
                     event TEXT, PRIMARY KEY (user_id, ts));

-- Graph (Neo4j):
MATCH (a:Person)-[:FRIEND]->(b:Person)
WHERE a.name = 'Amit' RETURN b.name;

A. NoSQL categories:

B. CAP theorem: Under a network partition, choose either CP (Consistency + Partition tolerance) or AP (Availability + Partition tolerance). You cannot have all three.

C. NewSQL: CockroachDB, Google Spanner, TiDB — SQL + ACID + horizontal scaling.

• Horizontal scalability: Add nodes to handle more load.
• Flexible schema: Add fields without migrations.
• High write throughput: Sharded by design (Cassandra, DynamoDB).
• Specialised queries: Graph traversal, full-text, time series.
• Latency: In-memory (Redis) gives sub-millisecond reads.
• Availability: AP systems stay online during partitions.

• Weaker consistency: Eventual consistency is common.
• Limited query language: No standard SQL (though improving).
• No joins in many stores: Denormalisation required.
• Operational complexity: Distributed systems to manage.
• Ecosystem: Fewer tools compared to RDBMS.
• Eventual consistency surprises: Applications must handle stale reads.

• BASE model: Basically Available, Soft state, Eventual consistency.
• Sharding: Data partitioned by key across nodes.
• Replication: Multiple copies for durability and availability.
• Denormalisation: Precomputed, duplicated data for fast reads.
• Schema-on-read: Structure applied by the application.
• Polyglot persistence: Use different DBs for different jobs.

    CAP Theorem:

        Consistency
             ▲
            ╱ ╲
           ╱   ╲
          ╱ CA  ╲
         ╱  (RDBMS)╲
        ╱            ╲
   CP  ╱──────────────╲  AP
      ╱ MongoDB, Redis ╲ Cassandra,
     ╱  HBase            ╲ DynamoDB
    ▼────────────────────▼
       Partition Tolerance

    Polyglot persistence:

      App → Users      → PostgreSQL (ACID)
          → Sessions   → Redis
          → Catalog    → MongoDB
          → Metrics    → InfluxDB
          → Social     → Neo4j

1. List the four main NoSQL categories with one example each.
2. Explain the CAP theorem with a diagram and examples.
3. Compare MongoDB and PostgreSQL for a product catalog.
4. Describe three workloads where a time-series database is preferable.
5. Design a polyglot persistence architecture for a social app.