Re: Query independency from updates problem for relational databases

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 - 11:41:54 CST