Programming Research Group Research Report RR-01-18

Andrei Bulatov and Peter Jeavons

October 2001, 21pp.

Abstract

We describe a common framework for the Constraint Satisfaction Problem and the Conjunctive Query Evaluation Problem, encompassing a generalised form of these problems in which different variables may take values from different sets. The framework we develop allows us to specify natural subclasses of these two problems using algebraic techniques, and to establish when these subclasses are tractable. We show that a range of tractable classes can be obtained by combining recently identified tractable subclasses of the usual constraint satisfaction problem over a single set of values. We also systematically develop an algebraic structural theory for the general problem, which provides the prerequisites for further use of the powerful algebraic machinery.