Supporting Evolving Ontologies by Capturing the Semantics of Change

John Avery [HREF1], Post Graduate Student (PhD), School of Information Technology and Mathematical Sciences,[HREF2] , University of Ballarat [HREF3], Victoria, 3350. j.avery@ballarat.edu.au

Professor John Yearwood [HREF4], Associate Professor, School of Information Technology and Mathematical Sciences,[HREF2] , University of Ballarat [HREF3], Victoria, 3350. j.yearwood@ballarat.edu.au

Abstract

In this paper we examine the notion of ontology evolution. Within a framework of generic ontology we suggest that the evolution of an ontology can be modelled more comprehensively and efficiently by identifying the elements of ontology change. Many of these fundamental units of ontology change are dependant on the ontology language. Here we describe these elements of change for the Web Ontology Language (OWL) by defining an extension of OWL called DOWL.

Introduction

Ontologies are becoming more and more pervasive, they are frequently used in e-commerce, are important topics in medicine and biology, and they form the core of the semantic web. It is important to realise that ontologies are not static. The imperfect nature of the knowledge acquisition process and the dynamic nature of human knowledge mean that in order to best represent knowledge ontologies must evolve.

Traditionally this evolution has been represented using the version mechanisms present in the various ontology languages. These mechanisms provide only simple descriptions of ontology change like version numbering, indicating compatibility, and deprecation. Ideally though the ontology evolution process should be a transparent one; changes to an ontology should not affect the actions of the users nor the operation of applications or software agents.

A fundamental step in solving this problem is capturing the semantics of changes in an ontology; in order for changes to be transparent we need to know not only what has changed but how it has changed.

In this paper we claim that the most efficient and comprehensive way to model these changes is to determine the atomic units of ontology change; these are the indivisible units of ontology change. Although the problem shares much with semantic mapping(Mena et al, 2000; Doan et al, 2002; Noy and Musen, 2003) we use a more fundamental approach in the vein of Ognyanov and Kiryakov's (2002) work in which they track the changes in RDF repositories by considering any change in an RDF repository as the addition or deletion of an RDFtriple.

Using a generic model of ontology we determine the atomic units of ontology change, and then argue that many of these atomic units of ontology change are dependent on the language being used to describe the ontology. The Web Ontology Language (OWL) which is the ontology language of the semantic web is used to demonstrate these language specific ontology changes. We conclude by describing the benefits of capturing the atomic units of ontology change, and contrast this with existing methods.

Ontology Change

In order to discuss concepts like ontology evolution we need ot make clear what we mean by ontology and the terms we use to discuss it. In this paper we consider an ontology to be anything which conforms to our generic ontology model.

In the generic ontology model an ontology is a model of a domain expressed in a formal language. The domain exists in the real world and we model entities from the domain. Entities are arbitrary constructs which correspond to some aspect or aspects of the domain. We call the model of an entity the representation of the entity.

• Transformation Changes of this type are changes in how an entity is modeled. A transformation implies a change to the ontological construct describing the representation, through either the addition, modification, or deletion of a statement.
• Translocation Changes of this type are changes in which entities are modeled. These types of changes capture the intent of the ontology designer and are not described by statements in the ontology.

Many ontology changes involve both transformation and translocation, for example changing the representation of a book entity so that e-books are included in the representation involves both a transformation of the representation (it now has to include e-books), and a translocation of the entity being modeled (an entity of physical books is different to one of physical and virtual books).

Other changes involve only transformation, for example changing the representation of the entity man by adding the notion that is disjoint with the entity woman.

Other changes involve only translocation, for example if the representation of an entity capturing the location of a web service is changed from a URI (representing many kinds of web resources) to a URL (representing only HTTP resources). This is not a transformation (both URI's and URL's are represented by a string), but there is certainly a conceptual difference between the two entities. If we consider this example it becomes clear why we need to capture these purely translocatory changes, i.e. after this change any documents that are annotated with the ontology will be invalid if they contain a location URI that is not a URL. Determining these kind of implications is an integral part of the ontology evolution process.

Ontology Changes in the Generic Ontology Model

We will now list the various atomic ontology changes that can occur in our generic ontology model, and describe both the transformation and translocation facets of these changes.

