Calculate the cost of the three strategies cited in example $23.$I if the Staff relation has $15000$ tuples, Branch $750$ tuples, there are $750$ Managers $($one for each branch$),$ and there are $25$ London Branches.

EXAMPLE $23\mathrm{.}1$ Comparison of different processing strategies

Find all Managers who work at a London branch.

We can write this query in SQL as:

SELECT $*$

FROM Staff s$,$ Branch b

WHERE s$.$branchNo $=$ b$.$branchNo AND

$($s$.$position $=$ 'Manager' AND b$.$city $=$ 'London'$)$;

$2.$ Generate Relational Algebra Trees $($R$.$A$.$T$)$ as described in the Analysis Phase of Query Decomposition for Pblm$.23\mathrm{.}17($a$)-($c$),$ pg$.733.$

following queries are semantically correct:

$($a$)$ SELECT r$.$type, r$.$price

FROM Room $r,$ Hotel $h$

WHERE r$.$hotel$\_$number $=$ h$.$hotel$\_$number AND h$.$hotel$\_$name $=$ 'Grosvenor Hotel' AND r$.$type $>100$;

$($b$)$ SELECT g$.$guestNo,

g$.$name

FROM Hotel h$,$ Booking b$,$ Guest g

WHERE h$.$ hotelNo $=$ b$.$hotelNo AND h$.$ hotelName $=$ 'Grosvenor Hotel';

$($c$)$ SELECT r$.$roomNo, h$.$hotelNo

FROM Hotel $h,$ Booking b$,$ Room r

WHERE h$.$hoteINo $=$ b$.$hoteINo AND h$.$ hotelNo $=\text{'}H2I^{\text{'}}$ AND b$.$roomNo $=$ r$.$roomNo AND type $=\text{'}$ S $\text{'}$

AND b$.$hotelNo $=\text{'}$H$22\text{'}$;

Exercises

The following tables form part of a database held in a relational DBMS:

Hotel $($hotelNo$,$ hotelName, city$)$

Room $($roomNo$,$ hotelNo, type, price$)$

Booking $($hotelNo$,$ guestNo, dateFrom, dateTo, roomNo$)$

Guest $($guestNo$,$ guest Name, guestAddress$)$

where Hotel contains hotel details and hotelNo is the primary key;

Room contains room details for each hotel and $($room No$,$ hotelNo$)$ forms the primary key;

Booking contains details of bookings and $($hotelNo$,$ guestNo, dateFrom$)$ forms the primary key;

Guest contains guest details and guest No is the primary key.

$23\mathrm{.}2$ Query Decompo

Root

Intermediate operations

Leaves

Conjunctive normal form: A sequence of conjuncts that are connected with the ${?}^{{?}^{?}}$

$($AND$)$ operator. Each conjunct contains one or more terms connected by the $v$

$(OR)$ operator. For example:

$(position=$ 'Manager' $vv$ salary $>20000){?}^{(}(){)}^b$ranchNo $=\text{'}B003\text{'}$

A conjunctive selection contains only those tuples that satisfy all conjuncts.

Disjunctive normal form: A sequence of disjuncts that are connected with the $($ vvOR $)$

operator. Each disjunct contains one or more terms connected by the ${?}^{{?}^{?}}($AND$)$

operator. For example, we could rewrite the previous conjunctive normal form as:

$(position=$ 'Manager' ${?}^{(}(){)}^b$ranchNo $=\text{'}B003\text{'})vv($ salary $>{20000}^{{?}^{?}}$ branchNo $=\text{'}B003\text{'})$

A disjunctive selection contains those tuples formed by the union of all tuples that

satisfy the disjuncts.

$3.$The RAT solutions can be hand drawn with the images pasted into the Word document.