We summarize our recent work on evaluating (unions of) conjunctive queries on circumscribed versions of description logic ranging from ℒℋℐ via ℰℒ to various versions of DL-Lite [1]. While standard description logics (DLs), such as those underlying the OWL 2 ontology language, do not include non-monotonic features, it is generally acknowledged that extending DLs with such features is very useful. Examples of applications include ontological modeling in the biomedical domain [2, 3] and the formulation of access control policies [4]. Circumscription is one of the traditional AI approaches to non-monotonicity, and it provides an important way to define non-monotonic DLs. In contrast to other approaches, such as default rules, it does not require the adoption of strong syntactic restrictions to preserve decidability. DLs with circumscription are closely related to several other approaches to non-monotonic DLs, in particular to DLs with defeasible inclusions and typicality operators [5, 6, 7, 8, 9]. The main feature of circumscription is that selected predicate symbols can be minimized, that is, the extension of these predicates must be minimal regarding set inclusion. Other predicates may vary freely or be declared fixed. In addition, a preference order can be declared on the minimized predicates. The traditional AI use of circumscription is to introduce and minimize abnormality predicates, which makes it possible to formulate defeasible implications. Circumscription is also closely related to the closure of predicates symbols as studied, for instance, in [10, 11, 12]. While DLs usually assume open-world semantics and represent incomplete knowledge, such closed predicates are interpreted under a closed-world assumption, reflecting that complete knowledge is available regarding those predicates. Circumscription may
Combined
Data be viewed as a soft form of closing concept names: there are no other instances of a minimized concept name except the explicitly asserted ones unless we are forced to introduce (a minimal set of) additional instances to avoid inconsistency.
A primary application of DLs is ontology-mediated querying, where an ontology is used to
enrich data with domain knowledge. Surprisingly, relatively little is known about
ontologymediated querying with DLs that support circumscription. The most popular choice of queries
are conjunctive queries (CQs) and unions thereof (UCQs), and to the best of our knowledge, in
this case not even decidability is known. In [
One of our main results is that UCQ evaluation is decidable in all these DLs when circumscription
is added, a summary of the complexities can be found in Table 1. It is 2Exp-complete in ℒℋℐ
w.r.t. combined complexity, and thus not harder than query evaluation without circumscription.
W.r.t. data complexity, there is a significant increase from coNP- to Π 2P-completeness. For
ℰ ℒ, both combined and data complexity turns out to be identical to that of ℒℋℐ, which
improves lower bounds from [
We also study the evaluation of the basic yet important atomic queries (AQs), conjunctive queries of the form () with a concept name. Also here, we obtain a rather complete picture of the complexity landscape. It is known from [13] that AQ evaluation in ℒℋℐ is coNExpNP-complete w.r.t. combined complexity. We show that the lower bound holds already for ℰ ℒ. Moreover, our Π 2P-lower bound for the data complexity of (U)CQ-evaluation in ℰ ℒ mentioned above only requires an AQ, and thus AQ evaluation in both ℒℋℐ and ℰ ℒ are Π 2P-complete w.r.t. data complexity. For DL-Lite, the data complexity drops to PTime in all considered versions, and the combined complexity ranges from coNExp- to Π 2P-complete, depending on which Boolean operators are admitted. A summary can be found in Table 2.
We highlight a key-ingredient that underlies the obtained decidability results and upper complexity bounds. Recall that an ℒℐ concept is built according to the rule , ::= ⊤ | | {} | ¬ | ⊓ | ∃. where ranges over concept names, over individual names, and over (possibly inverse) roles. An ℒℋℐ knowledge base (KB) takes the form = ( , ) with and being an ℒℋℐ TBox and ABox, defined in the standard way. The set of individual names used in is denoted ind(). The semantics is defined as usual in terms of interpretations, we refer to [14] for full details.
A circumscription pattern is a tuple CP = (≺ , M, F, V), where ≺ is a strict partial order on M called the preference relation, and M, F and V are a partition of the set of all concept names. The elements of M, F and V are the minimized, fixed and varying concept names. Role names always vary to avoid undecidability [13]. The preference relation ≺ on M induces a preference relation <CP on interpretations by setting <CP ℐ if the following conditions hold: 2. for all ∈ F, = ℐ , 3. for all ∈ M with ̸⊆ ℐ , there is a ∈ M, ≺ , such that ⊊ ℐ , 4. there exists an ∈ M such that ⊊ ℐ and for all ∈ M, ≺ implies = ℐ . A circumscribed KB takes the form CircCP() where is a KB and CP a circumscription pattern. A model ℐ of is a model of CircCP() if no <CP ℐ is a model of . This minimality condition poses a challenge for algorithms that try to find a countermodel ℐ for a query (¯) and tuple ¯, that, is a model ℐ of CircCP() with ℐ ̸|= (¯). Indeed, such algorithms rely on first establishing a ‘regular model property’ which states that if a countermodel exists, then there is a ‘regular’ one, typically tree-shaped or forest-shaped. This is proved by starting with any countermodel and then manipulating it, e.g. by unraveling. In the presence of circumscription, such manipulations are more challenging as they must preserve minimality w.r.t. the circumscription pattern. In what follows, we present a condition that is suficient for the preservation of minimality and underlies several of our constructions. It is stated as Lemma 1 below.
We first observe that a nominal may be viewed as a (strictly) closed concept name with a single instance. From this, we exhibit a reduction from UCQ evaluation on circumscribed ℒℋℐ KBs to UCQ evaluation on circumscribed ℒℋℐ KBs. We are thus left with ℒℋℐ TBoxes, which we generally assume to be in normal form, meaning that every concept inclusion has one of the following shapes: ⊤ ⊑ ⊑ ∃. ∃. ⊑ 1 ⊓ 2 ⊑ ⊑ ¬ ¬ ⊑ where , 1, 2, range over concept names and ranges over (possibly inverse) roles.
Let CircCP() be a circumscribed KB with = ( , ). The set of concept names in is denoted NC( ). We define a type to be a set of concept names ⊆ NC( ). For an interpretation ℐ and ∈ Δℐ , let tpℐ () := { ∈ NC( ) | ∈ ℐ }, and for a subset Δ ⊆ Δℐ , let tpℐ (Δ) = {tpℐ () | ∈ Δ}. We further write TP(ℐ) for tpℐ (Δℐ ). Finally, we set ⋃︁ TP( ) :=
TP(ℐ).
ℐ model of
We next show how to identify a ‘core’ part of a model ℐ of . These core parts play an important role in dealing with circumscription in our upper bound proofs.
Definition 1. Let ℐ be a model of . We use TPcore(ℐ) to denote the set of all types ∈ TP(ℐ) such that |{ ∈ Δℐ ∖ ind() | tpℐ () = }| < |TP( )|. We set TPcore(ℐ) = TP(ℐ) ∖ TPcore(ℐ) and Δcℐore = { ∈ Δℐ | tpℐ () ∈ TPcore(ℐ)}.
So the core of ℐ, which is the restriction of ℐ to domain Δcℐore, consists of all elements whose types are realized not too often, except possibly in the ABox. A good way of thinking about cores is that if a model ℐ of is minimal w.r.t. <CP, then all instances of minimized concept names are in the core. This is, however not strictly true since we may have ⊑ where is ⊤ or fixed, and is minimized.
The following crucial lemma provides a suficient condition for a model of to be minimal w.r.t. <CP, relative to a model ℐ of that is known to be minimal w.r.t. <CP. Lemma 1. Let ℐ be a model of CircCP() and a model of with Δcℐore ⊆ Δ . If tpℐ () = tp () for all ∈ Δcℐore and tp (Δ ∖ Δcℐore) = TPcore(ℐ), then is a model of CircCP().
We use the above lemma to show that if there exists a countermodel for a CQ (¯) and tuple ¯ ∈ ind()|¯| on CircCP(), then this is witnessed by a countermodel ℐ that has a regular shape. By regular shape, we mean that there is a ‘base part’ that contains the ABox, the core of ℐ, as well as some additional elements as representatives for certain types; all other parts of ℐ are tree-shaped with their root in the base part, and potentially with edges that go back to the core (but not to other parts of the base). We then show that the existence of a countermodel of such a shape can be decided using a mosaic procedure. The base part ℐbase of ℐ is part of all mosaics (intuitively, it is guessed) and the mosaics are used to ensure that ℐbase can be extended into a complete countermodel by adding tree-shaped parts. We trace partial query matches through the mosaics to make sure that the query doesn’t map into ℐ. Compliance with CircCP() can be checked solely on ℐbase, using Lemma 1. This gives the 2Exp upper bound w.r.t. combined complexity. Proving the Π 2P upper bound in data complexity requires extra work. We add a quotient construction that exploits the above regular shape, and preserves the base part so that Lemma 1 may again guarantee minimality.
To establish the improved bounds for the DL-Lite family, we refine Lemma 1. To prove that AQ evaluation on circumscribed DL-Litebℋool KBs is in PTime in data complexity, for example, we improve Lemma 1 by identifying a core part of the countermodel that lives purely within the ABox. This refinement is made possible by the limited expressivity of DL-Lite.
The research reported in this paper has been supported by the German Research Foundation DFG, as part of Collaborative Research Center (Sonderforschungsbereich) 1320 Project-ID 329551904 “EASE - Everyday Activity Science and Engineering”, University of Bremen (http: //www.ease-crc.org/). The research was conducted in subprojects “P02 – Ontologies with Abstraction” and “P05-N – Principles of Metareasoning for Everyday Activities”.
The authors acknowledge the financial support by the Federal Ministry of Education and Research of Germany and by the Sächsische Staatsministerium für Wissenschaft Kultur und Tourismus in the program Center of Excellence for AI-research “Center for Scalable Data Analytics and Artificial Intelligence Dresden/Leipzig”, project identification number: ScaDS.AI
This work is partly supported by BMBF (Federal Ministry of Education and Research) in DAAD project 57616814 (SECAI, School of Embedded Composite AI) as part of the program Konrad Zuse Schools of Excellence in Artificial Intelligence. [13] P. A. Bonatti, C. Lutz, F. Wolter, The complexity of circumscription in description logic, J.
Artif. Intell. Res. 35 (2009) 717–773. [14] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge University Press, 2017.