=Paper=
{{Paper
|id=None
|storemode=property
|title=Constraint Reuse in DL-Lite Core with Arbitrary Number Restrictions
|pdfUrl=https://ceur-ws.org/Vol-866/keynote2.pdf
|volume=Vol-866
|dblpUrl=https://dblp.org/rec/conf/amw/CasanovaBFVMS12
}}
==Constraint Reuse in DL-Lite Core with Arbitrary Number Restrictions==
<pdf width="1500px">https://ceur-ws.org/Vol-866/keynote2.pdf</pdf>
<pre>
       Constraint Reuse in DL-Lite Core with Arbitrary
                   Number Restrictions
                                    (Extended Abstract)


   Marco A. Casanova1, Karin K. Breitman1, Antonio L. Furtado1, Vânia M.P. Vidal2,
                 José A. F. de Macêdo2, Eveline R. Sacramento1,3
              1
                Department of Informatics – PUC-Rio – Rio de Janeiro, RJ – Brazil
                     {casanova, karin, furtado, esacramento}@inf.puc-rio.br
         2
           Department of Computing, Federal University of Ceará – Fortaleza, CE – Brazil
                                {vvidal, jose.macedo}@lia.ufc.br
     3
       Ceará State Foundation of Meteorology and Water Resources – Fortaleza, CE – Brazil
                                    eveline@funceme.br



       Abstract. The process of reusing an ontology involves two issues: (1) selecting
       a set of terms from the ontology vocabulary; and (2) using the ontology con-
       straints 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 opera-
       tions for a class of ontologies built upon DL-Lite core with arbitrary number re-
       strictions. Finally, for this class of ontologies, the paper addresses the question
       of minimizing the set of constraints which results from an operation.



       Keywords: constraints, DL-Lite Core, Description Logics.



1 Introduction

We introduce a set of concepts and procedures that promote constraint reuse in ontol-
ogy 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 theo-
ries. 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 devel-
oped 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 opera-
tion, but considered neither the other operations nor the question of optimizing the
representation of the resulting ontologies.




                                               2
   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 ontolo-
gies. Section 4 addresses the question of minimizing the set of constraints that result
from an operation. Finally, Section 5 contains the conclusions.


2 A Formal Framework

2.1 A Brief Review of Basic Concepts

The definition of the operations depends only on the notion of theory, which we in-
troduce 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 de-
scriptions and role descriptions of V depend on the specific description logic. An in-
clusion of V is an expression of the form u ⊑ v, where u and v both are concept de-
scriptions or both are role descriptions.
    An interpretation s of V consists of a nonempty set s, the domain of s, and an in-
terpretation function, also denoted s, with the usual definition [4]. We use s(u) to in-
dicate 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],
                    N
denoted DL - Litecore   . 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 con-
      cept descriptions and also concept descriptions
    If u is a concept description, then u (negated concept) is a concept description
                  N
    For DL - Litecore , 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 de-
scriptions.
    We use the following abbreviations: “⊤” for “” (universal concept), “p” for
“( 1 p)” (existential quantification), “( n p)” for “( n+1 p)” (at-most restriction)




                                            3
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, respec-
tively, and  is a finite set of inclusions of V, called the constraints of O. A light-
                                                                             N
weight ontology is an ontology whose constraints are inclusions of DL - Litecore .
   From this point on, we will use the terms class, property and constraint instead of
atomic concept, atomic role and inclusion, whenever reasonable.


2.2 Definition of the Operations

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 ontol-
            ogy 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 on-
            tology 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 re-
sulting ontology is not necessarily minimal, a point elaborated in Section 4.


2.3         An Example

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 On-
tology 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




                                             4
  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 con-
straints.

                                owl:disjointWith
                                                               foaf:Agent



             foaf:name
xsd:string               foaf:Person                           foaf:Group    foaf:Organization



                                         mo:MusicArtist                     mo:CorporateBody



                          mo:SoloMusicArtist         mo:MusicGroup              mo:Label



         Fig.1. The class hierarchies of MO rooted at classes foaf:Agent and foaf:Person.




                                                    5
3. Computing the Operations over Lightweight Ontologies

3.1 Constraint Graphs

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) con-
cept descriptions. The notion of constraint graphs [6] captures the structure of sets of
constraints.
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 ei-
         ther 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 la-
         beled 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  la-
   bels each node with a set of concept descriptions, is defined from g(,) by col-
   lapsing 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




                                             6
        b. there are nodes M and N, not necessarily distinct from K, and a basic con-
            cept 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. 
                                                               N
  Theorem 1 shows how to test logical implication for DL - Litecore inclusions [6].
                                       N                                     N
Theorem 1. Let  be a set of DL - Litecore  inclusions and  be a DL - Litecore  inclu-
sion. Assume that  is of the form e  f and let  = {e, f}. Then,    iff one of the
following conditions holds:
(i) The node of G(,) labeled with e is a -node; or
(ii) The node of G(,) labeled with f is a ⊤-node; or
(iii) There is a path in G(,) from the node labeled with e to the node labeled with f.

