Datalog vs. first-order logic
Authors:
- Y. GurevichYGY. Gurevich
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 142-147
Abstract
The relation between the expressive power of datalog and that of first-order languages, is clarified. It is then proved that every first-order expressible datalog query is bounded. A form of compactness theorem for finite structure implied by this result is examined, and counterexamples to natural generalizations of the above result are given.Keywords
This publication has 4 references indexed in Scilit:
- On the first-order expressibility of recursive queries1989
- Toward logic tailored for computational complexity1984
- On Local and Non-Local Properties1982
- Monadic generalized spectraMathematical Logic Quarterly, 1975