Module 3: Storage System in DBMS (Simplified Version)

Storage System in DBMS

A DBMS gives a clear view of stored data, but the data is actually stored as bits and bytes on storage
devices.

Types of Data Storage

Different storage types store data at different speeds and with different access methods:

1. Primary Storage

o Offers fast access but is volatile (data is lost when power is off).

o Main Memory: Handles instructions, stores GBs of data but not the entire database.

o Cache: Very fast, small, expensive memory maintained by computer hardware.

2. Secondary Storage (Online storage)

o Non-volatile: Data stays even after power off or crash.

o Flash Memory: USB drives, often used in servers for frequently used data.

o Magnetic Disk: Hard disks, stores large databases permanently.

3. Tertiary Storage (Offline storage)

o Slower but stores large amounts of data.

o Optical Storage: CDs (700MB), DVDs (4.7–8.5GB).

o Tape Storage: Cheap, used for backup, accesses data sequentially.

Storage Hierarchy

Organized by speed, cost, and reliability:

 Top: Fast and costly (e.g., Cache).

 Bottom: Slow and cheap (e.g., Tapes).

 Above Main Memory: Volatile

 Below Main Memory: Non-volatile

File Organization

 A file is a group of records, accessed using a primary key.

 File organization shows how records are mapped to disk blocks.

 Fixed-length record files are simpler than variable-length ones.

Objectives of File Organization:

 Fast record selection

  Quick and easy insert, delete, update

 No duplicates

 Efficient use of storage

Types of File Organization:

1. Sequential File Organization

o Records are stored one after another.

o Two types:

1. Pile File Method:

 Simple, stores records as inserted.

 Update/Delete: mark the old record, add a new one.

2. Sorted File Method:

 New record added at the end, then the file is sorted by key.

o Pros:

 Good for large data and reports

 Simple, cheap storage

o Cons:

 Slow search

 Sorting takes time and space

2. Heap File Organization

o Basic type, inserts records at the end.

o Records can go in any available block.

o Good for bulk inserts.

o Cons:

 Poor search/update/delete performance

3. Hash File Organization

o Uses a hash function to place records directly.

o Insert/search/update/delete using hash key.

o Records stored randomly.

4. B+ Tree File Organization

o Tree structure based on key index.

o All records in leaf nodes; internal nodes point to leaves.

 o Pros:

 Easy search with one path

 Sorted leaf nodes

 Balanced structure

o Cons:

 Not good for static data

5. ISAM (Indexed Sequential Access Method)

o Index made using primary key

o Fast search using index

o Pros:

 Supports partial/range search

o Cons:

 Needs extra space

 Must rebuild index on insert

6. Cluster File Organization

o Stores related records (from multiple tables) together.

o Useful for frequent joins.

o Types:

 Indexed Clusters: Grouped by cluster key

 Hash Clusters: Uses hash key to group records

o Cons:

 Not good for large databases or changing join conditions

Indexing in DBMS

 Used to speed up data access.

 Index is a data structure built from database columns.

 Two columns:

o Search Key (copy of key)

o Data Reference (pointer to actual data)

Indexing Methods: Indexing in DBMS

Indexing is a crucial technique used in databases to speed up the retrieval of records. Without
indexing, the DBMS would have to scan through every record in a table, which can be very slow
especially with large datasets. Indexes provide a mechanism that makes it much quicker to find
specific records.

How Indexing Works

An index in DBMS is a data structure built on one or more columns of a table. It consists of two
main components:

1. Search Key: This is typically a copy of the column values (like primary or foreign key).

2. Data Reference: This is a pointer or reference that leads to the actual data record.

The index allows you to directly jump to the record associated with the search key, saving time
instead of performing a full table scan.

Types of Indexes

1. Primary Index

 Definition: Created on the primary key column of a table, which ensures that the data is
unique.

 Types of Primary Index:

o Dense Index: An index record is created for every actual data record.

o Sparse Index: An index record is created only for some of the data records.

Advantages:

 It speeds up searches, especially for unique data.

Disadvantages:

 Dense index takes up more space since every record has an index entry.

 Sparse index may be less efficient in some cases.

2. Secondary Index

Secondary Indexing (Made Easy)

Sometimes, a database table is so big that a single-level index is not enough — it becomes too
large to keep in memory.

