CS 634 Midterm Exam,  March 31, 2014, for practice Spring, 2016

NAME_______________________________________

OPEN BOOK - OPEN NOTES -- CLOSED ELECTRONIC DEVICES  SHOW ALL WORK !
All problems are of equal weight, 20 points each. Note: this exam does not cover Chapter 15, but ours will.

1. Tables and FKs

1. Write a Create Table statement for the Passwords table of pg. 267, Exercise 7.5.  Allow up to 20 chars in the username and 25 chars in the password.













2. Suppose username is the PK of the users table. Add a clause to the create table you wrote above for Passwords to ensure that each username in use in Passwords is a good username in users.
3. Draw an E-R diagram for Passwords and Users, following the model of Figure 2.2 of the text, pg. 30.

 

 

 

2. B+-Tress. An Oracle table has 40,000,000 rows, each 100 bytes long., with primary key pid (int) and two other int columns c1 and c2. There is a non-clustered B+-tree index on c1.  The page size is 8KB, with 8000 bytes usable, aside from page header.

1. Calculate the data entry size assuming a keyvalue of 4 bytes, and a rowid of 12 bytes.  Then calculate how many data entries will fit on a page densely (as many as possible). According to pg. 346, B+ trees typically maintain 67%  (or 2/3) space occupancy.  Use this to estimate the average number of data entries per page.

 

 

 

2. Again using 67% occupancy, estimate the number of page pointers would exist in a non-leaf index page.  Assume page pointers are 6 bytes long.

 

 

3. Determine how many leaf level pages there will be in the B+-tree.

 

 

4. Determine the number of number of index pages in the level just above the leaf level.

 

 

5. Determine the number of levels in the B+-tree.

 

 

 

 

3. Hash Tables. Consider the linear hash table from homework 3. The 4 has just been inserted without split.

1. Suppose a key x hashes to 42 with the basic hash function h. We are trying to look up x to see if it’s in the hash table.  Explain how Next = 1 is used to guide the lookup to the right bucket of the hash table, and which bucket that is.

 

 

 

 

2. Give a hash value that is new to the hash table and would fill in the empty spot in the very first bucket.

 

3. Consider inserting a key y that hash value 46.  Does it cause a split?  Show the resulting hash table by fixing up the diagram above.

 

4. Joins. Consider a join T1 JOIN T2 on the join column TID appearing in both tables and is the primary key of T2.

1. Table T1 contains 180,000 tuples and has 20 tuples per page
2. Table T2 contains 90,000 tuples and has 10 tuples per page
3. Both tables are stored in heap files
4. There are no indexes in use here.
5. 100 buffer pages are available

What is the cost (in page i/os) of joining T1 and T2 using sort-merge join? Don’t count the cost of writing out the result of the join.  Show the passes of any sort (number and length of runs), to prove the number of passes you believe, and then further processing for the join.

 

 

 

 

 

 

 

 

5.  Index selection and reduction factors. Consider table

Reserves (sid: integer, bid: integer, day: dates, rname: string)

• 40 bytes long tuple, 100K records, 100 tuples per page, 1000 pages
• Table data is in a Heap file (no sort has been made)

 

Suppose we have  the following indexes on Reserves:

1. B+-tree index BI1 on (day, rname)
2. B+-tree index BI2 on (sid, bid, day)
3. Hash index H1 on (bid)
4. Hash index H2 on (sid)

 

1. Consider the Selection:

select * from reserves r
    where r.day = 8/12/03 and r.bid = 22

 

Which indexes match this selection?  For each match, give the primary conjuncts.

 

 

 

2. If there are 100 days of data (including 8/12/03), and 200 boats having unique bid values in the database, estimate the number of rows returned by the query of part a., showing work.

 

 

3. Consider the Selection

select count(*) from reserves
    where bid = 22 and sid = 10. 

 

Which single index matches so well that it yields an index-only plan?

What combination of indexes could be used?