• Addition The addition of a representation. Addition implies a transformation as a new ontological constructs must be created to describe the representation. Addition implies a translocation as a new entity is being modeled.
• Redefinition A change in how a representation models an entity. Redefinition implies, by definition, a transformation. Redefinition does not imply a translocation; ontology changes that involve a redefinition and a translocation should be described by a redefinition and one of the purely translocation changes (broadening, narrowing, or shifting). Redefinition is language specific and a particularly important aspect of ontology evolution that is discussed in detail in Section 4.
• Deletion The removal of a representation. Deletion implies a transformation as the ontological constructs describing the representation must be removed. Deletion implies a translocation as an entity that was previously modeled is no longer being modeled.
• Broadening The expansion of an entity so that it captures what it originally captured and more. Broadening implies a translocation as a different entity is modeled. Broadening does not imply a transformation; ontology changes that involve a broadening and a transformation should be described by a broadening and a redefinition.
• Narrowing The contraction of an entity so that it captures only concepts that were captured originally but not all of those concepts. Narrowing implies a translocation as the entity being modeled is different. Narrowing does not imply a transformation.
• Shifting The shift of an entity so that it captures different concepts to the original entity. Shifting implies a translocation as the entity being modeled is different. Shifting does not imply a transformation.
• Coalescing The combination of two or more representations into one representation. Coalescing implies a transformation as ontological constructs are changed in reflection of the representations they describe. Coalescing implies a translocation as the new representation models a new entity and the original entities are no longer modeled.
• Dividing The division of a representation into two or more representations. Dividing implies a transformation as ontological constructs are changed in reflection of the representations they describe. Dividing implies a translocation as the new representations model new entities and the original entity is no longer modeled.

Performing an informal analysis on the various version changes that two well known ontologies (DAML-S and UNSPSC) have undergone, we found no changes that could not be represented in terms of these operators. It is worth noting how we handled the concept of deprecation. The intent of deprecation is typically to remove a concept from an ontology without invalidating documents annotated with a previous version of the ontology, so in this sense the operation corresponds to a deletion. However in some cases a deprecated class was reintroduced, possibly modeling a different entity, the intent of deprecation, was to effectively say "we know we need this, but we are not sure why". This change is modeled by a shift of the entity (and a redefinition of the model).

We do not consider this a flaw in our model, but a weakness in the versioning operators that exist in todays ontology languages. They do not provide the flexibility to model all kinds of changes thus compromises must be made.

OWL

In order to discuss the redefinition class of ontology change at a level of detail beyond the generic model, we must set our discussion in the context of an ontology language. Redefinition's are transformations, changes to an ontological construct, and these constructs are expressed as statements in an ontology language. OWL is the ontology language of the semantic web, it is a recommendation of the world wide web consortium (w3c).

In this section we present a technical overview of OWL in order to facilitate the discussion in the subsequent section. Although OWL comes in various flavours (OWL Full, OWL DL, and OWL Lite) we discuss only the unrestricted flavour (OWL Full) that the other flavours (OWL DL and OWL Lite) are subsets of.

The fundamental building blocks of an OWL ontology are classes, properties and individuals. These objects are identified by an rdf:ID (name).

Individuals

An individual is a single object. For example a Person named John. Typically individuals are members of a class. We indicate an individual like so:

Or using the shorthand notation to indicate class membership:

Classes

Classes are groups of objects (typically individuals). For example the class of People. The members of a class are known as instances. A class is not the same as the set of its instances (called the class extension). That is to say that two classes may have the same class extension, yet be different classes. Classes may be members of their own class extension.

A subclass of a class C' is a class C in which all instances of C are also instances of C' (thus all classes are subclasses of themselves).

We indicate a class like so:

And a subclass like so:

Properties

Properties are objects which are binary relationships between objects. For example John likes Mary.

OWL is property centric which means that unlike most object oriented paradigms in which classes are defined by the properties that belong to them, in OWL, properties are defined by the classes to which they belong. Thus properties have a range that defines values that a property can take by indicating which class or classes the value of the property can belong to and a domain that defines the class or classes that a resource must belong to given that it has a certain property.

A subproperty of a property P' is a property P in which all subject and objects pairs related by P are also related by P' (thus all properties are subproperties of themselves).

