Abstrakt
We show that every constraint satisfaction problem (CSP) over a fixed constraint language that has bounded relational width has also relational width (2,3). Together with known results this gives a trichotomy: a CSP has either relational width 1, or relational width (2,3) (and no smaller relational width), or does not have bounded relational width.
A consequence of this result is that if Gamma is a finite constraint language containing relations of arity at most k, then the CSP over Gamma either cannot be solved by a Datalog program, or can be solved by a Datalog program consisting of rules with at most max{3, k} variables and at most 2 variables in the head.