Rada Chirkova and Chen Li "Materializing Views with Minimal Size to Answer Queries," in Proceedings of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-2003).
Abstract
In this paper we study the following problem. Given a
database and a set of queries, we want to find, in advance, 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 many 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. If queries can have self-joins, then a
disjunctive viewset can be a better solution than any set of conjunctive
views. We show that the problem of finding a minimal-size
disjunctive viewset is decidable, and give an upper bound on
its complexity. Surprisingly, if workload queries cannot have
self-joins, there is no need to consider disjunctive viewsets, and we
show that the problem is in NP. We describe a very compact search
space of conjunctive views, which contains all views in at least one
optimal disjunctive viewset. We give a dynamic-programming algorithm
that finds a minimal-size disjunctive viewset for queries without
self-joins, and discuss heuristics to make the algorithm efficient.