Database Management System

Data Independence: Physical vs. Logical

Data Independence is the architectural capacity to modify a database schema at one level of the three-schema architecture without having to alter the schemas at subsequent higher levels.

• Physical Data Independence: The ability to alter the physical storage structure, file organization, or indexing mechanisms (internal schema) without altering the logical/conceptual schema or application programs.
• Logical Data Independence: The ability to modify the conceptual schema (adding new attributes, splitting entities) without requiring changes to existing external views or user queries. Logical independence is substantially harder to achieve than physical independence.

Weak Entity Set and ER Representation

A Weak Entity Set is an entity set that does not possess sufficient key attributes to form its own primary key and depends existence-wise on a parent/identifying entity set.

• Identifying Key (Discriminator): Its records are uniquely distinguished only when combined with the primary key of the owner entity.
• ER Diagram Representation:
  • Weak entity set: Represented by a double rectangle.
  • Identifying relationship: Represented by a double diamond.
  • Partial discriminator key: Represented with a dashed underline inside the weak entity attribute oval.

Condition for Boyce-Codd Normal Form (BCNF)

A relational schema $R$ is in Boyce-Codd Normal Form (BCNF) if and only if for every non-trivial functional dependency $X \rightarrow Y$ holding over $R$:

$X$ must be a superkey of relation $R$.

In other words, BCNF strictly eliminates all functional dependencies where the determinant ($X$) is not a candidate key, thereby removing anomalies that can survive 3NF when overlapping candidate keys exist.

ACID Properties of Database Transactions

1. Atomicity (All-or-Nothing): Guarantees that all operations within a transaction execute completely or none of them are reflected in the database.
2. Consistency (Preservation of Invariants): Ensures the transaction transitions the database from one valid state satisfying all integrity constraints to another valid state.
3. Isolation (Concurrent Independence): Guarantees that the intermediate states of concurrently executing transactions are invisible to one another.
4. Durability (Persistence): Ensures that once a transaction commits, its state updates persist permanently in non-volatile storage, surviving subsequent system crashes.

DELETE vs. TRUNCATE in SQL

Entity-Relationship Modeling & Relational Schema Mapping

a. Entity-Relationship (ER) Architecture

• Entities & Attributes:
  • DEPARTMENT: {$\underline{\text{DeptID}}$, DeptName, OfficeLocation}
  • PROFESSOR: {$\underline{\text{EmployeeID}}$, Name, Qualification}
  • COURSE: {$\underline{\text{CourseCode}}$, CourseTitle, Credits}
  • STUDENT: {$\underline{\text{RollNo}}$, FullName, Semester}
• Relationships & Cardinalities:
  • Chairs (PROFESSOR to DEPARTMENT): $1:1$ (One professor chairs one department).
  • Works_In (PROFESSOR to DEPARTMENT): $N:1$ (Many professors belong to one department).
  • Offers (DEPARTMENT to COURSE): $1:N$ (One department offers many courses).
  • Enrolls (STUDENT to COURSE): $M:N$ (Many students enroll in many courses; Relationship attribute: Grade, AcademicYear).

b. Relational Schema Mapping

1. DEPARTMENT ($\underline{\text{DeptID}}$, DeptName, OfficeLocation, ChairProfID*)
   • Foreign Key: ChairProfID references PROFESSOR(EmployeeID) (Unique).
2. PROFESSOR ($\underline{\text{EmployeeID}}$, Name, Qualification, DeptID*)
   • Foreign Key: DeptID references DEPARTMENT(DeptID).
3. COURSE ($\underline{\text{CourseCode}}$, CourseTitle, Credits, DeptID*)
   • Foreign Key: DeptID references DEPARTMENT(DeptID).
4. STUDENT ($\underline{\text{RollNo}}$, FullName, Semester)
5. ENROLLMENT ($\underline{\text{RollNo*}, \text{CourseCode*}}$, AcademicYear, Grade)
   • Composite Primary Key: (RollNo, CourseCode)
   • Foreign Keys: RollNo references STUDENT(RollNo), CourseCode references COURSE(CourseCode).

