Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: Relational lattice completeness

Re: Relational lattice completeness

From: Marshall Spight <marshall.spight_at_gmail.com>
Date: 23 Apr 2006 11:23:42 -0700
Message-ID: <1145816621.974104.100360@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 - 13:23:42 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US