Database Management Systems

DBMS = Software that manages, stores, retrieves, and controls access to data in a database.

Key Functions:

• Data Storage – Stores large volumes of structured data
• Data Retrieval – Queries using SQL
• Data Security – Access control & permissions
• Data Integrity – Constraints ensure valid data
• Concurrency – Multiple users simultaneously
• Recovery – Restores data after failures

Simple Analogy: DBMS is to databases what an OS is to files on a computer.

DBMS Evolution Timeline:

E.F. Codd (IBM, 1970) — father of relational model

File System vs DBMS Comparison:

Conclusion: DBMS solves ALL file system problems systematically.

Major Advantages of DBMS:

1. Reduced Data Redundancy

Normalization eliminates duplicate storage.

2. Data Consistency

One update reflects everywhere.

3. Data Security

Role-based access control (RBAC).

4. Data Integrity

Constraints enforce valid data:

CREATE TABLE students (
  age INT CHECK (age >= 18)
);

5. Backup & Recovery

Automatic transaction logs.

6. Data Independence

Change storage without changing app code.

3-Schema (ANSI/SPARC) Architecture:

┌─────────────────────────────┐
│   EXTERNAL LEVEL (Views)    │  ← User 1, User 2
│   (What users SEE)          │
├─────────────────────────────┤
│   CONCEPTUAL LEVEL          │  ← Logical design
│   (What data EXISTS)        │
├─────────────────────────────┤
│   INTERNAL LEVEL            │  ← Physical storage
│   (How data is STORED)      │
└─────────────────────────────┘

Data Independence:

• Logical Independence – Change conceptual without changing external.
• Physical Independence – Change internal without changing conceptual.

Benefit: Applications don't break when database structure changes.

DBMS Internal Architecture:

Query Processing Layer:

• Parser – Checks SQL syntax.
• Query Optimizer – Finds best execution plan.
• Query Executor – Runs the optimized plan.

Storage Layer:

• Storage Manager – Manages disk ↔ memory.
• Buffer Manager – Caches pages in RAM.
• File Manager – Physical file organization.

Transaction Layer:

• Transaction Manager – ACID properties.
• Lock Manager – Concurrency control.
• Recovery Manager – Crash recovery.

Flow: SQL → Parser → Optimizer → Executor → Storage

ER Model = A conceptual data model for designing databases.

3 Main Components:

1. Entity (Rectangle □)

• A real-world object (Student, Course, Employee).

2. Attribute (Ellipse ○)

• Property of an entity.

3. Relationship (Diamond ◇)

• Association between entities.
• Example: Student enrolls in Course.

ER Diagram Example:

[Student] ---enrolls_in--- [Course]
    |                          |
 (S_ID, Name)           (C_ID, Credits)

Purpose: Blueprint before creating actual tables.

Types of Attributes:

1. Simple (Atomic)

Cannot be divided (Age, Roll Number).

2. Composite

Can be split (Name = FirstName + LastName).

3. Derived

Calculated from another attribute (dashed ellipse).

→ Age derived from Date_of_Birth.

4. Multivalued

Can have multiple values (double ellipse).

→ Phone_Numbers (one person, many phones).

5. Key Attribute

Uniquely identifies entity (underlined).

→ Student_ID.

Key Constraints (Cardinality Ratios):

Participation Constraints:

• Total Participation (double line ═)

Every entity MUST participate.

→ "Every employee MUST work in a department"

• Partial Participation (single line —)

Some entities may not participate.

→ "Some employees MAY manage a department"

Weak Entity:

• Cannot be uniquely identified by its own attributes alone.
• Depends on a Strong (Owner) Entity.
• Shown with double rectangle ▣.
• Has a Partial Key (dashed underline).

Example: [Employee] ══has══ ▣Dependent▣

Class Hierarchies (Generalization/Specialization):

• Generalization – Bottom-up: Combine Car, Truck → Vehicle.
• Specialization – Top-down: Vehicle → Car, Truck.
• Uses ISA triangle in ER diagram.

Disjoint: Entity belongs to ONLY ONE subclass.

Overlapping: Entity can belong to MULTIPLE subclasses.

