Database Management System · Quiz 2 · May 2025

We are given the relation \( R = (A, B, C, D) \) with functional dependencies \( \mathcal{F} = \{A \rightarrow B, \; B \rightarrow C, \; C \rightarrow D\} \), decomposed into: - \( R_1 = \{A, B\} \) - \( R_2 = \{A, C, D\} \) **1. Check Lossless Join Property:** - Common attribute: \( R_1 \cap R_2 = \{A\} \). - Attribute closure of \( \{A\} \): Since \( A \rightarrow B \rightarrow C \rightarrow D \), we have \( \{A\}^+ = \{A, B, C, D\} \), so \( A \) is a superkey of both \( R_1 \) and \( R_2 \)! - Therefore, the decomposition is **lossless**. **2. Check Dependency Preservation:** - Projected FDs on \( R_1(A, B) \): \( \mathcal{F}_1 = \{A \rightarrow B\} \). - Projected FDs on \( R_2(A, C, D) \): \( \mathcal{F}_2 = \{A \rightarrow C, \; A \rightarrow D, \; C \rightarrow D\} \). - Can we derive \( B \rightarrow C \) from \( \mathcal{F}_1 \cup \mathcal{F}_2 \)? Compute the closure of \( B \) under \( \mathcal{F}_1 \cup \mathcal{F}_2 \): Since no FD in \( \mathcal{F}_1 \cup \mathcal{F}_2 \) has \( B \) on the LHS, \( \{B\}^+ = \{B\} \), which does not contain \( C \)! - Thus, \( B \rightarrow C \) is **not preserved**, so the decomposition is **not dependency preserving**. **Answer: The decomposition is lossless but not dependency preserving.** A: **Incorrect:** The dependency `B -> C` spans across `R1` and `R2` and cannot be recovered from the projected FDs. B: **Incorrect:** The decomposition is lossless (since `R1 ∩ R2 = {A}` is a key) and not dependency preserving. C: **Correct:** `R1 ∩ R2 = {A}` determines `R1` and `R2` (lossless), but `B -> C` is lost (not dependency preserving). D: **Incorrect:** Because `A` is the key of `R`, intersecting at `{A}` guarantees a lossless join.

Let us find the **irreducible equivalent (canonical cover / minimal cover)** of \( \mathcal{F} = \{A \rightarrow B, \; AB \rightarrow C, \; D \rightarrow AC, \; D \rightarrow E\} \) step by step: **1. Split Right-Hand Sides into Single Attributes:** \[ \mathcal{F}_1 = \{A \rightarrow B, \; AB \rightarrow C, \; D \rightarrow A, \; D \rightarrow C, \; D \rightarrow E\} \] **2. Eliminate Extraneous Attributes from Left-Hand Sides:** - Consider \( AB \rightarrow C \). Since \( A \rightarrow B \) is in \( \mathcal{F}_1 \), the closure of \( A \) includes \( B \) (\( \{A\}^+ \supseteq \{A, B\} \)). Therefore, \( B \) is extraneous on the LHS of \( AB \rightarrow C \), reducing it to **\( A \rightarrow C \)**! \[ \mathcal{F}_2 = \{A \rightarrow B, \; A \rightarrow C, \; D \rightarrow A, \; D \rightarrow C, \; D \rightarrow E\} \] **3. Eliminate Redundant Functional Dependencies:** - Notice that we have \( D \rightarrow A \) and \( A \rightarrow C \). By transitivity, \( D \rightarrow C \) is implied by \( \{D \rightarrow A, \; A \rightarrow C\} \)! - Removing the redundant FD \( D \rightarrow C \) leaves the minimal/irreducible cover: \[ \mathcal{F}_{\text{min}} = \{A \rightarrow B, \; A \rightarrow C, \; D \rightarrow A, \; D \rightarrow E\} \] **Answer: {A -> B, A -> C, D -> A, D -> E} (Option A).** A: **Correct:** Reduces `AB -> C` to `A -> C`, splits `D -> AC` into `D -> A` and `D -> C`, and removes the transitive redundant FD `D -> C`. B: **Incorrect:** `B -> C` is not implied by `F` (only `AB -> C` and `A -> B` were given, which imply `A -> C`, not `B -> C`). C: **Incorrect:** Retains the redundant transitive dependency `D -> C` (which is already implied by `D -> A` and `A -> C`). D: **Incorrect:** Replaces `A -> C` with the invalid `B -> C` and retains redundant `D -> C`.

