Please wait a minute...
浙江大学学报(工学版)  2022, Vol. 56 Issue (2): 313-321    DOI: 10.3785/j.issn.1008-973X.2022.02.012
计算机与控制工程     
多区块链环境下的连接查询优化算法
董思含1(),信俊昌2,3,*(),郝琨1,4,姚钟铭2,陈金义2
1. 东北大学 医学与生物信息工程学院,辽宁 沈阳 110819
2. 东北大学 计算机科学与工程学院,辽宁 沈阳 110819
3. 辽宁省大数据管理与分析重点实验室,辽宁 沈阳 110819
4. 东软集团股份有限公司辽宁省区块链专业技术创新中心,辽宁 沈阳 110819
A join query optimization algorithm in multi-blockchain environment
Si-han DONG1(),Jun-chang XIN2,3,*(),Kun HAO1,4,Zhong-ming YAO2,Jin-yi CHEN2
1. College of Medicine and Biological Information Engineering, Northeastern University, Shenyang 110819, China
2. College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
3. Key Laboratory of Big Data Management and Analytics ( Liaoning Province) , Shenyang 110819, China)
4. Neusoft Corporation Research Center of Liaoning Promotion for Blockchain Engineering Technology, Shenyang 110819, China
 全文: PDF(929 KB)   HTML
摘要:

为了提高多区块链间的连接查询处理效率,提出多区块链环境下的连接查询优化算法. 该方法在传统的多区块链模型中增加语义信息,构建语义多区块链模型,为多区块链间的连接查询提供基础. 基于该模型,参考分布式数据库的索引结构,提出多区块链间的连接索引结构,将多条区块链进行属性连接,提高连接计算的效率,减少数据传输的通信代价. 在此基础上,提出多链连接查询优化算法,提升多区块链连接查询的效率. 最后,在2个真实公开的数据集上进行实验. 结果表明,多区块链间的连接索引结构稳定;与传统的直接进行连接查询的操作相比,多区块链连接查询优化方法简化了查询处理过程,通过访问连接索引直接获取查询结果,减少了本地计算负载和网络开销,提高了查询效率.

关键词: 多区块链语义多区块链模型多链连接索引多链连接查询区块链查询    
Abstract:

A join query optimization algorithm in a multiple blockchain environment was proposed, in order to improve the efficiency of join query processing on multi-blockchain. In this method, semantic information is added to the traditional multi-blockchain model, and a semantic multi-blockchain model is constructed to provide a basis for join query on multi-blockchain. Based on this model, referring to the index structure of the distributed database, a join index structure was proposed, which realizes attribute connection of multiple blockchains, improves the efficiency of connection calculation, and reduces the communication cost of data transmission. On these basis, a optimization algorithm about multi-blockchain join query was proposed to improve the efficiency of multi-blockchain connection query. The empirical study of the proposed method was conducted on two real public data sets. Results show that the connection index structure between multiple blockchains is stable. Compared with the traditional join query operation, multiple blockchain connection query optimization method simplifies the query processing process. Query results can be directly obtained by accessing the join index, which reduces local computing load and network overhead, and improves query efficiency.

Key words: multi-blockchain    semantic multi-blockchain model    multi-blockchain join index    multi-blockchain join query    blockchain query
收稿日期: 2021-07-14 出版日期: 2022-03-03
CLC:  TP 301  
基金资助: 国家重点研发计划资助项目(2021YFB3300900);国家自然科学基金资助项目(62072089);中央高校基本科研业务费资助项目(N2104001, N2116016, N2019007, N2024005-2, N180101028, N180408019);东软集团股份有限公司开放课题资助项目(NCBETOP2102)
通讯作者: 信俊昌     E-mail: dongsihan@stumail.neu.edu.cn;xinjunchang@mail.neu.edu.cn
作者简介: 董思含(1995—),女,硕士生,从事区块链技术研究. orcid.org/0000-0001-5248-3532. E-mail: dongsihan@stumail.neu.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
董思含
信俊昌
郝琨
姚钟铭
陈金义

引用本文:

