The complete paper is available in PostScript
Query folding is a technique for determining how a query may be answered using a given set of resources, which may include materialized views, cached results of previous queries, or queries answerable by other databases. Its applications include query optimization in centralized databases, query processing in distributed databases, and query answering in federated databases. The power of query folding can be considerably enhanced by taking into account integrity constraints that are known to hold on base relations. This paper describes an extension of query folding that utilizes functional dependencies to find foldings of queries that would otherwise be overlooked. We describe a strategy for finding foldings in the presence of functional dependencies and present a basic algorithm that implements that strategy.