# Re: Query independency from updates problem for relational databases

Date: Thu, 13 Dec 2007 09:41:54 -0800 (PST)

Message-ID: <e020326b-90f3-4019-9467-8511829ccda8_at_e25g2000prg.googlegroups.com>

On Dec 13, 12:28 am, Jan Hidders <hidd..._at_gmail.com> wrote:

> On 10 dec, 20:26, silent..._at_gmail.com wrote:

*>
**> > In paper "Independence of Logic Database Queries and Updates" by C.
**> > Elkan it is proven that for logical databases query independency from
**> > updates problem is undecidable. In some papers I've seen claims that
**> > this problem is also undecidable for relational databases (the papers
**> > are referring to the Elkan's paper). But, as far as I know, not every
**> > Datalog program can be expressed in terms of full relational algebra
**> > and vice versa.
**>
**> > So I'm wondering whether such statements are correct and whether this
**> > problem is indeed undecidable for relational databases?
**>
**> If you define relational database as database whose query language is
**> the usual relational algebra or something related then, yes, that is
**> correct. This follows fairly straightforward from the observation that
**> equivalence of two relational algebra expressions is undecidable.
**>
**> -- Jan Hidders
*

Do you know of any a reference where the undecidability of equivalence of two relational algebra expressions is discussed? The only thing I could find so far is "Equivalences among Relational Expressions" by A. V. Aho, Y. Sagiv, and J. D. Ullman where this problem is shown to be NP-complete.

Sergei Received on Thu Dec 13 2007 - 18:41:54 CET