Datalog vs First-Order Logic

Our main result is that every datalog query expressible in first-order logic is bounded; in terms of classical model theory this is a kind of compactness theorem for finite structures. In addition, we give some counter-examples delimiting the main result.

In the infinite case, that is if structures may be infinite, the main result is a simple consequence of the compactness theorem. The finite case much harder. It turned out, as Bruno Courcelle pointed out to us, that we reinvented the notion of finite width to establish the main result.

(Extended abstract in FOCS’89, 142-147.)