The process of reusing an ontology involves two issues: (1) selecting a set of terms from the ontology vocabulary; and (2) using the ontology constraints to derive those that apply to such terms. The first issue corresponds to the familiar practice of importing namespaces. This paper proposes to address the second issue by introducing a set of operations over ontologies, treated as theories and not just as vocabularies. It discusses how to compute the operations for a class of ontologies built upon DL-Lite core with arbitrary number restrictions. Finally, for this class of ontologies, the paper addresses the question of minimizing the set of constraints which results from an operation.
We introduce a set of concepts and procedures that promote constraint reuse in
ontology design. We start by introducing a set of operations on ontologies that create new
ontologies, including their constraints, out of other ontologies. Such operations extend
the idea of namespaces to take into account constraints and treat ontologies as
theories. Then, we concretely show how to compute the operations when the ontologies
are built upon DL-Lite core with arbitrary number restrictions [
The development in the paper adopts the machinery to handle constraints
developed in [
The paper is organized as follows. Section 2 presents the formal definition of the operations. Section 3 shows how to compute the operations for lightweight ontologies. Section 4 addresses the question of minimizing the set of constraints that result from an operation. Finally, Section 5 contains the conclusions.
The definition of the operations depends only on the notion of theory, which we
introduce in the context of Description Logic (DL) [
A DL language L is characterized by a vocabulary V, consisting of a set of atomic concepts, a set of atomic roles, and the bottom concept . The sets of concept descriptions and role descriptions of V depend on the specific description logic. An inclusion of V is an expression of the form u ⊑ v, where u and v both are concept descriptions or both are role descriptions.
An interpretation s of V consists of a nonempty set s, the domain of s, and an
interpretation function, also denoted s, with the usual definition [
Let be an inclusion of V and be a set of inclusions of V. We say that: s satisfies or s is a model of , denoted s ⊨ , iff s(u) s(v); s satisfies or s is a model of , denoted s ⊨ , iff s satisfies all inclusions in ; logically implies , denoted ⊨ , iff any model of satisfies ; is satisfiable or consistent iff there is a model of ; is strongly consistent iff is consistent and does not logically imply A ⊑ , for some atomic concept A.
The theory of a set of inclusions of V, denoted [], is the set of all inclusions of V which are logical consequences of .
We are specially interest in DL-Lite core with arbitrary number restrictions [
We use the following abbreviations: “⊤” for “” (universal concept), “p” for “( 1 p)” (existential quantification), “( n p)” for “( n+1 p)” (at-most restriction) and “u | v” for “u ⊑ v” (disjunction). By an unabbreviated expression we mean an expression that does not use such abbreviations.
Finally, an ontology is a pair O=(V,) such that V is a finite vocabulary, whose atomic concepts and atomic roles are called the classes and properties of O, respectively, and is a finite set of inclusions of V, called the constraints of O. A lightweight ontology is an ontology whose constraints are inclusions of DL - LitecNore .
From this point on, we will use the terms class, property and constraint instead of atomic concept, atomic role and inclusion, whenever reasonable.
We define the following operations over ontologies.
Definition 1: Let O1 = (V1,1) and O2 = (V2,2) be two ontologies, W be a subset of V1 and be a set of constraints over V1. (i) The selection of O1 = (V1,1) for , denoted [](O1), returns the ontology
OS = (VS ,S), where VS = V1 and S = 1 . (ii) The projection of O1 = (V1 ,1) over W, denoted [W](O1), returns the ontology OP = (VP,P), where VP = W and P is the set of constraints in [1] that use only symbols in W. (iii) The union of O1 = (V1 ,1) and O2 = (V2 ,2), denoted O1 O2, returns the ontology OU = (VU ,U), where VU = V1 V2 and U = 1 2. (iv) The intersection of O1 = (V1 ,1) and O2 = (V2 ,2), denoted O1 O2, returns the ontology ON = (VN ,N), where VN = V1 V2 and N = [1] [2]. (v) The difference of O1 = (V1 ,1) and O2 = (V2 ,2), denoted O1 O2, returns the ontology OD = (VD ,D), where VD = V1 and D = [1] [2].
Note that selections can be defined as unions. We also observe that the ontology that results from each operation is unique. However, the set of constraints of the resulting ontology is not necessarily minimal, a point elaborated in Section 4. 2.3
An Example
The Music Ontology (MO) [
Figure 1 shows the class hierarchies of MO rooted at classes foaf:Agent and foaf:Person. Let us focus on this fragment of MO.
We first recall that FOAF has two constraints, informally formulated as follows: each person has at most one name foaf:Person and foaf:Organization are disjoint classes Let V1 be the following set of terms from the FOAF and the XSD vocabularies: V1={ foaf:Agent, foaf:Person, foaf:Group, foaf:Organization, foaf:name, xsd:string } Let V2 contains the rest of the terms that appear in Figure 1: V2={ mo:MusicArtist, mo:CorporateBody, mo:SoloMusicArtist, mo:MusicGroup, mo:Label, mo:member_of }
Let O1=(V1,1) be the projection [V1](FOAF) of FOAF over V1. Let O2=(V2,2) be such that 2 contains just the inclusions over V2 shown in Figure 1: 2={ mo:SoloMusicArtist ⊑ mo:MusicArtist, mo:MusicGroup ⊑ mo:MusicArtist, mo:Label ⊑ mo:CorporateBody }
Then, most of Figure 1 is captured by the union O3=(V3,3) of O1 and O2. The rest of Figure 1 is obtained by the selection [5](O3) of O3, where 5={ mo:SoloMusicArtist ⊑ foaf:Person, mo:MusicGroup ⊑ foaf:Group, mo:CorporateBody ⊑ foaf:Organization, (1 mo:member_of) ⊑ foaf:Person, (1 mo:member_of) ⊑ foaf:Group } where the last two constraints indicate that the domain and range of mo:member_of are foaf:Person and foaf:Group, respectively.
Finally, we construct O0=(V0,0), the ontology that corresponds to Figure 1, in two different, albeit equivalent ways: (1) O0 = [5]( [V1](FOAF) O2 ) , using the selection operation (2) O0 = (( [V1](FOAF) O2 ) O5 ) , eliminating the selection operator
We stress that the expression of the right-hand side of Eq. (1) (or Eq. (2)) provides an explanation of how O0 is constructed from FOAF and additional terms and constraints.
owl:disjointWith 3. Computing the Operations over Lightweight Ontologies
This section introduces the concept of constraint graphs, which leads to procedures to compute the operations over lightweight ontologies.
We say that the complement of a basic concept description e is e, and vice-versa. If c is a concept description, then c denotes the complement of c.
Let be a set of (unabbreviated) inclusions and be a set of (unabbreviated)
concept descriptions. The notion of constraint graphs [
Definition 2: The labeled graph g(,)=(,,) that captures and , where labels each node with a concept description, is defined as follows: (i) For each concept description e that occurs on the right- or left-hand side of an inclusion in , or that occurs in , there is exactly one node in labeled with e. If necessary, the set of nodes is augmented with new nodes so that: (a) For each atomic concept C, there is one node in labeled with C. (b) For each atomic role P, there is one node in labeled with (1 P) and one node labeled with (1 P). (ii) If there is a node in labeled with a concept description e, then there must be exactly one node in labeled with e . (iii) For each inclusion e ⊑ f in , there is an arc (M,N) in , where M and N are the nodes labeled with e and f, respectively. (iv) If there are nodes M and N in labeled with (m p) and (n p), where p is either P or P and m<n, then there is an arc (N,M) in . (v) If there is an arc (M,N) in , where M and N are the nodes labeled with e and f respectively, then there is an arc (K,L) in , where K and L are the nodes labeled with f and e , respectively.
(vi) These are the only nodes and arcs of g(). Definition 3: The labeled graph G(,)=(,,) that represents and , where labels each node with a set of concept descriptions, is defined from g(,) by collapsing each strongly connected component of g(,) into a single node labeled with the descriptions that previously labeled the nodes in the strongly connected component. When is the empty set, we simply write G() and say that the graph represents .
If a node K of G(,) is labeled with e, then K denotes the node labeled with e , and K→M indicates that there is a path in G(,) from K to M.
Definition 4: Let G(,)=(,,) be the labeled graph that represents and . We say that a node K of G(,) is a -node with level n, for a non-negative integer n, iff one of the following conditions holds: (i)
K is is a -node with level 0 iff
a. K is labeled with , or
b. there are nodes M and N, not necessarily distinct from K, and a basic
concept description h such that M and N are labeled with h and h, and
K→M and K→N.
(ii) K is is a -node with level n+1 iff
a. There is a -node M of level n, distinct from K, such that K→M, and M is
the -node with the smallest level such that K→M, or
b. K is labeled with a minCardinality constraint of the form (1 P) (or of the
form (1 P)) and there is a -node M of level n, distinct from K, such
that M is labeled with (1 P) (or with (1 P)), and M is the -node with
the smallest level labeled with (1 P) or (1 P).
Definition 5: Let G(,)=(,,) be the labeled graph that represents and . Let K
be a node of G(,). We say that K is a -node iff K is a -node with level n, for
some non-negative integer n. We also say that K is a ⊤-node iff K is a -node.
Theorem 1 shows how to test logical implication for DL - LitecNore inclusions [
V0 = { foaf:Agent, foaf:Person, foaf:Group, foaf:Organization, mo:MusicArtist, mo:CorporateBody, mo:SoloMusicArtist, mo:MusicGroup, mo:Label, mo:member_of, foaf:name, xsd:string } and the set of constraints 0 shown in Table 2. Figure 3 depicts the graph G(0) that represents 0 (using unabbreviated constraints). (2foaf:name)
(2 foaf:name) (1 mo:member_of) (1 foaf:name) (1)foaf:name) (1 mo:member_of) mo:SoloMusicArtist foaf:Person
Let O1=(V1,1) and O2=(V2,2) be two lightweight ontologies and W be a subset of V1. We say that O1=(V1,1) and O2=(V2,2) are equivalent iff V1=V2 and [1]=[2].
Given O1=(V1,1) and W, procedure Projection (in Figure 4) generates 2, based on the representation graph of 1, so that O2=(W,2) is equivalent to the projection of O1=(V1,1) over W. Based on Theorem 1, Projection generates all constraints that involve only symbols in W and that are logical consequences of 1. However, it avoids generating both e ⊑ f and f ⊑ e , which are equivalent. We note that Projection is non-deterministic since the set of constraints generated depends on the order that the for-loop selects pairs of nodes of G(1), which is not unique.
The above argument can be generalized into a correctness proof of the Projection procedure, in the following sense. Let 1 /W denote the set of formulas that use only classes and properties in W and that are logically implied by 1.
Theorem 2: Let O1=(V1,1) be an ontology and W be a subset of V1. Let 2 be the set of constraints which Projection outputs for 1 and W. Then, 2 is logically equivalent to 1 /W.
Procedures to compute the selection, union, intersection and difference of ontologies can be likewise defined. Projection(V1 , 1 , W ; 2) input: a vocabulary V1 a set 1 of normalized constraints over V1 a subset W of V1 output: a set of constraints 2 begin Initialize 2 = ;
Construct G(1 ), the representation graph for 1; Mark all nodes of G(1) labeled with at least one expression
that uses only atomic concepts and atomic roles in W; for each node M of G(1) such that M is marked and M is a -node for each concept description e such that e labels M and e uses only classes and properties in W
add e ⊑ to 2; drop all -nodes and ⊤-nodes from G(1); for each node M of G(1) such that M is marked for each pair of concept descriptions e and f such that e and f label M and e and f use only classes and properties in W
add e f to 2;
for each pair of nodes M and N of G(1) /* compute the transitive closure */
if M and N are marked and there is a path from M to N in G(1)
then add e ⊑ f to 2 where
e and f are expressions that label nodes M and N, respectively, and
e and f use only classes and properties in W, and
e ⊑ f is an allowed DL-Lite core inclusion (in the sense of Section 2), and
f ⊑ e is not already in 2 /* to avoid redundant constraints */
end
return 2
4. Optimizing the Representation of Lightweight Ontologies
The procedures that implement each of the operations return a set of constraints that
may contain redundancies, since they work with the transitive closure of the
constraint graph (c.f. the procedure in Figure 4). Therefore, an interesting question
immediately arises: How to minimize the set of constraints of a lightweight ontology
(output by one such procedure)? We argue that this question is equivalent to finding
the minimum equivalent graph (MEG) of a graph G, defined as the graph G’ with the
minimum set of edges such that the transitive closures of G and G’ are equal. This
problem has a polynomial solution for acyclic graphs and is known to be NP-hard for
strongly connected graphs [
Let O1=(V1,1) be a lightweight ontology and G(1)=(,,) be the constraint graph for 1. In what follows, we outline how to construct a new set of constraints, 2, such that 2 is a minimal set and 1 and 2 are tautologically equivalent.
Recall that G(1) is acyclic and that each node of G(1) is labeled with a set of expressions that are equivalent.
Since G(1) is acyclic, we may construct a MEG G’=(,’,) of G(1)=(,,) in
polynomial time [
The apparent problem lies in the expressions that label each node of G(1). Indeed, by Definition 3, G(1) is defined from g(1) by collapsing each strongly connected component of g(1) into a single node labeled with the expressions that previously labeled the nodes in the strongly connected component. Thus, we would have to construct a MEG, G”, of each strongly connected component of g(1) and generate a set of constraints from G” as before. However, constructing a MEG of a strongly connected graph is NP-hard, as indicated before.
Recall that, for any two expressions e and f that label the same node of G(1), we have that 1 logically implies e f. From the point of view of an economical ontology description, for each strongly connected component of g(1), we suggest to construct a minimal set of equivalences which are tautologically equivalent to the inclusions that correspond to the arcs of g(1). But this new problem is equivalent to constructing a spanning tree T of each strongly connected component of g(1), which can be done in polynomial time. Then, for each edge {M,N} of T, add e f to 2, where e labels M and f labels N in g(1). If T has k nodes, we generate k-1 equivalences.
The final set of constraints, 2, contains a minimal set of inclusions, which correspond to the arcs of G’, and a minimal set of equivalences, which correspond to the edges of spanning trees of the strongly connected components of g(1). Finally, by construction, 1 and 2 will be tautologically equivalent.
In this paper, we introduced a set of concepts and procedures that promote constraint reuse in ontology design. We defined a set of operations that extend the idea of namespaces to take into account constraints and that treat ontologies as theories. We showed how to compute the operations when the ontologies are built upon DL-Lite core with arbitrary number restrictions. For such ontologies, we also showed how to minimize the set of constraints.
As for current work, from a formal perspective, we are extending the results to a
more expressive variant of DL-Lite core, considered in [