Re: deductive databases

alex goldman wrote:
> >>
> >> VC wrote:
> >>
> >>> -- that FOL can get rid of function symbols and be as expressive
as with
> >>> them;
> >>
> >> ?!?
> >>
> >>
> >> First-order logic without function symbols (F O) provided the
basis for
> >> query languages for the early commercial relational database
systems. Its
> >> appeal lies in its simplicity, clear semantics, and dual
declarative and
> >> procedural incarnations. Indeed, F O has a simple algebraization
which is
> >> particularly amenable to optimization. While F O has many
appealing
> >> features, it has limited expressive power. For instance, it cannot
> >> compute the transitive closure of a graph. [1]
> >>
> >> [1] Expressive Power of Query Languages, Serge Abiteboul & Victor
Vianu
> >>
> >>
>

http:www.informatik.uni-freiburg.de/~dbis/lehre/db-th-ws0001/papers/abi_vianu.ps
> >

FOL, with or without function symbols, cannot express transitive closure. The article talks about FOL recursive extentions, that's all.

E.g. non-recursive Datalog's expressive power is equivalent to that of FOL, but recursive Datalog is equivalent to, say, the negation and equality free existential fragment of least fixed-point logic (LFPL or FOL augmented with the least-point operator). Received on Wed May 18 2005 - 22:10:56 CEST