一种嵌入式实时数据库系统查询优化算法  

Query Optimization Algorithm for Embedded Real-time Database Systems

作　　者：宋静静[1] 贾智平[1] 

机构地区：[1]山东大学计算机科学与技术学院,济南250061

出　　处：《计算机工程》2007年第11期90-92,共3页Computer Engineering

基　　金：山东省科技攻关基金资助项目(2005GG1101001)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]