Expressibility question

From: John Fiskio-Lasseter <johnfl_at_cs.uoregon.edu>
Date: Wed, 12 Jun 2002 18:16:51 -0700
Message-ID: <120620021816515948%johnfl_at_cs.uoregon.edu>

Hello, all. I hope one of you can help with a newbie question:

Basically, I'm curious as to what's known about the expressibility of relational algebra vs the expressibility of a language with fixpoint operators -- say, Datalog, the mu-calculus, or data flow equations.

From reading through Kanellakis' survey in _Handbook of Theoretcal Computer Science_ (my main exposure to DB theory so far), I understand that Codd's algebra/calculus can't express any form of recursion, including the transitive closure query.

Now suppose we extend RA with a transitive closure operator. How would you characterize the expressibility of this "RA+" in comparison with a language equipped with a fixpoint operator. Certainly intuition tells me that we still get more expressve power with the FP operator, but I'd like to understand why.

I'll be even more specific. I started thinking about this because I was trying to express the classical "bit vector" data flow equations in RA+ -- for example, reaching definitions

   RD[l] = U { (RD[k] \ Kill[l]) U Gen[l] | for all (k,l) in the CFG}

But I'm stymied on how to do this. I've got an intuition that it can't be done in RA+, and that this has something to do with conditional reachability, such as we have above in the interplay between the Gen and Kill sets (attributes, relations, whatever). Or perhaps it is only because of the way that the flow equation defines the RD relation incrementally -- i.e. one equation for each l in the "domain" position of the RD schema -- whilst RA+ works at the courser granularity of the whole relation.

Anyway, my main interst is not so much this little puzzle, but a general comparison of the expressive power of the two approaches. Like I said, I'm pretty much a rookie with the database literature, except for the five or six leads I followed from Kanellakis' tutorial, and a few chapters from Atzeni and de Antonellis' textbook.

I'd appreciate some insight from anyone who knows something about this problem. Pointers to the relevant literature would also be very nice, but I'd also take an outright solution to the problem above (or even an outline of how to do it -- I'm not proud :-)

Thanks,
-- John

---

John Fiskio-Lasseter                   CIS Dept., University of Oregon
  * Phd. Student, Graduate Teaching Fellow, and GTFF Steward
  * Deschutes 234              x6-1385           johnfl_at_cs.uoregon.edu


----------------------------------------------------------------------

  Wit, an' it be thy will, put me into good fooling. Those wits who   think they have thee do very oft prove fools, while I, who am sure   I lack thee, may yet pass for a wise man. For what says Quinapalus:   "Better a witty fool than a foolish wit".

                                               _Twelfth Night_


----------------------------------------------------------------------

Received on Thu Jun 13 2002 - 03:16:51 CEST