Re: Relational lattice completeness
Date: 23 Apr 2006 11:23:42 -0700
Message-ID: <1145816621.974104.100360_at_e56g2000cwe.googlegroups.com>
Jan Hidders wrote:
> Mikito Harakiri wrote:
> >
> > AFIR you mentioned long time ago that there is some kind of
> > incompleteness result for RA. Do you have any reference? (Then it would
> > be clear for me what kind of completeness you have in mind.)
>
> I'm not sure I said that, but there is a strongly related result about
> the undecidability of equivalence of two relational algebra
> expressions. But I suspect that is not going to help you much.
I would like to second Mikito's request for a citation for this. For one thing, I now have this idea in my head that the equivalence of two RA expressions is undecidable, but no actual way to back that idea up. For another, it's a significant part of the motivation to work towards a proof that it *is* decidable for the Tropashko algebra.
Marshall Received on Sun Apr 23 2006 - 20:23:42 CEST