Finite Entailment of Local Queries in the Z Family of Description Logics
Bartosz Bednarczyk, Emanuel Kieronski
Abstract
In the last few years the field of logic-based knowledge representation took a lot of inspiration from database theory. A vital example is that the finite model semantics in description logics (DLs) is reconsidered as a desirable alternative to the classical one and that query entailment has replaced knowledge-base satisfiability (KBSat) checking as the key inference problem. However, despite the considerable effort, the overall picture concerning finite query answering in DLs is still incomplete. In this work we study the complexity of finite entailment of local queries (conjunctive queries and positive boolean combinations thereof) in the Z family of DLs, one of the most powerful KR formalisms, lying on the verge of decidability. Our main result is that the DLs ZOQ and ZOI are finitely controllable, i.e. that their finite and unrestricted entailment problems for local queries coincide. This allows us to reuse recently established upper bounds on querying these logics under the classical semantics. While we will not solve finite query entailment for the third main logic in the Z family, ZIQ, we provide a generic reduction from the finite entailment problem to the finite KBSat problem, working for ZIQ and some of its sublogics. Our proofs unify and solidify previously established results on finite satisfiability and finite query entailment for many known DLs.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 2765a789-bd81-48df-9791-b7f82802a7d4Related papers
- Stable Model Semantics for Description Logic TerminologiesFederica Di Stefano, Mantas SimkusAAAI 2024 · 5 citations
- The Price of Selfishness: Conjunctive Query Entailment for ALCSelf Is 2EXPTIME-HardBartosz Bednarczyk, Sebastian RudolphAAAI 2022 · 1 citation
- Data Complexity of Querying Description Logic Knowledge Bases Under Cost-Based SemanticsMeghyn Bienvenu, Quentin ManièreAAAI 2026 · 1 citation
- Query Optimization for Ontology-Mediated Query AnsweringWafaa El Husseini, Cheikh Brahim El Vaigh, François Goasdoué, Hélène JaudoinWWW 2024 · 5 citations
- Spectra of Cardinality Queries over Description Logic Knowledge BasesQuentin Manière, Marcin PrzybylkoAAAI 2025 · 1 citation
