Advanced Database Management Systems (25ME IT)

Assignment
QNO#01 What is a recovery system in DBMS, and why is it important?
Recovery System in DBMS:

A recovery system in the context of a Database Management System (DBMS) is a feature

responsible for maintaining the databases coherence and consistency in the event of failures such
as:
 System crashes: Power outages, hardware failures
 Transaction failure : Logical failure, deadlock
 Disk failure: Data corruption windows
 User errors : Accidental deletion of vital data
The recovery system restores state of the database by using following methods:
 Rollback: Provides Undo mechanisms: deletion and or updation of data.
 Redo: Reapplication of all the performed changes (even the ones made to the transactions
that will be reversed later).
 Checkpointing: Used when unexpected shutdowns are caused.

A recovery system ensures:

 Atomicity: Either all operations of a transaction are executed, or none.
 Durability: Once a transaction has been committed, the changes will survive even if there is a
crash.
 Consistency: The database remains in a valid state before and after transactions.
Why Recovery System is Important
1. Data Integrity: Ensure consistency of data.
2. Durability (ACID Property): Transaction is saved even after system failures.
3. Fault Tolerance: Minimizing downtime and loss of data.

Methods of Key Recovery

1. Recovery using Logs (Write-Ahead Logs - WAL)
• Changes within the database are written to a log file before any writing occurs on the disk
2. Checkpointing
• A checkpoint is taken by the DBMS periodically, capturing the current state of the
transactions to facilitate recovery.
3. Shadow Paging
• Keeps two versions of the data.
o Current Page Table (active)
o Shadow Page Table (backup)
• Modifications are made to the shadow copy.
4. Backup & Restore
• Database copy is created on a set schedule.

ARIES Recovery Algorithm (Advanced Recovery Method)

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is a recovery method for
modern systems like Oracle and SQL Server. They use DBMS with high efficiency performance.

Concepts

•Log Sequence Number (LSN): Log record identification number.

•Dirty Page Table: Contains modified pages that are yet to be rendered to the disk.

•Write-Ahead Logging (WAL): Guarantees that logs will always come before data being written.

Phases of ARIES Recovery

1. Analysis Phase:

Locate dirty pages and active transactions at the time of the crash.

2. Load Again Phase:

Reapplies all changes even for transactions that will eventually be rolled back.

3. Undo Phase:

Reverses uncommitted transactions.

 QNO#02 Define transaction failure and list some common causes?
What is Transaction Failure?
A transaction failure occurs when an attempt to execute a transaction does not complete successfully,
which requires an abort of the entire transaction. The failure must always be ensured not to end up leaving
the database in an inconsistent state.
Common Causes of Transaction Failure
Logical Errors (Application-Level Failures)
 Violation of Integrity Constraints
Example: Adding a primary key where another primary key field already exists which would
violate the UNIQUE constraint.
 Semantic Errors (Business Logic Errors)
Example: Executing a Bank transaction to transfer a negative amount.
 Division by Zero / Arithmetic Errors
Example: UPDATE accounts SET balance = balance / 0 WHERE user_id = 123;
 Deadlocks
Example:Transaction T1 locks Row A and is waiting to acquire Row B.
Transaction T2 locks Row B and is waiting to acquire Row A.
DBMS will identify the deadlock situation and subsequently block one of those two transactions.
System-Related Failures
 Resource Unavailability
Example: Exhausting memory or disk space while the transaction is running.
 Timeout Failures
Example: Total time spent on a transaction is excessive due to acquired locks and locks are
refreshed and the transaction is heuristically aborted.

 Concurrency Control Conflicts

Example: Execution of two transactions that alter the same data at the same instant gives way to
conflict (for example lost update or dirty read).
External Factors
 User-Initiated Abort
Example: A user voluntarily executes a ROLLBACK command.

 Network Failures
Example: A node in a distributed DBMS crashes, and hence transactions get rolled back.

How DBMS Handles Transaction Failures?

 Undo (Rollback) Changes

DBMS employs log files (pre-images) to roll back uncommitted changes.

Example: If a transaction aborts after having modified 3 rows, all the changes are rolled back.

 Deadlock Detection & Resolution

DBMS employs wait-for graphs for deadlock detection and aborts one transaction.

 Checkpointing & Recovery

Periodic checkpoints decrease recovery time by constraining the number of transactions to be

rolled back.
QNO#03 What is the difference between system crash and media failure?

Feature System Crash Media Failure

Type of Failure Temporary (soft failure) Permanent (hard failure)

- Software bugs - Disk head crashes

- OS failures - Bad sectors
Primary Causes - Power outages - Controller failures
- Memory overflow - Natural disasters
- DBMS process termination - Malicious damage

Data physically intact but may be Physical storage medium damaged

Data Status
logically inconsistent or unreadable

- Transaction logs (WAL) - Full/incremental backups

Recovery - Checkpointing - Archived logs
Mechanism - Redo/Undo operations - Disk replication
- ARIES algorithm - RAID recovery

- RAID configurations
- UPS systems
- Regular backups
Prevention - Fault-tolerant software
- Storage mirroring
Methods - Regular system updates
- ECC memory
- Process monitoring
- Disk scrubbing

Recovery Time Typically faster (minutes to hours) Typically slower (hours to days)

Impact Scope Affects current transactions Affects entire database storage

Dependency Depends on transaction logs Depends on backup systems

Failure Detection Automatic upon restart May require manual verification

Frequency More common Less common

Cost Implications Lower recovery costs Higher recovery costs

- Blue screen of death - Hard disk clicking sound

Example
- Database service crash - SSD controller failure
Scenarios
- Power grid failure - Flood damage to server

Data Loss
Only uncommitted transactions lost Potential loss of entire database
Potential

Human Often requires significant manual

Minimal (automatic recovery possible)
Intervention effort
 Feature System Crash Media Failure

- In-memory logging - Storage area networks

Advanced
- Non-volatile RAM - Cloud replication
Solutions
- Continuous checkpointing - Blockchain-based verification

QNO#04. Explain the role of the log file in database recovery.

