An Ontology Evolution Method For Reducing Cost Of Evolution

Since Tim Berners Lee,current W3C chairman, first proposed the Semantic Web,it is becoming the hot topic of computer information processing area. Ontologies are set to play a key role in the "Semantic Web", as they provide a reusable piece of knowledge about a specific domain. However, those pieces of knowledge are not static,but evolve over time. Domain changes , adaptations to different tasks , or changes in the conceptualization require modifications of ontology. As ontology development becomes a more ubiquitous and collaborative process, evolution becomes an important area of ontology research.Ontology evolution is apt to impact on ontology self and dependant applications However, different realizing methods for the same change requirements may result in very big different impact. Today, researches of ontology evolution mainly focus on how to satisfy the change requirements and maintain the consistency of an evolving ontology. Unfortunately, few of them care about how to reduce cost of ontology evolution, at the same time, there is no standard to assess the methods, so the result usually is not the best, which bring great burden to ontology management and maintenance. For these reasons, this paper proposes a methodology which could simplify the evolution procedure.Here're the steps of this ontology evolution methodology:propose the concept of additional atomy-change, which is the basic evolution operation of the minimum particle size; give the complete group of additional atomy-change and prove it; introduce the concept of cost of evolution, classify it according to the different influences that entity puts on Ontology, and derive the formula for calculating cost of evolution by doing quantitative analysis on the influence. For reducing the cost of evolution in ontology evolution, develop a group of evolution operation strategies to adapt the complicate environment for ontology evolution. Finally, propose the COST algorithm that can reduce cost of evolution, and apply heuristic strategy onto the algorithm to reduce the search space and accelerate evolution procedure efficiently.Additional change is the non-human-command evolution operation on respective entity of Ontology for evolution system to come to consistent. This operation can be classified into additional atomy-change and additional composite-change according to the different size of granularity. Additional atomy-change is the basic operation of minimum particle size, and additional composite-change is a group of additional atomy-change in fact. This paper gives the group of additional atomy-change, and proves that the group is complete and smallest. Hence it comes to the important conclusion: any complex additional change can be split into additional atomy-change in this group. This conclusion is not only the prerequisite to do the analysis of the cost of evolution, but also the vital evidence of making evolution operation strategies.Cost of evolution is the total cost that brought by the change of all the additional atomy-change against entity in Ontology evolution-path. In actual Ontology evolution, entity will influence Ontology on both structure level and function level. This paper classifies cost into structural cost and underlying cost according to the different influence on both aspects. Generally, structural cost is definite, and related to the structure of Ontology. Underlying cost is usually given artificially, and changes with the evolution procedure. Meanwhile, this paper gives the specific formula calculating cost of evolution, and simplify this formula for further quantizing cost. Here the number of entities connect with this entity is defined as structural cost, which is the number of lines connecting this node in Ontology. Correspondingly, the structural cost of relation is the number of node connected by this relation. Here we leave relatively big operation space for underlying cost, experts could value underlying cost of entities under their understanding on Ontology evolution, to make Ontology evolution develops towards the direction which the experts hope. We can say, because of the uncertainty of underlying cost, Ontology evolution becomes more flexible, and the test on Ontology becomes more convenient.In evolution procedure, there are many implementations, the cost from different implementations differ significantly. So, evolution operation strategies are proposed to reduce cost in Ontology evolution procedure. Note, experts can add strategies of additional change, which is defined by themselves; also, experts can consider additional atomy-change only when make strategies. The algorithm of evolution will choose the optimal strategy dynamically according to cost, so as to get a evolution-path which pays the minimum evolution cost.In the COST algorithm described in this paper, the question of Ontology evolution is defined as looking for a evolution-path to make Ontology after evolution to satisfy the constraint of consistancy, and minimize accumulated value of evolution cost.What's more, evolution can convert into graph searching process, where the node is Ontology and line is additional change. Here, value of line is the cost brought by entity. This paper also offers a kind of heuristic strategy applied on the algorithm to efficiently reduce potential results and accelorate the procedure of searching this algorith. The main theme of this heuristic strategy is to calculate the cost of paths which have been searched in the procedure of graph searching process. The searching ends when the value is bigger than the minimum value that has been found. During the searching,Ontology is considered as a new alternative solution, when it comes to a consistent situation, and the cost of the paths which has been searched is less than the minimum value that found before.In the actual practice, we designed a simple system of Ontology evolution and accomplished it. This paper gives a general introduction of this experiment system. This experiment system basically accomplished the Ontology evolution based on COST algorithm. The application of cost and evolution operation strategies in system is highlighted, in order to make a better understanding. Cost plays a guiding and controlling roll in evolution procedure; evolution operation strategy plays a positive roll in promoting the efficiency of Ontology evolution and reducing evolution cost.