Reasoning with Multi-Version Ontologies A Temporal Logic Approach

发布时间:2021-11-29 06:02:05

Reasoning with Multi-Version Ontologies: a Temporal Logic Approach
Zhisheng Huang and Heiner Stuckenschmidt
AI Department, Vrije Universiteit Amsterdam, The Netherlands {huang, heiner}@cs.vu.nl

Abstract. In this paper we propose a framework for reasoning with multi-version ontology, in which a temporal logic is developed to serve as its semantic foundation. We show that the temporal logic approach can provide a solid semantic foundation which can support various requirements on multi-version ontology reasoning. We have implemented the prototype of MORE (Multi-version Ontology REasoner), which is based on the proposed framework. We have tested MORE with several realistic ontologies. In this paper, we also discuss the implementation issues and report the experiments with MORE.

1

Introduction

When an ontology is changed, the ontology developers may want to keep the older versions of the ontology. Although maintaining multi-version ontologies increases the resource cost, it is still very useful because of the following bene?ts: – Change Recovery. For ontology developers, the latest version of an ontology is usually less stable than the previous ones, because the new changes have been introduced on it, and those changes and their consequences have not yet been fully recognized and evaluated. Maintaining the previous versions of the ontology would allow the possibilities for the developers to withdraw or adjust the changes to avoid unintended impacts. – Compatibility Ontology users may still want to use an earlier version of the ontology despite the new changes, because they may consider the functionalities of the earlier version of the ontology are su?cient for their needs. Furthermore, multi-version ontologies may have di?erent resource requirement. Ontology users may prefer an earlier version with less resource requirement to a newer version with higher resource requirement. The list above is not complete. We are going to discuss more bene?ts in the next section. Those bene?ts can justify to some extend that multi-version ontology management and reasoning systems are really useful. The change recovery requires the system should provide a facility to evaluate the consequences
0

The work reported in this paper was partially supported by the EU-funded SEKT project (IST-506826).

2

Zhisheng Huang et al.

raising from ontology changes and a tool to compare multi-versions of the ontology. Selecting a compatible version needs the system which can support a query language for reasoning on a selected version of the ontology. This requires a query language which can express the temporal aspects of the ontology changes. Intuitively multiple versions of an ontology can be considered as a temporal sequence of change actions on an ontology. That serves as our departure point in this paper. In this paper we will investigate how temporal logics serve as the semantic foundation of multi-version ontology reasoning. We propose a framework of reasoning with multi-version ontologies which is based on a temporal logic approach. We will show that the temporal logic can provide a solid semantic foundation which serve as an extended query language to detect the ontology changes and their consequences.We have implemented the prototype of MORE (Multi-version Ontology REasoner), which extends existing systems for querying Description Logic Ontologies with temporal operators that support the maintenance of multiple versions of the same ontology. We discuss the implementation of the MORE more prototype and report the preliminary experiences with applying MORE to realistic ontologies. This paper is organized as follows: Section 2 provides a brief survey on the ontology evolution and versioning. Section 3 discusses the problem of multiversion ontology reasoning. Section 4 presents a temporal logic for reasoning with multi-version ontologies. Section 5 shows how the proposed temporal logic can serve as a query language for reasoning with multi-version ontologies. Section 6 discusses the implementation issues of MORE and report the experiments with MORE. Section 7 discusses related work, further work, and concludes the paper.

2

Solved and Open Problems in Ontology Evolution

Database schema evolution is an important area related to the problem of ontology evolution. In the following, we summarize some of the basic requirements for schema evolution and versioning that have been stated in connection with the problem of schema evolution for object oriented databases that are most relevant for the problem of ontology evolution. Evolvability The basic requirement in connection with schema evolution is the availability of a suitable apparatus for evolving the schema in terms of change operations and a structure for representing changes. Integrity An important aspect of schema evolution is to preserve the integrity of the database during change. Syntactic con?icts may occur for example due to multiply de?ned attribute names in the same class de?nition. Further, semantic con?icts can appear if changes to the schema break up referential integrity or if the modi?cation of an integrity constraints makes it in compatible with another one. Compatibility The literature mentions two aspects of compatibility: downward compatibility means that systems that were based on the old version of the

Lecture Notes in Computer Science

3

