Database Management System · Quiz 2 · Jan 2026

**1. Read Works On participation:** The employee side has total participation, but the project side is single-lined. Thus every employee participates, while a project is allowed to have no currently assigned employee. **2. Read department relationships:** The Works In arrow toward Department makes an employee belong to at most one department; the employee’s double participation line makes this exactly one. The Department side of Has is not total, so an empty-project department is permitted. **3. Read the dependent relationship:** The arrow toward Employee and total participation of Dependent mean every dependent is associated with exactly one employee. Constraints on one relationship must not be transferred to a different relationship. **Answer: A, B, D — A project may exist on which no employee is currently working.; There may exist a department which currently has no ongoing projects; Every dependent depends on exactly one employee.** A: **Correct:** Single participation on the Project side of Works On allows a project without assigned employees. B: **Correct:** The diagram does not require every department to participate in Has, so a department can have no projects. C: **Incorrect:** The arrow toward Department imposes at most one department per employee, not multiple departments. D: **Correct:** The dependent-side total participation and arrow toward Employee give exactly one employee per dependent.

**1. Track the allowed search interval:** During a BST search for 52, a probe larger than 52 lowers the upper bound; a smaller probe raises the lower bound. Every later probe must stay within all earlier bounds. **2. Check A and B:** A keeps the target between successive bounds: 85,62 set upper bounds; −18 raises the lower bound; 55 lowers the upper bound; −8 and 51 raise the lower bound before reaching 52. B similarly respects \((-22,78)\), then \((-22,68)\), then \((-10,68)\), followed by upper bounds 58 and 55. **3. Reject the violations:** C reaches 45 after −25 and 82, so the next node must exceed 45; −10 violates that. D begins 28 then 75, so subsequent nodes must lie between 28 and 75; −15 already violates that interval. **Answer: A, B — 85, 62, -18, 55, -8, 51, 52; 78, -22, 68, -10, 58, 55, 52.** A: **Correct:** Every node remains within the ancestor-imposed interval and follows the target-directed branch. B: **Correct:** The alternating lower and upper bounds remain consistent through the final 52. C: **Incorrect:** After probing 45, going toward 52 requires its right subtree, where −10 cannot occur. D: **Incorrect:** After the root probe 28, the search stays in its right subtree, so −15 cannot be a later probe.

**1. Find the candidate keys:** R never appears on a dependency’s right side, so every key contains R. RS is a key because S supplies P,Q and PQR then supplies T. PQR is another key through PQR→ST. Both are minimal. **2. Count superkeys containing RS:** Attributes P,Q,T may each be included or omitted, giving \(2^3=8\) sets. **3. Count the remaining case:** Without S, a superkey must contain P,Q,R so that it can first derive S. T is optional, giving two additional sets: PQR and PQRT. **4. Add disjoint cases:** \(8+2=10\). The second case explicitly excludes S, so none of the eight first-case superkeys is counted twice. **Answer: 10.**

**1. Identify the natural-join column:** employee and designation share desgID. designation.desgID is a primary key, while employee.desgID references it. **2. Bound matches per employee:** Each employee row can match at most one designation row, because the referenced designation value is unique. Six designations therefore do not multiply each employee into six outputs. **3. Achieve the maximum:** If all 100 employees have non-null valid designation values, each contributes exactly one joined row. The maximum is 100; the department table is not joined in the query. **Answer: 100.**

**1. Find mandatory key attributes:** D and G never occur on the right of any dependency, so every key must contain both. From G→ABH and GB→C we obtain A,B,C,H; from D→EF we obtain E,F. Thus DG is the unique candidate key. **2. Inspect the redundant dependency:** CDE→F follows already from D→EF, which in particular gives D→F. Removing CDE→F therefore preserves not only the candidate key but the entire dependency closure. **3. Check the other removals:** Removing G→ABH loses the means to derive A,H; removing D→EF loses E; removing GB→C loses C. DG would no longer suffice in those cases, so the candidate-key set changes. **Answer: B — CDE → F.** A: **Incorrect:** Without this dependency, A and H can no longer be derived from DG. B: **Correct:** CDE→F is implied by D→F and can be removed without affecting candidate keys. C: **Incorrect:** Without D→EF, E cannot be obtained from DG, so its key status changes. D: **Incorrect:** Without GB→C, C cannot be obtained from DG, so additional key attributes become necessary.

