4.1.2 Constraints

Conceptually, a constraint defines the valid combinations of values
for a set of variables.
A *primitive constraint* is a n-ary predicate that relates a set of *n*
variables by defining the valid combinations of values for
those variables. A primitive constraint is a computable component which
may be implemented by a local table look-up, by the computation of a
local function, by retrieving a set of tuples from a remote wrapper,
or by calling an arbitrary external program.

In the sample network of Figure 8 the constraints
are shown as rounded rectangles. For example, the `computeDuration` constraint
involves three variables (`DepartureDate`, `ReturnDate`, and
`Duration`), and it's implemented by a function that computes the
duration of a trip given the departure and return dates. The
constraint `getParkingRate` is implemented by calling a wrapper
that accesses a web site that contains parking rates for airports in
the USA.

In Heracles, the set of possible values of each variable is determined by a *domain expression*.
The primitive constraints that operate on the same variable are combined to form a domain expression.
The grammar for domain expressions
is:

Exp = (AND Exp Exp) | (OR Exp Exp) | (DLIST Exp Exp ...) | PrimitiveConstraint PrimitiveConstraint = (PREDICATE var1 var2 ... varN)

The semantics of domain expressions is as follows: A conjunction (AND) of domain expressions evaluates to the intersection of the corresponding value sets. A disjunction (OR) evaluates to the union of value sets. A decision list (DLIST) takes the values of the first expression that evaluates to a non-empty value set. A domain expression can also be a primitive constraint and it evaluates to its corresponding possible value set.

For example, in the travel domain we might be able to compute accurate distances for some cities but not for others, which affects the computation of the driving time necessary to get to the airport. If we have a source that geocodes addresses, we can compute an accurate distance and driving time. However, there may be some smaller cities where the data is not available for geocoding. In this case we might want to assume a default value, say half an hour. These two constraints can be combined using a DLIST domain expression so that the system attempts the most accurate method first.

Each variable can also be associated with a preference constraint.
Evaluating the preference constraint over the possible values produces
the *assigned* value of the variable. Preference constraints are
often implemented as functions that impose an ordering on the values
of a domain. Preferences are *soft* constraints because they do
not affect the consistency of the network only the desirability of the
values. An example of a preference in the business travel domain is to
choose a hotel closest to the meeting.