How to implement query rewriting?

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?

Clearly, this is a process driven by rules. So Prolog would be a natural language to express this. Alas, all of what I have so far is implemented in Perl, so it would be nice if I could do the query rewriting in Perl.

But it strikes me that writing a Prolog interpreter in Perl first might not be the right way to go.

Thoughts?

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.

kai

-- 
I like BOTH kinds of music.