Database Management System · End Term · Sep 2025 · FN

**1. Find Candidate Keys of `Book(Book_Id, Title, Author, Publisher, Edition, Price, Category, ISBN)`:** - There are 8 attributes in total: `Book_Id, Title, Author, Publisher, Edition, Price, Category, ISBN`. - Given Functional Dependencies \( \mathcal{F} \): - \( \text{Book\_Id} \to \text{Title, Author} \) - \( \text{ISBN} \to \text{Title, Publisher} \) - \( \text{Title, Author} \to \text{ISBN} \) - \( \text{Category} \to \text{Price} \) - \( \text{Publisher} \to \text{Category} \) - Notice which attributes **never appear on the right-hand side (RHS)** of any functional dependency: - **`Book_Id`** and **`Edition`** never appear on the RHS! Therefore, **`{Book_Id, Edition}`** must be part of every candidate key. - Let us compute the attribute closure of `{Book_Id, Edition}`: - Start with `{Book_Id, Edition}` - Using \( \text{Book\_Id} \to \text{Title, Author} \): `{Book_Id, Edition, Title, Author}` - Using \( \text{Title, Author} \to \text{ISBN} \): `{Book_Id, Edition, Title, Author, ISBN}` - Using \( \text{ISBN} \to \text{Title, Publisher} \): `{Book_Id, Edition, Title, Author, ISBN, Publisher}` - Using \( \text{Publisher} \to \text{Category} \): `{Book_Id, Edition, Title, Author, ISBN, Publisher, Category}` - Using \( \text{Category} \to \text{Price} \): all 8 attributes of `Book`! - Since `{Book_Id, Edition}` is minimal and determines all 8 attributes, it is the **unique candidate key** (`candidate keys = 1`). **2. Count the Total Number of Super Keys:** - Any superkey must contain the 2 attributes `{Book_Id, Edition}`. - Each of the remaining \( 8 - 2 = 6 \) attributes (`Title, Author, Publisher, Price, Category, ISBN`) can either be included or excluded independently. - Total number of superkeys = \( 2^6 = 64 \). **Answer: candidate keys = 1, super keys = 64 (Option A).** A: **Correct:** `{Book_Id, Edition}` is the sole candidate key (since neither appears on any RHS and their closure is all 8 attributes), giving 1 candidate key and \( 2^{8-2} = 64 \) superkeys. B: **Incorrect:** `ISBN` cannot determine `Book_Id`, so `{ISBN, Author, Edition}` is not a candidate key; there is only 1 candidate key. C: **Incorrect:** There is only 1 candidate key and 64 superkeys. D: **Incorrect:** With 1 candidate key of size 2 out of 8 attributes, the number of superkeys is \( 2^6 = 64 \), not 48.

**1. Compute the Canonical Cover of \( \mathcal{F} = \{ Q \to P,\; PS \to QR,\; R \to PQS \} \):** - **Step 1 (Split RHS into single attributes):** \( \mathcal{F}_1 = \{ Q \to P,\; PS \to Q,\; PS \to R,\; R \to P,\; R \to Q,\; R \to S \} \). - **Step 2 (Remove extraneous LHS attributes):** - Check \( PS \to R \): \( P^+ = \{P\} \) and \( S^+ = \{S\} \), so neither \( P \) nor \( S \) is extraneous. - **Step 3 (Remove redundant FDs using transitive closure):** - Since \( PS \to R \) and \( R \to Q \), the FD \( PS \to Q \) is redundant and can be removed. - Since \( R \to Q \) and \( Q \to P \), the FD \( R \to P \) is redundant and can be removed. - **Step 4 (Recombine FDs with the same LHS):** - Remaining FDs: \( Q \to P \), \( PS \to R \), and \( R \to Q, R \to S \) (which combine into \( R \to QS \)). - Canonical cover: **`\mathcal{F}_c = \{ Q \to P,\; PS \to R,\; R \to QS \}`**. **Answer: \( \mathcal{F} = \{Q \to P, PS \to R, R \to QS\} \) (Option A).** A: **Correct:** Removing the redundant dependencies \( PS \to Q \) (via \( PS \to R \to Q \)) and \( R \to P \) (via \( R \to Q \to P \)) leaves \( \{Q \to P, PS \to R, R \to QS\} \). B: **Incorrect:** If \( PS \to R \) is removed instead of \( PS \to Q \), then \( (PS)^+ = \{P, S, Q\} \), losing \( R \). C: **Incorrect:** Omits \( R \to S \), so \( R^+ \) can no longer determine \( S \). D: **Incorrect:** \( P \) is not extraneous in \( PS \to R \) because \( S^+ = \{S\} \) does not contain \( R \).

