Datalog vs. first-order logic
Miklós Ajtai, Yuri G. Gurevich · 1989
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.>