Query Evaluation in CROQUE : Calculus and Algebra Coincide

Abstract

With the substantial change of declarative query languages<br />from plain SQL to the so-called "object SQLs", in particular OQL, there<br />has surprisingly been not much change in the way problems of query representation and optimization for such languages are tackled. We identify<br />some of the difficulties pure algebraic approaches experience when facing object models and the operations defined for them. Calculus-style<br />formalisms suite this challenge better, but are said not to be efficiently<br />implementable in the database context.<br />This paper proposes a hybrid query representation and optimization approach, combining the strengths of a many-sorted query algebra and<br />the monoid comprehension calculus. We show that efficient execution<br />plans beyond nested-loop processing can be derived in such a framework. The translation process accounts for queries manipulating bulk-typed values by employing various join methods of the database engine, as well as queries that use aggregation, construction of arbitrary values, and arithmetics.