Re: Expressibility question

In article <130620022205371942%johnfl_at_cs.uoregon.edu>, John Fiskio-Lasseter <johnfl_at_cs.uoregon.edu> wrote:
>[[ This message was both posted and mailed: see
> the "To," "Cc," and "Newsgroups" headers for details. ]]
>
>In article <3d08e78d$1_at_news.uia.ac.be>, Jan.Hidders
><hidders_at_hcoss.uia.ac.be> wrote:
>
>> Hope this helped,
>
>It did indeed. Thank you.

You are very welcome. It was nice to get away from all this OO vs. RM nonsense. Oops, I think I'd better duck now. :-)

>[...] I didn't realize how much work on descriptive complexity
>had been done wthin the DB community -- one of those disadvantages to
>being in a (relatively) small department that specalizes in only a few
>areas of research.

Don't worry. This also happens in big departments. Sometimes I even have the impression that it happens especially there. The fact that you dared to look a bit farther is a very good sign.

> [...] I thought I had an example of something
>common and useful that you can express with a FP operator but not with
>transitive closure alone. Oh well. Do you happen to know of a nice
>example of this off the top of your head?

No, unfortunately I don't, :-), and I'm sitting at home right now so I can't look it up. A quick look on-line taught me however that there is a proof by Phokion Kolaitis that showed that on unordered finite structures (aka. relational databases :-)) FO(PFP) has greater expressive power then FO(IFP) by showing that the first can define game trees (an often used technique in finite model theory, Abiteboul et al. explains some of it, Ebbinghaus et al. more, see Ehrenfaucht Fraisse games) and the second cannot. Since FO(TC) expresses a subset of FO(IFP) this also separates FO(TC) from FO(PFP). The reference is:

  KOLAITIS, P. 1991. The expressive power of stratified logic programs. Inf.   Comput. 90, 50 -- 66.

I wasn't able to find an on-line version, unfortunately. Whether there is a similar proof that shows that FO(IFP) is strictly stronger than FO(TC) I really don't know.

• Jan Hidders