Basics of Logs in Transactions
A transaction log (or just "log") is essential for the recovery of a database, as well as in maintaining
durability, atomicity, and consistency of data in case of any system failure or crash. A transaction log can
be thought of as a sequential record of all changes made to a database, thereby allowing the DBMS to
redo a committed transaction or undo an incomplete transaction after a crash.

Types of Structures in a Transaction Log

Every log file contains a number of different types of records, each of which is produced to serve a
different purpose in recovery:

Begin Transaction:This is an indicator that a transaction has commenced.

Write: Records the modifying after as old_Value and the new_Value after changing status regarding a
data item (X).
Commit: this signifies that a transaction is now complete successfully.
Abort : the transaction rolled back.
Checkpoint:This is done periodically to save the state of the database so that future optimization can be
performed.

Principal Functions that Transaction Logs Perform in Terms of Recovery

Atomicity Maintenance (Undo Operations)
In the case of a transaction failure before committing, DBMS will roll back by undoing changes made by
that transaction using old_value from the log.
Durability Maintenance (Redo Operations)
If the transaction commits but changes are not written to the disk, the DBMS redoes the operation using
the contents of new_value .
Addressing Media Failures with Archived Logs
The archived logs allow restoring data even in the event of a primary disk crash. They supplement
backup data to reestablish the database to a certain point in time.
Recovery Process with Logs.
The DBMS has a systematized recovery procedure as follows:
Analysis Phase : Committed and failed transactions identified from the log.
Redo Phase : All committed changes reapplied (even if not yet on disk).
Undo Phase : Rollback of uncommitted transactions.
 QNO#05 What is a checkpoint in DBMS recovery?
DBMS Recovery Checkpoint
A checkpoint in DBMS recovery is an essential facility to minimize the time of recovery and maintain
data consistency in case of system failure. The checkpoint is where the database system ensures all
committed transactions have been saved onto the disk so that less log can be processed during recovery.

Important Functions of Checkpoint:

 Flush Dirty Pages:
Permanent storage of all modified (dirty) buffer pages concerning committed transactions.
Ensures durability by making changes permanent.
 Log Checkpoint Record Write:
A special <CHECKPOINT> record is written into the transaction log, which indicates a consistent state.
Therefore, it allows determining up to which point the database is stable.
 Tracking Active Transactions:
The system records which transactions were still in progress (not yet committed) at the time of the
checkpoint.
This information is necessary for undoing or redoing transactions during recovery.
Importance of Checkpoints:
 Faster Recovery: If there were no checkpoints, the system would have to reprocess the
entire transaction log after a crash. With checkpoints, recovery is restricted to only those last
transactions.
 Less Overhead: By periodically flushing to disk, checkpoints obviate heavy logging.
 Consistency Assurance: Ensures that all transactions committed before the checkpoint
are safely stored.
Types of Checkpoints:
 Sharp Checkpoint (Blocking Checkpoint):
o Does immediate flushing of all dirty pages to disk.
o It causes brief pause of transaction processing, but recovery is simpler.
o Used in systems that require very high consistency.
 Fuzzy check point (Non-blocking Check Point):
o During checkpointing, it allows some dirty pages to remain in memory.
o Minimized performance impacts, but more complex recovery logic is necessary.
o Commonly found in high-performance DBs (e.g., Oracle, SQL Server).

Checkpoint frequency:
 Too many = high I/O overhead.
 Too few = recovery time increases.
 Most DBMS have some mechanism that alters their checkpoint frequency for the
workload.

QNO#06. Compare immediate update and deferred update recovery techniques.

 Feature Immediate Update Deferred Update

When Changes are Changes (updates) are written to Changes are written to disk only
Written to Disk disk before the transaction commits. after the transaction commits.

Log records (both redo and undo) Only redo logs are needed since no
Logging Approach
are written for every modification. uncommitted changes are on disk.

Recovery - Undo uncommitted changes. Only redo committed changes (no

Mechanism - Redo committed changes. need for undo).

Performance Higher overhead due to frequent Lower runtime overhead since

Impact disk writes during execution. writes happen only at commit.

Slower recovery (requires both

Recovery Speed Faster recovery (only redo needed).
undo and redo).

Concurrency Requires strict locking (e.g., 2PL) Easier to manage since uncommitted
Control to prevent dirty reads. changes are not visible.

Crash Recovery More complex (must handle partial Simpler (only committed changes
Complexity updates). are applied).

Suitable for high-consistency Preferred for high-throughput OLTP

Use Cases
systems (e.g., banking). systems (e.g., e-commerce).

QNO#07 . Explain how undo (rollback) and redo (roll-forward) operations work in recovery.
 Undo of a log record <Ti, X, V1, V2> writes the old value V1 to X
 Redo of a log record <Ti, X, V1, V2> writes the new value V2 to X
 Undo and Redo of Transactions
 undo(Ti) restores the value of all data items updated by Ti to their old values, going
backwards from the last log record for Ti
 each time a data item X is restored to its old value V a special log record <Ti , X,
V> is written out
 when undo of a transaction is complete, a log record
<Ti abort> is written out.
 redo(Ti) sets the value of all data items updated by Ti to the new values, going
forward from the first log record for Ti
 No logging is done in this case
From Failure:
 When recovering after failure:
o Transaction Ti needs to be undone if the log
 contains the record <Ti start>,
 but does not contain either a <Ti commit> or a <Ti abort>.record
 transaction Ti needs to be redone if the log
  contains the records <Ti start>
 and contains the record <Ti commit> or <Ti abort>
 Note that If transaction Ti was undone earlier and the <Ti abort> record written to the log,
and then a failure occurs, on recovery from failure Ti is redone
 such a redo redoes all the original actions including the steps that restored old values
 Known as repeating history
 Seems wasteful, but simplifies recovery greatly
QNO#08 A transaction `T1` performs the following operations in order:
- `Read(A)` (A=100)
- `Write(A=200)`
- `Read(B)` (B=50)
- `Write(B=150)`
If the system crashes before commit, what will be the final values of `A` and `B` in the database
under Deferred Update?
Recovery Scenario in Deferred Update Mode
Given Transaction T1:
1. Read(A) (A=100)
2. Write(A=200) (updated in memory, not yet on disk)
3. Read(B) (B=50)
4. Write(B=150) (updated in memory, not yet on disk)
5. System crashes before commit
How Deferred Update Works
 Changes are written to disk only after the transaction commits.
 Before commit, all modifications are kept in memory buffers (not persisted).
 The log records the intent to modify but does not apply changes to disk until commit.
