Re: Query independency from updates problem for relational databases

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