From dechter@ruffles.ICS.UCI.EDU Wed May 22 09:42:14 1996
Received: by lanai.cs.ucla.edu (8.6.12/1.00) with ESMTP id JAA09256 for ; Wed, 22 May 1996 09:42:10 -0700
Received: from paris.ics.uci.edu by delphi.cs.ucla.edu (8.7.1/2.1) with SMTP id JAA06094 for ; Wed, 22 May 1996 09:42:06 -0700 (PDT)
Received: from ruffles.ics.uci.edu by paris.ics.uci.edu id aa25831;
22 May 96 8:49 PDT
to: kaoru@cs.ucla.edu
subject: paper.tex
Date: Wed, 22 May 1996 08:49:13 -0700
From: Rina Dechter
Message-ID: <9605220849.aa25831@paris.ics.uci.edu>
Status: RO
Kaoru,
Please keep the following tex file for me. ftp doesn't work from Irvine.
-----Thanks.
%
% Use:
% relationally m-consistent
% relational m-consistency
% strongly k-consistent
% strong k-consistency
% globally consistent
% global consistency
% locally consistent
% local consistency
%
%\documentstyle[12pt]{article}
\documentstyle{llncs}
\title{
Local and Global Relational Consistency}
\author{Rina Dechter\inst{1} and Peter van Beek\inst{2}}
\institute{
Department of Information and Computer Science \\
University of California, Irvine \\
Irvine, California, USA ~ 92717 \\
dechter@ics.uci.edu \
\and
%Peter van Beek \\
Department of Computing Science \\
University of Alberta \\
Edmonton, Alberta, Canada ~ T6G 2H1 \\
vanbeek@cs.ualberta.ca}
\date{}
\newcommand{\shrink}[1]{}
\setcounter{example}{0}
\pagestyle{plain}
\begin{document}
\input{psfig}
\maketitle
\begin{abstract}
Local consistency has proven to be an important concept in the
theory and practice of constraint networks. In this paper, we
present a new definition of local consistency, called
{\em relational consistency}. The new definition is
{\em relation-based}, in contrast with the previous definition of
local consistency, which we characterize as variable-based. We
show the conceptual power of the new definition by showing how it
unifies known elimination operators such as resolution in theorem
proving, joins in relational databases, and variable elimination
for solving linear inequalities. We also show the usefulness of
the new definition in characterizing relationships between
properties of constraint networks---domain size and
acyclicity---and the level of local consistency needed to ensure
global consistency. As well, algorithms for enforcing relational
consistency are introduced and analyzed.
\end{abstract}
\section{Introduction}\label{SECTION:Introduction}
Constraint networks are a simple representation and reasoning
framework. A problem is represented as a set of variables, a
domain of values for each variable, and a set of constraints
between the variables. A central reasoning task is then to find
an instantiation of the variables that satisfies the
constraints.
In general, what makes constraint networks hard to solve is that
they can contain many local inconsistencies. A local
inconsistency is a consistent instantiation of $k-1$ of the
variables that cannot be extended to a $k${\it th} variable and
so cannot be part of any global solution. If we are using a
backtracking search to find a solution, such an inconsistency can
lead to a dead end in the search. This insight has led to the
definition of conditions that characterize the level of local
consistency of a network \cite{Mackworth77,Montanari74}
and to the development of algorithms for enforcing local
consistency conditions by removing local inconsistencies (e.g.,
\cite{Cooper89,DePe88,Freuder78,Mackworth77,Montanari74}).
In this paper, we present a new definition of local consistency called
{\em relational consistency}, introduced recently \cite{vBDe94b}.
The virtue of the new definition of local consistency is that,
firstly, it allows expressing the relationships between the
properties of the constraints and local consistency in a way that
avoids an explicit reference to the arity of the constraints.
Secondly, it is operational, thus generalizing the concept of the
composition operation defined for binary constraints, and can be
incorporated naturally in algorithms for enforcing desired levels
of relational consistency. Thirdly, it unifies known operators
such as resolution in theorem proving, joins in relational
databases, and variable elimination for solving equations and
inequalities. In particular it allows the formulation of an
elimination algorithm that generalizes algorithms appearing in
each of these areas. Finally, it allows identifying those
formalisms for which consistency can be decided by enforcing a
bounded level of consistency, like propositional databases and
linear equalities and inequalities, from general databases
requiring higher levels of local consistency. We also show the
usefulness of the new definition in characterizing relationships
between properties of constraint networks---domain size and
acyclicity---and the level of local consistency needed to ensure
global consistency. As well, algorithms for enforcing relational
consistency are introduced and analyzed.
\shrink{
For space considerations almost all proofs are omitted.
}
\section{Definitions and Preliminaries}\label{SECTION:Background}
\begin{definition}[constraint network\footnote{Note that
all the defintions and algorithms are applicable to relations
without the finiteness assumption; a point we make explicit
in section 4.2}]
A {\em constraint network} ${\cal R}$ is
a set of $n$ variables $X = \{x_1, \ldots, x_n\}$,
a domain $D_{i}$ of possible values for each variable $x_i$, $1 \leq i \leq n$,
and
a set of $t$ relations $R_{S_1}$, \ldots, $R_{S_t}$,
where $S_i \subseteq X$, $1 \leq i \leq n$.
A {\em constraint} or relation $R_{S}$ over a set of variables
$S = \{x_{1}, \ldots, x_{r}\}$ is a subset of the
product of their domains
(i.e., $R_{S} \subseteq D_1 \times \cdots \times D_r$).
The set of subsets $\{ S_1, \ldots, S_t \}$ on which constraints
are specified is called the {\em scheme} of ${\cal R}$.
A {\em binary constraint network} is the special case where all
constraints are over pairs of variables.
\end{definition}
\begin{definition}[solution to a constraint network]
An {\em instantiation} of the variables in $X$, denoted $X_I$, is an $n$-tuple
($a_1, \ldots, a_n$),
representing an assignment of
$a_i \in D_i$ to $x_i$, $1 \leq i \leq n$.
A {\em consistent instantiation} of a network is an instantiation of
the variables such that the constraints between variables are satisfied.
A consistent instantiation is also called a {\em solution}.
\end{definition}
The order of the variables constrained by a relation is not important;
that is, we follow the set-of-mappings formulation of relations (see
\cite{Ullman88}).
The notion of a consistent instantiation of a subset of the
variables can be defined in several ways.
\shrink{
The difference in the definitions lies in how we treat the case
where only some of the variables over which a relation is defined
are instantiated.
}
We use the following definition: an instantiation is consistent if it
satisfies all of the constraints that have no uninstantiated variables.
\begin{definition}[consistent instantiation of subsets of variables]
Let $Y$ and $S$ be sets of variables, and
let $Y_I$ be an instantiation of the variables in $Y$.
We denote by $Y_I[S]$ the tuple consisting of only the
components of $Y_I$ that correspond to the variables in $S$.
An instantiation $Y_I$
is {\em consistent} relative to a network ${\cal R}$
iff for all $S_i$ in the scheme of ${\cal R}$
such that $S_i \subseteq Y$,
$Y_I[S_i] \in R_{S_i}$.
The set of all consistent instantiations of the
variables in $Y$ is denoted $\rho(Y)$.
\end{definition}
One can view $\rho(Y)$ as the set of all solutions of the
subnetwork defined by $Y$. We now introduce the needed
operations on constraints adopted from the relational calculus
(see \cite{Ullman88} for details).
%***
% Peter, I introduce also the definition of pair-wise
%consistency using semi-join, because for bounded
%relation it is known to be tractable and some networks
%can be solved by it. I did not make any use of it so far
%so we may eliminate this later. I do think it is useful.
%***
\begin{definition}[operations on constraints]
Let $R$ be a relation on a set $S$ of variables,
let $Y \subseteq S$ be a subset of the variables, and
let $Y_I$ be an instantiation of the variables in $Y$.
We denote by $\sigma_{Y_I}( R )$ the selection of those tuples in
$R$ that agree with $Y_I$.
We denote by $\Pi_Y ( R )$ the projection of the relation $R$ on
the subset $Y$; that is, a tuple over $Y$ appears in $\Pi_Y ( R )$
if and only if it can be extended to a full tuple in $R$.
Let $R_{S_1}$ be a relation on a set $S_1$ of variables and let
$R_{S_2}$ be a relation on a set $S_2$ of variables. We denote
by $R_{S_1} \Join R_{S_2}$ the natural join of the two relations.
%ppp I define the join again:
The join of
$R_{S_1}$ and $R_{S_2}$ is a relation defined over $S_1 \cup S_2$
containing all the tuples $t$, satisfying $t_{S_1} \in R_{S_1}$
and $t_{S_2} \in R_{S_2}$.
\shrink{
in the join satisfiesif it can
be constructed by the following steps: (i) take a tuple $r$ from
$R_{S_1}$, (ii) select a tuple $s$ from $R_{S_2}$ such that the
components of $r$ and $s$ agree on the variables that $R_{S_1}$
and $R_{S_2}$ have in common (that is, on the variables
$S_1 \cap S_2$), and (iii) form the tuple $t$ by combining the
components of $r$ and $s$, keeping only one copy of components that
correspond to variables that the original relations $R_{S_1}$ and
$R_{S_2}$ have in common. The resulting relation is on the set
of variables given by $S_1 \cup S_2$.
}
\shrink{
We denote by $R_{S_1}~semijoin~R_{S_2}$ the semi-join of the two
relations, defined by : $R_{S_1}~semijoin~R_{S_2} = R_{S_1}
\cap \Pi_{S_1} (R_{S_1} \Join R_{S_2})$.
}
\end{definition}
\shrink{
A binary relation $R_{ij}$ between variables $x_i$ and $x_j$ can
be represented as a (0,1)-matrix with $| D_i |$ rows and $| D_j |$
columns by imposing an ordering on the domains of the
variables. A zero entry at row $a$, column $b$ means that the
pair consisting of the $a$th element of $D_i$ and the $b$th
element of $D_j$ is not permitted; a one entry means that the
pair is permitted.
}
Two properties of constraint networks that arise later in the paper
are domain size and row convexity.
\begin{definition}[$k$-valued domains]
A network of constraints is $k$-valued if the domain sizes
of all variables are bounded by $k$.
\end{definition}
\begin{definition}[row convex constraints (\cite{vBDe94a})]
A binary constraint $R$ on a set \{$x_1, x_2$\} of variables
with associated domains $D_1$ and $D_2$, is {\em row convex} if
there exists an ordering of $D_2$ such that, for every $a_1 \in
D_1$, the set \{$x_2 \mid (a_1, x_2) \in R$\} can be ordered
such that the elements appear consecutively in the ordering of
$D_2$.
An $r$-ary relation $R$ on a set $S$ of variables \{$x_1, \ldots,
x_r$\} is {\em row convex} if for every subset of $r-2$ variables
$Y \subseteq S$ and for every instantiation $Y_I$ of the
variables in $Y$, the binary relation $\Pi_{(S-Y)}(\sigma_{Y_I} (
R ))$ is row convex.
A constraint network is row convex if all its constraints are row convex.
\end{definition}
\addtocounter{example}{1}
{\bf Example \theexample.}
We illustrate the definitions using the following network
${\cal R}$ over the set $X$ of variables \{$x_1, x_2, x_3, x_4$\}.
The network is 3-valued.
The domains of the variables are $D_i$ $=$ \{a,b,c\}, $1 \leq i \leq 4$,
and the relations are given by,
\begin{tabbing}
xxx\=xxxl\=xx\=\{\=(b,b,b), \=(b,b,b), \=(b,b,b), \=(b,b,b), \=\kill
\> $R_{S_1}$ \> $=$ \> \{
\> (a,a,a), \> (a,a,c), \> (a,b,c), \> (a,c,b), \> (b,a,c), \\
\>\>\>\> (b,b,b), \> (b,c,a), \> (c,a,b), \> (c,b,a), \> (c,c,c)\},\\
\> $R_{S_2}$ \> $=$ \> \{
\> (a,b), (b,a), (b,c), (c,a), (c,c)\},\\
\> $R_{S_3}$ \> $=$ \> \{
\> (a,b), (a,c), (b,b), (c,a), (c,b)\},
\end{tabbing}
where $S_1$ = \{$x_1, x_2, x_3$\},
$S_2$ = \{$x_2, x_4$\}, and
$S_3$ = \{$x_3, x_4$\}.
%ppp
The projection of $R_{S_1}$ over $\{x_1, x_3\}$,
$\Pi_{\{x_1,x_3\}} = \{(a,a),(a,c),(a,b),(b,c),(b,b),(b,a),(c,b),(c,a),(c,c)\}$.
The join of $R_{S_2}$ and $R_{S_3}$ is given by:
$R_Y = R_{S_2} \Join R_{S_3} = \{(a,a,a),(a,b,b),(a,c,b),$$(b,c,a),(b,a,c),(c,c,a),(c,a,c)\}$, where $Y =\{x_2,x_3,x_4\}$.
The set of all solutions of the network is given by,
\begin{tabbing}
xxx\=lxxxx\=xx\=\{\=(b,b,b,b), \=(b,b,b,b), \=(b,b,b,b), \=(b,b,b,b), \=\kill
\> $\rho(X)$ \> = \> \{
\> (a,a,a,b), \> (a,a,c,b), \> (a,b,c,a), \> (b,a,c,b), \\
\>\>\>\> (b,c,a,c), \> (c,a,b,b), \> (c,b,a,c), \> (c,c,c,a)\}.
\end{tabbing}
Let $Y$ $=$ \{$x_2, x_3, x_4$\} be a subset of the variables and let
$Y_I$ be an instantiation of the variables in $Y$.
The tuple $Y_I$ $=$ (a,c,b) is consistent relative to ${\cal R}$ since
$Y_I[S_2]$ $=$ (a,b) and (a,b) $\in$ $R_{S_2}$, and
$Y_I[S_3]$ $=$ (c,b) and (c,b) $\in$ $R_{S_3}$.
The tuple $Y_I$ $=$ (c,a,b) is not consistent relative to ${\cal R}$ since
$Y_I[S_2]$ $=$ (c,b), and (c,b) $\not\in$ $R_{S_2}$.
The set of all consistent instantiations of the
variables in $Y$ is given by,
\begin{tabbing}
xxx\=lxxxx\=xx\=\kill
\> $\rho(Y)$ $=$
\{(a,a,b), (a,b,b), (a,c,b), (b,a,c), (b,c,a), (c,a,c), (c,c,a)\}.
\end{tabbing}
\section{Local Consistency}\label{SECTION:Local-Consistency}
Local consistency has proven to be an important concept in the
theory and practice of constraint networks. In this section we
first review previous definitions of local consistency, which we
characterize as variable-based. We then present new definitions
of local consistency that are {\em relation-based} and present
algorithms for enforcing these local consistencies.
%%% DELETED HERE %%%
\subsection{Variable-based consistency}
Mackworth \cite{Mackworth77} defines three properties
of networks that characterize local consistency of networks:
{\it node}, {\it arc}, and {\it path} {\it consistency}.
Freuder \cite{Freuder78} generalizes this to $k$-consistency.
\begin{definition}[$k$-consistency; Freuder \cite{Freuder78,Freuder82}]
A network is {\em $k$-consistent} if and only if given any
instantiation of any $k-1$ distinct variables satisfying all of
the direct relations among those variables, there exists an
instantiation of any $k$th variable such that the $k$ values
taken together satisfy all of the relations among the $k$
variables. A network is {\em strongly $k$-consistent} if and
only if it is $j$-consistent for all $j \leq k$.
\end{definition}
\shrink{
Note that the definition of path consistency subsumes arc
consistency if in the above definition we do not assume that
variables $x_i$ and $x_j$ are distinct. For simplicity, we will
assume that path consistency includes arc consistency.
}
Node, arc, and path consistency correspond to one-, two-, and
three-consistency, respectively. A strongly $n$-consistent
network is called {\em globally consistent}. Globally consistent
networks have the property that any consistent instantiation of a
subset of the variables can be extended to a consistent
instantiation of all of the variables without backtracking
\cite{Dechter92}. It is frequently enough to have a globally
consistent network along a single ordering of the variables as
long as this ordering is known in advance.
\begin{definition}[globally solved]
We say that a problem is globally solved if it is consistent,
and if there is a known ordering of the variables along which
solutions can be assembled without encountering deadends. An
algorithm {\em globally solves} a problem if it generates
a globally solved network.
\end{definition}
A globally solved representation is a useful representation of
all solutions whenever such a representation is more compact than
the set of all solutions.
\subsection{Relation-based consistency}
In \cite{vBDe94a}, we extended the notions of arc and path
consistency to non-binary relations, and used it to specify an
alternative condition under which row-convex non-binary networks
are globally consistent. The new local consistency conditions
were called relational arc- and path-consistency.
In \cite{vBDe94b} we
generalized relational arc- and path-consistency to
{\em relational $m$-consistency}.
In the definition of {\em relational-consistency}, the
relations rather than the variables are the primitive entities.
This allows expressing
the relationships between properties of the constraints
and local consistency in a way that avoids an explicit reference
to the arity of the constraints.
In this section we revisit the definition of relational
consistency and augment it with the option of having also an
explicit reference to a constraint's arity, to allow polynomial
algorithms for enforcing those conditions.
\begin{definition}[relational arc, and path-consistency]
Let ${\cal R}$ be a constraint network over a set of variables
$X$, and let $R_S$ and $R_T$ be two
relations in ${\cal R}$,
where $S,T \subseteq X$.
We say that $R_S$ is
{\em relationally arc-consistent} relative to a subset
of variables $A \subseteq S$
iff any consistent instantiation of the
variables in $A$ has an extension
to a full tuple in $R_S$; that is, iff
\begin{displaymath}
\rho(A) \subseteq \Pi_{A}( R_S ).
\end{displaymath}
(Recall that $\rho(A)$ is the set of all consistent instantiations
of the variables in $A$.)
A relation $R_S$ is
{\em relationally arc-consistent} if it is relationally
arc-consistent relative to every subset $A \subseteq S$.
A network is relationally arc-consistent iff every
relation is relationally arc-consistent.
%#####
% Peter, Here I also add the notion of pair-wise consistency
% which is identical to arc-consistency in the dual graph, and is less
% then path-consistency. Its value is that enforcing it will not change
% the scheme. It is enforceable by closing under semi-join.
% I am not sure yet to what extent we will use it, but I feel
% that is is an important concept since it can be enforced
% in polynomial time, as is known in relational databases.
\shrink{
We say that $R_S$ is {\em pair-wise consistent relative to} $R_T$
iff any consistent instantiation of the
variables in $S$, has an extension in a tuple of $R_T$.
Namely, iff
\begin{displaymath}
\rho(S) \subseteq \Pi_S R_T.
\end{displaymath}
A network is pair-wise consistent iff every pair of relations is
pair-wise consistent.
}
We say that $R_S$ and $R_T$ are
{\em relationally path-consistent} relative to a subset of variables
$A \subseteq S \cup T$ iff any consistent instantiation of the
variables in $A$ has an extension
to the variables in $S \cup T$
that satisfies $R_S$ and $R_T$ simultaneously; that is, iff
\begin{displaymath}
\rho(A) \subseteq \Pi_A ( R_S \Join R_T ),
\end{displaymath}
%where $A = ( S \cup T ) -\{x\}$.
A pair of relations $R_S$ and $R_T$ is
{\em relationally path-consistent}
iff it is relationally path-consistent relative
to every subset $A \subseteq S \cup T$.
A network is relationally path-consistent iff every
pair of relations is relationally path-consistent.
\end{definition}
\shrink{
Note that the definition of relational path-consistency subsumes
relational arc-consistency if in the above definition we do not
assume distinct pairs of relations. For simplicity, we will
assume that relational path-consistency includes relational
arc-consistency.
}
\begin{definition}[relational $m$-consistency]
Let ${\cal R}$ be a constraint network over a set of variables
$X$, and let $R_{S_1}, \ldots , R_{S_m}$ be $m$
distinct relations in ${\cal R}$,
where $S_i \subseteq X$.
We say that $R_{S_1}, \ldots , R_{S_m}$ are
{\em relationally $m$-consistent relative to a subset}
$A \subseteq \bigcup_{i=1}^m S_i$
iff any consistent instantiation of the
variables in $A$,
has an extension to $\bigcup_{i=1}^m S_i$
that satisfies $R_{S_1}, \ldots , R_{S_m}$ simultaneously;
that is, if and only if
\begin{displaymath}
\rho(A) \subseteq \Pi_A ( \Join_{i=1}^m R_{S_i} ) .
\end{displaymath}
A set of relations \{$R_{S_1}, \ldots , R_{S_m}$\} is
{\em relationally $m$-consistent}
iff it is relationally $m$-consistent relative to every
$A \subseteq \bigcup_{i=1}^m S_i$.
A network is
relationally $m$-consistent iff every set of $m$ relations is
relationally $m$-consistent.
\end{definition}
Note that if a network is relationally $m$-consistent then it is also
relationally $m^\prime$-consistent for every $m^\prime \leq m$.
Relational arc- and path-consistency correspond to
relational $1$- and $2$-consistency, respectively.
We next refine the definition of relational consistency to be restricted
to subsets of bounded size. This restriction is similar
to the original restriction used for variable-based
local consistency. In {\em relational $(i,m)$-consistency}
defined below, $m$ always indexes the cardinality of a set
of relations and
$i$ corresponds to the constraint's arity tested
for local consistency. When $i$ equals the number of variables, $n$,
relational $(i,m)$-consistency
is identical to relational $m$-consistency.
\begin{definition}[relational $(i,m)$-consistency]
A set of relations \{$R_{S_1}, \ldots , R_{S_m}$\} is
{\em relationally $(i,m)$-consistent}
iff it is relationally $m$-consistent relative to every subset $A$
{\em of size $i$},
$A \subseteq \bigcup_{i=1}^m S_i$.
A network is
relationally $(i,m)$-consistent iff every set of $m$ relations is
relationally $(i,m)$-consistent.
\end{definition}
Note that if ${\cal R}$ is relationally $(i,m)$-consistent and if
${\cal R}^\prime$ is generated by augmenting ${\cal R}$ with all
the projections of every relation on all its variable subsets,
% =======
% Old:
% then ${\cal R}^\prime$ is $(i^\prime , m)$-relational consistent
% relative to $i^\prime \leq i$.
% New:
then ${\cal R}^\prime$ is relationally $(j, m)$-consistent
for every $j \leq i$.
The relational based definition of arc-consistency given in
\cite{Mackworth77b} is identical to relational
(1,1)-consistency.
\begin{definition}[directional relational consistency]
Given an ordering of the variables, $o = x_1, \ldots,x_n$, a network
is $m$-{\em directionally relationally consistent} iff
for every $l$, every subset
of relations \{$R_{S_1}, \ldots , R_{S_m}$\} whose
largest index variable is $x_l$, is relationally $m$-consistent
relative to every subset
$A \subseteq \{ x_1 , \ldots, x_{l-1}\}$.
Directional relational $(i,m)$-consistency is defined
accordingly, by restricting the cardinality of $A$ to $i$.
\end{definition}
\addtocounter{example}{1}
{\bf Example \theexample.}
Consider the constraint network over the set of variables
\{$x_1$, $x_2$, $x_3$, $x_4$, $x_5$\}, where the domains of the
variables are all
$D_i$ $=$ \{a,b,c\}, $1 \leq i \leq 4$, and the relations are given by,
\begin{tabbing}
xxx\=xxxxxxl\=xx\=\kill
\> $R_{2,3,4,5}$ \> $=$ \> \{ (a,a,a,a), (b,a,a,a),
(a,b,a,a), (a,a,b,a), (a,a,a,b) \}, \\
\> $R_{1,2,5}$ \> $=$ \> \{ (b,a,b), (c,b,c), (b,a,c) \}.
\end{tabbing}
The constraints are not relationally arc-consistent.
For example, the instantiation
$x_2 = a$,
$x_3 = b$,
$x_4 = b$ is a
consistent instantiation as it satisfies all the applicable
constraints (trivially so, as there are no constraints defined
strictly over \{$x_2, x_3, x_4$\} or over any subset), but it does not
have an extension to $x_5$ that satisfies $R_{2,3,4,5}$.
%
% =======
% Old:
% It is not even 1-arc-consistent since the value $x_2 = b$ is
% New:
It is not even (1, 1)-consistent since the value $x_2 = b$ is
consistent, but is not consistent relative to $R_{2,3,4,5}$.
Similarly, the constraints are not relationally path-consistent.
For example, the instantiation
$x_1 = c$,
$x_2 = b$,
$x_3 = a$,
$x_4 = a$ is a
consistent instantiation (again, trivially so), but it does not
have an extension to $x_5$ that satisfies $R_{2,3,4,5}$ and $R_{1,2,5}$
simultaneously.
If we add the constraints
$R_{2}$ $=$ $R_{3}$ $=$ $R_{4}$ $=$ \{a\} and
$R_{1}$ $=$ $R_{5}$ $=$ \{b\} (namely, if we enforce (1,2)-consistency)
the set of solutions of the network does not change, and it can
be verified that the network is both relationally arc-
and path-consistent.
%ppp
Verification is easy since
all the variables' domains have a single value
and therefore the set of solutions over every subset of variables will
contains a single tuple only; the one that is extended to a
full solution.
%ppp
\vspace{6pt}
%333 Peter should we make it formal? lemma?
By definition, relational $k$-consistency implies
relational $(i,k)$-consistency for $i \leq k-1$,
which, for binary constraints, implies strong
variable-based $k$-consistency.
% otherwise the conditions are different.
\shrink{
In general, the definition of relational
$m$-consistency is similar but not identical to that of
variable-based $m$-consistency over the dual representation of
the problem in which the constraints are the variables, their
allowed tuples are their respective domains and two such
constraint-variables are constrained if they have variables in
common.
An explicit generalization of local consistency using the
notion of the dual graph and its use for generalizing
topological properties of constraint networks is given in
\cite{Jegou93b}.
}
%#####
% I changed this comparision to Jegou as he too uses rel. db. notation
% and I think that ``simpler'' is hard to argue---it is not clear
% that ours is simpler than his.
%#####
The virtue in the relational definition
(relative to the one based on the dual graph \cite{Jegou93b}),
is that it is easy to work with;
% in addition to being simple to work
% with for non-binary constraints, and in addition to be
% using known notations from the relational database model,
it can be incorporated naturally into algorithms for enforcing desired
levels of relational consistency,
it allows a simple generalization of local consistency relationships, and
it generalizes several operators of variable elimination.
Verifying relational $(i,m)$-consistency is $O(exp( i \cdot m ))$.
In general, however, we will not be
interested in verifying relational consistency,
but rather in the more demanding operation
of {\em enforcing} that condition.
\shrink{
In general
relational arc-consistency is verifiable in
$O(e n d^r)$, where $e$ is the number of constraints, $n$ is
the number of variables, $d$ is the size of the domains, and $r$
is the arity of the constraints.
Oddly, while verifying pair-wise is always polynomial
\cite{Maier83}, verifying this condition may be exponential
if the constraint arity is not bounded.
}
Below we present
algorithm {\sc Relational-Consistency} or $RC_{(i,m)}$,
a brute-force algorithm for enforcing
relational $(i,m)$-consistency on a network ${\cal R}$. Note that $R_A$ stands
for the current unique constraint specified over a subset of
variables $A$. If no constraint exists, then $R_A$ is the
universal relation over $A$.
%$A_i$ stands for a subset of variables of size $i$.
Algorithm $RC_m$ is the unbounded version of algorithm $RC_{(i,m)}$
in which the recorded constraints arity is not restricted.
\begin{tabbing}
xxx\=lxxx\=lxxx\=lxxx\=lxxx\=\kill
{\sc Relational-Consistency}(${\cal R},i, m$)$(RC_{(i,m)})$\\[3pt]
1. \> {\bf repeat} \\[3pt]
2. \>\> $Q \leftarrow {\cal R}$ \\[3pt]
3. \>\> {\bf for} every $m$ relations
$R_{S_1}, \ldots , R_{S_{m}} \in Q$ \\[2pt]
4. \>\> and every subset $A_i$ of size $i$,
$A_i \subseteq \bigcup_{j=1}^{m} S_j$ {\bf do} \\[4pt]
5. \>\>\> $R_{A_i} \leftarrow
R_{A_i} \cap ~ \Pi_{A_i} (\Join_{j=1}^{m} R_{S_j})$\\[3pt]
6. \>\>\> {\bf if} $R_{A_i}$ is the empty relation\\
7. \>\>\>\> {\bf then} exit and return the empty network\\
8. \> {\bf until} $Q = {\cal R}$
\end{tabbing}
\shrink{
The algorithm takes any $m$ relations that may or may not be
relationally $m$-consistent and enforces relational $m$-consistency
by tightening the relation among the appropriate subsets of
variables.
}
We call the operation in Step 5 {\em extended composition}, since
it generalizes the composition operation defined on binary relations.
\begin{definition}[(extended composition)]
The extended composition of relation $R_{S_1}$, \ldots, $R_{S_m}$
relative to a subset of variables $A \subseteq \bigcup_{i=1}^m S_i$,
denoted $EC_A ( R_{S_1}, \ldots, R_{S_m})$ is defined by:
\[
EC_A ( R_{S_1}, \ldots, R_{S_m})= \Pi_A \Join_{i=1}^m R_{S_i}
\]
When the operator is applied to $m$ relations, it is called
extended $m$-composition. If the projection operation restricted
to a set of size $i$ it is called extended $(i,m)$-composition.
\end{definition}
Algorithm $RC_{(i,m)}$ computes the closure of
${\cal R}$ with respect to extended $(i,m)$-composition.
Its complexity is $O(exp(i \cdot m))$ which is
clearly computationally expensive for large $i$ and $m$
though it can be improved in a
manner parallel to the improvements of path-consistency
algorithms \cite{MaFr85}. %Such improvements are not of much
%interest since enforcing relational
%consistency is likely to remain exponential for $m \ge 3$, unless
%Notice that enforcing relational $m$=consistency is likely to
%be exponential for $m \ge 3$.% unless
%the constraints are binary.
%We will see that even for $m = 3$, $RC_3$
%solves the NP-complete problem of propositional satisfiability.
%For the special case of pair-wise consistency it is known to
%be polynomial \cite{Maier83}.
%A more direct argument suggesting an increase in time and space
%complexity is the fact that the algorithm may need to record
%relations of arbitrary arity.
As with variable-based
local-consistency, we can improve the efficiency of enforcing
relational consistency by enforcing it only along a certain
direction. Below we present two versions of algorithm
{\sc Directional-Relational-Consistency}, $DRC_{(i,m)}$, ($DRC_m$,
respectively) which enforces
directional relational $(i,m)$-consistency ($m$-consistency, respectively)
on a network ${\cal R}$,
relative to a
given ordering $o=x_1, x_2, \ldots, x_n$. We
call the network generated by the algorithm the {\em (i,m)-directional
extension} ({\em $m$-directional extension}, respectively)
of ${\cal R}$, denoted $E_{(i,m)} (R)$ ($E_m(R)$, respectively).
Given an ordering of the variables,
the algorithm partition the relations into
buckets. In the bucket of $x_j$ it places all the relations whose largest
indexed variable is $x_j$. Buckets are subsequently
processed in descending order, and each is closed under the
extended $(i,m)$-composition relative to subsets that exclude
the bucket's variable.
The resulting relations are placed in lower buckets.
Since the operation of extended composition
computes constraints that eliminate certain variables
it is often called an {\em elimination operator}.
%ppp
Indeed, as we discuss later, the algorithm belongs to the class
of variable elimination algorithms.
%ppp
In addition to the main operation of extended composition we
propose two optional steps of {\em simplification} and {\em
instantiation}. These steps are targeted to provide a more
efficient implementation and allow the identification of some
tractable classes. The simplification step ensures that each
bucket contains relations defined on distinct subsets of
variables that are not included in each other. The instantiation
step exploits the property that whenever one of the relations in
the bucket is a singleton tuple we need not perform the full
extended $m$-composition. Instead we can restrict each relation
to those tuples that are consistent with the singleton tuple
%ppp
and move each resulting restriction to its appropriate buckets.
%ppp
This is equivalent to applying extended 2-composition between
each relation and the singleton relation. As we will see, this
step generalizes unit resolution.
%ppp
The special case-handling for instantiation exploits the
computational effect of {\em conditioning} as described
in \cite{Dechter90,bucket96}.
\begin{tabbing}
xxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=\kill
{\sc Directional-Relational-Consistency}(${\cal R},i, m, o$) ($DRC_{(i,m)}$)\\[3pt]
1. \> \parbox[t]{4.60in}{
Initialize: generate an ordered partition of the constraints,
$bucket_1$, \ldots, $bucket_n$, where $bucket_i$
contains all constraints whose highest variable is $x_i$.
}\\[2pt]
2. \> {\bf for} $p \leftarrow n$ {\bf downto} $1$ {\bf do}\\[2pt]
3. \>\> simplification step:\\
\>\> {\bf for} every $S_i, S_j \in bucket_p$,
such that $S_i \supseteq S_j$ {\bf do}\\[2pt]
\>\>\> $R_{S_i} \leftarrow
\Pi_{S_i}(R_{S_i} \Join R_{S_j})$\\[2pt]
4. \>\> instantiation step:\\
\>\> {\bf if} $bucket_p$ contains the constraint $x_p = u$ {\bf then}\\[2pt]
\>\>\> {\bf for} every $S_i \in bucket_p$ {\bf do}\\[2pt]
\>\>\>\> $A \leftarrow S_i -\{x_p\}$\\[2pt]
\>\>\>\> $R_A \leftarrow \Pi_A (\sigma_{x_p =u} R_{S_i})$\\[2pt]
\>\>\>\>\> {\bf if} $R_A$ is not the empty relation {\bf then}\\
\>\>\>\>\>\> add $R_A$ to its appropriate bucket\\
5. \>\> {\bf else}
\> $j \leftarrow \min$\{cardinality of bucket$_p$, $m$\}\\[2pt]
6. \>\>\> {\bf for} every $j$ relations
$R_{S_1}, \ldots, R_{S_j}$ in $bucket_p$ {\bf do}\\[2pt]
\>\>\>\> $F_j \leftarrow ~ \Join_{t=1}^j R_{S_t}$\\[2pt]
7. \>\>\>\> {\bf for} every subset of size $i$,
$A \subseteq \bigcup_{t=1}^j S_t - \{x_p\}$ {\bf do}\\[2pt]
% I am changing step 8 to not include the intersection since
% this will be done via the simplification step.
%8. \>\>\>\>\> $R_A \leftarrow R_A \cap ~ \Pi_A F_j$\\[2pt]
8. \>\>\>\>\> $R_A \leftarrow ~ \Pi_A F_j$\footnote{If more
than one relation is recorded on the same subset of variables, a subsequent simpification step will combine all such relations into one.}\\[2pt]
9. \>\>\>\>\> {\bf if} $R_A$ is not the empty relation {\bf then}\\
10. \>\>\>\>\>\> add $R_A$ to its appropriate bucket\\
11. \>\>\>\>\> {\bf else} \> exit and return the empty network\\
12. \> {\bf return} $E_{(i,m)}(R) = \bigcup_{j=1}^n bucket_j$
\end{tabbing}
Algorithm $DRC_m$ is identical to $DRC_{(i,m)}$ except that the
constraints recorded contain {\em all} the variables in the
bucket excluding $x_p$; that is, step 7 is modified to:\\[2pt]
7a. ~~ {\bf for} $A \leftarrow \bigcup_{t=1}^j S_t - \{x_p\}$ {\bf do}
\shrink{
Although algorithm $DRC_(i,m)$ enforces extended
$(i,m)$-composition only, it
generates a {\em strong} directionally relationally $m$-consistent
network in the following sense.
\begin{theorem}
The closure under $DRC_(i,m)$
along ordering $o= x_1 , \ldots, x_n$, is a network
such that all the relations in the same bucket are
strong directionally relationally $m$-consistent.
\end{theorem}
\noindent
{\bf Proof (sketch).}
It is clear that all the relations in the same bucket
are directional
relational $m$-consistent (abbreviated $drc_m$) since we enforce
this level of consistency. What we have to
show is that the relations in each bucket are
also $drc_k$ for every $k < m-1$.
Let us pick the bucket of $x_i$, let $R_{S_1}, \ldots, R_{S_j}$,
be the relations in this bucket, and let
$R_{S_1}, \ldots, R_{S_k}$ be a subset of $k$ relations,
$k < m \leq j$.
Let us take any subset of relations $R_{S_1 } , \ldots, R_{S_{m-1}}$
that contains these $k$ relations and
let $A_m = S_1 \cup \cdots \cup S_{m-1} - \{x_i \}$.
The algorithm generates by extended $(m-1)$-composition on the
bucket of $x_i$, the relation
\[
\rho_m = \Pi_{A_m }( \Join_{1 \leq r \leq m-1} S_r )
\]
which, when projected on the subset $A_k$ is at least
as tight as the relation generated by
extended $k$-composition.
Namely, $\Pi_{A_k} \rho_m \subseteq \rho_k$.
Consequently we are guaranteed that all the relations
in that bucket satisfy $drc_k$.
$\Box$
Lemma: Suppose we have a network processed by relational
directional path-consistency along ordering $d = X_1 , \ldots, X_n$.
Then for any $i$,
If $R_1$ is in bucket $X_i$, and if it is defined
on variable $X_j$, j smaller than i,
then the bucket of $X_j$ must contain a relation $R_2$ such that
$R_2$ is defined over a superset of $A$, $A$ being
the variables of $R_1$
that are also a subset of the first $j$ variables.
and also $\Pi_A R_2 \subseteq \pi_A R_1$.
(if $R_1$ is defined over $S_1$, then
$A= (S_1 - X_i) intersect \{X_1 , \ldots, X_j \}$) and
I think it is clear that the lemma completes the
proof of the theorem.
Proof of lemma:
We prove by induction on $i$.
For $i=1$ this is trivial
The induction hypothesis: for $i-1$ is that
for any relation $R_1$ in the bucket of $X_{i-1}$,
and for every $X_j$ (j not equal i-1),
on which $R_1$ is defined,
there exists a relation, $R_2$,
in the bucket of $X_j$ that "represents it" namely it is
defined on a superset of
$A= S_1 - X_{i-1} \cap \{X_1 , \ldots, X_j \}$ and
and it is tighter
then $R_1$ relative to $A$.
We now have to prove this for $i$. Let $R_1$ be a relation in
the $ith$ bucket, and let $j$ be a variable on which $R_1$ is defined,
different than $X_i$.
case 1: if the $ith$ bucket contains only $R_1$, the algorithm
project out $X_i$ and put the resulting
relation, let us call it R, in its appropriate bucket.
This bucket is equal or higher to $j$ but smaller than $i$.
Let us call that index $k$. If $k=j$ we are done, since $R$ is
the $R_2$ we are looking for. Else $k>j$, we can use
the induction hypothesis for $i=k$, and conclude
that a relation $R_2$ satisfying the right conditions exists in
the bucket for $X_j$.
case 2: The bucket of $X_i$ contains another relation
$R_3$.
Let R be the join of $R_1$ and $R_3$ when $X_i$ is projected out.
Let $t$ be the largest indexed variable in $R$.
If $t <=j$, then $R_2 = R$ satisfies all the required conditions.
Else, $R$ appears in a bucket between $j$ and $i$.
$R$ is tighter than $R_1$ and it is defined on $X_j$.
Then from the induction hypothesis it
follows that there will also be a relation $R_2$ in the bucket
of $X_j$ that is tighter than $R$.
$\Box$
}
\begin{theorem}
Let ${\cal R}$ be a network processed by $DRC_{(i,m)}$ ($DRC_m$, respectively)
along ordering $o$, then the directional extension $E_{(i,m)} ({\cal R})$
($E_m({\cal R})$, respectively) is
directionally relationally $(i,m)$-consistent ($m$-consistent, respectively)
relative to $o$.
\end{theorem}
\begin{proof}
Clear.
\end{proof}
\begin{theorem}
The complexity of $DRC_{(i,m)}$ is $O(n^i(k \cdot n)^{(i m)})$
where $k$ bounds the domain sizes and $n$ is the number of variables.
\end{theorem}
\begin{proof}
The main step of the algorithm (lines 5-8) relates to the processing
of a bucket. The number of relations in each bucket is bounded
by $r + n^i$ when $r$ is the initial set of relations and $O(n^i)$
bounds the number of possible relations of arity $i$ out
of $n$ variables.
The new relations recorded are of size
$k^i$ at the most since they are recorded on $i$ variables
only. The number of subsets of size $m$ out of $n^i$
relations is $O(n^{im})$. Performing $m$-way join
when each relation is of size at most $k^i$ takes
$O(k^{im})$, leading to an overall complexity of $O((n \cdot k)^{im})$.
Applying a projection over all subsets of size $i$ add a
factor of $n^i$ leading to an overall bound of
$O(n^i (n \cdot k)^{im})$.
$\Box$
\end{proof}
The complexity of the nonrestricted version of the
algorithms, $DRC_m$, is not likely to be polynomial even
for $m=2$ since, as we will see, it can solve $NP$-complete problems.
Like similar algorithms for enforcing directional consistency,
the worst-case complexity
of {\sc Directional-Relational-Consistency}
can be bounded as a function of
the topological structure of the problem via parameters like the
{\em induced width} of the graph \cite{DePe88},
also known as {\em tree-width} \cite{Arnborg85}.
\cite{ACP87}.
\begin{definition}[width, tree-width]
A constraint
network ${\cal R}$ can be associated with a constraint graph,
where each node is a variable and two variables that appear in
one constraint are connected. A general graph can be embedded in
a chordal graph\footnote{A graph is chordal if every cycle of size
4 or more has a chord.}.
%ppp
This is normally accomplished by picking a variable ordering
$d = X_1,...,X_n$, then, moving from $X_n$ to $X_1$,
recursively connecting all the neighbors of $X_i$
that precede it in the ordering.
The {\em induced width} (or {\em tree width}) of this ordered graph,
denoted $w*(d)$, is the maximal
number of earlier neighbors in the resulting graph of each
node.
The maximal cliques in the newly generated chordal graph
form a {\em clique-tree} and may
serve as the subproblems in a procedure called
{\em tree-clustering} \cite{DePe89}.
The induced width $w*(d)$ equals the maximal clique minus 1.
The size of the smallest induced width
over all the graph's clique-tree embeddings
is the {\em induced width}, $w*$ of the graph.
%ppp
\end{definition}
It is known that finding the induced width
of a graph is NP-complete \cite{ACP87}, nevertheless every
ordering of the variables $o$, yields a simple to compute upper
bound denoted $w^{*}(o)$ (see \cite{DePe89}). The complexity of
$DRC_m$ along $o$ can be bounded
as a function of $w^{*}(o)$ of its constraint graph.
Specifically \cite{DePe89},
\begin{theorem}
The time complexity and size of the network generated by $DRC_m$
along ordering $o$ is $O(\exp(m(w^{*}(o)+1)))$. In particular, the
time complexity of $DRC_2$ is $O(\exp(2(w^*(o)+1)))$.
\end{theorem}
\begin{proof}
Observe that the number of variables mentioned in any bucket
is at most $w*(o)$, and thus the number of relations in
a bucket is bounded by
$O(n^{w^*(o)})$ and since the number of tuples in each relation
is bounded by $k^{(w^*(o)+1)}$. Consequently,
the overall complexity for processing
a bucket is $O( (nk)^{(w^*(o)+1) m})$.
$\Box$
\end{proof}
The only case for which $DRC_m$ is tractable occurs when $m=1$.
\begin{lemma}
The complexity of $DRC_1$ is $O(n \cdot e^2 \cdot t^2 )$
when $e$ is the number of input relations, and $t$ bounds the number
of tuples in each relation.
\end{lemma}
\begin{proof}
We have $n$ buckets to process. Each bucket will not contain
more then $e$ relations, at any time. The reason is that
extended 1-composition involves projections and intersections
only, which add only a linear number of constraints and which
takes $O(t\cdot e)$ steps.
Simplification of a bucket takes
$O(e^2 \cdot t^2)$ yielding the result.
$\Box$
\end{proof}
%
% Example: Crossword puzzle.
%
\addtocounter{example}{1}
{\bf Example \theexample.}
Crossword puzzles have been used experimentally in evaluating
backtracking algorithms for solving constraint networks
\cite{GFHT90}. We use an example puzzle to illustrate algorithm
$DRC_2$ (see Figure~\ref{FIGURE:crossword}). One possible
constraint network formulation of the problem is as follows:
there is a variable for each square that can hold a character,
$x_1, \ldots, x_{13}$; the domains of the variables are the
alphabet letters; and the constraints are the possible words.
For this example, the constraints are given by,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{1,2,3,4,5}$ \> $=$ \> \{(H,O,S,E,S), (L,A,S,E,R), (S,H,E,E,T),
(S,N,A,I,L), (S,T,E,E,R)\} \\[4pt]
\> $R_{3,6,9,12}$ \> $=$ \> \{(H,I,K,E), (A,R,O,N), (K,E,E,T),
(E,A,R,N), (S,A,M,E)\} \\[4pt]
\> $R_{5,7,11}$ \> $=$ \> \{(R,U,N), (S,U,N), (L,E,T), (Y,E,S),
(E,A,T), (T,E,N)\} \\[4pt]
\> $R_{8,9,10,11}$ \> $=$ \> $R_{3,6,9,12}$ \\[4pt]
\> $R_{10,13}$ \> $=$ \> \{(N,O), (B,E), (U,S), (I,T)\} \\[4pt]
\> $R_{12,13}$ \> $=$ \> $R_{10,13}$
\end{tabbing}
\begin{figure}[thb]
\centering
\mbox{\psfig{figure=puzzle.ps,height=1.7in,width=2.04in}}
\caption{A crossword puzzle}\label{FIGURE:crossword}
\end{figure}
%#####
% This is the old version with only 3 iterations.
\shrink{
Let us perform three iterations of $DRC_3$
with the ordering of variables
$o = x_{13}, x_{12}, \ldots, x_{1}$.
Thus, $x_1$ is the highest variable
in the ordering and $x_{13}$ is the lowest.
The bucket for $x_1$ contains the single relation $R_{1,2,3,4,5}$.
Processing bucket$_1$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{2,3,4,5}$ \> $=$ \> $\Pi_{2,3,4,5}(R_{1,2,3,4,5})$\\[2pt]
\> \> $=$ \> \{(O,S,E,S), (A,S,E,R), (H,E,E,T), (N,A,I,L),
(T,E,E,R)\},
\end{tabbing}
to the bucket of variable $x_2$ which is processed next.
The bucket for $x_2$ contains the single relation $R_{2,3,4,5}$.
Processing bucket$_2$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{3,4,5}$ \> $=$ \> $\Pi_{3,4,5}(R_{2,3,4,5})$\\[2pt]
\> \> $=$ \> \{(S,E,S), (S,E,R), (E,E,T), (A,I,L), (E,E,R)\},
\end{tabbing}
to the bucket of variable $x_3$ which is processed next.
The bucket for $x_3$ contains the relations $R_{3,4,5}$ and $R_{3,6,9,12}$.
Processing bucket$_3$ adds one relation,
%333 Peter note the change here. According to the new defintion we
%record on one subset only if the constraint arity is not bounded.
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
%\> $R_{4,5}$ \> $=$ \> $\Pi_{4,5}(R_{3,4,5})$\\[2pt]
%\> \> $=$ \> \{(E,S), (E,R), (E,T), (I,L), (E,R)\},\\[4pt]
%\> $R_{6,9,12}$ \> $=$ \> $\Pi_{6,9,12}(R_{3,6,9,12})$\\[2pt]
%\> \> $=$ \> \{(I,K,E), (R,O,N), (E,E,T),
% (A,R,N), (A,M,E)\},\\[4pt]
\> $R_{4,5,6,9,12}$\> $=$ \> $\Pi_{4,5,6,9,12}
(R_{3,4,5} \Join R_{3,6,9,12})$\\[2pt]
\> \> $=$ \> \{(E,S,A,M,E), (E,R,A,M,E), (E,T,A,R,N),
(I,L,R,O,N), (E,R,A,R,N)\},
\end{tabbing}
to the bucket of variable
$x_4$.% (relations $R_{4,5}$ and $R_{4,5,6,9,12}$) and
%$x_6$ (relation $R_{6,9,12}$).
Continuing in this manner, at iteration 10 the empty relation is
derived and thus the algorithm can stop and report that the
network is inconsistent.
}
Let us perform a few iterations of
{\sc Directional-Relational-Consistency}, %(${\cal R}, m, o)$,
with $m$ equal to 2 and $o$ as the ordering of the variables
$x_{13}, x_{12}, \ldots, x_{1}$. Thus, $x_1$ is the highest variable
in the ordering and $x_{13}$ is the lowest.
The bucket for $x_1$ contains the single relation $R_{1,2,3,4,5}$.
Processing bucket$_1$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{2,3,4,5}$ \> $=$ \> $\Pi_{2,3,4,5}(R_{1,2,3,4,5})$\\[2pt]
\> \> $=$ \> \{(O,S,E,S), (A,S,E,R), (H,E,E,T), (N,A,I,L),
(T,E,E,R)\},
\end{tabbing}
to the bucket of variable $x_2$ which is processed next.
The bucket for $x_2$ contains the single relation $R_{2,3,4,5}$.
Processing bucket$_2$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{3,4,5}$ \> $=$ \> $\Pi_{3,4,5}(R_{2,3,4,5})$ $=$ \{(S,E,S), (S,E,R), (E,E,T), (A,I,L), (E,E,R)\},
\end{tabbing}
to the bucket of variable $x_3$ which is processed next.
This bucket contains the relations $R_{3,4,5}$ and $R_{3,6,9,12}$.
Processing bucket$_3$ adds one relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
%\> $R_{4,5}$ \> $=$ \> $\Pi_{4,5}(R_{3,4,5})$\\[2pt]
%\> \> $=$ \> \{(E,S), (E,R), (E,T), (I,L), (E,R)\},\\[4pt]
%\> $R_{6,9,12}$ \> $=$ \> $\Pi_{6,9,12}(R_{3,6,9,12})$\\[2pt]
%\> \> $=$ \> \{(I,K,E), (R,O,N), (E,E,T),
% (A,R,N), (A,M,E)\
\> $R_{4,5,6,9,12} = \Pi_{4,5,6,9,12}
(R_{3,4,5} \Join R_{3,6,9,12})$\\[2pt]
\> \> $=$ \{(E,S,A,M,E), (E,R,A,M,E), (E,T,A,R,N), (I,L,R,O,N), (E,R,A,R,N)\},
\end{tabbing}
to the bucket of variable $x_4$.
The bucket for $x_4$ now contains the relation $R_{4,5,6,9,12}$.
Processing $bucket_4$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{5,6,9,12}$\> $=$ \> \{(S,A,M,E), (R,A,M,E), (T,A,R,N), (L,R,O,N), (R,A,R,N)\}.
\end{tabbing}
The bucket for $x_5$ contains now the relations $R_{5,6,9,12}$, and
$R_{5,7,11}$.
Processing bucket$_5$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{6,7,9,11,12}$ \>\> $=$ \> \{(A,E,R,N,N), (A,U,M,N,E),
(A,U,R,N,N), (R,E,O,T,N)\}.
\end{tabbing}
The bucket for $x_6$ contains only the newly generated relation
$R_{6,7,9,11,12}$.
Processing bucket$_6$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{7,9,11,12}$\> $=$ \> \{(E,R,N,N), (U,M,N,E),
(U,R,N,N), (E,O,T,N)\},
\end{tabbing}
to the bucket for $x_7$.
Processing bucket$_7$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{9,11,12}$\> $=$ \> \{(R,N,N), (M,N,E), (O,T,N)\},
\end{tabbing}
to the bucket of $x_9$.
The bucket of $x_8$ contains only
the original relation $R_{8,9,10,11}$, and when processed it
adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
\> $R_{9,10,11}$ \> $=$ \> \{(I,K,E), (R,O,N), (E,E,T),
(A,R,N), (A,M,E)\}.
\end{tabbing}
The bucket for $x_9$ contains the relations
$R_{9,10,11}$, $R_{9,11,12}$.
Processing bucket$_9$ adds the relation,
\begin{tabbing}
\=xxxxxxxx\=xx\=\{\=\kill
%\> $R_{10,11}$ \> $=$ \> \{(K,E), (O,N), (E,T),
%(R,N), (M,E)\}, \\[4pt]
%\> $R_{11,12}$ \> $=$ \> \{(N,N), (N,E) (T,N)\}, \\[4pt]
%\> $R_{12}$ \> $=$ \> \{(E), (N), (N)\}, \\[4pt]
\> $R_{10,11,12}$\>
%$=$ \>$\Pi_{\{x_{10},x_{11},x_{12}\}} T_{9,10,11} \Join R_{9,11,12}$ \>\>\>\>\>\>\>\>\>\>\>\>
$=$ \{(O,N,N)\}.
\end{tabbing}
The bucket for $x_{10}$ contains the relations $R_{10,11,12}$, and
$R_{10,13}$.
Processing bucket$_{10}$ adds the empty relation.
Since the empty relation was derived, the algorithm stops and
reports that the network is inconsistent.
%Continuing in this manner, at iteration 10 the empty relation is
%derived and thus the algorithm can stop and report that the
%network is inconsistent.
Finally, we propose algorithm
{\sc Adaptive-Relational-Consistency} ($ARC$)
which is the relational counter-part of algorithm adaptive-consistency
\cite{DePe88}. Like algorithm $DRC_m$,
it process the buckets in order from last
to first. When processing the bucket of $x_j$, it applies
extended composition relative to {\em all} the relations in
that bucket, and with respect to the whole set of variables appearing in the
bucket excluding $x_j$. It then places the resulting relation in its
appropriate bucket. Algorithm $ARC^i$ is a restricted version
of $ARC$ that records relations
of arity $i$ only. It is identical to $ARC$ accept that
step 4 an 5 are modified to record constraints on subsets of size $i$.
Algorithm $ARC$ generates a globally-solved problem and it can be
viewed as a compilation algorithm since it yields a
representation from which the set
of solutions can be recovered in linear time.
It is identical
to $DRC_m$ when $m$ is not bounded.
For bravity, we omitted the steps of simplification and instantiations.
\begin{tabbing}
xxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=\kill
{\sc Adaptive-Relational-Consistency}(${\cal R}, o$)\\[3pt]
1. \> \parbox[t]{4.60in}{
Initialize: generate an ordered partition of the constraints,
$bucket_1$, \ldots, $bucket_n$, where $bucket_i$
contains all constraints whose highest variable is $x_i$.
}\\[4pt]
2. \> {\bf for} $p \leftarrow n$ {\bf downto} $1$ {\bf do}\\[2pt]
3. \>\> {\bf for} all the relations
$R_{S_1}, \ldots, R_{S_j}$ in $bucket_p$ {\bf do}\\[4pt]
4. \>\>\> $A \leftarrow \bigcup_{i=1}^{j} S_i -\{x_{p}\}$\\[4pt]
5. \>\>\> $R_A \leftarrow
R_A \cap ~ \Pi_A(\Join_{i=1}^{j} R_{S_i})$\\[4pt]
6. \>\>\> {\bf if} $R_{A}$ is not the empty relation {\bf then}\\
7. \>\>\>\> add $R_A$ to its appropriate bucket\\
8. \>\>\> {\bf else} \> exit and return the empty network\\
9. \> {\bf return} $E_o(R) = bucket_1 \cup bucket_2 \cup \cdots \cup bucket_n$
\end{tabbing}
\begin{theorem}
Algorithm {\sc Adaptive-Relational-Consistency} ($ARC$) globally
solves any constraint network.
The complexity of the algorithm when
processed along ordering $o$ is bounded by
$O(n \cdot exp(w^*(o)\cdot 2^{w^*(o)}))$.
\end{theorem}
\begin{proof}
The algorithm is clearly generating a backtrack-free
representation. The number of relations in each bucket will
increase to at most $2^{w^*(o)}$ relations. The arity
of each relation is bounded by $(w^*(o)+1)$ and thus its size is
bounded by $O(k^{(w^*(o)+1)})$. Consequently the overall
complexity is bounded by the cost of joining at most ($2^{w^*(o)}$) relations
of size $O(k^{w^*(o)+1})$ which can be bounded by
$O(exp (2^{w^*(o)} \cdot (w^*(o)+1)))$.
$\Box$
\end{proof}
Finally we can show that some NP-complete problems are solved
by $DRC_2$.
\begin{theorem}
Crossword puzzles can be globally solved by $DRC_2$ in any variable
ordering.
\label{thm-19}
\end{theorem}
\begin{proof}
Let ${\cal R}$ be a crossword puzzle instance. We will show that
the buckets
of the network generated by $ARC$
have at most two relations.
Therefore, for such problems $ARC$ reduces to $DRC_2$.
Since $ARC$ generates a backtrack-free problem
it follows that so will
$DRC_2$.
We will now prove that there are at most two relations in each bucket
of the crossword puzzle at any time during processing by $ARC$.
Let us annotate each variable in a constraint by a $+$ if
it appears in a horizontal word and by a $-$ if it
appears in a vertical word. Clearly, in the initial specification
each variable appears in at most two constraints and each
annotated variable appears in just one constraint
(with that annotation).
We show that this property is maintained throughout the algorithm's
performance.
It could be the case that the two annotated variables will appear
in the same constraint. The annotation of the variables
in the constraint resulting from extended 2-composition inherits the
annotation in the parent constraints. If a variable appeared with
annotation ``+'' in one, and annotation ``$-$'' in the other, its
annotation in the resulting constraint will be ``+,$-$''.
The claim can be proved by induction on the processed buckets.
Assume that after processing buckets $x_n, \ldots, x_i$
{\em all} the constraints appearing in the union of all
the buckets from $bucket_{i-1}$ to $bucket_1$,
satisfy that
each annotated variable appears in at most one constraint.
When processing $bucket_{i-1}$, since it contains only two
constraints (otherwise it will contain multiple annotations
of variable $x_{i-1}$), it generates a single new
constraint. Assume that the constraint is added
to the bucket of $x_j$.
Clearly, if $x_j$
is annotated positively (respectively negatively)
in the added constraint, $bucket_j$
cannot contain already a constraint with a positive (respectively, negative)
annotation of $x_j$. Otherwise, it means that before processing
bucket $i-1$, there were two constraints with positive (respectively negative)
annotation of $x_j$, one in the bucket of $x_{i-1}$
and one in the bucket of $x_j$, which
contradicts the induction hypothesis.
A very similar argument can be applied to the multiple annotation
case.
$\Box$
\end{proof}
The complexity of $DRC_2$ for the crossword puzzles is bounded
by $O(n \cdot k^{2(w*(o)+1)})$ thus reducing the base of the
exponent by a factor of $n$.
%In the next subsection we will show that known operators
%in propositional theories and linear inequalities
%are special cases of extended-relational composition.
\section{Variable elimination operators}
The extended $m$-composition operator unifies known operators such as
resolution in theorem proving, joins in relational databases, and
variable elimination for solving equations and inequalities.
%ddd delete
%It can be regarded as an operator of variable elimination.
%One known such operator for processing propositional {\em CNF} theories
%is the resolution operator.
%ddd
\subsection{Variable elimination in propositional {\em CNF} theories}
We denote propositional symbols, also called
{\em variables}, by uppercase letters $P,Q, R, \ldots$,
propositional literals (i.e., $P,\neg P$) by lowercase letters
$p,q,r, \ldots$, and
disjunctions of literals, or {\em clauses}, by $\alpha, \beta , \ldots$.
%For instance, $\alpha = (P \vee Q \vee R)$ is a clause.
%We will sometime denote by $\{P,Q,R \}$ the clause
%$(P \vee Q \vee R)$.
A {\em unit clause} is a clause of size 1.
The notation $(\alpha \vee T)$, when $\alpha = (P \vee Q\vee R)$
is a shorthand for
the disjunction $(P \vee Q \vee R \vee T )$, and $\alpha \vee \beta$
denotes the clause whose literal appears in either $\alpha$ or
$\beta$.
The {\em resolution} operation over two clauses $(\alpha \vee Q)$
and $(\beta \vee \neg Q)$ results
in a clause $(\alpha \vee \beta )$, thus eliminating $Q$.
%{\em Unit resolution} is a resolution operation when one of the
%clauses is a unit clause.
%The operator $\sim$
%over literals is defined as follows:
%If $p=\neg Q$, $\sim p = Q$; if $p=Q$, $\sim p24
A formula $\varphi$ in conjunctive normal form ({\em CNF})
is a set of clauses
$\varphi = \{\alpha_1 , \ldots, \alpha_t \}$ that denotes their
conjunction.
The set of $models$ of a formula $\varphi$, denoted $models(\varphi )$,
is the set of all satisfying truth assignments to all its symbols.
%A clause $\alpha$ is {\em entailed} by $\varphi$,
%$\varphi \models \alpha$, if and only if $\alpha$ is true in all
%models of $\varphi$. % A clause $\alpha$ is a {\bf prime implicate}
%of $\varphi$ if and only if $\varphi \models \alpha$ and
%$\not \exists \beta \subseteq \alpha$ such that $\varphi \models \beta$.
A Horn formula is a {\em CNF} formula whose clauses all have at most one
positive literal.
%A definite formula is a {\em CNF} formula that has exactly one positive
%literal.
%A clause is positive if it contains only positive literals and
%is negative if it contains negative literals only.
%A $k$-{\em CNF} formula is one whose clauses are
%all of length $k$ or less.
%It is easy to show that the clause generated by resolution
%is equivalent to the relation generated by extended 3-composition.
Let $EC_{Q^\prime}(R_A ,R_B)$ denote the relation generated by
extended 2-composition of $R_A$ and $R_B$
relative to $A \cup B - \{Q\}$, $Q \in A \cap B$.
It is easy to see that pair-wise resolution is equivalent to
extended 2-composition.
\begin{lemma}
The {\em resolution} operation over two clauses $(\alpha \vee Q)$
and $(\beta \vee \neg Q )$, results
in a clause $(\alpha \vee \beta )$ satisfying:
$models(\alpha \vee \beta ) = EC_{Q^\prime} (models(\alpha), models(\beta))$.
\end{lemma}
\begin{proof}
Clear.
\end{proof}
In \cite{vanBeek92b} we have shown that row-convex relations
that are closed under extended 2-composition can be globally
solved by $DRC_2$. Since any bi-valued relation is row-convex,
and since {\em CNF} theories are bi-valued,
$DRC_2$, if applied to the relational representation of a {\em CNF}
theory, will decide the problem's satisfiability and generate
a globally solved representation.
Since extended 2-decomposition can be applied to the {\em CNF} representation
directly, transformation to a relational representation can be avoided.
Replacing extended 2-composition by resolution
and the instantiation step by unit resolution in $DRC_2$,
results in algorithm {\em Directional Resolution (denoted $DR$)} which
is the core of the well known Davis Putnam algorithm for
satisfiability \cite{DaPu60,DeRi94}.
Applying the same exchange within
$DRC_{(i,2)}$
yields algorithm {\em bounded directional resolution ($BDR_i$)}
which is a polynomial approximation
of $DR$ \cite{DeRi94}.
As follows from our theory,
algorithm directional resolution
globally solves any {\em CNF} theory.
(It is well known that $DR$ solves the satisfiability of {\em CNF}s.)
\begin{tabbing}
xxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=\kill
{\sc Directional-Resolution} ($\varphi,o$)\\[3pt]
Input: \>\> \parbox[t]{4.30in}{
A {\em CNF} theory $\varphi$, an ordering
$o = Q_1 , \ldots,Q_n$ of its variables.
}\\[2pt]
Output: \>\> \parbox[t]{4.30in}{
A decision of whether $\varphi$ is satisfiable.
if it is, a theory $E_o (\varphi )$, equivalent to $\varphi$,
else an empty directional extension.
}\\[2pt]
1. \> \parbox[t]{4.50in}{
Initialize: generate an ordered partition of clauses into buckets.
$bucket_1$, \ldots, $bucket_n$, where $bucket_i$
contains all clauses whose highest literal is $Q_i$.
}\\[2pt]
2. \> {\bf for} $i \leftarrow n$ {\bf downto} $1$ {\bf do}\\
3. \>\> {\bf if} there is a unit clause {\bf then}\\
\>\>\> apply unit-resolution
and place the resolvents in their right bucket\\
\>\>\> if the empty clause was generated, theory is not satisfiable\\
4. \>\> {\bf else}
resolve each pair $\{(\alpha \vee Q_i),
(\beta \vee \neg Q_i)\} \subseteq bucket_i$.\\
\>\>\> {\bf if} $\gamma = \alpha \vee \beta$ is empty,
return $E_o(\varphi ) = \{\}$, theory is not satisfiable\\
\>\>\> {\bf else} determine the index of $\gamma$ and
add it to the appropriate bucket.\\[2pt]
5. \> {\bf return} $E_o (\varphi) \leftarrow \bigcup_{i} bucket_i$
\end{tabbing}
Incorporating resolution into $DRC_1$
%{\em with the simplification step},
yields algorithm unit propagation. The operation of
extended 1-composition has no effect
since projections
on clauses generate universal relations.
As well, the simplification step, if included,
allows resolution involving non-unit clauses
as long as the variables appearing in one clause are
contained in the other clause.
%333Peter should we leave the lemma or delete it.
%I delete it
%it is not clear what DLE_2 on Horn theories means exactly
%a simple meaning is that the relational expreassion of
%Horn theories is solvable by DLE_2. I dont know if it is
%worthwhile to mention.
%\begin{lemma}
%Algorithm $DRC_2$ %for {\em CNF} theories
%decides the satisfiability of Horn theories.
%$\Box$
%\end{lemma}
As in the general case, $DR$ generates a globally solved representation
and its complexity can be bounded
exponentially as a function of the induced width, $w^*$ of
the {\em CNF} theory.
The graph of a {\em CNF} theory associates propositional symbols
with nodes and connects two nodes if their associated symbols
appear in the same clause.
\subsection{Variable elimination in linear inequalities}
In database theory, a $k$-ary relation $r$ is a finite set
of tuples and a database is a finite set of relations.
However, the relational calculus and algebra can be developed
without the finiteness assumptions for relations.
We will use the term unrestricted relation, for finite or infinite
sets of points in a $k$-dimensional space \cite{kanelakis92}.
In particular, it was shown that relational calculus
is identical to relational algebra for countable domains and
that relational algebra for infinite relations is exactly
the same as for finite relations \cite{kanelakis90}\footnote{We
thank Manolis Koubarakis for pointing to us the extension to
infinite domains.}.
Therefore,
the relational framework we have presented applies as is
to infinite relations.
In this section we will demonstrate the applicability of our
results to the special case of linear inequalities over
infinite domains like the Rationals
as well as over
finite and infinite subsets of the Integers.
Let us consider the class of linear inequalities
% However to simplify
% we will assume that the domains are integers bounded between [-M,M]
% for very large M, whenever other bounds are not explicitly
% given.} of the integers and
where a constraint between $r$ variables
or less
is a conjunction of linear
equalities and inequalities of the form
$\sum_{i=1}^r a_i x_i \leq c$,
where $a_i$, and $c$ are
rational constants.
For example, the conjunction
$(3x_{i} + 2x_{j} \leq 3) \wedge (-4x_{i} + 5x_{j} \leq 1)$
is an allowed constraint between variables $x_i$ and $x_j$. A
network with constraints of this form can be formulated as a
%an integer
linear program
where the domains are infinite Rational,
or Integers,
or finite subsets of integers
restricted by unary linear inequalities.
We will show first that over the Rationals
the standard operation of variable elimination
is equivalent to
extended 2-composition while this equivalence is not maintained
over the integers.
Let us denote by $sol(\alpha)$ the unrestricted relation
of tuples from the domain satisfying a set of linear inequalities,
$\alpha$.
We define the elimination operation as follows:
\begin{definition}[linear elimination]
Let $\alpha = \sum_{i=1}^{(r-1)} a_i x_i + a_r x_r \leq c$,
and $\beta = \sum_{i=1}^{(r-1)} b_i x_i + b_r x_r \leq d$.
Then $elim_r(\alpha, \beta )$ is applicable only if $a_r$
and $b_r$ have opposite signs, in which case
$elim_r(\alpha, \beta ) = \sum_{i=1}^{r-1} ( - a_i \frac{b_r}{a_r}
+b_i ) x_i \leq -\frac{b_r}{a_r} c+d$.
If $a_r$ and $b_r$ have the same sign the elimination implicitly
generates the universal constraint.
\end{definition}
\begin{lemma}
$sol(elim_r(\alpha, \beta )) \supseteq EC_r (sol(\alpha), sol(\beta))$
when the domains are the Integers.
However, over the Rationals
$sol(elim_r(\alpha, \beta )) = EC_r (sol(\alpha), sol(\beta))$.
\end{lemma}
\begin{proof}
It is easy to see that if $a_r$ and $b_r$ have the same
sign (both are positive or both are negative), then
for any assignment to $x_1 , \ldots, x_{i-1}$
there is always a value for $x_r$ that extends
$x_1 , \ldots, x_{i-1}$ and that satisfies both $\alpha$ and
$\beta$. Therefore, the extended composition
produces the universal relation.
%Specifically, there is a value for $x_r$ that satisfies $\alpha$ and a
Assume now that $a_r$ and $b_r$ contain opposite signs.
Multiplying $\alpha$ by $ - \frac{b_r}{a_r}$ and summing
the resulting inequality with $\beta$ yields the inequality
\[
\sum_{i=1}^{r-1} ( - a_i \frac{b_r}{a_r}
+b_i ) x_i \leq -\frac{b_r}{a_r} c+d.
\]
In other words, any tuple satisfying this inequality can be extended
to a {\em rational value} of $x_r$ in a way that satisfies
both $\alpha$ and $\beta$. It is unclear, though,
that there exists an integer extension to $x_r$
which is the reason for partial containment for the integers.
$\Box$
\end{proof}
% Note that positive coefficient inequalities may not
% be closed under the elimination operator.
In \cite{vanBeek92b} we have shown that linear inequality
constraints over finite sets of integers are row-convex and
therefore can be globally solved by $DRC_2$ using their
relational form. The definition of row-convexity can be extended
to infinite domains without any modification. This implies that
linear inequalities over infinite domains that are relationally
2-consistent are globally solved and consequently they can be
globally solved by $DRC_2$.
Incorporating linear elimination into $DRC_2$ (when the
constraints are presented as linear inequalities) results
in algorithm {\em Directional Linear Elimination} (abbreviated
$DLE$) which is the well known Fourier elimination
algorithm (see \cite{lassez}).
Indeed, as dictated by our theory
and as is already known
the algorithm decides the solvability
of any set of linear inequalities over the Rationals.
% The algorithm may be modified to solve
% linear inequalities over the integers directly (without translation
% to a relational form).
% The algorithm does not include a simplification step.
\begin{tabbing}
xxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=\kill
{\sc Directional-Linear-Elimination} ($\varphi,o$)\\[3pt]
%\shrink{
Input: \>\> \parbox[t]{4.20in}{
A {\em set of linear inequalities} $\varphi$, an ordering
$o = x_1 , \ldots,x_n$ of its variables.
% defined over finite set of integers.
}\\[2pt]
Output: \>\> \parbox[t]{4.20in}{
A decision of whether $\varphi$ is satisfiable.
{\bf if} it is, a theory $E_o (\varphi )$, equivalent to $\varphi$,
else an empty directional extension.
}\\[2pt]
%}
1. \> \parbox[t]{4.50in}{
Initialize: generate an ordered partition of the inequalities into buckets.
% $bucket_1$, \ldots, $bucket_n$, where $bucket_i$
% contains all inequalities whose highest variable is $x_i$.
}\\[2pt]
2. \> {\bf for} $i \leftarrow n$ {\bf downto} $1$ {\bf do}\\[2pt]
3. \>\> {\bf if} $x_i$ has one value in its domain {\bf then}\\[2pt]
4. \>\>\> \parbox[t]{4.00in}{
substitute the value into each inequality
in the bucket and put the resulting
inequality in the right bucket.
}\\[2pt]
4. \>\> {\bf else}
\> for each pair $\{\alpha, \beta \}\subseteq bucket_i$,
compute $\gamma = elim_i(\alpha,\beta)$\\
\>\>\> if $\gamma$ has no solutions, return $E_o(\varphi ) = \{\}$,
theory is not satisfiable\\
\>\>\> else add $\gamma$ to the appropriate bucket.\\[2pt]
5. \> {\bf return} $E_o (\varphi) \leftarrow \bigcup_{i} bucket_i$
\end{tabbing}
\addtocounter{example}{1}
{\bf Example \theexample.}
\[
\varphi(x_1,x_2,x_3,x_4) = \{(1)~ 5x_4 + 3 x_2 -x_1 \leq 5 ,~
(2)~x_4+x_1 \leq 2, ~(3)~-x_4 \leq 0,
\]
\[
(4) ~x_3 \leq 5,~ (5)~x_1+x_2-x_3 \leq -10,~ (6)~x_1 +2x_2 \leq 0 \}.
\]
Initially, $bucket_4 = \{
5x_4 + 3 x_2 -x_1 \leq 5 ,~
x_4+x_1 \leq 2, ~ -x_4 \leq 0\}$,
$bucket_3 =\{~x_3 \leq 5,~ x_1+x_2-x_3 \leq -10\}$
and $bucket_2 = \{ x_1 +2x_2 \leq 0\}$.
Processing $bucket_4$, applying elimination relative to $x_4$
over inequalities (1) and (3) and (2) and (3), respectively,
results in:
$3x_2 -x_1 \leq 5$, placed into $bucket_2$, and
$x_1 \leq 2$, placed into $bucket_1$.
Processing $bucket_3$ next, eliminates $x_3$ from (4) and (5), yielding
$x_1 + x_2 \leq -5$, placed into $bucket_2$ and processing
$bucket_2$ adds no new inequality.
%\shrink{
We can now generate a backtrack-free solution in the following way.
Select a value for $x_1$ from its domains
satisfying the unary inequalities in
$bucket_1$. After selecting assignments to $x_1 , \ldots,x_{i-1}$
select a value for $x_i$ satisfying all the inequalities in
$bucket_i$. This is easy since all the constraints are unary
once the values of $x_1, \ldots,x_{i-1}$ are determined.
%333 Peter, should we comment on how easy this is?
%Simon Kasif had sent me a message discussing only
%the complexity of this issue. Should we comment on that?
%}
\begin{theorem}
$DLE$ (Fourier elimination) globally solves a set of linear
inequalities over the Rationals\footnote{The result holds also
for the Reals, however since relational algebra was extended
for countable domains only it does not follow from the general theory
and need to be proved directly.}.
\end{theorem}
\begin{proof}
It is known that Fourier elimination algorithm decides the
consistency of a set of linear inequalities over the rationals.
Since $DRC_2$ globally solves a set of row-convex constraints,
since linear inequalities are row-convex and are
closed under extended 2-composition, and since $DLE$
is equivalent to $DRC_2$, the claim follows.
$\Box$
\end{proof}
\subsubsection{Linear inequalities over the integers:}
When the domains are the Integers the algorithm is no longer
guaranteed to decide consistency since linear elimination is not
identical to extended 2-composition. If the empty relation is
generated by $DLE$, the problem is indeed inconsistent, else, the
problem may or may not be consistent. Nevertheless, the
representation generated by $DLE$ could be useful since it is a
backtrack-free representation relative to the rationals, of a
superset of the sought-for integer solutions. From such a
representation an integer solution may be extracted using
backtrack search that may enjoy substantial amount of pruning.
\shrink{
To make sure that
an integer extension to $x_r$ exists,
we only need to make sure
that any solution for $x_1, \ldots,x_{r-1}$
can be consistently extended, not just by a single value, but
by an interval of length 1 in $x_r$'s domain.
To capture this approximation we define
the notion of {\em integer linear elimination} as follows.
\begin{definition}[(integer linear elimination)]
Let $\alpha = \sum_{i=1}^{(r-1)} a_i x_i + a_r x_r \leq c$,
and $\beta = \sum_{i=1}^{(r-1)} b_i x_i + b_r x_r \leq d$.
Then $ielim_r(\alpha, \beta )$ is applicable only if $a_r$
and $b_r$ have opposite signs, in which case
$ielim_r(\alpha, \beta ) = \sum_{i=1}^{r-1} ( - a_i \frac{b_r}{a_r}
+b_i ) x_i \leq -\frac{b_r}{a_r} c+d - 1$.
If $a_r$ and $b_r$ have the same sign the elimination implicitly
generates the universal constraint.
\end{definition}
We will call $IDLE$ the elimination algorithm that uses
integer linear elimination. Clearly, if it recognize that
the restricted problem is unsatisfiable (no rational solution exists),
then no integer solution exists for the restricted problem
but one may still exists for the original set of inequalities.
Given a set of linear inequalities over the integers,
We can use both DLE and IDLE to generate two directional
extensions which are globally solved over the rationals,
while their integer solutions create a bounding envelope
over the integer solutions of the inequalities.
In summary:
\begin{theorem}
Let $r$ be a set of linear inequalities over the integers,
and $sol(r)$, its unrestricted relation over the integers.
Let $E_o(r)$ and $IE_o(r)$ be the directional extensions generated by
$DLE$ and $IDLE$, respectively,
then $sol(IE_o(r)) \subseteq sol(r) = sol(E_o(r))$.
\end{theorem}
\begin{proof}
to be completed
\end{proof}
}
\subsubsection{Complexity of DLE}
Algorithm $DLE$ is generally exponential since it may record
exponential number of constraints.
If the domains are finite, the finite
relational representation can be used
(in which case $DLE = DRC_2$), and in this case the complexity can
be bounded using the notion of
induced width.
Otherwise, $DLE$'s complexity may be worst-case exponential
even when the induced width $w^*$, is bounded.
The reason is that an exponential number of
inequalities may need to be recorded on the same
subset of variables.
One cannot ``intersect'' two
inequalities and replace them by one.
In other words, linear inequalities are not closed
under intersection while relations are.
\subsubsection{Case of binary inequalities:}
When the linear inequalities are over pairs of variables only,
algorithm $DLE$, as presented here is still exponential.
However it was shown to have a polynomial implementation
over the Rationals that uses a special data structure that
bound the number of inequalities over any pair of variables
and lead to a polynomial complexity \cite{naor}.
Over the integers the binary linear problem is
NP-complete \cite{lag85}.
A more restricted case of binary monotone inequalities
of the form $ax_i -bx_j \leq c$, where
$a,b,c$ positive integers,
was shown to be weakly NP-complete since
there exists a pseudo-polynomial algorithm \cite{naor}.
For bounded integer domains the general binary linear problem
can be expressed in a relational form
%Since the generated relations are row-convex (see also section 5), the
and since $DRC_2$ is polynomial over binary constraints,
the class can be solved in polynomial time
relative to the maximal range of the integer domains.
In summary,
\begin{theorem}
Algorithm $DLE$ is exponential
even for binary inequalities and even for bounded induced width.
For finite domains
$DRC_2$ is applicable. Its complexity for binary constraints
is polynomial (in the input and the maximum domain range),
and is exponentially bounded by
the induced width, for non-binary constraints.
$\Box$
\end{theorem}
%\begin{proof}
%to be completed
%\end{proof}
There are additional special classes for which $DLE$ is polynomial.
One case is the class of {\em simple temporal constraints}.
Those are unary
and binary constraints of the form $X-Y \leq a $.
Algorithm $DLE$ reduces, in this case, to the shortest path
algorithm presented in \cite{DMP91}.
The algorithm is polynomial
since the number of inequalities produced
is bounded
(in this simple case at most two inequalities are needed between
any pair of variables)
and since the class
is closed under linear elimination.
The linear elimination operator coincides
in this case, with extended 2-composition over the integers, and
therefore,
$DLE$ is complete for simple temporal constraints
over the integers as well.
Note, that although this is a subclass of monotone inequalities,
tractability of $DLE$ over this class
does not follow from \cite{naor} whereby a
special implementation was required.
\begin{theorem}
Algorithm $DLE$ is polynomial over the class
of unary and binary inequalities of the form $X-Y \leq a$,
$X \leq b$. The algorithm globally solves such
inequalities, over the integers, Rationals and the Reals.
\end{theorem}
\begin{proof}
Over the Integers and the Rationals, global consistency follows
from the global consistency of $DRC_2$. Over the Reals
the proof is given in \cite{DMP91}.
\end{proof}
\shrink{
Another interesting class which is closed under
linear elimination is what we call {\em Horn linear inequalities.}
\begin{definition}[(Horn linear inequalities)]
A set of linear inequalities are called $Horn$ if
they are either of the form $\sum_i x_i \leq a$
or $-x \leq a$.
\end{definition}
It is easy to see that for this class $DLE$ is polynomial since only
the simplification step is activated.
In other words, for this class $DLE = DLE_2$.
\begin{theorem}
$DLE$ is polynomial over Horn linear inequalities,
and it globally solves such problems
over the Rationals and the integers.
\end{theorem}
\begin{proof}
to be completed
\end{proof}
}
\subsubsection{Case of zero-diversity theories:}
Propositional {\em CNF}s as well as linear inequalities
share an interesting syntactic property: It is easy to
recognize whether applying extended 2-composition relative
to variable $x_i$ results in a universal constraint.
Both resolution and linear
elimination relative to $x_i$ are effective
only when the variable to be eliminated appears with opposite
signs. This leads to a simple-to-identify
tractable class for both these languages.
If there exists an ordering of the variables, such that
in each of its $bucket_i$,
$x_i$ appears with the same sign, then the theory
is already globally solved relative to that ordering.
We called in \cite{DeRi94} such theories as ``zero diversity''
and we showed that they can be recognized in linear time.
%333 DO WE NEED AN EXAMPLE?
\shrink{
\begin{definition}[Horn linear inequalities]
A set of linear inequalities are called $Horn$ if in each,
at most one variable appears negatively. We say that a variable
appears negatively if its coefficient is negative.
\end{definition}
\begin{lemma}
A set of Horn linear inequalities all having a positive variable
is satisfiable.
\end{lemma}
\noindent
{\bf Proof.} We can always assign each variable a small
enough integer value to satisfy
each inequality $\Box$.
We call {\em unit elimination}, algorithm $DRC_2$ when the
join operation in the simplification step is replaced with
linear elimination.
The algorithm eliminates unary linear inequalities over the
set of all inequalities. We conclude,
\begin{theorem}
A set of Horn linear inequalities over the integers
can be solved by unit elimination, or
by $DRC_2$, when domains are finite.
\end{theorem}
}
\section{From Local to Global Consistency}
Much work has been done on identifying relationships between
properties of constraint networks and the level of local
consistency sufficient to ensure global consistency. This work
falls into two classes: identifying topological properties of the
underlying graph of the network and identifying properties of the
constraints.
For work on identifying topological properties, Freuder
\cite{Freuder82} identifies a relationship between the
{\em width} of a constraint graph and the level of local
consistency needed to ensure a solution can be found without
backtracking. Dechter and Pearl \cite{DePe88} provide an
adaptive scheme where the level of local consistency is adjusted
on a node-by-node basis. Dechter and Pearl \cite{DePe89}
generalize the results on trees to hyper-trees which are called
acyclic databases in the database community \cite{BFMY83}.
For work on identifying properties of the constraints, Montanari
\cite{Montanari74} shows that path consistency is sufficient to
guarantee that a binary network is globally consistent
%(Montanari uses the term {\em decomposable})
if the relations are monotone.
Dechter \cite{Dechter92} identifies a relationship between the
size of the domains of the variables, the arity of the
constraints, and the level of local consistency sufficient to
ensure the network is globally consistent. These results were
extended recently by van Beek and Dechter to the property of
tightness and looseness of the constraints in the network
\cite{vBDe94b,vanBeek94}. Van Hentenryck, Deville, and Teng
\cite{VHDT92} show that arc consistency is sufficient to test
whether a network is satisfiable if the relations are from a
restricted class of functional and monotone constraints. These
properties were generalized recently to implicational
constraints \cite{Kirousis93,cooper94} and to the property of
row-convexity \cite{vBDe94a}.
Finally, for work that falls into both classes,
Dechter and Pearl \cite{DePe91} present effective procedures for
determining whether a constraint network can be formulated as a
{\em causal theory} and thus a solution can be found without
backtracking. Whether a constraint network can be so formulated
depends on the topology of the underlying constraint graph and
the type of the constraints.
Most of these relationships were formulated initially using the
variable-based definition of local-consistency. Reference to
constraints was indirect via the constraint's arity as a parameter.
Recently, we have shown that these relationships can be
generalized using relational consistency and
that they lead to a characterization of classes of problems
that can be solved by a restricted level $m$ of $DRC_m$.
The general pattern is as follows. We present a sufficient
condition showing that a network satisfying a property $p$, and having
a corresponding level of local consistency $l(p)$, is globally
consistent. This implies that whenever the property $p$ is maintained
under extended $l(p)$-composition, those networks (satisfying $p$) can
be globally solved by $DRC_{l(p)}$. Furthermore, it is sufficient for
condition $l(p)$ to hold only relative to the particular ordering on
which the algorithm is applied.
In this section we add two such generalized relationships
involving a bound on the size of the domains and acyclicity.
\subsection{Domain size and global consistency}
In \cite{Dechter92}, we have shown that:
\begin{theorem}\cite{Dechter92}\label{domains}
If ${\cal R}$ is a $k$-valued binary constraint network
that is $k+1$ consistent then it is globally consistent.
If ${\cal R}$ is a $k$-valued $r$-ary constraint network
that is $k(r-1)+1$ consistent
then it is globally consistent.
\label{domains2}
\end{theorem}
We now show that by using the notion of relational consistency
the above relationship for $r$-ary networks
(as well as its proof), are simplified.
Moreover, the implied algorithm can be stated more coherently.
\begin{theorem}
A $k$-valued constraint network ${\cal R}$, that is
$k$-relational-consistent is globally consistent.
\end{theorem}
\begin{proof}
We prove the theorem by showing that
relationally $k$-consistent $k$-valued networks are
relationally $(k+i)$-consistent for any $i~\ge~1$.
According to the definitions, we need to show that,
if there are relations $R_{S_1} , \ldots, R_{S_{k+i}}$,
all sharing variable $x_t$, and if \={x}
is a locally consistent tuple defined over $\bigcup_{i=1}^{k+i} S_i - \{x_t\}$,
then there is a value $a$ of $x_t$ such that (\={x},$ a$)
belongs to the joined relation
$R_{S_1} \Join, \ldots,\Join~R_{S_{k+i}}$.
With each value $j$, in the domain of $x_t$
we associate a subset
$A_j$ that contains all those relations in
$\{R_{S_1} , \ldots, R_{S_{k+i}} \}$
%$\bigcup_{i=1}^{k+i} S_i - \{x_{k+i}\}$,
that are consistent with the assignment
$x_t~=~j$.
Since variable $x_t$ may take on $k$ possible values
$1,2, \ldots,k$ we get $k$ such subsets,
$A_1, \ldots,A_k$.
We claim that there must be at least one set, say $A_1$,
that contains all the constraints
$\{R_{S_1} , \ldots, R_{S_{k+i}} \}$.
If this were
not the case, each subset $A_j$ would be missing some member,
say $R'_{S'_j}$, which means that the
partial tuple \={x'} = $\Pi_A$(\={x}), $A = \bigcup_{i=1}^k S'_i -\{x_t\}$,
is locally consistent,
namely it belongs to $\rho_A$, but it cannot be consistently
extended to a value of $x_t$ while satisfying
the $k$ relations
$R'_{S'_1}, \ldots,R'_{S'_k} $.
This leads to a contradiction because
as a subset of \={x}, \={x'} is locally consistent, and
from the assumption of relational $k$-consistency, this tuple
should be extensible by any additional variable including
$x_t$.
$\Box$
\end{proof}
Since the domains do not increase by extended $k$-composition we get:
\begin{theorem}\label{domain-sizes}
Any $k$-valued network ${\cal R}$
can be globally solved by $DRC_k$.
\end{theorem}
\addtocounter{example}{1}
{\bf Example \theexample.} From Theorem \ref{domain-sizes},
bi-valued networks can be globally solved by $DRC_2$.
In particular,
propositional {\em CNF}s can be globally solved by
$DRC_2$.
As we have seen, in this case, the operator
of extended 2-composition takes the form
of pair-wise resolution yielding algorithm directional
resolution \cite{DeRi94}.
\subsection{Acyclic and causal networks vs. global consistency}
Relational consistency and the $DRC_m$
algorithms can also easily capture the tractable classes of acyclic
and causal networks. It is well known that acyclic networks are
tractable \cite{Maier83,DePe89}.
%ppp
\begin{definition}[acyclic,causal-theories]
Here I should putthe definition
\end{definition}
%ppp
\begin{lemma}
If a network is acyclic then there exists an ordering of
the variables for which each bucket has a single relation.
\end{lemma}
Single-bucket networks contain the class of acyclic networks and
causal networks. It was shown in \cite{DePe91} that
it is possible to discover an ordering of the variables for
which each bucket contains a single relation, whenever such an
ordering exist. We conclude:
\begin{theorem}
Single-bucket networks that are closed under $DRC_1$ are tractable.
\end{theorem}
A special class of relations called {\em causal} \cite{DePe91},
have the property that their projection on any subset
of variables generate a universal relation. Such relations
are closed under $DRC_1$. Propositional
clauses as well as linear inequalities are causal by that
definition. Therefore, single-bucket {\em CNF} theories and linear
inequalities can be solved by $DRC_1$.
\section{Discussion}
The algorithms we presented in this paper belong to the class of
variable elimination algorithms, presented in the framework of what we
call {\em bucket elimination}. Such algorithms
generalize non-serial dynamic programming \cite{bertele}.
We have recently shown that a collection of probabilistic and
combinatorial optimization tasks can be formulated within
this framework \cite{bucket96}. Such algorithms were also presented for various
graph-based tasks by \cite{Arnborg85,ACP89}.
All the algorithms posses similar properties of compiling a theory into
a backtrack-free one (or greedy) and their complexity is dependent
on the same graph properties. Specifically they all have a complexity
bound which is exponential in the induced-width of some graph.
A propety of these algorithms, often overlooked,
is that they also require
space exponential in the induced width. This is a serious
barrier on their real practical application. We have recently
demonstrated how a method of conditioning can be incorporated
into the bucket-elimination framework to allow trading space
for time. The special case-handling of singleton values
that we had introduced permits this extension \cite{time-space}
and therefore such a combination is is applicable t any of the
algorithms we introduced.
Finally, Since all these algorithms may be quite time demanding unless
the problem is very sparse, practical applications call for the use
of approximation algorithms.
The polynomial approximation algorithms that we introduced,
such as $DRC_{(i,m)}$ may be extended to optimization and probabilistic
inference as well.
\section{Conclusions}
We focused on a new definion of local consistency
called {\em relational consistency}. This definition is
relational-based, in contrast with previous definition which
were variable-based.
We presented algorithms,
({\em Directional Relational Consistency ($DRC_m$)}), enforcing
relational consistency, using a general composition operator.
The new operator unifies known elimination opertors
such as resolution for $CNF$ theories,
variable elimination in linear inequalities and the project-join
operator in relational databases.
We also show that relational consistency is usefull in
characterizing relationships between
properties of constraint networks
and the level of local consistency needed to ensure
global consistency.
Specifically, we have shown that different levels of $DRC$ can globally
solve different classes of constraint networks:
\begin{enumerate}
\item $DRC_1$ globally solves acyclic and single-bucket,
causal relations in polynomial time.
It solves (not globally solves) Horn {\em CNF} theories.
\item $DRC_2$ globally solves
bi-valued domain networks,
crossword puzzles,
and linear inequalities over finite subsets of the integers.
The algorithm is polynomial for binary constraints over finite
domains in relational form, and can be exponential otherwise.
Algorithm $DLE$ is a linear elimination algorithm that
approximates $DRC_2$ over integers.
The resolution algorithm of Davis-Putnam is equivalent to $DRC_2$.
\item Algorithm $DRC_m$ globally solves $m$-valued networks.
The algorithm is polynomial for binary constraints.
\item Algorithm $ARC$ globally solves all networks and is exponential.
\item The complexity of both $DRC_m$ and $ARC$ is exponentially
bounded by $w^*$, the tree-width of the network over finite domains.
%ppp
\item We introduced a class of bounded directional
relational consistency algorithms $DRC_{(i,m)}$ that
approximate $DRC_m$ which are polynomial. The algorithms
are complete when $i \ge w*(o)$.
\end{enumerate}
All the algorithms we presented belongs to the family of variable
elimination algorithms that are widely applicable to
deterministic reasoning tasks, to optimization problems and to
probabilistic inference.
%ppp
\paragraph{Acknowledgement.}
We would like to thank Simon Kasif for mentioning Fourier's
elimination algorithm to us. This work was partially supported by
NSF grant IRI-9157636, By the electrical Power Research
institute (EPRI) and by grants from Xerox, Northrop and Rockwell.
This work was also supported in part by the Natural Sciences
and Engineering Research Council of Canada.
%\bibliography{/usr/gibbons/prof/vanbeek/lib/bibliographies/temporal}
%\bibliographystyle{plain}
\begin{thebibliography}{10}
\bibitem{Arnborg85}
S.~Arnborg.
\newblock Efficient algorithms for combinatorial problems on graphs with
bounded decomposability --- a survey.
\newblock {\em BIT}, 25:2--23, 1985.
\bibitem{ACP87}
S.~Arnborg, D.~G. Corneil, and A.~Proskurowski.
\newblock Complexity of finding an embedding in k-trees.
\newblock {\em SIAM Journal of Algebraic Discrete Methods}, 8:177--184, 1987.
\bibitem{ACP89}
S.~Arnborg, and A.~Proskurowski.
\newblock Linear time algorithms for NP-hard problems restricted to partial k-trees.
\newblock {\em Discrete and applied Mathematics} 23 (1989) 11-24.
\bibitem{BFMY83}
C.~Beeri, R.~Fagin, D.~Maier, and M.~Yannakakis.
\newblock On the desirability of acyclic database schemes.
\newblock {\em J. ACM}, 30:479--513, 1983.
\bibitem{bertele}
U. Bertele and F. Brioschi.
\newblock {\em Nonserial Dynamic Programming}, Academic Press,
New York, 1972.
\bibitem{Cooper89}
M.~C. Cooper.
\newblock An optimal k-consistency algorithm.
\newblock {\em Artif. Intell.}, 41:89--95, 1989.
\bibitem{DaPu60}
M.~Davis and H.~Putnam.
\newblock A computing procedure for quantification theory.
\newblock {\em J. ACM}, 7:201--215, 1960.
\bibitem{Dechter90}
R.~Dechter.
\newblock Enhancement schemes for constraint processing incorporating,
backjumping, learning and cutset decomposition.
\newblock {\em Artif. Intell.}, 41:273--312, 1990.
\bibitem{Dechter92}
R.~Dechter.
\newblock From local to global consistency.
\newblock {\em Artif. Intell.}, 55:87--107, 1992.
\bibitem{DMP91}
R.~Dechter, I.~Meiri, and J.~Pearl.
Temporal constraint networks.
{\em Artif. Intell.}, 49:61--95, 1991.
\bibitem{DePe88}
R.~Dechter and J.~Pearl.
\newblock Network-based heuristics for constraint satisfaction problems.
\newblock {\em Artif. Intell.}, 34:1--38, 1988.
\bibitem{DePe89}
R.~Dechter and J.~Pearl.
\newblock Tree clustering for constraint networks.
\newblock {\em Artif. Intell.}, 38:353--366, 1989.
\bibitem{DePe91}
R.~Dechter and J.~Pearl.
\newblock Directed constraint networks: A relational framework for causal
modeling.
\newblock In {\em Proc. of the 12th Int'l Joint Conf. on AI},
pages 1164--1170, 1991.
\bibitem{DeRi94}
R.~Dechter and I.~Rish.
\newblock Directional resolution: The {D}avis-{P}utnam procedure, revisited.
\newblock In {\em Proc. of the 4th Int'l Conf. on
Principles of KR\&R}, 134--145, 1994.
\bibitem{bucket96}
R. Dechter.
\newblock Bucket elimination: a unifying framework for probabilistic
inference.
\newblock In {\em Proceedings of Uncertainty in Artificial Intelligence
(UAI-96)}, 1996.
\bibitem{time-space}
R. Dechter.
\newblock Topological properties of time-space tradeoff.
\newblock In {\em Proceedings of Uncertainty in Artificial Intelligence
(UAI-96)}, 1996.
%\bibitem{fourier} Fourier J.B.J, reportend in: Analyse des travaux
%de l'Academie Royale des Sciences, Pendant l'annee 1824, Partie
%mathematique, Histoire de l'Academie Royale des Sciences de l'Institut
%de France 7 (1827) xlvii-lv. (Partial English translation in:
%D.A. Kohler, Translation of a report by Fourier on his work on
%Linear Inequalities, Opsearch 10 (1973) 38-42.
\bibitem{naor}
D. S. Hochbaum and J. Naor,
\newblock Simple and Fast algorithms for linear integer
programs with two variables per inequality.
\newblock {\em SIAM J. of Computing} 23:6:1179-1192, 1994.
\bibitem{Freuder78}
E.~C. Freuder.
\newblock Synthesizing constraint expressions.
\newblock {\em Comm. ACM}, 21:958--966, 1978.
\bibitem{Freuder82}
E.~C. Freuder.
\newblock A sufficient condition for backtrack-free search.
\newblock {\em J. ACM}, 29:24--32, 1982.
\bibitem{GFHT90}
M.~L. Ginsberg, M.~Frank, M.~P. Halpin, and M.~C. Torrance.
\newblock Search lessons learned from crossword puzzles.
\newblock In {\em Proc. of the 8th Nat'l Conf. on AI},
pages 210--215, 1990.
\bibitem{Jegou93b}
P.~J\'egou.
\newblock On the consistency of general constraint satisfaction problems.
\newblock In {\em Proc. of the 11th National Conf. on AI},
pages 114--119, 1993.
\bibitem{cooper94}
M.C. Cooper, D,A, Cohen and P.G. Jeavons.
\newblock Characterizing tractable constraints
\newblock {\em Artificial Intelligence} 65, 347-361, 1994.
\bibitem{kanelakis92}
P.C. Kanellakis, G.M. Kuper and P. Z. Revesz.
\newblock Constraint Query languages.
\newblock Proc. 9th ACM PODS, 299-313, 1990.
\bibitem{kanelakis90}
P. Kanellakis, {\em Elements of Relational Database Theory},
Handbook of Theoretical Computer Science, Chapter 17,
Vol, B, J. van Leeuwen editor, North-Holland, 1990.
\bibitem{Kirousis93}
L.~M. Kirousis.
\newblock Fast parallel constraint satisfaction.
\newblock {\em Artif. Intell.}, 64:147--160, 1993.
\bibitem{lag85} J. C. Lagarias, ``The computational complexity of
simultaneous Diophantine approximation problems'' {\em SIAM
Journal on Computing}, Vol 14, No. 1 (1985), pp. 196-209.
\bibitem{lassez} J-L Lassez and M. Mahler, ``On Fourier's algorithm
for linear constraints'' {\em Journal of Automated Reasoning}, Vol 9,
1992.
\bibitem{Mackworth77}
A.~K. Mackworth.
\newblock Consistency in networks of relations.
\newblock {\em Artif. Intell.}, 8:99--118, 1977.
\bibitem{Mackworth77b}
A.~K. Mackworth.
\newblock On reading sketch maps.
\newblock {\em International joint conference on Artificial Intelligence(IJCAI-77)}, Cambridge, Mass. 1977, pp. 587-606.
\bibitem{MaFr85}
A.~K. Mackworth and E.~C. Freuder.~The complexity of some
polynomial network consistency algorithms for constraint
satisfaction problems.~{\em Artif. Intell.}, 25:65--74, 1985.
\bibitem{Maier83}
D.~Maier.
\newblock {\em The Theory of Relational Databases}.
\newblock Computer Science Press, 1983.
\bibitem{Montanari74}
U.~Montanari.
\newblock Networks of constraints: Fundamental properties and applications to
picture processing.
\newblock {\em Inform. Sci.}, 7:95--132, 1974.
\shrink{
\bibitem{Nadel89}
B.~A. Nadel.
\newblock Constraint satisfaction algorithms.
\newblock {\em Comput. Intell.}, 5:188--224, 1989.
}
\bibitem{Ullman88}
J.~D. Ullman.
\newblock {\em Principles of Database and Knowledge-Base Systems, Vol. 1}.
\newblock Computer Science Press, 1988.
\bibitem{vanBeek92b}
P.~van Beek.
\newblock On the minimality and decomposability of constraint networks.
\newblock In {\em Proc. of the 10th National Conf. on AI},
pages 447--452, 1992.
\bibitem{vanBeek94}
P.~van Beek.
\newblock On the inherent level of local consistency in constraint networks.
\newblock In {\em Proc. of the 12th National Conf. on AI},
pages 368--373, 1994.
\bibitem{vBDe94b}
P.~van Beek and R.~Dechter.
\newblock Constraint tightness versus global consistency.
\newblock In {\em Proc. of the 4th Int'l Conf. on
Principles of KR\&R}, pages 572--582, 1994.
\bibitem{vBDe94a}
P.~van Beek and R.~Dechter.
\newblock On the minimality and global consistency of row-convex constraint
networks.
\newblock {\em Journal of the ACM}, 42:543-561, 1995.
\bibitem{VHDT92}
P.~Van~Hentenryck, Y.~Deville, and C.-M. Teng.
\newblock A generic arc consistency algorithm and its specializations.
\newblock {\em Artif. Intell.}, 57:291--321, 1992.
\shrink{
\bibitem{ViKa86}
M.~Vilain and H.~Kautz.
\newblock Constraint propagation algorithms for temporal reasoning.
\newblock In {\em Proc. of the 5th National Conf. on AI},
pages 377--382, 1986.
}
%\bibitem{Waltz75}
%D.~Waltz.
%\newblock Understanding line drawings of scenes with shadows.
%\newblock In P.~H. Winston, editor, {\em The Psychology of Computer Vision},
%pages 19--91. McGraw-Hill, 1975.
\end{thebibliography}
\end{document}