Query performance evaluation of distributed resource description framework data management systems

doi:10.11772/j.issn.1001-9081.2021020255

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (2): 440-448.DOI: 10.11772/j.issn.1001-9081.2021020255

• Data science and technology • Previous Articles

Query performance evaluation of distributed resource description framework data management systems

Jun FENG, Bingfa WANG, Jiamin LU()

College of Computer and Information，Hohai University，Nanjing Jiangsu 211100，China

Received:2021-02-22 Revised:2021-04-28 Accepted:2021-04-29 Online:2021-05-11 Published:2022-02-10
Contact: Jiamin LU
About author:FENG Jun， born in 1969， Ph. D.， professor. Her research interests include spatio-temporal data management， intelligent data processing， data mining， water conservancy informatization.
WANG Bingfa， born in 1995， M. S. candidate. His research interests include knowledge graph storage management， distributed SPARQL query optimization.
LU Jiamin， born in 1983， Ph. D.， lecturer. His research interests include distributed data processing， knowledge graph， water conservancy informatization.
Supported by:
National Key Research and Development Program of China(2018YFC0407901)

分布式资源描述框架数据管理系统查询性能评价

冯钧, 王秉发, 陆佳民()

河海大学计算机与信息学院，南京 211100

通讯作者: 陆佳民
作者简介:冯钧（1969—），女，江苏武进人，教授，博士，CCF会员，主要研究方向：时空数据管理、智能数据处理、数据挖掘、水利信息化；
王秉发（1995—），男，江西九江人，硕士研究生，CCF会员，主要研究方向：知识图谱存储管理、分布式SPARQL查询优化；
陆佳民（1983—），男，江苏南通人，讲师，博士，CCF会员，主要研究方向：分布式数据处理、知识图谱、水利信息化。
基金资助:
国家重点研发计划项目(2018YFC0407901)

Abstract

Abstract:

With the continuous development of knowledge graph technology， knowledge information management driven by knowledge graph has been widely applied in multiple domains， so the efficiency of distributed Simple Protocol and Resource description framework Query Language （SPARQL） query for knowledge graph is particularly important. Firstly， a detailed investigation on the existing Spark-based and Random Access Memory （RAM）-based distributed RDF systems was conducted. Secondly， query performance evaluation of eight representative systems selected from the above systems was performed， thereby comparing query performance differences between Spark-based and RAM-based systems with different query types， query diameters and datasets. Thirdly， the query performance of Spark-based and RAM-based systems was evaluated by analyzing the experimental results comprehensively. Finally， the future research directions of distributed SPARQL query optimization which oriented vertical application domain were pointed out aiming at problems of the existing distributed SPARQL query， such as poor query scalability， high query join complexity and long query compilation time.

Key words: distributed Resource Description Framework (RDF), Random Access Memory (RAM), Spark, distributed Simple Protocol and RDF Query Language (SPARQL) query, selectivity, query efficiency, query accuracy

摘要：

随着知识图谱技术的不断发展，知识图谱驱动的知识信息管理广泛应用于各个领域，因此面向知识图谱的分布式SPARQL（Simple Protocol and Resource description framework Query Language）的查询效率显得尤为重要。首先针对现有的基于Spark和基于主存（RAM）的分布式资源描述框架（RDF）系统进行详细调研；其次，从上述系统中选出8个具有代表性的系统进行查询性能评估，比较基于Spark和基于RAM的系统在不同查询类型、查询直径、数据集上的查询性能差异；然后，全面分析实验结果，对基于Spark和基于RAM的系统的查询性能进行评价；最后，针对现有系统在分布式SPARQL查询中存在的查询伸缩性差、查询连接复杂度高、查询编译时间长等问题，展望面向垂直应用领域的分布式SPARQL查询优化的未来研究方向。

关键词: 分布式资源描述框架, 主存, Spark, 分布式SPARQL查询, 选择性, 查询效率, 查询准确性

CLC Number:

TP311.133.1

Jun FENG, Bingfa WANG, Jiamin LU. Query performance evaluation of distributed resource description framework data management systems[J]. Journal of Computer Applications, 2022, 42(2): 440-448.

