W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

DBMS Core Concepts

Architectural Deep Dive into Transactions, Normalization, Indexing & Storage

DBMS Theory: Comprehensive guide covering Database Internals, ACID Integrity, B+ Tree Indexing, Normalization, and Relational Algebra.

Database Management Systems (DBMS)

System Architecture & Data Abstraction

A Database Management System (DBMS) is specialized software designed to define, store, manage, and query structured data securely. It serves as an abstraction layer between application software and raw storage disks.

Key Architectural Components:

Storage Engine: Manages physical page allocation on disk (e.g., InnoDB, WiredTiger).
Query Processor / Optimizer: Parses SQL statements, builds Abstract Syntax Trees (AST), and selects the lowest-cost execution plan.
Transaction & Lock Manager: Manages concurrency locks (Shared / Exclusive) and write-ahead logs (WAL) to preserve consistency.

Database Management Systems (DBMS) — SQL & Structural Example

-- Relational DDL Architecture Example
CREATE DATABASE EnterpriseCore;
USE EnterpriseCore;

CREATE TABLE Users (
    user_id BIGINT PRIMARY KEY AUTO_INCREMENT,
    username VARCHAR(64) NOT NULL UNIQUE,
    email VARCHAR(128) NOT NULL UNIQUE,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
) ENGINE=InnoDB;

DBMS vs Flat File Systems

Why Move Beyond Flat Files?

Storing production data in raw text or CSV files leads to critical architectural flaws as data scales:

Flat File Vulnerabilities:

Data Redundancy & Anomaly: Duplicate entries stored across multiple files create inconsistencies when updates fail mid-way.
No Atomic Guarantee: System crashes during file writes leave partial, corrupted data.
Lack of Concurrency Control: Simultaneous file reads and writes cause race conditions and lost updates.

DBMS Safeguards:

Centralized Integrity: Enforces UNIQUE, FOREIGN KEY, and NOT NULL constraints.
ACID Compliance: Guarantees all-or-nothing transaction execution.

DBMS vs Flat File Systems — SQL & Structural Example

-- Eliminating Anomalies via Foreign Keys
CREATE TABLE Departments (
    dept_id INT PRIMARY KEY,
    dept_name VARCHAR(100) NOT NULL
);

CREATE TABLE Employees (
    emp_id INT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    dept_id INT,
    CONSTRAINT fk_dept FOREIGN KEY (dept_id) REFERENCES Departments(dept_id)
        ON DELETE SET NULL
        ON UPDATE CASCADE
);

ACID Guarantee & Transaction Management

The Bedrock of Data Integrity

Every relational transaction must strictly satisfy the four ACID properties:

1. Atomicity (All-or-Nothing)

Transactions complete entirely or abort cleanly. If a single statement fails, every modification is reversed via undo logs.

2. Consistency (Valid State Invariants)

Data moves from one valid state to another, strictly adhering to schema constraints and domain rules.

3. Isolation (Concurrent Safety)

Concurrent execution of transactions produces the same state as executing them serially.

4. Durability (Crash-Proof Permanence)

Once committed, modifications survive power outages or system crashes by flushing Write-Ahead Logs (WAL) to disk before updating table files.

ACID Guarantee & Transaction Management — SQL & Structural Example

-- Atomic Fund Transfer Transaction
START TRANSACTION;

-- Step 1: Deduct from Source Account
UPDATE Accounts SET balance = balance - 500.00 WHERE account_id = 101 AND balance >= 500.00;

-- Step 2: Add to Destination Account
UPDATE Accounts SET balance = balance + 500.00 WHERE account_id = 202;

-- Verify & Commit
COMMIT; -- Changes permanently flushed via WAL

Keys & Integrity Constraints

Database Key Classification

Keys uniquely identify rows within a table and establish relationships across entities.

Super Key: Any set of attributes that uniquely identifies a row (may contain redundant fields).
Candidate Key: A minimal Super Key with zero unnecessary fields.
Primary Key: The single Candidate Key selected by database architects to uniquely index rows (cannot contain NULLs).
Foreign Key: A column referencing a Primary Key in another table to enforce referential integrity.
Composite Key: A primary key formed by combining two or more columns.

Keys & Integrity Constraints — SQL & Structural Example