We indicate a property like so:

Class Expressions

Class expressions are descriptions of groups of objects that do not necessarily have a name. A class expression may be a named class or an implicitly defined class (anonymous class) defined in one of three ways:

• by the elements of an enumeration;
• by the class of all individuals that satisfy a property restriction;
• by the class of all individuals that are described by a boolean combination of named classes, enumerations, and property restrictions.

Enumerations are simply lists of objects called the instances of the enumeration.

Property restrictions implicitly define an anonymous class that satisfies some set of restrictions on membership to the class. These restrictions can be restrictions based on properties that relate objects to other objects or properties that relate objects to values, the possible restriction types are:

• The owl:allValuesFrom restriction restricts the possible values of the property P to all belong to the class expression. This allows for local range restrictions. This is analogous to the universal quantifier of predicate logic.
• The owl:someValuesFrom restriction implies that at least one value of the property P must belong to the class expression or datatype reference. The owl:hasValue restriction implies that as least one value of the property P must be the individual object or datatype value. These restrictions are analogous to the existential quantifier of predicate logic.
• The owl:minCardinality and owl:maxCardinality restrictions define the class of objects which have respectively, at least N, or at most N, distinct values for the property P. The owl:cardinality restriction is short hand for an owl:minCardinality restriction and an owl:maxCardinality restriction that have the same value for N.

Boolean operators contain a list of class expressions and can be used to combine these class expressions in various ways. These elements are:

• owl:intersectionOf which defines a class which consists of all objects common to all the class expressions.
• owl:unionOf which defines a class which consists of all the objects that belong to at least one of the class expressions.
• owl:complementOf which defines a class which consists of all the objects that do not belong to the class expression.

Anonymous classes used in conjunction with the notion of subclass form an important modeling tool in OWL. For example to ensure that a lecture is held in a lecture theater in a university ontology we would indicate that the class Lecture is a subclass of the implicitly defined class which restricts the value of the hasRoom property to owl:someValuesFrom the LectureTheater class, and restricts the value of the hasRoom property to a cardinality of one.

For a complete description of OWL visit the Web-Ontology (WebOnt) Working Group [HREF5].

Language Specific Ontology Changes

Considering notions like individuals, classes, and properties, in the OWL language gives us some idea of the kind of redefinition operations that can occur, to ontological constructs within the OWL language. Figure 2 depicts a typical ontological construct in OWL, the four parts of the construct have been highlighted and labeled.

Each of these four parts is a candidate for ontology change. Name changes and non-logical changes have no effect on the semantics of the ontology.

Name changes represent a change of the identifier of an ontological construct. For example the MicroComputer class being changed to the PersonalComputer class to better reflect the terminology used by the people using the ontology. Non-Logical changes represent change in comments and labels that are used to inform people about the ontology. Logical changes are probably the most common type of redefinition. They represent changes to the logical specifications of ontological constructs. For example the addition of the notion that the class Man is owl:disjointWith the class Woman, or the extension of the class Publications to include OnlineArticle's. Type represent a change to the to the type of object. In OWL Full any owl:Thing is an individual. Any owl:Thing is potentially a class and/or a property. Thus we need to be able to add and remove the class and property attributes from an ontological construct. This change might occur when for example the Address class becomes the address property.

Figure 2 - A typical OWL construct

Dynamic OWL

Dynamic OWL (DOWL) is a language we have designed which extends OWL with a vocabulary for expressing changes in ontology. It is able to model all the changes thus specified, as well as specific examples of changes of, for example, the Logical or Type varieties. A DOWL ontology points to an ontology specified in OWL or DOWL and contains a description of a change or changes to that ontology. It can be considered a semantic mapping between two versions of an ontology.

The full DOWL language specification can be found at:

  http://uob-community.ballarat.edu.au/~javery/dowl/dowl.html[HREF6]

A DOWL ontology contains a header which points to the ontology being changed (the ontology). Within the header are one or more operators that specify how the ontology is to be changed. The basic format of an operators is:

The operator specific statements depend on the operator, for example if identifier is being renamed, then the operator specific statement would be <xsd:String rdf:value="newname">.

