Tractable Reasoning and Conjunctive Query Answering for Defeasible DL-Lite under Rational Closure

Giovanni Casini; Umberto Straccia

cs.AIJun 23, 2026

Tractable Reasoning and Conjunctive Query Answering for Defeasible DL-Lite under Rational Closure

Authors: Giovanni Casini, Umberto Straccia

Organizations: CNR - ISTI · University of Cape Town · Istituto di Scienza e Tecnologie dell’Informazione, CNR - ISTI, Pisa, Italy · University of Cape Town and CAIR, Cape Town, South Africa

Abstract

In Description Logics (DLs), reasoning under Rational Closure (RC) is a well-known and widely accepted non-monotonic formalism to handle defeasible knowledge. In this paper, we study the application of RC to the core and horn variants of the DL-Lite family of lightweight description logics. We analyze both entitlement (instance checking) and Conjunctive Query (CQ) answering under RC. Our main contribution is providing a plug-in architecture that builds upon existing standard classical reasoners, establishing that reasoning and CQ answering under RC for DL-Lite can be done efficiently with minimal computational overhead.

Explore similar work

Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)
Jul 18, 2026Lorenzo Marconi, Daniela Rieti, Riccardo RosatiOntology Entailment
A Horn extension of DL-Lite with NL data complexity
May 13, 2026Janos Arpasi, Bartosz Jan Bednarczyk, Magdalena OrtizOntology Complex Query Answering
Towards Non-Monotonic Entailment in Propositional Defeasible Standpoint Logic
Jun 2, 2026Nicholas Leisegang, Thomas Meyer, Ivan VarzniczakModal Logic Entailment

Jul 18, 2026 · cs.AIJ/K move · Enter open · S save

Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)

Lorenzo Marconi, Daniela Rieti, Riccardo Rosati

Sapienza University of Rome, Italy

We study Controlled Query Evaluation (CQE), a declarative approach to confidentiality-preserving data access, in the context of Description Logic (DL) ontologies, and for confidentiality policies expressed through Epistemic Dependencies (EDs). We first address the problem of answering queries (specifically, Boolean unions of conjunctive queries) under known semantics for CQE (GA- and IGA-entailment). Our results show that if the TBox is expressed in

\text{DL-Lite}_{\mathcal{R}}

, CQE is computationally intractable in general. Moreover, in the presence of EDs, the IGA semantics has recently been proven not to satisfy an important confidentiality preservation property known as indistinguishability. With the goal of defining computationally easier and confidentiality-preserving forms of CQE, we introduce a new semantics for CQE, based on the notion of minimal policy violation (MPV). We show that the new semantics provides a sound approximation of the previous ones, while satisfying the indistinguishability property. We also prove that, in the case of

\text{DL-Lite}_{\mathcal{R}}

ontologies, query entailment under the MPV semantics can be decided in polynomial time in data complexity. Finally, we present a software implementation of our framework that we used to evaluate the feasibility of this new approach using an existing benchmark for OWL 2 QL.

Ontology Entailment Complex Query Answering Privacy-Preserving Framework Computable

Open paper Ask about it PDF

Abstract

Explore similar work

Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)

A Horn extension of DL-Lite with NL data complexity

Towards Non-Monotonic Entailment in Propositional Defeasible Standpoint Logic