Re: Expressibility question

In article <120620021816515948%johnfl_at_cs.uoregon.edu>, John Fiskio-Lasseter <johnfl_at_cs.uoregon.edu> wrote:
>
>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.

The expressive power is indeed greater. The relational algebra is essentially equivalent with FO (first order logic) and from finite model theory it is known that *on ordered domains*:

• FO(TC) captures NLOGSPACE
• FO(IFP) captures PTIME
• FO(PFP) captures PSPACE

where FO(TC) is the extension of FO with transitive closure, FO(IFP) the extension with inflationary fixpoint, and FO(PFP) the extension with partial fixpoints. For stratified datalog with negation it is know that it coincides with FO(IFP).

If you want to know more about this see: - "Finite Model Theory" by Heinz-Dieter Ebbinghaus and Joerg Flum, Second

   edition. (e.g. page 133 Ch. 7.3)
- "Foundations of Databases" by Serge Abiteboul, Richard Hull and Victor Vianu.

   (e.g. pages 479, 480 Ch. 18.3)

Both classics in finite model theory and database theory, respectively.

>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.

Since the equation is monotonic in the sense that if any RD[i] grows then all others must also grow or stay the same, you can express this with the help of an inflationary fixpoint. For the same reason you can also express this in stratified datalog with negation.

>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.

Actually, I think you can do this with transitive closure. We have the following predicates:

  Pred(x) all computed predicates/variables   CFG(k, l) the flow graph
  Kill(l, x) iff x in Kill[l]
  Gen(l, x) iff x in Gen[l]

we can now define in non-recursive datalog with negation (and therefore also in RA):

  RD1(k, x, l, x) <- CFG(k, l) and Pred(x) and not Kill(l, x).   RD1(k, x, l, y) <- CFG(k, l) and Pred(x) and Pred(y) and Gen(l, y).

As you can see it does more or less one iteration step; if x is in RD[k] then y is in RD[l]. Note that you will have to do something special for the root node, but you get the picture. Now all you have to do is take the transitive closure of this relation, join the first two columns with the RD for the root node and project on the last to columns.

Hope this helped,

• Jan Hidders