We will not list the entire language specification (it is linked to above),however we will provide the general rules which we have used to build the language. Firstly operators exist for all the types of changes specified in the generic model. The redefinition operator is a superclass of operators for the four types of OWL specific changes (name, non-logical, logical, and type). The type operator is a superclass of a set of operators for defining or undefining something as a class, property or one of the special property types of OWL (i.e. functional property, transitive property).

Logical changes are additions, modifications, or deletions of various properties of objects (like owl:subClassOf, owl:subPropertyOf, owl:disjointWith, owl:sameAs). If the value of the property being modified is named then it can be added, or removed, if it is not named (an anonymous class for example) then it can only be added or redefined. This is a natural consequence of nameless objects, if we can not identify something then we can not remove it directly, we can of course remove it by redefining the properties values so they do not include it (we do not need to redefine named objects as they can be modified directly). These concepts are illustrated in the examples below:

Removing equivalence:

Redefining subclasses:

Ramifications of Ontology Change

In the ideal ontology evolution system a change to an ontology would be seamless, a change would be made and the actions required for that change to be propagated through the web would occur in a timely fashion, and in a way which is undetectable to the users of the ontologies. In order to realise such an ideal we must consider the ramifications of an ontology change. Klein (2002) described three classes of inconsistency that may arise from ontology change. We have expanded and labelled these classes as follows:

• Annotation The meaning of data that is annotated with an ontology may be interpreted differently.
• Dependency If an ontology is dependent on the changed ontology its meaning may be affected by the changes.
• Applications Applications that use the ontology may be hampered by changes to the ontology. In the ideal case, the conceptual knowledge that is necessary for an application should be merely specified in the ontology; however, in practice applications also use an internal model. This internal model may become incompatible with the ontology.
• Inferences Although not included by Klein, a change in an ontology may cause inferences made or queries answered using the ontology to be incorrect.

With these facets in mind we developed a list of possible ramifications of an ontology change, and determined the ramifications of each of our ontology change operators, which we associate with each each operator in the DOWL language specification. The possible ramifications are:

• No Ramifications using an operator of this type of no ramifications. This is included to describe the ramifications of operators that perform "housekeeping" functions in DOWL. It is included so we can relate a ramification to every DOWL operator.
• Human Ramifications using an operator of his type may have ramifications, but only for the interpretation of the ontology by people. This corresponds to operators which change labels and comments, e.g. dowl:changeLabel and dowl:changeComment.
• Identification Ramifications using an operator of this type means that documents may need to be re-annotated to be compatible with the new version of the ontology. Dependant ontologies and inferences may also need to be updated. This correspons to changes in which the name or identifier of an object is changed, e.g. dowl:rename.
• Annotation Ramifications using an operator of this type causes a semantic change in the ontology which may make existing documents invalid when annotated with the new version of the ontology. This corresponds to many kinds of operators, often in conjunction with other ramifications, e.g. dowl:defineAsTransitive. It is also the sole ramification of some operators, e.g. dowl:narrow. If we narrow a class then it is possible that individuals that fit within the original definition do not fit within the new definition.
• Dependency_Ramifications using an operator of this type may cause ontologies dependent upon, and inferences based on, and applications using, the older version of the ontology to no longer be correct. This corresponds to many kinds of operators, often in conjunction with other ramifications, e.g. dowl:defineAsTransitive. It is also the sole ramification of some operators, e.g. dowl:broaden. If we broaden a class then it is possible that reasoning that relied upon the class being a certain entity will fail, e.g. if we used the identifier class to provide a hyperlink to a resource in our application (because the class described a URL), and the class was changed to describe a URI then it is no longer necessarily that the resource can be accessed over the web.
• Inconsistency Ramifications using an operator of this type will not only cause a semantic change in the ontology (thus having annotation and/or dependency ramifications), but may cause the ontology itself to become inconsistent. This corresponds to changes that alter the structure of class or properties, e.g. dowl:redefineRange or dowl:isDisjointWith.

Discussion

