2.1 Definition

Ontology evolution has been defined in various ways. Haase and Stojanovic (Reference Haase and Stojanovic2005) see ontology evolution as the process to ‘adapt and change the ontology in a timely and consistent manner’. Flouris et al. (Reference Flouris, Manakanatas, Kondylakis, Plexousakis and Antoniou2008) define ontology evolution as a process aiming to ‘respond to a change in the domain or its conceptualization’ by implementing a set of change operators over a source ontology. The recently compiled NeOn Glossary of ontology engineering tasks states that ontology evolution is ‘the activity of facilitating the modification of an ontology by preserving its consistency’Footnote ⁵.

A common characteristic of the above definitions is that they have a strict view on ontology evolution focusing only on updating the ontology based on the required changes and therefore they see ontology versioning, the process of managing different ontology versions, as a separate activity. We argue that ontology versioning is intrinsically linked to the ontology evolution task and therefore should always be considered when discussing ontology evolution. As a result, in this paper, we adopt a broader view of ontology evolution encompassing both the changes made to an ontology as well as its versioning.

2.2 Ontology evolution stages

Ontology evolution is not an atomic, well-defined and self-contained notion. Supporting the evolution of an ontology implies the completion of a number of different tasks, for which different approaches can be envisaged. For this reason, several attempts at structuring and conceptualizing the general process of ontology evolution can be found in the literature. While these attempts are often motivated by the need to build a software framework for supporting ontology evolution, they are also useful for practitioners who need to have a complete picture of the tasks involved in ontology evolution. Despite these compelling reasons for a unified process model, the community has often created classifications that separate and isolate ontology evolution tasks (Flouris et al., Reference Flouris, Manakanatas, Kondylakis, Plexousakis and Antoniou2008). For example, the need for changing the ontology can be identified both by analyzing user activity (the main focus of Klein & Noy, Reference Klein and Noy2003; Stojanovic, Reference Stojanovic2004; Vrandecic et al., Reference Vrandecic, Pinto, Sure and Tempich2005; Noy et al., Reference Noy, Chugh, Liu and Musen2006), or external domain data (approach taken by Zablith, Reference Zablith2009), and ontology learning tools (Cimiano & Volker, Reference Cimiano and Volker2005; Maynard et al., Reference Maynard, Funk and Peters2009). Similar to the management side of the evolution, the community has created separate threads under the umbrella of ontology versioning and consistency checking, without connecting them back to the ontology evolution process. We therefore identify the need for a framework, which we refer to as ontology evolution cycle, connecting current views of the ontology evolution process models. We continue with a discussion of current ontology evolution process models and conclude with deriving a unified ontology evolution cycle.

In her thesis, Stojanovic (Reference Stojanovic2004) proposed a framework for ontology evolution. The framework is a six-phase cyclic process, starting with the change capturing phase where changes to be applied to the ontology are identified. Three types of changes are identified based on usage-driven change discovery (i.e., derived from user behavior), data-driven discovery (i.e., derived from changes to the ontology instances) and structure-driven change discovery where changes are derived from the analysis on the structure of the ontology. Hence, this evolution framework treats the ontology as a closed entity by initiating the evolution from the analysis performed on the ontology itself, without opening it to external domain data such as relevant text corpora. Change capturing is followed by the representation phase where the changes are represented following a specific model that the author calls the ‘evolution ontology’. The third phase is the semantics of change phase, during which syntactic and semantic inconsistencies that could arise as a result of the changes are addressed (Tamma & Bench-Capon, Reference Tamma and Bench-Capon2001). A syntactic inconsistency covers cases, such as violating constraints or using entities and concepts that have not been defined in the ontology. A semantic inconsistency occurs when an entity's meaning changes during the evolution process (Tamma & Bench-Capon, Reference Tamma and Bench-Capon2001). The fourth phase is the implementation of change phase coupled with user interaction for approving or cancelling changes. Change propagation is the fifth phase, allowing the update of outdated instances as well as recursively reflecting changes in referenced ontologies in the case of interconnected ontologies. The final phase is the validation phase, which checks that the performed changes led to a valid (or desirable) result, and allows the user to undo such changes if this is not the case.

Klein and Noy (Reference Klein and Noy2003) present a framework to support users when an ontology evolves from one version to another. Their framework is component based, and targets the following ontology evolution tasks: data transformation, where data in the old ontology version are transformed into a format compatible with the new ontology version; ontology update, where changes are propagated to the ontology under evolution; consistent reasoning to keep the ontology under evolution consistent; and, finally, verification and approval, where ontology developers perform final checks. The focus in this approach is mainly on the versioning side of the ontology, as an effect of the evolution. Hence, unlike the previous framework, this work does not deal with a change identification step, but mainly on making sure that the ontology consistently evolves from one version to another.

Noy et al. (Reference Noy, Chugh, Liu and Musen2006) describe a framework for ontology evolution in collaborative environments. This framework is scenario based and consists of various Protégé plugins. It includes the following tasks: examining changes between ontology versions, presented, for example, in the form of a table; accepting and rejecting changes, helpful in curated ontology evolution, where changes are approved or rejected with the change action recorded; and providing auditing information, where authors’ information (e.g., time of change, number of concepts changed) are compiled. Changes are recorded following the Change and Annotation Ontology (discussed by Klein & Noy, Reference Klein and Noy2003 as well). The framework serves as a means to manage collaborative changes to be performed on an ontology, where the changes are proposed by the ontology curators.

Evolva is an ontology evolution tool built on a component-based framework, which aims to evolve ontologies from existing domain data that are external (Zablith, Reference Zablith2009), unlike focusing purely on changes derived from within the ontology as targeted by Stojanovic (Reference Stojanovic2004). Such data can be found in text documents, folksonomies, RSS feeds or a list of terms. Each source requires a different method of content extraction handled by the information discovery component. The data validation component identifies new terms that are relevant to the ontology. It also checks the quality of content and filters out noise generated from the information discovery component. The validated information is passed to the ontology changes component in which lexical databases and online ontologies provide background knowledge for automating and evaluating the integration of new information into the ontology through its relation discovery and validation processes. As the evolution could generate conflicts and problems, such issues are handled at the level of the evolution validation component, by reusing existing solutions for consistency and duplication checks. Finally, the validated ontology is passed to the evolution management component where the user has control over the evolution, and changes are recorded and propagated to dependent ontologies. Part of the framework is implemented as a plugin for the NeOn Toolkit, and reuses some of the functionalities provided by the existing Toolkit plugins. The Evolva framework differs from the previously described frameworks by opening the evolution of ontologies to external domain data, which serve as a starting point to initiate the evolution.

Similar to the work of Noy et al. (Reference Noy, Chugh, Liu and Musen2006), DILIGENT deals with the collaborative aspect in evolving ontologies (Vrandecic et al., Reference Vrandecic, Pinto, Sure and Tempich2005). It is a decentralized user-centric methodology proposing an ontology engineering process targeting ‘user-driven’ ontology evolution, rather than its initial design. At a glance, the process starts by having a core ontology collaboratively built by users. After the building step, the ontology will be locally adapted without changing the core ontology. A board of users will then analyze the local changes, in order to come up with the changes that need to be incorporated in the shared ontology. The requests of changes are supported by arguments using an argumentation framework in order to come up with a balanced decision reflecting all the evolution requests. The changes are revised by the board of knowledge experts in order to maintain compatibility between different versions. The evolution of the ontology is a result of the experts’ decision. Finally, the shared evolved ontology is locally adapted at the different involved locations.

