Unnesting queries using algebraic equivalents in an Xquery engine

Abstract

Since the beginning of the 80’s, during the rise of relational databases, it has been developed many strategies to deal with problems of executing queries in a nested way. Most of these strategies are based on classification into generic query types, followed by an unnest technique for each type. The two main approaches to unnest are: source level and algebraic level. The latter has some advantages, as expressiveness. These publications were important to the success of relational database architectures. However, all this knowledge is not only useful for relational databases, but also for queries from non-relational databases, e.g. XML databases. Brackit is an open-source XQuery compilation engine, developed at Technische Universität Kaiserslautern. The compilation pipeline in this engine includes an optimization stage where we could develop unnesting algorithms. Aiming optimize the query evaluation in Brackit, we present how we applied algebraic equivalences to unnest queries. The contribution of this work is the implementation of an efficient and high level unnesting technique, easy to understand and to improve. This implementation reduces the heavy code legacy of the current optimizer version. The basis of these equivalences application was the good correspondence between the algebra and Brackit’s AST nodes. The optimization, thus, was based on AST manipulation. Here, we are going to call this manipulation as rewriting. For experimental analysis, it was performed simulations throw XQuery to prove the gain of the unnesting strategy.