Querying Circumscribed Description Logic Knowledge Bases
Circumscription is one of the main approaches for defining non-monotonic description logics (DLs). While the decidability and complexity of traditional reasoning tasks such as satisfiability of circumscribed DL knowledge bases (KBs) is well understood, for evaluating conjunctive queries (CQs) and unions thereof (UCQs), not even decidability had been established. In this paper, we prove decidability of (U)CQ evaluation on circumscribed DL KBs and obtain a rather complete picture of both the combined complexity and the data complexity, for DLs ranging from ALCHIO via EL to various versions of DL-Lite. We also study the much simpler atomic queries (AQs).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases
In this paper, we explore a quantitative approach to querying inconsistent description logic knowledge bases. We consider weighted knowledge bases in which both axioms and assertions have (possibly infinite) weights, whi…
On the Non-Monotonic Description Logic $\mathcal{ALC}$+T$_{\mathsf{min}}$
In the last 20 years many proposals have been made to incorporate non-monotonic reasoning into description logics, ranging from approaches based on default logic and circumscription to those based on preferential semanti…
BlockingAdding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
We study extensions of expressive decidable fragments of first-order logic with circumscription, in particular the two-variable fragment FO$^2$, its extension C$^2$ with counting quantifiers, and the guarded fragment GF.…
SentenceExploiting Uncertainty for Querying Inconsistent Description Logics Knowledge Bases
The necessity to manage inconsistency in Description Logics Knowledge Bases (KBs) has come to the fore with the increasing importance gained by the Semantic Web, where information comes from different sources that consta…
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Description Logics are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries, the standard query language in databases, have recently gained…