Closed-World Semantics for Conjunctive Queries with Negation over ELH-bottom Ontologies

1 Introduction

Ontology-mediated query answering (OMQA) allows using background knowledge for answering user queries, supporting data-focused applications offering search, analytics, or data integration functionality. An ontology is a logical theory formulated in a decidable fragment of first-order logic, with a trade-off between the expressivity of the ontology and the efficiency of query answering.

Ontology-based systems do not use the closed-domain and closed-world semantics of databases. Instead, they acknowledge that unknown (anonymous) objects may exist (open domain) and that facts that are not explicitly stated may still be true (open world). Anonymous objects are related to null values in databases, but are not used explicitly; for example, if we know that every person has a mother, then first-order models include all mothers, even though they may not be mentioned in the input dataset. The open-world assumption ensures that, if the dataset does not contain an entry on, e.g. whether a person is male or female, then we do not infer that this person is neither male nor female, but rather consider all possibilities.

The biomedical domain is a fruitful area for OMQA, due to the availability of large ontologies 1 and the demand for managing large amounts of patient data, in the form of electronic health records (EHRs) [Cresswell and Sheikh, 2017]. For example, for the preparation of clinical trials 2 a large number of patients need to be screened for eligibility, and an important area of current research is how to automate this process [Patel et al., 2007; Besana et al., 2010; K¨opcke and Prokosch, 2014; Ni et al., 2015]. 3

∗This is an abridged version of a paper from the proceedings of JELIA 2019 [Borgwardt and Forkel, 2019].

1 https://bioportal.bioontology.org

However, ontologies and EHRs mostly contain positive information, while clinical trials also require certain exclusion criteria to be absent in the patients. For example, we may want to select only patients that have not been diagnosed with cancer, 4 but such information cannot be entailed from the given knowledge. The culprit for this problem is the openworld semantics, which considers a cancer diagnosis possible unless it has been explicitly ruled out.

One possibility is to introduce (partial) closed-world semantics to ontology languages [Lutz et al., 2013; Ahmetaj et al., 2016]. For example, one can declare the predicate human to be "closed", i.e. if an object is not explicitly listed as human in the dataset, then it is considered to be not human. However, such approaches fail to deal with anonymous objects; indeed, they conflate the open-world and open-domain assumptions by requiring that all closed information is restricted to the known objects. For example, even if we don't know the mother of a person, we still know that she is human, even though this may not be explicitly stated in the ontology (but entailed by it). Using the semantics of [Lutz et al., 2013; Ahmetaj et al., 2016] would hence enforce a partial closeddomain assumption as well, in that A's mother would have to be a known object from the dataset.

Epistemic logics are another way to give a closed-worldlike semantics to negated formulas; e.g. one can formulate queries like "no cancer diagnosis is known" using the epistemic knowledge modality K. Such formalisms are also unable to deal with closed-world knowledge over anonymous objects [Wolter, 2000; Calvanese et al., 2006]. Most closely related to our proposal are Datalog-based semantics for negation, based on the (Skolem) chase construction [Hernich et al., 2013]. We compare all these existing semantics in detail in Section 3.

The contribution of this paper is a new closed-world semantics to answer conjunctive queries with (guarded) negation [B´ar´any et al., 2012] over ontologies formulated in ELH⊥, an ontology language that covers many biomedical ontologies. Our semantics is based on the minimal canonical model, which encodes all inferences of the ontology in the most concise way possible. As a side effect, this means that standard CQs without negation are interpreted under the standard openworld semantics. In order to properly handle negative knowledge about anonymous objects, however, we have to be careful in the construction of the canonical model, in particular about the number and type of anonymous objects that are introduced. Since in general the minimal canonical model is infinite, we develop a rewriting technique, in the spirit of the combined approach of [Lutz et al., 2009; Kontchakov et al., 2011], and most closely inspired by [Eiter et al., 2012; Bienvenu and Ortiz, 2015], which allows us to evaluate conjunctive queries with negation over a finite part of the canonical model, using traditional database techniques.

2 https://clinicaltrials.gov

3 https://n2c2.dbmi.hms.harvard.edu

4 An exclusion criterion of the clinical trial described at https://clinicaltrials.gov/ct2/show/NCT01463215

An extended version of this paper including proofs can be found at https://tu-dresden.de/inf/lat/papers.

2 Preliminaries

We recall the definitions of ELH⊥ and conjunctive queries. Let NC,NR,NI be countably infinite sets of concept, role, and individual names, respectively. A concept is built according to the syntax rule C ::= A | ⊤ | ⊥ | C ⊓ C | ∃r.C, where A ∈ NC and r ∈ NR. An ABox is a finite set of concept assertions A(a) and role assertions r(a, b), where a, b ∈ NI . A TBox is a finite set of concept inclusions C ⊑ D and role inclusions r ⊑ s, where C, D are concepts and r, s are roles. In the following we assume that all inclusions are of the form

