Abstract 1 Introduction 2 Ontology Embeddings 3 Basic Notions 4 Strong Faithfulness 5 Strong Faithfulness on Convex Models 6 Model Checking on Geometric Models 7 Conclusion and discussion References Appendix A Appendix

Strong Faithfulness for 𝓔𝓛𝓗 Ontology Embeddings

Victor Lacerda ORCID University of Bergen, Norway Ana Ozaki ORCID University of Oslo, Norway
University of Bergen, Norway
Ricardo Guimarães ORCID Zivid AS, Norway
Abstract

Ontology embedding methods are powerful approaches to represent and reason over structured knowledge in various domains. One advantage of ontology embeddings over knowledge graph embeddings is their ability to capture and impose an underlying schema to which the model must conform. Despite advances, most current approaches do not guarantee that the resulting embedding respects the axioms the ontology entails. In this work, we formally prove that normalized has the strong faithfulness property on convex geometric models, which means that there is an embedding that precisely captures the original ontology. We present a region-based geometric model for embedding normalized ontologies into a continuous vector space. To prove strong faithfulness, our construction takes advantage of the fact that normalized has a finite canonical model. We first prove the statement assuming (possibly) non-convex regions, allowing us to keep the required dimensions low. Then, we impose convexity on the regions and show the property still holds. Finally, we consider reasoning tasks on geometric models and analyze the complexity in the class of convex geometric models used for proving strong faithfulness.

Keywords and phrases:
Knowledge Graph Embeddings, Ontologies, Description Logic
Funding:
Victor Lacerda: Lacerda is supported by the NFR project “Learning Description Logic Ontologies”, grant number 316022, led by Ozaki.
Ana Ozaki: Ozaki is supported by the NFR project “Learning Description Logic Ontologies”, grant number 316022.
Copyright and License:
[Uncaptioned image] © Victor Lacerda, Ana Ozaki, and Ricardo Guimarães; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Description logics
Supplementary Material:
The authors declare that this article involves no relevant supplemental resources.
Received:
2024-04-24  
Accepted:
2024-10-23  
Published:
2024-12-18

1 Introduction

Knowledge Graphs (KGs) are a popular method for representing knowledge using triples of the form (subject, predicate, object), called facts.

Although public KGs, such as Wikidata [25], contain a large number of facts, they are incomplete. This has sparked interest in using machine learning methods to suggest plausible facts to add to the KG based on patterns found in the data. Such methods are based on knowledge graph embedding (KGE) techniques, which aim to create representations of KGs in vector spaces. By representing individuals in a vector space, these individuals can be ranked by how similar they are to each other, based on a similarity metric.

Their proximity in a vector space may be indicative of semantic similarity, which can be leveraged to discover new facts: if two individuals are close to each other in the embedding space, it is likely that they share a pattern of relations to other individuals. These patterns of relations can indicate of assertions not explicitly stated in the source knowledge graph.

Many attempts have been made to learn representations of knowledge graphs for use in downstream tasks [8]. These methods have traditionally focused only on embedding triples (facts), ignoring the conceptual knowledge about the domain expressed using logical operators. The former corresponds to the “Assertion Box”(ABox) of the ontology, while the latter corresponds to the “Terminological Box” (TBox) part of a knowledge base, with both being quite established notions in the fields of Description Logic and Semantic Web [2, 12]. Embeddings that consider both types of logically expressed knowledge are a more recent phenomenon (see Section 2), and we refer to them as ontology embeddings, where the ontology can have both an ABox and a TBox. Ontology embeddings offer advantages over traditional KGEs as they exploit the semantic relationships between concepts and roles. This enables ontology embeddings to better capture rich and nuanced relationships between concepts, making them good candidates for tasks requiring fine-grained reasoning, such as hierarchical reasoning and logical inference.

One question that arises in the study of ontology embeddings is the following: how similar to the source ontology are the generated embeddings? Being more strict, if we fix a semantics in order to interpret the generated embeddings, are they guaranteed to precisely represent the meaning of the source ontology and its entailments (of particular interest, the TBox entailments)? This property is called the strong faithfulness property [20] and, so far, no previous work for ontology embeddings has attempted to prove the property holds for their embedding method. Moreover, the existence of embedding models satisfying this property for the language has not been formally proven. Given that ontologies languages in the family have received most of the attention by the existing literature on ontology embeddings [22, 23, 1, 26, 14], this is a significant gap which we investigate in this work.

Contribution

We investigate whether has the strong faithfulness property over convex geometric models. We first prove the statement for embeddings in low dimensions, considering a region-based representation for (possibly) non-convex regions (Section 4). Also, we prove that the same property does not hold when we consider convex regions and only 1 dimension. We then investigate strong faithfulness on convex geometric models with more dimensions (Section 5). This result contributes to the landscape of properties for embedding methods based on geometric models [5, Proposition 11] and it provides the foundation of the implementation of FaithEL [16]. We do so including embeddings for role inclusions, a problem that has not been well studied in the ontology embedding literature. We also consider model checking in convex geometric models, a topic that has not been covered in previous works (Section 6).

2 Ontology Embeddings

Various methods for embedding ontologies have been proposed, with ontologies in the family being their primary targets. is a simple yet powerful language.

These embedding methods are region-based, that is, they map concepts to regions and entities to vectors (in some cases, entities are transformed into nominals and also embedded as regions), and represent roles using translations or regions within the vector space.

The precise shape of the embedding regions varies depending on the method. In EmEL [19] and ELem [15], the embeddings map concepts to n-dimensional balls. One disadvantage of this approach is that the intersection between two balls is not itself a ball. Newer approaches addressing this issue such as BoxEL, Box2EL, and ELBE [26, 14, 23], starting with BoxE [1], represent concepts as n-dimensional boxes. BoxE introduced the use of so-called “translational bumps” to capture relations between entities, an idea followed by Box2EL. Another language, 𝒜𝒞, has been studied under a cone semantics [20], which uses axis-aligned cones as its geometric interpretation. In the context of KGEs, n-dimensional parallelograms have also been used in ExpressivE [21].

Other approaches for accommodating TBox axioms in the embeddings have also been considered. Approaching the problem from a different direction, OWL2Vec* [7] targets the DL language 𝒮𝒪𝒬 and does not rely on regions, but uses the NLP algorithm word2vec to include lexical information (such as annotations) along with the graph structure of an OWL ontology. Another framework, TransOWL [9], uses background knowledge injection to improve link prediction for models such as TransE and TransR. Additionally, there has been an increased interest in querying KGEs, with strategies utilizing query rewriting techniques being put in place to achieve better results [13].

Although expressively powerful and well performing in tasks such as subsumption checking and link prediction, the generated embeddings often lack formal guarantees with respect to the source ontology. In the KGE literature, it is a well known that, e.g., TransE [3] is unable to model one-to-many relations (a difficulty present even in recent ontology embedding methods such as BoxEL) or symmetric relations. This has spurted a quest for more expressive models, with the intention of capturing an increasing list of relation types and properties such as composition, intersection, hierarchy of relations, among others [17, 27, 24, 21].

Expressivity is a key notion in ontology embedding methods, which often also feature these relation types and potentially other forms of constraints. For example, in Box2EL, ELem, and ELBE [14, 15, 23], axioms of the form r.C are only approximated by r.. This means that strong TBox faithfulness is not respected. Moreover, only EmEL and Box2EL [19, 14] include embeddings for role inclusions. In the case of EmEL, the axiom rs also enforces sr, which means it is not strongly faithful, while Box2EL has also been shown to not be strongly faithful [5].

3 Basic Notions

3.1 The Description Logic 𝓔𝓛𝓗

Let NC, NR, and NI be countably infinite and pairwise disjoint sets of concept names, role names, and individual names, respectively. concepts C,D are built according to the syntax rule

C,D::=||A|(CD)|r.C

where ANC and rNR. concept inclusions (CIs) are of the form CD, role inclusions (RIs) are of the form rs, concept assertions are of the form A(a) and role assertions are of the form r(a,b), where ANC, a,bNI, r,sNR, and C, D range over concepts. Instance queries (IQs) are role assertions or of the form C(a), with C being an arbitrary concept. An axiom is an CI, an RI, or an IQ. A normalized TBox is one that only contains CIs of the following forms:

A1A2B,r.AB, and Ar.B

where A1,A2,A,BNC and rNR. We say that an concept is in normal form if it is of the form A, r.A, or AB, with A,BNC and rNR. Similarly, an ontology is in normal form if its TBox part is a normalized TBox. An IQ is in normal form if it is a role assertion or of the form C(a) with C being a concept in normal form. The semantics of is defined classically by means of interpretations =(Δ,), where Δ is a non-empty countable set called the interpretation domain, and is an interpretation function mapping each concept name A in NC to a subset A of Δ, each role name r in NR to a binary relation rΔ×Δ, and each individual name a in NI to an element aΔ. We extend the function inductively to arbitrary concepts by setting :=Δ, :=, and

(CD) :=CD, and
(r.C) :={dΔeC such that (d,e)r}.

An interpretation satisfies: (1) CD iff CD; (2) rs iff rs, (3) C(a) iff a C; (4) r(a,b) iff (a,b)r.

An TBox 𝒯 (Terminological Box) is a finite number of concept and role inclusions. An ABox 𝒜 (Assertion Box) is a finite number of concept and role assertions. The union of a TBox and an ABox forms an ontology. An ontology 𝒪 entails an axiom α, in symbols 𝒪α if for every interpretation , we have that 𝒪 implies α (we may write similarly for the CI and RI entailments of a TBox). We denote by NC(𝒪),NR(𝒪),NI(𝒪) the set of concept names, role names, and individual names occurring in an ontology 𝒪. We may also write NI(𝒜) for the set of individual names occurring in an ABox 𝒜. The signature of an ontology 𝒪, denoted 𝗌𝗂𝗀(𝒪), is the union of NC(𝒪),NR(𝒪), and NI(𝒪).

3.2 Geometric models

We go from the traditional model-theoretic interpretation of the language to geometric interpretations, using definitions from previous works by [10] and [6]. Let m be a natural number and f:m×m2m a fixed but arbitrary linear map satisfying the following:

  1. 1.

    the restriction of f to m×{0}m is injective;

  2. 2.

    the restriction of f to {0}m×m is injective;

  3. 3.

    f(m×{0}m)f({0}m×m)={02m};

where 0m denotes the vector (0,,0) with m zeros. We say that a linear map that satisfies Points 1, 2, and 3 is an isomorphism preserving linear map.

Example 1.

The concatenation function is a linear map that satisfies Points 1, 2, and 3. E.g., if we have vectors v1=(n1,n2,n3) and v2=(m1,m2,m3) then for f being the concatenation function we would have f(v1,v2)=(n1,n2,n3,m1,m2,m3). Other linear maps that satisfy Points 1, 2, and 3 can be created with permutations. E.g., defining the function f such that f(v1,v2)=(n1,m1,n2,m2,n3,m3).

Definition 2 (Geometric Interpretation).

Let f be an isomorphism preserving linear map and m a natural number. An m-dimensional f-geometric interpretation η of (NC,NR,NI) assigns to each

  • ANC a region η(A)m

  • rNR a region η(r)2m, and

  • aNI a vector η(a)m.

We now extend the definition for arbitrary concepts:

η() :=
η() :=m,
η(CD) :=η(C)η(D), and
η(r.C) :={vmuη(C) with f(v,u)η(r)}.

