ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (12): 2715-2724.doi: 10.7544/issn1000-1239.2018.20170766

Previous Articles     Next Articles

Transformation Algorithm and Its Properties for D3L with Heterogeneous Semantic Mapping

Zhao Xiaofei1,2,3, Shi Zhongzhi2, Feng Zhiyong3   

  1. 1(School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387);2(Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190);3(School of Computer Science and Technology, Tianjin University, Tianjin 300072)
  • Online:2018-12-01

Abstract: Bridge rules provide an important mechanism describing semantic mapping and propagating knowledge for D3L (distributed dynamic description logics). The current research focuses on the homogeneous bridge rules which only contain atomic elements. In this paper, the research is extended to the D3L reasoning problem with the heterogeneous bridge rules which contain composite elements in the contained end. The regularity of distributed knowledge base is defined. Through the alternation of the bridge rules and transforming different forms into existing language mechanism, we present a algorithm which can convert the D3L knowledge base with dynamic description logic DSROIQ as local ontology language into a single DSROIQ knowledge base. Then we study the properties of the algorithm. We prove that the algorithm will terminate in polynomial time and the satisfiability of the target knowledge base is equivalent to the satisfiability of the original knowledge base. Thus, we prove that the worst-case time complexity of the centralized reasoning on regular D3L knowledge base with such bridge rules is the same as that on single DSROIQ knowledge base. The method proposed in this paper makes the reasoning for D3L to obtain the same worst-case time complexity as the existing distributed reasoning methods and solves the problem that the latter can not handle heterogeneous composite bridge rules.

Key words: distributed dynamic description logics (D3L), heterogeneous bridge rules, regularity, centralized reasoning, computation complexity

CLC Number: