基于迭代回溯的数据库查询优化算法

Iterative Backtrack Algorithm of Query Optimization

查询优化器是数据库系统最重要的组件之一。该文提出了一类新的查询优化算法,并对其性能进行了评估、讨论。它是基于分层回溯的一种查询优化算法,其优点主要在于对于一些复杂的应用环境,它在枚举算法的高复杂性和算法产生方案的质量之间取一个权衡点,以产生“次优”的优化结果来换取算法的执行效率,大大节省了运行环境的资源。该算法可以应用于当今一些新型数据库,如对象数据库和XML数据库等。

The query optimizer is one of the most important components of a database system.This paper presents and evaluates a new type of query optimization algorithms that are based on layered backtrack algorithm.If complex queries need to be processed,it can produce quite″good″plans while some other algorithms are not viable because of their high complexity.It can also be applied in some new kinds of databases as OODB and XML databases.