Consider the issue of interesting orders in optimization. Suppose you are given

a query that computes the natural join of a set of relations S$.$ Given a subset S$1$

of S$,$ what are the interesting orders of S$1?$

$(4)$

$($b$)$ Suppose you want to get answers to r $$ s sorted on an attribute of r$,$ and want

only the top K answers for some relatively small K$.$ Give a good way of

evaluating the query:

i When the join is on a foreign key of r referencing s$,$ where the foreign key

attribute is declared to be not null.

ii When the join is not on a foreign key.