Instructor: David Toman (david@uwaterloo.ca) Lectures: Monday 4:00-6:30 pm DC2568 Office: DC 3344, x34777 Class Info: http://cs.uwaterloo.ca/~david/cs848s13/
You can get an electronic (pdf) copy of the textbook
here
for free (while on UW campus network), or a hard-copy if you prefer from Amazon.
We introduce a case study of applying relational technology in non-traditional setting: the Linux kernel and discuss the desiderata for alternative approaches to relational query processing; this discussion will yield the goals of the class.
Reading for week 1:
Assignment 1 (due in class week 05/13)
The current approaches to physical design closely follows conceptual design: e.g., creating base files for all tables, adding additional indices, etc. New applications and performance requirements have lead to the introduction of additional physical structures, e.g., materialized views, but query optimization technology has fallen behind; typically using only ad-hoc techniques for including materialized views into query plans. The lecture will survey current practices, identify their weaknesses and outline possible solutions. It will also introduce the unifying theme for the remaining lectures: the development of an uniform and integrated approach to physical design that is decoupled from conceptual schemes and to query compilation and optimization in this setting.
Reading for week 2:
The lecture will introduce basic techniques for executing relational queries in terms of query plans. Furthermore it will discuss additional annotations, such as binding patterns and their use to describe physical designs.
Reading for week 4:
The lecture will discuss several case studies that allow refined physical designs possibly up to the level of (sets of) main-memory records connected by pointers. The theoretical underpinnings will be accompanied by examples of fine-grained descriptions of physical designs by elaborating on traditionally monolithic data structures (such as B+ trees) via constraints. It will also consider the reasoning complexity (decidability) vs. expressive power trade-offs in schema languages: what the right trade-off and the impact on query languages, query evaluation, and query "safety" issues might be.
The lecture will study chase-based approaches to query rewriting and its limitations (e.g., the inability of rewriting conjunctive queries over conjunctive views); the impact of binding patterns for accessing indices, and the integration with (simple) cost models. Other issues discussed in this lecture will relate to handling duplicates and order of data and to approaches for accommodating these crucial features in query plans. The lecture will also discuss shortcomings of existing approaches to rewriting complex queries based on ad-hoc approaches, such as the query graph model (QGM), and then introduce a novel technique based on the application of Craig's Interpolation Theorem to the query rewriting problem, in particular it will show how to extract rewritings from refutation proofs. In addition it will discuss the usual extensions needed for efficient query processing, e.g., binding patterns, duplicates, and ordering.
Reading for week 6:
The lecture will show how the query compilation technology can be applied to the problem of database update. It will show how the classical view update problem can be solved and then it will discuss advanced topics in database update,such as the value invention, etc.
Reading for week 7:
The presentation will consider an alternative to query rewriting (equivalence under constraints): the computation of certain answers. It will introduce the approach and discuss its computational price in terms of how powerful query and constraint languages are used. It will show that such an approach is computationally feasible for only relatively weak languages. It will then discuss the possibility of generating certain answer based on first-order rewritability in such a setting, i.e., for conjunctive queries over ontologies formulated in families of suitably restricted description logics, such as ELH and DL-Lite.
Reading for week 8:
Projects:
If you don't see any relation to your own research, here are a few alternative options.