Well-Founded Operators for Normal Hybrid MKNF Knowledge Bases

Jianmin Ji, Fangfang Liu, Jia-Huai You

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:

  1. 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.
  2. 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

Abstract

Hybrid MKNF knowledge bases have been considered one of the dominant approaches to combining open world ontology languages with closed world rule-based languages. Currently, the only known inference methods are based on the approach of guess-and-verify, while most modern SAT/ASP solvers are built under the DPLL architecture. The central impediment here is that it is not clear what constitutes a constraint propagator, a key component employed in any DPLL-based solver. In this paper, we address this problem by formulating the notion of unfounded sets for non-disjunctive hybrid MKNF knowledge bases, based on which we propose and study two new well-founded operators. We show that by employing a well-founded operator as a constraint propagator, a sound and complete DPLL search engine can be readily defined. We compare our approach with the operator based on the alternating fixpoint construction by Knorr et al. (2011. Artificial Intelligence 175, 9, 1528–1554) and show that, when applied to arbitrary partial partitions, the new well-founded operators not only propagate more truth values but also circumvent the non-converging behavior of the latter. In addition, we study the possibility of simplifying a given hybrid MKNF knowledge base by employing a well-founded operator and show that, out of the two operators proposed in this paper, the weaker one can be applied for this purpose and the stronger one cannot. These observations are useful in implementing a grounder for hybrid MKNF knowledge bases, which can be applied before the computation of MKNF models.
BibTeX
@inproceedings{ji2017well,
  author = {Jianmin Ji and Fangfang Liu and Jia-Huai You},
  title = {{Well-Founded Operators for Normal Hybrid MKNF Knowledge Bases}},
  booktitle = {Theory Pract. Log. Program},
  year = {2017},
  url = {https://openreview.net/forum?id=WxzLNF1T7ov},
}
Figure