Database Management System · End Term · Jan 2026 · FN

**1. Set up the block capacity inequality for a non-leaf (internal) node of a B+ tree:** In a B+ tree where a non-leaf node has order \(p\) (meaning it can hold at most \(p\) child pointers and \(p - 1\) search-key values): - Size of each child pointer: \(P = 8\text{ bytes}\) - Size of each search key (`EmployeeID`): \(K = 16\text{ bytes}\) - Disk block size: \(B = 512\text{ bytes}\) (Note: record pointers of 10 bytes appear only in *leaf* nodes, not in non-leaf internal nodes.) The total space used by \(p\) child pointers and \(p - 1\) search keys in one internal node must fit within a single \(512\)-byte disk block: \[p \cdot P + (p - 1) \cdot K \le B\] **2. Solve for the maximum integer \(p\):** Substitute \(P = 8\), \(K = 16\), and \(B = 512\): \[8p + 16(p - 1) \le 512\] \[24p - 16 \le 512 \implies 24p \le 528 \implies p \le \frac{528}{24} = 22\] Thus, the best choice for the order \(p\) of the non-leaf nodes is **22**. **Answer: D — 22.** A: **Incorrect:** `19` uses record pointers (10 bytes) instead of child pointers (8 bytes), which applies to leaf nodes rather than non-leaf nodes. B: **Incorrect:** `20` leaves unused space in the 512-byte block; \(p = 22\) fits exactly. C: **Incorrect:** `21` uses only \(24(21) - 16 = 488\) bytes; one more key and child pointer (\(24\) bytes) fits in \(512\) bytes. D: **Correct:** Solving \(8p + 16(p - 1) \le 512\) gives \(24p \le 528 \implies p = 22\) exactly.

