Computer science 5443 - find a longest sequence of data

Question

This assignment should be completed individually. Please make sure that your answer is legible (typing is preferred).

Question 1. Consider a Linear Hashing index that uses hi(k) = k mod 2iN as hash functions. In the following snapshot, N = 4, i = 0, and Next = 0. Assume that a bucket split will occur as soon as an insertion is made to a bucket that already contains 4 or more records.

	Primary Pages
0	16*	4*	24*
1	9*	25*
10	10*
11	31*	15*	7*	3*

(a) Starting from the given snapshot, find a longest sequence of data entries to insert, so that there is not split of any bucket.

(b) Starting from the given snapshot, find a shortest sequence of data entries to insert, so that each of the four buckets is split exactly once.

Question 2. Given the following instance of the Sailors-Boats-Reserves database, find the answers to the following relational algebra queries.

Sailors
sid	sname	rating	age
22	Dustin	7	45.0
31	Lubber	8	55.5
64	Horatio	7	35.0
85	Art	3	25.5

Boats
bid	bname	color
101	Laker	blue
102	Laker	red
103	Clipper	green
104	Mars	red

Reserves
sid	bid	day
22	101	10/10/08
22	102	10/10/08
31	102	11/10/08
64	101	9/5/08
64	104	11/6/08

(a) Π_color(σ_age>40.0(Sailors) Þa Reserves Þa Boats)
(b) Π_bid(σ_color=red(Boats)) ∩ Π_bid(Researves)
(c) (Π_sid(Sailors) - Π_sid(σ_day<10/11/08(Reserves))) Þa Sailors

Question 3. An inventory database has the following schema, in which primary keys of relations are underlined.

Suppliers(sid, sname, address)

Parts(pid, pname, color)

Catalog(sid, pid, price)

The Catalog lists prices of parts for each supplier. Write each of the following queries in SQL, relational algebra, and tuple relational calculus whenever possible.

(a) List the unique name of suppliers who supplied a red or a green part.

(b) List the name and id of suppliers who supplied every red part.

(c) List pairs of suppliers such that they supplied the same part, but the first supplier charges a higher price than the second supplier.

(d) List the pid of parts that are supplied by different suppliers.