Query Optimization Techniques for OODB Languages

这项研究是与俄勒冈州研究生院的大卫梅尔合作进行的。面向对象数据库（OODB）系统成功地与关系系统竞争以及满足许多非传统应用程序的性能要求的关键因素之一是开发有效的查询优化器。本研究解决了OODB语言的高效查询优化问题。该研究框架是基于一个演算，称为monoid理解演算，它已经被证明可以捕获现代OODB查询语言的大多数功能。这种有效而简单的方法将查询转换为基于该演算的中间形式，可以有效地优化。本研究集中在两个非常重要的优化问题，并提出了实用，有效，通用的解决方案。第一个问题是查询解嵌套，这是一种优化，尽管它可以显著提高性能，但大多数OODB系统都没有正确处理。开发了一个框架，概括了许多unnesting技术最近在文献中提出的，是能够消除任何形式的查询嵌套使用一个简单而有效的算法。第二个问题是在存在副作用的情况下的查询优化，即，可以在任何地方以任何形式包含对象更新的查询。一个实用的方法，允许相同的优化技术提出的常规查询使用最小的变化，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/