Datalog and Constraint Satisfaction with Infinite Templates

We relate the expressive power of Datalog and constraint satisfaction with infinite templates. The relationship is twofold: On the one hand, we prove that every non-empty problem that is closed under disjoint unions and has Datalog width one can be formulated as a constraint satisfaction problem (CSP) with a countable template that is

ω-categorical

. Structures with this property are of central interest in classical model theory. On the other hand, we identify classes of CSPs that can be solved in polynomial time with a Datalog program. For that, we generalise the notion of the

canonical Datalog program

of a CSP, which was previously defined only for CSPs with finite templates by Feder and Vardi. We show that if the template Γ is

ω

-categorical, then CSP(Γ) can be solved by an (

l

,

k

)-Datalog program if and only if the problem is solved by the canonical (

l

,

k

)-Datalog program for Γ. Finally, we prove algebraic characterisations for those

ω

-categorical templates whose CSP has Datalog width (1,

k

), and for those whose CSP has strict Datalog width

l

.

Topic:

Logic in Computer Science, Computational Complexity.