Rada Chirkova and Michael R. Genesereth:
"Database Reformulation", Symposium on Abstraction, Reformulation and Approximation (SARA-98), Pacific Grove, California, May 9-12, 1998.
Abstract
We introduce an approach to view materialization to reduce the evaluation costs of query workloads under a storage limit, in relational databases. The approach is based on relational reformulation. We present a method for automatically discovering views of the stored relations that are not already defined yet present valuable opportunities for materialization. The proposed reformulation algorithm works off-line and consists of two stages. The first stage produces a set of candidates for materialization. At this stage, the algorithm rewrites the rules for the queries, to define predicates of smaller arity, or merges several predicates into one. At the second stage, decisions are made on which candidates to materialize; the criterion here is the amount of disk space that is available to store the tables for the views. This method makes use of additional knowledge about relations, namely of the information about functional dependencies in relations. The reformulations produced by this method preserve answers to all queries and improve query-processing performance. Moreover, the reformulation algorithm is polynomial in time.