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

摘  要：为了提高数据库操作的性能，对数据库查询操作进行优化是必要的。本文对数据库三种关系数据语言之一的关系代数语言的基本概念及其在数据库中的应用进行了介绍，同时对数据库最基本、常用的操作之一的查询操作进行了研究；着重针对目前使用较为广泛的关系代数查询优化算法进行了深入的分析和研究，并结合国内外研究现状通过对比演算，从性能、效率以及数据库系统的安全性上说明了合理配置和使用优化算法的重要性。
关键词：优化；关系代数；查询算法

Abstract：In order to improve the performance of database operation, optimization of query operation is necessary. This paper first introduces the basic concepts and application area of  relational algebra language——one of the relational data language, and describes the most basic and popular query manipulation. The paper mainly focuses on the relational algebra query algorithm which is current operation in general use with deep-going analysis and study. Combined with the latest research at home and abroad in this day and age, the paper shows the importance of the rational allocation and optimization algorithm for database by comparing the situation calculus, performance, efficiency and security of the database system.
Key words：Optimization; Relational Algebra; Query Algorithm

1 引言
随着计算机的应用不断深入，各种应用软件的普及(OA日常办公系统;档案管理系统等)，应用数据也随着日常工作而迅速地增长，作为数据仓库的数据库的重要性也日益显著。
而信息化进程不断地演进，数据库中的数据量也日益增加，数据库应用系统的查询性能也逐渐成了一个备受关注的话题。特别是对于那些基于Browser/Server形式的数据库开发，查询速度的快慢直接影响到系统的推广和应用。影响数据库系统的因素有很多，在这些因素中，本质又至关重要的是数据库管理系统本身的查询优化技术。这是因为在数据库系统的开发过程中，用户业务逻辑必须转换成为数据库查询语言执行，或将数据库查询语言嵌入在宿主语言程序中执行。
早在1975年Rothnie.J就在他的论文“E-valuating Inter Entry Retrieval Expressions in a Relational Data Base Management System”中提出了数据库原形系统DAMAS的双变量查询优化方法[1]，这篇论文被认为是最早研究查询优化的文献。由于决策支持系统的发展，优化显得越来越重要，特别在近几年的ACMSIGMOD会议中，每年都有50%以上的文章以各种方式论述优化的问题。
同时也要认识到：要使各种信息系统高效、正常、安全地运行，其关键是数据库应用系统能否正常、高效地运行。当数据量比较小的时候，数据库的速度和可靠性往往被人忽视，但是一旦数据量达到了上百万甚至更多时，数据库的瓶颈就马上浮现了。而数据库又是管理信息系统的核心，这就导致了整个管理系统的性能低下，使用者的抱怨率大幅提高，间接降低了工作效率。因此，探索数据库优化技术方法具有非常重要的意义。查询是数据库中最基本、最常用、最复杂的操作。基于数据库的管理信息系统中，查询操作是所有数据库操作中所占据比重最大的操作。当我们的数据库系统积累到一定程度时(如银行账户达到了上百万条、上千万条)，若我们查询时采用单条顺序扫描，那么我们扫描一遍所有的记录可能就得花上几十分钟，甚至几小时，这样的系统就失去了现实的使用价值。如何设计数据库，采取什么样的查询策略，使查询时间降为几分钟或者几秒钟，这就是我们所需要研究的查询优化问题。以下以分布式数据库为研究对象，并结合RDBMS，主要就基于关系代数的查询优化算法进行讨论。
1.1 研究意义
数据库技术从诞生到现在，在不到半个世纪的时间里，形成了坚实的理论基础、成熟的商业产品和广泛的应用领域，吸引了越来越多的研究者加入，使得数据库成为一个研究者众多且被广泛关注的研究领域。随着信息管理内容的不断扩展和新技术的层出不穷，数据库技术面临着前所未有的挑战。面对新的数据形式，人们提出了丰富多样的数据模型，同时也提出了众多新的数据库技术[2]。当今，许多应用软件都与这些新的数据库技术密切相关，基于数据库的联机事务处理(OLTP) 和联机分析处理(OLAP) 是银行、企业、政府等部门最为重要的计算机应用之一。目前，绝大多数的数据库应用软件都是基于关系数据库系统，查询操作所占据的比重最大，而且查询操作所基于的SELECT 语句在SQL 语言中又是代价最大的语句，很大程度上直接影响数据库应用软件的执行效率和性能。因此对查询操作进行优化处理十分必要。
1.2 国内外研究现状
1980年以前，数据库技术的发展，主要体现在数据库的模型设计上。进入90年代后，计算机领域中其它相关技术的发展对数据库技术产生了重大影响。数据库技术与网络通信技术、人工智能技术、多媒体技术等相互渗透，相互结合，使数据库技术的新内容层出不穷。数据库的许多概念、应用领域，甚至某些原理都有了重大的发展和变化，形成了数据库领域众多的研究分支和课题，产生了一系列新型数据库[3]。主要有以下几种优化方法：