Duality Parallelization And Branch-and-bound For Ontology Diagnoses

Ontology,as a means of expressing semantic information in the Semantic Web,has always been the core of related theories and technologies of the Semantic Web.As more and more ontologies are available on the Semantic Web and the description of the ontology becomes more and more complex,it becomes very difficult to construct an ontology without errors.An important cause of ontology errors is the existence of unsatisfiable concepts in the ontology,which will lead to the incoherency of the ontology.Ontology diagnosis is an important way to solve the problem of ontology incoherency.Ontology diagnosis plays a key role in ensuring the quality of ontology,so it is of great significance to diagnose incoherent ontology.Usually,there are many diagnoses for an incoherent ontology,minimal diagnosis and cardinality-minimal diagnosis are two types of diagnosis with smaller number of problem axioms.Existing methods of computing ontology diagnoses are by expanding a hitting set tree(HST)to compute diagnoses,but they usually have a large time complexity.In order to solve the above problems,this paper designs two methods that can compute not only all minimal diagnoses but also a cardinality-minimal diagnosis for ontology diagnoses.They are parallel ontology diagnosis method based on duality and ontology diagnosis method based on branch-and-bound.The parallelization duality method is an ontology diagnosis method that implemented by exploring the hitting set duality between minimal incoherencypreserving sub-TBoxes(MIPS)and minimal diagnosis.The duality means that a minimal hitting set of all MIPSes is a minimal diagnosis,and a minimal hitting set of all minimal diagnoses is a MIPS.The dual method mainly uses the hitting set duality to make the two processes of duality provide useful information to each other.Since the two processes are independent of each other,and the application of parallelization technology has become more and more popular,The duality method by adding parallelization technology can be used to improve the efficiency of ontology diagnoses.The ontology diagnosis method based on branch-and-bound uses the concept of disjoint MIPS cover to define a lower bound for diagnoses,applying this lower bound we can verify whether a candidate cardinality-minimal diagnosis is indeed a cardinality-minimal diagnosis.Disjoint MIPS cover is a set of multiple disjoint MIPSes.The complement of the union of these MIPSes is coherent,so the union of MIPSes contains at least one diagnosis.Because the disjoint MIPS cover can only explore the minimal diagnoses space contained in the union of disjoint MIPS cover,in order to ensure the correctness of the algorithm,the remaining minimal diagnoses space is explored by using branch technology.The branch technology constructs each branch by removing every minimal hitting set of all minimal diagnoses in the union of disjoint MIPS cover,thereby all the minimal diagnoses space is explored,so the algorithm can also be used to calculate all minimal diagnoses.In order to verify the effectiveness of methods in this paper,this paper has experiments to count the number of minimal diagnoses in a specified time and time for calculating a cardinality-minimal diagnosis.The experimental results show that the duality-based parallelization method and branch-and-bound algorithm proposed in this paper has a good effect on ontology diagnoses.Among them,the parallelization method based on duality has a significant effect on computing all the minimal diagnoses,and can return a larger number of minimal diagnoses in a shorter time.The branch-and-bound method has a good experimental effect for calculating a cardinality-minimal diagnosis,it can return a cardinality-minimal diagnosis in a shorter time.