Datalog and constraint satisfaction with infinite templates

On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study this connection for infinite structures. This has applications for constraint satisfaction with infinite templates. If the template Γ is ω-categorical, we present various equivalent characterizations of those Γ such that the constraint satisfaction problem (CSP) for Γ   can be solved by a Datalog program. We also show that CSP(Γ)CSP(Γ) can be solved in polynomial time for arbitrary ω-categorical structures Γ if the input is restricted to instances of bounded treewidth. Finally, we characterize those ω-categorical templates whose CSP has Datalog width 1, and those whose CSP has strict Datalog width k.

► We study the connection between Datalog and pebble games on infinite structures. ► The connection is extended as to include finite-variable logics and dualities. ► This is applied to constraint satisfaction problems with infinite templates.