Before Crash:

<T1, START>

<T1, A, 200> (New value for A, not yet written to disk)

<T1, B,
After 150> Recovery
Crash: (New value for B, not yet written to disk)
Process
// No <T1,
1. COMMIT>
Check recorded
the log for committed transactions:

o T1 did not commit, so its changes must be discarded.

2. No redo needed (Deferred Update does not write uncommitted changes to disk).
3. No undo needed (since changes were never applied to disk).
Final Values in the Database
 A = 100 (original value, since Write(A=200) was deferred and never committed)
 B = 50 (original value, since Write(B=150) was deferred and never committed)
Why?
 Deferred Update ensures durability only after commit.
 Since T1 crashed before commit, none of its changes are reflected on disk.
 The database remains in its last consistent state before T1 started.

QNO#09 A transaction `T2` does the following:

- `Write(X=500)` (original X=200)
- `Write(Y=300)` (original Y=100)
- Commit
- System crashes before flushing logs to disk.
What happens to `X` and `Y` under Immediate Update with UNDO/REDO?
Recovery Scenario for Transaction T2 in Immediate Update with UNDO/REDO
Given Transaction T2:
1. Write(X=500) (original X=200)
2. Write(Y=300) (original Y=100)
3. Commit (transaction is marked as committed in the log)
4. System crashes before flushing logs to disk
Immediate Update with UNDO/REDO: Key Properties
 Changes are written to disk before commit (Immediate Update).
 Log records are written before data modifications (Write-Ahead Logging - WAL).
 Both UNDO (rollback) and REDO (rollforward) are supported for recovery.
Expected Log Entries (Before Crash):
<T2, START>
<T2, X, 200, 500> (Before-image=200, After-image=500)
<T2, Y, 100, 300> (Before-image=100, After-image=300)
<T2, COMMIT>

(Log records are in memory but not yet flushed to disk when the crash occurs.)

After Crash: Recovery Process

1. Analyze the log:

 o Since the log was not flushed, the COMMIT record is lost, and the DBMS

treats T2 as uncommitted (even though it logically committed before the crash).

o The disk still has the original values (X=200, Y=100) because the log (and thus the

changes) were not persisted.

2. Apply UNDO (rollback):
o The recovery manager checks the log (in memory, now lost) and sees that T2 was not

durably committed (no COMMIT on disk).

o However, since the log wasn’t flushed, no changes were applied to disk, so no UNDO is

needed.
3. No REDO needed:
o Since the COMMIT wasn’t durable, the DBMS assumes T2 never committed, and its

changes are discarded.

Final State of the Database
 X = 200 (original value, since the log and changes were never persisted)
 Y = 100 (original value, same reason)
QNO#10 Given the following log entries:
i. <START T1>
ii. <T1, A, 100, 200>
iii. <START T2>
iv. <T2, B, 50, 150>
v. <COMMIT T1>
vi. <CHECKPOINT>
vii. <T2, C, 200, 300>
viii. <COMMIT T2>
ix. CRASH
Using Immediate Update, determine which transactions are redone and which are undone.
Step 1: Identify Transactions and Their Status
Log Entry Transaction Action Status at Crash

<START T1> T1 Begins -

<T1, A, 100, 200> T1 Writes A=200 -

<START T2> T2 Begins -

Log Entry Transaction Action Status at Crash

<T2, B, 50, 150> T2 Writes B=150 -

<COMMIT T1> T1 Committed Committed

<CHECKPOINT> - System checkpoint -

<T2, C, 200, 300> T2 Writes C=300 -

<COMMIT T2> T2 Committed Committed

CRASH - System fails -

Step 2: Checkpoint Analysis

 The <CHECKPOINT> records the state of active transactions at that point.
 At checkpoint time:
o T1 is already committed (no action needed).
o T2 is still active (not yet committed).
Step 3: Recovery Rules (Immediate Update)
1. REDO all committed transactions (even if changes were applied, to ensure durability).
2. UNDO all uncommitted transactions (to maintain atomicity).
Transactions to Consider:
 T1: Committed before checkpoint → REDO needed (if changes weren’t flushed).
 T2: Started before checkpoint, committed after → REDO needed (committed before crash).
 Since T2 committed before the crash, it does not need UNDO.
 Only uncommitted transactions at crash time are undone.
Final Decision
Status at
Transaction Recovery Action
Crash

T1 Committed REDO (ensure A=200 is applied if not on disk)

REDO (ensure B=150 and C=300 are applied if

T2 Committed
not on disk)

(No active transactions at - No UNDO needed

 Status at
Transaction Recovery Action
Crash

crash)

Why No UNDO?
 T1 and T2 both committed before the crash, so their changes must persist (durability).
 No transaction was active at crash time, so nothing to roll back.
Why REDO Both?
 Even if some changes were written to disk, Immediate Update requires REDO for all committed
transactions to guarantee durability.
Summary of Recovery Actions
1. REDO T1: Reapply <T1, A, 100, 200> (set A=200).
2. REDO T2: Reapply:
o <T2, B, 50, 150> (set B=150).
o <T2, C, 200, 300> (set C=300).

3. UNDO: None (no active transactions at crash).

Final Database State After Recovery
 A = 200 (redone)
 B = 150 (redone)
 C = 300 (redone)
This ensures durability (committed changes persist) and atomicity (no partial updates)
QNO#11 A database uses Immediate Update with logging. Given:
- 10,000 transactions/day
- 2% abort rate
- Average 5 operations/transaction
- Each UNDO takes 2ms, each REDO takes 1ms

Calculate the total recovery time if a crash occurs at the end of the day.
Given Data
1. Number of transactions per day (T): 10,000
2. Abort rate (A): 2% (so 98% commit successfully)
3. Average operations per transaction (O): 5
4. Time per UNDO operation (U): 2 ms
 5. Time per REDO operation (R): 1 ms

