Query optimization in multidatabase systems considering schema conflicts

In a multidatabase system, the participating databases are autonomous. The schemas of these databases may be different in various ways, while the same information is represented. A global query issued against the global database needs to be translated to a proper form before it can be executed in a local database. Since data requested by a query (or a part of a query) is sometimes available in multiple sites, the site (database) that processes the query with the least cost is the desired query processing site. In this paper, we study the effect of differences in schemas on the cost of query processing in a multidatabase environment. We first classify schema conflicts to different types. For each type of conflict, we show how much more or less complex a translated query can become in comparison with the originally user-issued global query. Based on this observation, we propose an analytical method that considers the conflicts between local databases and finds the database(s) that renders the least execution cost in processing a global query. This research introduces a new level of query optimization (termed the schema-level optimization) in multidatabase environments. Our results provide a new dimension of enhancement for the capability of query optimizer in multidatabase systems.