schema can still use the database after the evolution. Upward compatibility means that system that are built on top of the new schema can still access the old data. In principle, the issues discussed above are also relevant for the problem of ontology evolution. In the following, we summarize recent work that addressed the di?erent aspects mentioned above for the special case of ontologies. Evolvability The evolvability of ontologies has been addressed by di?erent researchers by de?ning change operations and change representations for ontology languages. Change operations have been proposed for speci?c ontology languages. In particular change operations have been de?ned for OKBC, OWL (Klein 2004) and for the KAON ontology language (Stojanovic et al 2002). All approaches distinguish between atom and complex changes. Different ways of representing ontological changes have been proposed: besides the obvious representation as a change log that contains a sequence of operations, authors have proposed to represent changes in terms of mappings between two versions of the same ontology (Noy and Musen 2003). Integrity The problem of preserving integrity in the case of changes is also present for ontology evolution. On the one hand the problem is harder here as ontologies are often encoded using a logical language where changes can quickly lead to logical inconsistency that cannot directly be determined by looking at the change operation. On the other hand, there are logical reasoners that can be used to detect inconsistencies both within the ontology and with respect to instance data. As this kind of reasoning is often costly, heuristic approaches for determining inconsistencies have been proposed (Klein 2004, Stuckenschmidt and Klein 2003). While deciding whether an ontology is consistent or not can easily be done using existing technologies, repairing inconsistencies in ontologies is an open problem although there is some preliminary work on diagnosing the reasons for an inconsistency which is prerequisite for a successful repair (Schlobach and Cornet 2003). Compatibility The problem of compatibility with applications that use an ontology has received little attention so far. The problem is that the impact of a change in the ontology on the function of the system is hard to predict and strongly depends on the application that uses the ontology. Part of the problem is the fact that ontologies are often not just used as a ?xed structure but as the basis for deductive reasoning. The functionality of the system often depends on the result of this deduction process and unwanted behavior can occur as a result of changes in the ontology. Some attempts have been made to characterize change and evolution multiple versions on a semantic level (He?in and Hendler 2000, He?in and Pan 2004). This work provides the basis for analyzing compatibility which currently is an open problem. We conclude that at the current state of research the problem of de?ning the basic apparatus for performing ontology evolution in terms of change operations and representation of changes is understood. Open questions with respect to

4

Zhisheng Huang et al.

ontology evolution mainly concern the problem of dealing with integrity problems and with ensuring compatibility of the ontology with existing applications. The basic problem that has to address in the context of both of these topic lies in the logical nature of many ontology speci?cations. We therefore need methods that work a the semantic level and are aware of logical implications caused by changes. The formal characterization of ontology evolution provided by He?in is a step in the right direction, but it does not provide any concrete methods for supporting evolution that are necessary to resolve existing problems with respect to dealing with inconsistency or determining compatibility.

3

Multi-Version Reasoning: An Open Problem

As mentioned above, versioning is the key to compatibility as it enables each application to use a version of the ontology that best ?ts its requirements. Our work therefore focuses on supporting the management of di?erent versions of the same ontology on a semantic level. In particular, we want to provide functionality for answering queries about knowledge derivable from di?erent versions. The corresponding approach has to provide two kinds of functionalities: – Ask questions about statements derivable from certain versions. – Ask for versions that allow to derive certain statements While the ?rst kind of functionality can be used to inspect a given version of the ontology in order to ?nd out whether important statements can or cannot be derived from it, the second kinds of functionality helps to ?nd a version that is compatible with a given application because important statements can be derived from it. Another issues is the scope of the approach, in particular the space of versions to be considered. There are several possible scenarios. In most relevant cases, we are concerned with a history of di?erent versions of the same ontology where each version replaces the previous one. We call this the retrospective approach as a result, we have a sequence of versions. Typical questions in this setting are: Invariant Facts: Are the facts from the old version still derivable? Obsolete Facts: What facts are not derivable any more? New Facts: Are the facts are newly derivable from the new version? Version Retrieval: What is the last version that can be used to derive certain facts? There are also scenarios, in which di?erent versions of the ontology co-evolve. This is mostly the case in scenarios where the development of the ontology is not controlled by an authority. In the following, we ignore this scenario which is less relevant for professional ontology development. The other question is whether future versions are considered to be part of the space of versions. Such future versions can be characterized in terms of changes to an existing version.

Lecture Notes in Computer Science

5