Calculating Aborted and Committed Transactions

 Aborted transactions: 2% of 10,000 = 0.02 * 10,000 = 200 transactions
 Committed transactions: 10,000 - 200 = 9,800 transactions
Operations in Aborted and Committed Transactions
Each transaction has an average of 5 operations.
 Operations in aborted transactions (for UNDO): 200 transactions * 5 operations/transaction =
1,000 operations
 Operations in committed transactions (for REDO): 9,800 transactions * 5
operations/transaction = 49,000 operations
Time for UNDO and REDO
1. Total UNDO time: Number of operations to UNDO * time per UNDO
1,000 operations * 2 ms/operation = 2,000 ms
2. Total REDO time: Number of operations to REDO * time per REDO
49,000 operations * 1 ms/operation = 49,000 ms
Total Recovery Time
The total recovery time is the sum of UNDO and REDO times.
Total recovery time = UNDO time + REDO time
= 2,000 ms + 49,000 ms= 51,000 ms
Converting to Seconds
Since 1,000 ms = 1 second,
51,000 ms = 51 seconds Ans.
QNO#12 Explain how B+ Trees are used for indexing in databases. Why are they preferred over
binary search trees?
 A B+ Tree is a hierarchical, self-balancing data structure frequently utilized for indexing
in databases. It enables effective insertion, deletion, and search actions while maintaining the
tree's balance, ensuring reliable performance as data expands.

Composition of a B+ Tree:

Internal Nodes:

Include only keys (no information).

Guide the search through the tree.

Leaf Nodes:
 Include keys and references to data records (or actual data in certain designs).

Are connected in sequence to facilitate rapid range queries.

Balanced Tree:

Every data entry is at an identical depth (leaf level).

Maintains balance following insertions or deletions through node splits or unions.

How B+ Trees Are Utilized for Indexing:

Every index is realized as a B+ Tree.

Keys within the tree represent attribute values (e.g., names, IDs).

Every key in a leaf node directs to the relevant record(s) in the database.

Searching entails moving through the tree from root → internal nodes → leaf node

Why B+ Trees are Preferred Over Binary Search Trees (BSTs):

Feature B+ Tree Binary Search Tree

May become unbalanced (degraded to a

Balance Always balanced
linked list)

Optimized for disk/block access (few, wide

Disk I/O Deep trees increase disk reads
levels)

High fan-out (many keys per node) →

Fan-out Each node has ≤2 children (deep tree)
fewer levels

Search Time Logarithmic and consistent due to balance Can be O(n) in worst case

Range Queries Efficient due to linked leaf nodes Inefficient; must traverse nodes

Space
High, as only leaves store data Lower, all nodes may store data
Utilization

QNO#13. What is bitmap indexing and in what scenarios is it more efficient than B-Tree indexing?

What does Bitmap Indexing mean?

Bitmap indexing is a unique database indexing method in which each unique value of a column is
depicted by a bit-vector (bitmap). Each bitmap signifies the existence or non-existence of the value in
each row.

How It Operates:
Imagine you have a column titled `Gender` that contains the values: `Male`, `Female`, and `Other`. For a
table containing 8 rows:

| Coulumn | Gender |
| 1 | Man |

| 2 | Woman |

| 3 | Man |

| 4 | Other |

| 5 | Man |

| 6 | Woman |

| 7 | Woman |

| 8 | Other |

The bitmap index would appear as follows:

* Man → 1 0 1 0 1 0 0 0

* Female → 0 1 0 0 0 1 1 0

* Other → 0 0 0 1 0 0 0 1

Every bit signifies a row. A `1` indicates that the value exists in that row.

Utilizing Bitmap Index for Queries:

To locate all `Female` entries, simply examine the `Female` bitmap:

→ `0 1 0 0 0 1 1 0` → lines 2, 6, and 7.

To locate `Male OR Other`:

→ bitwise OR of `Male` and `Other`:

`1 0 1 0 1 0 0 0` OR `0 0 0 1 0 0 0 1` = `1 0 1 1 1 0 0 1`

Scenario Why Bitmap Index Wins

Low cardinality columns (few distinct
Fewer bitmaps, compact and fast to process
values)
Bit operations (AND/OR/NOT) are faster than B-Tree
Read-heavy queries
traversal
Efficient use of bitwise logic across multiple bitmap
Complex conditions (multi-column filters)
indexes
 Scenario Why Bitmap Index Wins
Data warehouses/OLAP systems Large data, mostly read-only, with analytical queries

Example use cases:

 Gender, Country, Marital Status

 Status flags (e.g., active/inactive)
 Star schema dimension attributes

When Bitmap Indexing is Not Recommended:

 High-cardinality columns (e.g., user ID, timestamps)

 Frequent updates or inserts (bitmaps require expensive rewriting)

QNO#14 Discuss how multilevel indexing improves performance in large-scale databases. What
are the trade-offs?
Multilevel Indexing in Large-scale Databases
Multilevel indexing is a method employed to enhance the efficiency of
searching, adding, and removing data in extensive databases by implementing a hierarchy of
indexes instead of depending on a one-level index.
Main Index:
Creates an index for the primary data file (organized by a key).
Indicates data segments.
Secondary (or advanced) Indexes:
Index the subordinate indexes.

Assist in preventing the linear scanning of a large index file.

This creates a structure resembling a tree (often akin to B+ Trees in real use).
Imagine you possess 1 million entries, each featuring a distinct key:
A single level index could contain 100,000 entries (assuming each block stores 10 records).
Examining this index in a linear manner or using binary search may incur high disk I/O costs.
Multilevel index presents:
A primary index featuring entries that direct to index blocks.
A secondary index that leads to primary blocks.
Maybe a third stage, and continuing on.
Containing 100 items for each block:
Initial tier: 10,000 blocks
Second tier: 100 blocks
Tertiary level: 1 block → rapid retrieval in 3 readings instead of thousands
Performance:
Feature Benefit
Reduced disk I/O Only a few levels to traverse, each reading one disk block
Scalability Handles large datasets efficiently
Faster searches Logarithmic access time compared to linear index scans