Intuitively, the function f combines two vectors that represent a pair of elements in a classical interpretation relation. An m-dimensional f-geometric interpretation η satisfies

  • an concept assertion A(a), if η(a)η(A),

  • a role assertion r(a,b), if f(η(a),η(b))η(r),

  • an IQ C(a), if η(a)η(C),

  • an CI CD, if η(C)η(D), and

  • an RI rs, if η(r)η(s).

We write ηα if η satisfies an axiom α. When speaking of m-dimensional f-geometric interpretations, we may omit m-dimensional and f-, as well as use the term “model” instead of “interpretation”. A geometric interpretation satisfies an ontology 𝒪, in symbols η𝒪, if it satisfies all axioms in 𝒪. We say that a geometric interpretation is finite if the regions associated with concept and role names have a finite number of vectors and we only need to consider a finite number of individual names, which is the case when considering the individual names that occur in an ontology.

Motivated by the theory of conceptual spaces and findings on cognitive science [11, 28], and by previous work on ontology embeddings for quasi-chained rules [10], we consider convexity as an interesting restriction for the regions associated with concepts and relations in a geometric model.

Definition 3.

A geometric interpretation η is convex if, for every ENCNR, every v1,v2η(E) and every λ[0,1], if v1,v2η(E) then (1λ)v1+λv2η(E).

Definition 4.

Let S={v1,,vm}d. A vector v is in the convex hull S of S iff there exist v1,,vnS and scalars λ1,λ2,,λn such that

v=i=1nλivi=λ1v1+λ2v2++λnvn,

where λi0, for i=1,,n, and i=1nλi=1.

Apropos of convexity, we highlight and prove some of its properties used later in our results.

Proposition 5.

For finite S1,S2d, where d is an arbitrary dimension, we have that S1S2 implies S1S2.

In the following, whenever we say a vector is binary, we mean that its values in each dimension can only be 0 or 1.

Theorem 6.

Let S{0,1}d where d is an arbitrary dimension. For any n, for any v=i=1nλivi, such that viS, if vSS then v is non-binary.

Corollary 7.

If v is binary and vS then vS.

Finally, we define strong faithfulness based on the work by [20].

Definition 8 (Strong Faithfulness).

Let 𝒪 be a satisfiable ontology (or any other representation allowing the distinction between IQs and TBox axioms). Given an m-dimensional f-geometric interpretation η, we say that:

  • η is a strongly concept-faithful model of 𝒪 iff, for every concept C and individual name b, if η(b)η(C) then 𝒪C(b);

  • η is a strongly IQ faithful model of 𝒪 iff it is strongly concept-faithful and for each role r and individual names a,b: if f(η(a),η(b))η(r), then 𝒪r(a,b);

  • η is a strongly TBox-faithful model of 𝒪 iff for all TBox axioms τ: if ητ, then 𝒪τ.

Example 9.

Let 𝒪 be an ontology given by 𝒯𝒜 with 𝒯={AB} and 𝒜={A(a),B(b)}. Let η be a (non-convex) geometric interpretation of 𝒪 in , where η(A)={0,1,2}, η(B)={0,1,2,3}, η(a)=2, and η(b)=3. Note that 𝒪A(a) and 𝒪B(b), and by definition η(a)η(A), η(b)η(B). Also, 𝒪AB and η(A)η(B). So one can see that η is both a strongly concept and TBox-faithful model of 𝒪. If we let η be a geometric interpretation such that η(A)={0,1,2,3}=η(B), we now have that η(b)η(A), which means η is not a strongly concept-faithful model of 𝒪 (since 𝒪⊧̸A(b)), and we have that η(B)η(A), which means it is not a strongly TBox-faithful model of 𝒪 (since 𝒪⊧̸BA).

We say that an ontology language has the strong faithfulness property over a class of geometric interpretations 𝒞 if for every satisfiable ontology 𝒪 in this language there is a geometric interpretation in 𝒞 that is both a strongly IQ faithful and a strongly TBox faithful model of 𝒪.

The range of concepts, roles, and individual names in Definition 8 varies depending on the language and setting studied. We omit the notion of weak faithfulness by [20] as it does not apply for since ontologies in this language are always satisfiable (there is no negation). The “if-then” statements in Definition 8 become “if and only if” when η satisfies the ontology. Intuitively, strong faithfulness expresses how similar the generated embedding is to the original ontology.

We observe that strong faithfulness with respect to the TBox component of the ontology is extremely desirable: it guarantees that concept and role inclusions are also enforced when coupled with a geometric interpretation in the embedding space. On the other hand, strong IQ faithfulness is not a desirable property for learned embeddings. Although this might seem counter-intuitive at first, it is a reasonable statement: an embedding that is strongly IQ faithful is unsuitable for link prediction, as the only assertions that hold in the embedding are those that already hold in the original ontology. This means that no new facts are truly discovered by the model. Here we prove both strong TBox and IQ faithfulness for for theoretical reasons.

Finally, observe that an embedding model that is both strongly TBox and IQ faithful must have the same TBox and IQ consequences as the original ontology. This is a stronger requirement than establishing that an embedding model for an ontology 𝒪 (within a method) exist if and only if a classical model for 𝒪 exists, which is a property of sound and complete embedding methods [5].

4 Strong Faithfulness

In this section we prove initial results about strong faithfulness for . In particular, we prove that has the strong faithfulness property over m-dimensional f-geometric interpretations for any m1 but this is not the case if we require that regions in the geometric interpretations are convex. We first introduce a mapping from classical interpretation to (possibly) non-convex geometric interpretations and then use it with the notion of canonical model to establish strong faithfulness for .

Definition 10.

Let =(Δ,) be a classical interpretation, and we assume without loss of generality, since Δ is non-empty and countable, that Δ is a (possibly infinite) interval in starting on 0. Let μ¯:Δ1 be a mapping from our classical interpretation domain to a vector space where:

μ¯(d)={(,d][d,),if Δis finite and d=max(Δ),(d1,d][d,d+1),otherwise.

where d and (d1,d] and [d,d+1) are intervals over 1, closed on d and d, and open on d+1 and d1.

 Remark 11.

For any interpretation , μ¯ covers the real line, that is, dΔμ¯(d)=1.

Definition 12.

We call η¯ the geometric interpretation of and define it as follows. Let be a classical interpretation. The geometric interpretation of , denoted η¯, is defined as:

η¯(a) :=d, such that d=a, for all aNI,
η¯(A) :={vμ¯(d)dA}, for all ANC, and
η¯(r) :={f(v,e)vμ¯(d) for (d,e)r}, for all rNR.
Figure 1: A partial visualization (showing only the positive section of the real line) of a geometric interpretation η¯ where elements d0d3 are mapped to their respective intervals, and where μ¯(d0),μ¯(d2),μ¯(d3)η¯(A) and μ¯(d2)η¯(B).

In Figure 1, we illustrate with an example the mapping in Definition 12. We now show that for (possibly) non-convex geometric models, a classical interpretation models arbitrary IQs and arbitrary TBox axioms if and only if their geometrical interpretation η¯ also models them.

Theorem 13.

For all axioms α, α iff η¯α.

We now provide a definition of canonical model for ontologies inspired by a standard chase procedure. In our definition, we use a tree shaped interpretation D of an concept D, with the root denoted ρD. This is defined inductively. For D a concept name ANC we define A as the interpretation with ΔA:={ρA}, AA:={ρA}, and all other concept and role names interpreted as the empty set. For D=r.C, we define D as the interpretation with ΔD:={ρD}ΔC, all concept and role name interpretations are as for C except that we add (ρD,ρC) to rD and assume ρD is fresh (i.e., it is not in ΔC). Finally, for D=C1C2 we define ΔD:=ΔC1(ΔC2{ρC2}), assuming ΔC1 and ΔC2 are disjoint, and with all concept and role name interpretations as in C1 and C2, except that we connect ρC1 with the elements of ΔC2 in the same way as ρC2 is connected. That is, we identify ρC1 with the root ρC2 of D2.

Definition 14.

The canonical model ¯𝒪 of a satisfiable ontology 𝒪 is defined as the union of a sequence of interpretations 0,1,, where 0 is defined as:

Δ0 :={aaNI(𝒜)},
A0 :={aA(a)𝒜} for all ANC, and
r0 :={(a,b)r(a,b)𝒜}, for all rNR.

Suppose n is defined. We define n+1 by choosing a CI or an RI in 𝒪 and applying one of the following rules:

  • if CD𝒪 and dCnDn then define n+1 as the result of adding to n a copy of the tree shaped interpretation D and identifying d with the root of D (assume that the elements in ΔD are fresh, that is, ΔDΔn=);

  • if rs𝒪 and (d,e)rnsn then set n+1 as the result of adding (d,e) to sn.

We assume the choice of CIs and RIs and corresponding rule above to be fair, i.e., if a CI or RI applies at a certain place, it will eventually be applied there.

Theorem 15.

Let 𝒪 be a satisfiable ontology and let ¯𝒪 be the canonical model of 𝒪 (Definition 14). Then,

  • for all IQs and CIs α over 𝗌𝗂𝗀(𝒪), ¯𝒪α iff 𝒪α; and

  • for all RIs α over 𝗌𝗂𝗀(𝒪), ¯𝒪α iff 𝒪α.

We are now ready to state our theorem combining the results of Theorems 13 and 15 and the notion of strong faithfulness for IQs and TBox axioms.

Theorem 16.

Let 𝒪 be a satisfiable ontology and let ¯𝒪 be the canonical model of 𝒪 (see Definition 14). The m-dimensional f-geometric interpretation of ¯𝒪 (see Definition 12) is a strongly IQ and TBox faithful model of 𝒪.

What Theorem 16 demonstrates is that the existence of canonical models for allows us to connect our result relating classical and geometric interpretations to faithfulness. This property of canonical models is crucial and can potentially be extended to other description logics that also have canonical models (however, many of such logics do not have polynomial size canonical models, a property we use in the next section, so we focus on in this work).

Corollary 17.

For all m1 and isomorphism preserving linear maps f, has the strong faithfulness property over m-dimensional f-geometric interpretations.

However, requiring that the regions of the geometric model are convex makes strong faithfulness more challenging. The next theorem hints that such models require more dimensions and a more principled approach to map ontologies in a continuous vector space.

Figure 2: An illustration of the region η(A)η(B).
Theorem 18.

does not have the strong faithfulness property over convex 1-dimensional f-geometric models.

Proof.

We reason by cases in order to show impossibility of the strong faithfulness property for the class of convex 1-dimensional f-geometric model for arbitrary ontologies. Let 𝒪 be an ontology, A, B, C NC concept names, a,bNI individuals, and let η(A), η(B), η(C), η(a), and η(b) be their corresponding geometric interpretations to 1. Assume 𝒪AB(a). There are three initial cases on how to choose the interval placement of η(A) and η(B):

  • Null intersection: (η(A)η(B))=.

    If (η(A)η(B))=, then either (η(a)η(A) and (η(a)η(B), or (η(a)η(B) and (η(a)η(A). Recall the definition of satisfiability for concept assertions. Since we assumed 𝒪AB(a), we would want our geometric interpretation to be such that η(a)η(A)η(B), a contradiction.

  • Total inclusion: η(A)η(B) and/or η(B)η(A).

    Consider an extension 𝒪 of our ontology where 𝒪A(c) and 𝒪⊧̸B(c). If we let η(A)η(B), it is clear that our ontology cannot be faithfully modeled, since by our assumption of total inclusion, we would have that η(c)η(A) and η(c)η(B), which goes against 𝒪⊧̸B(c). The same holds for the total inclusion in the other direction, where η(B)η(A). Therefore, we go to our last initial case to be considered.

  • Partial intersection: (η(A)η(B)).

    This is in fact the only way of faithfully giving a geometric interpretation to our concept assertion AB(a), while still leaving room for ABox axioms such that an arbitrary element could belong to one of our classes A or B without necessarily belonging to both of them. Then, η(A)η(B) and η(A)η(B) nor η(B)η(A).

After having forced the geometric interpretation of our two initial concepts A and B to partially intersect, we now show that by adding a third concept C, in which 𝒪ABC(a), either η(A)η(B)η(C) or η(B)η(A)η(C), even though this interpretation is not included in our original ontology. We are unable to include a concept assertion A(a)𝒪 without also having that η(a)η(C) in our geometric interpretation, or likewise for the case in which B(a)𝒪.

Stemming from the fact that our geometric interpretation must be convex, and it is modeled in an euclidean 1 space, we can visualize our classes A, B, and C as intervals on the real line. Assume, without loss of generality, that η(A) is placed to the left of η(B) (see Figure 2). Then, C can only be placed either to the right of B or to the left of A.

By reasoning in the same way as before, we know that η(C) must partially intersect with either η(A) or η(B), so one end of the interval representing C must be placed in η(A)η(B), without us having that either η(C)η(A), η(C)η(B), η(C)η(A)η(B) or η(C)η(A)η(B). This last requirement is due to the fact that we want to be able to have an ontology such that 𝒪C(a) and where 𝒪⊧̸A(a), 𝒪⊧̸B(a), or 𝒪⊧̸A(a)B(a). Assuming the intersection between η(A) and η(B) there are three more cases to be considered:

  • C is in the intersection of A and B: η(C)η(A)η(B) (Fig. 2 (a)).

    If η(C)η(A)η(B), it is immediately clear that by extending 𝒪 such that 𝒪C(b) but 𝒪⊧̸A(b), we would end up with η(b)η(C). But since we assumed that η(C)η(A)η(B), this means that η(b)η(A), and therefore our geometric interpretation would model the concept assertion A(b), a contradiction.

  • C goes from the intersection: η(A)η(B) to η(A)η(B) (Fig. 2 (b)).

    In this situation, we would have η(C)η(A), and if 𝒪C(a), we would necessarily have that η(a)η(C), but this means we would also have η(a)η(A), leading to the unwarranted consequence that ηA(a). There is one last case.

  • C is placed in a region such that: η(C)(η(A)η(B)) and η(C)(η(A)η(B)) (Fig. 2 (c)).

    This would mean that η(B)η(A)η(C), and that any concept assertion B(a) would entail either C(a) or A(a) in our geometric interpretation, while it is not necessary that 𝒪A(a) or 𝒪B(a). Since we are in 1, this desired placement can happen either to the right or to the left of the number line. By assumption that η(A) has been placed to the left of η(B) as shown in Figure 2 and following, we have just shown that placing η(C) to the right of η(B) leads to a contradiction. The same reasoning applies if we choose to place it to the left of η(A).

There are no more cases to be considered.

Figure 3: The three possible cases when there is an element in the intersection of A,B,C.

The problem illustrated in Theorem 18 arises even if the ontology language does not have roles (as it is the case, e.g., of Boolean 𝒜𝒞, investigated by [20]). It also holds if we restrict to normalized . We address the problem of mapping normalized ontologies to convex geometric models in the next section.

5 Strong Faithfulness on Convex Models

We prove that normalized has the strong faithfulness property over a class of convex geometric models. We introduce a new mapping μ from the domain of a classical interpretation to a vector space and a new geometric interpretation η based on this mapping. Our proofs now require us to fix the isomorphism preserving linear map f used in the definition of geometric interpretations (Definition 2). We choose the concatenation function, denoted , as done in the work by [10]. The strategy for proving strong faithfulness for normalized requires us to (a) find a suitable non-convex geometric interpretation for concepts and roles, and (b) show that the convex hull of the region maintains the property intact.

Definition 19.

Let =(Δ,) be a classical interpretation, and 𝒪 an ontology. We start by defining a new map μ:Δ𝖽, where 𝖽 corresponds to |NI(𝒪)|+|NC(𝒪)|+|NR(𝒪)||Δ|. We assume, without loss of generality, a fixed ordering in our indexing system for positions in vectors, where indices 0 to |NI(𝒪)|1 correspond to the indices for individual names; |NI(𝒪)| to k=|NI(𝒪)|+|NC(𝒪)|1 correspond to the indices for concept names; and k to k+(|NR(𝒪)||Δ|)1 correspond to the indices for role names together with an element of Δ. We adopt the notation v[a], v[A], and v[r,d] to refer to the position in a vector v corresponding to a, A, and r together with an element d, respectively (according to our indexing system). For example, v[a]=0 means that the value at the index corresponding to the individual name a is 0. A vector is binary iff v{0,1}𝖽. We now define μ using binary vectors. For all dΔ, aNI, ANC and rNR:

  • μ(d)[a]=1 if d=a, otherwise μ(d)[a]=0,

  • μ(d)[A]=1 if dA, otherwise μ(d)[A]=0, and

  • μ(d)[r,e]=1 if (d,e)r, otherwise μ(d)[r,e]=0.

Figure 4: A mapping to the binary vector μ(d) when dΔ, where da0, dA0 and (d,d0)r0.

Figure 4 illustrates a possible mapping for element dΔ, where da0, dA0 and (d,d0)r0.

Example 20.

Let 𝒪 be an ontology such as in Example 9, with 𝒯={AB}, 𝒜 being extended to 𝒜={A(a),B(b),r(a,b)}. Let be an interpretation such that Δ={d,e}, with a=d, b=e, r={(d,e)}, A={d}, and B={d,e}. In this case, μ:Δ6, with |NI(𝒪)|=2 (corresponding to a and b), |NC(𝒪)|=2 (corresponding to A and B), and |NR(𝒪)||Δ|=2 corresponding to r, d, and e. Assume our ordering in the definition holds, and assume further that the names in the signature of 𝒪 are ordered alphabetically. We have that the six dimensions correspond to, respectively: a,b,A,B,[r,d],[r,e]. By applying the mapping to the elements of Δ, we get the vectors μ(d)=(1,0,1,1,0,1) and μ(e)=(0,1,0,1,0,0).

We now introduce a definition for (possibly) non-convex geometric interpretations, in line with the mapping μ above.

Definition 21.

Let be a classical interpretation. The geometric interpretation of , denoted η, is defined as:

η(a) :=μ(a), for all aNI,
η(A) :={μ(d)μ(d)[A]=1,dΔ}, for all ANC,
η(r) :={μ(d)μ(e)μ(d)[r,e]=1,d,eΔ}, for all rNR.

We provide two examples, one covering both concept and role assertions, and one (which can be represented graphically), covering only concept assertions.

Example 22.

Let 𝒪, be as in Example 20. Then, the geometric interpretation η of is as: η(a)=μ(d), η(b)=μ(e), η(A)={μ(d)}, η(B)={μ(d),μ(e)},η(r)={μ(d)μ(e)}. We remark that this is a strongly faithful TBox embedding.

An intuitive way of thinking about our definition μ is that it maps domain elements to a subset of the vertex set of the 𝖽-dimensional unit hypercube (see Example 23).

Figure 5: A mapping of μ(d) and μ(e) according to interpretation . The axes colored in red, blue, and green correspond to the dimensions associated with a, A, and B, respectively.
Example 23.

Consider A,BNC and aNI. Let be an interpretation with d,eΔ such that d=a, dA, and eAB. We illustrate μ(d) and μ(e) in Figure 5. In symbols, μ(d)[a]=1, μ(d)[A]=1, and μ(d)[B]=0, while μ(e)[a]=0, μ(e)[A]=1, and μ(e)[B]=1.

Before proving strong faithfulness with convex geometric models, we show that η preserves the axioms that hold in the original interpretation . It is possible for two elements d,eΔ to be mapped to the same vector v as a result of our mapping μ. This may happen when d,e {aaNI} but it does hinder our results.

Proposition 24.

If μ(d)=μ(e), then dC iff eC.

We use a similar strategy as before to prove our result.

Theorem 25.

For all axioms α, α iff η𝒪α.

Since the definition of η uses vectors in a dimensional space that depends on the size of Δ and 𝒪, we need the canonical models to be finite. Therefore, we employ finite canonical models for normalized because canonical models for arbitrary CIs are not guaranteed to be finite. Our definition of canonical model is a non-trivial adaptation of other definitions found in the literature (e.g., [4, 18]).

Let 𝒜 be an ABox, 𝒯 a normalized TBox, and 𝒪:=𝒜𝒯. We first define:

Δu𝒪 :={cA|ANC(𝒪){}} and
Δu+𝒪 :=Δu𝒪{cAB|A,BNC(𝒪)}{cr.B|rNR(𝒪),BNC(𝒪){}}.
Definition 26.

The canonical model 𝒪 of 𝒪 is defined as

Δ𝒪 :=NI(𝒜)Δu+𝒪,a𝒪:=a,
A𝒪 :={aNI(𝒜)|𝒪A(a)}{cDΔu+𝒪|𝒯DA}, and
r𝒪 :={(a,b)NI(𝒜)×NI(𝒜)|𝒪r(a,b)}
{(a,cB)NI(𝒜)×Δu𝒪|𝒪r.B(a)}{(cs.B,cB)Δu+𝒪×Δu𝒪|𝒯sr}
{(cD,cB)Δu+𝒪×Δu𝒪|𝒯DA,𝒯Ar.B, for some ANC(𝒪)},

for all aNI, ANC, and rNR.

The following holds for the canonical model just defined.

Theorem 27.

Let 𝒪 be a normalized ontology. The following holds

  • for all IQs and CIs α in normal form over 𝗌𝗂𝗀(𝒪), 𝒪α iff 𝒪α; and

  • for all RIs α over 𝗌𝗂𝗀(𝒪), 𝒪α iff 𝒪α.

The main difference between our definition and other canonical model definitions in the literature is related to our purposes of proving strong faithfulness, as we discuss in Section 5. We require the CIs and RIs (in normal form and in 𝗌𝗂𝗀(𝒪)) that are entailed by the ontology are exactly those that hold in the canonical model.

Theorem 28.

Let 𝒪 be an ontology and let 𝒪 be the canonical model of 𝒪 (Definition 26). The 𝖽-dimensional (possibly non-convex) -geometric interpretation η𝒪 of 𝒪 is a strongly and IQ and TBox faithful model of 𝒪.

We now proceed with the main theorems of this section. Note that the dimensionality of the image domain of μ can be much higher than the one for μ¯ in Section 4 (which can be as low as just 1, see Corollary 17). We use the results until now as intermediate steps to bridge the gap between classical and convex geometric interpretations. In our construction of convex geometric interpretations, the vectors mapped by μ and the regions given by the non-convex geometric interpretation η are the anchor points for the convex closure of these sets. We introduce the notion of the convex hull of a geometric interpretation η using Definition 4.

Definition 29.

We denote by η the convex hull of the geometric interpretation η and define η as follows:

η(a) :=μ(a), for all aNI;
η(A) :={μ(d)dA}, for all ANC; and
η(r) :={μ(d)μ(e)(d,e)r}, for all rNR.
 Remark 30.

In Definition 29, η(a)=η(a) for all aNI. We include the star symbol in the notation to make it clear that we are referring to the geometric interpretation of individual names in the context of convex regions for concepts and roles.

Theorem 31.

Let η be a geometric interpretation as in Definition 21. If α is an CI, an RI, or an IQ in normal form then ηα iff ηα.

We are now ready to consider strong IQ and TBox faithfulness for convex regions.

Theorem 32.

Let 𝒪 be a normalized ontology and let 𝒪 be the canonical model of 𝒪 (Definition 26). The 𝖽-dimensional convex -geometric interpretation of 𝒪 (Definition 29) is a strongly IQ and TBox faithful model of 𝒪.

We now state a corollary analogous to Corollary 17, though here we cannot state it for all classes of m-dimensional f-geometric interpretations (we know by Theorem 18 that this is impossible for any class of 1-dimensional geometric interpretations). We omit “m-dimensional” in Corollary 33 to indicate that this holds for the larger class containing geometric interpretations with an arbitrary number of dimensions (necessary to cover the whole language).

Corollary 33.

Normalized has the strong faithfulness property over -geometric interpretations.

 Remark 34 (Number of parameters).

The final number of parameters for the convex geometric interpretation η𝒪 of the canonical model 𝒪 built on ontology 𝒪 is, thus: O(𝖽n) where 𝖽 is the embedding dimension given by map μ (Definition 19), and n=|Δ𝒪|.

6 Model Checking on Geometric Models

Here we study upper bounds for the complexity of model checking problems using convex geometric models as those defined in Definition 29 and normalized axioms. The results and algorithms in this section are underpinned by Theorem 31, which allow us to use η instead of η for model checking purposes. The advantage of using η instead of η is that the algorithms need to inspect only finitely many elements in the extension of each concept and each role, as long as the original interpretation has finite domain (and we only need to consider a finite number of concept, role, and individual names). For example, let =(Δ,) with Δ finite. If A𝖭𝖢 then η(A) can have infinitely many elements, while η(A) will have at most |Δ| elements (by Definition 21). Before presenting the algorithms, we discuss some assumptions that facilitate our analysis:

  1. 1.

    indexing vectors and comparing primitive types use constant time;

  2. 2.

    accessing the extension of an individual, concept, or role name in η takes constant time;

  3. 3.

    iterating over η(A) (and also η(r)) consumes time O(|Δ|) (O(|Δ||Δ|)) for all A𝖭𝖢 (r𝖭𝖱); and

  4. 4.

    if A𝖭𝖢 (r𝖭𝖱), testing if vη(A) (vη(r)) consumes time O(𝖽|Δ|) (O(𝖽|Δ||Δ|)).

Assumption (1) is standard when analysing worst-case complexity. The others are pessimistic assumptions on the implementation of η (and η). E.g., encoding the binary vectors as integers and implementing bit wise operations could reduce the complexity of membership access and iteration. Also, using a hash map with a perfect hash function would decrease the membership check to constant time.

We are now ready to present our upper bounds. For normalised CIs, we provide Algorithm 1 to decide if a concept inclusion holds in a convex geometric model built as in Definition 29. Theorem 31 guarantees that ηCD iff ηCD for any CI in normalised . Thus, as long as Δ is finite, Algorithm 1 terminates and outputs whether ηCD. Theorem 35 establishes that Algorithm 1 runs in polynomial time in the size of Δ and the dimension of vectors in η.

Algorithm 1 Check if a convex geometric model (Definition 29) satisfies an CI in normal form.
Theorem 35.

Given a finite geometric interpretation η and an CI in normal form, Algorithm 1 runs in time in O(𝖽𝗇4), where 𝖽 is as in Definition 19 and 𝗇=|Δ|.

As 𝖽 depends linearly on Δ and the size of the signature. If the latter is regarded as a constant, we can simply say that Algorithm 1 has time in O(𝗇5), where 𝗇=|Δ|. Similarly as for Algorithm 1, Theorem 31 allows us to design an algorithm to determine if a convex geometric model η satisfies an IQ in normal form α, as we show in Algorithm 2.

Algorithm 2 check if a convex geometric model (as in Definition 29) satisfies an IQ in normal form.

Theorem 36 shows that Algorithm 2 runs in time polynomial in 𝖽|Δ|.

Theorem 36.

Given a finite geometric interpretation η and an IQ in normal form, Algorithm 2 runs in time O(𝖽𝗇3), with 𝖽 as in Definition 19 and 𝗇=|Δ|.

Next, we present Algorithm 3, which handles RIs. Again, as a consequence of Theorem 31, we only need to check the inclusion between two finite sets of vectors in 2𝖽. Finally, we show an upper bound using Algorithm 3.

Algorithm 3 Check if a convex geometric model (as in Definition 29) satisfies an role inclusion.
Theorem 37.

Given a finite geometric interpretation η and an role inclusion, Algorithm 3 runs in time in O(𝖽𝗇4), where 𝖽 is as in Definition 19 and 𝗇=|Δ|.

The three algorithms presented in this Section run in polynomial time in 𝖽|Δ|. We recall that the construction of η (and also η) requires that both the signature and Δ are finite (which is reasonable for normalized ), otherwise the vectors in η would have infinite dimension.

7 Conclusion and discussion

We have proven that has the strong faithfulness property over (possibly) non-convex geometric models, and that normalized has the strong faithfulness property over convex geometric models. Furthermore, we give upper bounds for the complexity of checking satisfaction for axioms in normal form in the class of convex geometric models that we use for strong faithfulness.

As future work, we would like to implement an embedding method that is formally guaranteed to generate strongly TBox faithful embeddings for normalized ontologies, as well as expand the language so as to cover more logical constructs present in ++.

References

  • [1] Ralph Abboud, Ismail Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori. BoxE: A box embedding model for knowledge base completion. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9649–9661. Curran Associates, Inc., 2020. doi:10.5555/3495724.3496533.
  • [2] Franz Baader, Ian Horrocks, Carsten Lutz, and Uli Sattler. An Introduction to Description Logic. Cambridge University Press, USA, 1st edition, 2017. doi:10.1017/9781139025355.
  • [3] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In C. J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. doi:10.5555/2999792.2999923.
  • [4] Stefan Borgwardt and Veronika Thost. LTL over EL Axioms. Technische Universität Dresden, 2015. doi:10.25368/2022.213.
  • [5] Camille Bourgaux, Ricardo Guimarães, Raoul Koudijs, Victor Lacerda, and Ana Ozaki. Knowledge base embeddings: Semantics and theoretical properties. In Proceedings of the TwentyFirst International Conference on Principles of Knowledge Representation and Reasoning, pages 823–833, Hanoi, Vietnam, November 2024. International Joint Conferences on Artificial Intelligence Organization. doi:10.24963/kr.2024/77.
  • [6] Camille Bourgaux, Ana Ozaki, and Jeff Z. Pan. Geometric models for (temporally) attributed description logics. In Martin Homola, Vladislav Ryzhikov, and Renate A. Schmidt, editors, DL, volume 2954 of CEUR Workshop Proceedings. CEUR-WS.org, 2021. URL: https://ceur-ws.org/Vol-2954/paper-7.pdf.
  • [7] Jiaoyan Chen, Pan Hu, Ernesto Jimenez-Ruiz, Ole Magnus Holter, Denvar Antonyrajah, and Ian Horrocks. Owl2vec*: embedding of owl ontologies. Machine Learning, 110(7):1813–1845, July 2021. doi:10.1007/s10994-021-05997-6.
  • [8] Yuanfei Dai, Shiping Wang, Neal N. Xiong, and Wenzhong Guo. A Survey on Knowledge Graph Embedding: Approaches, Applications and Benchmarks. Electronics, 9(5):750, May 2020. doi:10.3390/electronics9050750.
  • [9] Claudia d’Amato, Nicola Flavio Quatraro, and Nicola Fanizzi. Injecting background knowledge into embedding models for predictive tasks on knowledge graphs. In Ruben Verborgh, Katja Hose, Heiko Paulheim, Pierre-Antoine Champin, Maria Maleshkova, Oscar Corcho, Petar Ristoski, and Mehwish Alam, editors, The Semantic Web, pages 441–457. Springer International Publishing, 2021. doi:10.1007/978-3-030-77385-4_26.
  • [10] Víctor Gutiérrez-Basulto and Steven Schockaert. From knowledge graph embedding to ontology embedding? an analysis of the compatibility between vector space representations and rules. In Michael Thielscher, Francesca Toni, and Frank Wolter, editors, KR, pages 379–388. AAAI Press, 2018. URL: https://aaai.org/ocs/index.php/KR/KR18/paper/view/18013, doi:10.4230/OASIcs.AIB.2022.3.
  • [11] Peter Gärdenfors. Conceptual Spaces: The Geometry of Thought. The MIT Press, March 2000. doi:10.7551/mitpress/2076.001.0001.
  • [12] Pascal Hitzler, Markus Krötzsch, and Sebastian Rudolph. Foundations of Semantic Web Technologies. Chapman & Hall/CRC, 2009.
  • [13] Anders Imenes, Ricardo Guimarães, and Ana Ozaki. Marrying query rewriting and knowledge graph embeddings. In RuleML+RR, pages 126–140. Springer-Verlag, 2023. doi:10.1007/978-3-031-45072-3_9.
  • [14] Mathias Jackermeier, Jiaoyan Chen, and Ian Horrocks. Dual box embeddings for the description logic el++. In Tat-Seng Chua, Chong-Wah Ngo, Ravi Kumar, Hady W. Lauw, and Roy Ka-Wei Lee, editors, Proceedings of the ACM on Web Conference, WWW, pages 2250–2258. ACM, 2024. doi:10.1145/3589334.3645648.
  • [15] Maxat Kulmanov, Wang Liu-Wei, Yuan Yan, and Robert Hoehndorf. EL embeddings: Geometric construction of models for the description logic EL++. In Sarit Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 6103–6109. ijcai.org, 2019. doi:10.24963/ijcai.2019/845.
  • [16] Victor Lacerda, Ana Ozaki, and Ricardo Guimarães. Faithel: Strongly tbox faithful knowledge base embeddings for . In Sabrina Kirrane, Mantas Šimkus, Ahmet Soylu, and Dumitru Roman, editors, Rules and Reasoning, pages 191–199, Cham, 2024. Springer Nature Switzerland. doi:10.1007/978-3-031-72407-7_14.
  • [17] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1), February 2015. doi:10.1609/aaai.v29i1.9491.
  • [18] Carsten Lutz and Frank Wolter. Deciding inseparability and conservative extensions in the description logic el. Journal of Symbolic Computation, 45(2):194–228, February 2010. doi:10.1016/j.jsc.2008.10.007.
  • [19] Sutapa Mondal, Sumit Bhatia, and Raghava Mutharaju. Emel++: Embeddings for EL++ description logic. In Andreas Martin, Knut Hinkelmann, Hans-Georg Fill, Aurona Gerber, Doug Lenat, Reinhard Stolle, and Frank van Harmelen, editors, AAAI-MAKE, volume 2846 of CEUR Workshop Proceedings. CEUR-WS.org, 2021. URL: https://ceur-ws.org/Vol-2846/paper19.pdf.
  • [20] Özgür Lütfü Özçep, Mena Leemhuis, and Diedrich Wolter. Cone semantics for logics with negation. In Christian Bessiere, editor, IJCAI, pages 1820–1826. ijcai.org, 2020. doi:10.24963/ijcai.2020/252.
  • [21] Aleksandar Pavlovic and Emanuel Sallinger. ExpressivE: A spatio-functional embedding for knowledge graph completion. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL: https://openreview.net/pdf?id=xkev3_np08z.
  • [22] Xi Peng, Zhenwei Tang, Maxat Kulmanov, Kexin Niu, and Robert Hoehndorf. Description logic EL++ embeddings with intersectional closure. CoRR, abs/2202.14018, 2022. arXiv:2202.14018, doi:10.48550/arXiv.2202.14018.
  • [23] Xi Peng, Zhenwei Tang, Maxat Kulmanov, Kexin Niu, and Robert Hoehndorf. Description logic EL++ embeddings with intersectional closure. CoRR, abs/2202.14018, 2022. arXiv:2202.14018.
  • [24] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. arXiv, June 2016. doi:10.48550/arXiv.1606.06357.
  • [25] Denny Vrandečić and Markus Krötzsch. Wikidata: A free collaborative knowledgebase. Commun. ACM, 57(10):78–85, September 2014. doi:10.1145/2629489.
  • [26] Bo Xiong, Nico Potyka, Trung-Kien Tran, Mojtaba Nayyeri, and Steffen Staab. Faithful embeddings for EL++ knowledge bases. In The Semantic Web – ISWC 2022, pages 22–38. Springer International Publishing, 2022. doi:10.1007/978-3-031-19433-7_2.
  • [27] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv, August 2015. arXiv:1412.6575.
  • [28] Frank Zenker and Peter Gärdenfors. Applications of Conceptual Spaces: The Case for Geometric Knowledge Representation, volume 359 of Synthese Library. Springer International Publishing, 2015. doi:10.1007/978-3-319-15021-5.

Appendix A Appendix

A.1 Omitted proofs for Section 3

See 5

Proof.

Let S1,S2 be finite sets with S1S2. We first prove the statement for vS1S1 and then for uS1S1. Let vS1 be an arbitrary vector. By assumption, vS2, and by the definition of convex hull, vS2. Now, by Definition 4 let uS1S1 be defined by i=1nλivi where v1vnS1 and n|S1|. Since S1S2, v1vnS2 and, by Definition 4, since u=i=1nλivi, this gives us that uS2. Thus, S1S2 implies S1S2.

See 6

Proof.

For this proof we use a notation introduced in Definition 19. We reason by cases. We need to cover all combinations of values that λi may take for arbitrary n. We cover two cases. One where all λ are strictly greater than zero and strictly lesser than 1, and a case where some λi may be zero. By setting n=1, we have v=λ1x1. By definition, λ1=1, giving us either v=0 or v=1, both binary vectors, which means vS iff vS. Therefore, this case is not in the scope of our lemma, and we assume n>1.

  • Case 1 (𝟎<λi<𝟏): We prove the case by induction on the number of n.
    Base case: In the base case n=2. Let v1,v2S with v1v2. Then, there is a dimension d such that v1[d]v2[d]. Since v1 and v2 are binary, we can assume, without loss of generality, v1[d]=1 and v2[d]=0. Now let v=λ1v1+λ2v2 be a vector, with λ1+λ2=1. Since we assumed λi 0<λi<1, this means v{0,1}d because v[d]=λ1, which is strictly between 0 and 1. Therefore, v is non-binary.
    Inductive step: Assume our hypothesis holds for v1,,vn1.

    Let vS. We know that v=i=1nλivi, with 0<λi<1, with viS, and with i=1nλi=1. Since ijvivj, there is a dimension d such that l,m with vl[d]vm[d]. Since S is a set of binary vectors, we decompose the value of a dimension d as a sum of vectors where vi[d]=1 and vj[d]=0. In order to do this, we introduce an ordering and assume, without loss of generality, that vi[d]=1 1ik where k<n, and vj[d]=0 k+1j<n. More explicitly:

    v[d]=i=1kλivi[d]+j=k+1nλjvj[d].

    However, j=k+1nλjvj[d]=0, so we only have to look at the first sum. Clearly, v[d]0, because vl[d]vm[d]. Since there exists at least one λj>0 and, in this case λi 0<λi<1, it is impossible for the sum to be equal to 1, giving us v[d](0,1).

  • Case 2 (λi=0 and λji we have 0λj<1):

    We prove the case directly. We start by noting that for this case to hold, n3, as n=2 would mean λ1=0 and λ2<1, which goes against the criterion that i=1nλivi=1 from the definition. Now, assume n3. We denote by m the number of λi where λi=0. Pick m such that 1mn2. Then, there are at least nm2 λj such that 0<λj<1. Which is the situation covered by Case 1.

There are no more cases to be considered.

See 7

Proof.

The corollary follows directly from Theorem 6.

A.2 Omitted proofs for Section 4

Lemma 38.

For all dΔ, for all concepts C, it is the case that dC iff μ¯(d)η¯(C) (see Definition 12).

Proof.

We provide an inductive argument in order to prove the claim.

Base case:

Assume C=ANC, and assume dA.

By the definition of η¯, dA iff for all vμ¯(d), vη¯(A), that is, iff μ¯(d)η¯(A). Now assume C=, and assume dC. By the definition of η¯, if dC, then μ¯(d)η¯(C). Now assume μ¯(d)η¯(C). Since we assumed C=, we have that μ¯(d)1, with dΔ. When C=, the statement is vacuously true.

Inductive step:

Assume our hypothesis holds for C1 and C2. There are two cases:

  • Case 1 (C𝟏C𝟐): Assume d(C1C2) by the semantics of , d(C1C2) iff dC1 and dC2. By the inductive hypothesis, dCi iff μ¯(d)η(Ci), i{1,2}. But this happens iff dη¯(C1)η¯(C2). By the definition of η¯, this means that μ¯(d)η¯(C1C2) iff d(C1C2).

  • Case 2 (r.C𝟏): Assume d(r.C1) by the semantics of , d(r.C1) iff (d,e)r and eC1. By the inductive hypothesis, eC1 iff μ¯(e)η¯(C1). By the definition of η¯, (d,e)r iff f(v,e)η¯(r) where vμ¯(d). By the semantics of η¯, f(v,e)η¯(r) and eη¯(C1) iff μ¯(d)η¯(r.C1).

Lemma 39.

For all interpretations , all concepts C, and all aNI, it is the case that C(a) iff η¯C(a)

Proof.

By the semantics of , we know C(a) iff aC. By Lemma 38, we know that aC iff η¯(a)η¯(C). By the semantics of geometric interpretation, this is the case iff η¯C(a).

Lemma 40.

For all rNR, for all a,bNI, we have η¯r(a,b) iff r(a,b).

Proof.

By the semantics of , r(a,b) iff (a,b)r. By the definition of η¯, we have (a,b)r iff f(v,b)η¯(r) for all vμ¯(a). From the Definition 12, b=η¯(b), hence (a,b)r iff f(v,η¯(b))η¯(r) for all vμ¯(a). Since η¯(a)μ¯(a), we get, by the semantics of η¯, that f(η¯(a),η¯(b))η¯(r) iff η¯r(a,b). Giving us r(a,b) iff η¯r(a,b).

Lemma 41.

Let 𝒪 be an ontology and let ¯𝒪 be the canonical model of 𝒪 (Definition 14). The geometrical interpretation η¯¯𝒪 of ¯𝒪 (Definition 12) is a strongly IQ faithful model of 𝒪.

Proof.

Since 𝒪 is a canonical model of 𝒪, 𝒪α iff 𝒪α (Theorem 15). By Lemmas 39 and 40, 𝒪α iff η¯¯𝒪α. Then, we have that 𝒪α iff η¯¯𝒪α.

Lemma 42.

Let be an interpretation, and μ¯ be a mapping derived from Definition 10. For all concepts C, if vη¯(C), then there is dΔ such that vμ¯(d), and dC.

Proof.

We provide an inductive argument for the claim.

Base case:

Assume C=ANC and let vη¯(A). By the definition of η¯, it is the case that vη¯(A) iff v{vμ¯(d)dA}. Assume C=. By the definition of η¯, we have vη¯(C) iff vμ¯(d) such that μ¯(d)1. This means vμ¯(d) and μ¯(d)η¯(C), for some dΔ. When C=, the statement is vacuously true.

Inductive step:

Assume our hypothesis holds for C1 and C2.

  • Case 1 (C𝟏C𝟐): Assume vη¯(C1C2). Then, by the definition of η¯, it is the case that vη¯(C1) and vη¯(C2). By the inductive hypothesis, if vη¯(C1), then dΔ such that vμ¯(d) and dC1, and if vη¯(C2), then dΔ such that vμ¯(d) and dC2. By definition of μ¯, this can only be if d=d since μ¯ maps elements of Δ to mutually disjoint subsets of 1. By the semantics of , if dC1 and dC2 then d(C1C2).

  • Case 2 (r.C𝟏): Assume vη¯(r.C1). By the definition of η¯, this means v is such that f(v,e)η¯(r) where vμ¯(d) for (d,e)r and eη¯(C1). By the inductive hypothesis, there is an eΔ such that eμ¯(e) and eC1. As eΔ, by the construction of μ¯, it is the case that e=e. Therefore, we have eC1. By the definition of μ¯ and the semantics of , this means dΔ such that vμ¯(d) and d(r.C1).

Lemma 43.

Let be an interpretation and η¯ the geometric interpretation of (Definition 12). For all concepts C and D, CD iff η¯CD.

Proof.

Let C,D be concepts. Assume CD. By the semantics of , this means CD. Let vη¯(C) be a vector. By Lemma 42, we know there is dΔ and dC such that vμ¯(d) and μ¯(d)η¯(C). By Lemma 38, this means dC, and, by assumption, that dD. By Lemma 38, this means μ¯(d)η(D). Since we have shown vμ¯(d) such that η¯(C) implies vη¯(D), this means η¯CD.

Now assume η¯CD. By the semantics of geometric interpretation, this means η¯(C)η¯(D). Let dC. We know, by Lemma 38, that dC iff μ¯(d)η¯(C). By assumption, this means μ¯(d)η¯(D). Again by Lemma 38, this means dD. Since we have shown dC implies dD, we have CD.

Lemma 44.

Let be an interpretation, μ¯ be a mapping (Definition 10), and η¯ the geometric interpretation of (Definition 12) derived from μ¯. For all role names rNR, if f(v,e)η¯(r), then there are d,eΔ such that vμ¯(d) for (d,e)r.

Proof.

Assume z=f(v,e)η¯(r). By the definition of η¯, we have z{f(v,e)vμ¯(d) for (d,e)r}. This means vμ¯(d) for dΔ, and, by definition, eΔ.

Lemma 45.

Let be an interpretation and η¯ the geometric interpretation of (Definition 12). For all roles r,sNR, it is the case that rs iff η¯rs.

Proof.

Assume rs. By the semantics of , rs. Now let vη¯(r). By Lemma 44, there is dΔ such that vμ¯(d), eΔ, and (d,e)r. By assumption, this gives us (d,e)s. By the construction of η¯, this means f(v,e)η¯(s) for vμ¯(d). Hence, f(v,e)η¯(r) implies f(v,e)η¯(s) and we can conclude that η¯rs. Now assume η¯rs. By the semantics of η¯, η¯(r)η¯(s). Let (d,e)r. From the definition of η¯, we know there is f(v,e)η¯(r) such that vμ¯(d). By assumption, we have f(v,e)η¯(s) and, by the definition of η¯, this is the case iff (d,e)s. Since (d,e) was arbitrary, we conclude rs.

See 13

Proof.

For the case where α is a concept inclusion, the result comes from Lemma 43. For the case where α is a role inclusion, the result comes from Lemma 45. For the case where α is an IQ, the result comes from Lemma 39 and from Lemma 40.

Lemma 46.

Let 𝒪 be an ontology and let ¯𝒪 be the canonical model of 𝒪 (see Definition 14). The m-dimensional f-geometric interpretation of ¯𝒪 (see Definition 12) is a strongly TBox faithful model of 𝒪. That is, 𝒪τ iff η¯¯𝒪τ, where τ is either an concept inclusion or an role inclusion.

Proof.

Since we know ¯𝒪 is canonical, 𝒪α iff ¯𝒪α. By Lemma 43 we know CD iff η¯CD, and by Lemma 45 we know rs iff η¯rs. This means that ¯𝒪CD iff η¯¯𝒪CD and ¯𝒪rs iff η¯¯𝒪rs, giving us 𝒪τ iff η¯¯𝒪τ.

See 16

Proof.

The theorem follows by Lemma 41 and by Lemma 46.

A.3 Omitted proofs for Section 5

See 24

Proof.

We provide an inductive argument for the claim.

Base case:

Notice that if μ(d)=μ(e), then μ(d)[i]=n iff μ(e)[i]=n, for all i. That is, the value at the ith index is n for μ(d) and μ(e), otherwise they would not be the same vector. Now, assume C=ANC, and dC. By the definition of μ, μ(d)[C]=1. Since μ(d)=μ(e), we have that μ(d)[C]=1 iff μ(e)[C]=1. But, by the definition of μ, μ(e)[C]=1 iff eC, thus giving us our result.

Inductive step:

Assume our hypothesis holds for C1 and C2.

Assume μ(d)=μ(e). By the semantics of , d(C1C2) iff dC1 and dC2. By the induction hypothesis, this happens iff eC1 and eC2. This means, of course, by the semantics of , that eC1 and eC2 iff e(C1C2). Finally, we get d(C1C2) iff e(C1C2).

We prove the case (r.C1) directly. Assume μ(d)=μ(e), and d(r.C1). Then, by the semantics of , d such that dC1, and r(d,d). By the definition of μ, we know μ(d)[r,d]=1. But from our initial observation, μ(d)[r,d]=1 iff μ(e)[r,d]=1. By definition of μ, μ(e)[r,d]=1 iff (e,d)r. By the semantics of , whenever dC1 and (e,d)r we have that e(r.C1).

Lemma 47.

Let be an interpretation, and μ a mapping derived from Definition 19. For all normalized concepts C, if vη(C), then there is dΔ such that v=μ(d) and dC.

Proof.

We provide an inductive argument for the claim.

Base case:

Assume C=ANC and assume vη(C). By the definition of η, it is the case that vη(C) iff v[C]=1. This is the case iff v=μ(d), for some dΔ.

Inductive step:

Assume our hypothesis holds for C1 and C2. We prove two cases.

  • Case 1 (C𝟏C𝟐): Assume vη(C1C2). Then, by definition of η, it is true that vη(C1) and vη(C2). By the inductive hypothesis, if this is the case, then v=μ(d)C1 and v=μ(d)C2, for dΔ. This gives us v=μ(d)η(C1)η(C2), which means v=μ(d)η(C1C2), for dΔ.

  • Case 2 (r.C𝟏): Assume vη(r.C1). Then, by the definition of η, uη(C1) and vuη(r). By the inductive hypothesis, if uη(C1), we get u=μ(e)η(C1), for eΔ. Now, vuη(r) iff vu{μ(d)μ(e)μ(d)[r,e]=1}, for d,eΔ. This gives us v=μ(d) such that μ(d)[r,e]=1. By construction of η, if we have u=μ(e)η(C1), and v=μ(d) such that μ(d)[r,e]=1 with vuη(r), this means v=μ(d)η(r.C1), for some dΔ.

Lemma 48.

Let be an interpretation and let μ be as in Definition 19. For all rNR, if uwη(r), then there are d,eΔ such that u=μ(d), w=μ(e), and (d,e)r.

Proof.

Assume v=uwη(r). Then, by the definition of η(r), it is the case that v{μ(d)μ(e)μ(d)[r,e]=1, for d,eΔ}. This means there are d,eΔ such that v=μ(d)μ(e) and μ(d)[r,e]=1. By construction of μ, it is true that μ(d)[r,e]=1 iff (d,e)r. This means there are d,eΔ such that u=μ(d), w=μ(e) and (d,e)r.

Lemma 49.

For all dΔ, for all concepts C, dC iff μ(d)η(C).

Proof.

We provide an inductive argument for the claim.

For all dΔ, for all concepts C, dC iff μ(d)η(C).

Base case:

Assume C=ANC and dC. By the definition of μ, dC iff μ(d)[C]=1. By the definition of geometric interpretation, μ(d)[C]=1 iff μ(d)η(C).

Inductive step:

assume our hypothesis holds for C1 and C2. We consider two cases:

  • Case 1 (C𝟏C𝟐): Assume d(C1C2). This is the case iff dC1 and dC2. By the inductive hypothesis, we have that μ(d)η(C1) and dη(C2). But μ(d)η(C1) and dη(C2) iff μ(d)η(C1C2). Finally, by the semantics of geometric interpretation, μ(d)η(C1C2) iff d(C1C2).

  • Case 2 (r.C𝟏): Assume d(r.C1). Then, by the semantics of , eC1 such that (d,e)r. By the inductive hypothesis, we get μ(e)η(C1). By the definition of η, (d,e)r iff μ(d)μ(e)η(r). But, by the semantics of our geometric interpretation, μ(d)μ(e)η(r) and μ(e)η(C1) iff μ(d)η(r.C1).

Lemma 50.

For all interpretations , all concepts C, all aNI, C(a) iff ηC(a).

Proof.

C(a) iff aC. By Lemma 49, aC iff μ(a)η(C). By the semantics of geometric interpretation, μ(a)η(C) iff ηC(a).

Lemma 51.

For all rNR, all a,bNI, r(a,b) iff ηr(a,b).

Proof.

Assume r(a,b). By the semantics of , this means there are d,eΔ such that d=a, e=b, and (a,b)r. By the definition of μ, this means μ(d)[a]=1, that μ(e)[b]=1, and that μ(d)[r,e]=1. By the definition of geometric interpretation, this means μ(d)=η(a), that μ(e)=η(b), and that μ(d)μ(e)η(r), which is the case iff ηr(a,b).

Now assume ηr(a,b). This means that η(a)η(b)η(r). By Lemma 48, we have that d,eΔ such that η(a)=μ(d), η(b)=μ(e), and (d,e)r. But, by the definition of geometric interpretation and construction of μ, we have η(a)=μ(d) iff d=a, and η(b)=μ(e) iff e=b, and (a,b)r. By the semantics of , this means r(a,b).

Lemma 52.

If 𝒪 is the canonical model of 𝒪, then the geometrical interpretation η𝒪 of 𝒪 is strongly IQ faithful with respect to 𝒪. That is, 𝒪α iff η𝒪α, where α is an IQ.

Proof.

𝒪 is canonical, therefore 𝒪α iff 𝒪α. By Lemma 50 we have that C(a) iff ηC(a), and by Lemma 51 we have that r(a,b) iff ηr(a,b). This just means α iff η𝒪α, giving us η𝒪α iff 𝒪α.

Lemma 53.

For all C,D it is the case that CD iff ηCD.

Proof.

Let C,D be concepts. Assume CD. By the semantics of , this means CD. Let vη(C). By Lemma 47 we have that v=μ(d)η(C). We know, by Lemma 49, that μ(d)η(C) iff dC. Since we have dC, we also have, by assumption, dD. Again by Lemma 49, this gives us μ(d)η(D). Since d was chosen arbitrarily, this is the case iff ηCD.

Now assume ηCD. By the semantics of , η(C)η(D). Now assume dC. We know, by Lemma 49, that this is the case iff μ(d)η(C). By assumption, we get μ(d)η(D). Since v was arbitrary, and we showed that dC implies dD, this means CD.

Lemma 54.

For all r,sNR, it is the case that rs iff ηrs.

Proof.

Assume rs. B the semantics of , rs. Now let v=uwη(r). This means v{μ(d)μ(e)(d,e)r}, and, by Lemma 48 there are d,eΔ such that u=μ(d), w=μ(e) and (d,e)r. By assumption, (d,e)s. By construction of μ, this means μ(d)[s,e]=1. Since we know v=μ(d)μ(e) and μ(d)[s,e]=1, by the definition of η we have that vη(s), and, therefore ηrs.

Now assume ηrs. By the semantics of , this means η(r)η(s). Let (d,e)r. By the construction of μ, this means μ(d)[r,e]=1. By the definition of η, there is v=μ(d)μ(e)η(r). By assumption, vη(s). But, by Lemma 48, there are d,eΔ such that u=μ(d), w=μ(e), and (d,e)s. Since we have proven (d,e)r implies (d,e)s, this means rs.

See 25

Proof.

When α is a concept inclusion, the result comes from Lemma 53. When α is a role inclusion, the result comes from Lemma 54. When α is an IQ, the result comes from Lemma 50 and from Lemma 51

See 27

Proof.

We divide the proof into claims, first for assertions and then for concept and role inclusions. In the following, let 𝒪=𝒯𝒜 be an ontology in normal form, with 𝒯 being the set of concept and role inclusions in 𝒪 and 𝒜 being the set of assertions in 𝒪. As mentioned before, NC(𝒪), NR(𝒪), and NI(𝒜) denote the set of concept, role, and individual names occurring in 𝒪, respectively. In the following, let A,A1,A2,B,B be arbitrary concept names in NC(𝒪), let a,b be arbitrary individual names in NI(𝒜), and let r,s,s be arbitrary role names in NR(𝒪).

Claim 55.

𝒪A(a) iff 𝒪A(a).

Proof.

Assume 𝒪A(a). Now, by the definition of 𝒪 (Definition 26), it is the case that A𝒪{aNI(𝒜)𝒪A(a)}. By assumption, we have that aA𝒪. But since aNI(𝒜), by the definition of 𝒪, we have a𝒪=a and, therefore, a𝒪A𝒪, which means 𝒪A(a).
Now assume 𝒪A(a). This means a𝒪A𝒪. We know, by the definition of 𝒪, that a𝒪=a. Also by the definition of 𝒪, we know A𝒪 = {aNI(𝒜)|𝒪A(a)} {cDΔu+𝒪|𝒪DA}. Since aNI(𝒜), we have that aΔu+𝒪, and thus, 𝒪A(a).

Claim 56.

𝒪r(a,b) iff 𝒪r(a,b).

Proof.

Assume 𝒪r(a,b). By the definition of canonical model (Definition 26), r𝒪{(a,b)NI(𝒜)×NI(𝒜)𝒪r(a,b)}. Since we assumed that 𝒪r(a,b), we have that (a,b)r𝒪. Now, again by the definition of 𝒪, we have that a𝒪=a, and b𝒪=b. This means (a𝒪,b𝒪)r𝒪, which is the case iff 𝒪r(a,b).
Now assume 𝒪r(a,b). Then, we know (a𝒪,b𝒪)r𝒪. By definition of r𝒪, we have that (a,b)r𝒪. Since a,bNI, by definition of 𝒪, we have 𝒪r(a,b).

Claim 57.

𝒪r.A(a) iff 𝒪r.A(a).

Proof.

Assume 𝒪r.A(a). By the definition of 𝒪 (Definition 26), we have r𝒪{(a,cA)NI(𝒜)×Δ𝒪𝒪r.A(a)}. This means (a,cA)r𝒪. Also, by the definition of the canonical model, a𝒪=a and cAA𝒪, and therefore a𝒪(r.A)𝒪. This gives us 𝒪r.A(a).
Now assume 𝒪r.A(a). Then, a𝒪(r.A)𝒪. By the definition of the canonical model, either (1) there is bNI(𝒜) such that (a,b)r𝒪 and bA𝒪 or (2) there is cAΔu𝒪 such (a,cA)r𝒪 and cAA𝒪. In case (1), by the definition of 𝒪, we have that (a,b)r𝒪 means that 𝒪r(a,b). We also have that it is the case that bA𝒪. By the definition of the canonical model, this means that b{bNI(𝒜)𝒪A(b)}, so 𝒪A(b). By the semantics of , 𝒪r(a,b) and 𝒪A(b) implies 𝒪r.A(a). In case (2), by the definition of 𝒪, (a,cA)r𝒪 means that 𝒪r.A(a). Again by the definition of 𝒪, cAA𝒪 implies 𝒯AA. This gives us 𝒪r.A(a).

Claim 58.

𝒪A1A2B iff 𝒪A1A2B.

Proof.

Assume 𝒪A𝟏A𝟐B. We make a case distinction based on the elements in Δ𝒪:=NI(𝒜)Δu+𝒪.

  • aNI(𝒜): Assume a(A1A2)𝒪. This is the case iff aA1𝒪 and aA2𝒪. By the definition of 𝒪, this means 𝒪A1(a) and 𝒪A2(a). By assumption, this gives us 𝒪B(a), which, by the definition of 𝒪, means that aB𝒪. Therefore, 𝒪B(a). Since a was an arbitrary element in NI(𝒜), this holds for all elements of this kind.

  • cDΔu+𝒪: Assume cD(A1A2)𝒪. This means cDA1𝒪 and cDA2𝒪. By the definition of 𝒪, this gives us that 𝒯DA1 and 𝒯DA2. By assumption, this means 𝒯DB. But, by the definition of 𝒪, this means cDB𝒪. Since cD was an arbitrary element in Δu+𝒪, this argument can be applied for all elements of this kind.

We have thus shown that, for all elements d in Δ𝒪, if d(A1A2)𝒪 then dB𝒪. So 𝒪A1A2B.
Now, assume 𝒪⊧̸A𝟏A𝟐B. We show that 𝒪⊧̸A1A2B by showing that cA1A2(A1A2)𝒪 but cA1A2B𝒪. By definition of 𝒪, cA1A2Ai𝒪 since 𝒯A1A2Ai (trivially), where i{1,2}. Then, by the semantics of , cA1A2(A1A2)𝒪. We now argue that cA1A2B𝒪. This follows again by the definition of 𝒪 and the assumption that 𝒪⊧̸A1A2B, since the definition means that cDB𝒪 iff 𝒪DB and we can take D=A1A2.

Claim 59.

𝒪r.BA iff 𝒪r.BA.

Proof.

Assume 𝒪r.BA. We make a case distinction based on the elements in Δ𝒪:=NI(𝒜)Δu+𝒪.

  • aNI(𝒜): Assume a(r.B)𝒪. In this case, by definition of 𝒪, either (1) there is bNI(𝒜) such that (a,b)r𝒪 and bB𝒪 or (2) there is cBΔu𝒪 such that (a,cB)r𝒪 and cBB𝒪. In case (1), by definition of 𝒪, (a,b)r𝒪 implies that 𝒪r(a,b). Also, bB𝒪 implies that 𝒪B(b). Together with the assumption that 𝒪r.BA, this means that 𝒪A(a). Again by definition of 𝒪, we have that aA𝒪. In case (2), by definition of 𝒪, (a,cB)r𝒪 implies that 𝒪r.B(a). Also, by definition of 𝒪, cBB𝒪 implies that 𝒯BB. Then, 𝒪r.B(a). By assumption 𝒪r.BA, which means that 𝒪A(a). Again by definition of 𝒪, we have that aA𝒪. Since a was an arbitrary element in NI(𝒜), this argument can be applied for all elements of this kind.

  • cDΔu+𝒪: Assume cD(r.B)𝒪. In this case, by definition of 𝒪, either (1) there is cBΔu𝒪 such that (cD,cB)r𝒪 and cBB𝒪 or (2) D is of the form s.B, (cD,cB)r𝒪, cBB𝒪, and 𝒯sr. In case (1), by definition of 𝒪, 𝒯DA and 𝒯Ar.B. Again by definition of 𝒪, cBB𝒪 implies 𝒯BB. This means that 𝒯Dr.B. By assumption 𝒪r.BA, which means 𝒯r.BA. Then, 𝒯DA. By definition of 𝒪, we have that cDA𝒪. In case (2), we have that 𝒯Dr.B since D is of the form s.B and 𝒯sr. Also, as cBB𝒪, by definition of 𝒪, 𝒯BB. Then, 𝒯Dr.B. By assumption, 𝒪r.BA, which then means that 𝒯DA. By definition of 𝒪, we have that cDA𝒪. Since cD was an arbitrary element in Δu+𝒪, this argument can be applied for all elements of this kind.

We have thus shown that, for all elements d in Δ𝒪, if d(r.B)𝒪 then dA𝒪. So 𝒪r.BA.
Now, assume 𝒪⊧̸r.BA. We show that 𝒪⊧̸r.BA by showing that cr.B(r.B)𝒪 but cr.BA𝒪. By the definition of 𝒪, (cs.B,cB)r𝒪 if 𝒯sr, which is trivially the case for s=r, and cBB𝒪 by definition of 𝒪. We now argue that cr.BA𝒪. By definition of 𝒪, an element of the form cD is in A𝒪 iff 𝒯DA. By assumption 𝒪⊧̸r.BA which means 𝒯⊧̸r.BA. So cr.B is not in A𝒪.

Claim 60.

𝒪Ar.B iff 𝒪Ar.B.

Proof.

Assume 𝒪Ar.B. We make a case distinction based on the elements in Δ𝒪:=NI(𝒜)Δu+𝒪.

  • aNI(𝒜): Assume aA𝒪. By definition of 𝒪, we have 𝒪A(a). By assumption 𝒪Ar.B, so 𝒪r.B(a). Then, by definition of 𝒪, (a,cB)r𝒪. Again by definition of 𝒪, we have cBB𝒪. So a(r.B)𝒪. Since a was an arbitrary element in NI(𝒜), the argument golds for all similar elements.

  • cDΔu+𝒪: Assume cDA𝒪. By definition of 𝒪, we have that 𝒯DA. By assumption, 𝒪Ar.B which means 𝒯Ar.B. Then, by definition of 𝒪, (cD,cB)r𝒪. Again by definition of 𝒪, we have that cBB𝒪. So cD(r.B)𝒪. Since cD was an arbitrary element in Δu+𝒪, this argument holds for all similar elements.

We have thus shown that, for all elements d in Δ𝒪, if dA𝒪 then d(r.B)𝒪. This means that 𝒪Ar.B.
Now, assume 𝒪⊧̸Ar.B. We show that 𝒪⊧̸Ar.B by showing that cAA𝒪 but cA(r.B)𝒪. By definition of 𝒪, we have that {cDΔu+𝒪|𝒯DA}A𝒪. For D=A we trivially have that 𝒯AA, so cAA𝒪. We now show that cA(r.B)𝒪. Suppose this is not the case and there is some element dΔ𝒪 such that (cA,d)r𝒪 and dB𝒪. By definition of 𝒪, this can happen iff d is of the form cB in Δu𝒪 and, moreover, 𝒯AA and 𝒯Ar.B for some ANC(𝒪). We now argue d=cBB𝒪 implies 𝒯BB. By definition of 𝒪, cBB𝒪 iff 𝒯BB. Since 𝒯AA and 𝒯Ar.B, we have 𝒯Ar.B, which means 𝒪Ar.B. This contradicts our assumption that there is some element dΔ𝒪 such that (cA,d)r𝒪 and dB𝒪. Thus, cA(r.B)𝒪, as required.

Claim 61.

𝒪rs iff 𝒪rs.

Proof.

Assume 𝒪rs. We make a case distinction based on the elements in Δ𝒪 and how they can be related in the extension of a role name in the definition of 𝒪.

  • (a,b)NI(𝒜)×NI(𝒜): Assume (a,b)r𝒪. We first argue that in this case 𝒪r(a,b). By definition of 𝒪, (a,b)r𝒪 iff 𝒪r(a,b). Since by assumption 𝒪rs we have that 𝒪s(a,b), so (a,b)s𝒪. Since (a,b) was an arbitrary pair in NI(𝒜)×NI(𝒜), the argument can be applied for all such kinds of pairs.

  • (a,cB)NI(𝒜)×Δu𝒪: Assume (a,cB)r𝒪. We first argue that in this case 𝒪r.B(a). By definition of 𝒪, we have that (a,cB)r𝒪 iff 𝒪r.B(a). By assumption 𝒪rs. So 𝒪s.B(a). Then, again by definition of 𝒪, we have that (a,cB)s𝒪. Since (a,cB) was an arbitrary pair in NI(𝒜)×Δu𝒪, this argument can be applied for all such kinds of pairs.

  • (cD,cB)Δu+𝒪×Δu𝒪: Assume (cD,cB)r𝒪. In this case, by definition of 𝒪, either (1) 𝒯DA and 𝒯Ar.B, for some ANC(𝒪), or (2) D is of the form s.B and 𝒯sr. In case (1), since by assumption 𝒪rs, we have that 𝒯DA and 𝒯As.B, for some ANC(𝒪). Then, by definition of 𝒪, it follows that (cD,cB)s𝒪. In case (2), since 𝒯sr and by assumption 𝒪rs (which means 𝒯rs), we have that 𝒯ss. Then, again by definition of 𝒪, as in this case D is of the form s.B, it follows that (cD,cB)s𝒪. Since (cD,cB) was an arbitrary pair in Δu+𝒪×Δu𝒪, this argument can be applied for all such kinds of pairs.

We have thus shown that 𝒪rs.
Now, assume 𝒪⊧̸rs. We show that 𝒪⊧̸rs. By definition of 𝒪, we have that {(cs.B,cB)Δu+𝒪×Δu𝒪𝒯sr}r𝒪. By taking B= and s=r (and since trivially 𝒯rr), we have in particular that (cr.,c)r𝒪. We now argue that (cr.,c)s𝒪. By definition of 𝒪, a pair of the form (cs.B,cB) is in s𝒪 iff 𝒯ss. By assumption 𝒪⊧̸rs, which means 𝒯⊧̸rs. So the pair (cr.,c) is not in s𝒪.

This finishes our proof.

Lemma 62.

Let 𝒪 be a normalized ontology and let 𝒪 be the canonical model of 𝒪 (Definition 26). The 𝖽-dimensional -geometric interpretation of 𝒪 (Definition 21) is a strongly TBox faithful model of 𝒪.

Proof.

From Theorem 27, if τ is an CI in normal form or an role inclusion over 𝗌𝗂𝗀(𝒪), then 𝒪τ iff 𝒪τ. Since, by Lemma 53 it is the case that CD iff ηCD (where C and D are arbitrary concepts) and by Lemma 54 it is the case that rs iff ηrs (with r,s𝖭𝖱), we have that τ iff η𝒪τ, where τ is a TBox axiom in normal form. This gives us η𝒪τ iff 𝒪τ for any normalized TBox axiom.

See 28

Proof.

This result follows from Lemmas 52 and 62.

Lemma 63.

For all rNR, all a,bNI, it is the case that ηr(a,b) iff ηr(a,b).

Proof.

We know that ηr(a,b) iff it is true that η(a)η(b)η(r). From the definition of η we know η(a)η(b)=η(a)η(b). Since μ(d) is binary for any d, we have η(a)η(b) is binary. From Corollary 7, we have η(a)η(b)η(r), which, by the definition of satisfaction is the case iff ηr(a,b).

Lemma 64.

For any vector v, such that v is a result of the mapping in Definition 19, if vη(A), then v[A]=1.

Proof.

By the definition of η and that of convex hull, for all v, it holds that vη(A) means λi0λi1 such that v=i=1nviλi, with viη(A). By the definition of η, it is true that viη(A) is the case iff vi[A]=1, for all 1in. By the definition of convex hull, this means v[A]=1.

Lemma 65.

For all IQs in normal form α, it is the case that ηα iff ηα.

Proof.

If α is a role assertion the Lemma follows from Lemma 63. Now, we will consider the remaining cases. Let A,BNC be concept names, and aNI be an individual name. We make a case distinction and divide the proof into claims for readability.

Claim 66.

Case 1: ηA(a) iff ηA(a).

Proof.

Assume ηA(a). By the semantics of geometric interpretation, η(a)η(A). By the definition of μ, it is the case that η(a) is binary and, by the definition of η, it is the case that η(a)=η(a). From Corollary 7 we get that η(a)η(A), which is the case iff ηA(a).
Now assume ηA(a). This means η(a)η(A). By definition of η, we know η(a)=η(a), and by Proposition 5 we know η(A)η(A). By assumption, η(a)η(A). By the semantics of geometric interpretation, this means ηA(a).

Claim 67.

Case 2: η(r.A(a)) iff η(r.A(a)).

Proof.

Assume ηr.A(a). By the semantics of η, we have that η(a)η(r.A). By the definition of η, we know η(a)=η(a). Also, by construction of μ, it is the case that η(a) is binary. If there is a binary vη(A) such that η(a)vη(r) then we are done. In this case, by Corollary 7, we have that vη(A) and η(a)vη(r). This means, by the semantics of η, that ηr.A(a).
Otherwise, for all vη(A) such that η(a)vη(r) we have that v is non-binary (and, moreover, such v exists). We rename this vector to z, giving us z=η(a)vη(r). This means that z=i=1nviλi, such that λi with 0λi1 and i=1nλi=1, and it also means that v1,,vnη(r). For clarity, we call the vector on the left-hand side of the concatenation operation its prefix 𝗉𝗋𝖾𝖿(x), and the one on the right-hand side its suffix 𝗌𝗎𝖿(x). For example, regarding the vector z2𝖽 renamed above, we have 𝗉𝗋𝖾𝖿(z)=η(a)𝖽 and 𝗌𝗎𝖿(z)=v𝖽.

We now need to demonstrate that zη(r.A(a)). We show that (1) 𝗉𝗋𝖾𝖿(z)[a]=1, (2) 𝗉𝗋𝖾𝖿(z)[r,e]=1, and (3) 𝗌𝗎𝖿(z)[A]=1.

  1. 1.

    We now argue that, for any viη(r) such that i=1nviλi = z, it must be the case that 𝗉𝗋𝖾𝖿(vi)=η(a). This is because η(a) cannot be written as a convex combination of vectors w(η(r){η(a)vv𝖽}) such that 𝗉𝗋𝖾𝖿(vi)=i=1nwiλk. If this was the case, every w would have 𝗉𝗋𝖾𝖿(w)[a]=0, which, multiplied by any λi, would of course still result in 𝗉𝗋𝖾𝖿(w)[a]=0, contradicting the fact that z=η(a)v. Since we know 𝗉𝗋𝖾𝖿(z)=η(a), we have that 𝗉𝗋𝖾𝖿(z)[a]=1.

  2. 2.

    We now argue that 𝗉𝗋𝖾𝖿(z)[r,e]=1. By Lemma 48, we know that, for viη(r), there are d,eΔ such that 𝗉𝗋𝖾𝖿(vi)=μ(d), 𝗌𝗎𝖿(vi)=μ(e), and (d,e)r, which, by the definition of μ, gives us 𝗉𝗋𝖾𝖿(vi)[r,e]=1.

  3. 3.

    From the fact we have assumed vη(A) and v=𝗌𝗎𝖿(z), we know that 𝗌𝗎𝖿(z)=i=1nviλi with viη(A). As vη(A), we get from Lemma 64 that 𝗌𝗎𝖿(z)[A]=1.

From these facts, we have that for z=i=1nviλi, it is true that 𝗉𝗋𝖾𝖿(z)[a]=1, that 𝗉𝗋𝖾𝖿(z)[r,e]=1, and that 𝗌𝗎𝖿(z)[A]=1. By definition of η, this means 𝗉𝗋𝖾𝖿(z)=η(a), that zη(r), and that 𝗌𝗎𝖿(z)=vη(A). Finally, by the semantics of η, we have ηr.A(a).
Now assume ηr.A(a). By the semantics of η, this means η(a)η(r.A). We know, by the definition of η, that η(a) = η(a), and therefore it is binary. Now, η(a)η(r.A) means η(a)vη(r) and vη(A). Since η(a)vη(r), this means it is a binary vector, and by Proposition 5, it gives us η(a)vη(r). Since v itself is binary and vη(A), again by Proposition 5, we have vη(A). This means, by the semantics of η, that ηr.A(a).

Claim 68.

Case 3: ηAB(a) iff ηAB(a)

Assume ηAB(a). By the semantics of geometric interpretation, this means η(a)η(A) and η(a)η(B). By the definition of η, it is the case that η(a)=η(a), and it is therefore binary. But, by Corollary 7 this means η(a)η(A) and η(a)η(B). This means η(a)η(A)η(B), which gives us ηAB(a).

Now assume ηAB(a). This means η(a)η(A) and η(a)η(B). By definition of η we have η(a)=η(a), and by Proposition 5 we have η(a)η(A) and η(a)η(B). This means η(a)η(A)η(B), giving us ηAB(a). This finishes our proof.

Lemma 69.

Let 𝒪 be a normalized ontology and 𝒪 be the canonical model of 𝒪. The geometrical interpretation η𝒪 of 𝒪 is strongly IQ faithful with respect to 𝒪. That is, 𝒪α iff η𝒪α, where α is an IQ in normal form.

Proof.

Since 𝒪 is canonical, 𝒪α iff 𝒪α. By Lemma 52, we know 𝒪α iff η𝒪α. By Lemma 65, we have that if α is an IQ in normal form then ηα iff ηα. This means η𝒪α iff η𝒪α. Hence, η𝒪α iff 𝒪α.

Lemma 70.

For all C,D, it is the case that CD iff ηCD, where CD is a TBox axiom.

Proof.

Let C,D be concepts. We prove the statement in two directions.

Assume CD. By Lemma 53, we know CD iff ηCD, which means η(C)η(D). By Proposition 5, this implies η(C)η(D). Finally, by the definition of satisfaction, this is the case iff ηCD. Now assume ηCD. Then, by the semantics of geometric interpretation, η(C)η(D). This means if vη(C), then vη(D), with v=i=1nλivi and v1,,vnη(C). So, assume C is non-empty. Then, there is dC, which, by Lemma 49 is the case iff μ(d)η(C). By the definition of convex hull, μ(d)η(C). By assumption, μ(d)η(D), and since μ(d) is binary, Corollary 7 gives us that μ(d)η(D). But again by Lemma 49, this is the case iff dD. Since d was arbitrary, we have CD.

Lemma 71.

For all r,sNR, it is the case that rs iff ηrs.

Proof.

First, assume rs. By Lemma 54, we know rs iff ηrs, which means η(r)η(s). By Proposition 5, this implies η(r)η(s), which, by the definition of satisfaction is the case iff ηrs.

Assume ηrs. Then, by the semantics of geometric interpretation, η(r)η(s), which means if vη(r), then vη(s), where v=i=1nλivi for v1,,vnη(r). Assume r is non-empty. Then, there must be (d,e)r. We must now show (d,e)s is true. Since (d,e)r, by the definition of η, we have μ(d)μ(e)η(r) with both μ(d) and μ(e) being binary vectors. By the definition of convex hull, μ(d)μ(e)η(r). Now, by assumption, μ(d)μ(e)η(s), but since μ(d)μ(e) is binary, by Corollary 7 we have that μ(d)μ(e)η(s). By definition of η, we have that μ(d)[s,e]=1. By definition of μ, for all d such that μ(d)=μ(d) we have that (d,e)s. In particular, this holds for d=d. So (d,e)s. We have shown that if (d,e)r, then (d,e)s, which is the case iff rs.

See 31

Proof.

The result for IQs in normal form follows from Lemma 65; the one for concept inclusions follows from Lemmas 53 and 70; and the one for role inclusion follows from Lemma 54 and from Lemma 71.

Lemma 72.

Let 𝒪 be a normalized ontology and let 𝒪 be the canonical model of 𝒪 (Definition 26). The 𝖽-dimensional convex -geometric interpretation of 𝒪 (Definition 29) is a strongly TBox faithful model of 𝒪. That is, 𝒪τ iff η𝒪τ, where τ is either a concept inclusion in normal form or a role inclusion.

Proof.

Theorem 27 implies that if τ is an CI in normal form or an RI then 𝒪τ iff 𝒪τ. From Lemma 70, we know ηCD iff CD, and by Lemma 71 we get that ηrs iff rs. This means that if τ is an CI in normal form or an RI then 𝒪τ iff η𝒪τ.

See 32

Proof.

The theorem follows from Lemmas 69 and 72.

A.4 Omitted proofs for Section 6

See 35

Proof.

Algorithm 1 has four main parts that are never executed in the same run, each corresponding to one of the normal forms that the input concept inclusion α can take.

α=AB:

In this case, the algorithm will execute lines 23. From assumption 1, line 3 spends time O(1) and by assumption 3 this line is run O(|Δ|) times. Hence, in this case, the algorithm consumes time O(|Δ|).

α=A1A2B:

From assumption 3, the loop from lines 56 is executed O(|Δ|) times. Each iteration consumes time O(1) by assumption 1. Thus, Algorithm 1 runs in time O(|Δ|) in this case.

α=Ar.B:

According to assumption 3, the nested loop from lines 811 uses time O(|Δ||Δ|). The membership check in line 10 takes time O(𝖽|Δ||Δ|), by assumption 4. Therefore, we get that Algorithm 1 requires time O(𝖽𝗇4), where 𝗇=|Δ|.

α=r.AB:

Algorithm 1 will execute from lines 1415 for CIs in this normal form. Each iteration of the for loop starting in line 14 consumes constant time according to assumption 1. Furthermore, the loop has O(|Δ||Δ|) iterations due to assumption 3. Hence, Algorithm 1 uses time O(|Δ||Δ|) for CIs in this normal form.

Therefore, Algorithm 1 consumes time O(𝖽𝗇4).

See 36

Proof.

We consider each the four forms that an IQ in normal form α can assume separately. In each of them a𝖭𝖨, A,B𝖭𝖢, and r𝖭𝖱.

α=A(a):

Due to assumptions 1 and 2, line 2 uses time O(1).

α=(AB)(a):

As in the previous case, the assumption 1 and 2 imply that line 4 executes in time O(1).

α=(r.A)(a):

By assumption 3, line 7 is run O(|Δ|) times, each iteration consuming time in O(𝖽|Δ||Δ|) (from assumptions 2 and 4). Therefore, Algorithm 2 spends time O(𝖽𝗇3) in such instance queries, where 𝗇=|Δ|.

α=r(a,b):

line 9 runs in time O(𝖽|Δ||Δ|) due to assumptions 2 and 4.

Therefore, Algorithm 2 consumes time O(𝖽𝗇3).

See 37

Proof.

There are O(|Δ||Δ|) iterations of the for loop starting in line 1 in a single run of Algorithm 3 as a consequence of the assumption 3. Additionally, each iteration consumes time O(𝖽|Δ||Δ|) by assumption 4. Therefore, Algorithm 3 runs in time O(𝖽𝗇4), where 𝗇=|Δ|.