Rada Chirkova, Chen Li, and Jia Li:
"Materializing Views with Minimum Size to Answer Queries", technical report, May 2004.
Abstract
In this paper we study the following problem. Given a
database and a set of queries, we want to find a set of views that
can compute the answers to the queries, such that the size of the
viewset (i.e., the amount of space, in bytes, required to store the
viewset) is minimal on the given database. This problem is important
for applications such as distributed databases, data warehousing, and
data integration. We explore the decidability and complexity of the
problem for workloads of conjunctive queries. We show that results
differ significantly depending on whether the workload queries have
self-joins. Further, for queries without self-joins we describe a
very compact search space of views, which contains all views in at
least one optimal viewset. We apply our theoretical results using a
real-life application: In a client-server framework, we devise an
efficient practical approach that finds a provably optimal
solution to the problem of minimizing the communication costs of
transferring answers to large-join queries when the answers have a
lot of redundancy. We validate the approach by extensive experiments
and discuss competing or complementary approaches.