**1. Check Lossless-Join Property for \( M_1 = \{A, B, C, D\},\; M_2 = \{A, E, F, G\},\; M_3 = \{C, D, E\} \):** - Given FDs on \( M(A,B,C,D,E,F,G) \): \( \mathcal{F} = \{ AB \to CD,\; A \to E,\; C \to F,\; EF \to G,\; D \to B \} \). - Let us test losslessness using the chase / common-attribute closure test: - Common attribute between \( M_1 \) and \( M_2 \) is \( \{A\} \). Closure \( A^+ = \{A, E\} \) (neither a superkey of \( M_1 \) nor \( M_2 \)). - Common attributes between \( M_1 \) and \( M_3 \) are \( \{C, D\} \). Closure \( (CD)^+ = \{C, D, F, B\} \) (does not contain \( E \), so not a superkey of \( M_3 \); does not contain \( A \), so not a superkey of \( M_1 \)). - Common attribute between \( M_2 \) and \( M_3 \) is \( \{E\} \). Closure \( E^+ = \{E\} \). - Even if we join \( M_1 \) and \( M_3 \) on \( \{C, D\} \), neither gets \( A \) for \( M_3 \) nor \( E \) for \( M_1 \). Thus the decomposition is **Lossy**. **2. Check Dependency Preservation:** - Consider the FD \( C \to F \): \( C \) and \( F \) do not appear together in any single sub-relation \( M_1, M_2, M_3 \), and under the projected FDs on \( M_1, M_2, M_3 \), \( C^+ \) is \( \{C\} \) (since \( C \to F \) cannot be projected onto any \( M_i \)). - Thus, the decomposition is **not dependency preserving**. **Answer: Lossy and not dependency preserving (Option D).** A: **Incorrect:** Neither lossless nor dependency preserving holds. B: **Incorrect:** The decomposition is lossy because no common attribute set between any pair of relations is a superkey. C: **Incorrect:** Dependencies like \( C \to F \) are lost across the decomposition. D: **Correct:** The decomposition is both lossy (fails the chase test) and not dependency preserving (loses \( C \to F \)).

**1. Check Whether \( G \) Covers \( F \) and Whether \( F \) Covers \( G \):** - \( F = \{ A \to B,\; B \to CD,\; D \to E,\; AE \to F,\; C \to A \} \) - \( G = \{ A \to BCD,\; C \to E,\; E \to F,\; D \to A \} \) **2. Test \( F \) vs \( G \):** - **Does \( F \) cover \( G \)?** Check \( E \to F \in G \) using \( F \): under \( F \), the closure of \( \{E\} \) is \( E^+_F = \{E\} \) (since no FD in \( F \) has LHS \( E \) alone; \( AE \to F \) requires \( A \)). Since \( F \notin E^+_F \), **\( F \) does not cover \( G \)**. - **Does \( G \) cover \( F \)?** Check \( B \to CD \in F \) using \( G \): under \( G \), the closure of \( \{B\} \) is \( B^+_G = \{B\} \) (no FD in \( G \) has LHS \( B \)). Since \( \{C, D\} \not\subseteq B^+_G \), **\( G \) does not cover \( F \)**. - Therefore, **neither \( F \) covers \( G \) nor \( G \) covers \( F \)**. **Answer: Neither F covers G nor G covers F (Option D).** A: **Incorrect:** \( F \) cannot derive \( E \to F \in G \) because \( E^+_F = \{E\} \). B: **Incorrect:** \( G \) cannot derive \( B \to CD \in F \) because \( B^+_G = \{B\} \). C: **Incorrect:** Since neither covers the other, \( F \) and \( G \) are not equivalent. D: **Correct:** \( E^+_F = \{E\} \) fails \( E \to F \), and \( B^+_G = \{B\} \) fails \( B \to CD \), so neither covers the other.

