DATABASE MANAGEMENT SYSTEM

Answer: (iii) both (a) and (b)

Explanation: Serializability (conflict or view) can be ensured by both locking protocols (2PL, strict 2PL) and timestamp ordering protocols. Locking prevents conflicting operations via locks; timestamping orders transactions by timestamps. Either mechanism or hybrid can guarantee serializability. Option checks "both locking and time stamping" as valid concurrency control methods.

Answer: (iii) B+ tree allows rapid random access as well as rapid sequential access

Explanation: B+ tree is variant of B-tree where all records stored in leaf nodes linked as linked list. Provides rapid random access via tree traversal (log N) and rapid sequential access via leaf chain. B tree allows random but sequential requires inorder traversal slower. B+ is preferred for indexes and range queries.

Answer: (ii) producing detailed summary or exception report

Explanation: Transaction Processing System (TPS/OLTP) handles routine business transactions: recording activity, confirming actions, maintaining data integrity, ACID. Producing detailed summary or exception reports is part of MIS/DSS or OLAP, not core TPS. TPS focuses on operational recording, not analytical summaries.

Answer: (iii) Database Administrator

Explanation: DBA = Database Administrator - person responsible for design, implementation, maintenance, security, backup, performance tuning of database. Data Administrator is broader organizational role, Data Bank Administrator is not standard.

Primary vs Secondary Index:

Primary Index: Ordered file on ordering key field (primary key or ordering field), sparse or dense, one per file, determines physical order (clustering). Example: File ordered by rollno, primary index on rollno. Has index entry per block. Cannot have many.

Secondary Index: On non-ordering field (any attribute), dense, may be many secondary indexes per file, does not determine file order, needs extra level (bucket for duplicates). Example: Index on name or department where file not ordered by that. Secondary is non-clustering, requires more entries.

Differences: Primary is on ordered key, reflects block anchors, sparse, clustering; Secondary is on non-ordered, dense, non-clustering, allows duplicates via buckets. Primary has unique entries per block, secondary may have many entries per value.

Bad Sector Remapping Effect on Retrieval Rates:

Disks have spare sectors; disk controller remaps bad sectors transparently to spare area (defect management). List maintained in defect map (P-list, G-list). When mapped, logical block accessed via redirect.

Effect on retrieval:

• Sequential access: Remapped sectors are at different physical location (spare area elsewhere), so sequential scan that was contiguous becomes random seek to spare, increasing seek time, breaking sequentiality, lowering throughput especially for large sequential reads.
• Random access: Minor impact - still one seek, but may add slight latency due to lookup and possible extra seek to spare cylinder.
• Caching: If remapped sector cached, less impact, but first access incurs penalty.
• Throughput drops proportionally to number of remapped sectors; heavily remapped disk sees degraded sequential rate (e.g., 10-30% slower).

Mitigation: Controller maintains translation table; OS unaware but performance variance observed. SMART monitors reallocated count.

Two-Phase Locking Protocol (2PL) & Conflict Serializability:

2PL: Transaction has growing phase (acquire locks, no unlock) and shrinking phase (release locks, no new locks). Ensures serializability but may deadlock. Strict 2PL holds exclusive locks till commit. Example: T1 locks A, B in growing, then unlocks.

Conflict Serializability: Schedule is conflict serializable if its conflict graph (precedence graph) is acyclic. Two operations conflict if they are from different transactions, on same item, at least one is write (RW, WR, WW). Graph has edge Ti -> Tj if operation of Ti conflicts before Tj.

Relationship: 2PL guarantees conflict serializability. Proof via lock points - transactions ordered by lock point (when last lock acquired). If Ti -> Tj in conflict, Ti's lock point before Tj's, no cycle. Rigorous 2PL holds.

Example: Schedule R1(A) W2(A) is not allowed under 2PL without proper lock ordering, ensures serial schedule T1->T2 or T2->T1.

Conflict serializable schedule can be transformed to serial via swapping non-conflicting operations.

Show 2PL Ensures Conflict Serializability and Serialization by Lock Points:

Proof: Consider any schedule S generated by 2PL-compliant transactions. Let lock point of Ti be the moment Ti has acquired its last lock (end of growing phase). Lemma: If Ti precedes Tj in a conflict (operation o_i before o_j conflicting), then lock_point(Ti) < lock_point(Tj). Because to perform conflicting operations, both need lock on same item; conflicting lock types (X vs S/X) exclude. Since Ti held lock before Tj could acquire it, Ti must have acquired it first and since 2PL forbids acquiring after unlocking, Ti's lock point before Tj's first conflicting lock release.

If schedule had cycle Ti -> Tj -> ... -> Ti, then lock points would have cycle lock(Ti) < lock(Tj) < ... < lock(Ti) impossible. Hence conflict graph acyclic -> conflict serializable.