Relational Algebra and SQL Queries

a. Employees working in ‘Kathmandu’

• Relational Algebra:

  Swipe to see the full formula↔

  $$\Pi_{\text{EmpName, Salary}} (\text{EMPLOYEE} \bowtie_{\text{EMPLOYEE.DeptNo = DEPARTMENT.DeptNo}} (\sigma_{\text{Location = 'Kathmandu'}} (\text{DEPARTMENT})))$$
• SQL Query:

  SELECT E.EmpName, E.Salary
  FROM EMPLOYEE E
  JOIN DEPARTMENT D ON E.DeptNo = D.DeptNo
  WHERE D.Location = 'Kathmandu';
  

b. Project with the highest budget

• SQL Query:

  SELECT ProjNo, ProjName, Budget
  FROM PROJECT
  WHERE Budget = (SELECT MAX(Budget) FROM PROJECT);
  

c. Employees working on all projects managed by Dept 10 (Relational Division)

• Relational Algebra:

  Swipe to see the full formula↔

  $$\Pi_{\text{EmpID, ProjNo}}(\text{WORKS\_ON}) \div \Pi_{\text{ProjNo}}(\sigma_{\text{DeptNo = 10}}(\text{PROJECT}))$$
• SQL Query:

  SELECT E.EmpName
  FROM EMPLOYEE E
  WHERE NOT EXISTS (
      SELECT P.ProjNo
      FROM PROJECT P
      WHERE P.DeptNo = 10
      EXCEPT
      SELECT W.ProjNo
      FROM WORKS_ON W
      WHERE W.EmpID = E.EmpID
  );
  

d. Department Name and total salary for departments with > 5 employees

• SQL Query:

  SELECT D.DeptName, SUM(E.Salary) AS TotalSalaryExpenditure
  FROM DEPARTMENT D
  JOIN EMPLOYEE E ON D.DeptNo = E.DeptNo
  GROUP BY D.DeptNo, D.DeptName
  HAVING COUNT(E.EmpID) > 5;
  

e. Update salary by +10% for employees on ‘Core Banking Upgrade’

• SQL Query:

  UPDATE EMPLOYEE
  SET Salary = Salary * 1.10
  WHERE EmpID IN (
      SELECT W.EmpID
      FROM WORKS_ON W
      JOIN PROJECT P ON W.ProjNo = P.ProjNo
      WHERE P.ProjName = 'Core Banking Upgrade'
  );
  

Database Normalization Analysis

a. Finding Candidate Keys

Compute attribute closures using $F$:

1. Closure of $(A, C)$:
   • $(AC)^+ = \{A, C\}$
   • $A \rightarrow B \implies \{A, B, C\}$
   • $BC \rightarrow D \implies \{A, B, C, D\}$
   • $D \rightarrow E \implies \{A, B, C, D, E\}$
   • $E \rightarrow G \implies \{A, B, C, D, E, G\} = R$
   • Thus, $(A, C)$ is a candidate key.
2. From $G \rightarrow A$: Closure of $(G, C)^+ = \{G, C, A, B, D, E\} = R$. Thus $(G, C)$ is a candidate key.
3. From $E \rightarrow G$: Closure of $(E, C)^+ = R$. Thus $(E, C)$ is a candidate key.
4. From $D \rightarrow E$: Closure of $(D, C)^+ = R$. Thus $(D, C)$ is a candidate key.
5. From $BC \rightarrow D$: Closure of $(B, C)^+ = R$. Thus $(B, C)$ is a candidate key.

Prime Attributes: $\{A, B, C, D, E, G\}$ (Every attribute is a member of at least one candidate key).

b. Determining Highest Normal Form

