A logic-based approach to query processing in federated databases (Q1331016)

The paper describes in detail an approach to query processing in multidatabase systems in which the local systems can be based on the relational, the network, or the hierarchical model. Basically, a global query, directed against the system as a whole, is decomposed into component queries which can be executed on local systems. While this idea is not new, the novel feature of the approach is to use logic as fas as possible. Indeed, a user query, here assumed to be written in an extension of SQL suitable for federated databases, is first transformed in to a domain relational calculus query, which is then optimized using integrity constraints specified for local and global schemas. The result is transformed into a query of relational algebra, which is decomposed such that it becomes applicable to a local database. Finally, subqueries get modified further, in case the local database in question is non- relational. Logic is additionally used in this paper for schema integration purposes. Indeed, local schemas, even if not based on the relational model, are interpreted as predicates, and global relation schemas are obtained via rules written as Horn clauses. As a result, two important aspects of federated databases, schema integration and query processing, can be treated in a uniform framework. The paper contains sufficiently many examples to illustrate the exposition; algorithms for query compilation and simplification using data dependencies are presented at an informal level. On the other hand, no properties of the translation procedure are formally investigated.