As mentioned above, di?erent proposals for change representations exist that could be used for this purpose. We call this the prospective approach. Typical questions here are: – Will this change make it possible to derive a certain fact? – Will this change disable the derivation of a certain fact that was derivable before? We believe that including future versions in the scope of the management approach has many bene?ts as it allows us to answer ’what if’ questions that help the ontology engineer to better plan new versions. In this paper, however, we limit our attention to the retrospective approach. The development of our method is based on the assumption that di?erent versions of an ontology are managed on a central server. In a commercial setting, ontologies are normally created and maintained on a development server. Stable versions of the ontology are moved to a production server publishes the corresponding models and therefore plays the role of the central server. Further Compatangelo et al (2004) propose a blackboard architecture that also allows the centralized management of di?erent ontology versions in distributed environments that makes our approach applicable also in the distributed setting. Based on this general assumption, there are a number of quite relevant application scenarios for the version management technology sketched above.

4

A Temporal Logic for Multi-version Ontology Reasoning

Temporal logics can be classi?ed as two main classes with respect to two di?erent time models: linear time model and branching time model. The linear time logics which express properties over a single sequence of states. This view is suitable for the retrospective approach to multi-ontology reasoning where we assume a sequence of versions. Branching time logics are express properties across di?erent sequences of states. This feature would be needed for the prospective approach where we consider di?erent possible sequences of changes in the future. The linear temporal logic LTL is a typical temporal logic for modeling linear time, whereas the computation tree logic CTL is a typical one for modeling branching time (Rescher 1971, van Benthem 1995, Clarke et al. 1999). Temporal logics are often future-oriented, because their operators are designed to be ones which involve the future states. Typical operators are: the operator Future φ which states that ’φ holds sometimes in the future with respect to the current state’, and the operator Alwaysf φ which states that ’φ always holds in the future with respect to the current state’, and the operator φ Until ψ which states that ’φ always holds in the future until ψ holds’. For a discrete time

6

Zhisheng Huang et al.

model, the operator Next φ is introduced to state that φ holds at the next state with respect to the current state. For the retrospective reasoning, we only need a temporal logic that only talks about the past. Namely, it is one which can be used to compare the current state with some previous states in the past. It is natural to design the following past-oriented operators, which correspond with the counterparts of the future oriented temporal operators respectively: – the previous operator states that a fact φ holds just one state before the current state the current state. – the the sometimes-in-the past operator states that a fact φ holds sometimes in the past with respect to the current state. – the always-in-the-past operator states that φ holds always in the past with respect to the current state. In this paper, we use a linear temporal logic, denoted as LTLm, which actually is a restricted linear temporal logic LTL to past-oriented temporal operators. 4.1 Version Spaces and Temporal Models

In the following, we will de?ne the formal semantics for the temporal operators by introducing an entailment relation between a semantic model (i.e., multi-version ontologies) and a temporal formula. We consider a version of an ontology to be a state in the semantic model. We do not restrict ontology speci?cations to a particular language (although OWL and its description logics are the languages we have in mind). In general, an ontology language can be considered to be a set of formulas that is generated by a set of syntactic rules in a logical language L. We consider multi-versions of an ontology as a sequence of ontologies which are connected each other via change operations. Each of these ontologies has a unique name. This is di?erent from the work in [10], in which an ontology is considered as one which contains the set of other ontologies which are backwards compatible with. We have the following de?nition. De?nition 1 (Version Space). An version space S over an ontology set Os is a set of ontology pairs, namely, S ? Os × Os. We use version spaces as a semantic model for our temporal logic, restricting our investigation to version spaces that present a linear sequence of ontologies: De?nition 2 (Linear Version Space). A linear version space S on an ontology set Os is a version space which is a ?nite sequence of ontologies S = { o1 , o2 , o2 , o3 , · · · , on?1 , on } Alternatively we write the sequence S as follows: S = (o1 , o2 , · · · , on )

Lecture Notes in Computer Science

7

We use S(i) to refer the i th ontology oi in the space. For a version space S = (o1 , o2 , · · · , on ), We call the ?rst ontology S(1) in the space the initial version of the version space, and the last ontology S(n) the latest version of the version space respectively. We introduce an ordering
S

with respect to a version space S as follows:
S

De?nition 3 (Ordering on Version Space). o in the sequence S, i.e., S = (· · · , o, · · · , o , · · · ).

o i? o occurs prior to o

Proposition 1 (Prior version and Linear Ordering). the prior version relation S is a linear ordering, namely, (i) irre?exive, i.e., (o S o), (ii) transitive, i.e., o S o and o S o ? o S o , (iii) asymmetry, i.e., o S o ? o S o, (iv) comparable, i.e., either o S o or o S o, for any ontology o, o , o . 4.2 Syntax and Semantics of LTLm

