{'fraction_non_alphanumeric': 0.051141317270349526, 'fraction_numerical': 0.015059047317111834, 'mean_word_length': 4.271464382703154, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Algebra of Lightweight Ontologies

This paper argues that certain ontology design problems are profitably addressed by treating ontologies as theories and by defining a set of operations that create new ontologies, including their constraints, out of other ontologies. The paper first shows how to use the operations in the context of ontology reuse, how to take advantage of the operations to compare different ontologies, or different versions of an ontology, and how the operations may help design mediated schemas in a bottom up fashion. The core of the paper discusses how to compute the operations for lightweight ontologies and addresses the question of minimizing the set of constraints of a lightweight ontology. Finally, the paper describes an implementation of the operations, as a Prot\'eg\'e plug-in.


Introduction
In this paper, we argue that certain familiar ontology design problems are profitably addressed by treating ontologies as theories and by defining a set of operations that create new ontologies, including their constraints, out of other ontologies. We show how to compute the operations for lightweight ontologies, that is, ontologies whose constraints are lightweight inclusions. This class of constraints is expressive enough to cover the types of constraints commonly used in conceptual modeling and is as expressive as the class of inclusions considered in DL-Lite core with arbitrary number restrictions (Artale et al., 2009). We also discuss how to minimize the set of lightweight inclusions.
In more detail, we define an ontology as a pair O=(V,S) such that V is a vocabulary and S is a set of constraints in V. The theory of S is the set of all constraints that are logical consequences of S. We emphasize that the constraints in S capture the semantics of the terms in V and must, therefore, be brought to the foreground. The theory of S in turn identifies the constraints that are implicitly defined, but which must be considered when using fragments of the ontology. Turning to the ontology design problems that motivated the introduction of the operations, consider first the problem of designing an ontology to publish data on the Web. If the designer follows the Linked Data principles (Bernes-Lee, 2006;Bizer et al., 2007), he must select known ontologies, as much as possible, to organize the data so that applications "can dereference the URIs that identify vocabulary terms in order to find their definition". We argue that the designer should go further and analyze the constraints of the ontologies from which he is drawing the terms to construct his vocabulary. Furthermore, he should publish the data in such a way that the original semantics of the terms is preserved. To facilitate ontology design from this perspective, we introduce three operations on ontologies, called projection, union and deprecation.
Consider now the problem of comparing the expressive power of two ontologies, O1=(V1,S1) and O2= (V2,S2). If the designer wants to know what they have in common, he should create a mapping between their vocabularies and detect which constraints hold in both ontologies, after the terms are appropriately mapped. The intersection operation answers this question. We argued elsewhere (Casanova et al., 2010) that intersection is also useful to address the design of mediated schemas that combine several export schemas in a way that the data exposed by the mediator is always consistent.
On the other hand, if the designer wants to know what holds in O1=(V1,S1), but not in O2=(V2,S2), he should again create a mapping between their vocabularies and detect which constraints hold in the theory of S1, but not in the theory of S2, after the terms are appropriately mapped. The difference operation answers this question.
Finally, a variant of ontology comparison is the problem of analyzing what changed from one version of an ontology to the other. Difference is especially useful here.
To compute the operations, we adopt the machinery developed in (Casanova et al., 2010(Casanova et al., , 2012b to handle lightweight inclusions. Previous work by the authors (Casanova et al., 2011;Casanova et al., 2012a) introduced the notion of open fragment, which is captured by the projection operation, and some of the operations discussed in detail in this paper. An early implementation of the operations is described in (Pinheiro, 2013).
The paper is organized as follows. Section 2 presents the formal definition of the operations. Section 3 illustrates the use of the operations to address ontology design problems. Section 4 introduces a decision procedure for lightweight inclusions, based on the notion of constraint graphs, and discusses the problem of minimizing a set of lightweight inclusions. Section 5 shows how to compute the operations for lightweight ontologies. Section 6 describes the Protégé plug-in implementation. Section 7 summarizes related work. Section 8 contains the conclusions.

A Brief Review of Basic Concepts
The definition of the operations depends only on the notion of theory, which we introduce in the context of Description Logic (DL) (Baader and Nutt, 2003).
Briefly, a vocabulary V consists of a set of atomic concepts, a set of atomic roles, and the bottom concept ^. A language in V is a set of strings, using symbols in V, whose definition depends on the specific variation of Description Logic adopted; the definition of the language typically includes definitions for the set of concept descriptions in V and for the set of role descriptions in V.
An inclusion in V is a statement of the form u ⊑ v, where u and v both are concept descriptions in V or both are role descriptions in V. We use u º v (equivalence) as an abbreviation for the pair of inclusions u ⊑ v and v ⊑ u.
An interpretation s for V consists of a nonempty set D s , the domain of s, whose elements are called individuals, and an interpretation function, also denoted s, where: s(^) = AE s(A) Í D s for each atomic concept A in V s(P) Í D s ´ D s for each atomic role P in V The function s is extended to role and concept descriptions in V. The exact definition again depends on the specific variation of Description Logic adopted. We use s(e) to indicate the value that s assigns to a concept description or a role description e in V.
Let s and s' be two inclusions in V and S be a set of inclusions in V. Assume that s is of the form u ⊑ v. We say that: • s is valid, denoted ⊨ s, iff any interpretation for V satisfies s. • s and s' are tautologically equivalent iff any model of s is a model of s' and vice-versa.
• S logically implies s, or s is a logical consequence of S, denoted S ⊨ s, iff any model of S satisfies s. • S is satisfiable or consistent iff there is a model of S.
The theory of S in V, denoted t[S], is the set of all inclusions in V that are logical consequences of S. We say that two sets of inclusions, G and Q, are equivalent, denoted Finally, an ontology is a pair O=(V,S) such that V is a finite vocabulary, whose atomic concepts and atomic roles are called classes and properties of O, respectively, and S is a set of inclusions in V, called the constraints of O. Two ontologies O1 = (V1,S1) and O2 = (V2,S2) are equivalent, denoted O1 º O2, iff S1 and S2 are equivalent.

Definition of the Ontology Operations
In this section, we introduce a collection of operations over ontologies, whose definition is not restricted to any specific variation of DL. Definition 1: Let O1 = (V1,S1) and O2 = (V2,S2) be two ontologies, W be a subset of V1, and Y be a set of constraints in V1. (i) The projection of O1 = (V1,S1) over W, denoted p[W](O1), returns the ontology OP = (VP,SP), where VP = W and SP is the subset of the constraints in t[S1] that use only classes and properties in W.
Section 3 presents concrete examples of the operations. At this point, we observe that deprecation does not reduce to difference since, in general, we have Using the notation in Definition 1, we also observe that In an earlier work (Casanova et al., 2011), we introduced the notions of open and closed fragments of an ontology. The operations capture these notions as follows. Let O1 = (V1,S1) be an ontology and W be a subset of V1. The open fragment of O1 defined by W is the projection p[W](O1) of O1 over W, and the closed fragment of O1 defined by W is expressed as p[W](O1) È O2, where O2 = (V1,F) and F contains an inclusion of the form A ⊑ ^, for each atomic concept A in V1, but not in W, and an inclusion of the form (³1 P) ⊑ ^, for each atomic role P in V1, but not in W (see Section 2.3 for the definition of (³1 P)); these inclusions force the interpretations of A and P to be the empty set.
We note that the ontology O that results from an operation is unique, by definition. However, there might be several ontologies that are equivalent to O. For example, if OP = (VP,SP) is the projection of O1 on W, there might be several sets of constraints that are equivalent to the set of constraints in the theory of O1 that use only terms in W. This simple observation will be helpful in Section 5, which addresses how to implement the operations.
Finally, we observe that we may generalize union, intersection and difference by considering a renaming of one or both vocabularies of the ontologies involved and appropriately renaming the terms that occur in the constraints when comparing the theories. This extension is used in the first example of Section 3.2, but it will not be considered further in this paper.

Lightweight Description Logic
The procedures that implement the operations, introduced in Section 5, assume that the inclusions meet certain restrictions, imposed by a variation of Description Logic, called Lightweight Description Logic, or Lightweight DL.
Lightweight DL is characterized by the following definitions and restrictions on the sets of concept descriptions, role descriptions and inclusions.
Definition 2: Let V be a vocabulary.
(i) A lightweight role description in V is an atomic role P in V or a string of the form P¯ (inverse role), where P is an atomic role in V. (ii) A lightweight basic concept description in V is the bottom concept ^, an atomic concept in V, or an at-least restriction of the form (³n p), where p is a lightweight role description in V and n is a positive integer. (iii) A lightweight concept description in V is a lightweight basic concept description in V, or a lightweight negated concept of the form ¬e, where e is a lightweight basic concept description in V. (iv) A lightweight inclusion in V is a string of one of the forms: (a) e ⊑ f, where e is an atomic concept or an at-least restriction in V and f is the bottom concept ^, an atomic concept in V, or an at-least restriction. (b) e ⊑ ¬f, where e and f are atomic concepts or at-least restrictions in V.
Definition 3: Let V be a vocabulary and s be an interpretation for V. The function s is extended to lightweight role and concept descriptions in V as follows (where P is an atomic role, e is a lightweight basic concept description and p is a lightweight role description): Since lightweight inclusions are a special case of inclusions, the notion of satisfiability, etc. remains as in Section 2.
We use the following abbreviations, where p is a lightweight role description: • "⊤" (universal concept) for "¬^" • "∃p" (existential quantification) for "(³1 p)" • "(£n p)" (at-most restriction) for "¬(³n+1 p)" By an unabbreviated concept description we mean a concept description that does not use such abbreviations. Care must be taken to eliminate the abbreviated concept descriptions before checking if an inclusion is indeed a lightweight inclusion. Also, in view of the restrictions in Definition 2(iv), a lightweight equivalence e º f is such that e and f both are atomic concepts or at-least restrictions in V.

Definition 4: An ontology O=(V,S) is a lightweight ontology iff S is a set of lightweight inclusions in V.
We conclude this section with brief remarks on the expressiveness of lightweight inclusions.
Let C and D be atomic concepts, p and q be lightweight role descriptions and m and n be positive integers. According to Definition 2(iv), inclusions of the following forms are lightweight inclusions: Lightweight inclusions are therefore sufficiently expressive to cover the simplest types of constraints used in conceptual modeling, as summarized in Table 1.
Let e and f be lightweight basic concept descriptions. Inclusions of the following forms are not lightweight inclusions: However, we note that (6) ^ ⊑ f, ^ ⊑ ¬f, e ⊑ ¬^ are valid (satisfiable by any interpretation) (7) ¬f ⊑ ¬e is tautologically equivalent to e ⊑ f Therefore, when defining an ontology, inclusions as in (3) can be ignored, since they are vacuous constraints, and inclusions of the form ¬f ⊑ ¬e can be replaced by e ⊑ f.
Finally, we remark that the definitions of DL-Lite 1234 5 inclusions (Artale et al., 2009) and lightweight inclusions differ only in that the latter, but not the former, rules out inclusions of the forms in (3). However, this is semantically immaterial since, given a set S of DL-Lite 1234 5 inclusions, we can always drop from S inclusions of the forms in (3) without affecting the theory of S, in view of (6). On the other hand, inclusion of the forms in (3) would unnecessarily complicate the structural proof procedure introduced in Section 4.1, based on Theorem 1.

Projection, Deprecation and Union
Projection allows the designer to define a set W containing just a few terms from the vocabulary of an ontology and retain the semantics of the terms in W through the constraints, derivable from those of the ontology, that apply to the terms in W. Deprecation simply allows the designer to drop constraints from an ontology. Finally, union allows the designer to combine two ontologies. These three operations offer the designer powerful tools to (partially) reuse vocabularies and to preserve the semantics of the terms. In this section, we further motivate this argument with the help of an example that uses the Music Ontology (Raimond and Giasson, 2010).
The Music Ontology (MO) provides concepts and properties to describe artists, albums, tracks, performances, arrangements, etc. 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) (Brickley and Miller, 2010) and the XML Schema (XSD) vocabularies. We respectively adopt the prefixes "mo:", "foaf:" and "xsd:" to 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 a constraint informally formulated as: foaf:Person and foaf:Organization are disjoint classes Table 1. Common constraint types used in conceptual modeling.

Domain Constraint
$P ⊑ C (³ 1 P) ⊑ C property P has class C as domain, that is, if (a,b) is a pair in P, then a is an individual in C Range Constraint property P or its inverse P¯ maps each individual in class C to at least k distinct individuals maxCardinality Constraint property P or its inverse P¯ maps each individual in class C to at most k distinct individuals Let V1 be the following set of terms from the FOAF and the XSD vocabularies, and let V2 contain the rest of the terms that appear in Figure  The union returns the ontology O5 = (V5,S5), where V5 = V3 and S5 = S3 È S4. Finally, we construct O0 = (V0,S0), the ontology that corresponds to Figure 1, as: The reader is invited to reflect upon the definition of O0. We contend that the expression defined using the operations provides a reasonable explanation of how O0 is constructed from FOAF and additional terms and constraints.

Intersection and Difference
Intersection and difference help the designer compare the expressive power of two ontologies O1=(V1,S1) and O2=(V2,S2). If the designer wants to know what the ontologies have in common, he uses intersection. On the other hand, if he is interested in what holds in O1, but not in O2, he should use difference.
To illustrate the use of intersection, we analyze two data sources from the scientific research domain, DBLP and Lattes. DBLP stores Computer Science bibliographic references -over half a million references -and links to researchers' homepages. Lattes is a database, organized by CNPq -the Brazilian Research Agency, storing researchers' CVs and research group descriptions. Assume that the Lattes vocabulary suffers a renaming where Document is mapped to Publication.
To simplify the discussion, Table 2 shows just a few constraints from each data source. Column (a) shows the DBLP constraints, Column (b), the Lattes constraints, and Column (c) the constraints in the intersection. For example, Line 1 of the table indicates that Article ⊑ Publication is a constraint in both ontologies, after Document is renamed to Publication, and hence is in their intersection. Line 7(b) indicates that Con-ferencePaper ⊑ Publication is a constraint of the Lattes ontology, again after Document is renamed to Publication; whereas Lines 1(a) and 3(a) implies that ConferencePaper ⊑ Publication is in the theory of the DBLP ontology; hence this constraint is also in the intersection of the ontologies, as shown in Line 7(c).
To illustrate the use of difference, consider a scenario where a domain specialist adopted the version of the FOAF ontology released on January 1 st , 2010 (call it FOAF1). However, on August 9 th , 2010, a new release of the FOAF ontology was published (call it FOAF2). The specialist then wants to verify what changed from one version to the other. He can then take the difference between FOAF1 and FOAF2 (and vice-versa). Table 3 shows the (partial) difference between FOAF1 and FOAF2. Line 2(c) indicates that the constraint Project ⊑ ¬Image is in the difference between FOAF1 and FOAF2. Indeed, since Image ⊑ Document is in the theory of FOAF1, we have that ¬Document ⊑ ¬Image is also in the theory of FOAF1. Hence, since Project ⊑ ¬Document is in the theory of FOAF1 (in fact, it is a constraint of FOAF1, according to Line 2(a)), we also have that Project ⊑ ¬Image is in the theory of FOAF1. However, this constraint is not in the theory of FOAF2. Likewise, Line 4(c) indicates that Organization ⊑ ¬Image is Table 2. Partial Intersection of the DBLP and Lattes ontologies.
ConferencePaper ⊑ Document ConferencePaper ⊑ Publication in the theory of FOAF1, but not in the theory of FOAF2. Finally, Line 6(a) indicates that FOAF1 has a constraint, Image ⊑ Document, which is not in the theory of FOAF2.

A Decision Procedure for Lightweight Inclusions
In this section, we review a decision procedure for lightweight inclusions, based on the notion of constraint graphs (Casanova et al., 2010). We also discuss the problem of minimizing a set of lightweight inclusions, which affects the implementation of the ontology operations. We stress that the concepts introduced in this section refer only to lightweight inclusions. Therefore, we often omit explicit reference to this variation of DL in what follows, a simplification that the reader must bear in mind.

Constraint Graphs
We say that the complement of a basic concept description b is ¬b, and vice-versa. If e is a basic concept description, or the negation of a basic concept description, then ̅ denotes the complement of e.
Let S be a set of lightweight inclusions and W be a set of lightweight concept descriptions.
Definition 5: The labeled graph g(S,W)=(g,d,k) that captures S and W, where k 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 S, or that occurs in W, there is exactly one node in g labeled with e. If necessary, the set of nodes is augmented with new nodes so that: (a) For each atomic concept C that occurs in S or in W, there is exactly one node in g labeled with C. (b) For each atomic role P that occurs in S or in W, there is exactly one node in g labeled with (³1 P) and exactly one node labeled with (³1 P¯).
(ii) If there is a node in g labeled with a concept description e, then there must be exactly one node in g labeled with ̅ .    When W is the empty set, we simply write g(S) and say that g(S) is the graph that captures S. We use K→M to indicate that there is a path in G(S,W) from K to M. Also, as a convenience, a path of length 0 is a path consisting of a single node.

Constraint
Informal specification (³1 foaf:name) ⊑ foaf:Person (³1 foaf:name¯ ) ⊑ xsd:string (³1 mo:member_of) ⊑ foaf:Person (³1 mo:member_of¯ ) ⊑ foaf:Group , and there are nodes M and N, not necessarily distinct from K, and a basic concept description b such that M and N are labeled with b and ¬b, respectively, and K→M and K→N. (ii) For each positive integer n, we say that a node K of G(S,W) is a ^-node of rank n iff K is not a ^-node of rank m, with m<n, and there is a ^-node L of rank n-1 such that (a) (K,L) is an arc of G(S,W), or (b) L is labeled with (³1 P¯) and K is labeled with (³1 P), or (c) L is labeled with (³1 P) and K is labeled with (³1 P¯).
Case (ii-b) captures the fact that, given an interpretation s, if s((³1 P¯))=AE, then s(P)=s((³1 P))=AE. Case (ii-c) follows likewise, when s((³1 P))=AE. In view of these cases, the notion of rank is necessary to avoid a circular definition.
Definition 8: Let G(S,W)=(h,e,l) be the constraint graph for S and W. Let K be a node of G(S,W). We say that K is a ^-node iff K is a ^-node with rank n, for some nonnegative integer n. We also say that K is a ⊤-node iff ; is a ^-node.
To simplify the procedures in Sections 4.2 and 5, we label the ^-nodes and the ⊤nodes of a constraint graph with "^-node" and "⊤-node", respectively. We refer to these new labels as tags, to avoid confusion with the labels introduced in Definition 5.

Definition 9:
The tagged constraint graph for S and W is the constraint graph for S and W, with the ^-nodes and the ⊤-nodes tagged with "^-node" and "⊤-node", respec- tively.
In what follows, let G(S,W) be the constraint graph for a set S of lightweight inclusions and a set W of lightweight concept descriptions. Propositions 1, 2 and 3 capture some simple properties of G(S,W). We only provide brief proof sketches for these propositions and refer the reader to (Casanova et al., 2010) for the details.

Proposition 1 (Duality properties):
(i) For any pair of nodes M and N of G(S,W), we have that M®N iff ; ® ; . (ii) For any node M of G(S,W), for any concept description e, we have that e labels M iff ̅ labels ; . (iii) For any node M of G(S,W), we have that M is a ^-node iff ; is a ⊤-node.

Proof sketch
Property (i) follows from Definition 5(v) and Definition 6. Property (ii) follows from Definition 5(ii) and Definition 6. Finally, Property (iii) follows from Definition 8. at-least restrictions, or (e) M is labeled only with ⊤ and N is labeled only with negated atomic concepts and negated at-least restrictions.

Proof sketch
Property (i) follows since, by Definition 6, G(S,W) is defined by collapsing each strongly connected component of g(S,W) into a single node. Property (ii) follows from Definition 5(i)(ii) and Definition 6. To prove Properties (iii) to (vi), we first observe that, by Definition 2(iv): (*) ¬e ⊑ f is not a lightweight inclusion, where e and f are lightweight basic concept descriptions Then, from (*) and Definition 5, all nodes in a strongly connected component of g(S,W) are labeled only with atomic concepts and at-least restrictions or only with negated atomic concepts and negated at-least restrictions. Hence, from Definition 6, we have that G(S,W) satisfies (iii). Properties (iv) and (v) follow from Property (iii) and Definitions 7 and 8. Property (vi) follows again from (*) and Definitions 5 and 6.
Recall that the complement of a basic concept description b is ¬b, and vice-versa. Also recall that, if e is a basic concept description, or the negation of a basic concept description, then ̅ denotes the complement of e.

Proof sketch
Property (i) follows by the transitivity of inclusions, Proposition 2 and Definitions 5 and 6. Property (ii) follows from Proposition 2(iv), Property (i) and Definitions 7 and 8, if we observe that, if S ⊨ e ⊑ b and S ⊨ e ⊑ ¬b then S ⊨ e ⊑ ^.
Property (iii) follows from Proposition 1 and Property (ii). Property (iv) follows by the transitivity of inclusions, Proposition 2 and Definitions 5 and 6.
Theorem 1 shows how to test logical implication for lightweight inclusions. In the "if" direction, Theorem 1 is just a restatement of Proposition 3. In the "only if" direction, the proof is far more complex that those of the previous propositions and can be found in (Casanova et al., 2010). Just as a reminder, a path from a node M to a node N has length 0 iff M=N. Theorem 1 (Completeness): Let S be a set of lightweight inclusions and e ⊑ f be a lightweight inclusion. Let W ={e,f}. Then, S ⊨ e ⊑ f iff one of the following conditions holds: (i) The node of G(S,W) labeled with e is a ^-node, or (ii) The node of G(S,W) labeled with f is a ⊤-node, or (iii) There is a path in G(S,W), possibly with length 0, from the node labeled with e to the node labeled with f.

Theorem 1 leads to a simple decision procedure, Implies, to test if a lightweight
inclusion e ⊑ f is a logical consequence of a set S of lightweight inclusions (see Figure   3).

Minimizing the Set of Constraints of a Lightweight Ontology
This section in devoted of the question of minimizing the set of constraints of a lightweight ontology. We argue that this question is quite similar to finding a minimal equivalent graph (MEG) of a graph G, defined as a graph H with a minimal set of edges such that the transitive closure of G and H are equal. This problem has a polynomial solution when G is acyclic and is NP-hard for strongly connected graphs (Aho, Garey and Ullman, 1972;Hsu, 1975;Khuller, Raghavachari and Young, 1975). Figure 3 contains all procedures developed to address this question, as well as procedures to construct constraint graphs and to test if a lightweight inclusion is a logical consequence of a set of lightweight inclusions, based on Theorem 1. The MinimizeGraph procedure is based on the strategy of finding the MEG of a constraint graph.
Step (2) of MinimizeGraph can be implemented in polynomial time (Aho, Garey and Ullman, 1972;Hsu, 1975), since H is acyclic (because so is G, by Proposition 2(i)). In view of Propositions 1 and 2, Step (2) considers just the nodes of H labeled only with atomic concepts and at-least restrictions. Furthermore, since Step (2) drops the dual arcs, H satisfies the properties listed in Propositions 1 and 2.
The GenerateConstraints procedure transforms graph H into a set of constraints S2. Again, in view of Propositions 1 and 2, Step (3) of GenerateConstraints considers just the nodes of H labeled only with atomic concepts and at-least restrictions. Finally, the MinimizeConstraints uses the previous procedure to transform a set of lightweight constraints S1 and output an equivalent, minimal set of constraints S2. The correctness of MinimizeConstraints is stated in Theorem 2.
Theorem 2: Let S1 be a set of lightweight constraints and S2 be the result of applying MinimizeConstraints to S1. Then, S1 and S2 are equivalent, that is, t[S1]=t [S2].
(See the appendix for a proof).

Input: a set S of lightweight inclusions and an optional lightweight inclusion e ⊑ f
Output: the tagged constraint graph G(S,W) 1. Construct the constraint graph G(S,W) for S and W ={e,f}, using Definition 6.

Implies:
Input: a lightweight inclusion e ⊑ f and a set S of lightweight inclusions Output: "True", if e ⊑ f is a logical consequence of a set S "False", otherwise 1. Call ConstructGraph to construct the constraint graph G(S,W) for S and W ={e,f}.
The node of G(S,W) labeled with e is a ^-node, or 4. The node of G(S,W) labeled with f is a ⊤-node, or 5.
There is a path in G(S,W), possibly with length 0, from the node labeled with e to the node labeled with f. 6. Return "False", otherwise.

MinimizeGraph:
Input: a tagged constraint graph G Output: a MEG H of G 1. Initialize H with the same nodes, arcs, labels and tags as G.

For each node L of H labeled only with atomic concepts and at-least restrictions, 3.
For each arc (L,M) in H, 4.
For each node N in H, do: 5.
If there are arcs (M,N) and (L,N) in H 6.
such that (L,N) is not a tautological arc, 7.
Drop from H both the arc (L,N) and the arc ( ; , @ ) connecting the dual nodes of L and M.

GenerateConstraints:
Input: a tagged constraint graph H Output: a set of constraints S2 1. Initialize S2 to be the empty set.
2. Mark all arcs of H as unprocessed.
3. For each node M of H labeled only with atomic concepts and at-least restrictions, do: 4. If M is tagged as a "^-node", then 5.
For each label e of M, 6.
Add to S2 a constraint of the form e ⊑ ^.
Order the labels of M, creating a list e1,…,en, and 9.

10.
For each arc (M,N) of H such that (M,N) is unprocessed, do: 11.
Select a label e of M and a label f of N and 12.
Add to S2 a constraint of the form e ⊑ f.

MinimizeConstraints:
Input: a set of lightweight constraints S1 Output: an equivalent, minimal set of constraints S2 1. Call ConstructGraph to construct the tagged constraint graph G for S1.

Call
MinimizeGraph with G to generate H.

Call
GenerateContraints with H to generate S2. 4. Return S2.  Table 5, with redundancies for the sake of our example)  Figure 4 shows the constraint graph G(SPMG). MinimizeConstraints first creates a MEG H of G(SPMG) by discarding the arcs indicated in Figure 4 as dashed lines. Next, MinimizeConstraints calls GenerateConstraints, which outputs the final set of constraints ΘPMG shown in Step (3-b-ii-b) marks as processed both an arc and its dual in each iteration.

Overview
We start with a few observations that, albeit simple, impact the implementation of the operations. First, Definition 1 guarantees that each operation is a function, as expected, that is, each operation returns a unique result OR for each input. However, we consider acceptable that the implementation of an operation actually computes an ontology OE which is equivalent to OR. Furthermore, if the input ontologies have a finite set of constraints, we require that the implementation returns an ontology that has a finite set of constraints. This may be problematic for projection, intersection and difference, whose definitions use the theories of the sets of constraints involved, rather than the sets of constraints themselves, as in the definition of deprecation and union. Let O1 = (V1,S1) and O2 = (V2,S2) be two lightweight ontologies, W be a subset of V1 and Y be a set of constraints in V1. From the perspective of the difficulty of implementation, we may divide the operations into three groups: Group 1: deprecation and union. These operations have direct implementations from Definitions 1(ii) and (iii). Given O1 andY, the Deprecation procedure returns the ontology OD = (VD,SD), where VD = V1 and SD is the result of minimizing S1 -Y. Given O1 and O2, the Union procedure returns the ontology OU = (VU,SU), where VU = V1 È V2 and SU is the result of minimizing S1 È S2. Hence, these procedures are quite simple and will not be further discussed.
Group 2: projection and intersection. These operations have implementations that depend on Theorem 1. The Projection procedure computes the projection of O1 onto W and follows directly from Definition 1(i), Theorem 1 and constraint minimization. The Intersection procedure likewise follows from Definition 1(iv). These procedures will be discussed in detail in Sections 5.2 and 5.3.
Group 3: difference. This operation raises difficulties as discussed in Section 5.4.

Implementation of Projection
Let O1 = (V1,S1) be a lightweight ontology and W be a subset of V1. Recall that the projection of O1 over W is the ontology OP = (VP, SP), where VP=W and SP is the set of constraints in t[S1] that use only classes and properties in W. Procedure Projection computes GP so that t[GP] = t [SP]. That is, given any light- weight inclusion e ⊑ f that involves only classes and properties in W, e ⊑ f is a logical consequence of GP iff e ⊑ f is a logical consequence of S1. Note that this does not mean that e ⊑ f is a logical consequence of the subset of S1 whose inclusions involve only classes and properties in W. Procedure Projection works as follows: (1) Construct G(S1), the tagged constraint graph for S1.
(3) Use G*(S1) to create a graph GW by discarding all concept descriptions that label nodes of G*(S1) and that involve classes and properties which are not in W; nodes that end up with no labels are discarded, as well as their adjacent arcs. The nodes of GW retain all tags as in G*(S1). (4) Call MinimizeGraph with GW to generate H.
The correctness of Projection is established in Theorem 3, whose proof follows directly from Theorem 1. In particular, the transitive closure G*(S1), generated in Step (2), is simply a convenient way to capture all paths in G(S1) required to apply Condition (iii) of Theorem 1.
Theorem 3 (Correctness of Projection): Let O1 = (V1,S1) be a lightweight ontology and W be a subset of V1. Let OP = (W, GP) be the ontology that Projection returns for O1 and W. Then, for any lightweight inclusion e ⊑ f that involves only classes and properties in W, we have that S1 ⊨ e ⊑ f iff GP ⊨ e ⊑ f.
The following example illustrates how Projection operates.  Table 7. For example, Projection returns the third constraint in Table 7 because G(SAPO) has a path from the node labeled with mo:Label to the node labeled with ¬(³1 foaf:name) (and, hence, G*(SAPO) has an arc between these two nodes), and likewise for the forth constraint.
Procedure Intersection computes GN so that t[GN] = t [SN]. That is, a lightweight inclusion is a logical consequence of GN iff it is a logical consequence of Sk, for k=1,2. We proceed to discuss the major decisions that lead to the Intersection procedure. First recall from Theorem 1 that a lightweight inclusion e ⊑ f is a logical consequence of Sk iff there are nodes M and N of G(Sk,W), with W ={e,f}, such that (i) The node of G(Sk,W) labeled with e is a ^-node, or (ii) The node of G(Sk,W) labeled with f is a ⊤-node, or (iii) There is a path in G(Sk,W), possibly with length 0, from the node labeled with e to the node labeled with f.
Therefore, we must construct GN so that e ⊑ f is a logical consequence of GN iff e ⊑ f satisfies the above conditions with respect to Sk, for k=1,2. However, a direct application of Theorem 1 depends on the inclusion e ⊑ f being tested (since the theorem depends on the constraint graph G(S,W), with W= ). We argue that we can simplify the application of Theorem 1 in the context of the intersection operation, if we define a set of concept descriptions as follows.
Definition 10: Let S1 and S2 be two sets of lightweight inclusions. The closure of S1 and S2 with respect to each-other is the set D of concept descriptions defined so that a concept description e is in D iff, for k=1,2, e occurs in an inclusion of Sk but not in an inclusion of Sk+1 (sum is module 2).
Proposition 4: Let S1 and S2 be two sets of lightweight inclusions and D be the closure of S1 and S2 with respect to each other. Then, for k=1,2, any lightweight inclusion e ⊑ f in Sk+1 (sum is module 2) is a logical consequence of Sk iff there are nodes M and N of G(Sk,D) such that (i) The node of G(Sk,D) labeled with e is a ^-node, or (ii) The node of G(Sk,D) labeled with f is a ⊤-node, or (iii) There is a path in G(Sk,D), possibly with length 0, from the node labeled with e to the node labeled with f.
The final case analysis to compute the intersection operation is summarized in Table  8 and results in a set of lightweight inclusions (Column C of Table 8).
Step (3), the core of the Intersection procedure, directly captures such case analysis. We decided to create a set of lightweight inclusions, rather than a constraint graph, just to clarify the decisions behind the Intersection procedure. The actual implementation is optimized and avoids this intermediate step.
Note that we need not consider ⊤-nodes of G(S1,D) (or of G (S2,D)). Indeed, by Proposition 1, there is a ⊤-node of G(S1,D) labeled with f iff there is a ^-node labeled with ̅ . Furthermore, there is a path, possibly with length 0, from a node labeled with e to a node labeled with f iff there is a path, possibly with length 0, from a node labeled with ̅ to a node labeled with ̅ . Therefore, Cases 4, 5 and 6 of Table 8 respectively reduce to Cases 2, 1 and 3 of Table 8.
Procedure Intersection works as follows: (1) Construct the closure D of S1 and S2 with respect to each other.
(2) Construct G(S1,D) and G (S2,D), the tagged constraint graphs for S1 and D and S2 and D, respectively. (3) Construct a set of constraints S3 as follows (see Table 8): (a) Initialize S3 to be the empty set.
(b) For each node M of G(S1,D) tagged with "^-node" and labeled only with atomic concepts and at-least restrictions, for each label e of M, do: (i) If e also labels a node of G(S2,D) tagged with "^-node", then add e ⊑ ^ to S3.
(ii) For each node K of G(S2,D) tagged with "⊤-node", for each label f of K, add e ⊑ f to S3.
(iii) For each path of G(S2,D), possibly with length 0, from a node labeled with e to a node labeled with f, add e ⊑ f to S3.
(c) For each node M of G(S1,D) not tagged with "^-node" and labeled only with atomic concepts and at-least restrictions, for each path in G(S1,D), possibly with length 0, from M to a node N, for each label e of M, for each label f of N (f ¹ e, if M=N), do: (i) If e also labels a node of G(S2,D) tagged with "^-node", then add e ⊑ f to S3.
(ii) If f also labels a node of G(S2,D) tagged with "⊤-node", then add e ⊑ f to S3.  (1) e is an atomic concept or an at-least restriction.
(2) f is the bottom concept ^, an atomic concept, a lightweight at-least restriction, a negated atomic concept or a negated at-least restrictions.
(iii) If there is a path in G(S2,D), possibly with length 0, from a node labeled with e to a node labeled with f, then add e ⊑ f to S3. (4) Call MinimizeContraints with S3 to generate GN. (5) Return ON = (V1ÇV2, GN).
Theorem 4 (Correctness of Intersection): Let O1 = (V1,S1) and O2= (V2,S2) be two sets of lightweight ontologies. Let D be the closure of S1 and S2 with respect to each other. Let ON =(V1ÇV2,GN) be the ontology that Intersection returns for O1 and O2.
Let e ⊑ f be a lightweight inclusion. Then, GN ⊨ e ⊑ f iff S1 ⊨ e ⊑ f and S2 ⊨ e ⊑ f.

A Discussion on Difference
The problem of creating a procedure to compute the difference between two ontologies, O1=(V1,S1) and O2=(V2,S2), lies in that it might not be possible to obtain a finite set of inclusions DN in such a way that This invalidates the effort to create a procedure to obtain a finite set of inclusions DN satisfying (1), along the lines of those exhibited in Sections 5.2 and 5.3. This remark in fact puts in doubt the usefulness of a (generic) difference operation.
For example, consider the following two sets of inclusions: Then, ignoring tautologies when computing t[Sj], j=1,2, we have: But this definition of DN is not satisfactory, since we have That is, to compute the difference DN = t[S1] -t[S2], we remove "e ⊑ f" from t[S1], only to get "e ⊑ f" back by logical implication from DN. In fact, in this rather obvious example, we cannot obtain a set of inclusions DN such that . Indeed, since the set of inclusions must not logically imply "e ⊑ f", the only candidates are: In both cases, we have that (again ignoring tautologies when computing t[Dk], k=1,2): A non-deterministic procedure Difference to compute a subset of t[S1] -t[S2] would be: (1) Construct the closure D of S1 and S2 with respect to each other.
(2) Construct G(S1,D) and G(S2,D), the tagged constraint graphs for S1 and D and S2 and D, respectively.
(3) Construct a constraint graph H as follows: (a) Initialize H = G(S1,D). Theorem 5 (Correctness of Difference): Let O1 = (V1,S1) and O2= (V2,S2) be two sets of lightweight ontologies. Let D be the closure of S1 and S2 with respect to each other. Let OD = (V1, GD) be the ontology that Difference returns for O1 and O2. Then, for any lightweight inclusion e ⊑ f, if GD ⊨ e ⊑ f, then S1 ⊨ e ⊑ f but not S2 ⊨ e ⊑ f.

A Protégé Plugin Implementation
The OntologyManagerTab, presented in this section, offers the ontology operation described in previous sections, integrated with traditional ontology management features. The tool was developed in Java as a tab plug-in over Protégé 3.4.8 (the implementation might require minor modifications to work with other versions of Protégé).
Despite the fact that OntologyManagerTab was developed as a Protégé plug-in, it works in a completely independent manner from the main framework, using Protégé only as a Graphical User Interface (GUI) enclosure. In other words, all the functionalities provided by OntologyManagerTab do not rely on any of the Protégé libraries, making the tool easier to adapt as a plug-in for any other frame-work or as a stand-alone software.
OntologyManagerTab normalizes and loads OWL ontologies to be operated upon and saves the resulting ontology as an OWL file. The plugin uses a two-column table to represent the constraints of an ontology, where: • each expression that occurs in a constraint of the ontology appears at least once in the first column; • each constraint e ⊑ f of the ontology appears in a separate line of the table, where e appears in the first column and f in the second; • if any bottom nodes are found there will be a row with its name in Column 1 and ^ in Column 2. To use the plugin you will need to run Protégé and open or create a new project as shown bellow on figures 4 and 5, where we chose to open the newspaper example.
Afterwards we need to enable our plugin "OntologyManagerTab" to run as a "Tab Widget". We follow the path Project->Configure select our plugin and click "OK" which will open the OntolgyManagerTab as shown on Figures 6, 7 and 8.
To load an ontology you need to either click on the "Load Ontology 1" or "Load Ontology 2" button and a browse window will appear as shown on Figure 9. In this example we chose to load the FOAF ontology, the plugin will normalize the ontology and load the result to a restriction graph in memory. We can see the tab feedback on Figure 10, wich shows the Graph axioms, and the normalized result on Figure 11. When loading an ontology the default visualization shows each element full IRI, to help the user with a better and easier interface we have a button that shows and hides this, in Figure 10 all IRIs have been hidden.
Aside from the projection all other operations are calculated over two ontologies. The projection option loads into the second table all the classes and properties from the ontology loaded in the first so that the user can choose over which nodes the operation will be done, as shown in Figure 12 and 13. Any other operation will request that a second ontology be loaded as show in Figure 14.
The OntologyManagerTab takes into account not only each node IRI but also the IRI of the original loaded ontology to run its operations, which allows a better matching when mapping correspondent nodes between ontologies. We now show an Intersection example between FOAF and MusicOntology in Figure 15.
It also provides a Graph minimization button, since we work with the transitive closures of each ontology it is very useful to extract the MEG for the obtained results. This minimization also finds equivalent cardinality restrictions and when possible collapse them into one.
OntologyManagerTab saves all resulting ontologies with "Normalized.owl" at its end, in Figure 16 and 17 we illustrate the saving of the ontology we obtained from the previous intersection as Test, the plugin automatically adds the "Normalized.owl" at its end resulting in the "TestNormalized.owl" file.

Related Work
The results reported in the paper cover a topic -improving Linked Data design by constraint reuse -that is still neglected in the literature. The question of Linked Data semantics is not new, though. For example, recent investigation (Halpin and Haynes, 2010;Jaffrin et al., 2008;McCuster and McGuinness, 2010) in fact questions the correct use of owl:sameAs to inter-link datasets. Jain et al. (2010) argues that the Linked Open Data (LoD) Cloud, in its current form, is only of limited value for furthering the Semantic Web vision. They discuss that the Linked Open Data Cloud can be transformed from "merely more data" to "semantically linked data" by overcoming problems such as lack of conceptual descriptions for the datasets, schema heterogeneity and absence of schema level links. Along this line, we advocated that the design of Linked Data sources must include constraints derived from those of the underlying ontologies.
We note that the problem we cover in this paper cannot be reduced to a question of ontology alignment in the context of Linked Data, addressed for example in (Leme et al., 2009;Prateek et al., 2010;Wang et al., 2011). Indeed, we stress that one of the problems we focus on refers to bootstrapping a new ontology (including its constraints) from one or more existing ontologies.
Some tools, such as Prompt (Noy and Musen, 2000) and ODEMerge (Ramos, 2001), allow the user to combine two or more ontologies in a semiautomatic or automatic way, respectively. Other tools, such as PromptDiff (Noy et al., 2004) and OntoDiff (Tury and Bieliková, 2006), deal with ontology change detection. However, these tools cannot capture changes in the semantics of the terms. The OntologyManagement tool described in (Pinheiro, 2013) circumvents this limitation since it is based on the operations described in this paper. Volz et al. (2003) proposes a tool that implements the projection operation by the creation of a database view resulting from query execution. However, this tool does not allow the generation of semantic information captured by the constraints that apply to the vocabulary terms.
Finally, previous work by the authors (Casanova et al., 2011) introduced the notion of open fragment, which is captured by the projection operation, whereas (Casanova et al., 2012b) considered the union and difference operations, the question of optimizing the representation of the resulting constraints and briefly described the OntologyManagement tool.

Conclusions
In this paper we argued that certain familiar ontology design problems could be profitably addressed by treating ontologies as theories and by defining a set of operations on ontologies. Such operations extend the idea of namespaces to take into account constraints.
As future work, we intend to expand the implementation of the operations to cover a more expressive family of ontologies, using the results presented in (Casanova et al., 2012a). We also intend to integrate the OntologyManagement tool with the Protégé ontology editor to take advantage of all functionalities already available in Protégé, such as ontology modeling and visualization, inference and reasoning tasks. and W. Then, for any lightweight inclusion e ⊑ f that involves only classes and properties in W, we have that S1 ⊨ e ⊑ f iff GP ⊨ e ⊑ f.

Proof
Let e ⊑ f be a lightweight inclusion that involves only classes and properties in W. We have to prove that S1 ⊨ e ⊑ f iff GP ⊨ e ⊑ f. (Ü) Assume that GP ⊨ e ⊑ f. Since GP Í t(S1) we trivially have S1 ⊨ e ⊑ f. (Þ) Assume that S1 ⊨ e ⊑ f. By Theorem 1, there are 3 cases to consider.
Case 1: The node of G(S1,{e,f}) labeled with e is a ^-node. Then, by Corollary 1, there is a ^-node M' of G(S1) such that M' is labeled with e' and e ⊑ e' is a tautology. Furthermore, since e is a lightweight expression that involves only classes and properties in W and since e ⊑ e' is a tautology, e' is a lightweight expression that involves only classes and properties in W. Therefore, by Steps (3), (4), (5) of procedure Projection and Theorem 2, we have that e' ⊑ ^ is in GP. Hence, since e ⊑ e' is a tautology, GP ⊨ e ⊑ ^. Therefore, GP ⊨ e ⊑ f.
Case 2: The node of G(S1,{e,f}) labeled with f is a ⊤-node f. Then, by Corollary 1, there is a ⊤-node N' of G(S1) such that N' is labeled with f' and f' ⊑ f is a tautology. Furthermore, since f is a lightweight expression that involves only classes and properties in W and since f' ⊑ f is a tautology, f' is a lightweight expression that involves only classes and properties in W. Then, the dual node of N' is a ^-node ; ′ of G(S1) labeled with ′ ; . Therefore, by Steps (3), (4), (5) of procedure Projection and Theorem 2, we have that ̅ ′ ⊑ ^ is in GP and, hence, ⊤ ⊑ f' is in GP. Thus, since f' ⊑ f is a tautology, GP ⊨ ⊤ ⊑ f. Therefore, GP ⊨ e ⊑ f.
Case 3: There is a path in G(S1,{e,f}), possibly with length 0, from the node labeled with e to the node labeled with f. Then, by Corollary 1, there is a path in G(S1), possibly with length 0, from the node M' labeled with e' to the node N' labeled with f' such that e ⊑ e' and f' ⊑ f are tautologies. Furthermore, since e is a lightweight expression that involves only classes and properties in W and since e ⊑ e' is a tautology, e' is a lightweight expression that involves only classes and properties in W (and likewise for f'). Therefore, by Steps (3), (4), (5) of procedure Projection and Theorem 2, we have that e' ⊑ f' is in GP. Thus, since e ⊑ e' and f' ⊑ f are tautology, GP ⊨ e ⊑ f. Theorem 4 (Correctness of Intersection): Let O1 = (V1,S1) and O2= (V2,S2) be two sets of lightweight ontologies. Let D be the closure of S1 and S2 with respect to each other. Let ON =(V1ÇV2,GN) be the ontology that Intersection returns for O1 and O2.
Let e ⊑ f be a lightweight inclusion. Then, GN ⊨ e ⊑ f iff S1 ⊨ e ⊑ f and S2 ⊨ e ⊑ f.

Proof
Let e ⊑ f be a lightweight inclusion. We have to prove that S1 ⊨ e ⊑ f and S2 ⊨ e ⊑ f iff GN ⊨ e ⊑ f. Case 9.4: g2 ⊑ g1 and h2 ⊑ h1. (Follows as in Case 3.3).
Theorem 5 (Correctness of Difference): Let O1 = (V1,S1) and O2= (V2,S2) be two sets of lightweight ontologies. Let D be the closure of S1 and S2 with respect to each other. Let OD = (V1, GD) be the ontology that Difference returns for O1 and O2. Then, for any lightweight inclusion e ⊑ f such that GD ⊨ e ⊑ f, we have that S1 ⊨ e ⊑ f but not S2 ⊨ e ⊑ f.

Proof
Let e ⊑ f be a lightweight inclusion. Assume that GD ⊨ e ⊑ f. By the case analysis of Table 10 and Theorem 1, we have S1 ⊨ e ⊑ f but not S2 ⊨ e ⊑ f.