Publication
FOCS 1989
Conference paper

Datalog vs. first-order logic

View publication

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.

Date

Publication

FOCS 1989

Authors

Share