Computer Science 460

Practice Midterm Exam

Part I. Multiple-choice (2 points each)

On the actual exam, you will need to darken the bubble for each multiple-choice answer in a grid on the cover page of the exam. Make sure to completely fill in the appropriate bubble, and to erase any stray marks.

1.    Given the portion of an ER diagram shown above (with a thickened arrow from R to

A), which of the following statements are true?

I.   R connects each entity in A to at least one entity in B

II.  R connects each entity in A to at most one entity in B

III. R connects each entity in B to at least one entity in A

IV. R connects each entity in B to at most one entity in A

A.       only I and II

B.       only II and III

C.       only I and IV

D.       only III and IV

E.       all four statements are true

2.    Consider a relation R(a, b, c) having the following tuples:

(1, 20, 100), (4, 20, 100), (2, 15, 100), and (1, 18, 100).

Which of the following attributes or attribute combinations could be the primary key of the relation? (Assume that no additional tuples will ever be added.)

A.       attribute a

B.       attribute b

C.       either the combination (a, b) or the combination (a, b, c)

D.       either the combination (b, c) or the combination (a, b, c)

E.       only the combination (a, b)

3.    You are given a table named Alums that contains the names and personal

information of all graduates of the college that you work for.  It includes name and age attributes, and a state attribute specifying the state in which a person resides.

Consider the following SQL queries:

I.             SELECT name, MIN(age)

FROM   Alums

WHERE  state = "CA";

II.            SELECT name, age

FROM   Alums

WHERE  state = "CA"

AND age <= ALL (SELECT age FROM Alums

WHERE state = "CA");

III.           SELECT name, age

FROM   Alums

WHERE  state = "CA"

AND age = (SELECT MIN(age) FROM Alums);

Which of these queries would successfully find the name and age of the youngest graduate living in California (CA)?

A.       only I

B.       only II

C.       only III

D.       only I and II

E.       only II and III

4.     You have two relations A and B.  A has three tuples, and B has two.  What is the

maximum number of tuples that could appear in the natural join of A and B?

A.       2

B.       3

C.       4

D.        5

E.        6

5.    The hash table shown at right is being maintained using

dynamic linear hashing.  The key "cat" was just inserted in the table, and as a result an extra bucket (bucket 4) was added to the table.  Which of the keys do we need to consider for possible movement to the new bucket?

A.       only "dog"

B.       only "lion"

C.       only "cat"

D.       both "dog" and "lion"

E.       all four of the keys

PART II: Answer all three questions in the space provided.

II-1.  Relational Queries (10 points total)

Consider the following relational schema (keys are underlined):

Product(pid, name, price, manufacturer)

Buys(cid, pid, month, day, year)

Customer(cid, cname, age)

Note that Buys(cid) references Customer(cid), and Buys(pid) references Product(pid).

a.  Write a single relational algebra query for the following: "Find the names of all

customers who have purchased products that are not manufactured by Acme." You may assume that "Acme" appears somewhere in the manufacturer field of all products manufactured by Acme. (5 points)

Do EITHER b or c below, and clearly indicate which one you want us to grade. (5 points)

b.  Write a single SQL query for the following: "For each product, determine how many  times it was bought in 2010, if at all." The result should be tuples of the form (product name, num times). If a product was not purchased at all in 2010, the second attribute should have a value of 0.

c.  Write a single SQL query for the following: "Find the names of all customers who have not purchased any Acme products."

II-2.  Record Formats and Tree-Based Index Structures (12 points total)

a.  Assume that a DBMS is using variable-length records that begin with a header of field offsets to store tuples from a slightly simplified Movie relation:

Movie(id CHAR(7), name VARCHAR(64), year INTEGER,

rating VARCHAR(5), runtime INTEGER, earnings_rank INTEGER)

If all of the values for a given row (including the primary key) are stored in the record, and we’re using 1-byte characters, 4-byte integer data values, and 2-byte integer metadata, what would the record look like for the following tuple?

("1234567", "The King's Speech", 2010, "R", 118, null)

b.  Consider the following B-tree of order 2:

What would the tree look like after the following sequence of operations:

insert an item whose key is 65, insert an item whose key is 79,

insert an item whose key is 85.

c.  Consider the following B+tree of order 2:

What would the tree look like after the following sequence of operations:

insert an item whose key is 65, insert an item whose key is 79,

insert an item whose key is 85.

II-3.  Dynamic Linear Hashing (8 points total)

Consider the following hash table, which was constructed using linear hashing with  the  hash function h(k) = the length of the string k. For example, "True Lies" has a hash code of 9, because it is 9 characters long.

a. Where would "Stuart Little" (length 13) and "Batman Returns" (length 14) be inserted in this table, assuming that they can be added without growing the table?

(You may find it helpful to make use of the chart of decimal-binary equivalents below.)

b. After these two insertions, if we then increase the size of the table by one bucket,

which keys would need to be rehashed, and which of them (if any) would actually be moved to a different bucket?

rehashed:

moved:

decimal-binary equivalents (for 5-bit non-negative integers):

0 = 00000   8 = 01000   16 = 10000   24 = 11000

1 = 00001   9 = 01001   17 = 10001   25 = 11001

2 = 00010   10 = 01010   18 = 10010   26 = 11010

3 = 00011   11 = 01011   19 = 10011   27 = 11011

4 = 00100   12 = 01100   20 = 10100   28 = 11100

5 = 00101   13 = 01101   21 = 10101   29 = 11101

6 = 00110   14 = 01110   22 = 10110   30 = 11110

7 = 00111   15 = 01111   23 = 10111   31 = 11111