Consider the following tables relating to trips on a suburban bus network

Trip(fromPlace:integer, toPlace:integer, tripDate:date)
Place(placeId:integer, address:string, suburb:string)

1. Write an SQL query that returns all of the addresses in Randwick that are the destination of a trip on March 4, 2005.

2. Give a naive translation of the SQL query into a relational algebra expression.

3. Translate the naive relational algebra expression into an equivalent expression using pushing of selections and projections.

4. Translate the optimized relational algebra expression into the most directly corresponding SQL query.

What are the possible join trees (without cross-products) for each of the following queries:

1. select * from R,S,T where R.a=S.b and S.c=T.d

2. select * from R,S,T where R.a=S.b and T.c=R.d

3. select * from R,S,T where R.a=S.b and S.c=T.d and T.e=R.f

4. select * from R,S,T,U
   where R.a=S.b and S.c=T.d and T.e=R.f and T.g=U.h and S.i=U.j

Do not include trees/sub-trees that are reflections of other tree/subtrees.

Consider a table R(a,b,c) and assume that

• all attributes have uniform distribution of data values
• attributes are independent of each other
• all attributes are NOT NULL
• r = 1000,   V(a,R) = 10,   V(b,R) = 100

Calculate the expected number of tuples in the result of each of the following queries:

1. select * from R where not a=k
2. select * from R where a=k and b=j
3. select * from R where a in (k,l,m,n)

where j, k, l, m, n are constants.

Consider the following tables relating to retail sales:

create table Item (
    iname       text,
    category    text,
    primary key (name)
);
create table Store (
    sname       text,
    city        text,
    street      text,
    primary key (city,street)
);
create table Transaction (
    item        text references Item(iname),
    store       text references Store(sname),
    tdate       date,
    primary key (item,store,tdate)
);

Consider the following query (expressed as SQL and relational algebra):

select category,city
from   Item, Store, Transaction
where  iname=item and store=sname and
       tdate='20-12-2004' and city='Sydney';

JoinResult   = Item Join[iname=item] Transaction Join[store=sname] Store
SelectResult = Sel[tdate='20-12-2004' and city='Sydney'](JoinResult)
FinalResult  = Proj[category,city](SelectResult)

Show the three most promising relational algebra expressions that the query optimizer is likely to consider; then find the most efficient query plan and estimate its cost.

Assume 50 buffer pages and the following statistics and indices:

• Item: 50,000 tuples, 10 tuples/page.
  Indexing: hashed on iname (assume no overflows).
• Store: 1,000 tuples, 5 tuples/page; 100 cities.
  Index1: Unclustered hash index on sname. Index2: Clustered 2-level B+tree on city.
• Transaction: 500,000 tuples, 25 tuples/page; 10 items bought per store per day.
  The relation stores transactions committed over a 50 day period.
  Index: 2-level clustered B+tree on the pair of attributes store,ttime.