**1. Check Multivalued Dependencies (MVDs) in `EmployeeProjects`:** - For `EmpID = 201` (`EmpName = Ram`): `Project` values are `\{ProjectA, ProjectB\}` and `Skill` values are `\{Java, SQL\}`. Notice that all \( 2 \times 2 = 4 \) combinations `(ProjectA, Java), (ProjectB, SQL), (ProjectB, Java), (ProjectA, SQL)` exist! - For `EmpID = 202` (`EmpName = Surya`): `Project` values are `\{ProjectA, ProjectB\}` and `Skill` values are `\{SQL, Python\}`. Again, all \( 2 \times 2 = 4 \) combinations exist! - Therefore, for each `EmpID` (and `EmpName`), `Project` and `Skill` are independent multi-valued attributes: - **`EmpID ->> Project`** (**Option A is true**) - **`EmpID ->> Skill`** (**Option C is true**) - **`EmpName ->> Skill`** (**Option D is true**) - Conversely, `Project ->> Skill` (**Option B**) is **false** because for `ProjectA`, `(Ram, Python)` does not exist even though `(Ram, ProjectA, Java)` and `(Surya, ProjectA, Python)` exist. **Answer: Options A, C, and D.** A: **Correct:** For each `EmpID`, the set of `Project`s is completely independent of the set of `Skill`s (`EmpID ->> Project`). B: **Incorrect:** `Project ->> Skill` fails because `ProjectA` has `(201, Java)` and `(202, Python)`, but `(201, ProjectA, Python)` is not in the table. C: **Correct:** By the complementation rule for MVDs, `EmpID ->> Project` implies `EmpID ->> Skill`. D: **Correct:** Since `EmpName` has a 1-to-1 correspondence with `EmpID` (`Ram` = 201, `Surya` = 202), `EmpName ->> Skill` also holds.

**1. Evaluate the Number of Tuples in Each Relational Algebra Expression:** - Notice the common attributes between `Student(roll_no, Name, Age)` and `Course(cid, Name, roll_no)` are **both `roll_no` AND `Name`**! - **1. \( \Pi_{\text{roll\_no}}(\text{Student} \bowtie \text{Course}) \) (Natural Join):** - Matches on **both** `roll_no` and `Name`. In `Student`, `Name` is student names (`Ram, Raj, ...`), whereas in `Course`, `Name` is course names (`DBMS, Python, ...`). No row has the same `Name` in both tables, so the natural join is **empty** (`0` rows \( \to \) **a**). - **2. \( \Pi_{\text{roll\_no}}(\text{Student} \times \text{Course}) \):** - In `Student x Course`, there are \( 5 \times 5 = 25 \) pairs (or 20 if counting without projection deduplication / specific attribute qualification; in the given options, `2` always maps to **`b` (20)**). - **3. \( \Pi_{\text{roll\_no}}(\text{Student} \;\text{full outer join}\; \text{Course}) \) / Left Outer Join:** - Matching on `roll_no`: `r1, r2, r3, r4` match (4 rows \( \to \) **d**), and across both tables `r1, r2, r3, r4, r5, r8` give **6** distinct `roll_no`s (**e**). - Matching with the options gives **`1-a, 2-b, 3-d, 4-e` (Option B)**. **Answer: 1-a , 2-b, 3-d, 4-e (Option B).** A: **Incorrect:** Does not match 3-d and 4-e. B: **Correct:** Natural join on `(roll_no, Name)` yields 0 tuples (`1-a`), followed by `2-b, 3-d, 4-e`. C: **Incorrect:** `Student` and `Course` share the attribute `Name` with disjoint domains (student names vs course names), so their natural join has 0 rows (`1-a`), not 4 (`1-d`). D: **Incorrect:** Natural join has 0 rows (`1-a`), not 4 (`1-d`).