Tradeoffs of Multi Level:

Trade-Off Description
📦 Extra Storage Each level of index consumes disk space
🛠️Maintenance Overhead Inserting/deleting records may require updates in multiple index levels
🔄 Slower updates More complex index management, especially with many levels
🧠 Complexity More logic needed for index traversal and synchronization

QNO#15 What is the role of indexing in distributed databases and how is index consistency
maintained across nodes?
Indexing in Distributed Databases
In distributed databases, information is disseminated across various nodes (servers or sites), and indexing
is essential for enabling efficient data access, retrieval, and query processing throughout the system.
Functions of Indexing in Distributed Databases:
Rapid Query Handling Across Nodes
Aids in finding data without examining all distributed tables.
Lowers query latency by identifying the correct node or partition.
Optimizing Data Locality
Indexes can direct queries to the particular node/partition that holds the pertinent data.
Assistance for Worldwide Inquiries
Global indexes offer a cohesive perspective across nodes, facilitating effective joins and
aggregations involving multiple nodes.
Distributing Workload
Indexes assist in directing queries to less-congested nodes, enhancing efficiency and scalability.
Partition-Trimming
Indexing enables bypassing unrelated partitions or shards, particularly in partitioned tables.

Maintaining Index Consistency Across Nodes

Maintaining index consistency in a distributed setup is challenging but essential for correctness and
performance.

Key Strategies:

1. Synchronous Updates (Eager Indexing)

o Index is updated immediately when data is inserted/updated/deleted.
o Guarantees consistency but adds latency and reduces write throughput.
2. Asynchronous Updates (Lazy Indexing)
o Index is updated eventually, often in the background or via batch jobs.
o Improves write performance but may cause temporary inconsistency (eventual
consistency model).
3. Distributed Transactions (2PC or Paxos/Raft-based)
o Ensure atomic update of both data and index across nodes using distributed consensus
protocols.
o Expensive and complex; used sparingly (e.g., for critical indexes).
4. Change Data Capture (CDC) + Log-based Indexing
o Changes are captured from logs (e.g., WAL) and applied to indexes.
o Common in systems like Apache Cassandra or MongoDB.
5. Quorum-based Validation (for replicated systems)
o Index updates are validated by a quorum of replicas to ensure consistency.

QNO#16 Describe the concept of two-phase locking (2PL). What are its rules and how does it
ensure conflict-serializability?

 A protocol which ensures conflict-serializable schedules.

 Phase 1: Growing Phase
• Transaction may obtain locks
• Transaction may not release locks
 Phase 2: Shrinking Phase
• Transaction may release locks
• Transaction may not obtain locks
 The protocol assures serializability. It can be proved that the transactions can be serialized in the
order of their lock points (i.e., the point where a transaction acquired its final lock).
 Two-phase locking does not ensure freedom from deadlocks
 Extensions to basic two-phase locking needed to ensure recoverability of freedom from cascading
roll-back
 Strict two-phase locking: a transaction must hold all its exclusive locks till it commits/aborts.
 Ensures recoverability and avoids cascading roll-backs
 Rigorous two-phase locking: a transaction must hold all locks till commit/abort.
 Transactions can be serialized in the order in which they commit.
 Most databases implement rigorous two-phase locking, but refer to it as simply two-phase
locking
  Two-phase locking is not a necessary condition for serializability
• There are conflict serializable schedules that cannot be obtained if the two-phase locking
protocol is used.
 In the absence of extra information (e.g., ordering of access to data), two-phase locking is
necessary for conflict serializability in the following sense:
• Given a transaction Ti that does not follow two-phase locking, we can find a transaction
Tj that uses two-phase locking, and a schedule for Ti and Tj that is not conflict
serializable.

QNO#17 What is the difference between strict 2PL and basic 2PL? How does strict 2PL help
prevent cascading rollbacks?

 Two-phase locking does not ensure freedom from deadlocks

 Extensions to basic two-phase locking needed to ensure recoverability of freedom from cascading
roll-back

• Strict two-phase locking: a transaction must hold all its exclusive locks till it
commits/aborts.

 Ensures recoverability and avoids cascading roll-backs

• Rigorous two-phase locking: a transaction must hold all locks till commit/abort.

 Transactions can be serialized in the order in which they commit.

 Most databases implement rigorous two-phase locking, but refer to it as simply two-phase
locking

How Strict 2PL Prevents Cascading Rollbacks

  By not releasing any write locks before commit:
o No other transaction can see uncommitted changes.
o So, no transaction reads dirty data.
o Hence, if a transaction aborts, no other transaction is affected

QNO#18 . How do timestamp ordering protocols manage concurrent transactions? What are the
advantages and drawbacks of this approach

The timestamp ordering (TSO) protocol

 Maintains for each data Q two timestamp values:

• W-timestamp(Q) is the largest time-stamp of any transaction that executed write(Q)

successfully.

• R-timestamp(Q) is the largest time-stamp of any transaction that executed read(Q)

successfully.

 Imposes rules on read and write operations to ensure that

• Any conflicting operations are executed in timestamp order

• Out of order operations cause transaction rollback

 The timestamp-ordering protocol guarantees serializability since all the arcs in the precedence
graph are of the form:

Thus, there will be no cycles in the precedence graph

 Timestamp protocol ensures freedom from deadlock as no transaction ever waits.

 But the schedule may not be cascade-free, and may not even be recoverable.

QNO#19 What are deadlocks in DBMS? How can deadlocks be detected, prevented, or resolved in
concurrency control?

Consider the partial schedule

 Neither T3 nor T4 can make progress — executing lock-S(B) causes T4 to wait for T3 to release its
lock on B, while executing lock-X(A) causes T3 to wait for T4 to release its lock on A.

 Such a situation is called a deadlock.

• To handle a deadlock one of T3 or T4 must be rolled back

and its locks released.

 The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil.

 Starvation is also possible if concurrency control manager is badly designed. For example:

• A transaction may be waiting for an X-lock on an item, while a sequence of other

transactions request and are granted an S-lock on the same item.