To solve this, we use two levels of indexing:

🔹 How It Works

1. First Level (Top Index)

o This is a small index with broad ranges (like chapters in a book).

o Example: A range like A–D, E–H, I–L...

 o This small index is kept in main memory (RAM) for fast access.

2. Second Level (Detailed Index)

o Each range in the first index points to a second index with more details.

o Example: A–D may be broken down into A–B, C–D, etc.

o This second index is stored on the hard disk (secondary memory).

3. Data Records

o The second-level index points to the actual data.

📚 Think of it Like a Book:

 First level = Table of contents (Chapters) → Fast to flip

 Second level = Page numbers inside each chapter

 Data = Actual pages

Advantages:

 Useful for queries that don’t involve the primary key.

Disadvantages:

 It adds extra overhead because of the second index level.

 Updates on indexed columns can be slow.

3. Clustering Index

 Definition: A special index where records are grouped together based on a column's value,
typically used when the records are frequently retrieved together.

 Clustering is based on a non-unique key.

 Records that share a common clustering key value are stored together in the same storage
block.

Advantages:

 It improves performance in operations like range queries or joins on the clustering key.

Disadvantages:

 Clustering indexes require more storage and space.

 Not very efficient when the data is constantly changing.

1. Ordered Indexes: Sorted for fast search

2. Primary Index:

o Built on primary key

 o Types: a. Dense Index: Every record has an index b. Sparse Index: Index only for
some records

3. Clustering Index: Made on non-unique key by combining columns

4. Secondary Index:

o Adds extra level of index to handle large tables

o First level (small) in primary memory, second level + data in disk

B-Tree in DBMS

 Balanced search tree for large data.

 Stores many keys per node, reducing height.

 Good for hard drives, SSDs.

Properties:

 All leaf nodes at same level

 Nodes have [m/2 -1] to [m-1] keys

 Internal nodes have m/2 to m children

 Keys are sorted in each node

Operations:

 Search: Follows paths based on comparisons

 Insert:

o Insert at leaf

o If full, split node and move up the middle key

 Delete: Remove and restructure if needed

B+ Tree in DBMS

 Like B-Tree but stores actual data only in leaf nodes.

 Internal nodes just point to leaf nodes.

 Leaf nodes are linked for fast sequential access.

Structure:

 Leaf node has key+pointer and points to next leaf

 Internal node has pointers only

Operations:
  Search: Go from root to correct leaf, then scan

 Insert: If leaf is full, split it and update internal node

 Delete: Remove from leaf and adjust internal nodes if needed

Sure! Here's your original content rewritten in simple and easy language just like you asked —
without adding new examples or extra explanations:

Hashing in DBMS – Simple Version

In large databases, searching all index values is slow. Hashing helps find the exact location of a data
record without using an index.
It stores data in data blocks or buckets, and their address is made using a hash function.

The hash function usually uses the primary key to make the address. The function can be simple or
complex. Sometimes, the primary key itself is used as the address.
This means, each row is stored in a block with an address same as its primary key.

The diagram shows addresses same as primary keys. The hash function can also be mod, cos, sin, etc.
If we use a mod (5) hash function, it gives results like 3, 3, 1, 4, 2 — so records go to those block
numbers.

Types of Hashing:

1. Static Hashing

 Here, the bucket address stays the same every time.

 Example: If EMP_ID = 103, mod(5) always gives 3.

 The number of buckets remains constant.

Operations in Static Hashing:

 Search: Use hash function to get the bucket and find data.

 Insert: Use hash key to find bucket, store record there.

 Delete: Find the record using hash key, delete it.

 Update: Find and change the record.

If the bucket is already full, it is called bucket overflow — a major problem in static hashing.

2. Dynamic Hashing

 Solves the bucket overflow problem.

 Buckets grow or shrink as records increase or decrease.

 Also called Extendable Hashing.

 Allows insert and delete without slowing down performance.

Here’s your "Transactions in DBMS" content rewritten in simple and easy language, just
how you asked:

Transactions – Simple Version

A transaction is a program that performs a set of operations on the database like insert,
delete, update, or read.
It is done as one single unit — either the whole thing happens, or nothing happens at all.
If a transaction only reads data and does not change anything, it is called a read-only
transaction.

