Re: Relational lattice

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Fri, 11 Mar 2005 18:13:02 GMT
Message-ID: <OclYd.35394$Ai.3302500@phobos.telenet-ops.be>

Jan Hidders wrote:
> Vadim Tropashko wrote:

>>
>> Is it possible to express transitive closure in a finite set of
>> equations as well?

>
> Good question. Very good question. I suspect not, but I'm not sure and
> certainly have no proof. I do know that you can if you use the nested
> relational algebra.
>
> By the way, I just ran into a somewhat related paper. It's probably not
> exactly what you are looking for, but you might be interested in it:
>
> "Solving equations in the relational algebra"
>
> http://arxiv.org/abs/cs.LO/0106034

Well, I'll be ...! The answer to your question is actually in that reference. See Remark 7.3 on page 16. If you want to know more, the paper by Kolaitis they refer to is actually also on-line: See Phokion's home page:

   http://www.cse.ucsc.edu/~kolaitis/

• Jan Hidders

Received on Fri Mar 11 2005 - 12:13:02 CST