Let us compare the old schema `Movies` with the new schema `Movies1` and `Movies2`: **1. Old Schema `Movies(MovieID, BranchID, StartTime, EndTime, Title, Genre, TicketPrice)`:** - Primary key is \( K = (\text{MovieID}, \text{BranchID}, \text{StartTime}, \text{EndTime}) \). - Notice the FD \( (\text{MovieID}, \text{BranchID}) \rightarrow \text{Genre} \). - Here, the non-prime attribute `Genre` depends on a **proper subset** \( (\text{MovieID}, \text{BranchID}) \) of the candidate key \( K \) (a **partial dependency**!). - Therefore, the old schema `Movies` was in 1NF, and **did NOT satisfy 2NF**. **2. New Schema `Movies1` and `Movies2`:** - `Movies1(MovieID, BranchID, StartTime, EndTime, Title, TicketPrice)` has key \( K \) and FDs \( K \rightarrow \text{Title} \) and \( K \rightarrow \text{TicketPrice} \) (full dependencies on \( K \), no transitive dependencies). - `Movies2(MovieID, BranchID, Genre)` has key \( (\text{MovieID}, \text{BranchID}) \) and FD \( (\text{MovieID}, \text{BranchID}) \rightarrow \text{Genre} \). - Both `Movies1` and `Movies2` satisfy 2NF, 3NF, and BCNF. **3. Weakest Normal Form Satisfied by the New Schema but Not the Old One:** Among the normal forms satisfied by the new schema that the old schema failed (2NF, 3NF, BCNF), the **weakest** (lowest in the hierarchy \( \text{1NF} \subset \text{2NF} \subset \text{3NF} \subset \text{BCNF} \)) is **2NF**. **Answer: 2NF.** A: **Incorrect:** Both the old and new schemas satisfy 1NF. B: **Correct:** The old schema violated 2NF due to the partial dependency `(MovieID, BranchID) -> Genre`, while the new schema satisfies 2NF (as well as 3NF and BCNF), making 2NF the weakest normal form that distinguishes them. C: **Incorrect:** While the new schema also satisfies 3NF, 2NF is weaker than 3NF and was already violated by the old schema. D: **Incorrect:** BCNF is the strongest of the listed normal forms, whereas the question asks for the *weakest* normal form satisfied by the new schema but not the old.

Let us trace the SQL query and `cur.fetchmany(6)` on Table 1 (`employee`): **1. Filter Rows Where `esalary < 35000`:** Let us check `esalary` for each of the 9 employees in Table 1: - `eid = 5` (Abhijeet): `72000` (No) - `eid = 6` (Shahid): `60080` (No) - `eid = 7` (Shab): `20000 < 35000` (**Match 1**) - `eid = 8` (Meenakshi): `33060 < 35000` (**Match 2**) - `eid = 9` (Dj): `52800` (No) - `eid = 10` (Sashi): `43200` (No) - `eid = 11` (Rekha): `30800 < 35000` (**Match 3**) - `eid = 12` (Joseph): `18224 < 35000` (**Match 4**) - `eid = 13` (Arif): `30375 < 35000` (**Match 5**) **2. Behavior of `cur.fetchmany(6)`:** - The `SELECT` query returns a total of **5 matching rows**. - Calling `cur.fetchmany(6)` requests *up to* 6 rows from the result set. Since only 5 rows exist in the query result, it returns all **5** available rows. **Answer: 5.** A: **Incorrect:** `fetchmany(6)` fetches up to 6 rows, not 1 row (`fetchone()`). B: **Incorrect:** There are 5 employees with `esalary < 35000` (`Shab`, `Meenakshi`, `Rekha`, `Joseph`, `Arif`), not 4. C: **Incorrect:** Although `fetchmany(6)` asks for at most 6 rows, only 5 rows in the table satisfy `esalary < 35000`. D: **Correct:** Exactly 5 rows satisfy `esalary < 35000`, so `cur.fetchmany(6)` returns those 5 rows.

