sample-final-b

pdf

School

University of Alberta *

*We aren’t endorsed by this school

Course

291

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by CorporalFoxPerson645

Family Name: ----------------------------------------------------- Given Name: ----------------------------------------------------- Student ID (last 3 digits): ----------------------------------------------------- University of Alberta Faculty of Science Fall CMPUT 291 – A1 File Structures and Data Management Duration: 2 Hours Aids Allowed: a one-page cheat sheet only. Your examination booklet must have 9 pages (including this page). QUESTION VALUE SCORE 1 9 2 16 3 4 4 4 5 12 6 7 8 8 6 13 TOTAL 72 © Davood Rafiei 2023

CMPUT 291 / A1 Final Exam - Fall Page 2 of 9 Question 1 [ 9 marks in total ] TRUE or FALSE: 1.5 marks for each correct answer; 0 mark for each incorrect answer; 0.5 mark if no choice is selected. a) In ER diagrams, a thick bold line from an entity set to a relationship set means every entity in the set must participate in the relationship. ( ) TRUE ( ) FALSE b) In the relational model, every key is a super key but not vice versa. ( ) TRUE ( ) FALSE c) Every relational algebra query can be expressed in relational calculus. ( ) TRUE ( ) FALSE d) For any pair of relations R and S, . ( ) TRUE ( ) FALSE e) Clustered indexes are generally more efficient than unclustered indexes for both searches and updates. ( ) TRUE ( ) FALSE f) The seek time is the time it takes to search through an index for a key. ( ) TRUE ( ) FALSE Question 2 [ 16 marks in total ] Consider the following tables with the primary key of each table underlined, and a few sample tuples shown. The columns cid and rid in bookings are foreign keys referencing customers and resorts respectively. (( R ▹◃ S ) ▹◃ R ) ▹◃ S = R ▹◃ S cid name city country age c10 Davood Edmonton Canada 20 c20 John Victoria Canada 65 cid rid arrival departure c10 r300 2021/12/17 2021/12/27 c20 r200 2021/12/24 2022/01/03 bookings customers

CMPUT 291 / A1 Final Exam - Fall Page 3 of 9 Express the following queries in SQL. In each case, write a single SQL statement. a) [4 marks] Find the name and the city of customers who have booked a resort in Mexico. b) [4 marks] Find the rid of resorts with at least 80% of their bookings made by customers from Canada. c) [4 marks] Find the names of all pairs of different customers from Edmonton such that both customers stay in the same resort and the days of their stays overlap. rid resort city country suites r200 Andaz Guanacaste Costa Rica 80 r300 Dreams Sands Cancun Mexico 60 resorts

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CMPUT 291 / A1 Final Exam - Fall Page 4 of 9 d) [4 marks] For each country and city that has a resort, list the country and the city, the number of resorts and the number of resorts with a customer booking from Canada. Question 3 [ 4 marks ] Based on the schema in Question 2, write a relational algebra or a relational calculus query (but not both) to find the rid of resorts that have no booking for customers of age 30 or less. Question 4 [ 4 marks ] Based on the schema in Question 2, write a SQL assertion to enforce that no resort can have more bookings (ignoring the dates) than the number of suites in the resort.

CMPUT 291 / A1 Final Exam - Fall Page 5 of 9 Question 5 [ 12 marks in total ] Consider a relation R with attributes ABCDE and functional dependencies {A à B, C à D, E à A}. a) [2 marks] Show that R is not in BCNF. b) [3 marks] List all keys of the relation. Justify that you have found all the keys. c) [2 marks] Is R in 3NF? Justify your answer. d) [3 marks] Using the BCNF decomposition algorithm discussed in class, find a lossless-join decomposition of R into BCNF. Show your work. e) [2 marks] Is your decomposition in Step d dependency-preserving? Explain.

CMPUT 291 / A1 Final Exam - Fall Page 6 of 9 Question 6 [ 8 marks in total ] Consider a B+ tree index where both leaf and non-leaf nodes can hold up to 3 entries. Perform the following operations, each on the specified tree, and show the resulting tree in each step. T1 T2 a) [2 marks] Insert 40* and 45* into T1. b) [2 marks] Insert 50* and 60* into the tree obtained after the insert in step a. c) [2 marks] Delete 85* from T2. d) [2 marks] Delete 55* and 80* from the tree obtained after the delete in step c. Question 7 [ 6 marks in total ] Consider an empty extendable hash file with the usual hash function 18*,35* 44, 80 80*, 85* 45*,55* 4*,16*,40*

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CMPUT 291 / A1 Final Exam - Fall Page 7 of 9 discussed in class, i.e. h i (k) = h(k) mod 2 i where k is a key value and i is a variable that changes as the file is updated. Suppose each bucket can hold up to 3 index entries. Perform the following operations in the given order. Show the final structure with all indicators after each step (interpret the given number for each entry as h(k)). a) [2 marks] Insert 3*,5*, 12* b) [2 marks] Insert 1* c) [2 marks] Insert 8*, 9* Question 8 [ 13 marks in total ] Consider the following query in the context of mini-project 2. r:great p:camera Suppose the full reviews are stored in file reviews.txt ; further assume the review terms

CMPUT 291 / A1 Final Exam - Fall Page 8 of 9 ( rterms ) are organized as a B+ tree and the product terms ( pterms ) are organized as a sorted file. The index entries for both rterms and pterms are in the form of ( term,reviewid,pid ) where pid is the address of the page in reviews.txt where the full record of the respective review is stored. Suppose each page of both the B+ tree index and the sorted file stores 100 index entries, whereas each page of the file reviews.txt stores 50 records. Suppose 5% of the review records satisfy the predicate r:great , 2% of the records satisfy the predicate p:camera and 1% of the records satisfy both predicates. Let N denotes the number of records in reviews.txt , 20N denotes the number of index entries in rterms and 3N denotes the number of index entries in pterms . a) [ 4 marks ] What is the cost (in terms of the number of I/Os) of evaluating the query if the query predicates r:great and p:camera are respectively evaluated using the B+ tree index and the sorted file, before retrieving the matching records from reviews.txt? Assume both the B+ tree and the sorted file are unclustered. Show your work. b) [ 3 marks ] What is the cost (in terms of the number of I/Os) of evaluating the query if the predicate r:great is processed using the B+ tree index, and the matching records are retrieved from reviews.txt before checking the predicate p:camera ? Assume the B+ tree index is unclustered. Show your work.

CMPUT 291 / A1 Final Exam - Fall Page 9 of 9 c) [ 3 marks ] Suppose the sorted file on pterms is clustered. What is the cost of evaluating the query if the predicate p:camera is evaluated first, then the matching records are retrieved from reviews.txt and the predicate r:great is checked? Show your work. d) [ 3 marks ] How does your answer to Parts b and c change if you are instead given the query r:great p:a% and 10% of the records satisfy the predicate p:a% and 2% of the records satisfy both predicates (assume everything else is kept the same).

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

sample-final-b

Related Documents