CREATE TABLE StudentCourses (
    student_id INT NOT NULL,
    course_id INT NOT NULL,
    enrollment_date DATE,
    -- Composite Primary Key
    PRIMARY KEY (student_id, course_id),
    FOREIGN KEY (student_id) REFERENCES Students(student_id),
    FOREIGN KEY (course_id) REFERENCES Courses(course_id)
);

Database Normalization (1NF to BCNF)

Eliminating Redundancy & Update Anomalies

Normalization structures relational schemas into standard normal forms to remove data duplication:

Normal Forms:

1NF (Atomic Values): Each cell contains a single non-divisible value. No repeating groups or arrays.
2NF (No Partial Dependency): Table must be in 1NF, and every non-key column must depend on the entire composite primary key.
3NF (No Transitive Dependency): Table must be in 2NF, and non-key columns must depend only on the primary key ($X \to Y \to Z$ dependencies removed).
BCNF (Boyce-Codd Normal Form): Every determinant $X$ in a functional dependency $X \to Y$ must be a Super Key.

Database Normalization (1NF to BCNF) — SQL & Structural Example

-- 3NF Normalized Schema Design

CREATE TABLE Instructors (
    instructor_id INT PRIMARY KEY,
    name VARCHAR(100),
    department VARCHAR(50)
);

CREATE TABLE Courses (
    course_id INT PRIMARY KEY,
    course_title VARCHAR(100),
    instructor_id INT,
    FOREIGN KEY (instructor_id) REFERENCES Instructors(instructor_id)
);

ER Diagrams & Schema Conversion

Entity-Relationship Modeling

ER Modeling maps real-world domains into visual structural representations before creating physical tables.

Core Elements:

Entities (Rectangles): Independent objects (e.g., User, Order).
Weak Entities (Double Rectangles): Objects depending on an owner entity for identity (e.g., OrderItem).
Attributes (Ovals): Entity properties (Simple, Composite, Derived, Multi-valued).
Relationships (Diamonds): Associations ($1:1$, $1:N$, $M:N$).

ER Diagrams & Schema Conversion — SQL & Structural Example

