Re: Query independency from updates problem for relational databases

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