S

is

The Language L+ for the temporal logic LTLm can be de?ned as an extension to the ontology language L with Boolean operators and the temporal operators as follows 1 : q ∈ L ? q ∈ L+ φ ∈ L+ ? ?φ ∈ L+ φ, ψ ∈ L+ ? φ ∧ ψ ∈ L+ φ ∈ L+ ? PreviousVersion φ ∈ L+ φ ∈ L+ ? AllPriorVersions φ ∈ L+ Where the negation ? and the conjunction ∧ must be new symbols that do not appear in the language L to avoid the ambiguities. De?ne the disjunction ∨, the implication →, and the bi-conditional ? in terms of the conjunction and the negation as usual. De?ne ⊥ as a contradictory φ ∧ ?φ and as a tautology φ ∨ ?φ respectively. Using these basic operators, we can de?ne some addition operators useful for reasoning about multiple versions. We de?ne the SomePriorVersion operator in terms of the AllPriorVersions operator as SomePriorVersionφ =df ?AllPriorVersions ?φ The always-in-the-past AllPriorVersions operator is one which does not consider the current state. We can de?ne a strong always-in-the-past AllVersions
1

Note that the logic also contains a Since operator which makes it a complete temporal logic. As there is not direct use of this operator for managing multiple versions, we omit it from the discussion

8

Zhisheng Huang et al.

operator as AllVersionsφ =df φ ∧ AllPriorVersions φ, which states that ’φ always holds in the past including the current state’. Let S be a version space on an ontology set Os, and o be an ontology in the set Os, we extend the entailment relation for the extended language L+ as follows: S, o |= q S, o |= ?φ S, o |= φ ∧ ψ S, o |= PreviousVersion φ S, o |= AllPriorVersions φ i? i? i? i? i? o |= q, f or q ∈ L. S, o |= φ. S, o |= φ, ψ. o , o ∈ S such that S, o |= φ. for any o such that o S o, S, o |= φ.

For a linear version space S, we are in particular interested in the entailment relation with respect to its latest version of the ontology S(n) in the version space S. We use S |= φ to denote that S, S(n) |= φ. Model checking has been proved to be an e?cient approach for the evaluation of temporal logic formulas (Clarke et al. 1999). In the implementation of MORE, we are going to use the standard model checking algorithm for evaluation a query in the temporal logic LTLm. Therefore, we do not need a complete axiomatization for the logic LTLm in this paper.

5

LTLm as a Query Language

There are two types of queries: reasoning queries and retrieval queries. The former concerns with an answer either ’yes’ or ’no’, and the latter concerns an answer with a particular value, like a set of individuals which satisfy the query formula. Namely, the evaluation of a a reasoning query is a decision problem, whereas the evaluation of a retrieval query is a search problem. In this section, we are going to discuss how we can use the proposed temporal logic to support both reasoning queries and retrieval queries. 5.1 Reasoning queries

Using the LTLm logic we can formulate reasoning queries over a sequence of ontologies that correspond to the typical questions mentioned in Section3. Are all facts still derivable? This question can be answered for individual facts using reasoning queries. In particular, we can use the query φ ∧ PreviousVersion φ to determine for facts φ derivable from the previous version whether they still hold in the current version. the same can be done for older versions by chaining the PreviousVersion operator or by using the operator AllVersions to ask whether formulas was always true in past versions and is still true in the current one (AllVersions φ).

Lecture Notes in Computer Science

9

What facts are not derivable any more? In a similar way, we can ask whether certain facts are not true in the new version any more. This is of particular use for making sure that unwanted consequences have been excluded in the new version. The corresponding query is ?φ ∧ PreviousVersion φ. Using the AllPriorVersions operator, we can also ask whether a fact that was always true in previous versions is not true anymore. Are the facts are newly derivable from the new version? Reasoning queries can also be used to determine whether a fact is new in the current version. As this is true if it is not true in the previous version, we can use the following query for checking this φ ∧ ?PreviousVersion φ. We can also check whether a new fact never holded in previous versions using the following query φ ∧ ?SomePriorVersion φ. What is the last version that can be used to derive certain facts? Using reasoning queries we can check whether a fact holds in a particular version. As versions are arranged in a linear order, we can move to a particular version using the PreviousVersion operator. the query PreviousVersion PreviousVersion φ for instance checks whether φ was true in the version before the previous one. A drawback of reasoning queries lies in the fact, that they can only check a property for a certain speci?c fact. When managing a di?erent versions of a large ontology, the user will often not be interested in a particular fact, but ask about changes in general. This speci?c functionality is provided by retrieval queries. 5.2 Retrieval Queries

