Hi everyone,

I need help with the question below.

Give the relation schema Baskets(BID, Item) where BID is the basket identifier, and assume:

(50 points)

1. The total number of distinct items is 10,000.
2. The total number of baskets is 1,000,000.
3. There are 20 items in each basket.
4. There are 20,000,000 tuples (records) in the relation table Baskets.

for the following query with the general query processing techniques in relational databases:

SELECTB1.Item, B2.Item, COUNT(B1.BID)

FROMBasketsB1,Baskets B2

WHEREB1.BID = B2.BID AND B1.Item < B2.Item

GROUP BY B1.Item,B2.Item

HAVINGCOUNT(B1.BID) >= s;

1.What is the time complexity of processing the query (or the cost in terms of big-O) if the Sort-Merge Join algorithm is used?

2.What is the total number of pairs, which will be generated from the query with the general query processing techniques such as Sort-Merge Join algorithm? How many tuples must be grouped and counted by the given SQL query?

3.If the value of s in the HAVING clause is 1,000, could you elaborate what the Apriori algorithm can help to improve processing of the given SQL query. (Please provide as much detail as possible).

See Jeffrey Ullman's notes (http://infolab.stanford.edu/~ullman/cs345-notes.html) for relevant material.

Thanks,

Alexander.