Bounded Predicates in Description Logics with Counting

Sanja Lukumbuzya, Mantas SimkusIJCAI 2021 · DOI

TL;DR

This paper tackles the computational challenges posed by "anonymous objects" in expressive Description Logics (DLs) by introducing the concept of "bounded predicates." They develop a novel integer programming-based approach to determine if the number of anonymous objects associated with a predicate is guaranteed to be finite, even without knowing the specific data. This work pushes the boundaries of decidability for complex ontology reasoning and enables new, safer ways to query these ontologies.

What Problem Does This Paper Address?

Knowledge Representation and Reasoning (KR&R) systems, particularly those using Description Logics (DLs), are crucial for intelligent data management. DLs allow us to describe complex domains using ontologies. A key feature of DLs is their ability to handle "anonymous objects" – entities that are not explicitly named but whose existence is implied by the ontology. While powerful, these anonymous objects can lead to significant computational complexity and even undecidability for reasoning tasks, especially when dealing with recursive structures or complex queries. This paper focuses on a specific type of DL, ALCHOIQ, extended with "closed predicates" (essentially, master data). The core problem is to understand when and how we can guarantee that the number of anonymous objects related to certain predicates remains bounded, independent of the actual data instances. This boundedness is crucial for ensuring decidability of reasoning and for developing practical query answering mechanisms.

Methods

The paper introduces a procedure based on integer programming to decide the existence of upper bounds on predicate sizes. This method works by reformulating the problem into checking finite-infinite satisfiability (fi-satisfiability), which determines if a TBox has a model where specific predicates are finite and others are infinite.

Key methodological contributions include:

  • Formalizing Boundedness: Defining both "weak boundedness" (boundedness for a specific knowledge base instance) and "strong boundedness" (boundedness independent of the ABox, relying only on the TBox and closed predicates).
  • Reduction to Fi-Satisfiability: Demonstrating that checking strong boundedness can be reduced to fi-satisfiability.
  • Integer Programming for Fi-Satisfiability: Developing a technique to encode fi-satisfiability problems into systems of linear inequalities with side conditions, solvable via integer programming. This involves defining "tiles" to represent domain elements and their neighborhoods.
  • Enriched Systems and Enriched ILPs: Extending integer programming to "enriched systems" and "enriched integer linear programs" to handle potentially infinite solutions and to compute bounds.
  • Safety Condition for Queries: Leveraging the concept of bounded predicates to define a new, decidability-ensuring "safety condition" for Datalog-based queries over DL ontologies, relaxing the strict DL-safety requirement.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Boundedness as a Decidability Enabler: The central insight is that guaranteeing boundedness of predicates is key to regaining decidability for complex reasoning tasks in expressive DLs, particularly for query answering.
  • Bridging Data-Independent and Data-Dependent Reasoning: The paper elegantly bridges the gap between reasoning about the ontology structure itself (data-independent) and reasoning about specific data instances (data-dependent). Strong boundedness is data-independent, while weak boundedness is data-dependent.
  • Integer Programming as a Powerful Tool: The paper showcases the power of integer programming as a formal tool for tackling complex reasoning problems in DLs, transforming logical constraints into numerical ones.
  • New Safety Condition for Queries: The proposed safety condition for ontology-mediated queries (OMQs) is a significant practical contribution, allowing for more expressive queries over anonymous objects without sacrificing decidability.

Key Results

  • NEXPTIME-completeness for Fi-Satisfiability: The fi-satisfiability problem for ALCHOIQ is shown to be NEXPTIME-complete.
  • CONEXPTIME-completeness for Boundedness: Both strong and weak boundedness for ALCHOIQ are proven to be CONEXPTIME-complete.
  • Doubly Exponential Bounds: The paper provides a method to compute an upper bound on the size of bounded predicate extensions, which is doubly exponential in the size of the TBox but polynomial in the size of the ABox.
  • CO2NEXPTIME-completeness for Safe OMQs: The entailment problem for the newly defined "safe OMQs" is CO2NEXPTIME-complete.
  • CONP-completeness for Data Complexity: The data complexity of satisfiability for ALCHOIQ KBs with closed predicates is found to be CONP-complete.

Limitations and Future Work

  • Computational Complexity: While decidability is achieved, the complexity bounds (NEXPTIME, CONEXPTIME) are high, indicating that practical implementations might still face challenges for very large ontologies. The authors acknowledge that explicitly building the integer programming systems is computationally expensive.
  • Approximation for Efficiency: Future work could explore efficient approximations for predicate boundedness by considering smaller systems of inequalities.
  • Role Predicates: While the paper discusses how to handle role predicates by converting them to concept predicates, the core analysis focuses on concept names. Further investigation into the direct handling of role boundedness might be beneficial.
  • Verification of Temporal Properties: The authors suggest that their techniques could be applied to identify state-bounded systems for verifying temporal properties of evolving graph databases.

Summary updated

BibTeX
@inproceedings{lukumbuzya2021bounded,
  author = {Sanja Lukumbuzya and Mantas Simkus},
  title = {{Bounded Predicates in Description Logics with Counting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/271},
}

Loading related content...

Figure