ALGEBRAIC OPTIMIZATION OF OBJECT-ORIENTED QUERY LANGUAGES

Advanced database applications demand new data modeling constructs bey ond those available in relational databases. These include both new da ta structures, e.g. arrays and quadtrees, and an integration with the object-oriented programming paradigm. Declarative object-oriented quer y languages transfer the burden of choosing an efficient execution pla n to the database query optimizer. The lack of a generally accepted ob ject-oriented data model and the trend towards extensible systems dema nd an extensible framework for object-oriented query optimization. We suggest such an algebraic optimization framework which is based on the computational metaphor of processing bulk data. Bulk data are defined using an abstract definition of the notion of data collection which i ncludes familiar and novel types of bulk data. In particular, we integ rate neatly object-oriented notions such as object identity and user-d efined methods. To obtain generally applicable results, we use an FP-l ike language in which programs are constructed from primitive function s using a fixed set of functional forms. The latter abstract common pa tterns of processing data collections. The resulting algebra of progra ms generalizes for any data collection the known laws for transforming relational queries. We go beyond FP by allowing data structures conta ining functions, thus supporting the optimization of programs required in database programming environments.