• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2021, Vol. 43 ›› Issue (12): 2272-2280.

• 人工智能与数据挖掘 • 上一篇    

基于蚁群遗传混合算法改进的连接查询研究

张逸风1,佟国香1,刘军2,屈亚宁2   

  1. (1.上海理工大学光电信息与计算机工程学院, 上海 200093;

    2.山东山大华天软件有限公司,山东 济南 250000)

  • 收稿日期:2020-07-23 修回日期:2020-10-24 接受日期:2021-12-25 出版日期:2021-12-25 发布日期:2021-12-31
  • 基金资助:
    国家重点研发计划(2018YFB1700902)

Connection query based on improved ant colony genetic algorithm

ZHANG Yi-feng1,TONG Guo-xiang1,LIU Jun2 ,QU Ya-ning2   

  1. (1.School of Optical-Electrical and Computer Engineering,

    University of Shanghai for Science and Technology,Shanghai 200093;

    2.Shandong Hoteam Software Co.,LTD.,Jinan 250000,China)

  • Received:2020-07-23 Revised:2020-10-24 Accepted:2021-12-25 Online:2021-12-25 Published:2021-12-31

摘要: 连接查询优化技术对提升数据库性能至关重要,提出一种改进的连接查询算法,结合Wander Join连接查询算法,使用蚁群遗传混合算法对连接顺序进行优化。执行新的连接计划后,用剪枝策略降低样本的连接复杂度,达到了减少存储代价的目的。
理论分析和基于TPC-H数据集、TPC-DS数据集的算法对比实验表明,在多表连接的样本置信区间大于或等于95%的条件下,根据选择率的不同,加入蚁群遗传混合算法和剪枝策略的连接查询算法的相对错误率与Wander Join连接查询算法相比下降了20%~70%。

关键词: 数据管理, 数据库, 查询优化, 连接图, 混合算法

Abstract: Connection query optimization technique is very important to improve database performance. This paper proposes an improved connection query algorithm, which combines the Wander Join query algorithm and the ant colony genetic hybrid algorithm to optimize the connection order. After executing the new connection plan, pruning strategy is used to decrease the complexity of sample connection, thus achieving the purpose of reducing storage cost. Theoretical analysis and comparative experiment on TPC-H data set and TPC-DS data set are carried out. Experimental results prove that, under the condition that the sample confidence interval of multi-table connection is greater than or equal to 95%, the connection query algorithm combing the ant colony genetic hybrid algorithm and pruning strategy can reduce the relative error rate by 20% to 70% in comparison to the Wander Join query algorithm.


Key words: data management, database, query optimization, connected graph, mixed algorithm