We are given `hotel_information(c_name, c_id, mobile, room_type, room_no)` with functional dependencies: \[ \mathcal{F} = \{\text{c\_id} \rightarrow (\text{c\_name}, \text{mobile}), \quad (\text{c\_name}, \text{mobile}) \rightarrow \text{room\_no}, \quad \text{room\_no} \rightarrow \text{room\_type}\} \] **1. Check Statement 1 (Lossless, Dependency-Preserving BCNF Decomposition):** Let us decompose along each FD: - \( R_1(\text{c\_id}, \text{c\_name}, \text{mobile}) \): key is `c_id`, preserves `c_id -> (c_name, mobile)` \( \rightarrow \) **in BCNF**. - \( R_2(\text{c\_name}, \text{mobile}, \text{room\_no}) \): key is `(c_name, mobile)`, preserves `(c_name, mobile) -> room_no` \( \rightarrow \) **in BCNF**. - \( R_3(\text{room\_no}, \text{room\_type}) \): key is `room_no`, preserves `room_no -> room_type` \( \rightarrow \) **in BCNF**. All three relations are in BCNF, the join is lossless, and every FD in \( \mathcal{F} \) is preserved! Thus, **Statement 1 is correct**. **2. Check Statement 2 (Decomposition into 3NF):** Every relation that is in BCNF is automatically in **3NF** (and 3NF decomposition is always possible for any relation). Thus, **Statement 2 is also correct**. **Answer: Both the statements are correct.** A: **Incorrect:** Statement 2 is also correct because any BCNF decomposition is automatically in 3NF. B: **Incorrect:** Both statements are true. C: **Incorrect:** Statement 1 is true because `R1(c_id, c_name, mobile)`, `R2(c_name, mobile, room_no)`, and `R3(room_no, room_type)` are all in BCNF and preserve all FDs. D: **Correct:** The relation can be decomposed into `R1`, `R2`, and `R3` which are in BCNF (and therefore also 3NF) while preserving all dependencies.

Let us trace the **Most Recently Used (MRU)** page replacement algorithm with **3 page frames** (initially empty) on the reference string: \[ \langle 1, \; 2, \; 3, \; 1, \; 4, \; 5, \; 1, \; 6, \; 2, \; 1, \; 0, \; 3, \; 2 \rangle \] *(In MRU, when a page fault occurs and all frames are full, we evict the page that was **most recently used**, i.e., the page referenced in the immediately preceding step!)* **Step-by-Step Trace:** 1. **`1`**: Frames `[1]` — **Fault #1** (MRU = 1) 2. **`2`**: Frames `[1, 2]` — **Fault #2** (MRU = 2) 3. **`3`**: Frames `[1, 2, 3]` — **Fault #3** (MRU = 3) 4. **`1`**: Hit! Frames `[1, 2, 3]` — *No fault* (MRU = 1) 5. **`4`**: Miss! Evict MRU (`1`) \( \rightarrow \) Frames `[4, 2, 3]` — **Fault #4** (MRU = 4) 6. **`5`**: Miss! Evict MRU (`4`) \( \rightarrow \) Frames `[5, 2, 3]` — **Fault #5** (MRU = 5) 7. **`1`**: Miss! Evict MRU (`5`) \( \rightarrow \) Frames `[1, 2, 3]` — **Fault #6** (MRU = 1) 8. **`6`**: Miss! Evict MRU (`1`) \( \rightarrow \) Frames `[6, 2, 3]` — **Fault #7** (MRU = 6) 9. **`2`**: Hit! Frames `[6, 2, 3]` — *No fault* (MRU = 2) 10. **`1`**: Miss! Evict MRU (`2`) \( \rightarrow \) Frames `[6, 1, 3]` — **Fault #8** (MRU = 1) 11. **`0`**: Miss! Evict MRU (`1`) \( \rightarrow \) Frames `[6, 0, 3]` — **Fault #9** (MRU = 0) 12. **`3`**: Hit! Frames `[6, 0, 3]` — *No fault* (MRU = 3) 13. **`2`**: Miss! Evict MRU (`3`) \( \rightarrow \) Frames `[6, 0, 2]` — **Fault #10** (MRU = 2) Total number of page faults \( = 10 \) (with 3 hits at steps 4, 9, and 12 out of 13 references). **Answer: 10.** A: **Incorrect:** Under-counts the page faults. B: **Incorrect:** There are 13 references and 3 hits, so `13 - 3 = 10` page faults, not 9. C: **Correct:** Tracing MRU across the 13 page references yields 3 hits (at `1`, `2`, `3`) and 10 page faults. D: **Incorrect:** Over-counts the page faults.