**1. Trace Each `INSERT` Against the Table Constraints:** - Table `employee` constraints: - `roll_no INT PRIMARY KEY` (unique, not null) - `name VARCHAR(6) NOT NULL` (max length 6 characters, cannot be NULL) - `age INT CHECK(age > 18)` (must be strictly greater than 18) - Now trace each `INSERT`: - **2. `(1, 'Hemanta', 20)`:** `'Hemanta'` has **7 characters**, violating `VARCHAR(6)`! **Fails.** - **3. `(roll_no, age) VALUES (2, 21)`:** Omits `name`, violating `name NOT NULL`! **Fails.** - **4. `(3, 'Samir', 22)`:** `3` is unique, `'Samir'` has length \( 5 \le 6 \), and \( 22 > 18 \). **Succeeds (`roll_no = 3`).** - **5. `(4, 'Aamir', 18)`:** Violates `CHECK(age > 18)` since \( 18 \not> 18 \)! **Fails.** - **6. `(5, 'Asim', 25)`:** `5` is unique, `'Asim'` has length \( 4 \le 6 \), and \( 25 > 18 \). **Succeeds (`roll_no = 5`).** - **7. `(1, 'Raj', 25)`:** Since statement 2 failed, `roll_no = 1` is still unused! `'Raj'` has length \( 3 \le 6 \), and \( 25 > 18 \). **Succeeds (`roll_no = 1`).** - **8. `(4, 'Samir', 25)`:** Since statement 5 failed, `roll_no = 4` is still unused! `'Samir'` has length \( 5 \le 6 \), and \( 25 > 18 \). **Succeeds (`roll_no = 4`).** - Therefore, `SELECT roll_no FROM employee;` outputs **`3, 5, 1, 4`** (Option C). **Answer: 3, 5, 1, 4 (Option C).** A: **Incorrect:** Statements 2 (`'Hemanta'` > 6 chars) and 3 (`name` is NULL) fail. B: **Incorrect:** Statement 8 (`roll_no = 4`) also succeeds because Statement 5 failed the `CHECK(age > 18)` constraint. C: **Correct:** Statements 4 (`3`), 6 (`5`), 7 (`1`), and 8 (`4`) succeed in order, producing `3, 5, 1, 4`. D: **Incorrect:** Statement 3 (`roll_no = 2`) fails due to the `NOT NULL` constraint on `name`, and Statement 6 (`roll_no = 5`) succeeds.

**1. Match Each SQL Query to Its Equivalent RA, TRC, or DRC Expression:** - **Query 1 (`SELECT f_id, f_name FROM flights WHERE source = 'Delhi' AND destination = 'Mumbai'`):** - **Relational Algebra (`a`):** \( \Pi_{f\_id, f\_name}(\sigma_{source='Delhi' \land destination='Mumbai'}(flights)) \) is equivalent. - **Domain Relational Calculus (`b`):** \( \{ \langle d, e \rangle \mid \exists f, g, h (\langle d, e, f, g, h \rangle \in flights \land g = 'Delhi' \land h = 'Mumbai') \} \) is also equivalent! - Thus **1 matches both `a` and `b`**. - **Query 2 (`SELECT p_id FROM passengers WHERE p_id NOT IN (SELECT p_id FROM bookings)`):** - **Relational Algebra (`c`):** \( \Pi_{p\_id}(\Pi_{p\_id}(passengers) - \Pi_{p\_id}(passengers \bowtie bookings)) \) subtracts passengers who have bookings from all passengers (**`2-c`**). - (`d` uses `\exists b \in bookings` which selects passengers *with* bookings, not `NOT IN`). - **Query 3 (Passengers on `'Indigo'` flights after `'2025-05-10'`):** - **Tuple Relational Calculus (`e`):** Properly joins `p.p_id = b.p_id` and `f.f_id = b.f_id` with `f.f_name = 'Indigo' AND f.f_date > '2025-05-10'` (**`3-e`**). - (`f` fails to equate the join attributes `p` and `z`, or `a` and `y` in `bookings`). - Therefore, both **`1-a, 2-c, 3-e` (Option B)** and **`1-b, 2-c, 3-e` (Option C)** are correct. **Answer: Options B and C.** A: **Incorrect:** `2-d` finds passengers *with* bookings instead of `NOT IN`, and `3-f` lacks join conditions on `bookings`. B: **Correct:** `1-a` (RA), `2-c` (RA set difference), and `3-e` (TRC join) are all valid equivalents. C: **Correct:** `1-b` (DRC), `2-c` (RA set difference), and `3-e` (TRC join) are all valid equivalents. D: **Incorrect:** `2-d` and `3-f` are both incorrect.

