SQL optimization, execution trees, relational algebra.

Look at the query below that finds the products, stores in Montreal and their managers where products that have a buying price of over $500$ are sold at a price that is less then $10\%$ higher than the buying price.

SELECT P$.$pid, S$.$storeId, S$.$manager

FROM Products P$,$ Stores S$,$ StorePrices SP

WHERE P$.$pid $=$ SP$.$pid

AND S$.$storeId $=$ SP$.$storeId

AND P$.$buyingPrice $>500\mathrm{.}00$

AND SP$.$sellingPrice $$ P$.$buyingPrice $*1\mathrm{.}1$

Assume, $1\%$ of all products have a buying price of over $500$ and there are around $10\%$ that are sold for less than $10\%$ over the buying price.

A non$-$optimized relational expression for this query is

$\backslash$pi pid,storeId,manager$(\backslash$sigma buyingPrice $>$Products $P500$sellingPrice less than buyingPrice$1\mathrm{.}1(($Products$\backslash$times Stores$)$ StorePrices$))$

An execution tree after a purely algebraic optimization is attached.

$1.$ For each of the edges in the tree with labels $($A$)-($F$),$ indicate the number of tuples and the

size of each of these tuples that flow from the child operator to the parent operator. Keep in

mind that SQL$,$ unlike relational algebra, keeps the join attributes from both input relations

in the output.

$2.$ Find an execution tree where the intermediate results have less tuples than in the tree of

Question $1.$ Calculate the number of tuples and their sizes that flow from one operator to

the next.