Reasoning and querying web-scale open data based on DL-Lite(A) in a divide-and-conquer way

doi:10.1016/j.websem.2019.01.003

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 数学所

	Reasoning and querying web-scale open data based on DL-Lite(A) in a divide-and-conquer way
	Gu, Zhenzhen 2; Zhang, Songmao1 ; Cao, Cungen 2
刊名	JOURNAL OF WEB SEMANTICS
	2019-03-01
卷号	55 页码:122-144
关键词	DL-lite(A) Open data Semantic web Knowledge base Query answering Divide-and-conquer
ISSN号	1570-8268
DOI	10.1016/j.websem.2019.01.003
英文摘要	We propose to use DL-Lite(A) techniques to reason and query the Web-scale Open Data (knowledge bases) described by Semantic Web standards like RDF and OWL due to the low reasoning complexity and suitable expressivity of the language. When facing the real-life scalability challenge, the actual reasoning and query answering may become infeasible by the following two factors. Firstly, for both satisfiability checking and conjunctive query answering, a polynomial size of queries may need to be answered over the data layers of the corresponding knowledge bases (KBs) w.r.t. the size of the schema knowledge of these KBs. Secondly, for KBs with massive individual assertions, evaluating a single query over the data layers may be highly time-consuming. This impels us to seek for a divide-and-conquer reasoning and query answering approach for DL-Lite(A), with the basic idea of partitioning both KBs and queries into smaller chunks and decomposing the original reasoning and query answering tasks into a group of independent sub-tasks such that the overall performance can be improved by taking advantage of parallelization and distribution techniques. The challenge for designing such an approach lies in how to carry out partitioning and reasoning reduction in a sound and complete way. Motivated by hash partitioning of RDF graphs, we expect the smaller KB chunks to have the local feature for both satisfiability checking and simple-query answering. Here simple-queries are the conjunctive queries whose query atoms share a common variable or individual. For query answering, we expect to partition a query into smaller simple-queries and evaluate them over smaller KB chunks. Under these expectations, our divide-and-conquer approach is constructed from both theoretical and practical perspectives. Theoretically, definitions of KB partitions and query partitions are presented, and the sufficient and necessary conditions are identified to determine whether a KB partition holds the desired features. Practically, based on the theoretical results, the concrete ways of partitioning KBs and queries as well as evaluating query partitions over KB partitions are described. Moreover, a strategy of optimizing the procedure of evaluating query partitions over KB partitions is provided to improve the overall query answering performance. To verify our approach, two Web-scale open datasets, DBpedia and BTC 2012 dataset, have been chosen. The empirical results indicate that the provided approach opens new possibilities for realizing performance-critical applications on the Web with both high expressivity and scalability. (C) 2019 Elsevier B.V. All rights reserved.
资助项目	National Key Research and Development Program of China[2017YFC1700300] ; National Key Research and Development Program of China[2017YFB1002300] ; National Key Research and Development Program of China[2016YFB1000902] ; Natural Science Foundation of China[61232015] ; Natural Science Foundation of China[61621003]
WOS研究方向	Computer Science
语种	英语
出版者	ELSEVIER SCIENCE BV
WOS记录号	WOS:000462166300009
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/34268]
专题	数学所
通讯作者	Gu, Zhenzhen
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Gu, Zhenzhen,Zhang, Songmao,Cao, Cungen. Reasoning and querying web-scale open data based on DL-Lite(A) in a divide-and-conquer way[J]. JOURNAL OF WEB SEMANTICS,2019,55:122-144.
APA	Gu, Zhenzhen,Zhang, Songmao,&Cao, Cungen.(2019).Reasoning and querying web-scale open data based on DL-Lite(A) in a divide-and-conquer way.JOURNAL OF WEB SEMANTICS,55,122-144.
MLA	Gu, Zhenzhen,et al."Reasoning and querying web-scale open data based on DL-Lite(A) in a divide-and-conquer way".JOURNAL OF WEB SEMANTICS 55(2019):122-144.