Throughout this work we have stressed that we are capturing the atomic units of ontology change, we have built our dynamic ontology language from the ground up, making a minimum number of assumptions about the nature of ontology. Other approaches recognise the need for ontology versioning and capture ontology change(Heflin and Hendler, 2000; Klein, 2001; Klein, 2002), some automatically capture this difference (Noy and Musen, 2003; Heflin and Hendler, 2000), while others consider the important issue of how to propagate change (Maedche et al, 2003). However, these approaches do not take the bottom up approach that we do, they instead build form high level concepts like semantic mapping or ontology systems. Although there is nothing inherently wrong with this approach, we feel that our bottom up approach leads to a more comprehensive exposition of ontology change. For example none of these works distinguish the difference between what we have called transformation and translocation.

Capturing atomic units of change is also likely to be more efficient in terms of the propagation of change through the web. Other approaches to ontology evolution are not necessarily language specific, but to represent the concepts of one ontology language in another can often be a difficult task (Klein, 2001), and require multiple operations. Propagating such complex changes through the web is going to be more time consuming than propagating atomic changes, making the timely delivery of the changes more difficult. In order to verify this claim experimentally we need to be able to compare our system with others, but at this time no systems are in a stage of development which allows this.

Finally none of the other work reveals the language they use to express their changes, although there must, of course, be some representation of the captured changes. Providing a language to express ontology evolution is a more fundamental approach, with all the benefits of any other open development. We do not proscribe any ontology tool, system or methodology.

Conclusion

By analysing a generic model of ontology we have discovered and described the atomic units of ontology change. As some of these atomic units of ontology change are language specific, we proceeded to describe the atomic units in the context of the ontology language of the semantic web, OWL. Finally we presented a dynamic ontology language which captures ontology change by way of these atomic units and can be used as the basis for supporting evolving ontologies.

Future work may involve:

• The exposition of composite operators. Although atomic units are the fundamental units of ontology change, they do not neccessarily correspond to the way in which people think about ontology change. Composite operators are combinations of atomic operators which capture the types of changes that people make to an ontology.
• The development of a theory of ontology change which formally demonstrates that this language cn handle the ramifications of onology change.
• The design and implementation of algorithms for propogating ontology changes. Although we have identified the ramifications of ontology change, handling them so that changes can be tranparently propogated is a particularily complex task.
• The description of dynamic ontology languages that describe the atomic components of change for other ontology languages.

References

Doan, A., Madhavan, J., Domingos, P., and Halvey, A. "Learning to map between ontologies on the semantic web". In The Eleventh International WWW Conference (Hawaii, 2002).

Heflin, J., and Hendler, J. "Dynmaic ontologies on the web". In In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000) (2000), pp. 443-449.

Klein, M. "Combining and relating ontologies: an analysis of problems and solutions". In Wokshop on Ontologies and Information Sharing IJCAI'01 (2001).

Klein, M. "Supporting evolving ontologies on the web". In Proceedings of the EDBT 2002 PhD Workshop (March 2002).

Maedche, A., Motik, B., Stojanovic, L., Studer, R., and Volz, R. "Establishing the semantic web 11: An infrastructure for searching, reusing, and evolving distributed ontologies". In Proceedings of the Twelth International Conference on Wolrd Wide Web (May 2003), ACM Press, New York, pp. 439-448.

Mena, E., Illarramendi, A., Kashyap, V.,and Sheth, A. "Observer: An approach for query processing in global information systems based on interoperation across pre-existing ontologies". In Distributed and Parallel Databases (2000), vol. 8.

Noy, N. F., and Musen, M. A. "Ontology versioning as an element of an ontology-evolution framework". In IEEE Intelligent Systems (2003).

Noy, N. F.,and Musen, M. A. "The prompt suite: Interactive tools for ontology merging and mapping". In International Journal of Human-Computer Studies (2003).

Ognyanov, D., AND Kiryakov, A. "Tracking changes in rdf(s) repositories". In 13th International Conference on Knowledge Engineering and Knowledge Management, EKAW 2002 (2002), A. G´omez-P´erez and V. R. Benjamins, Eds., vol. 2473 of Lecture Notes in Computer Science.

Hypertext References

HREF1

http://uob-community.ballarat.edu.au/~javery/

HREF2

http://www.ballarat.edu.au/itms/

HREF3

http://www.ballarat.edu.au/

HREF4

http://uob-community.ballarat.edu.au/~jyearwood/

HREF5

http://www.w3.org/2001/sw/WebOnt/

HREF6

http://uob-community.ballarat.edu.au/~javery/dowl/dowl.html

Copyright