Example: Steps of a Transaction

A task like updating data can be broken into 3 simple steps:

 read_item() – Get the data from storage into memory.

 modify_item() – Change the data in memory.

 write_item() – Save the changed data back into storage.

All database actions are based on read and write operations.

Transaction Operations

These are the small steps inside a transaction:

 begin_transaction – Marks the start of the transaction.

 read_item / write_item – Do the actual data work.

 end_transaction – Marks the end of the transaction.

 commit – Confirms everything was successful; changes are saved permanently.

 rollback – Cancels the transaction; changes are undone if anything goes wrong.

⚠️ Note: Once committed, a transaction cannot be rolled back.

Transaction States

A transaction can be in these 5 states:

1. Active – Transaction has started and is running.

2. Partially Committed – All commands are done, but not yet finalized.
 3. Committed – Success! All changes are saved permanently.

4. Failed – Something went wrong during execution.

5. Aborted – Changes are canceled and the database is restored to its original state.

ACID Properties (Important for Transaction)

Every transaction should follow ACID rules:

 Atomicity – All steps happen together or none happen.

 Consistency – The database remains correct before and after the transaction.

 Isolation – Transactions do not affect each other while running together.

 Durability – Once done, the changes will not be lost, even if the system fails.

Let me know if you'd like charts or diagrams in a simple way too!

ConfHere’s your topic “Schedules and Conflicts” rewritten in simple and easy language, just how
you wanted:

Schedules and Conflicts (Simple Version)

When many transactions are running at the same time in a system, the order in which their
operations happen is called a Schedule.

If we have multiple transactions (like T1, T2, T3…), then a schedule shows how their steps (like
read or write) are arranged in time.

Types of Schedules

1. Serial Schedule

 Only one transaction runs at a time.

 One must finish completely before the next starts.

 No overlapping between transactions.

🧠 Example:
If T1 runs first and completes, and then T2 starts – that’s a serial schedule.

2. Non-Serial Schedule
  Multiple transactions run at the same time, and their steps are mixed (interleaved).

 Some operations of T1, then T2, then again T1... (mixed order).

 Can lead to problems if not handled properly.

📌 Non-Serial schedules are divided into:

➤ Serializable

A non-serial schedule is Serializable if it gives the same result as a serial schedule, even though
operations are mixed.

✅ Benefits: More concurrency, faster processing, but still keeps data correct.

Types of Serializable Schedules:

1. Conflict Serializable

o Can be changed into a serial schedule by swapping operations that don’t conflict.

o Conflicting operations happen when:

 They are from different transactions.

 They work on the same data.

 At least one is a write.

2. View Serializable

o Looks the same as a serial schedule when seen from outside.

o Even if operations are mixed, if the final result is same, it is view serializable.

o All conflict serializable schedules are view serializable, but not always the other
way around.

➤ Non-Serializable

These schedules do not guarantee correct final results like a serial schedule.

Types:

1. Recoverable Schedule

o A transaction commits only after the one it depends on also commits.

o This keeps the database safe and recoverable in case of failure.

2. Non-Recoverable Schedule

o If the system crashes, we may not be able to fix or roll back properly.

o Unsafe and can cause data loss or corruption.

Conditions:

 Different transactions

 Access same data

 At least one is writing

Absolutely! Here's the same info rewritten in super simple and easy language, just like talking to a
friend:

📅 What is a Schedule?

A schedule just shows the order in which steps from different transactions happen.

📚 Types of Schedules

1. Serial Schedule

 One transaction at a time.

 No mixing.

 Example: T1 finishes → then T2 starts.

2. Non-Serial Schedule

 Many transactions run together.

 Their steps mix.

 Two types:

a. Serializable

 Even if mixed, it gives the same result as serial.

 Good for performance and safe.

 Two kinds:

o Conflict Serializable:

 If we can rearrange steps to make it look like serial.

 Conflict happens when:

 Two transactions work on same data.

 One of them writes.

o View Serializable:

 Final result looks like serial.

 It’s a bit more relaxed than conflict serializable.

  Can handle some tricky cases (like blind writes).

b. Non-Serializable

 Not safe. Can mess up data.

 Two types:

o Recoverable:

 A transaction commits only after the one it read from commits.

o Non-Recoverable:

 Commits without waiting.

 Can cause problems if there’s a crash.