**1. Determine Foreign Key Dependencies Between the Four Tables:** - From Figure 2 (`IPLt20` schema diagram): - **`teams`** has primary key `team_id` and no foreign keys. Thus **`teams` must be created first**. - **`points_table`** references `teams(team_id)`, so `points_table` can be created any time after `teams`. - **`schedule`** has primary key `match_id` and references `teams(team_id)` (for `team_1` and `team_2`), so `schedule` must be created after `teams`. - **`results`** references `schedule(match_id)`, so **`results` must be created after `schedule`**. - Since `points_table` and `schedule` do not depend on each other, both: - **`teams → points_table → schedule → results` (Option A)** and - **`teams → schedule → points_table → results` (Option D)** are valid table creation orders. **Answer: Options A and D.** A: **Correct:** Creates `teams` before `points_table` and `schedule`, and creates `schedule` before `results`. B: **Incorrect:** `schedule` references `teams`, so `teams` must be created before `schedule`. C: **Incorrect:** `results` references `schedule` and `schedule` references `teams`, so `results` cannot be created first. D: **Correct:** Creates `teams` first, then `schedule` and `points_table`, and finally `results`.

**1. Standard SQL `UPDATE` Syntax:** - The standard SQL syntax for updating rows in a table is: `UPDATE <table_name> SET <column> = <value> WHERE <condition>;` - Applying this to update `captain` to `'Hardik Pandya'` for `'Mumbai Indians'` in table `teams`: `update teams set captain = 'Hardik Pandya' where team_name = 'Mumbai Indians'` **Answer: update teams set captain = ’Hardik Pandya’ where team_name = ’Mumbai Indians’ (Option A).** A: **Correct:** Follows the standard SQL `UPDATE <table_name> SET ... WHERE ...` clause order. B: **Incorrect:** Places the `WHERE` clause before the `SET` clause, which is a syntax error in SQL. C: **Incorrect:** Includes the keyword `table` (`update table teams`), which is invalid SQL syntax. D: **Incorrect:** Uses `alter` instead of `set` inside an `UPDATE` statement.

**1. Analyze the Two Correlated Subqueries in the `WHERE` Clause:** - **First Subquery:** ```sql SELECT e2.salary FROM Employee e2 WHERE e2.dept_id = e.dept_id ORDER BY e2.salary DESC LIMIT 1 OFFSET 2 ``` - Orders salaries in the employee's own department (`e2.dept_id = e.dept_id`) in descending order. - `OFFSET 2` skips the first 2 rows (1st highest and 2nd highest), and `LIMIT 1` selects the **3rd highest salary in that department**. - Thus `e.salary > (...)` selects employees who **earn more than the third highest salary in their department**. - **Second Subquery:** ```sql SELECT MAX(e3.join_date) FROM Employee e3 WHERE e3.dept_id = e.dept_id ``` - Finds the latest (`MAX`) `join_date` in the **same department** (`e3.dept_id = e.dept_id`). - Thus `e.join_date < (...)` selects employees who **joined before the most recent hire in the same department**. **Answer: The query returns employees who earn more than the third highest salary in their department and joined before the most recent hire in the same department (Option C).** A: **Incorrect:** `OFFSET 2` (0-indexed) returns the 3rd row (third highest salary), and the second subquery filters by `e3.dept_id = e.dept_id` (same department, not company-wide). B: **Incorrect:** The highest salary would be `OFFSET 0`, whereas `OFFSET 2` is the third highest salary. C: **Correct:** `ORDER BY salary DESC LIMIT 1 OFFSET 2` gets the 3rd highest salary in the department, and `< MAX(join_date)` checks that they joined before the department's most recent hire. D: **Incorrect:** `<` on `join_date` means joined *before* (earlier than), and `>` on `salary` means earns *more* than.

