Transaction Management, Concurrency Control, and Indexing Structures

This chapter covers foundational Database Management System (DBMS) architecture, focusing on Transaction Control Language (TCL), ACID properties, concurrency control mechanisms, performance optimization via indexing structures, and data organization models.

1. Transaction Control Language (TCL) and Rollback Mechanics

Why Do We Need This?

When building mission-critical software (such as banking platforms), operations often span multiple database tables. If an unexpected crash occurs halfway through an execution block, leaving some tables updated and others untouched, the database enters a corrupted or inconsistent state.

Core Mental Model

Think of a database transaction like a bank ATM cash withdrawal workflow:

• The system must deduct funds from your account.
• The system must dispense physical cash.
• If the machine jams after deducting your balance but before dispensing the cash, the transaction cannot simply stop halfway. It must entirely undo (roll back) the deduction so you do not lose your money.

How TCL Solves It

Transaction Control Language (TCL) ensures that a group of queries execute as a single atomic unit. Either all queries succeed, or the entire transaction rolls back to its initial state.

2. SQL Constraints: Enforcing Data Integrity

Constraints are rules enforced on data columns in a table to ensure accuracy, reliability, and validity.

Key Constraint Types

• Primary Key (PRIMARY KEY): Uniquely identifies each record in a table (e.g., student_id). It cannot contain NULL values and must be unique.
• Foreign Key (FOREIGN KEY): Establishes a link between data in two tables by referencing the Primary Key of another table, enabling relational joins.
• Unique (UNIQUE): Ensures all values in a column are distinct (e.g., email addresses, mobile numbers).
• Not Null (NOT NULL): Enforces that a column cannot accept empty or NULL values.
• Check (CHECK): Validates data against a specific logical condition (e.g., CHECK (age >= 18)).
• Default (DEFAULT): Provides a fallback value if no explicit value is supplied during an insert operation (e.g., status defaults to 'active').

3. Database Normalization: Eliminating Redundancy

Normalization is the systematic approach of organizing data in a relational database to minimize data redundancy (duplication) and prevent data anomalies.

Why Do We Need Normalization?

Unnormalized tables suffer from three primary anomalies:

1. Update Anomaly: If a student named Rahul changes his phone number and his records exist in multiple rows, you must update every single row manually. Missing even one row creates conflicting data.
2. Insertion Anomaly: You cannot add a new product category without artificially creating a fake order entry to satisfy table schema requirements.
3. Deletion Anomaly: Deleting a specific order record might accidentally wipe out core product catalog information if stored in the same row.

4. The Normalization Forms (1NF to 4NF)

Note on Functional Dependency: A functional dependency ($X \rightarrow Y$) means the value of attribute $X$ uniquely determines the value of attribute $Y$. If two rows share the same $X$ value, they must share the same $Y$ value.

5. Transactions and ACID Properties

A transaction is a logical unit of work consisting of multiple database operations. To guarantee data safety, enterprise database engines adhere to the ACID properties:

• Atomicity: Treats the transaction as an indivisible unit. If a failure occurs midway, all changes are rolled back.
• Consistency: Ensures the database transitions from one valid state to another, respecting all predefined rules (e.g., an account balance can never drop below zero if constrained).
• Isolation: Guarantees that concurrent transactions execute independently without interference, preventing intermediate dirty states from being exposed.
• Durability: Once a transaction is committed, its changes are permanent, even if the database crashes immediately afterward (managed via write-ahead logging and replication).

Transaction Lifecycle States

6. Concurrency Control and Problems

When multiple users execute transactions simultaneously (concurrent execution), improper isolation leads to severe data anomalies.

Common Concurrency Problems

• Dirty Read: Transaction $A$ updates a value but hasn't committed yet. Transaction $B$ reads this uncommitted value. If Transaction $A$ rolls back, Transaction $B$ is left operating on invalid data.
• Unrepeatable Read: Transaction $A$ reads a value. Transaction $B$ updates or deletes that value and commits. When Transaction $A$ reads the same value again, it gets a different result.
• Lost Updates: Two transactions read the same data simultaneously and overwrite each other's changes, causing one update to be lost.

Concurrency Control Strategies

1. Lock-Based Protocols:
   • Shared Lock ($S$): Allows a transaction to read a data item. Multiple transactions can hold shared locks simultaneously.
   • Exclusive Lock ($X$): Required for writing (updating/deleting) data. While an exclusive lock is active, no other transaction can read or write that item.
2. Two-Phase Locking (2PL):
   • Growing Phase: Transactions may acquire locks but cannot release any.
   • Shrinking Phase: Transactions may release locks but cannot acquire any new ones.
   • The point where the final lock is acquired is known as the Lock Point.
3. Deadlocks:
   • Occurs when two or more transactions wait indefinitely for locks held by each other (Circular Dependency).
   • Resolution: Mechanisms like Wait-Die or Wound-Wait time-stamp transactions and abort/restart them if wait thresholds are exceeded.

7. Indexing Structures and Performance Optimization

Why Do We Need Indexing?

Scanning a table with 10 million rows row-by-row (Full Table Scan) is computationally expensive and slow ($O(N)$ time complexity). Indexing creates a specialized lookup structure—similar to an index at the back of a textbook or a dictionary guide—to locate data instantly.

Types of Indexes

• Primary Index: Built on the primary key column (usually clustered).
• Secondary Index: Built on non-primary columns (e.g., name, email) pointing back to the data records.
• Clustered Index: Determines the physical storage order of data rows on disk (only one clustered index per table).
• Non-Clustered Index: Maintains a separate logical structure containing pointers to the physical data rows.
• Composite Index: An index created on multiple columns combined.

Index Creation Syntax (SQL)

CREATE INDEX idx_student_name 
ON students(student_name);

Internal Data Structures: B-Trees vs. Hash Indexes

• B-Tree Index:
  • Self-balancing tree structure where every leaf node is at the same depth.
  • Operates in $O(\log N)$ time complexity.
  • Highly efficient for range queries (e.g., WHERE age BETWEEN 20 AND 30).
• Hash Index:
  • Uses a hash function to map keys directly to disk storage addresses.
  • Extremely fast for exact-match lookups ($O(1)$ time complexity), but useless for range-based queries.

Summary and Key Takeaways

• TCL & Rollback: Transaction Control Language commands (like rollback) ensure multi-query workflows execute atomically in banking and enterprise apps.
• Constraints: Rules such as Primary Key, Foreign Key, Unique, Not Null, and Check protect relational data integrity.
• Normalization: Eliminates data redundancy and anomalies (Update, Insertion, Deletion) by structuring data through 1NF, 2NF, 3NF, and BCNF.
• ACID Properties: Atomicity, Consistency, Isolation, and Durability form the bedrock of reliable transaction processing.
• Concurrency Hazards: Uncontrolled concurrent execution leads to dirty reads, unrepeatable reads, and lost updates.
• Locking & 2PL: Shared and Exclusive locks managed via Two-Phase Locking regulate access and prevent data corruption.
• Deadlocks: Circular lock dependencies require timeouts or timestamp policies (Wait-Die) for automated recovery.
• Indexing Architecture: B-Trees accelerate read operations from $O(N)$ linear scans to $O(\log N)$ logarithmic lookups.
• Clustered vs. Non-Clustered: Clustered indexes dictate physical table storage order; non-clustered indexes maintain pointers to record locations.