Re: Proof that relational algebra is eqivalent to FOL

"Marshall Spight" <marshall.spight_at_gmail.com> wrote in message news:1121611436.233467.72510_at_g14g2000cwa.googlegroups.com...
> Hi,
>
> I have seen reference (here and elsewhere) to the "common knowledge"
> that the relational algebra is equivalent in power to the first
> order logic.
>
> I would like to understand this proof, but I can't find any
> references to it online. Does anyone have any references?
> Books are okay too. I'd really like to understand this issue,
> so if anyone has any recommendations for further study, I'd
> be interested to hear them.
>

Briefly, a relational calculus(TRC or DRC) language is a FOL dialect with minor syntactical differences and limitations (no functions, limited domain of interpretaion (just the database itself), etc). Codd showed that RC (limited to "safe" expressions) was equivalent to RA in "Relational completeness of database sublanguages", 1972. I think (although I did not check) Date's "Introduction to RDBMS" might contain the proof.

When one says that "relational algebra is equivalent in power to the first order logic", what one means, hopefully, is that the RA (or RC) *expressive power* is equivalent to that of the FOL (actually it. is less due to the limitations I mentioned).

vc

>
> Marshall
>
Received on Sun Jul 17 2005 - 18:11:33 CDT