# Re: Query independency from updates problem for relational databases

Date: Fri, 14 Dec 2007 07:23:50 -0800 (PST)

Message-ID: <d45380dc-ee66-47a1-8adb-2f6623fcb651_at_s12g2000prg.googlegroups.com>

On Dec 13, 9:47 pm, Jan Hidders <hidd..._at_gmail.com> wrote:

> On 13 dec, 18:41, silent..._at_gmail.com wrote:

*>
**>
**>
**> > 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.
**>
**> > 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.
**>
**> The problem they discuss is the more simple case where you restrict
**> yourself to the algebra with only projection, selection and Cartesian
**> product. That class of queries is also known as the class of
**> conjunctive queries.
**>
**> Undecidability of the full algebra follows from undecidability of
**> first order logic under a finite model assumption (look for
**> Trakhtenbrot's theorem). The basic idea is that you can translate
**> every FOL formula to an algebra expression that returns always the
**> empty set iff the formula is satisfiable. You will probably understand
**> that if you cannot decide if an expression always returns an empty
**> set, then you also cannot decide the equivalence of two expressions.
**>
**> I could explain more if you want me to, but this should set you in the
**> right direction.
**>
**> -- Jan Hidders
*

Thanks a lot! That indeed makes sense. Since relational algebra is a sort of FOL, your reduction to Trakhtenbrot's theorem completely answers my question.

Sergei Received on Fri Dec 14 2007 - 16:23:50 CET