Query Optimization Techniques for OODB Languages

这项研究是与俄勒冈研究生院的David Maier合作进行的。面向对象数据库（OODB）系统要成功地与关系系统竞争并满足许多非传统应用程序的性能需求，关键因素之一是开发有效的查询优化器。本研究解决了面向对象数据库语言的高效查询优化问题。该研究框架基于一种称为单oid理解演算的演算，该演算已经被证明可以捕获现代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/