Research On Logical Difference Of Ontologies

The logical difference problem of ontologies, one of emerging new problems and closely related with other reasoning problems, came into being in the development of reasoning in ontologies. At the beginning of ontology application, researchers focused on developing reasoning programs for ALC or more complex description logics. It is the highly efficient reasoning programs for description logics in 1990s that sped up the widespread application of description logics and ontologies. Reasoning tasks include checking satisfiability of concept desriptions, checking consistency of ontologies, checking whether an entailment is entailed by an ontology, and answering queries. In 2000s, new reasoning tasks were put forward in applications. If an ontology is inconsistent, how can one find the causes of the inconsistency? Or, given an unwanted entailment entailed by an ontology, how can one find the part of the ontology, which entails the entailment, and modify the ontology according to that information? This kind of diagnosis problems is called non-standard reasoning tasks in ontologies. Many generic or specific diagnosing methods have been developed.Then the following scenario comes. Given an unwanted entailment entailed by an ontology, diagnosing methods return its causes. By destroying these causes, the unwanted entailment will not be valid any more. However, the difference between entailments entailed by the original ontology and the modified one is usually more than that unwanted entailment. Thus, to describe that difference is the problem explored by the logical difference of ontologies.In application and reasoning of ontologies, there is another topic related with the logical difference of ontologies. Ontology reuse is required in applications. Usually, users only want to reuse part of, instead of the whole of, an ontology. For safety concern, ontology administrators also want to provide to user the part he needs, instead of the whole ontology. How to extract partial ontology is the topic of ontology modularity. To assure correctness, the partial ontology extracted should convey the same knowledge in a given domain with the original ontology. That is, the logical difference between the extracted ontology and the original ontology should be empty. Researchers developed methods to extract ontology module via the logical difference of ontologies.This thesis carries research on the logical difference of ontologies around the following aspects.(1) Stratify the concept inclusion logical difference of EL terminologies. Based on a modified uniform interpolantion algorithm, we put forward concept difference, most general subconcept. With the help of these concepts, we present algorithms to stratify the logical difference. Through this method, we can distinguish which part of the logical difference is primitive, and which part is generated by entailments propogation. Thus, this method can show the dependency between entailments in the logical difference. We also explain how to apply these results to belief revision, using the results to guide the choice of candidate repair solutions.(2) The logical difference of fuzzy EL terminologies. We define the logical difference of fuzzy EL terminologies, and present some rules to decide the change of entailments without recomputing. We classify the contents of the logical difference, and provide different solutions to different situations. Case 1: when users care about the difference in taxonomy, ontology modularity is employed in preprocessing. Case 2: when the only change to the fuzzy EL terminology is change of fuzziness of one of its axioms, for a given entailment, without computing its new fuzziness from scratch in the modified ontology, we provide rules to decide whether the fuzziness will be changed or not, and its range if changed. Case 3: when users are interested at more information of the logical difference, we describe the logical difference by computing its cut sets.(3) Analyze different types of logical difference. In EL terminologies, we try to use instance logical difference to represent concept inclusion difference. In DL_Lite_bool, we try to get succinct representation of query logical difference with help of concept inclusion difference. We put forward new uniform interpolation algorithm, whose results are easy to understand. For three types of logical differences in DL_Lite_horn, we all discuss describing the logical difference through uniform interpolation.Future work will be carried out around theoretical and implementation aspects.In aspect of implementation we will try heuristics to get a system with scalability and reusability. More concretely, in the stratifying algorithm of EL terminologies, there is more space for improvement, like operations on propositional formula. We will implement controlling of ontology access, and analyze its efficiency when dealing with large scale ontologies. In DL_Lite description logics, we will explore how to solve problems efficiently with the help of OBDD routines.In theoretical aspect, we will continue to explore the connection between different types of difference, and their succinct representation. With the new query uniform interpolation of DL_Lite_bool, we will try to find a method to compute the query type of logical difference, and discuss applying the new method to extract modules. For DLs in DL_Lite family, explore the corresponding logical difference and try to clarify the logical characteristics (such as connectors, decidability) which affect properties of the logical difference. We will investigate how to show the dependency between entailments in the logical difference between DL_Lite ontologies.