where A(i) ∈ NC ∪ {⊤}, B ∈ NC ∪ {⊥}, r, s ∈ NR, and n ≥ 1. A knowledge base (KB) (or ontology) K = (T ,A) is a pair of a TBox T and an ABox A. We write C ≡ D to abbreviate the two inclusions C ⊑ D, D ⊑ C.

The semantics of ELH⊥ is defined in terms of interpretations I = (∆I , ·I ) as usual [Baader et al., 2007]. An axiom α is entailed by K (written K |= α) if α is satisfied in all models of K. We abbreviate K |= C ⊑ D to C ⊑T D, and similarly for role inclusions. Entailment in ELH⊥ can be decided in polynomial time [Baader et al., 2005].

A conjunctive query (CQ) φ(x) is a first-order formula ∃y. ϕ(x, y), where ϕ is a conjunction of concept and role atoms. Let I = (∆, ·I ) be a first-order interpretation. An assignment π: Var(φ) → ∆ satisfies φ in I if I, π |= φ under the semantics of first-order logic. Let K be a KB. A k-tuple a of individual names from K is an answer to φ in I if φ has a satisfying assignment π in I with π(x) = a; it is a certain answer to q in K if it is an answer to q in all models of K. We denote the set of all answers to φ in I by ans(φ, I), and the set of all certain answers to φ in K by cert(φ, K).

CQ answering over ELH⊥ KBs is combined first-order rewritable [Lutz et al., 2009]: For any CQ q and consistent KB K = (T ,A) one can find a first-order query qT and a finite interpretation I ′K with cert(q, K) = ans(qT , I ′K). This is based on the canonical model property of ELH⊥: For any consistent KB K one can construct a model IK that is homomorphically contained in any other model. This property is very useful since cert(q, K) = ans(q, IK) holds for all CQs q.

3 Conjunctive Queries With Negation

We are interested in answering queries of the following form.

Definition 1. Conjunctive queries with (guarded) negation (NCQs) are constructed by extending CQs with negated concept atoms ¬A(t) and negated role atoms ¬r(t, t′ ), such that, for any negated atom over terms t (and t′ ) the query contains at least one positive atom over t (and t′ ).

We first discuss different ways of handling negated atoms, and then propose a new semantics that is based on the minimal canonical model. We consider an example based on real EHRs (ABoxes) from the MIMIC-III database [Johnson et al., 2016], criteria (NCQs) from clinicaltrials.gov, and the large medical ontology SNOMEDCT 5 (the TBox).

We assume that the ABoxes have been extracted from EHRs by a natural language processing tool based, e.g. on existing concept taggers like [Aronson, 2001].