We are given the relation `BookPurchases(Customer, Book, Store, City)` where the multivalued dependency: \[ \text{Customer} \twoheadrightarrow \{\text{Book}, \text{City}\} \] (and consequently by complementation, \( \text{Customer} \twoheadrightarrow \text{Store} \)) holds! **1. Definition of Multivalued Dependency \( \text{Customer} \twoheadrightarrow \{\text{Book}, \text{City}\} \):** For a given customer (`Riya`), the set of `(Book, City)` pairs must appear in combination with **every** `Store` associated with `Riya`. - From Row 1: `Riya` has `(Book, City) = (Novel, Delhi)` and `Store = BookWorld`. - From Row 2: `Riya` has `(Book, City) = (Magazine, Mumbai)` and `Store = ReadersHub`. **2. Complete the Cross-Combinations in Rows 3 and 4:** - **Row 3 (`Riya, Novel, H, I`)**: Since `Book = Novel` is paired with `City = Delhi`, we must have **`I = Delhi`**, paired with the second store **`H = ReadersHub`**. - **Row 4 (`Riya, F, G, J`)**: This must be the remaining combination pairing `(Book, City) = (Magazine, Mumbai)` with `Store = BookWorld`: **`F = Magazine`**, **`G = BookWorld`**, and **`J = Mumbai`**. **Answer: F = Magazine, G = BookWorld, H = ReadersHub, I = Delhi, J = Mumbai.** A: **Incorrect:** If `F = Novel`, then `(Magazine, Mumbai)` is never paired with `BookWorld`. B: **Correct:** Pairs `(Novel, Delhi)` with `ReadersHub` (`H = ReadersHub, I = Delhi`) and `(Magazine, Mumbai)` with `BookWorld` (`F = Magazine, G = BookWorld, J = Mumbai`). C: **Incorrect:** Swaps `G` and `H`, repeating rows 1 and 2 instead of forming the cross-tuples. D: **Incorrect:** Swaps the cities and books.

We are given the relation \( R(H, I, J, K, L, M) \) with functional dependencies: \[ \mathcal{F} = \{H \rightarrow IJL, \; IK \rightarrow H, \; L \rightarrow M\} \] **1. Find All Candidate Keys of \( R \):** - Notice that attribute **\( K \)** never appears on the right-hand side of any FD in \( \mathcal{F} \)! Therefore, **\( K \) must be part of every candidate key**. - Closure of \( \{K\} \) alone: \( \{K\}^+ = \{K\} \) (not a superkey). - Try 2-attribute supersets of \( K \): - **\( HK \)**: Since \( H \rightarrow IJL \) and \( L \rightarrow M \), we have \( \{H, K\}^+ = \{H, K, I, J, L, M\} = R \). Since neither \( H \) nor \( K \) alone is a superkey, **\( HK \) is a candidate key**! - **\( IK \)**: Since \( IK \rightarrow H \), and \( H \rightarrow IJL \), and \( L \rightarrow M \), we have \( \{I, K\}^+ = \{I, K, H, J, L, M\} = R \). Thus, **\( IK \) is also a candidate key**! - Other pairs \( JK, LK, MK \) have closures \( \{J, K\}, \{L, K, M\}, \{M, K\} \neq R \), and no other FD can generate \( H \) or \( I \). - Therefore, the **only candidate keys of \( R \) are \( IK \) and \( HK \)** (**Option B is correct**, and Options A and C are false). **2. Check if \( R \) is in BCNF (Option D):** - In the FD \( H \rightarrow IJL \) (and \( L \rightarrow M \)), neither \( H \) nor \( L \) is a superkey of \( R \) (since every superkey must contain \( K \)). - Therefore, **relation \( R \) is NOT in BCNF** (**Option D is correct**). **Answer: IK and HK are the candidate keys of R, and Relation R is not in Boyce-Codd Normal Form (BCNF) (Options B and D).** A: **Incorrect:** `H` does not determine `K` (`{H}+ = {H, I, J, L, M}`), so `H` is not a candidate key. B: **Correct:** `K` is essential (never on RHS), and both `HK` and `IK` have closure `{H, I, J, K, L, M}` and are minimal. C: **Incorrect:** `L` only determines `M` (`{L}+ = {L, M}`), so `L` is not a candidate key. D: **Correct:** The determinants `H` (in `H -> IJL`) and `L` (in `L -> M`) do not contain `K` and are not superkeys, violating BCNF.

