Query Optimization Techniques for OODB Languages

这项研究是与俄勒冈州研究生院的大卫·迈尔合作进行的。面向对象数据库(OODB)系统成功地与关系系统竞争并满足许多非传统应用程序的性能要求的关键因素之一是开发有效的查询优化器。本研究致力于面向对象数据库语言的高效查询优化。该研究框架基于一种称为么半群理解演算的演算，该演算已经被证明能够捕获现代OODB查询语言的大部分特征。这种有效而简单的方法基于该演算将查询转换为可以高效优化的中间形式。这项研究集中在两个非常重要的优化问题上，并提出了实用、有效和通用的解决方案。第一个问题是查询解嵌套，这是一种优化，尽管极大地提高了性能，但大多数OODB系统并没有正确处理它。开发了一个框架，该框架概括了最近文献中提出的许多去嵌套技术，并且能够使用简单而有效的算法来消除任何形式的查询嵌套。第二个问题是在存在副作用的情况下的查询优化，即可能在任何位置以任何形式包含对象更新的查询。开发了一种实用的方法，允许将针对常规查询提出的相同优化技术用于具有副作用的OODB查询，并进行最小程度的更改。构建了一个原型查询优化器，证明了这些优化技术大大提高了查询和更新的性能。这项研究的结果将帮助OODB供应商构建更好的查询优化器，从而带来更好的系统性能。Http://www-cse.uta.edu/~fegaras/opt/

This research is carried out in collaboration with David Maier of the Oregon Graduate Institute. One of the key factors for object-oriented database (OODB) systems to successfully compete with relational systems as well as to meet the performance requirements of many non-traditional applications is the development of an effective query optimizer. This research addresses efficient query optimization for OODB languages. The research framework is based on a calculus, called the monoid comprehension calculus, which has already been shown to capture most features of modern OODB query languages. This effective, yet simple approach transforms the queries into an intermediate form, based on this calculus, that can be efficiently optimized. This research concentrates on two very important optimization problems and proposes practical, effective, and general solutions. The first problem is query unnesting, an optimization that, even though improves performance considerably, is not treated properly by most OODB systems. A framework is developed that generalizes many unnesting techniques proposed recently in the literature and is capable of removing any form of query nesting using a simple and efficient algorithm. The second problem is query optimization in the presence of side effects, i.e., queries that may contain object updates at any place and in any form. A practical method is developed that allows the same optimization techniques proposed for regular queries to be used with minimal changes for OODB queries with side effects. A prototype query optimizer is constructed to demonstrate that these optimization techniques considerably improve performance for queries as well as updates. The results of this research will help OODB vendors build better query optimizers, leading to better system performance. http://www-cse.uta.edu/~fegaras/opt/