=========================preview======================
(comp231)[2006](f)final~hpip^_56681.pdf
Back to COMP231 Login to download
======================================================
COMP231 C Fall 2006
FINAL EXAM (Sample Solution)
Problem 1 C Relational Model (28%)
Suppose a movie database contains the following three tables (primary keys are underlined and foreign keys are in italics):
MOVIE (TITLE, DIRECTOR, YEAR, COMPANY)
ACTOR (AID, ANAME, GENDER)
PLAYS (TITLE, AID, PAY)
Write the following queries in SQL, relational algebra, and/or relational calculus as specified.
1] Find the distinct names of the actors who played in a movie directed by An LEE in 2005.
1a] Algebra (3%)
name ( Actor JOIN (Director=An Lee and Year=2005 ( Movie ) JOIN Plays ) )
1b] Calculus (3%)
{ <n> | . i,g ( <i,n,g> Actor . t,p ( <t,i,p> Plays . d,y,c ( t,d,y,c ) Movie d=An Lee y=2005 ) ) }
1c] SQL (3%)
Select distinct AName
From Movie, Actor, Plays
Where Movie.Director=An Lee
And Movie.Year=2005
And Movie.Title=Plays.Title
And Plays.AID=Actor.AID
2] Find the distinct directors who have directed movies for all companies of existing movies. (Hint: this is a division query)
2a] Algebra (3%)
Director,Company movie Company movie
2b] Calculus (3%)
{ <d> | . c ( . t,y ( <t,d,y,c> movie ) ) }
2c] SQL (3%)
Select distinct director
From movie m1
Where not exists (select company from movie
except
select company from movie m2 where m1.director=m2.director)
3] For each movie that involves more than 100 actors, list the movie title and the number of actors involved in the movie.
SQL (5%)
Select movie.title, count(aid)
From movies, plays
Where movie.title=play.title
Group by movie.title
Having count(aid)>100
4] For each company, list the name of the actor whose total earning on the movies produced by the company is the highest among all actors who played movies for the company.
SQL (5%)
Select p.company, actor.aname
From (select company, aid, sum(pay) as total_pay
from plays, movie
where plays.title=movie.title
group by company,aid) as p, actor
where p.aid=actor.aid
and p.total_pay=(select max(total_pay)
from p as p2
where p2.company=p.company)
Problem 2 C Extendable Hashing (8%)
An extendable hashing structure contains a bucket address table (a directory) and a number of hash buckets. The address table and each bucket are labeled with the number of bits used for the address table and the bucket respectively. The entries in the address table are pointers to the hash buckets. Suppose in our extendable hashing scheme, the hash function Hi uses the least significant i bits of the binary representation of a search key as the hash value (e.g., H1(5) = 1, H2(5) = 01, H3(5) = 101). Furthermore, there is no overflow bucket, i.e., a bucket will split when it is full and needs to accommodate a new search key. Finally, assume each hash bucket can hold up to four search keys.
1] Draw the