Many Description Logic Reasoners support so-called retrieval queries that return a set of concept names that satisfy a certain condition. For example, a children concept c of a concept c, written child(c, c ), is de?ned as one which is subsumed by the concept c, and there exists no other concepts between them. Namely, child(c, c ) =df c c∧ ?c (c c ∧c c ∧ c = c ∧ c = c ).

Thus, the set of new/obsolete/invariant children concepts of a concept on an ontology o in the version space S is de?ned as follows newChildren(S, o, c) =df {c |S, o |= child(c, c )∧?PreviousVersion child(c, c )}. obsoleteChildren(S, o, c) =df {c |S, o |= ?child(c, c )∧PreviousVersion child(c, c )}. invariantChildren(S, o, c) =df {c |S, o |= child(c, c )∧PreviousVersion child(c, c )}. The same de?nitions can be extended into the cases like parent concepts, ancestor concepts, descendant concept and equivalent concepts. Those query supports are su?cient to evaluate the consequences of the ontology changes and the di?erences among multi-version ontologies. We will discuss more details in the section about the tests on MORE.

10

Zhisheng Huang et al.

5.3

Making version-numbers explicitly

Temporal logics allow us to talk about the temporal aspects without reference to a particular time point. For reasoning with multi-version ontologies, we can also talk about the temporal aspects without mentioning a particular version name. We know that each state in the temporal logic actually corresponds with a version of the ontology. It is not di?cult to translate the temporal statements into a statement which refers to an explicit version number. Here are two approaches for it: relative version numbering and absolute version numbering. Relative version numbering The proposed temporal logic is designed to be one for past-oriented. Therefore, it is quite natural to design a version numbering which is relative to the current ontology in the version space. We use the formula Version0 φ to denote that the property holds in the current version. Namely, we refer to the current version as the version 0 in the version space, and other states are used to refer to a version relative to the current version, written as Version?i as follows: Version0 φ =df φ. Version(?i) φ =df PreviousVersion(Version(1?i) φ). The formula Version?i φ can be read as ’the property φ holds in the previous i-th version’. Absolute version numbering Given a version space S with n ontologies on it, i.e., |S| = n + 1. For the latest version o = S(n), it is well reasonable to call the i-th ontology S(i) in the version space the version i of S, denoted as Versioni,S . Namely, we can use the formula Versioni,S φ to denote that the property φ holds in the version i in the version space S. Thus, we can de?ne the absolute version statement in terms of a relative version statement as follows: Version(i,S) φ =df Version(n?i) φ. Explicit version numbering provides the basis for more concrete retrieval queries. In particular, we now have the opportunity to compare the children of a concept c in two speci?c ontologies i and j in the version space S. The corresponding de?nitions are the following: newChildren(S, c)i,j =df {c |S |= Version(i,S) child(c, c )∧?Version(j,S) child(c, c )}. obsoleteChildren(S, c)i,j =df {c |S |= ?Version(i,S) child(c, c )∧Version(j,S) child(c, c )}. invariantChildren(S, c)i,j =df {c |S |= Version(i,S) child(c, c )∧Version(j,S) child(c, c )}. Again, the same can be done for other predicates like parent-, ancestor or descendant concepts.

Lecture Notes in Computer Science

11

Fig. 1. Architecture of MORE.

6

Implementation of MORE

We implemented a prototypical reasoner for multi-version ontologies called MORE based on the approach described above. The system is implemented as an intelligent interface between an application and state-of-the art description logic reasoners (compare ?gure 1) and provides server-side functionality in terms of an XML-based interface for uploading di?erent versions of an ontology and posing queries to these versions. Requests to the server are analyzed by the main control component that also transforms queries into the underlying temporal logic queries if necessary. The main control element also interacts with the ontology repository and ensures that the reasoning components are provided with the necessary information and coordinates the information ?ow between the reasoning components. The actual reasoning is done by model checking components for testing temporal logic formulas that uses the results of an external description logic reasoner for answering queries about derivable facts in a certain version. The MORE prototype in implemented in Prolog and uses the XDIG interface (Huang and Visser 2004), an extended DIG description logic interface for Prolog2 . MORE is designed to be a simple API for a general reasoner with multi-version ontologies. It supports extended DIG requests from other ontology applications or other ontology and metadata management systems and supports multiple ontology languages, including OWL and DIG (Bechhofer et al. 2003)3 . This means that MORE can be used as an interface to any description logic reasoner as it supports the functionality of the underlying reasoner by just passing requests on and provides reasoning functionalities across versions if needed. Therefore, the implementation of MORE will be independent of those particular
2 3