Binary Relationship (between 2 entities):

[Student] ──enrolls── [Course]

• Most common type (1:1, 1:N, M:N).

Ternary Relationship (between 3 entities):

[Supplier] ─┐
             ├─ supplies ─ [Project]
[Part]    ─┘

• A supplier supplies a part to a project.

Aggregation:

• Treats a relationship-set as a higher-level entity.
• Used when a relationship participates in another relationship.

Example:

([Employee]──works_on──[Project]) ──managed_by── [Manager]

The works_on relationship is aggregated into a unit.

Relational Algebra is the procedural mathematical foundation of databases. It tells the computer how to process the data step-by-step.

1. Selection (σ) – The Row Filter

• Think of it as a Coffee Filter that only lets certain rows drip through.
• σ_age>20(Student) → Gives you only the students older than 20.

2. Projection (π) – The Column Spotlight

• Think of it as a Spotlight that only shines on specific columns, hiding the rest.
• π_name,age(Student) → Gives you a table with just names and ages.

Set Operations:

• Union (∪): Combines rows from two tables (like a merger).
• Set Difference (−): Rows in Table A but NOT in Table B.
• Cartesian Product (×): Multiplies every row of Table A with every row of Table B (massive combination!).

A Join (⋈) is essentially a Cartesian Product followed by a Selection. It combines tables based on matching data.

1. Natural Join (⋈):

Automatically finds columns with the same name in both tables, links them up, and removes duplicate columns.

2. Theta Join (⋈_θ):

A join based on any general condition (like < or >). If the condition is strictly equality (=), it's called an Equi Join.

3. Outer Joins:

What if a row doesn't have a match? Normally, it gets dropped. Outer joins save them!

• LEFT Outer Join: Keeps all rows from the Left table (fills missing Right data with NULLs).
• RIGHT Outer Join: Keeps all rows from the Right table.
• FULL Outer Join: Keeps absolutely everything.

4. Division (÷):

Used for "ALL" queries. e.g., "Find students who have taken ALL the courses offered by the CS department."

While Relational Algebra is procedural (tells you the exact steps), Relational Calculus is Declarative.

Analogy: Relational Calculus is like ordering at a restaurant: "I want a burger." (You just say WHAT you want). Relational Algebra is like giving the chef a recipe: "Toast the bun, grill the patty..." (You say HOW to make it).

1. Tuple Relational Calculus (TRC):

• Variables represent entire Rows (Tuples).
• Formula: {t | t ∈ Student AND t.age > 20}
• "Give me all tuples 't' such that 't' is a student and 't's age is > 20."

2. Domain Relational Calculus (DRC):

• Variables represent individual Columns (Domains).
• Formula: {<n, a> | <n, a> ∈ Student AND a > 20}
• "Give me the name 'n' and age 'a' columns such that the age 'a' is > 20."

Both TRC and DRC have the exact same mathematical power as Relational Algebra!

SQL (Structured Query Language) is how humans talk to relational databases.

Basic Structure:

SELECT column_name     -- 5. What columns to output
FROM table_name        -- 1. Where to get the data
WHERE condition        -- 2. Filter the raw rows
GROUP BY column        -- 3. Organize into buckets
HAVING condition       -- 4. Filter the buckets
ORDER BY column;       -- 6. Sort the final result

The Big Secret (Logical Execution Order):

SQL is not executed top-to-bottom! The database actually reads it in this order:

FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY

This is why you can't use an alias defined in the SELECT clause inside the WHERE clause—the WHERE clause runs first!

SQL commands are grouped into 5 neat categories:

1. DDL (Data Definition Language) - The Architect:

Used to build or destroy structures (tables, schemas).

Examples: CREATE, ALTER, DROP, TRUNCATE (wipes data but keeps the table structure).

2. DML (Data Manipulation Language) - The Data Entry:

Used to modify the actual data rows.

Examples: INSERT, UPDATE, DELETE.

3. DQL (Data Query Language) - The Detective:

Used only to search and view data.

Example: SELECT.

4. DCL (Data Control Language) - The Bouncer:

Manages user permissions and security.

