Monoid Comprehensions as a Target for the Translation of OQL.
Torsten Grust · 1996
The rich type models that make object-oriented data models superior to their relational antecedents have an impact on the query formalism that is needed to capture today’s modern object query languages, like ODMG’s OQL [Cat95]. Instead of reintroducing the classical object algebra operators for each of the bulk type constructors like set, bag, and list — which led to rather intractable algebras in recent approaches, especially suffering from type conversion operators — the concept of a monoid can take the role of what the set played in the relational model [WT91]. These simple algebraic structures, obeying a few simple laws, allow for a uniform treatment of collections and scalars. They therefore account for the intermix of bulk operations and general purpose computations (e.g. arithmetics) that modern query languages feature. Comprehensions [Tri91] provide a convenient way to describe operations carried out on monoids, thus providing us with a powerful object calculus. ODMG OQL can be mapped to this calculus in a straightforward manner. The problem of deriving efficient execution plans for these calculus expressions has been tackled by recent work that promotes normlization by unnesting [FM95]. However, these approaches do not overcome the nestedloop nature the comprehensions imply. In contrast, we propose to translate OQL into a hybrid mix of calculus and algebra expressions [Nak90], letting each formalism handle the parts of the queries it can cope best with. We derive query plans that employ the strenghts of objects algebras when it comes to set-based computations, joins, grouping, etc., and at the same time can reason about quantification, arithmetics, and type conversion expressed by calculus expressions. In pure algebraic approaches, the latter were not captured by the formalism and as a consequence have been “black boxes” that were simply passed around during the rewriting phase of rule-based optimizers. Here, they have become amenable to pattern-matching and optimization, too. The algebra and calculus we use are tailored to support the interplay between both, e.g. in terms of exchanging selection predicates. We claim, that the proposed framework captures OQL-like query language completely and allows the derivation of more efficient execution plans, employing sophisticated join techniques, like nestjoins and semijoins.