Computational ontologies of parthood, componenthood, and containment

1 Introduction

My car has components, for example, its engine, its oil pump, its wheels, etc. (See Figure 1.) Roughly, a component of an object is a proper part of that object which has a complete bona fide boundary (i.e., boundary that correspond discontinuities in reality) and a distinct function. Thus all components of my car are parts of my car, but my car has also parts that are not components. For example, the left side my car has neither a complete bona fide boundary nor a distinct function. My car is also a container. It contains the driver in the seat area and a tool box and a spare-tire in its trunk. Containment is here understood as a relation which holds between disjoint material objects when one object (the containee) is located within a space partly or wholly enclosed by the container. In this paper, we study formal properties of proper parthood, componenthood, and containment relations and demonstrate how they can be represented and distinguished from one other in formal ontologies expressed in languages of different expressive power.

At first sight, these three relations seem to have quite similar properties. All three are transitive and asymmetric. The screw-driver is contained in my tool box and the tool box is contained in the trunk of my car, therefore the screw-driver is contained in the trunk of my car. And if an object (e.g., a tool box) is contained in the trunk of my car, then the trunk of my car is not contained in that object. It is easy to see that the componenthood (See Figure 1) and proper parthood relations are also asymmetric and transitive. Due to their similarities these relations are not always clearly distinguished in ontologies such as, e.g., GALEN [Rogers and Rector, 2000] or SNOMED [Spackman, 2001].

∗ This work has been supported by the Wolfgang Paul Program of the Alexander von Humboldt Foundation, the EU Network of Excellence in Semantic Datamining, and the Volkswagen Foundation Project "Forms of Life".

However, there are important differences between these relations. There can be a container with a single containee (e.g., the screw-driver is the only tool in my tool box) but no object can have single proper part. Also the components of complex artifacts form tree-structures. Thus, two components share a component only when one is a sub-component of the other. (It is because components form tree structures that tree graphs of component structures can be given in assembly manuals.) The parthood relation does not have this property: The left half of my car and the bottom half of my car share the bottom left part of my car but they are not proper parts of each other.

Ontologies are tools for making explicit the semantics of terminology systems [Guarino, 1998]. In this paper we develop ontologies which explicate the distinct properties of proper parthood, componenthood and containment relations. These ontologies can be used to specify the meaning of terms such as 'proper-part-of', 'component-of', and 'contained-in'. We start by characterising important properties of binary relations and then study how these properties can be expressed both in ontological theories formulated in first order logic and in ontologies formulated in a description logic.

...

2 Binary relations

In this section, we define properties of binary relation structures that will be useful for distinguishing proper parthood, component-of, and containment relations.

2.1 R-structures

A R-structure is a pair, (∆,R), that consists of a non-empty domain ∆ and a binary relation ∅ ̸ = R ⊆ ∆ × ∆. We write R(x, y) to say that the binary relation R holds between the individuals x, y ∈ ∆, i.e., (x, y) ∈ R. We can define the following relations on ∆ in terms of R:

For a given R-structure, the defined relations R=, RO, or Ri may be empty or identical to R. For example, if R is the identity relation on ∆, i.e., R = {(x, x) | x ∈ ∆}, then R= = R = RO and Ri = ∅.

2.2 Properties of binary relations

An R-structure (∆, R) may have or lack the properties listed in Table 1. For example, for any ∆ the identity relation on ∆ is reflexive, symmetric and transitive. Moreover, for any (∆, R), RO is symmetric, Ri is intransitive, and R= is reflexive. As pointed out above, on their respective domains proper parthood, componenthood, and containment are asymmetric and transitive.

We say (∆,R) has the weak supplementation property (WSP) if and only if for all x, y ∈ ∆ if R(x, y) then there is a z ∈ ∆ such that R(z, y) but NOT RO(z, x). As an example of a relation that has the weak supplementation property, consider the proper parthood relation on the domain ∆S of spatial objects, (∆S, proper-part-of). In this structure proper-part-of O is the overlap relation. WSP tells us that if x is a proper part of y then there exists a proper part z of y that does not overlap x. For example, since the left side of my car is a proper part of my car there is some proper part of my car (e.g., the right side of my car) which is discrete from the left side of my car.

Another example of a structure that has the weak supplementation property is the componenthood relation on the domain of artifacts, (∆A, component-of). Here component-of O is the relation of sharing a component. WSP tells us that if x is a component of y then there exists a component z of y such that z and x do not have a common component. For example, since the engine of my car is a component of my car there is some component of my car (e.g., the body of my car) which does not have a component in common with the engine. (See Figure 1.)

