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 [3]. We refer to such ontologies as lightweight ontologies. Finally, for lightweight ontologies, we show how to minimize the set of constraints.
The development in the paper adopts the machinery to handle constraints developed in [6] [7] [8], which uses DL-Lite core with arbitrary number restrictions [3]. Previous work by the authors [7] introduced the equivalent of the projection operation, but considered neither the other operations nor the question of optimizing the representation of the resulting ontologies.
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) [4].
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 [4]. We use s(u) to indicate the value that s assigns to an expression u of V.
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 [3], denoted
. The sets of basic concept descriptions, concept descriptions and role descriptions in this case are defined as follows:
If P is an atomic role, then P and P (inverse role) are role descriptions If u is an atomic concept or the bottom concept, and p is a role description, then u and ( n p) (at-least restriction, where n is a positive integer) are basic concept descriptions and also concept descriptions
, an inclusion of V is an expression of one of the forms u ⊑ v or u ⊑ v, where u and v both are basic concept descriptions. That is, an inclusion may contain a negated concept only on the right-hand side and it may not involve role descriptions.
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
. 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.
, returns the ontology O P = (V P , P ), where V P = W and P is the set of constraints in
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.
The Music Ontology (MO) [11] provides concepts and properties to describe artists, albums, tracks, performances, arrangements, etc. on the Semantic Web. It is used by several Linked Data sources, including MusicBrainz and BBC Music. The Music Ontology RDF schema uses terms from the Friend of a Friend (FOAF) [5] and the XML Schema (XSD) vocabularies, among others. We adopt the prefixes "mo:", "foaf:" and "xsd:" to respectively refer to these vocabularies.
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 V 1 be the following set of terms from the FOAF and the XSD vocabularies: V 1 ={ foaf:Agent, foaf:Person, foaf:Group, foaf:Organization, foaf:name, xsd:string } Let V 2 contains the rest of the terms that appear in Figure 1: V 2 ={ mo:MusicArtist, mo:CorporateBody, mo:SoloMusicArtist, mo:MusicGroup, mo:Label, mo:member_of Finally, we construct O 0 =(V 0 , 0 ), the ontology that corresponds to Figure 1, in two different, albeit equivalent ways:
We stress that the expression of the right-hand side of Eq. ( 1) (or Eq. ( 2)) provides an explanation of how O 0 is constructed from FOAF and additional terms and constraints.
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 [6] captures the structure of sets of constraints.
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. 2. Figure 3 depicts the graph G( 0 ) that represents 0 (using unabbreviated constraints).
and O 2 =(V 2 , 2 ) be two lightweight ontologies and W be a subset of V 1 .
We say that
and W, procedure Projection (in Figure 4) generates 2 , based on the representation graph of 1 , so that O 2 =(W, 2 ) is equivalent to the projection of
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 .
be an ontology and W be a subset of V 1 . 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.
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 [1][9] [10].
Let O 1 =(V 1 , 1 ) be a lightweight ontology and G( 1 )=(,,) be the constraint graph for 1 . In what follows, we outline how 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 [1][9]. The nodes of G' are those of G, with the same labels as in G. The procedure adopted to construct a MEG of a graph has to be modified to also drop an arc (M,N), if the arc ) M N ( , connecting the dual nodes of M and N is dropped. This modification is necessary to preserve the characteristics of constraint graphs (see Definitions 2 and 3). Then, for each arc (M,N) in ', select an expression e that labels M and an expression f that labels N, and add the constraint e ⊑ f to 2 .
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 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 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 [8], which supports a restricted form of role hierarchy. From a practical perspective, we have implemented a tool that accepts lightweight ontologies, described in OWL, and offers an interface to apply the operations to create new ontologies. We are also designing a tool to extract constraints from a Linked Data source S by combining the information in the VoiD document [2] of the source, if any, with a probing technique. The tool explores the idea of the operations introduced in this paper both to compute the constraints that apply to S and to document them in an extension of the VoiD vocabulary.