⚠️ What is a Conflict?

A conflict happens if:

1. Steps are from different transactions.

2. They use the same data.

3. At least one of them is a write.

✅ What is Serializability?

It means:

 Even if transactions run together,

 The result is same as if they ran one after another.

🔄 Equivalence Between Schedules

Two schedules are equal if:

1. Result Equivalence: Final answer is same.

2. View Equivalence: Do the same thing, same way.

3. Conflict Equivalence: Conflicting steps are in same order.

🤝 What is Concurrency Control?

When many users use the database at once, we need rules to keep it correct.
This is called Concurrency Control.
🛡️ Methods for Concurrency Control

1. Lock-Based Protocol

 Transactions lock data before using.

 Two types:

o 🔒 Shared Lock (Read only): Many can read.

o 🔐 Exclusive Lock (Read + Write): Only one can use.

Types of Locking Methods:

 Simplistic: Lock before use, unlock after done.

 Pre-claiming: Ask for all locks first.

 Two-Phase Locking (2PL):

o First: Take locks.

o Then: Release them.

 Strict 2PL:

o Locks are only released after the transaction finishes.

2. Timestamp Protocol

 Each transaction gets a timestamp when it starts.

 Older timestamps get priority.

Read Rule:

 Can read if no newer transaction wrote on it.

Write Rule:

 Can write only if no older transaction already read/wrote it.

3. Validation (Optimistic) Protocol

Used when conflicts are rare.

Steps:

1. Read Phase: Do work in local memory.

2. Validation Phase: Check if it’s safe.

3. Write Phase: Save to database.

If not safe → rollback.

🔁 Multiversion Control

 Keeps many versions of data.

 Readers can use an older version, no waiting needed.

Got it! Here's the same explanation you gave me in your prompt, but in simple and easy
language — no cutting anything, just making it clearer:

Optimistic Concurrency Control Algorithm – Easy Language

In systems where conflicts between transactions are rare, checking every transaction in
detail during execution can slow down performance.

So instead of checking early, the system waits till just before commit to check if everything is
okay. Because conflicts don’t happen often, the chance of a problem is also low.

This method is called Optimistic Concurrency Control (optimistic = hopeful, expecting no

issues).

🔁 Transaction's Life Cycle Has 3 Phases:

1. Execution Phase
→ The transaction reads data into memory and does its work there.
→ It does not update the real database yet.

2. Validation Phase
→ The transaction checks: "If I save my changes now, will there be any problems?"
→ It tests if saving would break serializability (correct order of operations).
3. Commit Phase
→ If validation passes (no conflicts), it saves all the changes to the actual database.
→ If validation fails, the transaction is rolled back (cancelled).

✅ During Validation Phase, 3 Rules Are Used:

These rules help keep the database correct and consistent when many transactions are
running at the same time.

Rule 1: Read–Write Conflict

 If there are two transactions Ti and Tj,

 And Ti is reading a data item that Tj is writing,

 Then Ti’s execution phase and Tj’s commit phase must not happen at the same time.

 So, Tj can only commit after Ti is done executing.

 Rule 2: Write–Read Conflict

 If Ti is writing a data item that Tj is reading,

 Then Ti’s commit phase and Tj’s execution phase must not happen at the same time.

 So, Tj can only start executing after Ti has committed.

Rule 3: Write–Write Conflict

 If both Ti and Tj are writing the same data item,

 Then their commit phases must not happen at the same time.

 So, Tj can only commit after Ti has committed.

Let me know if you want this turned into a short story or visual too — happy to help!

Basic Rules:

 Two writing same thing? → one waits.

 Reading while other writing? → wait.

 Writing while other reading? → wait.

💥 Recovery Techniques (When Crash Happens)

If system crashes, we need to bring it back to normal.

Ways to do that:

1. Mirroring:

o Keep two copies of data.

o If one breaks, use the other.

2. Backup Recovery:

o Store copies regularly.

o Two types:

 Immediate (for quick fix).

 Archival (for big disasters).

3. Transaction Logs:

o Keep a log of what was done.

 o Use it to undo or redo after crash.

4. Shadow Paging:

o Keep two versions of data pages.

o If crash, use the old (shadow) one to recover.

Want this in PDF or diagram too?