http://wasp.cs.vu.nl/sekt/dig http://dl.kr.org/dig/

12

Zhisheng Huang et al.

applications or systems. A prototype of MORE is available for download at the website: http://wasp.cs.vu.nl/sekt/more. 6.1 Experiments with MORE

We have tested the current implementation of the MORE system on di?erent versions of real life ontologies from di?erent domains. In the following, we brie?y report experiments we performed on detecting changes in the concept hierarchy of the following two ontologies. The OJKL Ontology The OJKL Ontology (Ontology of the Juridical Legal Knowledge) is a legal Ontology that has been developed in the SEKT project4 to support the content-based retrieval of legal documents (Casanovas et al. 2005). We used ?ve di?erent versions of the ontology from di?erent stages of the development process. Each of these version contains about 80 concepts and 60 relations. The BiosSAIL Ontology The BioSAIL Ontology which was developed within the BioSTORM project5 . It has been used in earlier experiments on change management reported in (Klein 2004). the complete data set consists of almost 20 di?erent versions of the ontology. We take three versions of the BioSAIL ontology for the tests reported below. Each version of BioSAIL ontology has about 180 classes and around 70 properties. Those two ontologies have been tested with di?erent temporal reasoning queries. We concentrated on retrieval queries about the structure of the concept hierarchy. In particular, we used retrieval queries with explicit version numbering as introduced in section 5.3. Below we show the results for the queries about the new and obsolete child, parent, ancestor, and descendant relations in the concept hierarchy. It has to be noted that the result are not the result of a syntactic analysis of the concept hierarchy, but rely on description logic reasoning. This means that we also detect cases where changes in the de?nition of a concept lead to new concept relations that are only implicit in the Ontology. The results of these queries can be found at http://wasp.cs.vu.nl/sekt/more/test/. Further, arbitrary temporal queries using the operators introduced in this paper can be formulated and executed. the only limitation is the interface to the underlying DL reasoner, that currently is only implemented for queries about the concept hierarchy. This can easily be extended to any functionality provided by the RACER system (Haarslev and M¨ller 2001). A list of the template queries for temporal reasoning o queries are available at the MORE testbed, which can be download from the MORE website. The average time cost for each temporal reasoning query is
4 5

http://www.sekt-project.com/ http://smi-web.stanford.edu/projects/biostorm/

Lecture Notes in Computer Science Results for the BioSAIL Ontology Version(from) Version(to) NC OC NP OP NA OA ND OD Total BioSAILv16 BioSAILv20 136 10 123 49 228 104 227 32 909 BioSAILv20 BioSAILv21 54 1 42 21 193 32 192 1 536 Results for the OJKL Ontology Version(to) NC OC NP OP NA OA ontoRDF2 82 25 53 10 141 16 ontoRDF3 82 17 49 13 144 17 oblk 49 43 36 20 70 20 objk 4 7 2 1 8 6

13

Version(from) ontoRDF ontoRDF2 ontoRDF3 oblk

ND 141 144 54 8

OD 74 21 85 18

Total 542 487 377 54

NC = New Children concept relation, OC = Obsolete Children concept relation, NP = New Parent concept relation, OP = Obsolete Parent concept relation, NA = New Ancestor concept relation, OA = Obsolete Ancestor concept relation, ND = New Descendant concept relation, and OD = Obsolete Descendant concept relation. Fig. 2. MORE Tests on Concept Relations

about 7 seconds for the OJKL Ontology and 3 seconds for the BioSAIL ontology on a PC with 2Ghz CPU 512 MB memory under Windows 2000.

7

Discussion and Conclusions