Consider the structure (∆C, contained-in) with ∆C = {C1, C2, C3, C4, B1, B2} as depicted in Figure 2. The block B1 is immediately contained in the container C2 which in turn is immediately contained in the container C1. B1 is contained, but not immediately contained, in C1. Note that contained-in does NOT have the weak-supplementation property: B1 is the only entity contained in C2. Thus, every entity contained in C2 stands in the contained-inO relation to B1.

We say (R,∆) has the no-partial-overlap property (NPO) if and only if for all x, y ∈ ∆: if RO(x, y) then x = y or R(x, y) or R(y, x). The structure (∆A, component-of) has the NPO property. As a representative example consider the substructure of (∆A, component-of) depicted in Figure 1: Two distinct car components share a component only if one is a subcomponent of the other.

The structure (∆S, proper-part-of), on the other hand, does not have the no-partial-overlap property. As pointed out earlier, the left half of my car and the lower half of my car overlap partially. Note also that containment structures (domains with a containment relation) often do not have the NPO property: Consider the tool box in the trunk of my car. It is also contained in my car. My car and the trunk of my car share a containee (the tool box), i.e., contained-inO holds, but my car is not contained in the trunk of my car nor is the trunk contained in the car.

Containment structures are discrete. For example (∆C, contained-in) is up- and dn-discrete: if x is contained in y then either x is an immediately contained in y or (a) there exists a z such that x is an immediately contained in z and z is contained in y , and (b) there exists a z such that x is contained in z and z is immediately contained in y. Similarly, the structure (∆A, component-of) is discrete. If x is a component of y then either x is a immediate component of y or (a) there exists a z such that x is a immediate component of z and z is a component of y , and (b) there exists a z such that x is a component z and z is an immediate component of y. Again, Figure 1 is a representative example.

The structure (∆S, proper-part-of), is dense due to the existence of fiat parts (parts which lack a complete bona fide boundary) [Smith, 2001]. Consider my car and its proper parts. My car does not have an immediate proper part - Whatever proper part x we chose, there exists another slightly bigger proper part of my car that has x as a proper part.

(R,∆) has the single-immediate-successor property (SIS) if and only if no x ∈ ∆ can stand in the Ri relation to two distinct members of ∆. Again, a representative example is the component-of structure depicted in Figure 1. In the structure (∆S, proper-part-of) SIS trivially holds since this structure has the density property and no immediate proper parts exist. But note that containment structures often do not have the SIS property: Consider again the tool box in the trunk of my car. It is also contained in my car. My car and the trunk of my car are distinct immediate containers for my tool box.

(R,∆) has the no-single-immediate-predecessor property (NSIP) if and only if for all x, y ∈ ∆: if Ri(x, y) then there exists a z ∈ ∆ such that Ri(z, y) and not x = z. Again, the componenthood structure depicted in Figure 1 is a representative example for a structure that has the NSIP property. Again, in the structure (∆S, proper-part-of) NSIP is trivially true since no immediate proper parts exist. But containment structures like (∆C, contained-in) lack the NSIP property.

Given the properties in Table 1 we can classify Rstructures according to the properties of the relation R. In Table 2 we list classes of R-structures that will be useful for modelling proper parthood, componenthood, and containment relations.

Finally, note the following facts about R structures: (F1) If (∆,R) has the no-partial-overlap property then it has the single-immediate-successor property; (F2) If (∆,R) is finite and has the single-immediate-successor property then it has the no-partial-overlap property; (F3) If (∆,R) is up-discrete and has also the no-partial-overlap property, then (∆, R) has the weak-supplementation property if and only if it has the no-single-immediate-predecessor property; (F4) If (∆,R) is reflexive, then Ri = ∅.

2.3 Parthood-containment-component structures

The relations that we are interested in do not exist in separation but form complex structures involving more than one relation. The structure (∆,PP,CntIn,CmpOf) is a parthood-containment-component structure if and only if: (i) the substructure (∆,PP) is a parthood structure; (ii) (∆,CntIn) is a discrete partial ordering; (iii) (∆,CmpOf) is a component-of structure; and addition the following conditions hold:

• (iv) If CntIn(x, y) and PP(y, z) then CntIn(x, z);
• (v) If PP(x, y) and CntIn(y, z) then CntIn(x, z);
• (vi) If CmpOf(x, y) then PP(x, y);

As an example of a parthood-containment-component structure consider the set ∆ formed by all parts of my car and everything that is contained in my car. The substructure (∆, CmpOf ) is depicted partly in Figure 1.