Commonalities can be easily detected in the descriptions of the different frameworks above. Figure 1 depicts the general ontology evolution cycle we rely on in this article and which intends to abstract from the specificity of each framework. This cycle is made of five main steps or tasks (represented in rectangles, where ‘Recording Changes’ and ‘Versioning’ are sub-tasks of the ‘Managing Changes’ step, and the subsumption is depicted by the empty arrow heads), with each step potentially relying on different inputs and background information (represented in the ovals). The ontology in the center serves both as input to all the tasks, and receives input from the ‘Managing Changes’ tasks, hence the double-sided arrow. The cycle is repeated after applying the changes and passing again through the ontology. We hereby define these steps as well as their relation to other frameworks.

Figure 1

Ontology evolution cycle

Detecting the Need for Evolution initiates the ontology evolution process by detecting a need for change. Such a need can be derived from user behavior (i.e., the usage of a system that relies on the ontology) or data sources both internal or external to the ontology. This stage corresponds to the change capturing step in Stojanovic's process model, to the information discovery task of Evolva and to the local changes step of DILIGENT, but it is not present in the other approaches that focus on the versioning aspect of evolution, namely Klein and Noy (Reference Klein and Noy2003) and Noy et al. (Reference Noy, Chugh, Liu and Musen2006).

Suggesting Changes represents and suggests changes to be applied to the ontology. Some approaches handle this task by applying patterns to text corpora representing the domain of the ontology (unstructured sources), while others rely on structured data sources, such as online ontologies, to suggest the appropriate changes. This stage corresponds to the representation phase of Stojanovic, to the data transformation step of Klein and Noy and the relation discovery task of Evolva.

Validating Changes filters out those changes that should not be added to the ontology as they could lead to an incoherent or inconsistent ontology, or an ontology that does not satisfy domain or application-specific constraints. A similar stage is present in all the frameworks that we have previously described. Current approaches handle both a formal validation of changes making sure the ontology is logically consistent as per specified constraints, and a domain validation of changes focusing on the domain relevance of the changes.

Assessing Impact measures the impact on external artifacts that are dependent on the ontology (i.e., other ontologies, application) or criteria such as costs and benefits of the proposed changes. Currently, impact is based on the cost involved in adding a suggested change to the ontology, or the effect of such a change at the application level, for example, to the ability to answer specific queries. Only two frameworks have similar steps, namely Stojanovic's propagation stage and Noy et al.'s auditing step.

Managing Changes applies and records changes and keeps track of the various versions of the ontology. This is a continuous task, active through the entire ontology cycle, and is divided into two sub-tasks: recording the changes realized on the ontology, and keeping track of the different versions of the ontology. Indeed, all existing frameworks acknowledge the need for such a task.

Table 1 gives an overview of the way the steps in the evolution cycle described here relate to the components of the frameworks detailed above. While commonalities exist with other frameworks, one particular advantage of our proposed framework is that it offers a more granular process to evolve ontologies, a bridge among functionalities that are often considered separately within the community. For example, bringing new entities from external data sources has been confined to the area of ontology learning, where the management side of changes is not of core interest. In the next sections, we describe each of the five tasks of our cycle in more detail and survey current approaches, techniques and tools that support them.

Table 1

Relations between tasks of the ontology evolution cycle and components of existing ontology evolution frameworks

3.1 Detecting the need for evolution from data