Serialization order: Sort transactions by lock points ascending. That order is a serial schedule conflict-equivalent to S, because all conflicting pairs respect lock point order. Strict 2PL also ensures recoverability.

Example holds.

ACID Properties (Transaction):

• Atomicity: Transaction is all-or-nothing indivisible. Either all operations done or none upon failure, via log/undo. Example: Transfer money debit and credit both or none.

• Consistency: Transaction transforms database from one consistent state (satisfying integrity constraints, invariants) to another. If constraints violated, abort.

• Isolation: Concurrent transactions appear isolated, intermediate states hidden, final result as if serial. Via concurrency control (2PL, MVCC). Prevents dirty/read phenomena.

• Durability: Once committed, results persist despite failures (via write-ahead logging, stable storage, checkpoints). Committed data not lost on crash.

Together ensure reliable transaction processing despite concurrency and failures. Example: Banking transaction respects ACID: atomic transfer, consistent balance >=0, isolated from others, durable after commit.

Given schedule S' with immediate modification, strict 2PL, common buffer/log, initial A=B=C=D=0. Sequence: T1 R(A) A=A+5 commit (A=5 logged), T2 R(B) B=B+5 (B=5 uncommitted), T3 R(C) C=C+5; C=C+5 (C=10 uncommitted, but two increments? note C incremented twice to 10), T4 R(A) A=A+5 (A reads 5, writes 10), R(D) D=D+5 commit (D=5 committed), then T2 commit then T3 commit.

Immediate modification means uncommitted updates may be written to disk before commit (steal), so undo needed. Strict 2PL holds X locks till commit, so T2 holds B, T3 holds C, T4 holds A,D till commit.

Failure occurs at T2:commit statement (T2 attempting commit, T4 already committed, T1 committed, T2 and T3 have not fully committed at failure point).

Recovery (UNDO/REDO via log analysis):
Log contains <T1 start>, <T1, A, 0,5>, <T1 commit>, <T2 start>, <T2, B,0,5>, <T3 start>, <T3, C,0,5>, <T3,C,5,10>, <T4 start>, <T4,A,5,10>, <T4,D,0,5>, <T4 commit> (steal may have flushed B,C,A). At failure, checkpoint analysis:

• REDO: T1 and T4 are committed (and flushed before failure) - redo their updates to ensure durability (A=10? Actually T1 A=5 then T4 overwrote A=10, so final A=10, D=5).
• UNDO: T2 and T3 are active/uncommitted at crash (T2 commit not completed, T3 not committed). Since immediate modification, their updates may be on disk and must be undone: B=0 (undo B 0->5), C=0 (undo C chain 0->5->10). Using undo log records in reverse.

If strict 2PL buffer sharing noted: no dirty read but dirty writes possible via buffer. After recovery, DB reflects only committed transactions: A=10, D=5, B=0, C=0, then T2/T3 will be restarted/aborted. Some textbooks show T2's commit record not yet written, so T2 also undone. Result: T1 and T4 persist.

Concurrency Control Techniques: Methods to ensure isolation and serializability when multiple transactions execute concurrently.

Techniques:

• Lock-Based: 2PL (growing/shrinking), Strict 2PL, Shared (S) and Exclusive (X) locks, prevents dirty read/write. Example: before read acquire S, before write acquire X.

• Timestamp Ordering: Assign timestamp TS(T), ensure conflict order follows timestamp via W-timestamp/R-timestamp, Thomas write rule for obsolete writes.

• Validation/Optimistic: Read phase, validation (check conflicts), write phase - no locking, abort if conflict (good for low contention).

• Multiversion (MVCC): Keep multiple versions for reads without locking, readers read snapshot.

• Granularity: Multiple granularity locks (IS, IX, SIX) for hierarchy.

Goal: Prevent anomalies: lost update, dirty read, non-repeatable read, phantom. Provide serializable schedule.

Short note on Database Recovery:

Recovery restores database to consistent state after failure (crash, power, media) ensuring atomicity and durability via ACID.

Techniques:

• Log-Based: Write-Ahead Logging (WAL) records <T, X, old, new> before DB update to stable log. Undo/Redo.

• Shadow Paging: Keep shadow copy, switch pointer on commit.

• Checkpoints: Periodic flush, log checkpoint record to bound recovery time.

Recovery types: Immediate (steal, uncommitted updates on disk need UNDO) vs Deferred (no steal, only REDO).

ARIES algorithm: Analysis (identify active/dirty), Redo (repeat history), Undo (rollback loser transactions).

Example: Log <T1 start>, <T1,A,0,5>, commit. Crash after T1 commit but before flush - redo applies A=5. If T2 uncommitted had B=5 on disk, undo restores B=0.

Importance: prevents loss, ensures durability.