To start with we give an abstract definition of a constraint language.
According to [Höhfeld and Smolka1988] a constraint 
is some piece
of syntax constraining the values of the variables occurring in it,
i.e., which denotes a set of assignments for these variables relative
to a given interpretation.
The following definitions are all made with respect to some given constraint language.
A constraint is satisfiable if there exists at least
one interpretation in which has a solution. A constraint
is valid in an interpretation 
if every -assignment is a solution of in , i.e., if
I = ASSI. An interpretation
satisfies a constraint if is valid in . An
interpretation is a model of a set 
of constraints if it
satisfies every constraint in .
The subsumption preordering on sets of constraints and the corresponding equivalence relation is defined as follows (following the notation of [Dörre1993]):
A variable renaming is a bijection VAR 
VAR that is the
identity except for finitely many exceptions. If 
is a renaming,
a constraint 
is called a -variant of a constraint
if
for every interpretation ( 
denotes the functional composition of both functions).
A constraint is called a
variant of a constraint if there exists a renaming
such that is a -variant of . Note that renaming is
homomorphic with respect to the subsumption relation, thus it does not
affect the subsumption ordering of constraints (see proposition 2.2 in
[Höhfeld and Smolka1988]).
A constraint language is closed under renaming if every constraint
has a -variant for every renaming . A constraint is
closed under intersection if for every two constraint and
there exists a constraint 
such that I 
'I = I for every interpretation .
A constraint language is decidable if the satisfiability of its constraints is decidable. In section 3.2.2 we present a decidable constraint language.
A constraint language is compact if for every set of constraints
holds: is satisfiable iff every finite subset of
is satisfiable.
Before we present in section 3.2.2 the constraint language to be used in this thesis we present the relational extension of constraint languages.