**1. Derive the candidate keys:** R and S never occur on any right side and must be in every key. Adding P gives Q and then T; adding Q gives T via QR and then P; adding T gives P then Q. The candidate keys are RSP,RSQ,RST. **2. Classify attributes:** Every attribute occurs in at least one candidate key, so all attributes are prime. For each nontrivial listed dependency, the right-side attributes are therefore prime, satisfying 3NF’s prime-attribute alternative. **3. Test BCNF:** T→P violates BCNF because T alone does not determine R or S and is not a superkey. Thus the original relation is in 3NF but not BCNF. **Answer: C — 3NF.** A: **Incorrect:** The relation already satisfies the stronger 3NF condition, so 1NF is not its highest normal form. B: **Incorrect:** All attributes are prime and the relation satisfies 3NF, beyond 2NF. C: **Correct:** Every dependency has a prime right-side attribute, while a non-superkey determinant prevents BCNF. D: **Incorrect:** T→P has a determinant T that is not a superkey of the full relation.

**1. Isolate the troublesome dependency:** CH→G has a determinant that does not determine all of R. Decompose losslessly into CHG and ABCDEFH: the intersection CH determines the first component. **2. Decompose the remaining component:** In ABCDEFH, A determines BCEFH through A→BC, B→CFH and F→E. Split losslessly into ABCEFH and AD, whose intersection A determines ABCEFH. **3. Check BCNF:** CH is a key of CHG. In ABCEFH, each of A,B,E,F determines all its attributes, and all nontrivial projected dependencies have superkey determinants. AD has no nontrivial dependency. Thus all three components are BCNF. **4. Check preservation:** A→BC, B→CFH and E→A are within ABCEFH. F→E is there too; F also derives C,H there and then G via CH→G in CHG. Consequently F→EG is preserved by the union of projected dependencies, and no original FD is lost. **Answer: D — No dependency is lost in the normalization process..** **Convention note:** Dependency preservation is assessed using the union of projected dependencies, allowing inference across them without joining table data. The claim does not require every original FD to appear verbatim inside one component. A: **Incorrect:** The exhibited three-relation lossless BCNF decomposition disproves a claimed minimum of four. B: **Incorrect:** A valid lossless BCNF decomposition has been explicitly constructed. C: **Incorrect:** F derives CH in ABCEFH, and CH derives G in CHG, so F→G is preserved transitively. D: **Correct:** Every original dependency is implied by the dependencies on the resulting relations.

**1. Calculate transfer time:** Reading one 4-KB block at 256 KB/s takes \(4/256=0.015625\) seconds, or 15.625 ms. **2. Add positioning delays:** Total access time includes the stated average seek time, average rotational delay and block transfer time. **3. Sum in consistent units:** \(12+3.5+15.625=31.125\) ms. The common KB unit cancels in the transfer calculation. **Answer: D — 31.125 ms.** A: **Incorrect:** It is smaller than the sum of the stated 15.5-ms positioning delay and 15.625-ms transfer time. B: **Incorrect:** It uses an incorrect transfer-time contribution. C: **Incorrect:** 15.5 ms is only seek plus rotational delay and omits transferring the block. D: **Correct:** The required sum is 12 + 3.5 + 15.625 = 31.125 ms.

**1. Interpret the correlated count:** For each shoe S1, the subquery counts shoes S2 whose price is strictly greater than S1.price. This is the number of shoes ranked ahead of it by descending price. **2. Apply the condition:** COUNT(*)<4 keeps shoes having zero,one,two or three more expensive shoes. These are the first,second,third and fourth most costly shoes. **3. Use the distinct-price assumption:** Since every price differs, there are no tied ranks. The query returns the models of the top four shoes, or all models if fewer than four exist; output order is unspecified without ORDER BY. **Answer: B — models of four most costly shoes..** A: **Incorrect:** The fourth most costly alone would require exactly three more expensive shoes, not a count below four. B: **Correct:** Counts zero through three select the four highest distinct prices. C: **Incorrect:** Counting more expensive shoes does not isolate the fourth least costly shoe. D: **Incorrect:** The least costly shoes have many more expensive alternatives rather than fewer than four.

