Database Management System · Quiz 2 · Sep 2024

**1. Check whether every original attribute survives:** The original schema contains W, X, Y, Z, A, B, C and D. The proposed components WXYZ, YA and ZBC contain every attribute except D. Therefore their join cannot reconstruct the original full tuples, including their D values. **2. Check dependency preservation:** WX→YZ is local to WXYZ, Y→A is local to YA, and Z→BC is local to ZBC. However, A→D cannot be enforced using these projected relations because none even contains D. **3. Classify the proposal:** Under the intended answer categories it is lossy and not dependency-preserving. More precisely, it fails the initial requirement that a decomposition cover the entire original schema. **Answer: D — Lossy and not dependency preserving.** **Convention note:** Strictly, this is an incomplete schema cover rather than a valid decomposition to which the usual lossless-join test applies. D is the intended category because both required properties fail. A: **Incorrect:** The missing D attribute prevents reconstruction and preservation of A→D. B: **Incorrect:** Even the reconstruction claim fails because D appears in no component. C: **Incorrect:** A→D is not preserved, in addition to the information loss. D: **Correct:** D is omitted and its functional dependency cannot be checked locally.

**1. Choose the useful original dependency:** A→C is given. Augment both sides by D to obtain \(AD\to CD\). This is Armstrong augmentation, not reflexivity. **2. Chain the result:** Since CD→F is also given, transitivity yields \[AD\to CD,\quad CD\to F\quad\Longrightarrow\quad AD\to F.\] **3. Check the rule names:** Reflexivity derives only dependencies whose right side is a subset of the left. F is not in AD, so reflexivity alone cannot justify the final dependency. **Answer: D — augment A→C to AD→CD, then apply transitivity.** A: **Incorrect:** The final inference uses transitivity, not reflexivity. B: **Incorrect:** The first inference requires augmentation rather than reflexivity. C: **Incorrect:** The listed reflexivity justification does not establish the required dependency. D: **Correct:** It correctly augments A→C by D and then uses transitivity with CD→F.

**1. Determine the candidate key:** SID and CID together determine IID, and then InstructorName; CID also determines CourseName. Neither SID nor CID is derivable from other attributes, so both must be in every key. Hence (SID,CID) is the candidate key. **2. Detect the first normal-form violation:** CID alone determines the nonprime attribute CourseName. This is a dependency on a proper subset of the composite key, violating second normal form. **3. State the highest satisfied form:** Assuming atomic attribute values, the relation is in 1NF. Because it fails 2NF, it also fails the stronger 3NF and BCNF requirements. **Answer: A — 1NF.** A: **Correct:** Atomic values satisfy 1NF, while the partial dependency prevents 2NF. B: **Incorrect:** CID→CourseName is a partial dependency on the key (SID,CID). C: **Incorrect:** A relation failing 2NF cannot satisfy 3NF. D: **Incorrect:** CID is not a superkey but determines CourseName, violating BCNF.

**1. Separate attributes by determinant:** OID determines PID and OrderDate; PID determines Quantity and SPID; SPID determines CustID. Use Order(OID,PID,OrderDate), Product(PID,Quantity,SPID), and Sales(SPID,CustID). **2. Check BCNF and dependency preservation:** OID, PID and SPID are keys of their respective components. Every local nontrivial determinant is a superkey. The remaining original dependency OID→CustID follows through OID→PID→SPID→CustID. **3. Check lossless reconstruction:** Order joins Product through PID, a key of Product; the result joins Sales through SPID, a key of Sales. These key-based splits are lossless, retaining the association between orders, products and customers. **Answer: A — Order(OID,PID,OrderDate), Product(PID,Quantity,SPID), Sales(SPID,CustID).** A: **Correct:** It separates the three determining keys, preserves the dependencies and permits lossless joins. B: **Incorrect:** Order contains PID→SPID even though PID does not determine OID, so it is not BCNF. C: **Incorrect:** The proposed Sales relation has SPID→CustID without SPID determining OrderDate. D: **Incorrect:** The large Order component retains non-key dependencies such as PID→Quantity.

**1. Show that F implies G:** From A→B, augment to A→AB; combine with AB→C to get A→C. Thus A→BC. F also explicitly gives D→A and D→E, hence D→AE. **2. Show that G implies F:** A→BC gives both A→B and A→C, so AB→C follows by augmentation. D→AE gives D→A and D→E; chaining D→A with A→C also gives D→AC. **3. Compare closures:** Every dependency in either set follows from the other. Therefore \(F^+=G^+\), so the two dependency sets are equivalent. **Answer: C — F and G are equivalent.** A: **Incorrect:** F does imply G, but G also implies F; a one-way-only conclusion is incomplete. B: **Incorrect:** G does imply F, but F also implies G. C: **Correct:** Both implication directions hold, establishing equivalence. D: **Incorrect:** The two sets have the same dependency closure.

**1. Separate descriptive dependencies:** Put doctor names in Doctor(did,dname), patient names in Patient(pid,pname), and medicine names in Medicine(mid,mname). In each relation the identifier is a key, eliminating the non-key name dependencies from the original prescription relation. **2. Remove independent multivalued facts:** The stated MVDs say a doctor’s patient set and medicine set vary independently. A ternary (did,pid,mid) relation would repeat every patient–medicine combination. Split it into DoctorPatient(did,pid) and DoctorMedicine(did,mid). **3. Check 4NF:** The entity relations have key-based FDs; the binary association relations have no nontrivial stated MVD with a non-superkey determinant. The MVD decomposition is lossless precisely because the patient and medicine sets are independent for a fixed doctor. **Answer: D — Doctor, Patient, Medicine, DoctorPatient and DoctorMedicine relations.** A: **Incorrect:** The three entity tables omit the doctor–patient and doctor–medicine relationships. B: **Incorrect:** Keeping the ternary association retains the nontrivial doctor multivalued dependencies. C: **Incorrect:** Keeping names in association tables leaves non-key identifier-to-name dependencies. D: **Correct:** The three entity tables and two binary relationship tables eliminate the FD and MVD violations.

