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.