摘要： 针对嵌入式实时数据库系统的特点，提出了一种新的连接顺序优化算法 (Greedy Iterative Improvement, GII)。该算法结合了贪婪算法和迭代改进算法的优点，能满足系统的实时要求，可以控制查询优化时间，比传统查询优化策略更好地适应不同类型事务的需要。模拟实验结果表明，该算法在穷举式搜索适用时，能以比它小得多的时间和内存开销找到最优解；在穷举式搜索无法实现优化时，GII算法生成解的质量也明显优于贪婪算法和迭代改进。

关键词: 嵌入式实时数据库系统, 连接顺序, 贪婪算法, 迭代改进, 查询优化

Abstract: Based on the characteristics of embedded real-time database systems, this paper proposes a new join order optimization algorithm, which is a combination of greedy algorithm(GA) and iterative improvement(II). This algorithm can meet the real-time requirements and controls the query optimization time, therefore it is more suitable for the need of different kinds of transactions than traditional query optimization strategies. The simulation experiments show that the algorithm can find the optimal solution with less time and space complexity compared with exhaustive search(ES) and obviously outperforms GA and II in terms of output quality in situations where ES is not viable.

Key words: Embedded real-time database systems, Join order, Greedy algorithm, Iterative improvement, Query optimization

中图分类号: 

• TP311