Let us construct the **Binary Search Tree (BST)** by inserting `15, 14, 30, 5, 13, 19, 26, 12, 1, 6` in order (with the root node at **level 0**): **1. Step-by-Step Insertion:** - **`15`**: Root (**Level 0**) - **`14`**: `< 15` \( \rightarrow \) left child of `15` (**Level 1**) - **`30`**: `> 15` \( \rightarrow \) right child of `15` (**Level 1**) - **`5`**: `< 15, < 14` \( \rightarrow \) left child of `14` (**Level 2**) - **`13`**: `< 15, < 14, > 5` \( \rightarrow \) right child of `5` (**Level 3**) - **`19`**: `> 15, < 30` \( \rightarrow \) left child of `30` (**Level 2**) - **`26`**: `> 15, < 30, > 19` \( \rightarrow \) right child of `19` (**Level 3**) - **`12`**: `< 15, < 14, > 5, < 13` \( \rightarrow \) left child of `13` (**Level 4**) - **`1`**: `< 15, < 14, < 5` \( \rightarrow \) left child of `5` (**Level 3**) - **`6`**: `< 15, < 14, > 5, < 13, < 12` \( \rightarrow \) left child of `12` (**Level 5**) **2. Evaluate Each Option:** - **Option A**: The deepest node is `6` at **Level 5** (`15 -> 14 -> 5 -> 13 -> 12 -> 6`), so the height is **5**, not 6. (**Incorrect**) - **Option B**: The **leaf nodes** (nodes with no children) are `1`, `6`, and `26`. Their sum is: \[ 1 + 6 + 26 = 33 \] (**Correct**) - **Option C**: Node `1` is the left child of `5`, whereas `13` is the right child of `5`. Thus `1` is **not** in the subtree of `13`. (**Incorrect**) - **Option D**: `15` is at Level 0, `30` is at Level 1, and `19` (left child of `30`) is at **Level 2**. (**Correct**) **Answer: The sum of the leaf nodes of the binary search tree is 33, and Node 19 is at level 2 (Options B and D).** A: **Incorrect:** The longest path from root `15` to leaf `6` has 5 edges, so the height is 5, not 6. B: **Correct:** The leaf nodes are `1`, `6`, and `26`, whose sum is `1 + 6 + 26 = 33`. C: **Incorrect:** Node `1` is the left child of node `5`, not in the left subtree of node `13`. D: **Correct:** Root `15` is at level 0, `30` is at level 1, and `19` (left child of `30`) is at level 2.

In a classic **SQL injection** tautology attack designed to retrieve **all rows** from the `course` table regardless of the `credits = 4` filter: **1. Why `OR` with an Always-True Condition is Required:** - Using `AND 'a' = 'a'` (Option A) or `AND credits = credits` (Option C) evaluates to `credits = 4 AND TRUE`, which still only returns courses where `credits = 4` (not *all* rows). - Using **`OR 1 = 1`** (Option B) or **`OR credits = credits`** (Option D) makes the `WHERE` condition evaluate to `TRUE` for every row in the table (`credits = 4 OR TRUE` \( \equiv \) `TRUE`), retrieving **all rows** from `course`. **Answer: SELECT * FROM course WHERE credits = 4 OR 1 = 1; and SELECT * FROM course WHERE credits = 4 OR credits = credits; (Options B and D).** A: **Incorrect:** `credits = 4 AND 'a' = 'a'` simplifies to `credits = 4`, which only returns rows with 4 credits. B: **Correct:** `OR 1 = 1` is a tautology that makes the `WHERE` clause true for every row, returning all rows in `course`. C: **Incorrect:** `credits = 4 AND credits = credits` still restricts the output to rows where `credits = 4`. D: **Correct:** `OR credits = credits` evaluates to true on all rows, bypassing `credits = 4` and retrieving the entire table.

