There are two relations, registered(participant,topic) and fee(participant,amount). The primary key for registered is (participant, topic) and the primary key for fee is participant.

The premise is that of an academic conference. The relation registered stores the names of the participants and the names of the topics registered by them. On the other hand, the fee relation stores the names of participants and the fees that they have paid for the topics.

Also the participants are segregated into five categories depending on the amount of fees they paid. The fees paid under each category are Rs 1000, 2000, 3000, 4000 and 5000. It may be safely assumed that each category has equal number of participants.

Now the query that we are interested in is :

List all topics registered by participants who have paid more than a given amount, x

The query is presented in the following two approaches:

Approach 1 :

   create table r1 as select * from fee where amount > x ;
   select distinct topic
   from registered as R, r1 as T
   where R.participant = T.participant ; 

Approach 2 :

   select distinct topic
   from registered as R, fee as T
   where R.participant=T.participant and amount > x ;

Henceforth, I have two questions that have arisen...

(i) Which if the approaches is faster for x = 3000 , and why ?

(ii) Which approach has less disk access time ?

It would be great if I could have some help on the above problem. I'll share my advances on the same :

Assuming there are m participants in each of the categories,the number of rows in relation fee would be 5m. In Approach 1, there's a query running throw these 5m entries to extract out those which have a fees amount value greater than x ( = 3000, here ). Now in this context, this would mean table r1 that Approach 1 creates would have 2m entries ( due to the fact that there are only two categories above 3000 viz 4000 and 5000 ). So finally when we select distinct topics from the subsequent query we make 2m * 5m ( for R.participant = T.participant ) = 10m + 5m = 15m comparisons to ascertain the fact in approach 1.

Whereas in Approach 2, we don't have any such table as r1 being created, and that makes the single select distinct topic query on registered and fee comparing participant names and a check for amount > x use 5m * 5m = 25m comparisons to retrieve the data we looking for in the query result.

So could this enable me to say that Approach (1) would work faster than Approach (2) for x=3000 in the given query ?

  • $\begingroup$ An SQL query describes a result, not an algorithm. This can't be answered until you tell us how to determine an algorithm from a query. You have done that yourself, but you don't explain. It's not clear exactly what all the givens are & what the assignment is. Including how you got 2 algorithms, what they are & what are the definitions & complexities for operators they refer to. $\endgroup$
    – philipxy
    Aug 24, 2021 at 1:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.