Identifying Bottlenecks in Practical SAT-Based Model Finding for First-Order Logic Ontologies with Datasets

Shirly Stephen, Torsten HahmannAAAI 2019 · DOI

Introduction

In Knowledge Representation, First-Order Logic (FOL) ontologies serve as a robust framework for describing complex domains. A critical task in utilizing these ontologies is "model finding," which involves verifying the logical consistency of a set of facts (an ABox) against the rules defined in the ontology (the TBox). While translating FOL problems into Propositional Satisfiability (SAT) problems is a standard approach, it faces significant scalability challenges. Historically, SAT-based model finding has been restricted to small datasets, typically with fewer than 20 individuals. This paper identifies a primary bottleneck—"optional definitions"—and proposes a method to scale model finding to hundreds of individuals.

Methodology: Addressing Optional Definitions

The researchers investigated the impact of explicit definitions within the TBox, specifically focusing on "optional definitions." These are predicates defined in the TBox that are not utilized by any other rules within the ontology. To mitigate their performance impact, the authors propose a syntactic transformation:

  1. Identification: Locate optional definitions in the TBox.
  2. Substitution: Replace these predicates in the ABox with their corresponding logical formulas (the "definiens").
  3. Removal: Delete the optional definitions from the TBox.

This "defined assertion" approach maintains logical equivalence while reducing the number of predicates the SAT solver must manage. The method was evaluated using the Paradox model finder across 13 syntactic variations of a spatial ontology.

Experimental Setup

The study utilized the CODI (Combined Ontology for 2D Continuity) family, a mid-sized spatial ontology comprising 26 axioms. The ABox was derived from a real-world dataset of lynx habitats in Maine, containing 173 spatial objects and 3,665 assertions. Experimental samples of varying sizes ($I = 40, 60, 80$) were used to assess scalability.

Results and Discussion

The quantitative analysis revealed that the structure of definitions significantly impacts performance, even when logical content remains identical.

Table 1: Performance metrics across 13 TBox variations for different domain sizes (I).

As shown in Table 1, the performance disparity is stark. For a sample size of $I=40$, Case 1 (minimal definitions) required only 7 seconds, whereas Case 13 (including all five optional definitions) took 5,740 seconds. For larger samples ($I=80$), versions with numerous optional definitions frequently timed out (indicated by ~), while the optimized versions found models in under 10 minutes.

The "Arity Trap" explains much of this behavior: an $n$-ary predicate results in $d^n$ propositional variables for $d$ individuals. However, the authors also noted that the structure of the resulting clauses can cause a 1,000x increase in computation time even when the number of variables does not double, indicating that search space complexity is driven by more than just variable count.

Conclusion

The study demonstrates that "unrolling" optional definitions in the dataset is a highly effective preprocessing step. This technique allows SAT-based solvers to handle datasets previously considered computationally infeasible. Future work includes automating this substitution process and exploring its applicability to other logic families, such as Description Logics, and different solver architectures like iProver.

Summary updated

BibTeX
@inproceedings{stephen2019identifying,
  author = {Shirly Stephen and Torsten Hahmann},
  title = {{Identifying Bottlenecks in Practical SAT-Based Model Finding for First-Order Logic Ontologies with Datasets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.330110039},
}
Figure