CS 4400 SAMPLE QUIZ 4 Chapters 5, 6, 14, 15 (15.1) from 3rd edition Chapters 10, 11, 13, 14 from 4th edition 1. Desirable properties of relational normalization include (a) minimizing insertion/deletion anomalies (b) minimizing redundancy (c) minimizing update anomalies (d) all of the above 2. A relation schema R is in 3rd normal form if (a) each nonprime attribute in R is fully dependent on every key (b) all attributes in R have atomic domains (c) R satisfies 2nd normal form and no nonprime attribute of R is transitively dependent on the primary key (d) R contains only 3 keys 3. If a relation R is decomposed into {R1, R2, ..., Rn} and the decomposition is lossless then (a) the natural join of R1, R2, ..., Rn will have the same number of tuples as the original relation for R (b) the natural join of R1, R2, ..., Rn can have more tuples than the original relation for R (c) the relations R1, R2, ...,Rn are each in 3rd normal form (d) none of the above 4. If the following functional dependencies, (A -> B, B -> C) hold for database schema R(A,B) and S(B,C), then the join of R and S will be (a) lossy (b) lossless (c) non lossless (d) none of the above 5. If we use the algorithm for producing a Lossless Join Decomposition into 3rd normal form with the relation schema of R(A,B,C) and the set of Fds as (AB -> C, C -> A), then the the algorithm would produce as output (a) a relation schema with (C,A) and a relation schema with (C,B) (b) a relation schema with (A,B,C) (c) a relation schema with (C,A) and a relation schema with (A,B) (d) a relation schema with (A), a relation schema with (B) and a relation schema with (C) 6. If we use the algorithm for producing a Lossless Join Decomposition into Boyce-Codd normal form with the relation schema of R(A,B,C) and the set of Fds as (AB -> C, C -> A), then the the algorithm would produce as output (a) a relation schema with (C,A) and a relation schema with (C,B) (b) a relation schema with (A,B,C) (c) a relation schema with (C,A) and a relation schema with (A,B) (d) a relation schema with (A), a relation schema with (B) and a relation schema with (C) 7. We have the set of Fds, (B -> C, C -> A, B -> D), for the relation schema R(A,B,C,D). Which of the following decompositions has the dependency preserving property? (a) a decomposition with relation schemas (C,A) and (C,B,D) (b) a decomposition with relation schemas (A,C,D) and (B,D) (c) a decomposition with relation schemas (C,A) and (A,B,D) (d) all of the above 8. One of the timing components involved with reading data from disk is the seek time, which is the time needed (a) to transfer a block from disk to main memory (b) for the read/write arm to be positioned on the correct track (c) for the desired sector to rotate under the read/write head (d) to search the main memory buffer area 9. For a B+ tree of order 10, consisting of 3 levels, the maximum number of leaf nodes would be (a) 121 (b) 100 (c) 1000 (d) 36 10. The insertion of a record in a B+ tree will always cause the height of the tree to increase by one when (a) the tree consists of only a root node (b) the record is to be inserted into a full leaf node (c) all the nodes in the path from the root to the desired leaf node are full before insertion (d) all the nodes in the B+ tree are half full 11. When searching a B+ tree for a range of key values (a) the search always starts at the root node (b) the search always ends at a leaf node (c) multiple leaf nodes may be accessed (d) all of the above 12. An index is used in relational database systems (a) to improve the efficiency of normalizing relations (b) to improve the efficiency of retrieving tuples from a relation (c) to improve the efficiency of the Create Table statement (d) none of the above 13. Linear Hashing has the following characteristic(s) (a) it avoids having to reorganize the entire hash file at one time (b) it maintains overflow buckets when needed (c) it incrementally adds new buckets to the primary area (d) all of the above 14. Linear Hashing (a) supports the efficient reading of the file in order by key value (b) does not maintain overflow chains (c) has a maximum successful search cost of 1 bucket (d) does none of the above 15. Consider the insertion of a record into a Linear Hash file that started with 1 bucket where currently the next bucket to split is number 4 and the number of times the file has doubled is 7. If the key for the record to be inserted is 601, then what bucket should store this record? (a) 5 (b) 255 (c) 89 (d) 11 16. Consider the insertion of a record into a Linear Hash file that started with 1 bucket where currently the next bucket to split is number 2 and the number of times the file has doubled is 5. If the insertion triggers an expansion of the main file, then what bucket number should be added to the file? (a) 2 (b) 32 (c) 34 (d) 17 17. Extendible Hashing (a) uses an index (b) does not maintain overflow chains (c) has a one disk-access search cost (if index fits in memory) (d) does all of the above 18. Consider the search for a record from an Extendible Hash file whose index level is 4. If the hash function produces the bit string 110001, then what bucket should have this record? (a) the bucket whose address is 17 (b) the bucket whose address is stored in index entry 24 (c) the bucket whose address is stored in index entry 49 (d) the bucket whose address is stored in index entry 12 19. Consider an Extendible Hash file whose index level is 4. If we insert a record with hash key value 0010100 into a full bucket of 2 records with hash key values 0010001 and 0010010 and whose bucket level is 4, then the following will take place: (a) the index will double in size (b) at least one record will move to the new bucket (c) a new bucket will be added (d) all of the above 20. Tracks on a disk are (a) the smallest unit of access for reading/writing (b) concentric circles on a platter, which are comprised of sectors (c) composed of a number of cylinders (d) non magnetized areas on a disk's surface 21. Given the following schema R(Emp#,Dept#,City) with functional dependencies, F = {Emp# -> City, Emp# -> Dept#, Dept# -> City, Emp#,Dept# -> City}, which set of functions dependencies is a minimal cover for F? (a) {Emp#Dept# -> City, Emp# -> Dept#} (b) {Emp# -> City, Emp# -> Dept#} (c) {Emp# -> City, Dept# -> City} (d) {Emp# -> Dept#, Dept# -> City} 22. Which of the following functional dependencies are redundant: {A -> B; AD -> C; DB -> E; B -> C} for the relation R(A,B,C,D,E). (a) B -> C (b) A -> B (c) AD -> C (d) DB -> E 23. Which of the attributes are extraneous in the functional dependency, ABC -> D, considering the relational schema R(A,B,C,D,E,G) and FDs {B -> E; C -> G; EG -> D }. (a) A (b) B (c) C (d) none of the above 24. Which nonkey attribute(s) cause a violation of 2NF, based on the primary key definition where the primary key is SID,CID for the relation R(SID,CID,CNAME,SNAME,GRADE) with FDs: {SID -> SNAME; CID -> CNAME; SID,CID -> GRADE}. (a) SNAME (b) CNAME (c) GRADE (d) both (a) and (b) 25. Consider a disk with the following characteristics: 8,192 cylinders, a block size of 4096 bytes, an average rotational latency of 5ms, an average seek time of 7ms, a block transfer time of 0.5ms. How much time would it take to read 100 blocks that are randomly stored on disk? (a) 1250ms (b) 62ms (c) 57ms (d) 12.5ms ANSWERS ************************************************************ 1. d 2. c 3. a 4. b 5. b 6. a 7. a 8 b 9. b 10. c 11. d 12. b 13. d 14. d 15. c 16. c 17. d 18. d 19. d 20. b 21. d 22. c 23. a 24. d 25. a ********************************************************************