The need for evolution can be initiated from the analysis of various types of data. While some approaches limit the data analysis to information available within the ontology, for example, the work of Stojanovic (Reference Stojanovic2004), other tools identify ontology changes by analyzing external data sources, including unstructured sources, for example, text documents (Velardi et al., Reference Velardi, Fabriani and Missikoff2001; Cimiano & Volker, Reference Cimiano and Volker2005; Bloehdorn et al., Reference Bloehdorn, Haase, Sure and Volker2006; Novacek et al., Reference Novacek, Laera and Handschuh2007; Ottens et al., Reference Ottens, Gleizes and Glize2007; Maynard et al., Reference Maynard, Funk and Peters2009) and metadata (Maynard et al., Reference Maynard, Peters, d'Aquin and Sabou2007), or structured data, such as databases (Haase & Sure, Reference Haase and Sure2004).

Stojanovic (Reference Stojanovic2004) defines data-driven ontology evolution as the process of discovering ontology changes based on the analysis of the ontology instances, for example, by relying on data mining techniques. Another type of change detection defined by Stojanovic is structure driven, where the evolution is initiated based on the analysis performed on the ontology structure using a set of heuristics. For example, ‘if all subconcepts have the same property, the property may be moved to the parent concept’, or ‘a concept with a single subconcept should be merged with its subconcept’ (Stojanovic, Reference Stojanovic2004).

Another type of data source for detecting the need for evolution are domain data, external to the ontology under evolution. Such more ‘traditional’ forms of storing information about the domain often contain valuable knowledge that should be encapsulated in the ontology itself. Bloehdorn et al. (Reference Bloehdorn, Haase, Sure and Volker2006) based their work on the six-phase ontology evolution process proposed by Stojanovic (Reference Stojanovic2004). They identified that valuable information reside in databases and documents, but require better structuring and easy accessibility through the use of ontologies. Unike Stojanovic (Reference Stojanovic2004), who considers data-driven ontology evolution as the evolution triggered from the ontology instances, they consider data-driven changes as changes happening in external data sources, such as the addition and deletion of documents in a corpus, or changes occurring in databases (Haase & Sure, Reference Haase and Sure2004; Bloehdorn et al., Reference Bloehdorn, Haase, Sure and Volker2006). Other tools that initiate ontology changes from text documents include the ontology learning tools Text2Onto (Cimiano & Volker, Reference Cimiano and Volker2005) and Semantic Pattern Recognition and Annotation Tool (SPRAT) (Maynard et al., Reference Maynard, Funk and Peters2009). Moreover, Evolva detects the need for evolution by identifying terms from various types of data sources including RSS feeds, text corpus or a list of raw terms (Zablith, Reference Zablith2009). In addition, Dino is a framework for integrating ontologies which are learned from text (Novacek et al., Reference Novacek, Laera and Handschuh2007; Laera et al., Reference Laera, Handschuh, Zemanek, Volkel, Bendaoud, Hacene, Toussaint, Delecroix and Napoli2008), and Dynamo is a multi-agent system-based approach that falls in this category of tools as well (Ottens et al., Reference Ottens, Hernandez, Gleizes and Aussenac-Gilles2009). We discuss in more details the processes involved within these approaches in the next sections.

3.2 Detecting the need for evolution from usage

In addition to using data analysis as a starting point for detecting the need for evolution, some approaches rely on the study of usage patterns to which the ontology is subject to. For example, Alani et al. (Reference Alani, Harris and O'Neil2006) propose that, based on what parts of the ontology are mostly used by applications, the ontology can shrink to better fit its purpose in the environment. In addition to application usage, user behavior is studied to detect the need for evolution, which is called usage-driven ontology evolution (Stojanovic, Reference Stojanovic2004). Bloehdorn et al. (Reference Bloehdorn, Haase, Sure and Volker2006) rely on a usage-log, which is a record kept of the interaction between the user and the ontology (e.g., user behavior and contextual search history), to analyze and detect the need for evolution. Such a log file can store information about what has been queried, which elements in the ontology have been viewed by the user, etc., and used to derive usage preferences and suggest changes to the ontology. This source of change is useful to keep the ontology adapted to the user needs, while removing the parts that become unused in the environment. This would indirectly help in the maintenance cost, and increase the efficiency of processing the ontology to perform the required tasks based on the assumption that smaller ontologies are easier to manage and explore. Another work identifies the need for an agile approach to maintain ontologies and adapt them based on the application and user requirements (Luczak-Rosch, Reference Luczak-Rosch2009). Luczak-Rosch (Reference Luczak-Rosch2009) proposes a methodology and framework for ontology maintenance, which takes into account two types of feedback: dynamic application feedback and user feedback. This will help adapt the ontology to the information relevant to the scenario in which it is used. Javed et al. (Reference Javed, Abgaz and Pahl2011) employ pattern detection applied on the ontology's change log analysis. This will help derive ontology changes from analyzing the historical ontology changes, and identifying frequent change sequences. Another approach proposes the use of adaptive ontologies that evolve depending on a user context and evolution of the domains on the Web (Pruski et al., Reference Pruski, Guelfi and Reynaud2011). The objective is to enhance information retrieval from the Web relevant to the user needs.

Table 2 provides a summary of the various methods involved in detecting the need for evolution from data and usage. We can conclude that the majority of evolution detection methods make use of data sources (as opposed to usage information) and that, within data-centric methods, those that exploit text corpora are the most widespread. One possible explanation of this phenomenon lies in the availability of several off-the-shelf corpus analysis methods from the areas of Natural Language Processing (NLP) in general, and ontology learning in particular.

Table 2

Approaches used for detecting the need for evolution

4.1 Suggesting changes by relying on unstructured knowledge

Text2Onto derives ontology changes through processing text documents and extracting ontological entities (Cimiano & Volker, Reference Cimiano and Volker2005). It is designed to overcome the limitations of other ontology learning tools which (i) are domain dependent, (ii) lack user interaction during the ontology learning process and (iii) execute the ontology learning process from scratch whenever a change occurs in the text corpus. Text2Onto uses a Probabilistic Ontology Model, coupled with data-driven change discovery that enables specific changes detection from new text documents, without having to process all the corpus when new documents are added. In addition to the extraction of concepts and instances (i.e., corresponding to the ‘Detecting the Need for Evolution’ task), Text2Onto includes lexico-syntactic pattern-based algorithms to extract various types of relations, including ‘Instance-of’, ‘Subclass-of’, ‘Part-of’ and other general relations. When these relations are discovered between a concept that already exists in the ontology and a newly derived concept, they represent concrete ontology change suggestions.

Similar to Text2Onto, SPRAT suggests ontology changes from text documents (Maynard et al., Reference Maynard, Funk and Peters2009). It combines existing ontology-based information extraction (OBIE) techniques, named entity recognition and relation extraction from text. It provides additional patterns to refine the process of entity identification and relations between them, and to transform them into ontological entities. SPRAT relies on lexico-syntactic patterns applied to text documents to identify terms and their corresponding relations.

Furthermore, Bloehdorn et al. (Reference Bloehdorn, Haase, Sure and Volker2006) propose an architecture applied in a digital library domain or other electronic repositories. The authors specify that ontology learning algorithms, such as the ones provided by Text2Onto, can be used to extract document contents, which can be used to evolve the ontology based on the information in the corpus.

Another tool developed to detect changes from text documents and merging ontologies is Dino (Novacek et al., Reference Novacek, Laera and Handschuh2007; Laera et al., Reference Laera, Handschuh, Zemanek, Volkel, Bendaoud, Hacene, Toussaint, Delecroix and Napoli2008). Dino is a framework for integrating ontologies, and includes a semi-automatic integration of learned ontologies with a master ontology built by ontology designers. It relies on the use of ontology alignment, coupled with agent-negotiation techniques, to generate and select mappings between learned ontologies from text and the base ontology. In more detail, Text2Onto is used to extract information from documents in the Dino framework. The learning algorithms of Text2Onto are customized through a user interface, and the confidence values of extracted terms are fed to an ontology alignment/negotiator wrapper (Novacek et al., Reference Novacek, Laera and Handschuh2007). The learned ontology representing new concepts, and the master ontology collaboratively developed by the knowledge experts are aligned, through a set of mappings between the classes, entities and relations of the two ontologies created using the alignment wrapper. Agreement of the semantics used is reached through negotiation using the negotiation wrapper. An axiom ontology is created containing the merged statements between the learned and the master ontology.

Dynamo also falls in the category of exploiting external data sources for building ontologies (Ottens et al., Reference Ottens, Hernandez, Gleizes and Aussenac-Gilles2009). It consists of a multi-agent system for dynamic ontology construction from domain-specific sets of text documents. Dynamo relies on an adaptive multi-agent system architecture, within a framework where the ontology designer interacts with the system during the process of building the ontology. The system considers the extracted entities from text sources as separate agents, which are related to other entities (agents) through a certain relationship. In other words, an ontology is treated as a multi-agent system.

4.2 Suggesting changes by relying on structured knowledge

Structured knowledge represents and defines conceptual information entities, connected through explicit relations. Such representation allows reusing knowledge entities with less effort compared to the unstructured knowledge sources discussed previously. In this section we focus on approaches that suggest ontology changes during ontology evolution by making use of two types of structured sources: lexical databases and online ontologies.

4.2.1 Lexical databases

WordNet (Fellbaum, Reference Fellbaum1998) is one of the major lexical databases providing a wealth of entities interconnected with taxonomical links represented in the form of hyponyms and hypernyms, in addition to other types of relations including meronymy and holonymy links. WordNet is used to support various tasks including word sense disambiguation (Li et al., Reference Li, Szpakowicz and Matwin1995; Ide & Veronis, Reference Ide and Veronis1998; Banerjee & Pedersen, Reference Banerjee and Pedersen2002), information retrieval (Li et al., Reference Li, Szpakowicz and Matwin1995) and question answering (Pasca & Harabagiu, Reference Pasca and Harabagiu2001; Clark et al., Reference Clark, Fellbaum and Hobbs2008).

Maedche et al. (Reference Maedche, Motik, Stojanovic, Studer and Volz2002) propose the use of WordNet to improve semantic bridging and similarity computation during ontology evolution. Ontology learning tools such as SPRAT (Maynard et al., Reference Maynard, Funk and Peters2009) and Text2Onto (Cimiano & Volker, Reference Cimiano and Volker2005) use pattern-based relation extraction techniques over unstructured data sources to suggest changes. These tools make use of WordNet to improve their pattern detection algorithms, for example, by extracting pattern examples from WordNet's relations.

As part of ontology evolution, WordNet is used to discover taxonomical relations between newly discovered concepts and existing concepts in the ontology (Zablith et al., Reference Zablith, Sabou, d'Aquin and Motta2008). The authors devise a technique based on the WordNet Java libraryFootnote ⁶, which identifies the appropriate relation between two terms, along with the relation path. Since WordNet can be stored locally, extracting information from it is faster than using remote structured sources, such as online ontologies. However, Zablith et al. (Reference Zablith, Sabou, d'Aquin and Motta2008) found that WordNet lacks the richness of named relations and the steadily increasing diversity provided by the online ontologies. As a result, they later used online ontologies as an alternative to WordNet.

4.2.2 Online ontologies

Online ontologies form a ready-to-reuse body of knowledge and have been used to perform a variety of tasks, including ontology matching (Sabou et al., Reference Sabou, d'Aquin and Motta2008) and development (Alani, Reference Alani2006), question answering (Lopez et al., Reference Lopez, Uren, Sabou and Motta2009), folksonomy enrichment (Angeletou et al., Reference Angeletou, Sabou and Motta2008) and word sense disambiguation (Gracia et al., Reference Gracia, d'Aquin and Mena2009). Besides their advantages discussed before, their uptake is also due to their increased availability and the presence of tools, such as Watson (d'Aquin et al., Reference d'Aquin, Baldassarre, Gridinoc, Sabou, Angeletou and Motta2007), Swoogle (Ding et al., Reference Ding, Pan, Finin, Joshi, Peng and Kolari2005) and Sindice (Oren et al., Reference Oren, Delbru, Catasta, Cyganiak, Stenzhorn and Tummarello2008), for discovering and consuming them. The use of online ontologies has been pioneered in the area of ontology building (Alani, Reference Alani2006) and lead to the identification of a few challenges when using this paradigm: (1) Semantic Web tools are not mature enough yet—although the situation has changed dramatically since 2006; (2) not all ontologies created by individuals are made available online; (3) large ontologies can provide big segments, resulting with a big messy ontology that is hard to clean; (4) the quality of the online ontologies affects the overall quality of the resulting ontology; also, a segment of a good ontology does not necessarily preserve the quality of the source ontology.

Zablith et al. (Reference Zablith, Sabou, d'Aquin and Motta2008) use online ontologies as background knowledge for integrating newly discovered concepts in the ontology under evolution. In their Evolva evolution framework, new concepts are discovered from external data sources, including concepts from text corpora or RSS feeds. These concepts trigger the need for evolution, and are integrated by relying on background knowledge provided mainly by online ontologies (Zablith et al., Reference Zablith, Sabou, d'Aquin and Motta2008). Online ontologies enable a mechanism for checking how new concepts connect with existing knowledge in the ontology. Unlike reusing ontology segments as described above by Alani (Reference Alani2006), this work limits the reuse of ontologies to the level of statements, that is, ontologies are not processed as one block of statements. Statements are easier to evaluate by users, and offer a more granular control over what to add or ignore during ontology evolution. The process of identifying the possible relations between concepts relies on the Scarlet relation discovery engineFootnote ⁷. Scarlet (Sabou et al., Reference Sabou, d'Aquin and Motta2008) uses the Watson Semantic Web gateway (d'Aquin et al., Reference d'Aquin, Baldassarre, Gridinoc, Sabou, Angeletou and Motta2007) to automatically select and explore online ontologies to discover relations between two given concepts. For example, when relating two concepts labeled ResearchAssistant and AcademicStaff, Scarlet (1) identifies (at run-time) online ontologies that can provide information about how these two concepts inter-relate and then (2) combines this information to infer their relation. Besides subsumption relations, Scarlet is also able to identify disjoint relations (e.g., ResearchAssistant is disjoint from Professor) and named relations. By reusing online ontologies, new changes proposed to the ontology are ready to be applied without further transformation, as they are already represented in an ontology compatible format.

Table 3 summarizes the approaches discussed in this section and the types of sources they use to suggest ontology changes. Unstructured, textual sources are the most frequent sources for suggesting ontology changes. Structured sources, such as the WordNet lexical database are used to improve the pattern-based relation extraction mechanisms that typically work over textual data (SPRAT, Text2Onto) as well as to derive potential changes from its structure. Finally, the use of online ontologies is a recent, promising trend to ontology change suggestion.

Table 3

Approaches to suggesting ontology changes from external data sources

5.1 Domain-based validation of suggested changes

Domain-based ontology changes validation uses existing domain data to evaluate suggested changes before being applied to the ontology. Approaches in this area differ in terms of (i) their purpose, which can be either domain relevance or correctness; (ii) the granularity of the change (change level) as some assess only the relevance of the newly added concepts/instances, while others validate a logical statement that corresponds to the proposed change; (iii) the techniques they use; and (iv) the type of domain data resources employed. We use these criteria to structure the discussion of the approaches and to summarize them in Table 4.

Table 4

Domain-based validation approaches

Approaches that detect and suggest changes by analyzing text corpora such as Text2Onto (Cimiano & Volker, Reference Cimiano and Volker2005) and SPRAT (Maynard et al., Reference Maynard, Funk and Peters2009), often include statistical techniques to assess the domain relevance of a term that they suggest to add to the ontology. Their purpose, therefore, is to assess relevance in terms of how representative a given term is for a text corpus. These approaches focus on validating individual terms rather than entire statements. The technique employed both by Text2Onto and SPRAT is TF-IDF, an information retrieval measure that quantifies how representative a term is for a given text corpus. Due to relying on statistical measures, these methods usually require a large corpora size to perform well. Additionally, these assessments mainly focus on term relevance with respect to the external corpus and are agnostic to the ontology that is being evolved. However, these approaches are highly useful when large text repositories are available to evolve the ontology.

In Dino (Novacek et al., Reference Novacek, Laera and Handschuh2007), the proposed ontology changes are sorted according to a relevance measure and only those above a certain threshold are shown to the users of the tool. In this case, unlike the previous approaches who mainly focus on term-based relevance, the authors propose applying relevance at the level of triples (i.e., in the form of subject, predicate, object). In this case the relevance measure relies on a string similarity between the entities of the triple, and a set of wanted or unwanted words specified by users. At this level, it is expected that users manually create a list of words that reflect domain relevance. Similar to the previous approaches, this work does not take the ontology into consideration to check the relevance. In other words, this approach is mainly based on matching the labels in the proposed change triple with the user-defined set, without performing structural content analysis that the triple would bring to the ontology.

Zablith et al. (Reference Zablith, d'Aquin, Sabou and Motta2010) also highlight the need for relevance checking in their line of work. In this case the authors propose an approach to change validation that takes into account the ontology to be evolved when computing the relevance of a change triple, that is, it aims to make sure that the proposed change is relevant to the ontology in question. To determine this relevance, their technique compares the evolving ontology to the ontological context of the logical statement that represents the proposed change. This ontological context is extracted from online ontologies where the statement appears through a recursive technique that selects the entities linked to the subject and object of the statement. The comparison between the base ontology and the statement's context uses a pattern-based approach that considers the structure of both data structures. For example, one of the five patterns that the technique relies on is applied when the statement is introducing to the ontology a new concept and this new concept has siblings named identically both in the base ontology and in the statement's context. For example, adding the statement 〈Tutorial, subClass, Event〉 derived from the International Semantic Web Conference ontology contextFootnote ⁸, to the Semantic Web for Research Communities ontologyFootnote ⁹, is ranked as highly relevant because Tutorial has the siblings Workshop and Conference in both data structures. The study and evaluation of this work shows the superiority of the use of relevance patterns, compared to baseline techniques, such as randomly generated statements or context overlap-based techniques (Zablith et al., Reference Zablith, d'Aquin, Sabou and Motta2010). While this work focuses mainly on statement relevance checking, it does not answer the question whether the statement in focus is correct or not.

Additional work has been done on checking the correctness of ontology statements that could be used to filter out invalid relations that should not be added to the ontology in the first place. One approach measures the level of agreement and disagreement within online ontologies on how to represent specific statements, by relying on a formal framework using the semantics within the ontology (d'Aquin, Reference d'Aquin2009). Even though formal measures are applied at this level, we classify this work as a domain-based validation rather than a formal properties one, because it employs online ontologies as domain knowledge to perform the evaluation. Another work checks the correctness of statements on the Semantic Web, allowing the prediction of how two concepts should be correctly linked based both on the length of the relation path connecting the two concepts in online ontologies and the statement's popularity in online ontologies (Sabou et al., Reference Sabou, Fernandez and Motta2009).

Table 4 summarizes the approaches for domain-based validation of changes. We observe a wide variety in terms of the techniques and the domain resources used: (i) approaches stemming from NLP-based research use statistical methods over text corpora to compute term relevance; (ii) Dino moves the focus to statement (rather than term) level relevance although the technique, in essence, measures string similarity between the triple's concepts and a user-specified list of words; (iii) Evolva introduces a technique that takes into account the labels and structure of the evolving ontology, and relies on online ontologies to provide an ontological context for the validated statement. We also discussed methods that measure statement correctness, and could act as a first filter for validating changes.

5.2 Formal properties-based validation

Several recent works have acknowledged the need for imposing custom, application-specific or user-defined properties (in the form of integrity constraints) upon ontologies (Serfiotis et al., Reference Serfiotis, Koffina, Christophides and Tannen2005; Motik et al., Reference Motik, Horrocks and Sattler2007; Lausen et al., Reference Lausen, Meier and Schmidt2008; Tao et al., Reference Tao, Sirin, Bao and McGuinness2010). In this case, formal validation is necessary to prevent cases where the application of a change upon the ontology causes it to violate the imposed integrity constraints. In addition, even if no integrity constraints are considered, Description Logic (DL) (Baader et al., Reference Baader, Calvanese, McGuinness, Nardi and Patel-Schneider2002) or OWLFootnote ¹⁰ ontologies are usually required to be consistent and coherent (see Flouris et al., Reference Flouris, Huang, Pan, Plexousakis and Wache2006), which is another form of validity. Note that in RDF/SFootnote ¹¹ ontologies, inconsistency or incoherence cannot occur.

In this subsection, we study works that prevent invalidities from occurring during changes, through a careful application of the changes guaranteeing that any invalidities that occur will be detected and resolved, either automatically, or with the help of the ontology engineer. For reasons of conciseness and uniformity, we do not consider works which fall into the closely related field of ontology debugging (Flouris et al., Reference Flouris, Manakanatas, Kondylakis, Plexousakis and Antoniou2008), that is, works dealing with (and resolving) invalidities without considering how these invalidities occurred.

The requirement of applying changes in a way that the result satisfies the imposed properties (integrity constraints, consistency, coherency) is called the Principle of Validity. Moreover, validation during changes often requires that the changes performed to guarantee validity are ‘minimal’ (per the Principle of Minimal Change; Alchourron et al., Reference Alchourron, Gärdenfors and Makinson1985), in the sense of having minimal effects on the ontology. Note that, even though various works have tried to quantify the ‘impact’ of a change, or to define what ‘minimality’ is, in various contexts (e.g., Alchourron et al., Reference Alchourron, Gärdenfors and Makinson1985; Gärdenfors, Reference Gärdenfors1992; Flouris et al., Reference Flouris, Plexousakis and Antoniou2006; Konstantinidis et al., Reference Konstantinidis, Flouris, Antoniou and Christophides2008a, Reference Konstantinidis, Flouris, Antoniou and Christophides2008b; Ribeiro et al., Reference Ribeiro, Wassermann, Antoniou, Flouris and Pan2009; Flouris et al., Reference Flouris, Konstantinidis, Antoniou and Christophides2013), this notion is, in principle, application dependent. Finally, in most cases, we also want the original change to be actually applied to the ontology, that is, we do not want the process of resolving the invalidity to ‘undo’ one of the changes that the original evolution operation caused; this is called the Principle of Success.

Originally, validation was performed manually by the editor/curator using ontology editors (e.g., Protégé: Noy et al., Reference Noy, Fergerson and Musen2000, Reference Noy, Chugh, Liu and Musen2006; OilEd: Bechhofer et al., Reference Bechhofer, Horrocks, Goble and Stevens2001) and reasoners used to pinpoint invalidities (for a related evaluation and a list of related editor features, see Stojanovic & Motik, Reference Stojanovic and Motik2002). Since then, more specialized tools appeared, which can identify the changes to be performed to guarantee validity, possibly with some user interaction. User interaction may be direct, through an intuitive interface (e.g., Lam et al., Reference Lam, Sleeman and Vasconselos2005), or indirect through parameters, like evolution strategies (used by Stojanovic et al., Reference Stojanovic, Maedche, Motik and Stojanovic2002). Examples of such tools are KAON (Gabel et al., Reference Gabel, Sure and Voelker2004), OntoStudio (formerly OntoEdit; Sure et al., Reference Sure, Angele and Staab2003) and ReTax++ (Lam et al., Reference Lam, Sleeman and Vasconselos2005).

A formal method for applying changes in the presence of integrity constraints appears in Konstantinidis et al. (Reference Konstantinidis, Flouris, Antoniou and Christophides2008a, Reference Konstantinidis, Flouris, Antoniou and Christophides2008b) and Flouris et al. (Reference Flouris, Konstantinidis, Antoniou and Christophides2013). This work considers explicitly the three principles described above (validity, minimal change and success) and automatically determines the actions to be taken to resolve invalidities created by the update. A declarative approach for data updating in RDF/S ontologies, using the RUL language, appears in Magiridou et al. (Reference Magiridou, Sahtouris, Christophides and Koubarakis2005); this work considers a number of constraints on the resulting RDF/S ontology, and guarantees that the result will satisfy them.

In EvoPat (Riess et al., Reference Riess, Heino, Tramp and Auer2010), the validation is performed using SPARQLFootnote ¹² queries to determine invalidities (called ‘bad smells’ by Riess et al., Reference Riess, Heino, Tramp and Auer2010); a ‘bad smell’ is associated with one or more SPARQL UpdateFootnote ¹³ statements that resolve it. A similar approach (defining inconsistency patterns and resolving them using change patterns) appears in Djedidi and Aufaure (Reference Djedidi and Aufaure2009, Reference Djedidi and Aufaure2010). Moguillansky et al. (Reference Moguillansky, Rotstein and Falappa2008) present an approach for describing the process of detecting and resolving inconsistencies and incoherencies during evolution using ideas from argumentation frameworks. Updating for DL ontologies is addressed by Liu et al. (Reference Liu, Lutz, Milicic and Wolter2006) and Roger et al. (Reference Roger, Simonet and Simonet2002); these works focus on validating and guaranteeing the consistency and coherency of the result. Haase et al. (Reference Haase, van Harmelen, Huang, Stuckenschmidt and Sure2005) use ontology debugging techniques to guarantee the validity of the evolution result.

Another family of approaches uses belief revision (Gärdenfors, Reference Gärdenfors1992) techniques and ideas to validate the consistency of the ontology and guarantee minimal changes. For example, Lee and Meyer (Reference Lee and Meyer2004), deal with ontologies represented in the ALU fragment of DLs; OWL ontologies are handled by Halaschek-Wiener and Katz (Reference Halaschek-Wiener and Katz2006) and Ribeiro and Wassermann (Reference Ribeiro and Wassermann2007) deal in general with knowledge representation formalisms that do not support negation (making it applicable to RDF/S ontologies, as well as ontologies represented using certain DL fragments).

Gutierrez et al. (Reference Gutierrez, Hurtado and Vaisman2006) study the problem of ‘erasing’ in RDF/S ontologies. Erasing consists of removing triples from an RDF/S ontology to reflect the fact that a given relationship is no longer true in the domain represented by the ontology. Even though integrity constraints are not considered, and incoherence or inconsistency cannot occur in RDF/S ontologies, the problem is far from trivial, because the removed triple may reappear in the result through RDFS entailment (thereby violating the Principle of Success). The approach of Gutierrez et al. (Reference Gutierrez, Hurtado and Vaisman2006) addresses this problem using a technique inspired by belief revision.

The most successful paradigm for formalizing the principles of success, validity and minimal change in the context of belief revision is the so-called AGM postulates (Alchourron et al., Reference Alchourron, Gärdenfors and Makinson1985). A series of works studied the feasibility and consequences of applying these postulates in the ontological context (Flouris et al., Reference Flouris, Plexousakis and Antoniou2004, Reference Flouris, Plexousakis and Antoniou2005, Reference Flouris, Plexousakis and Antoniou2006; Flouris, Reference Flouris2006a, Reference Flouris2006b; Flouris & Plexousakis, Reference Flouris and Plexousakis2006). These works showed that the AGM postulates cannot be applied in several ontology representation formalisms, because, in general, DLs are not closed with respect to updates, in the sense that the set of models corresponding to the ‘correct’ update (as specified by the AGM postulates, or any other belief revision paradigm) may not be expressible in the given DL. This motivated the development of approximation techniques, that is, approaches resulting to a DL ontology whose set of models is as close as possible to the desired one (Giacomo et al., Reference Giacomo, Lenzerini, Poggi and Rosati2007; Wang et al., Reference Wang, Wang and Topor2010). Giacomo et al. (Reference Giacomo, Lenzerini, Poggi and Rosati2009) propose two approaches: the first extends DL-Lite_F to a specially designed DL that happens to be closed with respect to data updates (so data updates can be normally supported using belief revision techniques) and the second uses an approximation technique as above. Ribeiro and Wassermann (Reference Ribeiro and Wassermann2006) and Ribeiro et al. (Reference Ribeiro, Wassermann, Antoniou, Flouris and Pan2009) present the belief revision notion of relevance (which was proposed in the belief revision literature as another formalization of the Principle of Minimal Change; Hansson, Reference Hansson1991), as an alternative to some of the AGM postulates for the ontological context. Note that this class of works considers only consistency.

The maxi-adjustment algorithm (Benferhat et al., Reference Benferhat, Kaci, Le Berre and Williams2004) is an approach for repairing inconsistencies in stratified propositional KBs in a minimal manner; the works by Qi et al. (Reference Qi, Liu and Bell2006a, Reference Qi, Liu and Bell2006b) were based on this approach to develop evolution algorithms that guarantee the validity of the result in the context of stratified ontologies. Note, however, that this line of work assumes that ontologies are expressed using disjunctive DLs (Meyer et al., Reference Meyer, Lee and Booth2005). The approach by Qi and Du (Reference Qi and Du2009) proposes three different revision operators that guarantee the consistency of a DL ontology after an update, putting special emphasis on the result being syntax independent. Validation of changes may also be done at the level of the ontology metadata; this is done by Maynard et al. (Reference Zeginis, Tzitzikas and Christophides2007), where the effects of the ontological changes on the ontology metadata (and vice versa) are studied, in order to validate that the data is consistent with respect to the associated metadata, and vice versa.

Table 5 summarizes the works presented in this subsection. The second column describes the ontology representation language that is supported by each work, the third column the type of properties that are considered (e.g., custom validity rules, consistency, coherency) and the fourth column describes how the problems are resolved when the validation check fails (e.g., using user input, an automated process, or some process inspired by belief revision or other approaches). Note that the various works (in the first column) have been grouped in categories, depending on the content of the other three columns (e.g., Protégé and OilEd appear together, because they share the same properties as related to the other columns).

Table 5

Formal properties-based validation approaches

DL = Description Logic

6.1 Application and usage

Former research on assessing the impact of ontology evolution mostly focused on the possible inconsistencies inside the ontology. However, since ontologies are widely used in several application scenarios, the consequences of ontology evolution with respect to the dependent artifacts should be carefully examined as well. The need for such mechanisms was identified in several works that will be presented below. For example, Klein and Fensel (Reference Klein and Fensel2001) differentiate among invalidation of data instances, dependent ontologies and applications. We adopt this classification as a backbone for structuring this section.

Qin and Atluri (Reference Qin and Atluri2009) deal with instance invalidation, where the authors distinguish between structural and semantic validity of data instances and propose approaches to ensure them. To achieve that, they propose semantic views as a subset of the ontology and demonstrate that the semantic view, rather than the entire ontology, is responsible for the validity of a data instance. Those views are then used to detect instance invalidation.

A generic framework allowing the systematic study of ontology evolution and instance data sources, as well as the evolution of ontology-related mappings is proposed by Hartung et al. (Reference Hartung, Kirsten and Rahm2008). The framework supports the computation of several measures to describe individual ontology versions and mappings, as well as their evolution. Then, it is used to evaluate the evolution of the most popular life science ontologies and to determine the impact of the evolution on the dependent mappings and instances.

Ontologies are often interconnected in intricate ontology networks established through reusing ontology elements (e.g., one ontology extends a concept defined in another ontology), alignments established between ontologies or versioning relations. If one of the ontologies in the network evolves, the impact on the other members of the network (i.e., dependent ontologies) should be assessed. For example, an approach that determines whether the changes in one ontology affect the reasoning inside other mapped ontologies is presented by Klein and Stuckenschmidt (Reference Klein and Stuckenschmidt2003): the authors developed a change detection and analysis method that predicts the effect of changes on the concept hierarchy and allows ontologies to evolve without unpredictable effects on other ontologies. Thor et al. (Reference Thor, Hartung, Gross, Kirsten and Rahm2009) propose a generic approach to annotate generated ontology mappings independently from the matching approach used. Then, as the ontology evolves, stability measures are calculated over the annotations to identify the quality of the mappings and the impact of ontology evolution on them.

Regarding the impact of ontology evolution on the dependent applications, MORE (Huang & Stuckenschmidt, Reference Huang and Stuckenschmidt2005) is an early attempt that evaluates the consequences of ontology changes for compatibility with applications that rely on it. The authors show that temporal logic can provide a solid semantic foundation and serve as an extended query language to detect the ontology change and its consequences. Their approach can answer queries about the facts that were true in previous versions that no longer hold, as well as to determine the ontology version that can answer specific queries.

The floating version model (Xuan et al., Reference Xuan, Bellatreche and Pierra2006) is another approach to restrict the evolution scenarios for maintaining compatibility. The authors propose the principle of ontological continuity, according to which the evolution of an ontology should not falsify axioms that were previously true, so only the addition of new information is permitted; this limits the impact of ontology evolution on existing applications.

Wang et al. (Reference Wang, Liu and Ye2008) propose approaches to maintain the consistency and to keep the continuousness of the dependent applications during ontology evolution. A virtual-space framework is put forward and most of the changes are to be made there. The impact of two specific change operations (namely, the change property range and the split property) on the dependent application is evaluated and resolution strategies are proposed.

Recent works try to assess the impact of ontology evolution on the dependent applications based on the end-user's incoming queries. In early works, Liang et al. (Reference Liang, Alani and Shadbolt2006a, Reference Liang, Alani and Shadbolt2006b) keep track of the changes while updating the ontology and use that information to validate and repair queries of the dependent applications. A more formal approach in the same spirit is presented by Kondylakis and Plexousakis (Reference Kondylakis and Plexousakis2011a). A high-level language of changes is employed to capture ontology changes, and efficient algorithms are described to recognize the input queries affected (Kondylakis & Plexousakis, Reference Kondylakis and Plexousakis2012). Besides the identification of the changes that invalidate the query, query rewriting techniques are used to repair the queries and/or produce best overapproximations (Kondylakis & Plexousakis, Reference Kondylakis and Plexousakis2011b). In this context, other approaches apply Stream Reasoning techniques to reason over rapidly changing ontologies (Della Valle et al., Reference Della Valle, Ceri, Barbieri, Braga and Campi2008; Ren & Pan, Reference Ren and Pan2011). In this case, the reasoning occurs taking into account the changes that are continuously applied to an ontology, rather than considering the ontology at a static point in time. This would enable, for example, the ability to answer queries in real-time changing environments (Barbieri et al., Reference Barbieri, Braga, Ceri, Della Valle and Grossniklaus2009). At this level, the evolution impact is directly reflected by the query applied.

Finally, a more liberal schema evolution approach that could be used in ontology evolution is presented by Papastefanatos et al. (Reference Papastefanatos, Vassiliadis, Simitsis and Vassiliou2009, Reference Papastefanatos, Vassiliadis, Simitsis and Vassiliou2010). The authors discuss the problem of performing impact prediction for changes that occur at the schema level. In this approach, schema, queries and views are represented as directed graphs. Those graphs enable the user to create hypothetical evolution events and examine their impact over a graph. They also allow the definition of rules for regulating the evolution impact on the system and to automate its adaptation to evolution events.

6.2 Formal criteria

In addition to application and usage-based impact assessment, formal methods have also been employed to assess the impact of a change on an ontology under evolution. We discuss in this section the impact in terms of (i) assertional effects, (ii) cost of performing a change and (iii) notion of minimal impact.

Assertional effects measure what is gained or lost after performing an ontology change (Pammer et al., Reference Pammer, Serafini and Lindstaedt2009). This work is meant to aid the user to have a quick overview of a change impact, in order to make a decision about whether the change should be applied or not, while preserving conceptual consistency. The work formally describes the assertional effects, and an implementation is supplied as a support for the users during ontology development (Pammer et al., Reference Pammer, Ghidini, Rospocher, Serafini and Lindstaedt2010).

Another approach proposes the evaluation of changes in ontology evolution using an impact function, which computes the cost involved in performing the change (Palmisano et al., Reference Palmisano, Tamma, Iannone, Payne and Doran2008). This cost is aimed for agents using and changing the ontology, to make a better decision whether to apply the change or not. The authors propose an approach to compute such costs without the use of reasoning, but by identifying the parts of the ontology that will be affected as a result of the change. The impact takes into consideration the number of axioms involved in the change, and the expressivity of the ontology parts.

Haase and Stojanovic (Reference Haase and Stojanovic2005) present the notion of minimal impact, a concept dependent on user requirements. The idea is based on selecting and implementing the minimum number of ontology changes, which result in a ‘maximal consistent subontology’. The authors define the concept of maximal consistent subontology, as the part of the ontology to which you cannot add any axiom, without loosing its consistency. Table 6 presents a summary of works involved in measuring and evaluating impact resulting from evolving ontologies, highlighting the popularity of approaches that focus on measuring impact on dependent artifacts.

Table 6

Evolution impact approaches

7.1 Recording changes

One of the crucial tasks related to ontology evolution is the management of the differences (deltas) of subsequent versions of ontologies. This proved to play a crucial role in various tasks, such as the synchronization of autonomously developed versions (Cloran & Irwin, Reference Cloran and Irwin2005) or the visualization and understanding of the evolution history of an ontology (Noy et al., Reference Noy, Chugh, Liu and Musen2006). Deltas are also useful to reduce communication or storage overhead, because they are usually more compact in size than entire versions (so they can be communicated and stored more efficiently) (Papavassiliou et al., Reference Papavassiliou, Flouris, Fundulaki, Kotzinos and Christophides2009, Reference Papavassiliou, Flouris, Fundulaki, Kotzinos and Christophides2013).

Changes can be recorded as they happen in a manual or automatic manner, or they can be a posteriori detected using some change detection tool. Both applications require a change language used to represent such changes; a change language is essentially a set of different changes, along with their semantics, which the delta management system understands and records (or detects).

The recording process itself, which keeps track of changes as they happen, is trivial given a change language, so in this subsection we focus on two different aspects of change management: the various change languages that have been defined in the literature, and the change detection tools that have been proposed.

7.1.2 Change detection tools

To address the problem of identifying the changes between two (subsequent) versions of an ontology when direct recording is not possible, change detection tools can be used. Such tools can identify the changes that happened between versions after the change has occurred, that is, using as input only the two ontology versions. Change detection tools are based on some language of changes, and can be categorized depending on whether the corresponding language is low level or high level.

Low-level change detection tools (e.g., Volkel et al., Reference Volkel, Winkler, Sure, Kruk and Synak2005; Zeginis et al., Reference Zeginis, Tzitzikas and Christophides2007, Reference Zeginis, Tzitzikas and Christophides2011; Konev et al., Reference Konev, Walther and Wolter2008; Kontchakov et al., Reference Kontchakov, Wolter and Zakharyaschev2008; Franconi et al., Reference Franconi, Meyer and Varzinczak2010) usually report simple add/delete operations; despite the simplicity of the underlying change language, such tools differ in their semantics and properties, as well as in the supported ontology representation language. Given that low-level changes are not concise or intuitive enough to guarantee human readability, many such works focus on formally studying the change detection process and guaranteeing useful formal properties for the produced deltas (Zeginis et al., Reference Zeginis, Tzitzikas and Christophides2007, Reference Zeginis, Tzitzikas and Christophides2011; Franconi et al., Reference Franconi, Meyer and Varzinczak2010).

On the other hand, high-level change detection tools usually focus on the definition of a change language that is intuitive and concise enough to capture the editor's intuition. As a result, less focus is placed on the formal properties of the language, or the detection algorithm (Rogozan & Paquette, Reference Rogozan and Paquette2005; Palma et al., Reference Palma, Haase, Wang and d'Aquin2007). This causes the semantics of the various supported change operations to be presented informally, often resulting in unclear definitions; furthermore, there is usually no formal machinery to guarantee any properties regarding the detection algorithm.

Klein (Reference Klein2004), Noy and Musen (2004, 2002) and Noy et al. (Reference Noy, Kunnatur, Klein and Musen2004) all present a high-level change detection approach, which is implemented in PromptDiff, an extension of Protégé, and employs heuristic-based matchers to detect the changes between versions. As a result, the detection process involves an uncertainty aspect, and has been measured to have a recall of 96% and a precision of 93%. A similar approach appears in the context of OntoView (Klein et al., Reference Klein, Fensel, Kiryakov and Ognyanov2002).

Plessers et al. (Reference Plessers, de Troyer and Casteleyn2007) propose detecting changes using temporal queries over a version log that is maintained during updates. The most important feature of this approach is that it can use a dynamic, user-defined change language. Thus, the user can define custom changes, through the Change Definition Language, and these changes can be subsequently detected using the approach. The downside is that the detection process requires a version log to be maintained, so it essentially requires recording information on the changes as they happen; in addition, terminological changes are not supported.

Papavassiliou et al. (Reference Papavassiliou, Flouris, Fundulaki, Kotzinos and Christophides2009, Reference Papavassiliou, Flouris, Fundulaki, Kotzinos and Christophides2013) propose a formal framework for defining high-level change operations and define a set of requirements for such operators, such as conciseness, intuitiveness, consistent application and detection semantics, reversibility and others. Then, a particular language of changes and the corresponding detection algorithm are proposed, and the authors show that their language (and the corresponding detection algorithm) satisfies the proposed requirements. Apart from the detection semantics, emphasis is also put in the ability to traverse the history of versions in both ways by applying the detected changes or their inverses.

A similar approach is COnto-Diff (Hartung et al., Reference Hartung, Groß and Rahm2012), which detects high-level changes according to a language of changes defined by Hartung et al. (Reference Hartung, Groß and Rahm2012). The detection process uses a rule-based approach, coupled with a mapping between the elements (concepts, properties) of the two ontology versions. The application of the detected changes (and their inverses) is also considered in this work.

Table 7 summarizes the works presented in this subsection. For each work, we describe the considered formalism (second column), as well as the characteristics of the change language and the detection algorithm (if any), in the third and fourth column, respectively. Note that the various works (in the first column) have been grouped in categories, depending on the content of the other three columns (e.g., PromptDiff and OntoView appear together, because they share the same properties as related to the other columns).

Table 7

Change languages and change detection approaches

DL = Description Logic

As can be seen also in Table 7, most existing approaches employ high-level change languages, acknowledging the fact that these languages are most useful from a user perspective, because they result in more concise and intuitive deltas. In this respect, the most challenging issue is the identification of a ‘standard’ high-level language that would be suitable for each of the major representation formalisms (e.g., RDF/S, OWL, etc.), as well as the formal definition of its semantics and corresponding detection algorithm. As already mentioned above, the proposed high-level languages are different in structure, and most of them are not coupled with formal semantics and/or are not associated with a deterministic detection algorithm, which causes various problems when it comes to automatically manipulating deltas.

7.2 Ontology versioning approaches

Ontology versioning refers to the ability to handle an evolving ontology by creating and managing its different versions (Klein & Fensel, Reference Klein and Fensel2001). Given that ontologies are often interlinked or reused, versioning of evolving ontologies is necessary to guarantee smooth interoperation. Furthermore, ontologies are being used by various agents, applications or other elements, and a change could potentially cause problems in such accessing elements; in such a case, versioning can allow the agent or application to switch to the older version until such problems are fixed.

To achieve a smooth evolution we need not only to store the different versions of an evolving ontology, but also to manage these versions, with the aim of minimizing any adverse effects that a change in a given ontology could have upon related (dependent) ontologies, agents, applications or other elements. This can be done by relating versions with accessing elements (i.e., ontologies, applications or agents) and transparently providing access to either the current or some older version of the ontology, depending on the needs of the accessing element (Klein & Fensel, Reference Klein and Fensel2001). This ability allows the dependent elements to upgrade to the new version at their own pace, if at all, which is considered a very useful feature (Heflin et al., Reference Heflin, Hendler and Luke1999; Heflin & Pan, Reference Heflin and Pan2004). In fact, it has been argued that ontology versioning should be an indispensable part of ontology management tools such as Protégé (Noy & Musen, Reference Noy and Musen2004).

Several issues are associated with versioning. One such issue is related to identification, namely, how to identify and label new versions. This issue is not as trivial as it may seem: for example, it is not clear whether a subtle syntactic change should result in the creation of a new version or the overwriting of the existing one (Heflin et al., Reference Heflin, Hendler and Luke1999; Klein et al., Reference Klein, Fensel, Kiryakov and Ognyanov2002).

Another issue is related to the identification and recording of the relationship between different versions. The term ‘relationship’ in this context could refer to the identification of which version emerged from which, and how. As such, it could involve information regarding compatibility between the versions (Klein & Fensel, Reference Klein and Fensel2001), fine-grained information regarding the relationships between ontological elements in the two versions (Klein & Fensel, Reference Klein and Fensel2001), the delta that led from one ontology to the other (Klein et al., Reference Klein, Fensel, Kiryakov and Ognyanov2002; Klein, Reference Klein2004) and other metadata regarding the evolution and the versions themselves (Klein et al., Reference Klein, Fensel, Kiryakov and Ognyanov2002). The above information would form a tree of versions, which shows which version evolved out of which and contains some relevant metadata such as those described above.

Maintaining the compatibility information between versions is very important to correctly relate versions with accessing elements without causing problems in the functioning of such elements. Klein and Fensel (Reference Klein and Fensel2001) define and study different types of compatibility. It has been argued that compatibility determination cannot be performed fully automatically (Heflin & Pan, Reference Heflin and Pan2004); to address this problem, Heflin and Hendler (Reference Heflin and Hendler2000) and Heflin et al. (Reference Heflin, Hendler and Luke1999) proposed to make backwards compatibility between versions explicit in a machine readable format using the SHOE language (Luke et al., Reference Luke, Spector, Rager and Hendler1997). This allows a computer agent to determine compatibility between versions, and to choose automatically which version to use; this approach is in contrast with work by Klein and Fensel (Reference Klein and Fensel2001) and Klein et al. (Reference Klein, Fensel, Kiryakov and Ognyanov2002), where a centralized approach is adopted.

Usually, versioning metadata refer to the two versions as a whole; it has been argued that such metadata could also be defined at the level of ontological elements (Klein & Fensel, Reference Klein and Fensel2001). This results in a more fine-grained specification of the relationship between the versions, which allows the explication of the relation between ontological elements and the identification of the evolution history of each element independently.

Another work related to ontology versioning is performed by Redmond et al. (Reference Redmond, Smith, Drummond and Tudorache2008), who present a system for managing changes in a multi-editor environment, providing metadata about different revisions. Kirsten et al. (Reference Kirsten, Hartung, Gross and Rahm2009) design a database to store the changes on biomedical ontologies supporting different kinds of change analysis. Allocca et al. (Reference Allocca, d'Aquin and Motta2009) present an approach for automatically detecting version relations between different ontologies, using heuristics based on the ontologies’ URIs and identifiers.

Another line of work in versioning is inspired by temporal reasoning (Huang & Stuckenschmidt, Reference Huang and Stuckenschmidt2005; Plessers et al., Reference Plessers, de Troyer and Casteleyn2005; Keberle et al., Reference Keberle, Litvinenko, Gordeyev and Ermolayev2007; Grandi, Reference Grandi2009). Obst and Chan (Reference Obst and Chan2005) discuss the architecture and requirements of a system to handle ontology management, by presenting initial ideas regarding the need for a generic versioning system that supports users while evolving ontologies. Theoretical aspects of the problem are studied by Heflin and Pan (Reference Heflin and Pan2004).

Table 8 summarizes the works presented in this subsection. The second column of the table shows the main versioning-related problems that each work addresses, and the third column shows the version-related metadata considered. The various works (in the first column) have been grouped in categories, depending on the content of the other columns.

Table 8

Ontology versioning

Most of the current works related to ontology versioning require human input, or user-provided metadata. The development of an automated versioning system that would automatically detect versions, and, most importantly, compatibility information and/or other metadata between versions, would be a great step forward in the field. Such an automated system would successfully address the problem of ontology interoperability in dynamic settings, which is an important problem being faced in many practical applications involving ontologies.