Consider the following schema of a shoe store database:

Store(sid, location)

ShoeType(id, style, size, color)

Inventory(type, sid, quantity)

Table Store has the data of each shoe store in the database which contains a unique id and the location. The ShoeType table has the data of each possible type of shoe in the database. This table keeps a unique value as the id, the style, size and the color of the shoe. The Inventory table listed the number of shoe types in each store.

Inventory.type is a foreign key to ShoeType.id and Inventory.sid is a foreign key to Store.sid. We are given the following information about the database: Store contains 500 records with 10 records per page. ShoeType contains 1000 records with 40 records per page. Inventory contains 50,000 records with 50 records per page.

There are 100 values for Inventory.type.

There are 50 value for Store.location

There are 10 values for ShoeType.size (5,6,,14)

There are 1000 values for Inventory.quantity

Consider the following query:

SELECT S.sid, S.location, T.size

FROM Store S, ShoeType T, Inventory I

WHERE S.sid=I.sid AND I.type = T.id;

Draw all possible unique left-deep join query trees for the query.

From your previous answer, consider only those trees where the smallest relation is the left most relation. Now, for the first join in each such tree (i.e. the join at the bottom of the tree), what join algorithm would work best (i.e. cost the least)? Assume that you have 70 pages of buffer memory. There are no 3 indexes; so indexed nested loop is not an option. Consider the Page Oriented Nested Join (PNJ), Block-NJ, Sort-Merge-J, and Hash-J