关系代数查询优化算法的研究与实现

（2）把SELECT操作运算沿查询树下移，如图6所示：

 
（3）首先应用更具限制性的SELECT操作，如图7所示：

 
（4）用Join操作代替笛卡尔积和SELECT操作，如图8所示：

 
（5）把投影操作下移，如图9所示：

5 总结
查询处理是数据库管理的核心[19]，而查询优化又是查询处理的关键技术。任何类型的数据库都会面临查询优化问题，对于关系数据库来说，由于其依据理论的特点查询优化问题的研究和解决，反而成为其蓬勃发展的重要机遇。查询优化一般分为：代数优化，物理优化和代价估算优。代数优化是指对关系代数表达式的优化；物理优化是指存储路径和底层操作算法的优化，代价估算优化是对多个查询策略的优化选择。在此，主要讨论代数优化，其特点是在启发式规则的指导下，用关系代数等价变换对表达式进行优化组合，以提高查询效率。关系代数的优化规则主要有“尽早执行选择”、“尽早执行投影”和“避免单独执行笛卡尔积”等。
现代的数据库系统内部存在查询优化器，里面已经固化了由世界顶尖程序员开发出来的众多查询优化算法。因此，对于我们任何查询要求，数据库已经依据数据字典和经验为我们制定了了最优（应该说是较优）的查询执行策略，并且在内部将SQL语句转换为了关系代数，同时以查询树为数据结构，依据查询优化启发式规则，按照关系代数等价变换的公式进行优化的。所以，我们看到的最后结果已经是较优的了。
由于大部分优化算法只掌握在少数人手里，并且受到版权保护，我在本论文中只就应用较为广泛的基于启发式规则的查询优化算法加以研究和讨论。同时，限于现代数据库系统高度的集成性，无法对内部处理机制加以干预，本人无法对算法进行实现，进而加以演示，所以，只能在人为设定的环境中，在给予同等资源的条件下对优化结果进行一个估算，这是本毕业论文的一个缺陷。

参考文献
[1] 邵佩英.分布式数据库系统及其应用[M].北京:科学出版社,2003：105-108.
[2] 萨师煊,王珊.数据库系统概论[M].北京:高等教育出版社,2002：98-103.
[3] 王能斌.数据库系统原理[M].北京:电子工业出版社,2000：36-40.
[4] 冯勇,白杨,徐红艳.分布式查询优化算法与应用实践[J].辽宁大学学报,2003：105-112.
[5] 郑勇明,彭凤梅,陈越.分布式数据库查询优化处理---基于关系代数等价变换的查询优化处理.电脑知识技术[J],2007：87-93.
[6] 王艳,陶俊才,周兴斌.分布式数据库查询优化处理的研究与应用[J].南昌大学学报,2005：19-110.
[7] 钟武,胡守仁.一种分布式数据库查询优化方法[J].计算机学报，1998：15-17.
[8] 王朝瑞.图论[M].北京：国防工业出版社出版，1985(5)：79-82.
[9] A.P.Sheth and J.A.Larson. Federated database systems formanaging distributed, heterogeneous, and autonomous Databases[J]. ACM Computing Surveys, September, 1990：54-56.
[10] Kifer Michael, Kim Won, and Sagiv Yehoshua. Querying object-oriented databases[C].In Proc. ACM SIGMOD, 1992：32-36.
[11] John Grant, Witold Litwin, Nick Roussopoulos, and Timos Sell-is. Query languages for relational multidatabases[J]. VLDBJournal, 1993, 2(2)：14-15.