Finite Entailment of Local Queries in the Z Family of Description Logics

Bartosz Bednarczyk, Emanuel KieronskiAAAI 2022 · DOI

Introduction

Description Logics (DLs) serve as the formal foundation for knowledge representation systems, most notably the Semantic Web's OWL 2 standard. Traditionally, reasoning in DLs assumes "classical semantics," where entailment is checked against all possible models, including those with infinite domains. However, in database applications, data is inherently finite. This discrepancy leads to the "finite entailment" problem: determining if a query holds across all finite models of a knowledge base (KB).

This paper addresses this challenge for the $\mathcal{Z}$ family of DLs. These logics are highly expressive, incorporating features like regular expressions in roles, nominals, and number restrictions, placing them at the boundary of decidability.

Syntax and semantics of the $\mathcal{Z}$ family operators.

The Challenge of Finite Query Entailment

Finite query entailment is notoriously difficult because some logical statements may be valid in all finite models but fail when infinite models are permitted. For expressive DLs, the finite model property—where a KB is satisfiable if and only if it has a finite model—often fails. The authors focus on "local queries" (Positive Boolean Combinations of Conjunctive Queries where variables are clustered), investigating whether reasoning over finite models is computationally harder than the unrestricted case.

Methodological Framework

The researchers employed two distinct theoretical strategies based on the specific logic within the $\mathcal{Z}$ family:

1. Finite Controllability for $\mathcal{ZOQ}$ and $\mathcal{ZOI}$

For the logics $\mathcal{ZOQ}$ (nominals and qualified number restrictions) and $\mathcal{ZOI}$ (nominals and inverse roles), the authors proved "finite controllability." This property ensures that for local queries, entailment over finite models coincides with entailment over all models.

To prove this, they developed a sophisticated finite model construction technique. The process begins with an infinite "quasi-forest" model. The authors identify recurring finite patterns, termed components, and "stitch" them together to form a large but finite model. This constructed model preserves the truth of the KB while simultaneously avoiding the query, thereby proving that if a query is not entailed in the unrestricted case, a finite countermodel exists.

Illustration of the model construction process, stitching together components to form a finite model.

2. Reduction to Finite Satisfiability for $\mathcal{ZIQ}$

The logic $\mathcal{ZIQ}$ (inverse roles and qualified number restrictions) lacks the finite model property, making the "stitching" approach inapplicable. Instead, the authors utilized the property of being "locally of treewidth-one" (ltw1). They established a generic reduction that transforms the problem of finite query entailment into the problem of finite Knowledge Base Satisfiability (KBSat). This reduction implies that if one can determine whether a $\mathcal{ZIQ}$ KB has any finite model, one can also solve the finite query entailment problem.

Key Insights and Results

The research yields several critical insights for the KR community:

  • Complexity Parity: For $\mathcal{ZOQ}$ and $\mathcal{ZOI}$, finite entailment of local queries is 2EXPTIME-complete, matching the complexity of the unrestricted case. This allows the adaptation of existing optimized algorithms for finite-domain applications.
  • Automaton Roles: The use of "automaton roles"—where roles are defined by regular languages—allows for complex path-based constraints. The authors demonstrated how these constraints can be maintained within finite model constructions.
  • Unification of Results: By addressing the high-level $\mathcal{Z}$ family, the paper provides a unified framework that encompasses and extends results for simpler sublogics like $\mathcal{ALC}$.

Conclusion and Future Directions

While this work bridges a significant gap, the finite satisfiability of $\mathcal{ZIQ}$ and $\mathcal{ZOIQ}$ remains an open question. The reduction provided for $\mathcal{ZIQ}$ sets the stage for future proofs of decidability. Additionally, extending these results to non-local queries, such as regular path queries, remains a challenge, as these often push expressive logics into the realm of undecidability.

Summary updated

BibTeX
@inproceedings{bednarczyk2022finite,
  author = {Bartosz Bednarczyk and Emanuel Kieronski},
  title = {{Finite Entailment of Local Queries in the Z Family of Description Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20487},
}
Figure