CS 634 Midterm Exam, March 31, 2014, for practice Spring,
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
- 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.
- 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.
- 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.
- 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.
- Again using 67% occupancy, estimate the number of page pointers
would exist in a non-leaf index page. Assume page pointers are 6
- Determine how many leaf level pages there will be in the B+-tree.
- Determine the number of number of index pages in the level just
above the leaf level.
- 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.
- 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.
- Give a hash value that is new to the hash table and would fill in
the empty spot in the very first bucket.
- Consider inserting a key y that hash value 46. Does it cause a
split? Show the resulting hash table by fixing up the diagram
4. Joins. Consider a join T1 JOIN T2 on the join column TID appearing
in both tables and is the primary key of T2.
- Table T1 contains 180,000 tuples and has 20 tuples per page
- Table T2 contains 90,000 tuples and has 10 tuples per page
- Both tables are stored in heap files
- There are no indexes in use here.
- 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
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:
- B+-tree index BI1 on (day, rname)
- B+-tree index BI2 on (sid, bid, day)
- Hash index H1 on (bid)
- Hash index H2 on (sid)
- 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
- 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.
- 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?