Self-Organizing Databases

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. We look at view design - the process of automatically inventing new views - and its application to increasing the efficiency of answering database queries. This application is important for query optimization, data warehouse design, and information integration. We also discuss the broader idea of self-organizing databases, which is based on view (re)design and (re)materialization over time, in response to changing demands on database performance. We discuss how, given a query workload, a database, and constraints on the materialized views, to produce an optimal viewset - a set of views that satisfies the constraints and minimizes the evaluation costs of the workload queries on the database. We analyze the problem in relational databases under set, bag, and bag-set semantics for select-project-join queries with equality selections, also known as conjunctive queries. We address the theoretical questions that need to be answered in designing efficient scalable view-design algorithms for self-organizing databases, and examine the complexity of the problem.