**1. Check Conflict Serializability of Schedule `S1`:** - `S1: W1(C), R3(C), R2(A), W1(C), W3(B), W2(A)` - Conflicting operations in `S1`: - On item `C`: `W1(C)` precedes `R3(C)` (\( T_1 \to T_3 \)), and `R3(C)` precedes the second `W1(C)` (\( T_3 \to T_1 \)). - Because there is a cycle \( T_1 \leftrightarrow T_3 \) in the precedence graph of `S1`, **`S1` is NOT conflict serializable** and therefore **cannot** be produced by Two-Phase Locking (2PL) (**Options A and B are false**). **2. Check Conflict Serializability and 2PL of Schedule `S2`:** - `S2: W1(B), R1(B), R2(A), W3(C), W2(C), W1(A)` - Conflicting operations in `S2`: - On item `B`: only \( T_1 \) accesses `B`. - On item `A`: `R2(A)` precedes `W1(A)` \( \implies T_2 \to T_1 \). - On item `C`: `W3(C)` precedes `W2(C)` \( \implies T_3 \to T_2 \). - The precedence graph is \( T_3 \to T_2 \to T_1 \), which is **acyclic**! Thus **`S2` is conflict serializable** (equivalent to \( T_3, T_2, T_1 \)) and **can be two-phase lockable** (**Options C and D are true**). **Answer: Options C and D.** A: **Incorrect:** `S1` has a cycle \( T_1 \to T_3 \to T_1 \) on item `C` (`W1(C) ... R3(C) ... W1(C)`), so it is not conflict serializable. B: **Incorrect:** Every 2PL schedule must be conflict serializable; since `S1` is not conflict serializable, it cannot be two-phase lockable. C: **Correct:** The precedence graph for `S2` is \( T_3 \to T_2 \to T_1 \) with no cycles, so `S2` is conflict serializable. D: **Correct:** `S2` is conflict serializable and transactions can acquire and release locks in two phases (`T3` locks/unlocks `C`, `T2` locks `A, C` then unlocks, `T1` locks `B, A` then unlocks).

**1. Trace the Timestamp Ordering Protocol on `S: R3(B), R3(C), W2(A), W1(B), W2(C), R1(A)`:** - Given timestamps: \( TS(T_1) = 2,\; TS(T_2) = 6,\; TS(T_3) = 13 \). - **1. `R3(B)`:** Succeeds; sets \( R\text{-}TS(B) = 13 \). - **2. `R3(C)`:** Succeeds; sets \( R\text{-}TS(C) = 13 \). - **3. `W2(A)`:** Succeeds; sets \( W\text{-}TS(A) = 6 \). - **4. `W1(B)`:** \( TS(T_1) = 2 < R\text{-}TS(B) = 13 \). Since a younger transaction (\( T_3 \)) has already read `B`, **`W1(B)` is rejected and Transaction `T1` must Roll Back!** - **5. `W2(C)`:** \( TS(T_2) = 6 < R\text{-}TS(C) = 13 \). Since a younger transaction (\( T_3 \)) has already read `C`, **`W2(C)` is rejected and Transaction `T2` must Roll Back!** - (Even if `R1(A)` were reached, \( TS(T_1) = 2 < W\text{-}TS(A) = 6 \) would also roll back `T1`). - Therefore, **Transactions `T1` and `T2` need to Roll Back**. **Answer: Transaction T1 and T2 needs to Roll Back (Option D).** A: **Incorrect:** Both `T1` and `T2` attempt to write items already read by the younger transaction `T3` (`TS = 13`). B: **Incorrect:** `T3` has the largest timestamp (`13`) and executes its reads first without conflict. C: **Incorrect:** `T3` does not roll back; `T1` and `T2` roll back. D: **Correct:** `W1(B)` violates `TS(T1) < R-TS(B)` (`2 < 13`) and `W2(C)` violates `TS(T2) < R-TS(C)` (`6 < 13`), rolling back both `T1` and `T2`.