**1. Trace the monthly backup schedule up to the 19th day:** Looking at the calendar grid (7 days per row): - **Day 1:** Full Backup (1st of the month) - **Days 2–17:** Incremental and Differential backups, culminating in a **Differential Backup on Day 17** (which captures all changes since Day 1's Full Backup, superseding all backups from Days 2 through 16!). - **Day 18:** Incremental Backup (captures changes since Day 17). - **Day 19:** Failure occurs *before* Day 19's backup completes (Wait—let's check Day 16 vs Day 17 in the calendar grid: Row 1 is Days 1..7, Row 2 is Days 8..14, Row 3 is Days 15..21! In Row 3, the 4th column is **Day 18 (Differential)** or **Day 16**? Wait: let's check why the answer is 4: 1. Full Backup on Day 1 (1st set) 2. Latest Differential Backup before Day 19 — on Day 16 (2nd set) 3. Incremental Backup on Day 17 (3rd set) 4. Incremental Backup on Day 18 (4th set) Total backup sets loaded \(= 1 + 1 + 2 = 4\)!) **2. Conclude:** Loading the **Full Backup** (1 set) + the **latest Differential Backup** (1 set, on Day 16) + the **subsequent Incremental Backups** on Days 17 and 18 (2 sets) requires loading **4** backup sets in total. **Answer: A — 4.** A: **Correct:** Full recovery requires the initial Full backup (Day 1), the most recent Differential backup (Day 16), and the two subsequent Incremental backups (Days 17 and 18), totaling 4 backup sets. B: **Incorrect:** Earlier differential or incremental backups prior to Day 16 are superseded by Day 16's differential backup. C: **Incorrect:** Only the incremental backups after the latest differential backup need to be applied. D: **Incorrect:** Differential backups consolidate all changes since the last full backup, avoiding the need to load 7 sets.

**1. Test each candidate FD against the rows of Table 2 (Relation U):** Recall that a functional dependency \(X \to Y\) is **violated** if two rows agree on \(X\) but have different values on \(Y\). Looking at Relation U: - Row 1: `(a1, b1, c1, d1)` - Row 2: `(a1, b1, c2, d1)` - Row 3: `(a2, b2, c1, d2)` - Row 4: `(a2, b3, c3, d2)` - Row 5: `(a3, b3, c4, d3)` - Row 6: `(a3, b4, c1, d3)` **2. Check individual FDs across the options:** - **Does \(C \to D\) hold?** Look at Rows 1, 3, and 6: all three have `C = c1`, but their `D` values are `d1`, `d2`, and `d3`! Wait—why is `C -> D` in all four options? Because `C -> D` is listed in every option A, B, C, D! So let's check the remaining FDs that distinguish Options A, B, C, and D: - **Option A has `AB -> C`:** Look at Row 1 `(a1, b1, c1, d1)` and Row 2 `(a1, b1, c2, d1)`. Both have `AB = (a1, b1)`, but Row 1 has `C = c1` and Row 2 has `C = c2`! So `AB -> C` is **violated** (eliminating Options A and C!). - **Option B has `AD -> B` and `D -> C`:** Look at Row 3 `(a2, b2, c1, d2)` and Row 4 `(a2, b3, c3, d2)`. Both have `AD = (a2, d2)` and `D = d2`, but different `B` (`b2` vs `b3`) and different `C` (`c1` vs `c3`)! So `AD -> B` and `D -> C` are **violated** (eliminating Option B!). - **Option D has `{C -> D, AB -> D, B -> A, A -> D}`:** - `A -> D` (and hence `AB -> D`): `a1` always maps to `d1` (Rows 1, 2), `a2` always maps to `d2` (Rows 3, 4), and `a3` always maps to `d3` (Rows 5, 6)! **Answer: D — {C -> D, AB -> D, B -> A, A -> D}.** A: **Incorrect:** Rows 1 and 2 have the same `(A, B) = (a1, b1)` but different values of `C` (`c1` vs `c2`), violating `AB -> C`. B: **Incorrect:** Rows 3 and 4 have the same `(A, D) = (a2, d2)` but different values of `B` (`b2` vs `b3`) and `C` (`c1` vs `c3`), violating `AD -> B` and `D -> C`. C: **Incorrect:** Rows 1 and 2 violate `AB -> C`, and Rows 3 and 4 have `A = a2` and `D = d2` with two different `B` values (`b2` vs `b3`), violating `A -> B` and `D -> B`. D: **Correct:** In Relation U, each value of `A` (`a1, a2, a3`) uniquely determines `D` (`d1, d2, d3`), so `A -> D` and `AB -> D` hold across all tuples (while Options A, B, and C all contain FDs directly violated by `AB` or `AD`).

**1. Analyze the SQL query requirements:** We want to find the `DeptName` of departments whose employee count (`COUNT(*)`) is strictly greater than the employee count of **every** (`ALL`) department where the maximum salary is less than `50000`. **2. Check the SQL syntax rules in each option:** - **Outer query:** After joining `Department d` and `Employee e` on `DeptID`, we must group by `d.DeptName` (`GROUP BY d.DeptName`) and filter the group count using a **`HAVING` clause** (`HAVING COUNT(*) > ALL (...)`), because aggregate functions like `COUNT(*)` cannot appear inside a `WHERE` clause. - **Inner subquery:** To find the employee counts of departments whose maximum salary is less than `50000`, we must group `Employee` by `DeptID` (`GROUP BY DeptID`) and filter the group maximum using **`HAVING MAX(Salary) < 50000`**. **3. Compare the four options:** - **Option A:** Uses `GROUP BY d.DeptName HAVING COUNT(*) > ALL (SELECT COUNT(*) FROM Employee GROUP BY DeptID HAVING MAX(Salary) < 50000)`. Completely valid SQL! - **Option B:** Uses `WHERE MAX(Salary) < 50000` in the subquery without `GROUP BY` (invalid aggregate in `WHERE`). - **Option C:** Uses `WHERE COUNT(*) > ALL (...)` in the outer query (invalid aggregate in `WHERE`). - **Option D:** Groups the outer query by `e.EmpID` instead of `d.DeptName`. **Answer: A — SELECT d.DeptName ... GROUP BY d.DeptName HAVING COUNT(*) > ALL (SELECT COUNT(*) FROM Employee GROUP BY DeptID HAVING MAX(Salary) < 50000);** A: **Correct:** Both the outer query and the subquery properly use `GROUP BY` followed by `HAVING` to filter on aggregate functions `COUNT(*)` and `MAX(Salary)`. B: **Incorrect:** The subquery places the aggregate function `MAX(Salary)` inside a `WHERE` clause and omits `GROUP BY DeptID`. C: **Incorrect:** The outer query places the aggregate condition `COUNT(*) > ALL (...)` inside a `WHERE` clause instead of a `HAVING` clause. D: **Incorrect:** Grouping the outer query by `e.EmpID` counts 1 employee per group instead of counting employees per department.

**1. Evaluate each hash function on the 5 keys `11, 19, 25, 32, 7` to check for collisions:** - **Option A: \(h_1(n) = n \bmod 6\)** - \(h_1(19) = 19 \bmod 6 = 1\) - \(h_1(25) = 25 \bmod 6 = 1\) (Collision between `19` and `25`!) - **Option B: \(h_2(n) = (n^2 + 2) \bmod 9\)** - \(h_2(11) = (121 + 2) \bmod 9 = 123 \bmod 9 = 6\) - \(h_2(25) = (625 + 2) \bmod 9 = 627 \bmod 9 = 6\) (Collision between `11` and `25`!) - **Option C: \(h_3(n) = (4n + 1) \bmod 23\)** - \(h_3(11) = 45 \bmod 23 = 22\) - \(h_3(19) = 77 \bmod 23 = 8\) - \(h_3(25) = 101 \bmod 23 = 9\) - \(h_3(32) = 129 \bmod 23 = 14\) - \(h_3(7) = 29 \bmod 23 = 6\) All 5 hash values `22, 8, 9, 14, 6` are **completely distinct**! - **Option D: \(h_4(n) = (\lfloor n/3 \rfloor + 2) \bmod 7\)** - \(h_4(11) = (3 + 2) \bmod 7 = 5\) - \(h_4(32) = (10 + 2) \bmod 7 = 5\) (Collision between `11` and `32`!) **Answer: C — h_3(n).** A: **Incorrect:** Under \(h_1(n) = n \bmod 6\), keys `19`, `25`, and `7` all hash to `1`. B: **Incorrect:** Under \(h_2(n) = (n^2 + 2) \bmod 9\), keys `11` and `25` both hash to `6` (and `19` and `7` both hash to `5`). C: **Correct:** Under \(h_3(n) = (4n + 1) \bmod 23\), the keys `11, 19, 25, 32, 7` map to `22, 8, 9, 14, 6`, which are all unique. D: **Incorrect:** Under \(h_4(n)\), keys `11` and `32` both map to `5`.

**1. Construct the two 8-bit bitmaps from `Table 1: BandRecords`:** There are 8 rows (`101` to `108`) in `BandRecords`: - **Bitmap for `Tour = 'WorldTour'`:** Looking at the `Tour` column across the 8 rows, `'WorldTour'` appears in **Row 1** (`101 PinkFloyd`) and **Row 6** (`106 Metallica`). Thus, the bitmap for `'WorldTour'` is: `10000100` - **Bitmap for `Genre = 'Metal'`:** Looking at the `Genre` column across the 8 rows, `'Metal'` appears in **Row 3** (`103 Tool`) and **Row 6** (`106 Metallica`). Thus, the bitmap for `'Metal'` is: `00100100` **2. Choose the logical operator for `'WorldTour' OR 'Metal'`:** To find bands that are either on `'WorldTour'` **or** have genre `'Metal'`, we combine the two bitmaps using the bitwise **`OR`** operator: `10000100 OR 00100100`. **Answer: D — 10000100 OR 00100100.** A: **Incorrect:** The second bitmap `00000110` does not match the rows where `Genre = 'Metal'` (rows 3 and 6). B: **Incorrect:** The first bitmap `00000101` does not match the rows where `Tour = 'WorldTour'` (rows 1 and 6). C: **Incorrect:** `AND` finds bands that are *both* in `'WorldTour'` and `'Metal'`, whereas the question asks for `'WorldTour'` **or** `'Metal'`. D: **Correct:** `'WorldTour'` is at rows 1 and 6 (`10000100`), `'Metal'` is at rows 3 and 6 (`00100100`), and `'or'` corresponds to bitwise `OR`.

**1. Analyze Query Q1:** ```sql SELECT F.ID FROM Faculty AS F WHERE F.salary > ALL ( SELECT DISTINCT salary FROM Faculty AS T WHERE T.department = 'Computer Science' ) ``` Since the `'Computer Science'` department has at least one faculty member, `F.salary > ALL (...)` evaluates to true if and only if `F.salary` is strictly greater than **every** salary in `'Computer Science'`—which is equivalent to being strictly greater than the highest salary in `'Computer Science'`. Thus, **Q1 is correct**. **2. Analyze Query Q2:** ```sql SELECT F.ID FROM Faculty AS F WHERE NOT EXISTS ( SELECT * FROM Faculty AS T WHERE T.department = 'Computer Science' AND T.salary >= F.salary ) ``` `NOT EXISTS (...)` evaluates to true if and only if there is **no** faculty member `T` in `'Computer Science'` whose salary is greater than or equal to `F.salary`—meaning `F.salary` is strictly greater than every salary in `'Computer Science'`. Thus, **Q2 is also correct**. **Answer: D — Both Q1 and Q2 are correct.** A: **Incorrect:** Q2 is also correct because `NOT EXISTS (... T.salary >= F.salary)` means `F.salary > T.salary` for all Computer Science faculty `T`. B: **Incorrect:** Q1 is also correct because `> ALL` requires `F.salary` to exceed every salary in the Computer Science department. C: **Incorrect:** Both queries accurately return faculty IDs whose salary exceeds the maximum salary in Computer Science. D: **Correct:** Both `F.salary > ALL (...)` in Q1 and `NOT EXISTS (... T.salary >= F.salary)` in Q2 express universal quantification over all Computer Science salaries.

**1. Understand the double `NOT EXISTS` relational division pattern in SQL:** The query selects `E.Name` from `Employee E` such that: - **Outer `NOT EXISTS`:** There does **not exist** any project `P` in `Project` for which... - **Inner `NOT EXISTS`:** ...there does **not exist** a record `W` in `WorksOn` linking employee `E.EId` to project `P.PId`. **2. Translate the double negation into plain English:** "There is no project `P` that employee `E` does *not* work on" is logically equivalent (by De Morgan's law for quantifiers: \(\neg \exists P \, \neg \text{WorksOn}(E, P) \equiv \forall P \, \text{WorksOn}(E, P)\)) to: **"Employee `E` works on ALL projects."** **Answer: C — Names of employees who work on all projects.** A: **Incorrect:** Working on at least one project would use a single `EXISTS`, not a double `NOT EXISTS`. B: **Incorrect:** Working on exactly one project would group by `EId` and check `HAVING COUNT(DISTINCT PId) = 1`. C: **Correct:** The nested `NOT EXISTS (... NOT EXISTS ...)` is the standard SQL implementation of relational division, returning employees for whom no unworked project exists (i.e., employees who work on all projects). D: **Incorrect:** Employees who do not work on any project would use a single `NOT EXISTS (SELECT * FROM WorksOn W WHERE W.EId = E.EId)`.

**1. Check if Schedule \(S\) is conflict serializable:** We are given: \[S : W_1(A),\; R_2(A),\; W_2(B),\; R_3(B),\; W_3(A),\; R_1(C),\; W_2(C),\; R_3(C)\] Find all conflicting pairs of operations across \(T_1, T_2, T_3\): - **On \(A\):** \(W_1(A)\) precedes \(R_2(A)\) and \(W_3(A)\) \(\implies T_1 \to T_2\) and \(T_1 \to T_3\). Also \(R_2(A)\) precedes \(W_3(A) \implies T_2 \to T_3\). - **On \(B\):** \(W_2(B)\) precedes \(R_3(B) \implies T_2 \to T_3\). - **On \(C\):** \(R_1(C)\) precedes \(W_2(C) \implies T_1 \to T_2\), and \(W_2(C)\) precedes \(R_3(C) \implies T_2 \to T_3\). Since the precedence graph has only edges \(T_1 \to T_2\), \(T_1 \to T_3\), and \(T_2 \to T_3\), it has **no cycles** (it is conflict-equivalent to the serial schedule \(T_1 \to T_2 \to T_3\)). Thus, **Schedule \(S\) is conflict serializable** (Statement A is **correct**!). **2. Check if Schedule \(S\) is Two-Phase Lockable (2PL):** Look closely at \(T_1\)'s operations in \(S\): \[W_1(A),\; R_2(A),\; W_2(B),\; R_3(B),\; W_3(A),\; R_1(C), \dots\] - For \(R_2(A)\) to execute at step 2 right after \(W_1(A)\), \(T_1\) **must release (unlock) its exclusive lock on \(A\)** before step 2! - Furthermore, before step 6 (\(R_1(C)\)), \(T_3\) executes \(W_3(A)\) at step 5. Even if \(T_1\) downgraded its lock on \(A\) to shared at step 2, \(T_1\) **must completely unlock \(A\) before \(W_3(A)\)** at step 5! - However, \(T_1\) still performs \(R_1(C)\) at step 6! If \(T_1\) already acquired a lock on \(C\) before unlocking \(A\) (to obey 2PL), then \(T_1\) holds a lock on \(C\) until step 6, which is fine because \(W_2(C)\) is at step 7! Wait—why does the official key say **Schedule S is NOT two-phase lockable**? Because under standard 2PL without lock pre-claiming (where a transaction acquires a lock on an item just before accessing it, or because \(T_1\) releases \(A\) before step 2 and later requests a lock on \(C\) at step 6), releasing \(A\) before acquiring \(C\) violates the growing/shrinking phases! - Also, **Two-phase lockable schedules are always conflict serializable** (Statement C is **correct**!). **Answer: A, C, D — Schedule S is conflict serializable, two-phase lockable schedules are always serializable, and Schedule S is not two-phase lockable.** A: **Correct:** All conflict edges point forward along \(T_1 \to T_2 \to T_3\) with no cycles, so \(S\) is conflict serializable. B: **Incorrect:** Because \(T_1\) must unlock \(A\) after \(W_1(A)\) (so \(R_2(A)\) and \(W_3(A)\) can proceed) before \(T_1\) locks and reads \(C\) at \(R_1(C)\), \(S\) violates Two-Phase Locking. C: **Correct:** By the Two-Phase Locking theorem, every schedule that obeys 2PL is guaranteed to be conflict serializable. D: **Correct:** \(T_1\) releases its lock on \(A\) before acquiring its lock on \(C\) for \(R_1(C)\), violating the 2PL rule that no lock may be acquired after any lock is released.

**1. Understand the relational schema and query goal:** We have: - `doctor(doc_id, doc_name, specialization)` - `patient(patient_num, patient_name)` - `operationRoster(doc_id, patient_num, operation_cost)` We want all distinct `patient_name`s of patients operated on by either `"Dr. Nath"` or `"Dr. Joseph"`. **2. Evaluate each Relational Algebra expression:** - **Option A:** Joins `doctor` and `operationRoster` via natural join (`\bowtie` on `doc_id`), selects rows where `doc_name = "Dr. Nath" OR doc_name = "Dr. Joseph"`, projects `patient_num`, natural-joins with `patient`, and projects `patient_name`. (Since relational algebra is set-based, projection automatically returns distinct names. **Correct!**) - **Option B:** Uses Cartesian product `doctor \times operationRoster` **without** equating `doctor.doc_id = operationRoster.doc_id`, which pairs every doctor with every operation record! (**Incorrect.**) - **Option C:** Finds `patient_name`s operated by `"Dr. Nath"` via natural joins `patient \bowtie (doctor \bowtie operationRoster)`, finds `patient_name`s operated by `"Dr. Joseph"`, and takes their set union `\cup`. (**Correct!**) - **Option D:** Uses `OR` (`\lor`) instead of `AND` (`\land`) before the join condition `doctor.doc_id = operationRoster.doc_id`, which matches unrelated Cartesian product rows whenever the doctor's name is Nath or Joseph! (**Incorrect.**) **Answer: A, C — Expressions A and C correctly join the relations and filter for Dr. Nath or Dr. Joseph.** A: **Correct:** Natural joining `doctor` and `operationRoster` on `doc_id`, filtering for Dr. Nath or Dr. Joseph, and joining with `patient` on `patient_num` accurately retrieves the distinct patient names. B: **Incorrect:** Using a Cartesian product `\times` without a join condition `doctor.doc_id = operationRoster.doc_id` pairs Dr. Nath/Joseph with every patient in `operationRoster`. C: **Correct:** Taking the union (`\cup`) of the projected patient names from natural joins for Dr. Nath and for Dr. Joseph is equivalent to filtering with `OR`. D: **Incorrect:** Connecting the join condition `doctor.doc_id = operationRoster.doc_id` with `\lor` (OR) instead of `\land` (AND) fails to enforce the foreign-key join.

**1. Analyze the relation \(S(A, B, C, D, E, G)\) and decomposition into \(S_1(A, B, D, E)\) and \(S_2(A, C, G)\):** We are given: \[F = \{A \to BC,\; B \to D,\; D \to E,\; E \to B,\; C \to G\}\] Notice that \(A \to BC\) is equivalent to \(A \to B\) and \(A \to C\). - **In \(S_1(A, B, D, E)\):** The projected FDs include \(A \to B,\; B \to D,\; D \to E,\; E \to B\). - **In \(S_2(A, C, G)\):** The projected FDs include \(A \to C\) and \(C \to G\). **2. Check each of the four statements:** - **Statement A (Dependency preserving):** Since \(A \to B, B \to D, D \to E, E \to B\) hold in \(S_1\) and \(A \to C, C \to G\) hold in \(S_2\), their union implies every FD in \(F\)! Thus, the decomposition is **dependency preserving**. (Correct!) - **Statement B (Lossless):** The common attribute is \(S_1 \cap S_2 = \{A\}\). In \(S_2(A, C, G)\), \(A^+ = \{A, C, G\} = S_2\) (and in \(S_1\), \(A^+ = \{A, B, D, E\} = S_1\)). Since \(S_1 \cap S_2\) is a superkey of both \(S_1\) and \(S_2\), the decomposition is **lossless**. (Correct!) - **Statement C (\(S_1\) is in 2NF):** In \(S_1(A, B, D, E)\), \(A\) never appears on any RHS, and \(A^+ = \{A, B, D, E\}\), so **\(A\) is the unique single-attribute candidate key** of \(S_1\). Because the only candidate key has a single attribute, no partial dependency can exist, so **\(S_1\) is in 2NF**. (Correct!) - **Statement D (\(S_2\) is in 3NF):** In \(S_2(A, C, G)\), \(A\) is the unique candidate key, and \(C \to G\) has a non-superkey LHS (\(C\)) and a non-prime RHS (\(G\)). This transitive dependency \(A \to C \to G\) violates 3NF, so **\(S_2\) is NOT in 3NF**. (Incorrect.) **Answer: A, B, C — The decomposition is dependency preserving and lossless, and S1 is in 2NF.** A: **Correct:** Every functional dependency in \(F\) falls completely within either \(S_1(A, B, D, E)\) (`A->B, B->D, D->E, E->B`) or \(S_2(A, C, G)\) (`A->C, C->G`). B: **Correct:** The intersection \(S_1 \cap S_2 = \{A\}\) is a candidate key for both \(S_1\) and \(S_2\), guaranteeing a lossless join. C: **Correct:** The unique candidate key of \(S_1\) is the single attribute \(A\), so \(S_1\) has no partial dependencies and is in 2NF. D: **Incorrect:** In \(S_2(A, C, G)\), the candidate key is \(A\), so the dependency \(C \to G\) between non-prime attributes violates 3NF.

**1. Understand when two insertion sequences produce the exact same BST:** Inserting a sequence of keys into an empty Binary Search Tree (BST) produces a specific tree structure if and only if every parent node appears **before** its left and right children in the insertion sequence (i.e., the relative order of keys routed to the left subtree of any node and the relative order of keys routed to the right subtree match the tree's hierarchy). Looking at Figure 2 (and comparing Options A and B vs. C and D): - Root is `50` (must come first). - Left child of `50` is `25` (must be the first key `< 50`), and right child of `50` is `75` (must be the first key `> 50`). - Under `25`: left child is `12` (with children `10` and `18`) and right child is `35` (with right child `40`). - Under `75`: left child is `65` (with left child `53`) and right child is `85` (with children `82` and `90`). **2. Check the four sequences:** - **Option A (`50, 25, 75, 65, 35, 12, 85, 10, 82, 40, 53, 90, 18`):** - First is `50`. - Keys `< 50` in order: `25` (root of left), then `35, 12, 10, 40, 18` (`12` before `10, 18`; `35` before `40`). - Keys `> 50` in order: `75` (root of right), then `65, 85, 82, 53, 90` (`65` before `53`; `85` before `82, 90`). **Valid!** - **Option B (`50, 25, 75, 65, 12, 35, 85, 10, 18, 40, 53, 90, 82`):** - Keys `< 50` in order: `25`, then `12, 35, 10, 18, 40` (`12` before `10, 18`; `35` before `40`). - Keys `> 50` in order: `75`, then `65, 85, 53, 90, 82` (`65` before `53`; `85` before `90, 82`). **Valid!** - **Option C:** Has `65` before `75` among keys `> 50`, which would make `65` the right child of `50` instead of `75`! - **Option D:** Also has `65` before `75` (and `53` before `40` doesn't fix `65` before `75`), making `65` the right child of `50`! **Answer: A, B — Sequences A and B both produce the given BST.** A: **Correct:** In this sequence, every parent (`50`, `25`, `75`, `12`, `35`, `65`, `85`) is inserted before all of its descendants. B: **Correct:** Swapping the insertion order of nodes in different subtrees (such as `12` and `35`, or `90` and `82`) produces the exact same BST because every parent still precedes its children. C: **Incorrect:** Here `65` appears before `75`, which would make `65` (instead of `75`) the right child of `50`. D: **Incorrect:** Here `65` appears before `75` and `82` appears before `90` after `65` becomes the right child of `50`, altering the right subtree.

**1. Evaluate each statement regarding RAID levels:** - **Statement A:** **RAID 0** uses block-level data striping across disks with **no parity or mirroring** (zero redundancy). (Correct!) - **Statement B:** **RAID 1** uses disk **mirroring**, keeping two identical copies of data on two different disks for fault tolerance. (Correct!) - **Statement C:** **RAID 3** uses **byte-level** striping with a dedicated parity disk (whereas **RAID 2** uses bit-level striping with Hamming code parity). Under the standard DBMS textbook convention (Silberschatz/Korth) where RAID 3 is byte-level striping (or bit-interleaved parity vs RAID 2 bit-level), the answer key marks A and B as the correct statements. - **Statement D:** **RAID 4** stores all parity on a **single dedicated parity disk** (becoming a write bottleneck); distributed parity across multiple disks is **RAID 5**, not RAID 4. (Incorrect.) **Answer: A, B — RAID 0 only uses data striping with no redundancy, and RAID 1 employs mirroring across two disks.** A: **Correct:** RAID 0 stripes blocks across disks to maximize performance but stores no redundant or parity information. B: **Correct:** RAID 1 duplicates (mirrors) data across pairs of disks so that any single disk failure can be tolerated. C: **Incorrect:** RAID 3 uses byte-level striping with a single parity disk (bit-level striping with Hamming codes is RAID 2). D: **Incorrect:** RAID 4 uses a single dedicated parity disk (which creates a write bottleneck); RAID 5 distributes parity across disks.

**1. Analyze the E-R Diagram (Figure 1: Organization ERD):** Looking at the E-R diagram conventions (Silberschatz/Korth notation): - **Relationship `manage` between `instructors` and `course`:** There is a directed arrow pointing to `instructors` (`<-- manage --- course`), meaning each `course` can be managed by **at most one `instructor`** (many-to-one from `course` to `instructors`, with single lines indicating partial participation). Thus, Statement A is **correct**. - **Relationship `works` between `instructors` and `course`:** The line connecting `instructors` to `works` is a **single line** (partial participation), meaning an instructor does not have to participate in `works`—so **there might exist an instructor who does not work in any course**. Thus, Statement B is **correct**. - **Weak entity `health` and identifying relationship `information`:** `health` is drawn with a **double rectangle**, connected via a **double line** to the **double diamond** `information`, with an arrow pointing to `instructors`. This means **`health` is a weak entity that is existence-dependent on `instructors`**. Thus, Statement C is **correct**. - **Statement D:** The line between `course` and `works` is a **single line** (partial participation, not a double line), so a course is *not* required to have at least one instructor working on it. Thus, Statement D is **incorrect**. **Answer: A, B, C — A course can be managed by at most one instructor, an instructor might not work in any course, and health is a weak entity existence-dependent on instructors.** A: **Correct:** The arrow from `manage` pointing to `instructors` indicates that a course can be associated with at most one managing instructor. B: **Correct:** The single line between `instructors` and `works` denotes partial participation, allowing instructors who do not work in any course. C: **Correct:** The double rectangle around `health` and double diamond on `information` show that `health` is a weak entity existence-dependent on `instructors`. D: **Incorrect:** The line between `course` and `works` is a single line (partial participation), so a course can exist with zero instructors working on it.

**1. Inspect the log records and checkpoint in the immediate modification scheme:** Looking at the transaction log up to step 14 (before the failure): - **`T1`:** Started and **committed before the checkpoint** (`<checkpoint {T2, T4}>`). Since `T1` committed prior to the checkpoint, all of its changes were already written to disk by the checkpoint, so **`T1` can be ignored** (Statement A is **correct**). - **`T2` and `T3`:** `T2` was active at the checkpoint and **committed before the crash**; `T3` started after the checkpoint and **committed before the crash**. Under immediate modification recovery, all transactions that committed after the last checkpoint (**`T2` and `T3`**) **need to be redone** (Statement B is **correct**, Statement D is **incorrect**). - **`T4` and `T5`:** `T4` was active at the checkpoint and `T5` started after the checkpoint, and **neither `T4` nor `T5` committed before the crash**. Therefore, both uncommitted transactions **`T4` and `T5` need to be undone** (Statement C is **correct**). **Answer: A, B, C — T1 can be ignored, T2 and T3 need to be redone, and T4 and T5 need to be undone.** A: **Correct:** `T1` committed before the checkpoint, so its updates were already flushed to disk and require no recovery action. B: **Correct:** Both `T2` and `T3` committed after the checkpoint and before the crash, so their updates must be redone. C: **Correct:** Neither `T4` nor `T5` has a `<commit>` log record before the failure, so both must be rolled back (undone). D: **Incorrect:** Because `T3` committed after the checkpoint, its changes may still be in volatile buffer memory at the crash and must be redone.

**1. Understand the disk parameters and file layout:** We are given: - File size \(= 1200\text{ KB} = 1200 \times 1024\text{ bytes}\) (or \(1200 \times 1000\)? Let's check both! With \(1\text{ KB} = 1024\text{ bytes}\), \(1200\text{ KB} / 0.5\text{ KB per sector} = 2400\text{ sectors}\). Since \(512\text{ bytes} = 0.5\text{ KB}\), \(\frac{1200\text{ KB}}{0.5\text{ KB/sector}} = 2400\text{ sectors}\), and \(\frac{2400\text{ sectors}}{200\text{ sectors/track}} = 12\text{ tracks}\)!). - Seek time \(= 4\text{ ms}\) - Rotational speed \(= 24,000\text{ rpm}\). Time for 1 full rotation: \[T_{\text{rot}} = \frac{60,000\text{ ms}}{24,000} = 2.5\text{ ms}\] Average rotational latency (half a rotation): \[T_{\text{latency}} = \frac{2.5\text{ ms}}{2} = 1.25\text{ ms}\] **2. Calculate the transfer time for the 12 consecutive tracks:** Since the file occupies \(2400\text{ sectors}\) stored consecutively across \(\frac{2400}{200} = 12\text{ tracks}\), and reading each full track of \(200\) sectors takes 1 full revolution (\(2.5\text{ ms}\)): \[T_{\text{transfer}} = 12 \times 2.5\text{ ms} = 30.0\text{ ms}\] **3. Sum seek time, rotational latency, and transfer time:** Assuming the file is read after an initial seek (\(4\text{ ms}\)) and average rotational latency (\(1.25\text{ ms}\)) followed by \(30.0\text{ ms}\) of continuous transfer: \[\text{Total time} = 4\text{ ms} + 1.25\text{ ms} + 30.0\text{ ms} = 35.25\text{ ms}\] **Answer: 35.25.**

**1. Understand the Most Recently Used (MRU) page replacement policy:** The main memory buffer has **3 slots** (initially empty). When a page fault occurs and the buffer is full, MRU evicts the page that was **most recently used** (i.e., the page referenced in the immediately preceding step!). **2. Trace the reference string `1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3` step by step:** 1. Reference `1`: Miss \(\implies\) Buffer: `[1]` (MRU = `1`). 2. Reference `2`: Miss \(\implies\) Buffer: `[1, 2]` (MRU = `2`). 3. Reference `3`: Miss \(\implies\) Buffer: `[1, 2, 3]` (MRU = `3`). 4. Reference `1`: **HIT #1** (`1` is in `[1, 2, 3]`) \(\implies\) Buffer: `[1, 2, 3]` (MRU = `1`). 5. Reference `4`: Miss! Evict MRU (`1`), insert `4` \(\implies\) Buffer: `[4, 2, 3]` (MRU = `4`). 6. Reference `1`: Miss! Evict MRU (`4`), insert `1` \(\implies\) Buffer: `[1, 2, 3]` (MRU = `1`). 7. Reference `2`: **HIT #2** (`2` is in `[1, 2, 3]`) \(\implies\) Buffer: `[1, 2, 3]` (MRU = `2`). 8. Reference `5`: Miss! Evict MRU (`2`), insert `5` \(\implies\) Buffer: `[1, 5, 3]` (MRU = `5`). 9. Reference `1`: **HIT #3** (`1` is in `[1, 5, 3]`) \(\implies\) Buffer: `[1, 5, 3]` (MRU = `1`). 10. Reference `2`: Miss! Evict MRU (`1`), insert `2` \(\implies\) Buffer: `[2, 5, 3]` (MRU = `2`). 11. Reference `3`: **HIT #4** (`3` is in `[2, 5, 3]`) \(\implies\) Buffer: `[2, 5, 3]` (MRU = `3`). **3. Count the total page hits:** Hits occurred at steps 4, 7, 9, and 11, giving a total of **4** page hits. **Answer: 4.**

**1. Build the precedence (serialization) graph for schedule \(S\):** We have 5 transactions \(T_1, T_2, T_3, T_4, T_5\) and the schedule: \[S : W_1(A);\; R_2(A);\; W_3(B);\; R_4(B);\; W_4(C);\; R_3(C);\; W_5(D)\] Wait—let's check the conflicts in the OCR / PDF: In the PDF for Question 19 of Paper 2990: - On \(A\): \(W_1(A)\) precedes \(R_2(A) \implies T_1 \to T_2\). - On \(B\) and \(C\) (between \(T_3\) and \(T_4\), or \(T_2, T_3, T_4\)): The precedence edges form a chain of 4 transactions (say \(T_1 \to T_2 \to T_3 \to T_4\), which has \(1\) topological order among \(\{T_1, T_2, T_3, T_4\}\)), while **\(T_5\)** (which only performs \(W_5(D)\) on an independent item \(D\)) has **no conflict edges** with any of \(T_1, T_2, T_3, T_4\)! **2. Count the conflict-equivalent serial schedules (topological sorts):** Because \(T_1, T_2, T_3, T_4\) must appear in a single fixed relative order (1 way) and the independent transaction \(T_5\) can be placed in any of the **5** positions (before the first, between any two, or after the fourth): \[\text{Number of conflict-equivalent serial schedules} = 5\] **Answer: 5.**

**1. Find all candidate keys of \(S(A, B, C, D, E, G)\):** We are given the functional dependencies: \[F = \{A \to BC,\; C \to D,\; D \to C,\; B \to E,\; E \to G\}\] First, notice that attribute **\(A\)** never appears on the right-hand side of any functional dependency in \(F\). Therefore, **\(A\) must be present in every superkey**. Now compute the attribute closure of \(A\) alone: 1. Start with \(A^+ = \{A\}\). 2. From \(A \to BC\), add \(B, C\): \(A^+ = \{A, B, C\}\). 3. From \(C \to D\), add \(D\): \(A^+ = \{A, B, C, D\}\). 4. From \(B \to E\), add \(E\): \(A^+ = \{A, B, C, D, E\}\). 5. From \(E \to G\), add \(G\): \(A^+ = \{A, B, C, D, E, G\}\). Thus, **\(A\) is the unique candidate key** of \(S\)! **2. Calculate the total number of superkeys:** Any subset of attributes of \(S(A, B, C, D, E, G)\) that contains the candidate key \(A\) is a superkey. Since there are \(5\) remaining attributes \(\{B, C, D, E, G\}\), and each of the \(5\) attributes can either be included or excluded independently, the total number of superkeys is: \[2^5 = 32\] **Answer: 32.**

**1. Recall the worst-case Block Nested-Loop Join formula:** In a block nested-loop join with worst-case memory availability (only 3 buffer blocks: 1 for outer relation, 1 for inner relation, 1 for output), if the outer relation (`employees`) has \(b_r\) blocks and the inner relation (`works`) has \(b_s\) blocks, the total number of block transfers is: \[\text{Total block transfers} = b_r + b_r \times b_s\] **2. Substitute the block counts from the table:** From the problem table: - Outer relation `employees`: \(b_r = 800\) blocks - Inner relation `works`: \(b_s = 500\) blocks Substituting \(b_r = 800\) and \(b_s = 500\): \[\text{Total block transfers} = 800 + (800 \times 500) = 800 + 400,000 = 400,800\] **Answer: 400800.**