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?

Sergei

On 10 dec, 20:26, silent... (AT) gmail (DOT) com wrote:
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

On Dec 13, 12:28 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:
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

On 13 dec, 18:41, silent... (AT) gmail (DOT) com wrote:
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

On Dec 13, 9:47 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

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