**1. Read the required parent relationships:** The root is 24, with left child 12 and right child 60. Under 60, 48 has left child 36; 72 has right child 96, whose children are 84 and 108. **2. Use the insertion constraint:** An ancestor must be inserted before its descendants. Insertions in separate branches may be interleaved without changing the final tree. **3. Trace the decisive right branch:** Both A and D insert 72 before 96 and 96 before 84 and 108, while maintaining the other ancestor constraints. B inserts 84 before 96, making 84 their ancestor. C inserts 108 before 96, making 108 their ancestor. **Answer: A, D — 24, 60, 48, 72, 12, 36, 96, 84, 108; 24, 12, 60, 72, 96, 48, 84, 36, 108.** A: **Correct:** Every node is inserted after its ancestors, including 96 before 84 and 108. B: **Incorrect:** 84 precedes 96, so it becomes the parent in that branch instead of a child of 96. C: **Incorrect:** 108 precedes 96 and changes the required right-subtree structure. D: **Correct:** Interleaving the branches is valid, and all ancestor-before-descendant constraints hold.

**1. Find the keys:** Sname cannot be derived, so it is required in every key. (Sname,class) determines teacher; (Sname,teacher) determines class. These are the two candidate keys, making all three attributes prime. **2. Apply 3NF:** In teacher→class, teacher is not a superkey, but the right-hand attribute class is prime. The other given dependency has a candidate-key determinant. Thus 3NF holds, and therefore 2NF holds as well. **3. Apply BCNF:** Teacher alone does not determine Sname, so teacher→class violates the stricter BCNF requirement that every nontrivial determinant be a superkey. **Answer: A, D — Relation is in 2NF as well as in 3NF.; Relation is in 3NF but not in BCNF..** A: **Correct:** 3NF holds, which also implies 2NF. B: **Incorrect:** The relation satisfies 3NF because class is prime. C: **Incorrect:** teacher→class has a determinant that is not a superkey, ruling out BCNF. D: **Correct:** The prime-attribute exception allows 3NF, while BCNF has no such exception.

**1. Count keys for the first dependency set:** With A→B, BC→D and E→A, C and E never occur on a right-hand side and must be in every key. \((CE)^+=ABCDE\), so CE is the unique candidate key and \(m=1\). **2. Count keys for the second set:** B→C→E→AB, with AB→D, so B, C and E each determine the whole relation. A and D cannot start such a chain. Any larger set containing B, C or E is nonminimal, giving \(n=3\). **3. Count keys for the cycle:** A→B→C→D→E→A means each single attribute determines all five. There are five singleton candidate keys, so \(p=5\). **4. Add the counts:** \(m+n+p=1+3+5=9\). **Answer: 9.**

**1. Group the functional dependencies:** A→BC belongs in ABC. AF→J belongs in AFJ. The cycle F→GH, G→I, I→F belongs in FGHI; F, G and I each determine all attributes of that component. **2. Check BCNF and preservation:** A is the key of ABC, AF is the key of AFJ, and F, G and I are keys of FGHI. Each original dependency appears in a component, so the decomposition preserves all dependencies. **3. Verify losslessness:** ABC and AFJ intersect on A, which determines ABC. Their join with FGHI intersects on F, which determines FGHI. Both joins are lossless. **4. Explain the minimum:** Preserving A→B requires a projected dependency involving A and B. A BCNF component containing them cannot include attributes outside ABC, because A determines only ABC. With just one other component, that component must contain F,G,H,I,J; then F→G is nontrivial but F cannot determine J, violating BCNF. Thus two components cannot suffice, and the three shown are minimal. **Answer: 3.**

**1. Count recording surfaces:** Four platters with two recording surfaces each give \(4\times2=8\) surfaces. **2. Multiply all storage factors:** \[8\times1024\times2048\times512=2^3\cdot2^{10}\cdot2^{11}\cdot2^9=2^{33}\text{ bytes}.\] **3. Convert using the options’ binary convention:** \(2^{33}/2^{30}=8\), so the listed answer is 8 GB, more precisely 8 GiB. **Answer: D — 8 GB.** **Convention note:** The exam uses GB for a binary multiple; the precise SI/IEC name for 2³³ bytes is 8 GiB. A: **Incorrect:** The capacity is 1024 times larger than 8 MiB. B: **Incorrect:** This is far below the calculated 2³³-byte capacity. C: **Incorrect:** It double-counts the available surfaces or another factor of two. D: **Correct:** Eight surfaces and the given track, sector and byte counts yield 8 GiB.

**1. Compute one rotation:** At 8000 revolutions per minute, \[T=\frac{60}{8000}\text{ s}=0.0075\text{ s}=7.5\text{ ms}.\] **2. Average the angular wait:** With a uniformly random target sector, the average rotational latency is half a revolution: \(7.5/2=3.75\text{ ms}\). **3. Keep seek time separate:** The 3 ms seek is not part of rotational latency. It would make seek plus average rotation 6.75 ms before transfer time, but that combined access time is not asked. **Answer: A — 3.75 ms.** A: **Correct:** Average rotational wait is half of the 7.5 ms rotation period. B: **Incorrect:** 7.5 ms is a full revolution rather than the average wait. C: **Incorrect:** It incorrectly combines seek time with rotation and also uses seconds instead of milliseconds. D: **Incorrect:** It does not equal the average rotational wait and uses the wrong time unit.