Let us evaluate each of the four computer science / storage statements: - **Option A**: Binary search repeatedly halves the search interval on a sorted array of \( n \) elements, taking \( O(\log n) \) time. (**Correct**) - **Option B**: In a **linked list**, nodes are dynamically allocated on the heap and connected via pointers; they are **not** required to be stored in contiguous memory locations (arrays use contiguous memory). (**Incorrect**) - **Option C**: In the memory hierarchy, **CPU registers and cache memory (SRAM)** are faster and more costly per byte than main memory (DRAM). (**Incorrect**) - **Option D**: On a magnetic disk, a **sector** is the smallest physical addressable unit of data read or written during disk I/O. (**Correct**) **Answer: Options A and D.** A: **Correct:** Binary search has a worst-case and average-case time complexity of `O(log n)`. B: **Incorrect:** Linked list nodes can be scattered anywhere in memory and are linked via pointers; arrays require contiguous memory. C: **Incorrect:** CPU registers and L1/L2/L3 cache are faster and more expensive per byte than main memory (RAM). D: **Correct:** A sector is the smallest physical unit of data transfer on a magnetic disk.

Let us analyze the two SQL queries on `students(roll_no, sname, age, university)` and `course(course_id, cname, grade, roll_no)`: **1. Query 1 (`SELECT s.sname, c.grade FROM students s NATURAL JOIN course c WHERE university = 'Mumbai'`):** - Query 1 performs a **join** between two different tables (`students` and `course`) on the common attribute `roll_no`. - A **multitable clustering file organization** stores related records from multiple tables (e.g., each `students` tuple alongside its matching `course` tuples) in the same disk block, making join queries like Query 1 execute much more efficiently! (**Option A is correct**). **2. Query 2 (`SELECT sname FROM students WHERE roll_no = 'ME003'`):** - Query 2 accesses a **single table** (`students`) filtering on its primary key `roll_no`. - A **sequential (single-table) clustering file organization** stores `students` tuples contiguously ordered by `roll_no` (without interleaving `course` records from another table), allowing fast lookup and scan on `students` for Query 2! (**Option C is correct**). **Answer: Query 1 will execute more efficiently when multitable clustering file organization scheme is used, and Query 2 will execute more efficiently when sequential clustering file organization scheme is used (Options A and C).** A: **Correct:** Multitable clustering stores each `students` record together with its matching `course` records in the same block, accelerating the join in Query 1. B: **Incorrect:** Query 1 is a two-table join that benefits from multitable clustering rather than sequential single-table clustering. C: **Correct:** Query 2 only reads the `students` table by `roll_no`, which is faster when `students` is stored in a sequential clustering file without interleaved `course` tuples. D: **Incorrect:** Sequential clustering separates `students` and `course` into different files, requiring more block accesses for the join in Query 1.

Consider a Binary Search Tree (BST) with \( N = 31 \) elements (where the root node is at level 0, so a single-node tree has height 0, or let us verify both conventions: notice the difference \( m - n \) is **invariant** to whether height is defined by edges or nodes!). **1. Using the Edge-Count Definition of Height (Root at Level 0):** - **Maximum height \( m \)**: Occurs when the BST is completely skewed (a degenerate chain of 31 nodes): \[ m = N - 1 = 31 - 1 = 30 \] - **Minimum height \( n \)**: Occurs when the BST is a完美/complete binary tree of \( N = 31 = 2^5 - 1 \) nodes: \[ n = \lfloor \log_2(31) \rfloor = 4 \] - **Difference \( m - n \)**: \[ m - n = 30 - 4 = 26 \] **2. Using the Node-Count Definition of Height (Root at Level 1):** - \( m = 31 \) and \( n = \lfloor \log_2(31) \rfloor + 1 = 5 \), which also gives \( m - n = 31 - 5 = 26 \)! **Answer: 26.**