• The same transaction is repeatedly rolled back due to deadlocks.

 Concurrency control manager can be designed to prevent starvation.

 System is deadlocked if there is a set of transactions such that every transaction in the set is
waiting for another transaction in the set.
Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Some
prevention strategies:

• Require that each transaction locks all its data items before it begins execution (pre-
declaration).

• Impose partial ordering of all data items and require that a transaction can lock data items
only in the order specified by the partial order (graph-based protocol).

More deadlock prevention techniques:

 wait-die scheme — non-preemptive

• Older transaction may wait for younger one to release data item.

• Younger transactions never wait for older ones; they are rolled back instead.

• A transaction may die several times before acquiring a lock

 wound-wait scheme — preemptive

• Older transaction wounds (forces rollback) of younger transaction instead of waiting for
it.

• Younger transactions may wait for older ones.

• Fewer rollbacks than wait-die scheme.

 In both schemes, a rolled back transactions is restarted with its original timestamp.

• Ensures that older transactions have precedence over newer ones, and starvation is thus
avoided.

 Timeout-Based Schemes:
 • A transaction waits for a lock only for a specified amount of time. After that, the wait
times out and the transaction is rolled back.

• Ensures that deadlocks get resolved by timeout if they occur

• Simple to implement

• But may roll back transaction unnecessarily in absence of deadlock

 Difficult to determine good value of the timeout interval.

• Starvation is also possible

Deadlock detection:

 Wait-for graph

• Vertices: transactions

• Edge from Ti Tj. : if Ti is waiting for a lock held in conflicting mode byTj

 The system is in a deadlock state if and only if the wait-for graph has a cycle.

 Invoke a deadlock-detection algorithm periodically to look for cycles.

Wait-for graph without a cycle Wait-for graph with a cycle

Deadlock Recovery:

 When deadlock is detected :

• Some transaction will have to rolled back (made a victim) to break deadlock cycle.

 Select that transaction as victim that will incur minimum cost

• Rollback -- determine how far to roll back transaction

 Total rollback: Abort the transaction and then restart it.

 Partial rollback: Roll back victim transaction only as far as necessary to release
locks that another transaction in cycle is waiting for

 Starvation can happen (why?)

 • One solution: oldest transaction in the deadlock set is never chosen as victim

QNO#20 What are the key differences between traditional DBMS and big data systems like Hadoop
in terms of data storage and processing?

Data storage

Feature Traditional DBMS Hadoop (Big Data Systems)

Structured (tables with fixed Structured, semi-structured, and unstructured (text,
Data Type
schemas) logs, images, etc.)
Centralized or vertically scalable Distributed file system (e.g., HDFS); horizontally
Storage Model
(scale-up) scalable (scale-out)
Storage
Local storage or SAN/NAS Commodity hardware across a cluster
Location
Schema-on-write (define schema Schema-on-read (schema applied when reading
Schema
before storing) data)
Capacity Terabytes (TBs) Petabytes (PBs) and beyond

Data Processing

Feature Traditional DBMS Hadoop (Big Data Systems)

Row-based transactional Batch processing (MapReduce, Spark) and
Processing Model
processing (OLTP) streaming (Kafka, Flink)
Query Language SQL MapReduce (Java), HiveQL, Pig, Spark SQL
Limited in classic Hadoop; improved with
Real-time Processing Strong (ACID-compliant)
tools like Spark and Flink
Concurrency & High concurrency, full ACID Limited transaction support, focuses on
Transactions support eventual consistency
Processing moves to where data resides (data
Data Locality Data fetched to processing
locality optimization)

QNO#21 . Explain the role of HDFS (Hadoop Distributed File System) in the Hadoop ecosystem.
How does it handle large-scale data storage compared to a DBMS

What is HDFS?

HDFS (Hadoop Distributed File System) is the foundation of storage in the Hadoop ecosystem. It
enables the reliable, scalable, and distributed storage of large datasets across clusters of inexpensive
hardware.

Role of HDFS in Hadoop

 1. Central Storage Layer
All other components in Hadoop (like MapReduce, Hive, Pig, Spark) rely on HDFS to store and
retrieve data.
2. Storage for Big Data Workloads
Handles very large files (gigabytes to petabytes) by splitting them into blocks and storing them
across multiple nodes.
3. Supports Fault-Tolerant Processing
Works closely with Hadoop's processing engines (e.g., MapReduce) to ensure computation can
continue even when hardware fails.
4. Optimized for Streaming Access
Designed for high-throughput, streaming reads and writes, not for low-latency, small updates.

Feature HDFS Traditional DBMS

Purpose Large-scale data storage & batch processing OLTP (transaction processing)
Handles all types: structured, semi-structured,
Data Types Mostly structured
unstructured
Scales vertically (more powerful
Scalability Scales horizontally (add more cheap machines)
servers)
Fault
Built-in via data replication Needs backup/restore mechanisms
Tolerance
Frequent updates and deletes
Update Model Write-once, read-many
supported
Schema Schema-on-read (flexible) Schema-on-write (rigid, predefined)

QNO#22 How does the MapReduce programming model work in Hadoop, and how is it different
from SQL-based querying in DBMS

What is MapReduce?

MapReduce is a programming model used in Hadoop to process large-scale datasets in a distributed

manner across a cluster of machines. It breaks computation into two main phases:

1. Map Phase

 Input: Key-value pairs (e.g., <offset, line> from a text file)

 Operation: The Map() function processes each pair and emits intermediate key-value pairs.

🧱 2. Shuffle & Sort Phase

 Intermediate results are shuffled and sorted by key.

 Ensures that all values associated with the same key go to the same reducer.

🧱 3. Reduce Phase

 The Reduce() function processes the grouped intermediate data to generate final output.

SQL-Based Querying in DBMS

  In a traditional RDBMS, users write queries using SQL (e.g., SELECT, JOIN, GROUP BY).
 The DBMS engine parses, optimizes, and executes these queries directly on structured data.
 SQL is declarative: you specify what you want, not how to compute it.

Key Differences: MapReduce vs. SQL

Feature MapReduce (Hadoop) SQL-Based Querying (DBMS)

Paradigm Procedural (you define how) Declarative (you define what)

