Re: How to implement query rewriting?

Kai Großjoha nn wrote:
> I have designed a query language and a logical algebra for it. I have
> a program which converts a query into the logical algebra. I'm in the
> process of defining the operators of the physical algebra.
>
> The question now is: how to transform the query from a logical algebra
> expression into a physical algebra expression?

The nice thing about the Prolog approach is that you have an explicit representation for the rules that determine how the logical algebra is translated to the physical algebra. The nice thing about this is that your program will be easy to extend if the physical algebra is extended or if you think of better rules.

But this doesn't necessarily mean that you have to implement Prolog. I think it is more efficient to think of a data structure to represent your rules in, and then write in Perl a function that has the logical algebra expression and the rules as its arguments, and the physical algebra expression as its result. I say this because I suspect that the rules are likely to be very simple and won't need the full power of Prolog such as back-tracking and the cut operator.

For starters you could simply translate every logical operator to one physical operator.

> PS: I know that query optimization is something I need to look at, but
> to keep it simple I'll be happy if I get any physical algebra
> expression at all, it need not be efficient.

In theory query optimization is often split in two steps: first you optimize the logical expression, and second you choose the physical expressions. Usually the second step doesn't involve a lot of rewriting. So I would first implement the second step. If that works then I would start thinking about doing optimization in the first step.

-- 
Kind regards,

    Jan Hidders