-- Mapping Many-to-Many (M:N) Relationship to Junction Table
CREATE TABLE Orders (
    order_id INT PRIMARY KEY,
    order_date TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

CREATE TABLE Products (
    product_id INT PRIMARY KEY,
    title VARCHAR(100),
    price DECIMAL(10,2)
);

-- Junction Table for M:N Relationship
CREATE TABLE OrderLineItems (
    order_id INT,
    product_id INT,
    quantity INT DEFAULT 1,
    PRIMARY KEY (order_id, product_id),
    FOREIGN KEY (order_id) REFERENCES Orders(order_id),
    FOREIGN KEY (product_id) REFERENCES Products(product_id)
);

Concurrency Control & Isolation Levels

Managing Simultaneous Execution

When thousands of transactions execute simultaneously, database isolation prevents concurrency anomalies:

Concurrency Anomalies:

Dirty Read: Reading uncommitted data modified by another concurrent transaction.
Non-Repeatable Read: Re-reading a row yields different values because another transaction committed an update.
Phantom Read: Re-running a range query returns new rows inserted by another committed transaction.

SQL Standard Isolation Levels:

READ UNCOMMITTED (Fastest, permits all anomalies).
READ COMMITTED (Prevents Dirty Reads, default in PostgreSQL/Oracle).
REPEATABLE READ (Prevents Dirty & Non-Repeatable Reads, default in InnoDB).
SERIALIZABLE (Strict lock-based execution, prevents all anomalies).

Concurrency Control & Isolation Levels — SQL & Structural Example

-- Setting Session Isolation Level in MySQL/PostgreSQL
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;

START TRANSACTION;
SELECT SUM(balance) FROM Accounts WHERE region = 'APAC';
-- Guarantee: Re-executing this query inside the transaction yields identical results
COMMIT;

Indexing & B+ Trees

Accelerating Query Performance

An Index is an auxiliary data structure (typically a B+ Tree) that reduces lookups from an $O(N)$ full table scan down to $O(\log N)$ disk reads.

Index Types:

Clustered Index: Physically orders data rows on disk according to the index key (Only 1 per table, usually Primary Key).
Secondary (Non-Clustered) Index: Maintains a separate B+ tree pointing to the physical primary key location.
Composite Index: Indexes multiple columns together (Leftmost prefix rule applies).

Indexing & B+ Trees — SQL & Structural Example

-- Composite Index Creation
CREATE INDEX idx_user_status_date ON Users(status, created_at);

-- Query utilizing the composite index (Leftmost prefix match)
EXPLAIN SELECT * FROM Users WHERE status = 'ACTIVE' AND created_at >= '2026-01-01';

Database Views & Security Proxies

Virtual Tables & Security Layers

A View is a saved SQL query representing a virtual table. Views simplify complex joins and restrict access to sensitive fields.

Types of Views:

Standard View: Evaluates dynamically on every query execution (Zero disk space for data).
Materialized View: Physically caches query results on disk and must be periodically refreshed.

Database Views & Security Proxies — SQL & Structural Example

-- Creating Security View for HR Data
CREATE VIEW PublicEmployeeDirectory AS
SELECT emp_id, first_name, last_name, department, work_email
FROM Employees
WHERE employment_status = 'ACTIVE';

-- Grant access ONLY to the view, hiding salary & SSN fields
GRANT SELECT ON PublicEmployeeDirectory TO auditor_role;

Stored Procedures & Triggers

Database Server-Side Programming

Stored Procedures: Precompiled SQL logic executed on the server, reducing network round-trips for multi-step operations.
Triggers: Automated event handlers triggered automatically BEFORE or AFTER INSERT, UPDATE, or DELETE operations.

Stored Procedures & Triggers — SQL & Structural Example

-- Audit Logging Trigger Example
DELIMITER //
CREATE TRIGGER audit_salary_update
AFTER UPDATE ON Employees
FOR EACH ROW
BEGIN
    IF OLD.salary <> NEW.salary THEN
        INSERT INTO AuditLogs (emp_id, old_salary, new_salary, modified_by)
        VALUES (NEW.emp_id, OLD.salary, NEW.salary, CURRENT_USER());
    END IF;
END //
DELIMITER ;

Relational Algebra & Set Theory

Mathematical Foundation of SQL

Relational Algebra is the procedural mathematical query language underlying SQL optimization engine:

Core Operators:

Selection ($\sigma$): Filters rows meeting a condition (SQL WHERE).
Projection ($\pi$): Selects specific columns (SQL SELECT col1, col2).
Cartesian Product ($\times$): Combines every tuple of table A with table B (SQL CROSS JOIN).
Natural Join ($\bowtie$): Joins tables on common column names (SQL INNER JOIN).

Relational Algebra & Set Theory — SQL & Structural Example

-- Relational Algebra Formula: π(name, salary)(σ(dept = 'CS')(Employees))

-- Equivalent SQL Statement:
SELECT name, salary
FROM Employees
WHERE dept = 'CS';

🎯 Key Interview Concepts — DBMS

ACID Guarantees: Atomicity (Undo Logs), Consistency (Constraints), Isolation (Locks/MVCC), Durability (Write-Ahead Logs).

B+ Tree Advantage: Leaf nodes are linked sequentially, providing fast range scans and logarithmic $O(\\log N)$ equality lookups.

3NF vs BCNF: 3NF allows $X \\to Y$ if $Y$ is a prime attribute; BCNF strictly requires $X$ to be a Super Key.

-- Relational DDL Architecture Example CREATE DATABASE EnterpriseCore; USE EnterpriseCore; CREATE TABLE Users ( user_id BIGINT PRIMARY KEY AUTO_INCREMENT, username VARCHAR(64) NOT NULL UNIQUE, email VARCHAR(128) NOT NULL UNIQUE, created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP ) ENGINE=InnoDB;

-- Eliminating Anomalies via Foreign Keys CREATE TABLE Departments ( dept_id INT PRIMARY KEY, dept_name VARCHAR(100) NOT NULL ); CREATE TABLE Employees ( emp_id INT PRIMARY KEY, name VARCHAR(100) NOT NULL, dept_id INT, CONSTRAINT fk_dept FOREIGN KEY (dept_id) REFERENCES Departments(dept_id) ON DELETE SET NULL ON UPDATE CASCADE );

-- Atomic Fund Transfer Transaction START TRANSACTION; -- Step 1: Deduct from Source Account UPDATE Accounts SET balance = balance - 500.00 WHERE account_id = 101 AND balance >= 500.00; -- Step 2: Add to Destination Account UPDATE Accounts SET balance = balance + 500.00 WHERE account_id = 202; -- Verify & Commit COMMIT; -- Changes permanently flushed via WAL

CREATE TABLE StudentCourses ( student_id INT NOT NULL, course_id INT NOT NULL, enrollment_date DATE, -- Composite Primary Key PRIMARY KEY (student_id, course_id), FOREIGN KEY (student_id) REFERENCES Students(student_id), FOREIGN KEY (course_id) REFERENCES Courses(course_id) );

-- 3NF Normalized Schema Design CREATE TABLE Instructors ( instructor_id INT PRIMARY KEY, name VARCHAR(100), department VARCHAR(50) ); CREATE TABLE Courses ( course_id INT PRIMARY KEY, course_title VARCHAR(100), instructor_id INT, FOREIGN KEY (instructor_id) REFERENCES Instructors(instructor_id) );

-- Mapping Many-to-Many (M:N) Relationship to Junction Table CREATE TABLE Orders ( order_id INT PRIMARY KEY, order_date TIMESTAMP DEFAULT CURRENT_TIMESTAMP ); CREATE TABLE Products ( product_id INT PRIMARY KEY, title VARCHAR(100), price DECIMAL(10,2) ); -- Junction Table for M:N Relationship CREATE TABLE OrderLineItems ( order_id INT, product_id INT, quantity INT DEFAULT 1, PRIMARY KEY (order_id, product_id), FOREIGN KEY (order_id) REFERENCES Orders(order_id), FOREIGN KEY (product_id) REFERENCES Products(product_id) );

Managing Simultaneous Execution

When thousands of transactions execute simultaneously, database isolation prevents concurrency anomalies:

Concurrency Anomalies:

Dirty Read: Reading uncommitted data modified by another concurrent transaction.
Non-Repeatable Read: Re-reading a row yields different values because another transaction committed an update.
Phantom Read: Re-running a range query returns new rows inserted by another committed transaction.

SQL Standard Isolation Levels:

READ UNCOMMITTED (Fastest, permits all anomalies).
READ COMMITTED (Prevents Dirty Reads, default in PostgreSQL/Oracle).
REPEATABLE READ (Prevents Dirty & Non-Repeatable Reads, default in InnoDB).
SERIALIZABLE (Strict lock-based execution, prevents all anomalies).

-- Setting Session Isolation Level in MySQL/PostgreSQL SET TRANSACTION ISOLATION LEVEL REPEATABLE READ; START TRANSACTION; SELECT SUM(balance) FROM Accounts WHERE region = 'APAC'; -- Guarantee: Re-executing this query inside the transaction yields identical results COMMIT;

-- Composite Index Creation CREATE INDEX idx_user_status_date ON Users(status, created_at); -- Query utilizing the composite index (Leftmost prefix match) EXPLAIN SELECT * FROM Users WHERE status = 'ACTIVE' AND created_at >= '2026-01-01';

-- Creating Security View for HR Data CREATE VIEW PublicEmployeeDirectory AS SELECT emp_id, first_name, last_name, department, work_email FROM Employees WHERE employment_status = 'ACTIVE'; -- Grant access ONLY to the view, hiding salary & SSN fields GRANT SELECT ON PublicEmployeeDirectory TO auditor_role;

-- Audit Logging Trigger Example DELIMITER // CREATE TRIGGER audit_salary_update AFTER UPDATE ON Employees FOR EACH ROW BEGIN IF OLD.salary <> NEW.salary THEN INSERT INTO AuditLogs (emp_id, old_salary, new_salary, modified_by) VALUES (NEW.emp_id, OLD.salary, NEW.salary, CURRENT_USER()); END IF; END // DELIMITER ;

🎯 Key Interview Concepts — DBMS

ACID Guarantees: Atomicity (Undo Logs), Consistency (Constraints), Isolation (Locks/MVCC), Durability (Write-Ahead Logs).

B+ Tree Advantage: Leaf nodes are linked sequentially, providing fast range scans and logarithmic $O(\\log N)$ equality lookups.

3NF vs BCNF: 3NF allows $X \\to Y$ if $Y$ is a prime attribute; BCNF strictly requires $X$ to be a Super Key.