NAME *Optor.pm* -- query optimization. DESCRIPTION This package includes the implementation of data structures and optimization algorithms for the logical optimization of the query expressions. The core of the module is the data structure *mesh* for the representation of sets of queries. Common sub-expressions of queries are shared ie. each query is represented in *mesh* only once. Queries are organized into equivalence classes. The module is the platform for the study of query optimization algorithms appropriate for the data environment of Qios. The module *Rule.pm* is used to perform logical transformations of the query trees and the module *Cost.pm* is applied for the computation of the cost of the newly generated query trees. The module currently includes the implementation of sub-optimal optimization algorithm based on dynamic programming. Mesh *mesh* is a data structure for storing query trees. The basic structure of *mesh* is directed acyclic graph (dag). The query trees have to share the common parts hence there is only one representation of a query expression in *mesh*. Further, the query trees are organized into equivalence classes. *mesh* has three entry points. First, queries in *mesh* can be accessed using the unique identifiers of queries which are created when query is entered in *mesh*. The mapping is realized between query trees (roots of) and the entries in *mesh* holding the queries. Second, queries in *mesh* can be accessed thru the equivalence classes which again have unique identification generated on the creation of the equivalence class. The inverse relationship from the query trees (roots of) to the equivalence classes is also defined. Third, queries can be accessed using the normalized query expressions (character strings) as the hash index targeting roots of query trees. In spite of various access methods, queries are in *mesh* defined free of the cover data structures as they are created using module *Que.pm*. Each query node includes solely a reference to the equivalence class to which it belongs. Optimization algorithms The algorithm implemented in *Optor.pm* is based on dynamic programming. The optimization is performed bottom-up: the leaves of the query tree are optimized first progressing then upwards toward the root of the query tree. For each query tree all possible logical transformations of the root of query tree are generated and optimized, recursively. At this point of the algorithm, the search space can be reduced by selecting only the promising queries based on cost estimation. COMMENTS This module is part of the *qios* programming environment.