Examples: GRANT (give access), REVOKE (take access away).

5. TCL (Transaction Control Language) - The Save Button:

Manages database transactions.

Examples: COMMIT (save permanently), ROLLBACK (undo).

A Subquery is simply a query placed inside another query.

1. Independent (Standard) Subqueries:

• The inner query runs ONCE, completely independently.
• It passes its final result to the outer query.
• Example: Find employees making more than the company average. (The inner query calculates the company average once).

2. Correlated Subqueries (The Heavy Looper):

• The inner query relies on data from the outer query.
• It runs MULTIPLE TIMES—once for every single row processed by the outer query.
• Analogy: Like a nested for-loop in programming. It is very slow and resource-heavy.
• Example: Find employees making more than the average of their specific department. For every employee checked, the inner query has to recalculate that specific department's average.

Aggregate Functions take many rows and crush them down into a single value.

Examples: COUNT(), SUM(), AVG(), MAX(), MIN().

GROUP BY (The Buckets):

Instead of crushing the entire table into one value, GROUP BY organizes the rows into separate buckets based on a column, and then aggregates each bucket.

Example: SELECT department, AVG(salary) ... GROUP BY department; (Calculates average salary per department bucket).

HAVING (The Bucket Filter):

• WHERE filters individual rows before they go into buckets.
• HAVING filters the buckets after they are grouped.
• Example: HAVING AVG(salary) > 50000; (Only show me the departments where the bucket's average salary is huge).

SQL Triggers are automated event listeners in the database. They are stored procedures that "fire" automatically when a specific event happens to a table.

The Mechanics:

• You attach a trigger to a table for an event like INSERT, UPDATE, or DELETE.
• You can choose whether it fires BEFORE the event or AFTER the event.
• Inside the trigger, you have access to special keywords: OLD (the data before the change) and NEW (the data after the change).

Common Use Cases:

• Audit Logs: Automatically recording who changed a salary and when.
• Complex Validation: Throwing an error if someone tries to withdraw money they don't have.

Databases that heavily rely on triggers to enforce business logic are called Active Databases.

In SQL, NULL is not zero, and it is not an empty string. NULL literally means "Unknown" or "Missing".

Because NULL means Unknown, you cannot use normal math or equals signs with it. 5 = NULL doesn't equal False; it equals Unknown!

This introduces Three-Valued Logic (3VL): TRUE, FALSE, and UNKNOWN.

• TRUE AND UNKNOWN = UNKNOWN
• FALSE AND UNKNOWN = FALSE
• TRUE OR UNKNOWN = TRUE

How to handle NULL properly:

• 1. Never use =: Always use IS NULL or IS NOT NULL in your WHERE clauses.
• 2. Aggregates ignore it: SUM() and AVG() completely skip NULL rows.
• 3. COALESCE: Use the COALESCE(column, 'default') function to automatically replace NULLs with a fallback value (like 0) so your math doesn't break.

Databases are useless if applications can't talk to them. Here is how they connect:

1. Embedded SQL:

Literally typing raw SQL statements directly inside the code of a host language like C or COBOL. The code is pre-compiled to handle the database commands.

2. ODBC (Open Database Connectivity):

Created by Microsoft. It is an API that acts like a universal translator. It allows an application written in any language (C++, Python) to talk to any database (MySQL, Oracle) using standard driver software.

3. JDBC (Java Database Connectivity):

Exactly like ODBC, but specifically designed exclusively for Java. It allows Java applications to open connections, send SQL queries, and process the returned results.

Analogy: ODBC is like a universal travel adapter for power outlets, letting your software plug into any database worldwide.

Schema Refinement is the process of improving database design by breaking down bad, chunky tables into smaller, highly efficient tables to eliminate data redundancy.

If you don't refine your schema, you face Anomalies (glitches in data logic):

1. Insertion Anomaly:

You can't add data because another piece of data is missing.

Example: You can't add a new professor to the database because they haven't been assigned a student yet (if professor and student share the same table).

2. Update Anomaly:

You update data in one place, but forget to update it in the 5 other places it was duplicated. Now the database contradicts itself.

3. Deletion Anomaly:

You delete one piece of data and accidentally destroy completely unrelated data.

Example: Deleting the last student in a course accidentally deletes all record of the course existing.

A Functional Dependency (X → Y) means: "If I know X, I can definitively tell you Y."

Analogy: Student_ID → Name. If I know your Student ID, I definitively know your Name. It is impossible for one Student ID to belong to two different people.

Armstrong's Axioms: The mathematical rules for discovering hidden dependencies.

1. Reflexivity (The Trivial Rule):

If Y is a subset of X, then X → Y.

Example: (Name, Age) → Name.

2. Augmentation (The Addition Rule):

If X → Y, then XZ → YZ. You can add the same attribute to both sides.

3. Transitivity (The Chain Rule):

If X → Y, and Y → Z, then X → Z.

Example: If ID determines Department, and Department determines Building, then ID determines Building.

A table is in 1NF if it follows the golden rule of Atomicity: Every cell must contain exactly one single, indivisible value.

Violations of 1NF:

• Repeating Groups / Arrays: Having a cell like [Math, Physics, Bio].
• Multiple Values: Storing phone numbers as 123-4567, 987-6543 in one cell.

How to fix it:

Flatten the table! If Alice is taking 3 subjects, Alice gets 3 separate rows in the table.

Note: 1NF tables are flat, but they are often terrible because flattening them introduces massive data duplication.

To be in 2NF, a table must first be in 1NF, AND it must have No Partial Dependencies.

What is a Partial Dependency?

It only happens when you have a Composite Primary Key (a primary key made of two or more columns, like StudentID + CourseID).

A partial dependency occurs when a non-key column depends on only part of the primary key, rather than the whole thing.

Example Violation:

Primary Key is (StudentID, CourseID).

Another column is Course_Name.

Course_Name only depends on CourseID, not the StudentID. This is illegal in 2NF!

How to fix it:

Split the table. Take the offending column and the piece of the key it depends on, and put them in their own separate table.

To be in 3NF, a table must be in 2NF, AND it must have No Transitive Dependencies.

What is a Transitive Dependency?

When a non-key column depends on another non-key column. (A → B, and B → C).

Rule of thumb: A non-key attribute must provide a fact about the key, the whole key, and nothing but the key.

Example Violation:

Primary Key: EmployeeID.

Other columns: DepartmentID, DepartmentName.

DepartmentName depends on DepartmentID, which depends on EmployeeID. Because DepartmentName isn't depending directly on the Primary Key, it's transitive.

How to fix it:

Move DepartmentID and DepartmentName into their own 'Departments' table.

BCNF is a stricter, stronger version of 3NF (sometimes called 3.5NF).

The Rule:

For EVERY functional dependency (X → Y), X must be a Superkey.

When does a table pass 3NF but fail BCNF?

This rare edge case only happens when you have overlapping candidate keys. Specifically, when a non-key attribute tries to determine part of a primary key.

Example Violation:

Table: Student, Course, Teacher.

Rule: A student takes a course, a teacher teaches one course, a course has many teachers.

Primary Key: (Student, Course).

Dependency: Teacher → Course.

Since Teacher determines Course, but Teacher is not a superkey, this violates BCNF!

How to fix it:

Split into (Student, Teacher) and (Teacher, Course).

A Transaction is a logical unit of work (like transferring money from Account A to Account B). It must pass the ACID test to guarantee reliability.

1. Atomicity (All or Nothing):

Either the entire transaction completely succeeds, or it completely fails and rolls back. No partial execution.

2. Consistency (Rule Abidance):

The transaction must leave the database in a valid state. If the rule is "Account balance cannot be negative," the transaction cannot violate this rule.

3. Isolation (Do Not Disturb):

When multiple transactions happen at the same time, they must not interfere with each other. It should feel as if they executed one by one sequentially.

4. Durability (Written in Stone):

Once a transaction is committed, it is permanent. Even if someone pulls the plug on the server 2 seconds later, the data is safe on the disk.

A transaction moves through a specific lifecycle (State Machine):

1. Active: The initial state. The transaction is currently executing its Read/Write operations.

2. Partially Committed: The last operation has executed, but the changes are still in RAM. They haven't been permanently written to the disk yet.

3. Failed: Something went wrong (a hardware crash, a rule violation, or a user cancellation) during the Active or Partially Committed state.

4. Aborted: The system has successfully "rolled back" the failed transaction, undoing all its temporary changes to keep the database clean.

5. Committed: The changes have been safely written to permanent storage. The transaction is complete and cannot be undone.

What is a Schedule?

When multiple transactions run simultaneously, the CPU interleaves their Read (R) and Write (W) operations. The exact chronological sequence of these operations is called a Schedule.

The Problem:

Interleaving operations can cause data corruption (like two people trying to book the last airplane ticket at the exact same millisecond).

The Solution: Serializability

A schedule is Serializable if its interleaved execution yields the exact same final result as if the transactions were executed one after the other in strict sequence (Serially).

If a schedule is serializable, it is guaranteed to be safe and mathematically correct.

These are the two ways to prove if a concurrent schedule is safe.

1. Conflict Serializability:

We look for "Conflicts" — operations from two different transactions on the same data item, where at least one is a Write (e.g., Read-Write, Write-Read, Write-Write).

• We draw a Precedence Graph.
• If the graph has NO LOOPS (cycles), the schedule is Conflict Serializable (and completely safe).

2. View Serializability:

A slightly weaker, more mathematical check.

• If two schedules have the same initial reads, same intermediate reads, and the same final writes, they are "View Equivalent."
• If a schedule is View Equivalent to a Serial schedule, it is View Serializable.

Note: All Conflict Serializable schedules are View Serializable, but not all View Serializable schedules are Conflict Serializable (due to "Blind Writes").

These deal with what happens when a transaction fails in the middle of a schedule.

Recoverable Schedule:

If Transaction T2 reads a value that was written by Transaction T1, then T1 must commit BEFORE T2 commits.

Why? If T1 fails and rolls back, but T2 has already committed, T2 committed based on "dirty" data! This breaks durability.

Cascadeless Schedule:

A stricter version of recoverable.

If Transaction T1 writes a value, no other transaction is even allowed to read that value until T1 fully commits.

Why? If T1 fails, every transaction that read T1's dirty data must also be rolled back. If they were read by other transactions, it causes a domino effect (a Cascading Rollback), which crashes system performance. Cascadeless prevents the domino effect entirely.

Concurrency Control is the traffic light system of the database. It prevents multiple transactions from crashing into each other when reading/writing the exact same data simultaneously.

The Lock Mechanism:

To edit data, a transaction must first "lock" it, just like locking the door to a public restroom. Nobody else can enter until you unlock it.

Two Types of Locks:

• 1. Shared Lock (S-Lock): Used for READING.

Analogy: Reading a bulletin board. Many people can read it at the same time, but nobody is allowed to staple a new paper over it while people are reading.

• 2. Exclusive Lock (X-Lock): Used for WRITING/UPDATING.

Analogy: Writing in a diary. Only one person can hold the pen. If someone has the X-lock, NO ONE else can read or write until they are finished.

Two-Phase Locking (2PL) is the golden rule for guaranteeing Serializability (safety) when using locks.

It forces a transaction to go through two distinct phases:

1. Growing Phase:

The transaction aggressively acquires all the locks it needs (S-locks and X-locks).

CRITICAL RULE: During this phase, it can ONLY acquire locks. It is never allowed to release a lock.

2. Shrinking Phase:

Once the transaction releases its very first lock, it enters the Shrinking Phase.

CRITICAL RULE: During this phase, it can ONLY release locks. It is never allowed to acquire any new locks.

Why it works: By forcing the transaction to grab all its locks before letting any go, we mathematically eliminate the chance of data corruption. However, 2PL does NOT prevent deadlocks.

Instead of using messy locks, this protocol uses Time to keep order.

When a transaction enters the system, it is stamped with the exact system time (e.g., T1 = 10:00AM, T2 = 10:05AM).

The Rule of Age: Older transactions always get priority over younger transactions.

Every piece of data in the database has two secret labels:

• Read Timestamp (R-TS): The time the data was last read.
• Write Timestamp (W-TS): The time the data was last written.

How it works (Thomas Write Rule):

If Young T2 tries to overwrite data that Old T1 is currently reading, that's fine. But if Old T1 tries to overwrite data that Young T2 has already written, the system rejects it! T1 is "too late" to the party, so T1 is killed, rolled back, and restarted with a brand new timestamp.

Deadlock is a Mexican Standoff.

• Transaction A has a lock on Data 1, and is waiting for Data 2.
• Transaction B has a lock on Data 2, and is waiting for Data 1.

Both will wait forever. The system freezes.

Handling Methods:

1. Deadlock Prevention:

Stop the standoff before it happens. Use Timestamp protocols like:

• Wait-Die: If an old transaction wants a lock held by a young one, it waits. If a young transaction wants a lock held by an old one, the young one dies (rolls back).
• Wound-Wait: Older transactions ruthlessly "wound" (kill) younger ones holding the lock.

2. Deadlock Detection & Recovery:

Let the deadlock happen. Periodically, the database draws a Wait-For Graph (a map of who is waiting for who). If it detects a circle (a cycle), it ruthlessly assassinates one of the transactions to break the loop.

Types of DBMS Failures:

1. Transaction Failure

• Logical errors (bad input, rule violation)
• Internal errors (deadlock, killed by system)

2. System Crash

• Hardware failure (RAM dies, CPU faults)
• OS crash, power failure
• Note: Disk remains intact.

3. Disk Failure

• Hard drive crash, bad sectors, data corruption
• Most severe failure type

Goal of Recovery: To restore the database to the most recent consistent state before the failure, ensuring ACID properties (Atomicity & Durability).

Log-Based Recovery:

The DBMS keeps a highly secure journal called a Log File on the disk. Every single change made to the database is recorded here before the actual database is modified.

Write-Ahead Logging (WAL) Protocol:

• 1. A log record must be written to disk BEFORE the actual data page is updated on disk.
• 2. All log records for a transaction must be written to disk BEFORE the transaction can COMMIT.

Log Record Contents:

[Transaction_ID, Data_Item, Old_Value, New_Value]

This ensures that if the system crashes, we can look at the log to either UNDO (rollback) incomplete transactions or REDO (reapply) committed ones.

Checkpoints are save states for the database.

Without checkpoints, if the system crashes, the recovery manager would have to scan the log file from the very beginning of time. This takes too long.

How Checkpoints Work:

• 1. Periodically, the DBMS stops accepting new transactions temporarily.
• 2. It forces all modified buffers (dirty pages) in RAM to be written to the disk.
• 3. It writes a [checkpoint] record to the log.
• 4. It resumes normal operation.

During Recovery:

The system only needs to scan the log backwards until it hits the last checkpoint. It ignores any transaction that finished before the checkpoint, massively speeding up recovery time.

Shadow Paging is a recovery technique that doesn't use a log file for UNDO/REDO.

How it works:

• The database maintains two page tables: the Current Page Table and the Shadow Page Table.
• When a transaction starts, the Shadow table is saved to disk and untouched.
• The transaction makes all its changes using the Current table.

Outcome:

• If it Commits: The Current table becomes the permanent table, and the old Shadow table is deleted.
• If it Fails/Crashes: The system simply throws away the Current table and points back to the untouched Shadow table. Instant rollback!

Pros: Very fast recovery, no UNDO/REDO needed.

Cons: Causes data fragmentation, expensive to copy page tables.

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the industry standard recovery algorithm used in IBM DB2, SQL Server, etc.

Key Principles:

• Uses Write-Ahead Logging (WAL).
• Uses Log Sequence Numbers (LSN) to track exactly which log record applies to which data page.

The 3 Phases of ARIES Recovery:

• 1. Analysis Phase: Scans the log forward from the last checkpoint to figure out exactly which transactions were active at the time of the crash, and which pages were dirty.
• 2. REDO Phase: Scans forward, reapplying ALL updates (even for uncommitted transactions) to bring the database exactly back to the state it was in at the crash moment.
• 3. UNDO Phase: Scans backward, undoing the effects of all transactions that were active (but not committed) at the time of the crash.