Data Type Support Structured, semi-structured, unstructured Mostly structured

Moderate scale, vertical or

Scalability Massive scale, horizontal (thousands of nodes)
clustered

Usually requires additional

Fault Tolerance Built-in with task re-execution
setup

Latency High (batch processing) Low (fast query response)

Use Case Batch analytics, ETL, log processing Real-time queries, transactions

Programming Java, Python, or high-level tools like Hive

SQL
Language (SQL-like)

QNO#23 What are the limitations of traditional RDBMS that Hadoop addresses in big data
environments?

Limitations of Traditional RDBMS That Hadoop Addresses in Big Data Environments

Traditional Relational Database Management Systems (RDBMS) are excellent for structured data
and transactional workloads, but they face significant challenges in big data environments. Here's how
Hadoop overcomes these limitations:

1. Limited Scalability

 RDBMS: Typically scales vertically (by upgrading to more powerful hardware), which is
expensive and has limits.
 Hadoop: Scales horizontally by adding more inexpensive commodity nodes to the cluster.

✅ Hadoop allows near-infinite scaling at low cost.

2. Inability to Handle Unstructured Data

 RDBMS: Designed for structured data with fixed schemas (tables, rows, columns).
 Hadoop: Handles structured, semi-structured, and unstructured data (text, images, logs,
JSON, video, etc.).
✅ Hadoop is schema-flexible and supports diverse data types.

3. Cost of Storage and Processing

 RDBMS: High cost due to proprietary software and expensive storage systems.
 Hadoop: Uses open-source software and commodity hardware, significantly reducing costs.

✅ Hadoop is budget-friendly for storing and processing massive datasets.

4. Performance Bottlenecks with Large Volumes

 RDBMS: Performance degrades with large data volumes (terabytes or more).

 Hadoop: Designed to process petabyte-scale data efficiently using distributed computing
(MapReduce/Spark).

✅ Hadoop handles massive datasets without performance drop-offs.

5. Rigid Schema and Predefined Structures

 RDBMS: Enforces a schema-on-write approach — schema must be defined before inserting

data.
 Hadoop: Follows schema-on-read — schema is applied only when reading the data.

✅ Hadoop offers more flexibility in data ingestion and analysis.

6. Limited Fault Tolerance

 RDBMS: Uses transaction logs and replication, but recovery is complex and may require manual
intervention.
 Hadoop (HDFS): Automatically replicates data blocks across multiple nodes for fault
tolerance.

✅ Hadoop is highly resilient to hardware failures.

7. Batch and Parallel Processing Limitations

 RDBMS: Optimized for OLTP (transactional) systems; less effective for parallel batch
processing.
 Hadoop: Built for batch and parallel processing via MapReduce or Spark.

✅ Hadoop processes large datasets in parallel, speeding up analytics.

QNO#24 Describe how data replication in HDFS ensures fault tolerance. How does this compare
with backup strategies in DBMS?

How HDFS Ensures Fault Tolerance Through Data Replication

HDFS (Hadoop Distributed File System) provides fault tolerance by replicating data blocks across
multiple nodes in the cluster.

🧱 Key Mechanism:

 Each file in HDFS is split into large blocks (e.g., 128MB or 256MB).
 Every block is replicated on multiple DataNodes — default replication factor is 3.

✅ Example:

If you store a 512MB file:

 It’s split into 4 blocks (128MB each).

 Each block is stored on 3 different nodes, possibly on different racks.

🔄 What Happens on Failure?

 If a DataNode fails, HDFS continues serving data from other replicas.

 NameNode detects failure and re-replicates missing blocks on healthy nodes.
 This ensures high availability and durability even in case of hardware failure.

🔸 How Backup Works in Traditional DBMS

RDBMS systems (e.g., MySQL, Oracle, SQL Server) handle fault tolerance using:

🔁 Backup Strategies:

1. Full backups – periodic copies of the entire database.

2. Incremental/differential backups – backup only changes since the last backup.
3. Transaction logs – record every change, allowing point-in-time recovery.

⚠️On Failure:

 Restore the latest backup.

 Apply transaction logs to bring the system to a consistent state.
 Downtime may occur during restoration.

QNO#25 What are the main differences between OLAP in traditional DBMS and big data
analytics frameworks like Hadoop or Spark?

 OLAP (Online Analytical Processing) refers to systems optimized for complex queries and
data analysis, typically involving large amounts of historical data for reporting, trend analysis,
and decision support.

Key Differences: Traditional OLAP vs. Hadoop/Spark-Based Analytics

Feature Traditional OLAP (DBMS) Big Data Analytics (Hadoop/Spark)

Architecture Centralized (data warehouse on RDBMS) Distributed (cluster-based)
 Feature Traditional OLAP (DBMS) Big Data Analytics (Hadoop/Spark)
Structured, semi-structured, and
Data Type Structured data only
unstructured data
Stored in star/snowflake schemas Stored in HDFS or distributed file
Storage
(normalized/denormalized) systems
Processing SQL-based OLAP engines (e.g., Oracle OLAP, Batch (MapReduce) or in-memory
Engine SQL Server Analysis Services) (Spark)
Higher in Hadoop (batch); Low in
Latency Low for pre-aggregated data
Spark (in-memory)
Horizontal scaling across thousands
Scalability Limited vertical scaling
of nodes
Query SQL-like tools (Hive, Spark SQL) +
SQL/MDX
Language code (Python, Scala, Java)
Lower (open-source, commodity
Cost High (enterprise licenses, powerful servers)
hardware)
Fault Built-in fault tolerance (HDFS
Manual backups, RAID
Tolerance replication, Spark DAG recovery)

QNO#26 How does Hadoop achieve scalability and parallelism, and why is this crucial for big data
analytics

🔹 What Is Hadoop?

Hadoop is an open-source big data framework designed to store and process massive datasets efficiently
across clusters of inexpensive, commodity hardware.

🚀 How Hadoop Achieves Scalability

1. Horizontal Scaling

o Add more nodes (machines) to increase storage and processing power.

o No need to upgrade hardware — just plug in more servers.
o Easily scales from a few nodes to thousands.

2. HDFS (Hadoop Distributed File System)

