Abstract
Logic programming systems traditionally rely on depth-first search with chronological backtracking, which can be highly inefficient due to its "blind" nature. This paper presents a method for "Intelligent Control" that utilizes Integrity Constraints (ICs) to prune the search space. By interpreting failures as learned constraints and applying subsumption algorithms, the system can avoid redundant computations and close nodes early. This approach is designed to be independent of execution mode, supporting both sequential and parallel logic programming environments.
Introduction
In the early 1980s, logic programming—exemplified by Prolog—was constrained by a "blind" search strategy: depth-first search with chronological backtracking. When a program encountered a failure, it would simply step back to the most recent choice point and attempt the next alternative. This process is inherently inefficient because the system does not analyze why a failure occurred, often leading it to repeat the same mistakes in different branches of the search tree. Kohli and Minker proposed a more robust mechanism to use domain knowledge and failure analysis to prune the search space dynamically.
Methods: Integrity Constraints as Control
The authors propose using Integrity Constraints (ICs)—logical invariants that must always be true—as a control mechanism. These ICs are categorized into three functional forms: negated data (combinations of facts that can never hold), implications (if one set of facts is true, another must be provable), and functional dependencies (relationships between arguments).
The "Intelligent Control" system operates in two directions:
- Forward Execution: Before expanding a goal, the system checks if it violates any ICs using a linear-time subsumption algorithm. If a goal is "subsumed" by a constraint (i.e., it is a specific instance of a known impossible state), the node is pruned immediately.
- Backward Execution (Failure Analysis): When a literal fails to unify with any clause in the knowledge base, the system treats that failure as an implicit integrity constraint. For example, a failure of
P(a, x)generates a new rule<- P(a, x), which can then be used to prune other branches.
Search Tree Optimization
A key advantage of this method is the ability to "close" nodes early. In standard Prolog, a node is only closed when all alternatives are exhausted. In the proposed system, a node can be closed as soon as ICs prove that no further alternatives will yield a result.
As shown in the search tree above, the system explores various paths (nodes 1-8). By propagating learned constraints, the engine can identify deterministic nodes—where only one possible solution exists—and kill off entire branches before they are even expanded. Because this method relies on the logic of the constraints rather than the state of a stack, it is equally effective for both sequential and parallel execution modes, such as the PRISM system.
Conclusion
The use of Integrity Constraints transforms failure from a dead end into valuable information. By treating failures as learned rules, logic programming systems can move beyond blind backtracking toward a more informed and efficient search. While currently limited to function-free Horn clauses, this framework provides a significant step toward high-performance, intelligent logic inference. Future work will focus on extending these techniques to more complex logic structures and evaluating the overhead of constraint maintenance in large-scale systems.
Summary updated