In this paper, we discussed the integrated management of multiple versions of the same ontology as an open problem with respect to ontology change management. We proposed an approach for multi-version management that is based on the idea of using temporal logic for reasoning about commonalities and di?erences between di?erent versions. For this purpose, we de?ne the logic LTLm that consists of operators for reasoning about derivable statements in di?erent versions. We show that the logic can be used to formulate typical reasoning and retrieval queries that occur in the context of managing multiple versions. We have implemented a prototypical implementation of the logic in terms of a reasoning infrastructure for ontology-based systems and successfully tested it on real ontologies. Di?erent from most previous work on ontology evolution and change management our approach is completely based on the formal semantics of the ontologies under consideration. This means that our approach is able to detect all implications of a syntactic change. In previous work, this could only be done partially in terms of ontologies if changes and heuristics that were able to predict some, but not all consequences of a change. Other than previous work on changes at the semantic level which were purely theoretical, we have shown that out approach can be implemented on top of existing reasoners and is able to provide answers in a reasonable amount of time. In order to be able to handle large ontologies with thousands of concepts, we have to think about

14

Zhisheng Huang et al.

optimization strategies. Existing work on model checking has shown that these methods scale up to very large problem sets if optimized in the right way. This makes us optimistic about the issue of scalability. One of the reasons for the e?ciency of the approach is the restriction to the retrospective approach, that only considers past versions. This restriction makes linear time logics su?cient for our purposes. A major challenge is the extension of our approach with the prospective approach that would allow us to reason about future versions of ontologies. This direction of work is challenging, because it requires a careful analysis of a minimal set of change operators and their consequences. There are proposals for sets of change operators, but these operators have never been analyzed form the perspective of dynamic temporal logic. The other problem is that taking the prospective approach means moving from linear to branching time logic which has a serious impact on complexity and scalability of the approach.

References
1. Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, Peter PatelSchneider, (eds.), The Description Logic Handbook Theory, Implementation and Applications, Cambridge University Press, Cambridge, UK, 2003. 2. van Benthem, J., Temporal Logic, in: D. M. Gabbay, C. J. Hogger, and J. A. Robinson, Handbook of Logic in Arti?cial Intelligence and Logic Programming, Volume 4, Oxford, Clarendon Press, 241-350, 1995. 3. Sean Bechhofer, Ralf M¨ller, and Peter Crowther. The DIG Description Logic o Interface. In DL2003 International Workshop on Description Logics, Rome, September 2003. 4. Casanovas, Pompeu; Poblet, Marta; Casellas, Nuria; Contreras, Jess; Benjamins, V.Richard; Blzquez, Mercedes., Supporting newly-appointed judges: A legal knowledge management case study. Journal of Knowledge Management, 2005 (to appear). 5. Edmund M. Clarke and Orna Grumberg and Doron A. Peled, Model Checking, The MIT Press, Cambridge, Massachusetts, 1999. 6. Compatangelo, E., Vasconcelos, W., and Scharlau, B., Managing ontology versions with a distributed blackboard architecture. Proceedings of the 24th Int Conf. of the British Computer Societys Specialist Group on Arti?cial Intelligence (AI2004), Springer-Verlag, 2004. 7. Peter Haase, York Sure, and Denny Vrandecic, Ontology Management and Evolution - Survey, Methods and Prototypes, SEKT Deliverable D3.1.1, 2004. 8. Volker Haarslev, and Ralf M¨ller, Description of the RACER System and its Apo plications, Proceedings of the International Workshop on Description Logics (DL2001), Stanford, USA, 1.-3. August 2001, pp. 132-141. 9. He?in J., Hendler J. Dynamic Ontologies on the Web. Proceedings of AAAI-2000 Conference. AAAI/MIT Press, Menlo Park, CA, 443-449 10. Je? He?in and ZhengXiang Pan, A Model Theorectic Semantics for Ontology Versioning, Proceeding of ISWC, 2004.

Lecture Notes in Computer Science

15