• 1NF: Satisfied (atomic attributes).
• 2NF: A relation is in 2NF if no non-prime attribute is partially dependent on any candidate key. Since all attributes in $R$ are prime attributes, there are no non-prime attributes. Therefore, $R$ is in 2NF.
• 3NF: For every $X \rightarrow Y$, either $X$ is a superkey OR $Y$ is a prime attribute.
  • In $A \rightarrow B$: $A$ is not a superkey, but $B$ is a prime attribute (holds!).
  • In $D \rightarrow E$: $D$ is not a superkey, but $E$ is prime (holds!).
  • In $E \rightarrow G$: $E$ is not a superkey, but $G$ is prime (holds!).
  • In $G \rightarrow A$: $G$ is not a superkey, but $A$ is prime (holds!).
  • Therefore, $R$ is in 3NF.
• BCNF: Requires $X$ to be a superkey for every non-trivial $X \rightarrow Y$. In $A \rightarrow B$, $A$ is not a superkey (closure of $A$ is $\{A, B\} \neq R$). Hence, $R$ is NOT in BCNF.
• Highest Normal Form: 3NF.

c. Decomposing into BCNF

To eliminate violations of BCNF:

1. Identify violating dependency: $A \rightarrow B$ ($A^+ = \{A, B\}$).
   • Decompose $R$ into $R_1(A, B)$ with candidate key $A$.
   • Remaining relation: $R_2(A, C, D, E, G)$.
2. In $R_2$, candidate keys are $(A, C), (D, C), (E, C), (G, C)$.
   • Dependencies holding in $R_2$: $AC \rightarrow D, D \rightarrow E, E \rightarrow G, G \rightarrow A$.
   • $D \rightarrow E$ violates BCNF ($D$ is not a superkey of $R_2$).
   • Decompose $R_2$ into $R_{21}(D, E)$ and $R_{22}(A, C, D, G)$.
3. In $R_{22}$, $G \rightarrow A$ violates BCNF.
   • Decompose into $R_{221}(G, A)$ and $R_{222}(C, D, G)$.
4. In $R_{222}$, $D \rightarrow G$ (via $D \rightarrow E \rightarrow G$).
   • Decompose into $R_{2221}(D, G)$ and $R_{2222}(C, D)$.

Final BCNF Relations:

• $R_1(A, B)$, $R_2(D, E)$, $R_3(E, G)$, $R_4(G, A)$, $R_5(B, C, D)$. This decomposition is strictly lossless.

Concurrency Control and Database Recovery Techniques

a. Two-Phase Locking (2PL) Protocols

The 2PL protocol guarantees serializability of concurrent execution schedules by dividing transaction lock management into two distinct phases:

1. Growing Phase: The transaction may obtain new locks (shared or exclusive) but cannot release any lock.
2. Shrinking Phase: The transaction may release locks but cannot acquire any new locks.

Variations of 2PL:

• Basic 2PL: Locks are acquired as needed during execution and released gradually once the lock point is reached. Susceptible to cascading rollbacks and deadlocks.
• Conservative (Static) 2PL: The transaction predeclares and locks all required data items simultaneously before commencing execution. Prevents deadlocks completely, but reduces concurrency.
• Strict 2PL: All exclusive (write) locks acquired by a transaction are held until the transaction explicitly commits or aborts.
• Rigorous 2PL: Both shared (read) and exclusive (write) locks are held until transaction commit/abort.

b. Prevention of Cascading Aborts by Strict 2PL

A cascading abort occurs when transaction $T_1$ writes an uncommitted value to item $X$, transaction $T_2$ reads that dirty value of $X$, and subsequent failure of $T_1$ forces $T_2$ to abort as well. In Strict 2PL, transaction $T_1$ never releases its exclusive lock on $X$ until its commit or abort is logged. Consequently, $T_2$ cannot obtain a shared read lock on $X$ and is blocked from reading uncommitted data. Thus, cascading rollbacks are eliminated.

c. Write-Ahead Logging (WAL) and Recovery

The Write-Ahead Logging (WAL) protocol mandates:

1. The log record representing an update must be flushed to non-volatile disk before the modified data page is written to disk.
2. All log records for a transaction must be flushed before the commit record is recorded.

Deferred Update vs. Immediate Update:

• Deferred Update (NO-UNDO/REDO): Updates are recorded only in the transaction log during execution; actual database buffers on disk are updated only after the transaction successfully commits. If system crashes before commit, no database rollback is needed (NO-UNDO). Committed transactions are redone (REDO).
• Immediate Update (UNDO/REDO): Updates are applied to active database buffers and may be written to disk before the transaction commits. If a crash occurs before commit, uncommitted updates on disk must be rolled back (UNDO). Committed updates must be reapplied (REDO).

Comprehensive Enterprise Database Architecture Case Analysis: MeroBank

a. Transaction Isolation Levels and Recommendations

Architectural Recommendations:

1. Digital Fund Transfers (Debit/Credit): Must run under Repeatable Read or Serializable (or Snapshot Isolation with first-committer-wins conflict detection). When Account A transfers funds to Account B, both accounts must be debited and credited atomically without dirty reads or phantom balance updates.
2. Branch Manager Audit & Analytics Reports: Must run under Read Committed (or Snapshot Isolation). Long-running read queries take a point-in-time snapshot, ensuring they never acquire shared read locks that block customer transactions.

---

b. Multi-Version Concurrency Control (MVCC) Solution

In traditional locking systems, readers block writers and writers block readers. MVCC resolves this contention by creating a new version of a data record whenever an update occurs:

• How MVCC Works: Each row maintains two system timestamps: xmin (creation transaction ID) and xmax (deletion/expiration transaction ID).
• Read Operations: When a transaction $T$ reads a record, the database engine returns the highest committed version of the row where xmin $\le T_{\text{start}}$ and xmax $> T_{\text{start}}$.
• Benefit for MeroBank: Long-running reporting queries read old, committed snapshots of account records while simultaneous customer fund transfers create new row versions without being blocked. Readers never block writers, and writers never block readers.

---

c. Indexing Strategy: B+ Tree vs. Hash Indexing

1. Customer Account Lookup (AccountNo exact match):
   • Hash Index: Provides $O(1)$ time complexity for exact point queries (WHERE AccountNo = '01002345'). However, Hash indexes do not support range scans, sorting, or prefix matching.
   • B+ Tree Index: Provides $O(\log N)$ lookup and supports range filtering.
   • Recommendation: Utilize a Unique B+ Tree Index on AccountNo as the clustered index. B+ trees maintain sorted leaf node linkage, which handles both point lookups and branch account sweeps efficiently.
2. Transaction History Queries (WHERE TxnDate BETWEEN '2081-01-01' AND '2081-01-31'):
   • Recommendation: Implement a Composite Non-Clustered B+ Tree Index on (AccountNo, TxnDate DESC). The B+ tree leaf nodes contain contiguous doubly linked pointers, allowing fast index range scans for statement generation without full table scans.

---

d. Disaster Recovery and High Availability (HA) Architecture

To satisfy MeroBank’s RPO $\approx 0$ (zero data loss) and RTO $< 15$ minutes:

1. Fuzzy Checkpointing:
   • Instead of flushing all dirty buffer pages to disk during a checkpoint (which halts disk I/O), the DBMS writes a CHECKPOINT_BEGIN record and records dirty page table (DPT) addresses. Dirty pages are written asynchronously in the background. The CHECKPOINT_END record allows the recovery engine to pinpoint the earliest log record required during recovery.
2. ARIES Recovery Algorithm (Analysis, Redo, Undo):
   • Analysis Phase: Scans the log forward from the latest checkpoint to reconstruct the active transaction table and DPT.
   • Redo Phase: Scans forward from the earliest unwritten page LSN to redo all logged operations (both committed and uncommitted) to restore the exact pre-crash state.
   • Undo Phase: Scans backward to undo the changes of all active (uncommitted) transactions, writing compensating log records (CLRs).
3. Active-Standby Database Replication:
   • Deploy Synchronous Physical Replication to a secondary standby database in a separate seismic zone (e.g., Pokhara or Butwal).
   • Core transactions commit only after write-ahead logs are synchronously acknowledged by the standby instance.
   • Automatic Failover: An automated cluster heartbeat manager triggers standby promotion within 60 to 90 seconds in the event of primary hardware failure, easily beating the 15-minute RTO target.