Example 2. We consider three patients. Patient p1 (patient 2693 in the MIMIC-III dataset) is diagnosed with breast cancer and an unspecified form of cancer (this often occurs when there are multiple mentions of cancer in a patient's EHR, which cannot be resolved to the same entity). Patient p2 (MIMICIII patient 32304) suffers from breast cancer and skin cancer ("Stage IV breast cancer with mets to skin, bone, and liver"). For p3 (MIMIC-III patient 88432), we know that p3 has breast cancer that involves the skin ("Skin, left breast, punch biopsy: Poorly differentiated carcinoma").

Since SNOMEDCT does not model patients, we add a new role name diagnosedWith to connect patients with diagnoses, which can be used in two ways. One can explicitly introduce individual names for diagnoses, e.g. diagnosedWith(p1, d1), BreastCancer(d1), diagnosedWith(p1, d2), Cancer(d2), implying that these diagnoses are treated as distinct entities under the standard name assumption. Alternatively, one can use complex assertions like ∃diagnosedWith.Cancer(p1), which allows the logical semantics to resolve whether two diagnoses refer to the same object. Since ABoxes only contain concept names, in this case one has to introduce auxiliary definitions like CancerPatient ≡ ∃diagnosedWith.Cancer into the TBox. We use both variants in our example, to illustrate their different behaviours.

We obtain the KB KC, containing knowledge about different kinds of cancers and cancer patients, together with information about the three patients. The information about cancers is taken from SNOMEDCT (in simplified form):

SkinCancer ≡ Cancer ⊓ ∃site.SkinStruct BreastCancer ≡ Cancer ⊓ ∃site.BreastStruct SkinOfBreastCancer ≡ Cancer ⊓ ∃site.SkinOfBreastStruct SkinOfBreastStruct ⊑ BreastStruct ⊓ SkinStruct

5 https://www.snomed.org/snomed-ct

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

The EHRs are compiled into several assertions per patient:

Patient p1: BreastCancerPatient(p1), CancerPatient(p1)

Patient p2: SkinCancerPatient(p2), BreastCancerPatient(p2)

Patient p3: diagnosedWith(p3, c3), SkinOfBreastCancer(c3)

Additionally, we add the following definitions to the TBox:

CancerPatient ≡ ∃diagnosedWith.Cancer

SkinCancerPatient ≡ ∃diagnosedWith.SkinCancer

BreastCancerPatient ≡ ∃diagnosedWith.BreastCancer

For example, skin cancers and breast cancers are cancers that have as (finding) site specific parts of the body ("body structure" in SNOMEDCT), and a breast cancer patient is someone who is diagnosed with breast cancer. This means that, in every model of KC, every object that satisfies BreastCancerPatient (in particular p2) must have a diagnosedWith-connected object that satisfies BreastCancer, and so on.

For a clinical trial, 6 we want to find patients that have "breast cancer", but not "breast cancer that involves the skin." This can be translated into an NCQ:

Since p1 is diagnosed with BreastCancer as well as Cancer, and the former is more specific, we assume that the latter refers to the same object. However, we have no information about an involvement of the skin, so p1 should be an answer to qB.

We know that p2 suffers from cancer in the skin and the breast, but not if the skin of the breast is also affected. Since neither location is implied by the other, we assume that they refer to distinct areas. p2 should thus be an answer to qB.

For p3, it is explicitly stated that it is the same cancer that is occurring at the skin of the breast. In this case, the ABox assertions override the distinctness assumption we made for p2. Thus, p3 should not be an answer to qB. ■

In practice, more complicated cases than in our example can occur: For example, in SNOMEDCT it is possible to describe many details of a cancer, such as the kind of cancer, whether it is a primary or secondary cancer, and in which part of the body it is found. This means that even a single assertion can lead to the introduction of multiple levels of anonymous objects in the canonical model. In some ontologies there are even cyclic concept inclusions, which lead to infinitely many anonymous individuals, e.g. in the GALEN ontology 7 . We focus on Example 2 in this paper, to illustrate the relevant issues in a clear and easy to follow manner. We now evaluate existing semantics on this example.

6 https://clinicaltrials.gov/ct2/show/NCT01960803

Epistemic Logic allows us to selectively apply closed-world reasoning using the modal knowledge operator K. For a formula Kϕ to be true, it has to hold in all "connected worlds", which is often considered to mean all possible models of the KB, adopting an S5-like view [Calvanese et al., 2006]. For qB, we could read ¬SkinStruct(z) as "not known to be a skin structure", i.e. ¬KSkinStruct(z). Consider the model IKC in Figure 1 and the assignment π = {x ↦→ p3, y ↦→ c3, z ↦→ f3}, for which we want to check whether it satisfies qB. Under epistemic semantics, ¬KSkinStruct(z) is considered true if K has a (different) model in which f3 does not belong to SkinStruct. However, f3 is an anonymous object, and hence its name is not fixed. For example, we can easily obtain another model by renaming f3 to f1 and vice versa. Then f3 would not be a skin structure, which means that ¬KSkinStruct(z) is true in the original model IKC , which is not as expected. This is a known problem with epistemic first-order logics [Wolter, 2000].

Skolemization can enforce a stricter comparison of anonymous objects between models. For example, the inclusion SkinCancer ⊑ ∃site.SkinStruct could be rewritten as the firstorder sentence

where f is a fresh function symbol. This means that c3 would be connected to a finding site that has the unique name f(c3) in every model. Queries would be evaluated over Herbrand models only. Hence, for evaluating ¬KSkinStruct(z) when z is mapped to f(c3), we would only be allowed to compare the behavior of f(c3) in other Herbrand models. The general behavior of this anonymous individual is fixed, however, since in all Herbrand models it is the finding site of c3. Then, since p3

7 http://www.opengalen.org/

is inferred to be a BreastCancerPatient, the Skolemized version of BreastCancerPatient ⊑ ∃diagnosedWith.BreastCancer introduces a new successor g(p3) of p3 satisfying BreastCancer, which, together with the definition of BreastCancer, means that p3 is an answer to qB since there is an additional breast cancer diagnosis that does not involve the skin.

Datalog-based Ontology Languages with negation [Hernich et al., 2013] are closely related to Skolemized ontologies, since their semantics is often based on the so-called Skolem chase [Marnette, 2009]. However, it suffers from the same drawback of Skolemization described above, due to superfluous successors. To avoid this, our semantics uses a special minimal canonical model (see Definition 4), which is similar to the restricted chase [Fagin et al., 2005] or the core chase [Deutsch et al., 2008], but always produces a unique model without having to merge domain elements.

3.1 Semantics for NCQs

We propose to answer NCQs over a special canonical model of the knowledge base. On the one hand, this eliminates the problem of tracking anonymous objects across different models, and on the other hand enables us to encode our assumptions directly into the construction of the model. In particular, we should only introduce the minimum necessary number of anonymous objects since, unlike in standard CQ answering, the precise shape and number of anonymous objects has an impact on the semantics of negated atoms.

Given KC, in contrast to the Skolemized semantics, we will not create both a generic "Cancer" and another "BreastCancer" successor for p1, because the BreastCancer is also a Cancer, and hence the first object is redundant. Therefore, in the minimal canonical model of KC depicted in Figure 1, for patient p1 only one successor is introduced to satisfy the definitions of both BreastCancerPatient and CancerPatient at the same time. In contrast, p2 has two successors, because BreastCancer and SkinCancer do not imply each other. Finally, for p3 the ABox contains a single successor that is a SkinOfBreastCancer, which implies a single site-successor that satisfies both SkinStruct and BreastStruct.

To detect whether an object required by an existential restriction ∃r.A is redundant, we use the following notion:

Definition 3 (Structural Subsumption). Let ∃r.A, ∃t.B be concepts with A, B ∈ NC and r, t ∈ NR. We say that ∃r.A is structurally subsumed by ∃t.B (written ∃r.A ⊑sT ∃t.B) if r ⊑T t and A ⊑T B. Given a set V of existential restrictions, we say that ∃r.A ∈ V is minimal w.r.t. ⊑sT (in V ) if there is no ∃t.B ∈ V such that ∃t.B ⊑sT ∃r.A.

In contrast to standard subsumption, ∃r.A is not structurally subsumed by ∃t.B w.r.t. the TBox T = {∃r.A ⊑ ∃t.B}, as neither r ⊑T t nor A ⊑T B hold.

Definition 4 (Minimal Canonical Model). Let K = (T ,A) be an ELH⊥ KB. We construct the minimal canonical model IK of K as follows:

1. Set ∆IK := NI and aIK := a for all a ∈ NI.
2. Define AIK := {a | K |= A(a)} for all A ∈ NC and rIK := {(a, b) | K |= r(a, b)} for all r ∈ NR.
3. Repeat:
4. (a) Select d ∈ ∆IK that has not been selected before and let V := {∃r.B | d ∈ AIK and d ̸∈ (∃r.B)IK with A ⊑T ∃r.B, A,B ∈ NC}.
5. (b) For each ∃r.B ∈ V that is minimal w.r.t. ⊑sT , add a fresh element e to ∆IK , for each B ⊑T A add e to AIK , and for each r ⊑T s add (d, e) to sIK .

By IA we denote the restriction of IK to named individuals, i.e. the result of applying only Steps 1 and 2, but not Step 3.

If Step 3 is applied fairly, i.e. such that each new domain element that is created in (b) is eventually also selected in (a), then IK is indeed a model of K (if K is consistent at all). In particular, all required existential restrictions are satisfied at each domain element, because the existential restrictions that are minimal w.r.t. ⊑sT entail all others.

Moreover, IK satisfies the properties expected of a canonical model [Lutz et al., 2009; Eiter et al., 2012]: it can be homomorphically embedded into any other model of K, and therefore cert(q,K) = ans(q, IK) holds for all CQs q. We now define the semantics of NCQs as described before, i.e. by evaluating them as first-order formulas over the minimal canonical model IK, which ensures that our semantics is compatible with the usual certain-answer semantics for CQs.

Definition 5 (Minimal-World Semantics). The (minimalworld) answers to an NCQ q over a consistent ELH⊥ KB K are mwa(q, K) := ans(q, IK).

For Example 2, we get mwa(qB, KC) = {p1, p2} (see Figure 1), which is exactly as intended. Unfortunately, in general the minimal canonical model is infinite, and we cannot evaluate the answers directly. Hence, we employ a rewriting approach to reduce NCQ answering over the minimal canonical model to (first-order) query answering over IA only.

In our full paper [Borgwardt and Forkel, 2019] we show that NCQ answering is combined first-order rewritable, and we obtain the following complexity result.

Theorem 6. Checking whether a given tuple a is a closedworld answer to an NCQ φ over a consistent ELH⊥ KB K can be done in polynomial time in data complexity.

More important than the complexity is that this approach can be used to evaluate NCQs using standard database methods, e.g. using views to define the finite interpretation IA based on the input data in A, and SQL queries to evaluate rewT (φ) over these views [Kontchakov et al., 2011].

4 FutureWork

We are working on an implementation with the aim to deal with NCQs over large ontologies like SNOMEDCT. We will also further develop our approach to represent temporal and numeric information, such as the precise order and duration of a patient's illnesses and treatments, and the dosage of medications. Such information is important for evaluating the eligibility criteria of clinical trials.

Acknowledgments

This work was supported by the DFG grant BA 1122/19-1 (GOASQ) and grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science).