Survey of Physical Design Specification Languages
The goal of this project is to survey the state of art in how physical design decisions are communicated to database and information systems, ranging from system build/configuration options to extensions of the DDL/DML languages.
Survey of Chase-based Approaches to Query Rewriting
The goal of the project is to survey the literature on the Chase and Backchase style approaches, starting with the original paper
Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999, pages 459-470.including extensions beyond relational systems.
Extension of Chase-style Query Rewriting to account for interesting orders in Data
The goal of the project is to propose an extension of the Chase and Backchase approach to account for interesting orders in the data. The extension should include revisions to the query rewriting algorithm and explanation how the rewritten queries take (algorithmically) advantage of the additional information about order.
Survey of interpolation techniques for various proof systems
The goal of the project is to assemble a comprehensive (as feasible) list of approaches to interpolation extraction in various proof systems, e.g.,
Interpolation for conjunctive queries with binding patterns
The goal of the project is extend the interpolation-based technique for finding query rewritings to the case of conjunctive queries (CQ) with allowance for binding patterns (or "index declarations") for physical relations. The approach should accommodate query rewritings that can be obtained in the chase-based approaches for CQs.
Interpolation for conjunctive queries with ordering
The goal of the project is extend the interpolation-based technique for finding query rewritings to the case of conjunctive queries (CQ) with allowance for interesting orders for physical relations. The approach should devise the space of possible plans (i.e., how to take advantage of the ordering information algorithmically) and how to obtain such plans from interpolants.
Database design for certain answer approaches (EL, DL-Lite)
The goal of this project is to refine the construction of the canonical interpretation used to answer EL/DL-Lite queries efficiently to a more sophisticated design (i.e., beyond the table of "triples"). In particular, the issues of how to group data based on the database schema (and, preferably also on query/update workloads) is to be considered.
Efficient maintenance of canonical interpretations (EL, DL-Lite)
The goal of this project is to develop techniques for efficient maintenance of the canonical interpretations needed for efficient query answering under EL (DL-Lite) schemas. Of particular interest are incremental view maintenance techniques (including maintaining non-first order definable views in the case of EL).
Integrating Cost Models into Query Rewriting
The goal of the project is to investigate how query rewriting can be influenced by cost estimates. A particular focus is on how to modify the query rewriting algorithm(s) to generate plans with low estimated cost and/or how to use a cost model to prune the search space for feasible plans. This project can be either for the "chase-style" approach(es) and/or for the "Craig interpolation style" rewriting.
Conceptual Schema, Physical design, and Updates
The goal of this project is to investigate how to accommodate updates in a loosely-coupled physical designs (this relates closely to the problem of view updates.
Beyond FOL: Inductive Types, Fixpoints, and Datalog
The goal of this project is to (begin to) investigate the possibilities of using more powerful schema languages to capture non-first order constructs, such as linked lists.