(iv) ensures that parts are contained in the container of the whole, e.g., my head is part of my body and my body is contained in my car, so my head must also be contained in my car. (v) ensures that if a part of some whole contains something then so does the whole, e.g., since my tool box is contained in the trunk of my car and the trunk is part of my car, my tool box is also contained in my car. (vi) tells us that componenthood is a special case of parthood, e.g., since the engine is a component of my car, it is also a proper part of my car.

3 A formal ontology of parthood, containment, and componenthood

The formal theory developed in this section is presented in standard first-order predicate logic with identity. We use x, y, and z for variables. Leading universal quantifiers are generally omitted. Names of axioms begin with the capital letter 'A', names of definitions begin with the capital letter 'D', and names of theorems begin with the capital letter 'T'.

We include the primitive relation symbols PP, CntIn, and CmpOf in the language of our theory. The intended interpretations are the relations PP, CntIn, and CmpOf respectively of parthood-containment-component structures.

3.1 Axioms for PP

We introduce the symbols PP=, PPO, and define that PP= xy holds if and only if either PP xy or x and y are identical (DPP= ); PPO xy holds iff x and y share a common part or are identical (DPPO ).

We then include the axioms of asymmetry and transitivity (APP1-APP2) as well as an axiom (APP3) that ensures that interpretations of PP have the weak supplementation property (WSP).

The theory that includes APP1-3 as axioms is known as basic mereology [Simons, 1987]. Finally we add a density axiom to include fiat parts into our domain (APP4).

Models the the theory that includes APP1-4 as axioms are parthood structures as defined in Table 2.

3.2 Axioms for CmpOf

We introduce the symbols CmpOf = and CmpOf O and add the respective definitions (DCmpOf = and DCmpOf O ).

We then include an axiom of transitivity (ACP1).

Corresponding to (vi) we add an axiom that ensures that CmpOf xy implies PP xy (ACP2) and can then prove that CmpOf is asymmetric (TCP1).

We introduce the symbol CmpOf i and define CmpOf i xy to hold iff CmpOf i xy and there is no z such that CmpOf i xz and CmpOf i zy (DCmpOf i ). We then add an axiom that enforces that interpretations of CmpOf have the discreteness property (ACP3).

From DCmpOf i we can prove immediately that CmpOf i is intransitive (TCP2).

We then add axioms that require that CmpOf has the nopartial-overlap property (ACP4) and that CmpOf has the nosingle-immediate-predecessor property (ACP5).

We now can prove that the the weak-supplementation principle holds (TCP3) and that nothing has two distinct immediate successors (TCP4).

TCP3 CmpOf xy → (∃z)(CmpOf zy ∧ ¬CmpOf O zx) TCP4 CmpOf i xz1 ∧ CmpOf i xz2 → z1 = z2

3.3 Axioms for CntIn

We introduce the symbols CntIn=, CntInO, and CntIni and add the respective definitions (DCntIn= , DCntInO , and DCntIni ).

DCntIn= CntIn= xy ≡ CntIn xy ∨ x = y DCntInO CntInO xy ≡ (∃z)(CntIn= zx ∧ CntIn= zy) DCntIni CntIni xy ≡ CntIn xy ∧ ¬(∃z)(CntIn xz ∧ CntIn zy)

We then include axioms of asymmetry, transitivity, and discreteness (ACT1-3).

We add axioms, corresponding to (iv) and (v), parts are contained in the container of the whole (ACT4) and that if a part contains something then so does the whole (ACT5).

We call the theory consisting of the axioms APP1-4, ACP15 and ACT1-5 FO-PCC. Parthood-composition-containment structures are models of this theory.

4 Representation in a description logic

Description Logics (DLs) are a family of logical formalisms which are significantly less powerful than first order logic but which are (relatively) easily implemented on the computer [Baader et al., 2002]. The task of this section is to investigate to what extent and how FO-PCC can be approximated by a theory expressed in a description logic. For this task, we consider DLs with different expressive capabilities, some of which are better suited than others for formulating properties of parthood, componenthood and containment relations. Notice, that it is not the purpose of this paper to provide a complexity analysis for these DLs.

4.1 The syntax and semantics of description logics

Basic expressions in description logics are concept and role descriptions. Concepts are interpreted as sets. Roles are interpreted as binary relations. General rules for forming concept and role descriptions (based on [Baader et al., 2002]) are given below. Note, however, that specific DLs typically allow for the formulation of some, but not all, of the complex concept and role descriptions listed.