**1. Separate execution from retrieval:** Executing sends an SQL command to the database. Fetching reads rows from a result set produced by an earlier execution. **2. Match the execute methods:** cursor.execute() runs a command with its parameters; cursor.executemany() runs a command for a sequence of parameter sets. **3. Match the fetch methods:** fetchall() and fetchmany() retrieve already available result rows. They do not execute a new SQL statement. **Answer: A, B — cursor.execute(); cursor.executemany().** A: **Correct:** execute runs an SQL operation with the supplied parameter values. B: **Correct:** executemany executes an operation for successive parameter sets. C: **Incorrect:** fetchall retrieves all remaining rows from a previous query result. D: **Incorrect:** fetchmany retrieves a limited batch of rows rather than submitting SQL.

**1. Compute closures without nontrivial FDs:** If X is any proper subset of ABCD, its closure is only X. There is no dependency capable of deriving an omitted attribute. **2. Identify the superkey:** ABCD determines every attribute by reflexivity. Removing any one attribute leaves a proper subset that fails to determine the removed attribute. **3. Apply minimality:** Therefore ABCD is the unique candidate key. The surrounding braces in the option list a set containing that one candidate key. **Answer: C — {ABCD}.** A: **Incorrect:** Each listed three-attribute set misses a fourth attribute that it cannot derive. B: **Incorrect:** No single attribute determines the remaining attributes without nontrivial dependencies. C: **Correct:** The complete attribute set is a superkey, and every proper subset fails, making it the unique candidate key. D: **Incorrect:** ABCD is a valid candidate key, so rejecting every option is incorrect.

**1. Test losslessness:** The intersection of R1(BCDE) and R2(EA) is E. Since E→A, the intersection determines all of R2, satisfying the binary lossless-join criterion. **2. Test dependency preservation:** D→B and CD→E are represented within R1; E→A is within R2. Their union retains every original FD. **3. Check the normal forms:** CD is a key of R1, but D→B determines a nonprime attribute from the proper subset D. That partial dependency violates 2NF. R2 is BCNF because E is its key. **Answer: B — The decomposition is lossless and dependency preserving..** A: **Incorrect:** The intersection E determines R2, so the decomposition is not lossy. B: **Correct:** It meets the lossless-join condition and retains all three dependencies. C: **Incorrect:** R2 is at least 3NF, but R1 fails 2NF because D→B is a partial dependency on key CD. D: **Incorrect:** R1 is not in 2NF, making the conjunction false.

**1. Simplify the equivalence requirement:** Each of P,Q,R determines the other two. An equivalent cover must therefore let every attribute reach every other attribute by dependency inference. **2. Construct a minimum cover:** \(P\to Q,\ Q\to R,\ R\to P\) forms a directed cycle. Transitivity recovers all six singleton consequences of the original dependencies. **3. Show why fewer cannot suffice:** Every attribute must have an outgoing dependency to determine anything else; a two-edge singleton cover cannot give all three attributes this reachability. Three is the minimum number of singleton FDs. **4. State the convention:** The requested answer three is valid for a minimum-cardinality singleton cover, and also after grouping common left sides in the canonical covers here. Inclusion-minimal singleton covers can contain four edges; those are counted in the next solution. **Answer: 3.** **Convention note:** “Minimal” conventionally means irredundant, not necessarily minimum cardinality. Under singleton-RHS form, some minimal covers have four FDs. The source answer three uses a minimum-size cover or grouped canonical-cover convention; it is not the size of every irredundant singleton cover.

**1. Apply LRU:** Keep blocks ordered from least recently used to most recently used. A hit moves the requested block to the most-recent end; a miss faults and evicts the least-recent block if all three frames are occupied. **2. Trace the first six requests:** Requests 1,3,2 are faults, filling [1,3,2]. Request 4 faults and evicts 1, leaving [3,2,4]. Requests 2 and 3 hit, giving [4,2,3]. There have been four faults. **3. Trace the remaining requests:** Request 1 faults, evicting 4: [2,3,1]. Request 2 hits: [3,1,2]. Request 4 faults, evicting 3: [1,2,4]. Request 3 faults, evicting 1: [2,4,3]. Request 1 faults, evicting 2: [4,3,1]. The last request 4 hits. **4. Count:** Faults occur at request positions 1,2,3,4,7,9,10,11: eight in total. **Answer: 8.**