冯钧, 王秉发, 陆佳民. 分布式资源描述框架数据管理系统查询性能评价[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 440-448.

Figures/Tables 10

References 27

1	邹磊，彭鹏.分布式RDF数据管理综述［J］.计算机研究与发展， 2017， 54（6）： 1213-1224. 10.7544/issn1000-1239.2017.20160908
	ZOU L， PENG P. A survey of distributed RDF data management［J］. Journal of Computer Research and Development， 2017， 54（6）： 1213-1224. 10.7544/issn1000-1239.2017.20160908
2	ZOUAGHI I， MESMOUDI A， GALICIA J， et al. Query optimization for large scale clustered RDF data ［C］// Proceedings of the 22nd International Workshop on Design， Optimization， Languages and Analytical Processing of Big Data Co-located with EDBT/ICDT 2020 Joint Conference. Aachen： CEUR-WS.org， 2020： 56-65.
3	SPARQL query language for RDF ［EB/OL］. （2013-03-26）［2021-02-15］. . 10.1002/9780471650126.dob1092
4	BONIFATI A， MARTENS W， TIMM T. An analytical study of large SPARQL query logs［J］. The VLDB Journal， 2020， 29（2/3）： 655-679. 10.1007/s00778-019-00558-9
5	CHAWLA T， SINGH G， PILLI E S. HyPSo： hybrid partitioning for big RDF storage and query processing ［C］// Proceedings of the 2019 ACM India Joint International Conference on Data Science and Management of Data. New York： ACM， 2019： 188-194. 10.1145/3297001.3297025
6	KYU K M， OO A N. Graph-based indexing method for searching in RDF data ［C］// Proceedings of the 2019 International Conference on Advanced Information Technologies. Piscataway： IEEE， 2019： 96-101. 10.1109/aitc.2019.8920921
7	SALEEM M， SZÁRNYAS G， CONRADS F， et al. How representative is a SPARQL benchmark？ an analysis of RDF triplestore benchmarks ［C］// Proceedings of the 2019 World Wide Web Conference. New York： ACM， 2019： 1623-1633. 10.1145/3308558.3313556
8	SCHATZLE A， PRZYJACIEL-ZABLOCKI M， SKILEVIC S， et al. S2RDF： RDF querying with SPARQL on Spark［J］. Proceedings of the VLDB Endowment， 2016， 9（10）： 804-815. 10.14778/2977797.2977806
9	杨程，陆佳民，冯钧.分布式环境下大规模资源描述框架数据划分方法综述［J］.计算机应用， 2020， 40（11）： 3184-3191. 10.1109/bigdata50022.2020.9378227
	YANG C， LU J M， FENG J. Survey of large-scale resource description framework data partitioning methods in distributed environment［J］. Journal of Computer Applications， 2020， 40（11）： 3184-3191. 10.1109/bigdata50022.2020.9378227
10	ABADI D J， MARCUS A， MADDEN S R， et al. Scalable Semantic Web data management using vertical partitioning ［C］// Proceedings of the 33rd International Conference on Very Large Data Bases. New York： ACM， 2007： 411-422.
11	王鑫，邹磊，王朝坤，等.知识图谱数据管理研究综述［J］.软件学报， 2019， 30（7）： 2139-2174. 10.13328/j.cnki.jos.005841
	WANG X， ZOU L， WANG C K， et al. Research on knowledge graph data management： a survey［J］. Journal of Software， 2019， 30（7）： 2139-2174. 10.13328/j.cnki.jos.005841
12	SCHIEVELBEIN G， ARRASCUE AYALA V A， WEI-KLEINER F， et al. Exploiting wide property tables empowered by inverse properties for efficient distributed SPARQL query evaluation ［C］// Proceedings of the ISWC 2019 Satellite Tracks （Posters and Demonstrations， Industry， and Outrageous Ideas） co-located with 18th International Semantic Web Conference. Aachen： CEUR-WS.org， 2019： 81-84.
13	AYALA V A A， KOLEVA P， ALZOGBI A， et al. Relational schemata for distributed SPARQL query processing ［C］// Proceedings of the 2019 International Workshop on Semantic Big Data. New York： ACM， 2019： No.3. 10.1145/3323878.3325804
14	王鑫，徐强，柴乐乐，等.大规模RDF图数据上高效率分布式查询处理［J］.软件学报， 2019， 30（3）： 498-514. 10.13328/j.cnki.jos.005696
	WANG X， XU Q， CHAI L L， et al. Efficient distributed query processing on large scale RDF graph data［J］. Journal of Software， 2019， 30（3）： 498-514. 10.13328/j.cnki.jos.005696
15	GUBICHEV A， NEUMANN T. Exploiting the query structure for efficient join ordering in SPARQL queries ［C］// Proceedings of the 17th International Conference on Extending Database Technology. ［S.l.］： OpenProceedings.org， 2014： 439-450.
16	李国良，周煊赫，孙佶，等.基于机器学习的数据库技术综述［J］.计算机学报， 2020， 43（11）： 2019-2049. 10.11897/SP.J.1016.2020.02019
	LI G L， ZHOU X H， SUN J， et al. A survey of machine learning based database techniques［J］. Chinese Journal of Computers， 2020， 43（11）： 2019-2049. 10.11897/SP.J.1016.2020.02019
17	GRAUX D， JACHIET L， GENEVÈS P， et al. SPARQLGX： efficient distributed evaluation of SPARQL with Apache Spark ［C］// Proceedings of the 2016 International Semantic Web Conference， LNCS9982. Cham： Springer， 2016： 80-87.
18	LI S H， SHEN D R， KOU Y， et al. Query optimization for massive RDF data based on Spark ［C］// Proceedings of the 4th International Conference on Big Data Computing and Communications. Piscataway： IEEE， 2018： 219-224. 10.1109/bigcom.2018.00042
19	COSSU M， FÄRBER M， LAUSEN G. PRoST： distributed execution of SPARQL queries using mixed partitioning strategies ［C］// Proceedings of the 21th International Conference on Extending Database Technology. ［S.l.］： OpenProceedings.org， 2018： 469-472. 10.1145/3323878.3325804
20	HASSAN M， BANSAL S K. RDF data storage techniques for efficient SPARQL query processing using distributed computation engines ［C］// Proceedings of the 2018 IEEE International Conference on Information Reuse and Integration. Piscataway： IEEE， 2018： 323-330. 10.1109/iri.2018.00056
21	HASSAN M， BANSAL S K. Data partitioning scheme for efficient distributed RDF querying using Apache Spark ［C］// Proceedings of the IEEE 13th International Conference on Semantic Computing. Piscataway： IEEE， 2019： 24-31. 10.1109/icosc.2019.8665614
22	GURAJADA S， SEUFERT S， MILIARAKI I， et al. TriAD： a distributed shared-nothing RDF engine based on asynchronous message passing ［C］// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 289-300. 10.1145/2588555.2610511
23	HARBI R， ABDELAZIZ I， KALNIS P， et al. Accelerating SPARQL queries by exploiting Hash-based locality and adaptive partitioning［J］. The VLDB Journal， 2016， 25（3）： 355-380. 10.1007/s00778-016-0420-y
24	POTTER A， MOTIK B， NENOV Y， et al. Dynamic data exchange in distributed RDF stores［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（12）： 2312-2325. 10.1109/tkde.2018.2818696
25	ABDELAZIZ I， HARBI R， KHAYYAT Z， et al. A survey and experimental comparison of distributed SPARQL engines for very large RDF data［J］. Proceedings of the VLDB Endowment， 2017， 10（13）： 2049-2060. 10.14778/3151106.3151109
26	ALUÇ G， HARTIG O， ÖZSU M T， et al. Diversified stress testing of RDF data management systems ［C］// Proceedings of the 2014 International Semantic Web Conference， LNCS8796. Cham： Springer， 2014： 197-212.
27	HOFFART J， SUCHANEK F M， BERBERICH K， et al. YAGO2： a spatially and temporally enhanced knowledge base from Wikipedia［J］. Artificial Intelligence， 2013， 194： 28-61. 10.1016/j.artint.2012.06.001

系统	执行模型	存储模式	基数评估方式	查询规划方式
S2RDF	Spark	VP+ExtVP	概要统计信息	贪心搜索
PRoST	Spark	VP+WPT	概要统计信息	贪心搜索
WiW	Spark	WPT+iWPT	特征集	贪心搜索
C3W	Spark	WPT+iWPT+jWPT-inner	特征集	贪心搜索
C2WVP	Spark	WPT+iWPT+VP	特征集	贪心搜索
TriAD	RAM	六重索引	摘要图	动态规划
AdPart	RAM	哈希划分	概要统计信息	动态规划
RDFox	RAM	哈希划分	摘要图	动态规划

系统	执行模型	存储模式	基数评估方式	查询规划方式
S2RDF	Spark	VP+ExtVP	概要统计信息	贪心搜索
PRoST	Spark	VP+WPT	概要统计信息	贪心搜索
WiW	Spark	WPT+iWPT	特征集	贪心搜索
C3W	Spark	WPT+iWPT+jWPT-inner	特征集	贪心搜索
C2WVP	Spark	WPT+iWPT+VP	特征集	贪心搜索
TriAD	RAM	六重索引	摘要图	动态规划
AdPart	RAM	哈希划分	概要统计信息	动态规划
RDFox	RAM	哈希划分	摘要图	动态规划

数据集	三元组数/10⁶	唯一主语数/10⁶	唯一宾语数/10⁶	唯一的主语与宾语交集数/10⁶	唯一谓语数/10⁶	数据集大小/GB
WatDiv-1B	1 092.16	52.12	179.09	46.95	86	149.00
YAGO2	150.70	10.06	31.77	1.33	98	9.35

数据集	三元组数/10⁶	唯一主语数/10⁶	唯一宾语数/10⁶	唯一的主语与宾语交集数/10⁶	唯一谓语数/10⁶	数据集大小/GB
WatDiv-1B	1 092.16	52.12	179.09	46.95	86	149.00
YAGO2	150.70	10.06	31.77	1.33	98	9.35

查询类型	查询响应时间/ms
查询类型	S2RDF	PRoST	WiW	C3W	C2WVP	TriAD	AdPart	RDFox
L1	1 619	997	993	1 532	1 009	21	12	2
L2	1 093	940	946	1 132	961	38	37	38
L3	1 181	519	536	672	604	14	5	2
L4	567	359	373	602	455	12	4	4
L5	781	582	615	999	842	52	56	28
GM-L	985	633	649	931	742	23	14	7
S1	354	202	204	1 024	1 822	84	43	5
S2	975	491	510	552	550	73	17	12
S3	452	538	479	582	587	29	8	9
S4	478	743	751	661	874	68	25	23
S5	456	518	534	594	545	—	10	8
S6	396	501	473	582	541	24	3	4
S7	351	1 403	1 519	716	1 311	9	6	2
GM-S	647	759	758	659	794	—	10	7
F1	1 175	1 555	1 469	1 484	1 319	45	21	15
F2	3 366	1 060	1 163	1 331	1 066	562	33	5
F3	9 020	23 935	28 525	1 616	2 406	505	28	6
F4	4 410	25 927	153 779	1 772	100 174	—	49	11
F5	4 952	6 536	6 692	1 708	1 806	763	26	4
GM-F	3 787	5 821	8 711	1 574	3 609	—	30	7
C1	7 170	2 313	2 533	7 613	2 339	482	104	201
C2	3 610	42 384	46 924	—	6 814	675	145	198
C3	23 267	5 791	6 757	7 489	5 055	845	10 076	295
GM-C	8 445	8 280	9 295	—	4 319	650	534	227

Query performance evaluation of distributed resource description framework data management systems

分布式资源描述框架数据管理系统查询性能评价

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 27

Related Articles 15

Recommended Articles

Metrics

[1]	ZHANG Hao, ZHU Rui, SONG Fuyao, FANG Peng, XIA Xiufeng. Bichromatic reverse k nearest neighbor query method based on distance-keyword similarity constraint [J]. Journal of Computer Applications, 2021, 41(6): 1686-1693.
[2]	Xiajie ZHANG, Jinghua ZHU, Yang CHEN. Distributed rough set attribute reduction algorithm under Spark [J]. Journal of Computer Applications, 2020, 40(2): 518-523.
[3]	Bin LIU, Jinrong HE, Yuancheng LI, Hong HAN. Apple price prediction method based on distributed neural network [J]. Journal of Computer Applications, 2020, 40(2): 369-374.
[4]	Junhua GU, Feng WANG, Yongjun QI, Zheran SUN, Zepei TIAN, Yajuan ZHANG. Retrieval method of pulmonary nodule images based on multi-scale convolution feature fusion [J]. Journal of Computer Applications, 2020, 40(2): 561-565.
[5]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[6]	CHENG Wenliang, WANG Zhihong, ZHOU Yu, GUO Yi, ZHAO Junfeng. Design of distributed computing framework for foreign exchange market monitoring [J]. Journal of Computer Applications, 2020, 40(1): 173-180.
[7]	GUAN Haoyuan, ZHU Bin, LI Guanyu, CAI Yongjia. Efficient subgraph matching method based on resource description framework graph segmentation and vertex selectivity [J]. Journal of Computer Applications, 2019, 39(2): 360-369.
[8]	LIU Jing, XIAO Guanfeng. Bus arrival time prediction system based on Spark and particle filter algorithm [J]. Journal of Computer Applications, 2019, 39(2): 429-435.
[9]	LIU Zihao, LI Ling, YE Feng. Anomaly detection method for hydrologic sensor data based on SparkR [J]. Journal of Computer Applications, 2019, 39(2): 436-440.
[10]	ZHAO Wenfang, WANG Jingli, SHANG Min, LIU Yanan. Forecasting model of pollen concentration based on particle swarm optimization and support vector machine [J]. Journal of Computer Applications, 2019, 39(1): 98-104.
[11]	LI Longyang, DONG Yihong, SHI Weijie, PAN Jianfei. SQM: subgraph matching algorithm for single large-scale graphs under Spark [J]. Journal of Computer Applications, 2019, 39(1): 46-50.
[12]	CUI Chen, ZHENG Linjiang, HAN Fengping, HE Mujun. Design of secondary indexes in HBase based on memory [J]. Journal of Computer Applications, 2018, 38(6): 1584-1590.
[13]	GU Junhua, HUO Shijie, WU Junyan, YIN Jun, ZHANG Suqi. Parallel multi-layer graph partitioning method for solving maximum clique problems [J]. Journal of Computer Applications, 2018, 38(12): 3425-3432.
[14]	FU Mou, YANG Hekun, WU Tangmei, HE Run, FENG Chaosheng, KANG Sheng. Fast video transcoding method based on Spark Streaming [J]. Journal of Computer Applications, 2018, 38(12): 3500-3508.
[15]	GU Junhua, WU Junyan, XU Xinyun, XIE Zhijian, ZHANG Suqi. Optimization and implementation of parallel FP-Growth algorithm based on Spark [J]. Journal of Computer Applications, 2018, 38(11): 3069-3074.

查询类型	查询响应时间/ms
查询类型	S2RDF	PRoST	WiW	C3W	C2WVP	TriAD	AdPart	RDFox
IL-1-5	129 621	19 616	20 360	174 888	19 564	10 223	48	4
IL-1-6	38 406	24 666	24 021	31 658	24 488	20 456	26	4
IL-1-7	42 092	23 683	26 743	174 985	25 499	33 169	187	35
IL-1-8	41 929	26 083	27 139	175 935	25 134	17 896	20	5
IL-1-9	43 990	27 303	24 183	181 073	26 924	9 201	332	5
IL-1-10	40 206	26 543	28 947	174 527	27 597	8 688	242	19
GM-IL-1	49 954	24 506	25 073	132 399	24 719	14 659	85	8
IL-2-5	115 919	27 597	28 301	202 488	28 230	10 247	68	5
IL-2-6	38 007	33 236	35 160	21 580	34 046	15 317	66	3
IL-2-7	36 270	33 605	34 689	413 067	35 138	4 501	178	12
IL-2-8	35 536	35 802	34 716	382 925	34 336	20 112	115	7
IL-2-9	39 118	37 377	37 119	386 668	37 298	17 968	122	7
IL-2-10	36 211	34 563	39 133	384 681	38 251	17 891	189	10
GM-IL-2	44 762	33 548	34 683	216 440	34 391	12 881	113	7
IL-3-5	177 629	38 661	42 775	94 754	44 299	—	—	782 884
IL-3-6	364 554	118 863	90 537	57 232	87 870	—	—	2 042 988
IL-3-7	211 957	76 291	80 042	57 150	86 393	—	—	1 307 131
IL-3-8	4 263 406	96 191	96 693	143 280	164 449	—	—	7 379 970
IL-3-9	351 679	165 339	155 332	95 340	107 036	—	—	2 452 539
IL-3-10	354 677	168 895	167 061	135 009	169 329	—	—	2 154 819
GM-IL-3	440 430	99 004	95 898	91 099	100 039	—	—	2 082 383

查询类型	查询响应时间/ms
查询类型	S2RDF	PRoST	WiW	C3W	C2WVP	TriAD	AdPart	RDFox
IL-1-5	129 621	19 616	20 360	174 888	19 564	10 223	48	4
IL-1-6	38 406	24 666	24 021	31 658	24 488	20 456	26	4
IL-1-7	42 092	23 683	26 743	174 985	25 499	33 169	187	35
IL-1-8	41 929	26 083	27 139	175 935	25 134	17 896	20	5
IL-1-9	43 990	27 303	24 183	181 073	26 924	9 201	332	5
IL-1-10	40 206	26 543	28 947	174 527	27 597	8 688	242	19
GM-IL-1	49 954	24 506	25 073	132 399	24 719	14 659	85	8
IL-2-5	115 919	27 597	28 301	202 488	28 230	10 247	68	5
IL-2-6	38 007	33 236	35 160	21 580	34 046	15 317	66	3
IL-2-7	36 270	33 605	34 689	413 067	35 138	4 501	178	12
IL-2-8	35 536	35 802	34 716	382 925	34 336	20 112	115	7
IL-2-9	39 118	37 377	37 119	386 668	37 298	17 968	122	7
IL-2-10	36 211	34 563	39 133	384 681	38 251	17 891	189	10
GM-IL-2	44 762	33 548	34 683	216 440	34 391	12 881	113	7
IL-3-5	177 629	38 661	42 775	94 754	44 299	—	—	782 884
IL-3-6	364 554	118 863	90 537	57 232	87 870	—	—	2 042 988
IL-3-7	211 957	76 291	80 042	57 150	86 393	—	—	1 307 131
IL-3-8	4 263 406	96 191	96 693	143 280	164 449	—	—	7 379 970
IL-3-9	351 679	165 339	155 332	95 340	107 036	—	—	2 452 539
IL-3-10	354 677	168 895	167 061	135 009	169 329	—	—	2 154 819
GM-IL-3	440 430	99 004	95 898	91 099	100 039	—	—	2 082 383

查询类型	不同系统下的查询响应时间/ms
查询类型	S2RDF	PRoST	WiW	C3W	C2WVP	TriAD	AdPart
Y1	3 483	1 272	1 121	1 513	1 052	16	3
Y2	3 546	1 754	3 294	5 349	4 869	1 568	19
Y3	2 400	1 406	1 440	1 655	1 334	220	11
Y4	2 340	1 435	1 306	3 850	1 313	18	2
GM-Y	2 886	1 457	1 623	2 680	1 731	100	6

查询类型	不同系统下的查询响应时间/ms
查询类型	S2RDF	PRoST	WiW	C3W	C2WVP	TriAD	AdPart
Y1	3 483	1 272	1 121	1 513	1 052	16	3
Y2	3 546	1 754	3 294	5 349	4 869	1 568	19
Y3	2 400	1 406	1 440	1 655	1 334	220	11
Y4	2 340	1 435	1 306	3 850	1 313	18	2
GM-Y	2 886	1 457	1 623	2 680	1 731	100	6