Every concept name is a concept description (atomic concept), ⊤ is the top-concept. ⊥ is the bottom-concept. If C and D are concept descriptions then C ⊓ D (concept-intersection), C ⊔ D (concept-union), ∼ C (concept-complement) are also concept descriptions. Every role name, R, is a role description (an atomic role). If S and T are role descriptions, then S ⊓ T (role-intersection), S ⊔ T (role-union), ∼ S (rolecomplement), S◦T (role-composition), and R - (role-inverse) are also role descriptions. Id is the name of the identity role. If C is a concept description and R is a role name then (∃R.C), (∀R.C), and (= 1R) are concept descriptions. The semantics of the various constructors is given in Table 3.

A terminology is a set of terminological axioms of the form C . = D and S . = T (called equalities) or C ⊑ D and S ⊑ T (called inclusions), where C and D are concept descriptions and S and T are role descriptions. An interpretation I satisfies an inclusion C ⊑ D iff C I ⊆ D I and S ⊑ T iff S I ⊆ T I . (See [Baader et al., 2002].) It satisfies an equality C . = D iff C I =D I and S . = T iff S I = T I .

Table 3: Concept and role constructors with their semantics. I is the interpretation function and ∆ is the domain of individuals.

4.2 Stating ontological principles

Let LWSP be a language that includes at least the constructors (ia, iia, iii, via-c, vii, viii, ix [Table 3]). In this language we can state a DL-version of FO-PCC. In particular, if R is the name of a relation R then we are able to state in this language that R has the WSP property, we are able to define the relation Ri in terms of R, and we are able to state that R is a discrete (or dense) relation:

But since LWSP is undecidable [Schmidt-Schauß, 1989], it is important to identify less complex sub-languages of LWSP that are still sufficient to state axioms distinguishing parthood, componenthood, and containment relations. Otherwise the DL version of FO-PCC would have no computational advantages over the first order theory.

Let L be the DL which includes only the constructors (ia-b, iia, iii, vii, ix, and v [Table 3]) and in which the role composition operator (vii) only occurs in acyclic role terminologies with inclusion axioms of the form R ◦ R ⊑ R, S ◦ R ⊑ R, and R ◦ S ⊑ R. Unlike LWSP the DL L is decidable [Horrocks and Sattler, 2004].

If R is the name of the relation R then we are able to state in L that R is transitive (R ◦ R ⊑ R). Moreover, in L we can very naturally represent DL-versions of the axioms ACP2 and ACT4-5. Unfortunately, in L we are not able to state either that R asymmetric, that R has the WSP property, or that R has the NPO property. Also we cannot state a DL-version of the definition of Ri in terms of R (as in def-i).

Let Ri be an undefined relation name interpreted as Ri in the R-structure (∆,R) (e.g., as contained-ini in a containment structure). In L we are able to use this additional primitive to say that R has the no-single-immediate-predecessor property (NSIP) and the single-immediate-successor property (SIS).

Notice however that, since we introduced Ri as an undefined relation name we do not know that the interpretation of Ri is an intransitive subrelation of R unless additional axioms are included in the theory. In L we can state that Ri is a subrelation of R but we cannot not say that Ri is intransitive. Notice also, that in L, we cannot say that R is irreflexive (R ◦ Id ⊑ ⊥) since L does not include a constructor for the identity relation.

Let L ∼Id⊔ be the DL obtained by extending L with the identity relation (viii), negation restricted to relation names (a restricted version of vic), and role union (vib). In this DL we can say that Ri is intransitive, that R is asymmetric, and that R has the NPO property.

Unfortunately, including role negation into a DL-language significantly increases the complexity of the underlying reasoning [Lutz and Sattler, 2000]. Though L ∼Id⊔ is less expressive than LWSP (we cannot state WSP or discreteness axioms or define Ri) it is an open question whether L ∼Id⊔ is decidable. (It is known though that ALC-DLs that include axioms of the form R ◦ S ⊑ T1 ⊔ . . . ⊔ Tn are undecidable [Wessel, 2001].)

4.3 Describing parthood-composition-containment structures in L

We chose L as the DL to formulate an approximation of FOPCC because L is decidable and does include the composition operator which is important for expressing interrelations between relation and for reasoning (particularly in biomedical ontologies) [Spackman, 2001; Rogers and Rector, 2000; Horrocks and Sattler, 2004].