Example 1: The fragment of the Music Ontology shown in Figure 1 is formalized as
the ontology O0=(V0,0), where
    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).
                       Table 2. Constraints of the ontology in Figure 1.
   (1 foaf:name) ⊑ foaf:Person                    (1 mo:member_of) ⊑ foaf:Person
   (1 foaf:name ) ⊑ xsd:string                   (1 mo:member_of ) ⊑ foaf:Group
   mo:MusicArtist ⊑ foaf:Agent                     mo:MusicGroup ⊑ mo:MusicArtist
   foaf:Group ⊑ foaf:Agent                         mo:MusicGroup ⊑ foaf:Group
   foaf:Organization ⊑ foaf:Agent                  mo:CorporateBody ⊑ foaf:Organization
   mo:SoloMusicArtist ⊑ foaf:Person                mo:Label ⊑ mo:CorporateBody
   mo:SoloMusicArtist ⊑ mo:MusicArtist
   foaf:Person ⊑ foaf:Organization                foaf:Person ⊑ (2 foaf:name)




                                               7
                              (2foaf:name)           (2 foaf:name)

     (1 mo:member_of)       (1 foaf:name)          (1)foaf:name)     (1 mo:member_of)


      mo:SoloMusicArtist      foaf:Person             foaf:Person       mo:SoloMusicArtist


        mo:MusicArtist                                                     mo:MusicArtist


       mo:MusicGroup           foaf:Agent              foaf:Agent         mo:MusicGroup


          foaf:Group        foaf:Organization       foaf:Organization       foaf:Group


     (1 mo:member-of )   mo:CorporateBody         mo:CorporateBody    (1 mo:member-of )


                                mo:Label                 mo:Label


       (1 foaf:name)         xsd:string              xsd:string         (1 foaf:name)


                   Fig. 3. The graph G(APO) representing the constraints of APO.




3.2 Computing the Operations

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 in-
volve 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 ontolo-
gies can be likewise defined.




                                                  8
 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 */
         return 2
 end

                                  Fig. 4. Procedure Projection.




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 con-
straint graph (c.f. the procedure in Figure 4). Therefore, an interesting question im-
mediately 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 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 ex-
pressions 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.




                                                 9
The procedure adopted to construct a MEG of a graph has to be modified to also drop
an arc (M,N), if the arc ( N , M ) 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 la-
beled the nodes in the strongly connected component. Thus, we would have to con-
struct 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 con-
nected 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 construct-
ing 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 la-
bels 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 corre-
spond 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.


5 Conclusions

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 restrict-
ed 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 ap-
ply 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.




                                          10
Selected References

[1]  Aho, A. V., Garey, M. R., Ullman, J. D. (1972). The Transitive Reduction of a Directed
     Graph. SIAM J. Comp., 1(2), 131-137.
[2] Alexander, K., Cyganiak, R., Hausenblas, M., Jun Zhao, J. Describing Linked Datasets
     with the VoID Vocabulary. W3C Interest Group Note (03 March 2011). Available at:
     http://www.w3.org/TR/void/
[3] Artale, A.; Calvanese, D.; Kontchakov, R.; Zakharyaschev, M. The DL-Lite family and
     relations. J. of Artificial Intelligence Research 36, 1–69.
[4] Baader, F., Nutt, W. Basic Description Logics. In: F. Baader, D. Calvanese, D.L.
     McGuiness, D. Nardi, P.F. Patel-Schneider (eds), The Description Logic Handbook: The-
     ory, Implementation and Applications, Cambridge U. Press, UK (2003), pp. 43–95.
[5] Brickley, D., Miller, L. FOAF Vocabulary Specification 0.98. Namespace Document 9
     August 2010 - Marco Polo Edition.
[6] Casanova, M.A., Lauschner, T., Leme, L. A. P. P., Breitman, K. K., Furtado, A. L., Vi-
     dal, V. M. P. Revising the Constraints of Lightweight Mediated Schemas. Data &
     Knowledge Engineering, v.69, pp.1274 - 1301, 2010.
[7] Casanova, M. A., Breitman, K. K., Furtado, A. L., Vidal, V. M. P., Macêdo, J. A. F. The
     Role of Constraints in Linked Data. Proceedings of the Confederated International Con-
     ferences: CoopIS, DOA-SVI, and ODBASE 2011, Part II. Lecture Notes in Computer
     Science. Heidelberg: Springer, 2011. v.7045. p.781 - 799.
[8] Casanova, M.A., Breitman,K.K., Furtado, A.L., Vidal, V.M.P., Macêdo, J.A.F. An Effi-
     cient Proof Procedure for a Family of Lightweight Database Schemas. In: Michael G.
     Hinchey and Lorcan Coyle (eds.), Conquering Complexity. Springer, London, 2012.
[9] Hsu, H. T. (1975). An Algorithm for Finding a Minimal Equivalent Graph of a Digraph.
     Journal of the Association for Computing Machinery, 22(1), 11-16.
[10] Khuller, S., Raghavachari, B., Young, N. (1995). Approximating the Minimum Equiva-
     lent Digraph. SIAM Journal on Computing, 24(4), 859-872.
[11] Raimond, Y., Giasson, F. Music Ontology Specification. Specification Document - 28
     November 2010. Latest version: http://purl.org/ontology/mo/ (RDF/XML, Turtle).




                                           11

</pre>