Re: Query cost

In article <96157010-f9eb-414a-a3b7-2b86ef34573b_at_googlegroups.com>,  jemanuelcabral_at_gmail.com wrote:

> Hi.
>
> Let
> r,s be two relations
> rn – number of tuples of r
> sn – number of tuples of s
> rb – number of blocks of r
> sb – number of blocks of s
> R – attributes of r
> S – attributes of s
>
> Compute abstract r÷s I/O cost (forget CPU,comunications, buffers)
>
> Any ideas?

This sounds like homework. Or is it? :)
As others have already noted, the problem, as posed, is underspecified (which is fine if this is homework, because your teacher would formulate such problems within a context). Besides, it would be more accurate to talk about files, records and fields instead of relations, tuples and attributes, since this is a physical design problem.

> Divison is not a primitive operation; It is implemented using a equivalent RA
> expression
> ÉÆRÅ|S((ÉÆRÅ|S(r)Å~s)Å|ÉÆRÅ|S,S(r))

I don't understand your notation. In any case, I would rather think in terms of how *you* would design an algorithm for the division. Think about the meaning of the operation: to compute the result of R(X,Y) ÷ S(Y) you need to find all the tuples in R that share a common X-value and, for each such group, you must check that every tuple in S occurs as a Y-value of some tuple in that group. Does it sound similar to a join? Then, you may get inspired by the various join algorithms.

Hope this helps (if not, a book like Silberschatz et al.'s Database Systems Concepts will).

Nicola

• news://freenews.netfront.net/ - complaints: news_at_netfront.net ---