Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


3. PROGRAMMING WITH A CONSTRAINT STORE

3.1. PRIMITIVE CONSTRAINTS

The traditional model of a computer store admits only two possible states for a variable: assigned or unassigned. Constraint programming uses a generalization of this model. A so-called constraint store can hold partial information about a variable, expressed as constraints on the variable. In this model, an unassigned variable is an unconstrained variable. An assigned variable is maximally constrained: no further nonredundant constraints can be imposed on the variable, without introducing an inconsistency.

Primitive constraints are the constraints that can be held in the constraint store. The simplest constraint store is the ordinary single-assignment store used in functional programming. In our terms, it is a constraint store in which all constraints have the form Variable = Value.

The first generalization is the introduction of the logical variable. This allows information of the form Variable = Term to be stored, where Term is any term in first-order logic. For example it is possible to store X = f(Y). The same representation can be used to store partial information about X. Thus, if nothing is known about the argument of f, we can store X = f(_). This is the model used in logic programming, and in particular by Prolog.

The storage model used by logic programming has a weakness, however. This is best illustrated by a simple example. The equation X - 3 = Y + 5 is rejected because logic programming does not associate any meaning with - or + in such an equation.

The extension of logic programming to store equations involving mathematical functions was an important breakthrough. Equations involving mathematical functions are passed to the constraint store, and checked by a specialized solver. In fact, not only (linear) equations but also inequations can be checked for consistency by standard mathematical techniques. It is necessary, each time a new equation or inequation is encountered, to check it against the complete set of equations encountered so far.

Linear equations and inequations are examples of primitive constraints. Thus, we have an example of a constraint store. Further constraint stores can be built for different classes of primitive constraints, by designing constraint solvers specifically for those classes of constraints.

We use the term storage model, rather than data model, because the facility to store constraints is independent of the choice of data model -- object-oriented, temporal, etc. On the other hand, the term storage model as used here does not refer to any physical representation of the stored information.

Definition: A constraint store is a storage model that admits primitive constraints of a specific class. Each new primitive constraint that is added to the store is automatically checked for consistency with the currently stored constraints.

This definition of a constraint store specifies an equivalent operation to writing to a traditional store. However, no equivalent to the read statement is specified. There are two important facilites useful for extracting information from a constraint store.

First, it is useful to retrieve all those constraints that involve a given variable, or set of variables. For example, if the constraint store held three constraints X [greater than or equal to] Z, Y [greater than or equal to] X, W [greater than or equal to] Z, the constraints involving X would be Y [greater than or equal to] X and X [greater than or equal to] Z. However, retrieving only constraints explicitly involving a variable may not give a full picture of the entailed constraints on the variable. For example, the store X [greater than or equal to] Y, Y [greater than or equal to] Z entails X [greater than or equal to] Z. The mechanism necessary to return all the constraints and entailed constraints on a given variable or set of variables is termed projection. A very useful property of a class of primitive constraints is the property that the projection of a set of primitive constraints on a given variable, or set of variables, is also expressible as a set of primitive constraints. If the primitive constraints have this property, it is possible, for example, to drop a variable from the constraint store when it is no longer relevant. This is the equivalent to reclaiming the store associated with a variable in a traditional programming language when the variable passes out of scope.

Second, it is useful to retrieve particular kinds of entailed constraints from a constraint store. For example, it is very useful to know when a constraint store entails that a particular variable has a fixed value. For example, the constraint store $X [greater than or equal to] Y, Y [greater than or equal to] 3, 3 [greater than or equal to] X, entails that both X and Y have the value 3.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.