Reasonable Macros for Ontology Construction and Maintenance Henrik Forssell, Daniel P. Lupp, Martin G. Skjæveland, and Evgenij Thorstensen Department of Informatics, University of Oslo {jonf,danielup,martige,evgenit}@ifi.uio.no Abstract. Creating and maintaining ontology knowledge bases are dif- ficult processes that can be improved by using macro or templating languages that help structure the ontology engineering task and reduce unnecessary repetitions of ontology patterns. However, since the templates themselves need to be created and maintained, suitable tool support for their maintenance is vital in order to ensure the quality of the resulting knowledge base, and to lower the cost of its construction and maintenance. In this paper, we show that a simple and powerful macro or templating language for description logic (DL) knowledge bases can be defined in description logic itself. In other words, DL allows for macros that are themselves DL knowledge bases; maintenance and debugging for such macros can therefore be done using existing DL reasoners, and does not require extra tool support. We define such macros for the DL SROIQ, which underlies the W3C standard OWL 2. We then show that notions of containment and other problems of interest for such macros become standard reasoning problems supported by existing reasoners. We explore the uses of such macros, showcase how they can be used as restricted higher-order queries, and apply our insights to the setting of data exchange. 1 Introduction Like any knowledge representation task, creating ontologies is a difficult and time-consuming process that requires the utmost diligence of the ontology engineer. Ontology design patterns (ODPs) are a proposed solution to improve the ontology engineering process by, in part, providing reusable favourable ontology building blocks to recurrent ontology modelling problems, thus avoiding common pitfalls and introducing best modelling practices [9, 14]. Many tools and languages exist for building ontologies using patterns, macros or templates, e.g., [17, 18, 22, 24, 30]. However, they in turn incur the cost of needing tool support to manage and debug the macros or templates as well as the ontologies themselves. The latter is easier, since OWL is a standard with a lot of tool support available. In fact, to our knowledge, existing ontology construction tools rely completely on the resulting OWL ontology for checking the ontological quality of the templating mechanism, if this is addressed at all. The goal of our paper is to show that a powerful macro language for ontologies expressed in common description logics (DLs) can be defined using the description logics themselves. In other words, we present the simple, but novel idea of using ontologies to represent macros for description logics, and call such macros ontology templates or just templates. A template is itself an ontology in the given DL language. Templates may have parameters, may be defined from other templates, and are instantiated by substituting parameters with suitable concept expressions, role expressions, and constants in the ontology. A template defined from other templates may be expanded by recursively replacing template expressions with the ontology they represent. Thus, an expanded template represents the semantics of the pattern in the form of a prototypical ontology. A set of templates can actively be used in the ontology engineering process as an abstraction interface for representing ontological statements at a suitable level of granularity, i.e., using its unexpanded form. The templates themselves may be constructed and maintained, both in isolation and as an expanded ontology, using available ontology editors and reasoners. One can imagine the design of an ontology relying completely on a (relatively small) set of well-organised templates managed by ontology experts, while the bulk content of the ontology is represented as a (large) set of template instances, typically managed by domain experts. The construction, maintenance and debugging of templates require little additional tool support, as templates may be built using existing ontology editors, and problems related to redundancy and correctness become standard reasoning problems that are supported by existing ontology reasoners. What does require additional tool support, is the process of instantiating templates. A prototype implementation is available which specifies an OWL vocabulary for expressing templates and instances, and software to interpret the vocabulary and produce expansions, queries, transformations and data input formats from the templates [1]. Example 1. To build some intuitions, we give an informal example before formally defining templates and operations on templates. The following expression P(x, y) 7→ {x v ∃R.y} represents a template P with parameters x and y. We may instantiate P with concepts C, D, written P(C, D), to obtain the instance {C v ∃R.D}. Using the template P, we can now define the complex template Q as Q(x, y, z) 7→ {P(x, y), P(y, z), x v ∀S.z}. Expanding Q(x, y, z) gives the ontology {x v ∃R.y, y v ∃R.z, x v ∀S.z}. Any macro or templating language can also be viewed as a query language, where a macro producing an object given values becomes a query asking for values that would produce a given object. In our case, a template is a knowledge base that takes individual names as well as concept and role expressions as input. Using it as a query over another knowledge base is then a way of extracting from this knowledge base concept and role expressions and individuals of interest. This is both a tool for exploring large ontologies and for ontology transformation and maintenance. Due to the fact that templates are also ontologies, problems such as query containment become standard DL reasoning problems. By exploiting the duality between templates as macros and templates as queries, we show that templates find natural use in data exchange and ontology approximation. Pairs of templates can be seen as specifying fairly rich mappings between different ontologies. Since templates are themselves ontologies, existing reasoners can be used to good effect in computing properties of interest. We want to further exploit this fact to explore the different relationships between patterns represented as templates which are useful for their maintenance and use, cf. [11]. 1.1 Related work A predecessor and inspiration to the current form of templates was presented in [19]. To our knowledge, the idea of representing macros for description logics as ontologies is not previously discussed in the literature. However, it is related both to various macro approaches in use, as well as to notions from the field of data exchange. In a paper from 2005 [29], Vrandec̆ić introduces the concept of macros for OWL ontologies and discusses advantages and disadvantages of macros, and their possible applications and implementations. Here, a macro is defined as a symbol, possibly with parameters, and is expanded according to a set of rules. Our papers share many ideas, but Vrandec̆ić’s exposition is less detailed; for instance the format of the rules is left unspecified. Also, it is not clear if macros can be composed from other macros, which is a core feature of our templates. Mappings in the field of data exchange are also related, where queries over source data or knowledge bases are mapped to queries over a target schema or ontology [2, 4, 21]. In a sense, the target queries are used as macros to produce an (incomplete) database or ABox from data retrieved by the source queries. Our approach differs in that templates, when viewed as queries, are a restricted case of higher-order queries, as concept and role expressions are part of the answers. In data exchange, queries are furthermore supposed to produce, as far as possible, a ground database or ABox, as opposed to a full theory in some logical language. Viewed as queries, templates are a very restricted kind of higher-order queries; they return concept and role expressions in addition to individual names. Higher- order queries for DL knowledge bases have been investigated for OWL [23], but usually with very expressive semantics based on entailment [7]. We recognise the merits of such an approach, but the drawback is that very careful and strong restrictions are required to control decidability and complexity. In our case, the reliance on substitution allows us to bypass these problems. Many practical tools and languages for constructing knowledge bases using template or macro mechanisms exist; a few of these are the following: R2RML [6], OPPL [17] M2 [24], XDP [10, 12] Ontorat [30], Populous [18], XLWrap [20], RDF123 [13], Tawny-OWL [22], Thea [28] and InfixOWL [25]. 2 Preliminaries We take as our starting point the expressive description logic language SROIQ that underlies the W3C standard OWL 2 [16]. Many other well-studied and used DL languages (e.g. DL-LiteR [5] and EL⊥ [3], which underlie OWL 2 profiles) can be defined in terms of syntactic restrictions on SROIQ. Our definitions of SROIQ templates will therefore carry over to these languages in a straightforward manner. SROIQ uses a vocabulary N = NC ∪ NR ∪ NI with countable sets of concept names NC , role names NR , and individual names NI . Complex concepts and complex roles are defined as the smallest sets containing all concepts and roles that can be inductively constructed using the concept and role constructors in Fig. 1, where C, D are concepts, P, R are atomic or inverse roles, S, Q are any roles including role chains, a, b are individual names, and n a positive integer. A SROIQ knowledge base (KB) is a finite set of axioms of the form shown in Fig. 1. Further restrictions apply, so that not every finite set of axioms of this form is a SROIQ knowledge base1 . For instance, S · Q v R and Dis(P, R) is an illegal combination of axioms. See [16] for further details. Expression Syntax Semantics Subst. app. I I Complement ¬C ∆ \C ¬(Cσ) Intersection C uD C I ∩ DI Cσ u Dσ Union C tD C I ∪ DI Cσ t Dσ Exist. restr. ∃R.C {x | ∃yhx, yi ∈ RI ∧ y ∈ C I } ∃(Rσ).(Cσ) Univ. restr. ∀R.C {x | ∀yhx, yi ∈ RI → y ∈ C I } ∀(Rσ).(Cσ) Card. restr. ≥nR.C {x | #{y | hx, yi ∈ RI ∧ y ∈ C I } ≥ n} ≥n(Rσ).(Cσ) Self restr. ∃R.Self {x | hx, xi ∈ RI } ∃(Rσ).Self Nominal {a} {aI } {aσ} Inv. role R− {hy, xi | hx, yi ∈ RI } (Rσ)− Univ. role, conc. U, > ∆I × ∆I , ∆ I U, > (invar.) Empty conc. ⊥ ∅ ⊥ (invar.) Chain (w) S·Q S I ◦ QI Sσ · Qσ Axiom Syntax Semantics Subst. app. I I Conc. incl. CvD C ⊆D Cσ v Dσ Role incl. wvR w I ⊆ RI wσ v Rσ Reflexivity assert. Ref (R) RI is reflexive Ref (Rσ) Role disjointness Dis(P, R) P I ∩ RI = ∅ Dis(P σ, Rσ) Concept assert. C(a) aI ∈ C I Cσ(aσ) Role assert. R(a, b) haI , bI i ∈ RI Rσ(aσ, bσ) Neg. role assert. ¬R(a, b) haI , bI i 6∈ RI ¬Rσ(aσ, bσ) Fig. 1. Syntax, semantics, and substitution application for SROIQ A DL interpretation is a pair h∆I , ·I i where ∆I 6= ∅ and ·I is a function such that aI ∈ ∆I for all a ∈ N I , AI ⊆ ∆I for all A ∈ NC , and RI ⊆ ∆I × ∆I for all R ∈ NR . Interpretation of concept and role expressions is inductively defined as given in Fig. 1. An axiom φ is satisfied by I if I satisfies the respective constraint in Fig. 1, and a knowledge base K is satisfied by I if I satisfies every axiom in K. Substitutions. Let L be a description logic language. An L-substitution σ is a function from the sets of concept, role, and individual names to, respectively, the sets of concept expressions, role expressions, and individual names allowed in L. Given a set of concept, role, and individual names S, the restriction of a substitution σ to the elements of S is denoted σ|S , given by σ|S (x) = σ(x) if x ∈ S, and σ(x) = x otherwise. Let σ be an L-substitution. We recursively define the result of applying an L-substitution σ to the concepts, roles, and axioms in the DL SROIQ according to Fig. 1. The result of applying σ to an L-knowledge base K is the set of axioms Kσ obtained by applying σ to every axiom in K. 1 Since we do not distinguish between terminological axioms and assertions in this paper, we also use “knowledge base” and “ontology” interchangeably. Closure under substitutions. Let L, K, and σ be as above. Since there may be restrictions on what set of (L-)axioms form L-knowledge bases, Kσ may not be an L-knowledge base, even though K is. We say that Kσ is a legal instance for L if Kσ is an L-knowledge base. When L is understood from context, we will simply say that Kσ is legal. We say that L is closed under substitutions if applying an L-substitution to an L-knowledge base always produces a legal instance. Working with substitutions and notions based on substitutions in a description logic which is not closed under substitutions is necessarily somewhat more intricate. In particular, the notions of containment presented in Sec. 4 can behave counterintuitively in this case. In this paper we therefore restrict ourselves to fragments of SROIQ that are closed under substitutions. The general case will be presented in future work. SROIQ itself is not closed under substitutions. However, any set of SROIQ axioms that do not mention role chains is a legal SROIQ knowledge base (see [16]). Accordingly, ALCHOIQ, the fragment of SROIQ that does not allow role chains, is closed under substitutions. SHIQ [15] and EL++ [3] are not closed under substitutions, while ALC [27] is. 3 Ontology Templates Let L be a DL language. An L-template is an L-knowledge base T together with a set param(T ) of distinguished concept names, role names, and constants from T called the parameters. Given an L-substitution σ, we define the instance T σ of T to be T σ|param(T ) . Example 2. We write PartOf(part, whole) 7→ {whole v ∃hasPart.part} to desig- nate the template PartOf which has a single axiom knowledge base {whole v ∃hasP art.part} where hasPart is a role name and the concept names part and whole are parameters. Let σ be the substitution {part 7→ SteeringWheel , whole 7→ Car }, then PartOfσ = PartOf(SteeringWheel , Car ) is the following instance of PartOf: {Car v ∃hasPart.SteeringWheel }. Note that also PartOf(part, whole) is an instance of PartOf with the identity function as substitution; this instance is {whole v ∃hasPart.part}. If several templates have been defined, it would be convenient to re-use existing templates to create new ones. To that end, we define a complex template as a template that, in addition to axioms, contains one or more (complex) template instance statements. To avoid circular templates that cannot meaningfully be expanded, we demand that the digraph given by one complex template containing an instance statement of another template be acyclic. In addition, to ensure unique expansions we pose requirements essentially to the effect that parameters in a complex template do not occur as non-parameters in its descendants. Instantiating a complex template T using a substitution σ is then defined as before, with the application of σ to an instance statement T τ being T τ σ. It is clear that a complex template can be re-written into an equivalent non-complex template, by recursively replacing each template instance statement with the corresponding instance. Doing so is called expanding a complex template. For the remainder of the paper, we assume that all templates are expanded, i.e., non-complex, unless noted otherwise. Example 3. Let QualityValue be the template QualityValue(x, hasQuality, uom, val) 7→ {x v ∃hasQuality.(∀hasDatum.(∃hasUOM .{uom} u ∃hasValue.{val}))} which intuitively expresses that x has a quality with a given value val with a given unit of measure uom. Using this template and the PartOf template from Ex. 2, we can define the complex template PartLength as PartLength(whole, part, length) 7→ {PartOf(part, whole), QualityValue(part, hasLength, meter , length)} which expresses that the whole has a part with a given length measured in meters. An example instance of the template is PartLength(Porsche123 , SoftTop, 3 .40 ) stating that (the car) Porsche123 has a softtop (roof) of length 3.40 meters. The expansion of PartLength(whole, part, length) is {whole v ∃hasPart.part, part v ∃hasLength.(∀hasDatum.(∃hasU OM.{meter} u ∃hasValue.{length}))}. A clear motivation for using templates as ontology macros is as a practical implementation for applying and composing ontology patterns when engineering ontologies, as mentioned in Sec. 1. Currently, ODPs offer little framework for actually using the patterns in the construction of an ontology other than importing and/or copying and extending the ontology representation of the pattern manually. There is no prescribed way of representing if and how a pattern has been used. By regarding an ODP as a template where the relevant concepts, roles and individuals are marked as parameters, we can simply instantiate the pattern to get a customised copy of it fit for the ontology engineering task at hand. The template instance expression serves as documentation of how the template pattern is used. Creating new patterns using the techniques in [12, 26], e.g., specialising, cloning, composing and templating, is made simple with templates, as illustrated by the examples above. A set of ODPs represented as templates can actively be used in the ontology engineering process as an abstraction interface for representing ontological statements at a suitable level of granularity, i.e., possibly in their unexpanded form. The templates themselves may be constructed and maintained, both in isolation and as an expanded ontology, using available ontology editors and reasoners. 3.1 Templates as Queries A template T can also be viewed as a query, retrieving from some knowledge base O all concept and role expressions as well as individuals that, when used as input to T , would produce a subset of O — a notion dual to that of a template instance. Formally, the result of evaluating T on O is the set of substitutions eval(T, O) = {σ|param(T ) | T σ a satisfiable instance such that T σ ⊆ O}. We require satisfiabil- ity to make templates as queries well-behaved even in the case of an unsatisfiable KB O. This becomes particularly useful when O is unsatisfiable due to axioms that have nothing to do with T . Example 4. Let PartLength be the template as defined in Ex. 3. To get all lengths of the parts of a Porsche123, we can use the following template as query: PartLength(Porsche123 , part, length). Evaluating this template over an ontology containing the example instance in Ex. 3 will give an answer set containing the single substitution {part 7→ SoftTop, length 7→ 3 .40 }. Using templates as queries for extracting pattern instances may be useful in many cases; for instance, representing an ontology as a set of template instances, rather than its DL axioms, should convey a better picture of the contents of the ontology to a human user. Also, there is a case to made for using templates both as macros and as queries in data exchange settings and for translating between different ontology languages. This is discussed further in Sec. 5. When querying an ontology O with a template T one might be interested in answers which are, e.g., semantically entailed by O, rather than syntactically stated in O. We point to this issue again in Sec. 6. For our current, expository, purposes, however, the simpler syntactic definition of eval(T, O) is sufficient. Complexity. Deciding whether there exists a substitution such that T σ ⊆ O is NP-complete. Membership is obvious, while for hardness, we reduce from 3-colourability by using axioms of the form A u B v > to simulate the edges of the input graph, where A, B are vertices. Let this KB be the template T , with every vertex a parameter. We likewise encode K3 , the complete graph on three vertices, and call it O. It is clear that the input graph is 3-colourable if and only if there exists a substitution σ such that T σ ⊆ O. Therefore, the complexity of deciding whether eval(T, O) is empty is the greater of NP and the complexity of checking whether a candidate substitution σ is such that T σ is a satisfiable instance. The complexity of checking satisfiability depends on the language of T , and is a well-studied topic; see [8] for an overview. 4 Reasoning about Templates Whether viewing templates as macros or queries, it would be useful to be able to discuss and decide various relationships between them. For templates, a natural idea is to consider notions of containment between the instances produced by two templates. Below, we define two such notions, one based on set inclusion and corresponding to containment of templates as queries, and one based on logical consequence. For the latter, we will show in Sec. 5 how it can be applied to the setting of data exchange. Furthermore, we consider the question of whether a template T can be used to describe a given knowledge base. Being able to decide this is important when considering the practical usability of a set of templates, and show a simple characterisation for it. In the following, we assume that T1 and T2 are L-templates such that param(T1 ) ⊆ param(T2 ). We say that T1 is syntactically contained in T2 , written T1 ⊆s T2 , if T1 σ ⊆ T2 σ for every substitution σ. It is worth noting that the the requirement param(T1 ) ⊆ param(T2 ) is only seemingly restrictive to this definition: in fact, syntactic containment implies parameter containment. The following theorem characterises the relationship between syntactic con- tainment and the template parameters. Theorem 1. Let T1 and T2 be L-templates. Then the following are equivalent: 1. T1 ⊆s T2 ; 2. T1 ⊆ T2 and no axiom or assertion in T1 contains a parameter from param(T2 ) \ param(T1 ) 3. T1 σ 0 ⊆ T2 σ 0 , where σ 0 maps each concept, role, or individual name to a new, previously unused name. Proof. 1 → 2 : Choosing σ as the identity shows that T1 ⊆ T2 . Let ϕ(P2 ) be an axiom or assertion in T1 such that P2 ∈ param(T2 ) \ param(T1 ). Then ϕσ|T1 (P2 ) ∈ T1 σ for every σ. Choose σ 0 such that σ 0 (P2 ) = P20 for a new and previously unused symbols P20 and the identity otherwise. Applying σ 0 |T1 to ϕ(P2 ) yields ϕσ 0 |T1 (P2 ), while σT0 2 yields ϕσ 0 |T2 (P20 ). In particular, ϕσ 0 |T1 (P2 ) 6∈ T2 σ 0 and therefore T1 σ 0 6⊆ T2 σ 0 . 2 → 3 : Let σ 0 be as described in the theorem and let ϕ ∈ T1 be an axiom or assertion. Applying σ 0 |T1 to ϕ yields the same as applying σ 0 |T2 to ϕ: if ϕ does not contain parameters, then ϕσ 0 = ϕ in both templates; if it contain parameters they must come from param(T1 ), and hence ϕσ 0 |T1 = ϕσ 0 |T2 . Hence T1 σ 0 ⊆ T2 σ 0 . 3 → 1 : Proof by contraposition: Assume σ is a substitution such that ϕσ|T1 is not in T2 σ for some axiom or assertion ϕ ∈ T1 . If ϕ 6∈ T2 then T1 σ 0 6⊆ T2 σ 0 for σ 0 as defined in the theorem. If ϕ ∈ T2 then ϕ must contain a parameter P from param(T2 ) \ param(T1 ), since ϕσ|T1 6∈ T2 σ. Thus ϕσ 0 |T1 still contains P , since σ 0 |T1 acts as the identity on names not in param(T1 ). P is not in the image of σ 0 |T2 and therefore ϕσ 0 |T1 6∈ T2 σ 0 , i.e., T1 σ 0 6⊆ T2 σ 0 . Similarly to above, we say that a template T1 is entailment contained in T2 , written T1 ⊆e T2 , if T2 σ |= T1 σ for every substitution σ. Theorem 2. Let T1 and T2 be L-templates where param(T1 ) ⊆ param(T2 ). Then T1 ⊆e T2 if and only if T2 σ 0 |= T1 σ 0 , where σ 0 is a substitution that maps each concept, role, and individual name to a fresh, previously unused name. Proof. We need only prove the “if” direction, which we show by contradiction. Assume there exists a substitution σ and a model M such that M |= T2 σ and M 6|= T1 σ. We expand this model to M 0 by taking into account the fresh names from σ 0 : define M 0 (P σ 0 ) = M (P σ) for parameters P ∈ param(T2 ). Then by the standard inductive constructions, we get M 0 (ϕσ 0 |param(T2 ) ) = M (ϕσ|param(T2 ) ) and hence M 0 |= T2 σ 0 and M 0 6|= T1 σ 0 . Since templates as macros and templates as queries are dual to each other, the fundamental notion of feeding the answers of one query into another (used in many applications for first-order queries) becomes more powerful. In the following, we define this operation formally and give examples of its use. a convenient bit of notation. Given a set of substitutions S, First, we will need S define instsat (T, S) = {T σ | T σ satisfiable, σ ∈ S}. Then a template T is said to produce a knowledge base O if there exists a set of substitutions S such that O = instsat (T, S). Now, we define the move or materialise operator as follows: Let T1 and T2 be two L-templates with param(T1 ) ⊆ param(T2 ), and let O be a knowledge base. We define M (O, T1 , T2 ) = instsat (T2 , eval(T1 , O)). This operator can be used to decide whether a knowledge base O is comprised entirely of instances of a given template T1 , by checking whether M (O, T1 , T1 ) = O. The axioms in O \ M (O, T1 , T1 ), if not empty, are the ones that do not match any axioms in the template. This is summarised in the following theorem. Theorem 3. Let T be a template and O a knowledge base. T can produce O if and only if M (O, T, T ) = O. 5 Using Templates for Data Exchange Templates can be used for data exchange. In particular, observe that two L- templates TS and TT with param(TT ) = param(TS ) define an implicit mapping from any satisfiable instance TS σ to the instance TT σ. This observation can be exploited for data exchange. Let OS be a source knowledge base, and TS a template describing the concepts, roles, and individuals from OS that we wish to transfer to a different setting (e.g., into some other knowledge base). To do so, we use a target template TT , potentially by renaming parameters in an existing template that we have used to build other parts of our target KB. We can now use TS and TT as the body and head of a data exchange mapping. The result of applying such a mapping is precisely captured by the operator M defined in Sec. 4. Example 5. Assume that the knowledge base OC models partonomy relationships (between car components) using the role isComponentOf , and suppose we want to translate these relations into using the hasPart role used by the PartOf template as defined in Ex. 2. This can be achieved by the following data exchange setting using the PartOf template as query and the following template as macro: CMPT(part, whole) 7→ {part v ∃isComponentOf .whole}. The materialisation of the exchange is M (OC , PartOf, CMPT) = instsat (CMPT, eval(PartOf, OC )). Let OT = M (OS , TS , TT ). It is possible that TT is more restrictive than TS when it comes to satisfiable instances. If so, then some of the substitutions retrieved by TS create unsatisfiable instances of TT , which are then discarded. We can check whether this occurs by reversing the materialisation, and considering the KB OS0 = M (OT , TT , TS ). Since OS may have a lot of statements not retrieved by TS in the first place, the two are not comparable. However, consider the subset of OS that TS does retrieve, that is, M (OS , TS , TS ) ⊆ OS . It is always the case that M (OT , TT , TS ) ⊆ M (OS , TS , TS ), since for every axiom φ in M (OT , TT , TS ) we have that there exists a substitution σ such that φ ∈ TS σ. Then, we have that TT σ ⊆ OT = M (OS , TS , TT ), and hence that TS σ ⊆ OS . Therefore, σ ∈ eval(OS , TS ), and hence φ ∈ M (OS , TS , TS ). If this inclusion is an equality, then in terms of concepts retrieved and in- serted, we have lost no information. In fact, we have kept the syntactic form of the axioms as they appear in the templates. When is this always the case, i.e., M (OT , TT , TS ) = M (OS , TS , TS ) for every OS ? Recall that we assumed that L is closed under substitutions — it follows that this becomes a ques- tion of conditional satisfiability. We want the following property: For every σ, if TS σ is satisfiable, then so is TT σ. If the DL language we are working in allows unrestricted equivalence axioms, then this problem is equivalent to checking whether there exists a set of equivalence axioms S = {A ≡ φ | A ∈ param(TS ), φ a concept/role expression or individual name} such that TS ∪ S is satisfiable but TT ∪ S is not. This is a difficult problem, but as a preliminary result, we can show that entailment containment is sufficient, and hence that syntactic containment is also. Theorem 4. Let L be a DL language, and TS , TT be L-templates with param(TS ) = param(TT ). We have that M (OT , TT , TS ) = M (OS , TS , TS ) for every L-KB OS if TT ⊆e TS . The converse is false. Proof. Let TS (A) = {A v B} and TT (A) = {A v C}. It is clear that for any OS , all substitutions for A create satisfiable instances of both TS and TT . Equally, it is clear that there is no containment between TS and TT . On the other hand, let OS be arbitrary. If TT ⊆e TS , then for every σ ∈ eval(OS , TS ), TT σ is satisfiable, and hence TT σ ⊆ OT . Then, we have that σ ∈ eval(TT , OT ), and thus that TS σ ⊆ M (OS , TS , TS ). The above notion of not losing information is rather restrictive. More natural is the semantic notion, whether M (OT , TT , TS ) |= M (OS , TS , TS ). Since equality implies entailment, the above result applies also to this case. However, we do not yet have a characterisation for the general case. 6 Conclusion and Future Work We have presented ontology templates, a notion of ontology macros for the DL SROIQ. We have shown how such macros can be used to assist knowledge base creation and maintenance, in particular by treating templates as queries as needed. We have also presented preliminary results on relationships between templates, and argued that they have a use within data exchange. In addition to extending our preliminary results, we plan to investigate the areas below. Closure under substitution. As specified in Sec. 2, we have restricted ourselves to description logics that are closed under substitutions. Several notable description logics, including SROIQ itself, do not have this property. Thus extending our scope to such DLs is an important current and future consideration. In particular, we are investigating suitable conditions on substitutions that guarantee that an instance of an L-template is always an L-ontology for relevant descriptions logics L. We hope that such conditions will allow us to compare templates across DL languages. For the rest of this section we continue to assume that L is closed under substitution, that all substitutions are L-substitutions, and that all templates T and KBs O are in L. However, the research questions below have natural extensions to description logics that are not closed under substitution. Queries and entailment relations. Recall from Sec. 3.1 that a template T can be used as a query on a KB O. Intuitively, such a query searches O for instances of the pattern expressed by T . According to the definition in Sec. 3.1, the query returns the parameter substitutions σ such that T σ ⊆ O and T σ is satisfiable. Since this is formulated in terms of set inclusion, evaluating T over O returns only the instances of T that are explicitly in O. However, one might also be interested in instances that are entailed by O, for whatever notion of entailment one finds relevant. For semantic entailment, for instance, the results of the query would be parameter substitutions σ such that T σ is satisfiable and O  T σ. Example 6. Let T be the template P(x, y) 7→ {x v y} and O the KB {A v B, B v C}. The result of querying O with T with respect to set inclusion and semantic entailment, respectively, are eval(T, O) = {{x 7→ A, y 7→ B}, {x 7→ B, y 7→ C}} and eval (T, O) = {{x 7→ φ, y 7→ ψ} | φ, ψ L-concept expressions, and O  φ v ψ}. In particular, {x 7→ A, y 7→ C} is not in eval(T, O), but it is in eval (T, O). In general, eval (T, O) is an infinite set, containing “redundant” concept and role expressions such as A u A, as well as concept names that do not occur in O. Thus on the one hand, eval(T, O) is too restrictive. On the other hand, eval (T, O) is too permissive, resulting in an infinite set on the trivial ontology of Ex. 6, and allowing clearly redundant answers. We plan to investigate notions of evaluation of a template over an ontology that lie between these two extremes. Knowledge base translations and templates. Let ` be an entailment relation between L-ontologies, such as set inclusion or semantic entailment. Together with the notion of L-substitution, this induces a mapping, or translation, between ontologies. A translation f : O → O0 is a substitution σ with the properties that 1) for any name x, if σ(x) 6= x then x occurs in O and f (x) is an expression constructed from names occurring in O0 , and 2) O0 ` Oσ. Such translations compose, and so form a category, i.e. a formal system of morphisms. Although well-known, such translations do not seem to have been studied in the DL context. Templates lend themselves well to be studied in the setting of formal systems of ontologies and translations. First, they can be defined there, as simply a special kind of translation between two ontologies. Second, the operations involving templates, e.g. extending an ontology by a template instance and querying an ontology with a template, can be represented using basic categorical operations. In general, the study of templates in the system of ontology translations provides a flexible and formal language and framework for the representation of templates and the formulation and study of their relations. Further operations that naturally suggest themselves in this setting are, in particular, allowing for the parameters themselves to form an ontology, different from the template ontology. This allows for conditional extensions of ontologies by template instances; the template first queries the ontology for an instance of the parameter pattern, and if one is found, it extends this pattern with an instance of the template pattern. It also becomes possible to use templates as a form of constraint, expressing that whenever an instance of the parameter pattern is present in an ontology, the ontology must also witness the corresponding instance of the template pattern. References 1. Ontology templates. http://swtmp.gitlab.io. 2. M. Arenas, J. Pérez, J. L. Reutter, and C. Riveros. Foundations of schema mapping management. In J. Paredaens and D. V. Gucht, editors, Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’10), pages 227–238. ACM, 2010. 3. F. Baader, S. Brandt, and C. Lutz. Pushing the EL envelope. In L. P. Kaelbling and A. Saffiotti, editors, IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005, pages 364–369. Professional Book Center, 2005. 4. M. Bienvenu, B. ten Cate, C. Lutz, and F. Wolter. Ontology-based data access: A study through disjunctive datalog, csp, and mmsnp. In Proceedings of the 32Nd Symposium on Principles of Database Systems, PODS ’13, pages 213–224, New York, NY, USA, 2013. ACM. 5. D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The dl-lite family. J. Autom. Reasoning, 39(3):385–429, 2007. 6. S. Das, S. Sundara, and R. Cyganiak. R2rml: Rdb to rdf mapping language. Technical report, W3C, 2012. 7. G. De Giacomo, M. Lenzerini, and R. Rosati. Higher-order description logics for domain metamodeling. In W. Burgard and D. Roth, editors, Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. AAAI Press, 2011. 8. F. M. Donini. Complexity of reasoning. In F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors, The Description Logic Handbook: Theory, Implementation, and Applications, pages 96–136. Cambridge University Press, 2003. 9. A. Gangemi and V. Presutti. Ontology Design Patterns, pages 221–243. Springer, 2009. 10. K. Hammar. Ontology design patterns in webprotege. In Proceedings of the ISWC 2015 Posters & Demonstrations Track co-located with the 14th International Semantic Web Conference (ISWC-2015), Bethlehem, PA, USA, October 11, 2015., 2015. 11. K. Hammar et al. Collected Research Questions Concerning Ontology Design Patterns, chapter 9, pages 189–198. Volume 025 of Hitzler et al. [14], 2016. 12. K. Hammar and V. Presutti. Template-based content odp instantiation. Work- shop on Ontology and Semantic Web Patterns, published online: http:// ontologydesignpatterns.org/wiki/images/1/11/WOP2016_paper_01.pdf. 13. L. Han, T. Finin, C. Parr, J. Sachs, and A. Joshi. A.: Rdf123: from spreadsheets to rdf. In ISWC. Springer, 2008. 14. P. Hitzler et al., editors. Ontology Engineering with Ontology Design Patterns: Foundations and Applications, volume 025. IOS Press, Amsterdam, 2016. 15. I. Horrocks. Practical reasoning for very expressive description logics. In Journal of the Interest Group in Pure and Applied Logics 8, pages 293–323, 2000. 16. I. Horrocks, O. Kutz, and U. Sattler. The even more irresistible SROIQ. In KR, pages 57–67. AAAI Press, 2006. 17. L. Iannone, A. L. Rector, and R. Stevens. Embedding knowledge patterns into OWL. In ESWC, pages 218–232, 2009. 18. S. Jupp et al. Populous: a tool for building OWL ontologies from templates. BMC Bioinformatics, 13(S-1):S5, 2012. 19. J. W. Klüwer, M. G. Skjæveland, and M. Valen-Sendstad. ISO 15926 templates and the semantic web. W3C Workshop on Semantic Web in Oil & Gas Industry, 2008. 20. A. Langegger. Xlwrap — querying and integrating arbitrary spreadsheets with sparql. In ISWC, pages 359–374, 2009. 21. D. Lembo, J. Mora, R. Rosati, D. F. Savo, and E. Thorstensen. Mapping analysis in ontology-based data access: Algorithms and complexity. In International Semantic Web Conference (1), volume 9366 of Lecture Notes in Computer Science, pages 217–234. Springer, 2015. 22. P. Lord. The semantic web takes wing: Programming ontologies with tawny-owl. In OWLED, 2013. 23. B. Motik. On the properties of metamodeling in OWL. J. Log. Comput., 17(4):617– 637, 2007. 24. M. J. O’Connor, C. Halaschek-Wiener, and M. A. Musen. M2: A language for mapping spreadsheets to owl. In OWLED, 2010. 25. C. Ogbuji. Infixowl: An idiomatic interface for owl. In OWLED, 2008. 26. V. Presutti and A. Gangemi. Content ontology design patterns as practical building blocks for web ontologies. In ER, pages 128–141. Springer, 2008. 27. M. Schmidt-Schauß and G. Smolka. Attributive concept descriptions with comple- ments. Artificial Intelligence, 48(1):1 – 26, 1991. 28. V. Vassiliadis, J. Wielemaker, and C. Mungall. Processing owl2 ontologies using thea: An application of logic programming. In OWLED, pages 89–98. CEUR-WS.org, 2009. 29. D. Vrandec̆ić. Explicit knowledge engineering patterns with macros. In Proceedings of the Ontology Patterns for the Semantic Web Workshop at the ISWC 2005, 2005. 30. Z. Xiang, J. Zheng, Y. Lin, and Y. He. Ontorat: automatic generation of new ontology terms, annotations, and axioms based on ontology design patterns. Journal of Biomedical Semantics, 6(1):4, 2015.