11. Zhisheng Huang and Cees Visser, Extended DIG Description Logic Interface Support for Prolog, SEKT Deliverable D3.4.1.2, 2004. 12. Zhisheng Huang and Heiner Stuckenschmidt, Reasoning with Multiversion Ontologies, SEKT Deliverable D3.5.1, 2005. 13. Klein, M., Fensel, D., Kiryakov, A., and Ognyanov, D. Ontology Versioning and Change Detection on the Web. Proceedings of the 13th International Conference on Knowledge Engineering and Knowledge Management (EKAW02) (Siguenza, Spain), Springer-Verlag, pp. 197–212, 2002. 14. Klein, M., Change Management for Distributed Ontologies. PhD thesis, Vrije Universiteit Amsterdam, 2004. 15. Pieter De Leenheer and Carlo Wouters, Requirements for Versioning Tool, OMWG D6.1, DERI OMWG Working Draft 22 October 2004. 16. Pieter De Leenheer, Revising and Managing Multiple Ontology Versions in a Possible Worlds Setting. Proceedings of the OTM 2004 Workshops, LNCS, 2004. Springer Verlag. http://www.omwg.org/2004/d6/d6.1/ 17. Noy, N. F. and Musen, M. A., The PROMPT suite: Interactive tools for ontology merging and mapping. International Journal of Human- Computer Studies, 59(6):9831024, 2003. 18. Rescher, N. and Urquhart, A., Temporal Logic, Springer-Verlag, 1971. 19. Stuckenschmidt, H., and Klein, M., Integrity and change in modular ontologies, Proceedings of the 18th International Joint Conference on Arti?cial Intelligence, Acapulco, Mexico, 2003.


相关文档

  • Campenhout. Reasoning with temporal logic on truncated paths
  • Situated nonmonotonic temporal reasoning with BABY-SIT
  • Temporal Reasoning with Abductive Logic Programming
  • Diagnosis of Repeated Failures For Discrete Event Systems With Linear-Time Temporal Logic
  • Modularity and Temporal Reasoning a Logic Programming Approach
  • A Tableau Calculus for a Temporal Logic with Temporal Connectives
  • Executable Temporal Logic for Nonmonotonic Reasoning
  • Formal Reasoning about Actor Programs Using Temporal Logic
  • Multi-dimensional modal logic as a framework for spatio-temporal reasoning
  • Localized Temporal Reasoning A State-Based Approach
  • 猜你喜欢

  • 八年级语文下册课件18吆喝 (共19张PPT)
  • 英文版——大话西游剧本。
  • 刍议新闻传播的制约因素与传播策略
  • Android App:获取屏幕旋转角度
  • 天津财经大学国际经济01.第一讲 绪论
  • 打造阳光心态培训课件课件
  • 动感时尚MG动画图文介绍宣传动态ppt模板
  • 汽油发动机起动困难原因分析与探微
  • 新生命的诞生(知识点整理)
  • 英国留学签证面试官常问问题
  • 【精品模板】c038TGp_education_diagram_v2文化教育类PPT模板
  • 公文写作提速的方法
  • 治疗老年人风湿痛的药酒
  • 2019年牛津译林版九年级英语 上册Unit 3 Teenage problems单元测试卷(含答案)
  • 【公文范文】大学生村官年度考核情况报告
  • 微信零钱提现手续费
  • 四川省2016年下半年监理工程师执业资格:工程师的口头指示试题
  • 老人怎样保护心脏
  • 期中考试语文反思作文
  • 【IT专家】为什么我的ajax请求将空对象发送到服务器
  • 汽机实操题集
  • 江西省金溪县第一中学2018_2019学年高二历史12月月考试题(含解析)
  • 益气熄风汤对高血压大鼠AngⅡ和ALD的干预作用
  • 运行Hadoop自带的wordcount单词统计程序
  • 幼儿简笔画:可怕的小恐龙
  • 湖南省益阳市2016-2017学年高一下学期3月月考试题 数学 Word版含答案
  • 云南省2018年保育员三级考试试题试卷及答案
  • (技术合同)设计委托合同书
  • 2011届高考政治第一轮复习课件9
  • 三星s8home键隐藏设置
  • 北师大版 二年级数学上册 《5.6回家路上》 精品PPT课件 (2)
  • 职业培训工作计划通用4篇
  • 初中语文阅读教学提问策略研究
  • 广州市声皇音响设备有限公司(企业信用报告)- 天眼查
  • 江苏省扬州市高邮市车逻镇九年级数学上册第1章一元二
  • 最新-市人大机关扶贫工作计划 精品
  • 05第五章 内燃机混合气的形成与燃烧partI
  • 2017_2018学年高中地理第三章防灾与减灾第一节自然灾害的监测与防御课件新人教版选修5
  • 【精品】最新组织变革中的HR战略
  • [小初高学*]XX六年级数学下册总复*第六单元集体备课上课学*上课学*教案
  • 2020年大学学生会各部门工作计划【精品】
  • 2014年1-6月青海省及全国农用氮、磷、钾化学肥料总计(折纯)月度产量
  • 电脑版