We add the symbols CP, PP and CT as well as CPi, PPi and CTi to L. The intended interpretations of these symbols are the relations CmpOf , PP, CntIn, CmpOf i, PPi, and CntIni of parthood-composition-containment structures. We then include the following axioms for CP and PP:

For CT we include a subrelation axiom and a transitivity axiom:

We include also axioms A10-12 corresponding to (iv-vi) in Section 2.3.

We call the theory formed by A1-12 DL-PCC. The sub-theory formed by A1-4 is similar to the theories proposed in [Sattler, 2000] and [Lambrix and Padgham, 2000].

But, as discussed in the previous subsection, we are not able to add to DL-PCC the following axioms and definitions that are needed to constrain the models to parthoodcomposition-containment structures: (1) We are not able to state that CP, PP, and CT are asymmetric and irreflexive; (2) We are not able to state a discreteness axiom for CP or CT or a density axiom for PP; (3) We are not able to define CPi, PPi, and CTi in terms of CP, PP, and CT respectively; (4) We are not able to state the weak supplementation principle (WSP) for interpretations of PP.

Consider (1). Since DL-PCC lacks asymmetry axioms it admits models in which CP, PP, and CT are interpreted as reflexive relations. In those models CPi, PPi, and CTi are all interpreted as the empty relation (making the axioms A3, A4, and A7 trivially true). (See also F4 in Section 2.2.) For example the structure (∆C, identical-to) is a model of DLPCC (but not of FO-PCC) if we interpret CP, PP, and CT as identical-to and CPi, PPi, and CTi as ∅. Clearly, this model is not a parthood-component-containment structure.

Consider (3). We included CPi, PPi, and CTi as undefined primitives in DL-PCC and added axioms (A1, A5, and A8) that require their interpretations to be sub-relations of the interpretations of CP, PP, and CT. Unfortunately, DLPCC admits models in which PPi and PP are the same relation (similarly for CP and CPi or CT and CTi). Consider Figure 2 and interpret CP and CPi as the relation icr = {(C2,C1), (C3,C1)} (immediately-contained-in-theroot-container), and PP, PPi, CT, CTi all as contained-in. Then (∆C, contained-in, icr) is a model of DL-PCC (but not of FO-PCC). This particular kind of unintended interpretations of PPi and CTi can be avoided by requiring that the interpretation of these relations are intransitive. However in L we are not able to require that a given relation is intransitive.

Consider (4). The closest we can get to requiring that the interpretation of PP has the WSP property is to require that the NSIP property holds (axiom 7). However the NSIP property is strictly weaker than the WSP property. 1 Consequently, DL-PCC admits models that would have been rejected by a theory including an axiom that requires WSP for interpretations of PP (e.g. FO-PCC). Similar comments apply to (2).

These are strong limitations if the purpose of the presented theory is to serve as an ontology that specifies the meaning of the terms 'proper part of', 'component of' and 'contained in' rather than to support automatic reasoning in some specific and possibly finite domain. 2 If the DL L ∼Id⊔ is decidable we can get a better DL approximation of FO-PCC that is computationally tractable. But even a L ∼Id⊔ version of FO-PCC will fall short of FO-PCC in expressivity since we cannot state WSP for PP.

5 Conclusions

We studied formal properties of parthood, componenthood and containment relations. Since it is the purpose of an ontology to make explicit the semantics of terminology systems, it is important to explicitly distinguish relations such as proper parthood, componenthood, and containment. We demonstrated that first order logic has the expressive power required to distinguish important properties of these relations. In description logics like L several important properties of these relations cannot be specified.

DLs are best used as reasoning tools for specific tasks in specific domains (as suggested in [Sattler, 1995; 2000; Lambrix and Padgham, 2000]). DLs are not appropriate for formulating complex interrelations between relations. Thus we need to understand a computational ontology as consisting of two complementary components: (1) a DL based ontology that enables automatic reasoning and constrains meaning as much as possible and (2) a first order ontology that serves as meta-data and makes explicit properties of relations that cannot be expressed in computationally efficient description logics. The first order theory then can be used by a human being to decide whether or not the DL-ontology in question is applicable to her domain. Moreover, meta-data can also be used to write special-purpose programs that phrase knowledge bases and enforce the usage of relations in accordance to the meta-data.

1 NSIP entails WSP only in conjunction with discreteness and NPO. We cannot require that interpretations of PP are discrete or have the NPO property since then the proper parthood relation on the domain of spatial objects could not be an interpretation for PP.

2 If we constrain our models to finite domains then, for example, it is indeed sufficient to include (A3) and (A4) as axioms to require the WSP and the NPO properties for CP (F1-3).