Abstract
Hybrid MKNF (Minimal Knowledge and Negation as Failure) knowledge bases provide a powerful framework for integrating Description Logics (DL) with Logic Programming (LP). However, reasoning within this framework has traditionally relied on inefficient "guess-and-verify" techniques. This paper addresses this bottleneck by introducing novel well-founded operators based on the extension of unfounded sets to the hybrid MKNF setting. We present two operators, $W_{\mathcal{K}}$ and $E_{\mathcal{K}}$, which function as effective constraint propagators. These operators not only improve pruning during search but also resolve convergence issues found in previous state-of-the-art methods, enabling a more efficient DPLL-style search architecture for hybrid reasoning.
Introduction
In the field of Knowledge Representation, two dominant paradigms often exist in tension: Description Logics (DL), which underpin ontologies and the Semantic Web via the Open World Assumption (OWA), and Logic Programming (LP), which governs rules and databases via the Closed World Assumption (CWA). Hybrid MKNF was developed to merge these paradigms, allowing for sophisticated reasoning that accounts for both known and unknown information.
Despite its expressive power, the practical application of Hybrid MKNF has been hindered by computational performance. Most existing solvers utilize a "guess-and-verify" approach, essentially brute-forcing truth values and checking for consistency post-hoc. This paper proposes a transition toward the DPLL (Davis-Putnam-Logemann-Loveland) architecture—the backbone of modern SAT and Answer Set Programming (ASP) solvers—by developing mathematically sound and computationally efficient "propagators" for hybrid logic.
The Challenge of Hybrid Propagation
The primary difficulty in building a propagator for Hybrid MKNF lies in the interaction between the DL base and the LP rules. To prune a search space effectively, a solver must be able to identify "unfounded sets"—groups of facts that cannot be proven true given current partial knowledge. While well-understood in standard logic programming, extending this concept to a hybrid environment where a DL ontology can also influence truth values is non-trivial.
Previous attempts to define such operators suffered from a significant flaw: they failed to converge when applied to arbitrary partial assignments. This "non-converging behavior" made them unsuitable for the iterative nature of DPLL search engines, where truth values are assigned and retracted dynamically.
Methodology: $W_{\mathcal{K}}$ and $E_{\mathcal{K}}$ Operators
The authors bridge this gap by introducing two new operators designed to identify unfounded atoms and propagate truth values:
- The Well-Founded Operator ($W_{\mathcal{K}}$): This operator utilizes the greatest unfounded set to derive false atoms while using the rules to derive true ones. Crucially, $W_{\mathcal{K}}$ is proven to be stronger than previous operators (such as those proposed by Knorr et al.) and is guaranteed to converge even when starting from a partial assignment. This makes it a reliable tool for simplifying knowledge bases during preprocessing.
- The Expanding Well-Founded Operator ($E_{\mathcal{K}}$): This is a more aggressive version of the operator that incorporates unit propagation—a staple of SAT solving. By inferring more truth values during the search process, $E_{\mathcal{K}}$ acts as a powerful engine for pruning the search tree, though the authors note it must be used carefully during simplification to avoid accidentally removing valid models.
These operators are integrated into a standard DPLL search algorithm (Algorithm 2), providing a formal template for a new generation of hybrid solvers.
Key Insights and Results
The theoretical contributions of this paper are centered on the relationship between unfounded sets and MKNF models:
- Unfounded-Free Models: The authors establish that MKNF models are precisely those that contain no unfounded atoms. This provides a solid theoretical foundation for using unfounded sets as a pruning mechanism.
- Superior Propagation: Mathematical proofs demonstrate that $W_{\mathcal{K}}$ and $E_{\mathcal{K}}$ propagate more truth values than the previous standard-bearer in the field, leading to a more significant reduction in the search space.
- Computational Complexity: Despite the increased power of these operators, they maintain polynomial data complexity (provided the underlying Description Logic is also polynomial). This ensures that the added reasoning power does not introduce an exponential computational overhead.
Conclusion and Future Work
By defining unfounded sets for hybrid MKNF and developing the $W_{\mathcal{K}}$ and $E_{\mathcal{K}}$ operators, this paper provides the necessary components for efficient, DPLL-style hybrid reasoning. While the current work is limited to "normal" hybrid MKNF (excluding disjunctive rules), it sets the stage for significant performance gains in hybrid logic solvers.
Future research directions include extending these operators to disjunctive knowledge bases and incorporating advanced SAT techniques such as conflict-directed backtracking and clause learning (CDCL). These enhancements will be critical for scaling hybrid MKNF reasoning to real-world, large-scale semantic applications.
Summary updated