董思含,信俊昌,郝琨,姚钟铭,陈金义. 多区块链环境下的连接查询优化算法[J]. 浙江大学学报(工学版), 2022, 56(2): 313-321.

Si-han DONG,Jun-chang XIN,Kun HAO,Zhong-ming YAO,Jin-yi CHEN. A join query optimization algorithm in multi-blockchain environment. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 313-321.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2022.02.012        https://www.zjujournals.com/eng/CN/Y2022/V56/I2/313

图 1  多区块链模型示意图
图 2  语义区块结构
图 3  S-Inverted Index结构
图 4  S-Bitmap和S-B+-tree索引结构
attr t1/ms t2/ms
1 4929 4791
2 4658 4624
3 4656 4944
4 4646 4713
5 4660 4710
6 4638 4751
7 4628 4764
8 4687 4863
表 1  索引构建所需时间
图 5  不同区块数时索引构建时间的变化
图 6  不同链数时索引构建时间的变化
图 7  D1数据集中不同结果集的连接查询时间变化
图 8  D2数据集中不同结果集的连接查询时间变化
图 9  D1数据集中不同链数时连接查询时间
1 NAKAMOTO S Bitcoin: a peer-to-peer electronic cash system[J]. Decentralized Business Review, 2008, 21260
2 WOOD G Ethereum: a secure decentralised generalised transaction ledger[J]. Ethereum Project Yellow Paper, 2014, 151: 1- 32
3 ISTI S, HARMAN Y, ENRICO L, et al Designing a permissioned blockchain network for the Halal industry using hyperledger fabric with multiple channels and the raft consensus mechanism[J]. Journal of Big Data, 2021, 8 (1): 1- 16
doi: 10.1186/s40537-020-00387-6
4 RUAN P, CHEN G, DINH T T A, et al Fine-grained, secure and efficient data provenance on blockchain systems[J]. Proceedings of the VLDB Endowment, 2019, 12 (9): 975- 988
doi: 10.14778/3329772.3329775
5 QIAO R, LUO X Y, ZHU S F, et al Dynamic autonomous cross consortium chain mechanism in e-Healthcare[J]. IEEE Journal of Biomedical and Health Informatics, 2020, 24 (8): 2157- 2168
doi: 10.1109/JBHI.2019.2963437
6 AMIRI M J, AGRAWAL D, ABBADI A E Caper: a cross-application permissioned blockchain[J]. Proceedings of the VLDB Endowment, 2019, 12 (11): 1385- 1398
doi: 10.14778/3342263.3342275
7 LI D, LIU W, DENG L, et al Design of multimedia blockchain privacy protection system based on distributed trusted communication[J]. Transactions on Emerging Telecommunications Technologies, 2021, 32 (2): e3938
8 ZHOU J, TANG F, ZHU H, et al. Distributed data vending on blockchain [C]// 2018 IEEE International Conference on Internet of Things and IEEE Green Computing and Communications and IEEE Cyber, Physical and Social Computing and IEEE Smart Data. Halifax: IEEE, 2018: 1100-1107.
9 王千阁, 何蒲, 聂铁铮, 等 区块链系统的数据存储与查询技术综述[J]. 计算机科学, 2018, 45 (12): 12- 18
WANG Qian-ge, HE Pu, NIE Tie-zheng, et al Survey of data storage and query techniques in Blockchain systems[J]. Computer Science, 2018, 45 (12): 12- 18
10 MUZAMMAL M, QU Q, NASRULIN B Renovating blockchain with distributed databases: an open source system[J]. Future Generation Computer Systems, 2019, 90: 105- 117
doi: 10.1016/j.future.2018.07.042
11 LI Y, ZHENG K, YAN Y, et al. EtherQL: a query layer for blockchain system [C]// International Conference on Database Systems for Advanced Applications. Suzhou: Springer, 2017: 556-567.
12 RAIKWAR M, GLIGOROSKI D, VELINOV G. Trends in development of databases and blockchain [C]// 2020 7th International Conference on Software Defined Systems. [S.l.]: IEEE, 2020: 177-182.
13 ZHU Y, ZHANG Z, JIN C, et al. Sebdb: semantics empowered blockchain database [C]// 2019 IEEE 35th International Conference on Data Engineering. Macau: IEEE, 2019: 1820-1831.
14 DINH T T A, DATTA A, OOI B C. A blueprint for interoperable blockchains [EB/OL]. (2019-10-22). https://arxiv.org/abs/1910.00985.
15 李芳, 李卓然, 赵赫 区块链跨链技术进展研究[J]. 软件学报, 2019, 6: 1649- 1660
LI Fang, LI Zhuo-ran, ZHAO He Research on the progress in cross-chain technology of blockchains[J]. Journal of Software, 2019, 6: 1649- 1660
16 ZAKHARY V, AGRAWAL D, ABBADI A E. Atomic commitment across blockchains [EB/OL]. (2019-06-18). https://xueshu.baidu.com/usercenter/paper/show?paperid=1n5p04y0k4690te01p5q04902d261734&site=xueshu_se&hitarticle=1.
17 JIANMO N. Amazon review data (2018) [DB/OL]. [2021-06-01]. https://nijianmo.github.io/amazon/index.html.
[1] 陈小波,陈玲,梁书荣,胡煜. 重尾非高斯定位噪声下鲁棒协同目标跟踪[J]. 浙江大学学报(工学版), 2022, 56(5): 967-976.
[2] 杜晓昕,王浩,崔连和,罗金琦,刘岩,张剑飞,王一萍. 基于聚类和探测精英引导的蜻蜓算法[J]. 浙江大学学报(工学版), 2022, 56(5): 977-986.
[3] 王万良,金雅文,陈嘉诚,李国庆,胡明志,董建杭. 多角色多策略多目标粒子群优化算法[J]. 浙江大学学报(工学版), 2022, 56(3): 531-541.
[4] 熊国文,张敏,许文鑫. 基于众包模式的两级开闭混合车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55(12): 2397-2408.
[5] 吴敬理,伊国栋,裘乐淼,张树有. 高温混合障碍空间中的移动机器人路径规划[J]. 浙江大学学报(工学版), 2021, 55(10): 1806-1814.
[6] 张则强,许培玉,蒋晋,张裕. 站间操作者不同的并行拆卸线平衡问题优化[J]. 浙江大学学报(工学版), 2021, 55(10): 1795-1805.
[7] 鲁建厦,翟文倩,李嘉丰,易文超,汤洪涛. 基于改进混合蛙跳算法的多约束车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55(2): 259-270.
[8] 程松,邹宗峰. 平面桁架构建的定日镜面形支撑结构优化及实验[J]. 浙江大学学报(工学版), 2020, 54(12): 2310-2320.
[9] 冀俊忠,宋晓妮,杨翠翠. 基于鱼群算法的脑功能连接邻域粗糙集特征归约方法[J]. 浙江大学学报(工学版), 2020, 54(11): 2247-2257.
[10] 付晓峰,牛力,胡卓群,李建军,吴卿. 基于过渡帧概念训练的微表情检测深度网络[J]. 浙江大学学报(工学版), 2020, 54(11): 2128-2137.
[11] 吴其,黄小红,马严,丛群. 复合型日志的模板提取方法[J]. 浙江大学学报(工学版), 2020, 54(8): 1557-1561.
[12] 刘葛辉,陈绍宽,金华,刘爽,彭宏勤. 基于延迟时间模型的不完全检修计划优化模型[J]. 浙江大学学报(工学版), 2020, 54(7): 1298-1307.
[13] 周朝君,黄明辉,陆新江. 基于低维约束嵌入的分布参数系统建模[J]. 浙江大学学报(工学版), 2019, 53(11): 2154-2162.
[14] 徐嘉豪,冀俊忠,杨翠翠. 基于蝙蝠算法的蛋白质网络功能模块检测[J]. 浙江大学学报(工学版), 2019, 53(8): 1618-1629.
[15] 董立岩,金佳欢,方塬程,王越群,李永丽,孙铭会. 基于非负矩阵分解的Slope One算法[J]. 浙江大学学报(工学版), 2019, 53(7): 1349-1353.