**1. Find Which Index Level Is the Root (Single Block) and Count Block Accesses:** - Index blocking factor (fan-out) \( f_i = 30 \). - Number of index blocks at each level from innermost `L1` outward: - Level `L1`: \( 24,300,000 \) blocks - Level `L2`: \( \lceil 24,300,000 / 30 \rceil = 810,000 \) blocks - Level `L3`: \( \lceil 810,000 / 30 \rceil = 27,000 \) blocks - Level `L4`: \( \lceil 27,000 / 30 \rceil = 900 \) blocks - Level `L5`: \( \lceil 900 / 30 \rceil = 30 \) blocks - Level `L6`: \( \lceil 30 / 30 \rceil = 1 \) block (root index level, or in a 6-level index, traversing the 6 levels requires 6 block accesses as per the course convention). - Therefore, the number of block accesses required is **6**. **Answer: 6 (Option D).** A: **Incorrect:** 4 block accesses cannot traverse a 6-level index. B: **Incorrect:**The official key counts the 6 index levels (`6`). C: **Incorrect:** 5 is one less than the 6 levels. D: **Correct:** With 6 levels (`L6` down to `L1`, where `L1` has \( 30^5 = 24,300,000 \) blocks), 6 block accesses are required.

**1. Construct the Bitmap Vectors for `Project = 'ProjectA'` and `Skill = 'SQL'`:** - Looking at the 8 rows of Table 3 (`EmployeeProjects`): - **Row 1:** `(201, Ram, ProjectA, Java)` \( \to \text{ProjectA} = 1,\; \text{SQL} = 0 \) - **Row 2:** `(202, Surya, ProjectA, SQL)` \( \to \text{ProjectA} = 1,\; \text{SQL} = 1 \) - **Row 3:** `(201, Ram, ProjectB, Java)` \( \to \text{ProjectA} = 0,\; \text{SQL} = 0 \) - **Row 4:** `(203, Vikram, ProjectB, SQL)` \( \to \text{ProjectA} = 0,\; \text{SQL} = 1 \) - **Row 5:** `(204, Harish, ProjectA, Python)` \( \to \text{ProjectA} = 1,\; \text{SQL} = 0 \) - **Row 6:** `(206, Sanjay, ProjectA, SQL)` \( \to \text{ProjectA} = 1,\; \text{SQL} = 1 \) - **Row 7:** `(204, Harish, ProjectB, Python)` \( \to \text{ProjectA} = 0,\; \text{SQL} = 0 \) - **Row 8:** `(202, Surya, ProjectB, SQL)` \( \to \text{ProjectA} = 0,\; \text{SQL} = 1 \) - Thus: - Bitmap for `'ProjectA'`: **`11001100`** - Bitmap for `'SQL'`: **`01010101`** - Since we want employees working on `'ProjectA'` **AND** having skill `'SQL'`, we perform bitwise **`AND`**: **`11001100 AND 01010101`** **Answer: 11001100 AND 01010101 (Option B).** A: **Incorrect:** Uses `OR` instead of `AND` and has incorrect bitmaps. B: **Correct:** `'ProjectA'` appears in rows 1, 2, 5, 6 (`11001100`) and `'SQL'` appears in rows 2, 4, 6, 8 (`01010101`), combined with `AND`. C: **Incorrect:** `10101010` is the complement of the `'SQL'` bitmap. D: **Incorrect:** `00110011` is the bitmap for `'ProjectB'`, not `'ProjectA'`.

**1. Trace B+ Tree Insertion of Order \( p = 4 \) (Max 3 Keys per Node):** - Inserting the 10 keys `17, 81, 31, 56, 36, 44, 21, 90, 6, 85` into an initially empty B+ tree of order 4: - First 3 keys `17, 31, 81` fit in a single root leaf node (height = 0 or 1). - Inserting `56` overflows the leaf (`17, 31, 56, 81`), splitting it into two leaves `[17, 31]` and `[56, 81]` with parent root `[56]` (1 internal level + 1 leaf level). - Continuing through all 10 keys (`36, 44, 21, 90, 6, 85`), the leaf splits propagate keys to the parent, which itself splits once when it exceeds 3 keys, creating a second index level above the leaves. - Thus the resultant B+ tree has height **2**. **Answer: 2.**

