Constraint satisfaction with an object-oriented knowledge representation language (Q1330407)

This article presents constraint satisfaction in the hybrid language LAURE. It is deductive using rules which can be processed top-down (recursive query processing) also bottom-up (production rules). Constraints, rules and methods (procedural code) can be combined. This makes it an extensible constraint solver where rules and methods can be used to guide constraint resolution. LAURE comprises 100,000 lines of C code, is designed for large applications with up to 100,000 objects, and is coupled with an object-oriented or relational database. The concept of virtual memory in UNIX is used to store all objects which must be made available for constraint resolution at run-time, respectively. Emphasis is put on applications and practical use of constraint satisfaction in LAURE Section 2 shows two examples which have been implemented with LAURE. The first example shows the link between objects and constraints for a user interface management system. The second problem is a time-constrained traveling salesman problem with distances between nodes and a time window for each node. The LAURE code for the Hamiltonian circuit and for additional constraints is sketched. Section 3 gives an overview of objects and attached constraints in LAURE by a more practical perspective. Objects are nodes in a large semantic network, mono- or multivalued logic relations between nodes can be defined by rules or constraints. The set of logical relations is organized into a set of layers. Constraints are defined on objects from a given set and restrict the values of certain logic relations. Production rules, negative constraints and dependencies within a calculus of relational algebra are discussed. Relaxation paths support the specification of distances between solutions. Section 4 presents constraint resolution more theoretically. The resolution strategy uses a domain-reduction technique which is based on abstract interpretation. The concept of solution querying is discussed and techniques for reactive resolution are demonstrated. The reasoning concept is based on the notation of so-called worlds. Section 5 describes the data structures for these worlds. Using relational algebra the LAURE implementation of large relations and object worlds, translations and object operators, domain reduction and abstract interpretation are discussed. In the last section various aspects of performance and comparisons to other approaches of constraint satisfaction are pointed out. Both, for the theoretical treatment of problem complexity and for practical software engineering aspects, the flexibility of such a high-level hybrid language must be emphasized with respect to other families of implemented systems.