Re: Calculus versus algebra

In article <vaf4remcios.fsf_at_lucy.cs.uni-dortmund.de>, Kai Großjohann <Kai.Grossjohann_at_CS.Uni-Dortmund.DE> wrote:
>We have the Relational Calculus (tuple calculus and domain calculus?)
>and we have the Relational Algebra.
>
>I'm having a bit of trouble to generalize that to other cases. What's
>the underlying idea that distinguishes the calculus from the algebra?

The calculus is supposed to be more declarative (you state in terms of first-order logic what your query is) and the the algebra is more imperative (you state in which steps you want your query to be computed). This is not an absolute distinction, if you want to you can interpret the calculus as a way to compute the query and you can also read the algebra expression as a specification of your query, but there are some aspects here that make them each more suitable for their tasks. For example, for first-order logic we have a complete set of reasonig rules, and for algebra we have a nice set of rewrite rules that allows us to do query optimization and after that choose specific algorithms for joins et cetera. You could also do query optimization in the calculus but the most obvious interpretation of "joins" there would be nested loops which is not what you always want.

>But suppose that I have something which produces sequences instead of
>sets.

Yes, let's suppose we don't use the relational model and see if the relational operators are still useful. :-)

>Then the algebra approach is still easy: just have operations
>which take sequences as inputs and produce sequences as outputs. But
>for the calculus it's not so easy. For having a formula which
>determines whether it belongs to the result won't help. Instead, we
>might have a formula which computes the index in the result.

Actually it's exactly the other way around. If you look at research literature for functional programming languages (and also XML) and query/program optimization where lists are manipulated you will see that they rarely use the algebra approach and usually the calculus approach. If you want me to I can give you some pointers.

• Jan Hidders