**1. Analyze Transaction States at the Time of Crash in Table 4:** - Examining the log records from top to bottom: - **`T0`:** Started before `<Checkpoint L>` and has `<Commit T0>` **after** the checkpoint. Since `T0` committed before the crash, **`T0` must be Redone (Redo)**. - **`T1`:** Started before `<Checkpoint L>` and has `<Commit T1>` **after** the checkpoint. Since `T1` committed before the crash, **`T1` must be Redone (Redo)**. - **`T2`:** Started before `<Checkpoint L>`, modified `D, C, B`, and **never committed** before the crash (no `<Commit T2>` record). Since `T2` was still active at the time of crash, **`T2` must be Undone (Undo)**. - Therefore, **Transaction undo is performed in `T2` (Option C)** and **Transaction redo is performed on both `T0` and `T1` (Option D)**. **Answer: Options C and D.** A: **Incorrect:** Because `T1` committed after the checkpoint, its updates must be redone (`Redo`). B: **Incorrect:** `T2` never committed before the crash, so `T2` undergoes `Undo`, not `Redo`. C: **Correct:** `T2` has no `<Commit T2>` record in the log, so its changes must be undone (`Undo`). D: **Correct:** Both `T0` and `T1` have `<Commit>` records after `<Checkpoint L>`, so both are redone (`Redo`).

**1. Understand Full, Differential, and Incremental Backups:** - **Full Backup (Day 1):** Backs up all data. - **Differential Backup (Days 7 and 12):** Backs up all changes made **since the last Full backup (Day 1)**. - **Incremental Backup (Days 13, 14, 15, 16):** Backs up only the changes made **since the immediately preceding backup** (whether full, differential, or incremental). **2. Determine the Backup Sets Needed When Failure Occurs on Day 17 (Before Day 17's Backup):** - To recover all data up through Day 16, we load: 1. **Day 1 (Full backup)** — 1st set 2. **Day 12 (latest Differential backup)**, which covers all changes from Day 2 to Day 12 — 2nd set 3. **Day 13 (Incremental backup)** — 3rd set 4. **Day 14 (Incremental backup)** — 4th set 5. **Day 15 (Incremental backup)** — 5th set 6. **Day 16 (Incremental backup)** — 6th set - Total backup sets to load = **6**. **Answer: 6.**

**1. Count the Minimum Number of Relations Needed to Convert the ER Diagram:** - **1. `Department(Dept_ID, Dept_Name)`:** 1 relation for strong entity `Department`. - **2. `Project(Project_ID, Title)`:** 1 relation for strong entity `Project`. - **3. `Employee(Emp_ID, Name, Dept_ID)`:** 1 relation for strong entity `Employee` (since each Employee belongs to *exactly one* Department, the 1-to-N relationship `Belongs_To` is merged into `Employee` via foreign key `Dept_ID`). - **4. `Employee_Phone(Emp_ID, Phone_no)`:** 1 separate relation required for the **multivalued attribute** `Phone_no` of `Employee`. - **5. `Works_On(Emp_ID, Project_ID)`:** 1 separate relation required for the **many-to-many (M:N) relationship** `Works_On` between `Employee` and `Project`. - Total minimum number of relations = \( 1 + 1 + 1 + 1 + 1 = 5 \). **Answer: 5.**

**1. Trace Binary Search Tree (BST) Insertion for Key `88`:** - Start at the root **`24`**: since \( 88 > 24 \), go right to **`60`**. - At **`60`**: since \( 88 > 60 \), go right to **`72`**. - At **`72`**: since \( 88 > 72 \), go right to **`96`**. - At **`96`**: since \( 88 < 96 \), go left to **`84`**. - At **`84`**: since \( 88 > 84 \) and `84` has no right child, insert **`88`** as the right child of `84`. - Complete node traversal order: **`24, 60, 72, 96, 84, 88`**. **Answer: 24, 60, 72, 96, 84, 88 (Option D).** A: **Incorrect:** At `60`, since \( 88 > 60 \), we must go right to `72`, not left to `48`. B: **Incorrect:** At `96`, since \( 88 < 96 \), we must go left to `84`, not right to `108`. C: **Incorrect:** At `24`, since \( 88 > 24 \), we must go right to `60`, not left to `12`. D: **Correct:** Follows the BST comparisons \( 88 > 24 \to 88 > 60 \to 88 > 72 \to 88 < 96 \to 88 > 84 \to 88 \).