Re: Query independency from updates problem for relational databases

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