o Breaks files into blocks and distributes them across the cluster.
o Enables distributed storage without centralized bottlenecks.
o Automatically replicates data (default: 3 copies) for fault tolerance.

3. Flexible Architecture

o Hadoop clusters can dynamically grow or shrink.

o No need to reformat or migrate data for scaling.
⚡ How Hadoop Achieves Parallelism

1. MapReduce Programming Model

o Breaks computation into two phases: Map() and Reduce().

o Each task is processed in parallel across multiple nodes.
o Processing occurs where data is stored — avoids network bottlenecks.

2. Task Division

o Jobs are split into independent tasks (map tasks and reduce tasks).
o Tasks are executed simultaneously across the cluster.

3. YARN (Yet Another Resource Negotiator)

o Manages computing resources across Hadoop cluster.

o Allocates CPU and memory to different jobs in parallel.

Why Scalability and Parallelism Matter in Big Data Analytics

Challenge in Big Data How Hadoop Solves It

Volume (terabytes to petabytes) Horizontally scalable HDFS stores huge datasets.

Velocity (real-time or batch ingestion) Parallel processing shortens computation time.

Variety (structured, semi-structured, unstructured

Works with all data types in distributed fashion.
data)

Complex Computations MapReduce/Spark divide and conquer complex tasks.

Scales using commodity hardware — cheaper than

Cost Efficiency
RDBMS.

QNO#27 How does MongoDB handle schema design, and what are the benefits of a schema-less
model?

MongoDB is an open source, document-oriented database designed with both scalability and developer
agility in [Link] of storing your data in tables and rows as you would with a relational database, in
MongoDB you store JSON-like documents with dynamic schemas(schema-free, schema less).

 MongoDB does not need any pre-defined data schema

 Every document could have different data
 Benefits of Schema-Less Model

Benefit Description
Flexibility You can add/remove fields at any time without altering the entire collection.
Ideal for startups or evolving applications where requirements change
Agile Development
frequently.
Supports storing documents with varying structures — useful for IoT, user-
Heterogeneous Data
generated content, etc.
Developers can deploy new features without downtime or expensive
Faster Iterations
migrations.
Allows nested fields (documents within documents), reducing the need for
Embedded Documents
JOINs.
Performance You can denormalize data for faster reads without worrying about rigid
Optimization schemas.

QNO#28 What is a collection in MongoDB, and how does it compare to a table in RDBMS?

A collection in MongoDB is a grouping of documents similar to how a table in a relational

database (RDBMS) is a grouping of rows. However, there are some important differences:

Aspect MongoDB Collection RDBMS Table

Data Stores documents (JSON-like BSON
Stores rows with a fixed schema (columns)
Structure objects)
Schema-less — documents can have Schema-defined — every row has the same
Schema
different fields and types columns and data types
Very flexible, supports nested fields and
Flexibility Rigid, normalized data model
arrays
No native joins; uses $lookup for basic join-
Joins Supports complex joins natively
like operations
Ideal for evolving data and Best for structured, tabular data with strict
Use Cases
semi/unstructured information schema

QNO#29Explain the structure of a BSON document. How is it different from JSON?

Binary-encoded serialization of JSON-like documents

• Zero or more key/value pairs are stored as a single entity

• Each entry consists of a field name, a data type, and a value

• Large elements in a BSON document are prefixed with a length field to facilitate scanning

Key Differences Between BSON and JSON

 Feature BSON JSON
Format Binary-encoded Text-based
Supports additional types (Date, Binary, Limited to strings, numbers, booleans,
Data Types
ObjectId, Int32/64, Timestamp) arrays, objects, null
More compact for certain types; includes length Larger due to textual encoding and no
Size Efficiency
prefixes for faster traversal length prefixes
Faster parsing and traversal due to binary Slower to parse as text, needs
Speed
format and length prefixes conversion
Human
Not human-readable Human-readable and editable
Readability

QNO#30 What is the Cypher query language, and how is it used in graph databases like Neo4j?

Cypher - A Next-Generation Query Language

• Cypher was based on the power of SQL, but optimized specifically for graphs.

• The syntax is concise and straightforward, allowing users to easily simple andwrite all the normal
CRUD operations in a maintainable way.

• Neo4j CQL

• Is a query language for Neo4j Graph Database.

• Is a declarative pattern-matching language.

• Follows SQL like syntax.

• SyNtax is very simple and in human readable format.

Like Oracle SQL

• Neo4j CQL has commands to perform Database operations.

• Neo4j CQL supports many clauses such as WHERE, ORDER BY, etc., to write very complex
queries in an easy manner.

• Neo4j CQL supports some functions such as String, Aggregation. In addition to them, it also
supports some Relationship Functions.

 Data Modeling:
Define and organize data as interconnected nodes and relationships.
 Querying Relationships:
Easily express queries like "find friends of friends," "shortest path between two nodes," or
"common connections."
  Graph Analytics:
Perform operations like community detection, influence scoring, and traversal with intuitive
syntax.
 Updating Graphs:
Insert, update, and delete nodes/relationships with simple commands.

QNO#31 Explain the advantages of graph databases in performing recursive queries or deep
relationships.

Advantage Explanation
Graph databases store data as nodes and edges directly, mirroring relationships
Native Graph Structure
naturally without expensive JOINs.
Traversing connected nodes is fast because relationships are stored as pointers,
Efficient Traversals
enabling quick navigation from one node to its neighbors.
Recursive queries (like "all descendants" or "shortest path") are easily expressed
Flexible Depth Queries
and efficiently executed using graph query languages (Cypher, Gremlin).
Unlike relational databases that require multiple JOINs for recursive queries
Avoids Costly Joins (which can be very expensive), graph DBs handle these natively with simple
traversals.
Each node directly references its connected nodes, allowing constant-time
Index-Free Adjacency
neighbor access regardless of dataset size.
Intuitive Query Languages like Cypher allow concise, expressive queries to explore recursive
Languages patterns, paths, and cycles without complex SQL recursion or procedural code.
Handles Complex, Graphs can naturally represent irregular or changing relationship patterns without
Evolving Schemas schema redesign.