| In modern database systems, it is common to define views of stored data. The view mechanism provides opportunities for view materialization , whereby a database system precomputes and stores the tuples satisfying the view definition. To materialize the best views for a given application, it may be necessary to invent new views. This thesis considers automated database restructuring—the process of automatically inventing new views—and its application to increasing the efficiency of answering queries. This application is important for query optimization, data warehouse design, and information integration.; The thesis concentrates on developing complete database-restructuring algorithms that, given a query workload, a storage limit, and database statistics, would produce an optimal viewset—a viewset that satisfies the storage limit and minimizes the evaluation costs of the workload, on all databases with the given statistics. The thesis analyzes the problem in relational databases under set semantics and for conjunctive queries, also known as select-project-join queries with equality selections. The thesis addresses the theoretical questions that need to be answered in designing a complete database-restructuring algorithm, and examines the complexity of complete database-restructuring algorithms for the problem.; It is shown in the thesis that the search space of all acceptable viewsets can be infinite even for a single query. It is also shown that in spite of this fact, for any problem input with a conjunctive query workload there exists a finite and well-defined set of views that includes all views in at least one optimal (conjunctive) viewset. As a consequence, automated database restructuring is decidable for conjunctive queries and views. Another issue in automated database restructuring is how many views should be materialized to minimize the evaluation costs of a query. For two well-known cost models for joins, it is shown in the thesis that for some problem inputs and databases, the number of views in an optimal viewset is exponential in the size of the problem input. It follows that under set semantics, automated database restructuring has an exponential-time lower bound for conjunctive queries and views. |
