Semantic query optimization in heterogeneous DBMSs

Semantic query optimization is the process of transforming a query issued by a user into a different query which, because of the semantics of the application, is guaranteed to yield the correct answer for all states of the database. While this process has been successfully applied in centralized databases, its potential for distributed and heterogeneous systems is enormous, as there is the potential to eliminate inter-site joins which are the single biggest cost factor in query processing. Further justification for its use is provided by the fact that users of heterogeneous databases typically issue queries through high-level languages which may result in very inefficient queries if mapped directly, without consideration of the semantics of the system. Even if this is not the case, users cannot be expected to be familiar with the semantics of the component databases, and may consequently issue queries which are unnecessarily complicated. In this paper, we present the design of a semantic query optimizer for a heterogeneous database management system. It is based on an extension of a centralized implementation which focusses on finding a `near optimal' query that can be derived quickly. The semantics of the application are represented as a relational database and algorithms are defined which access this database to perform transformations to the query.