Topics in Database Systems: Topic: Main Memory and Embedded DBMS

CS 848, Waterloo, Spring '18

  Instructor:   David Toman (david@uwaterloo.ca)
  Lectures:     Tuesday 03:30-06:20 DC2568 
  Office:       DC 3344, x34777
  Class Info:   http://cs.uwaterloo.ca/~david/cs848s18/

Summary:

Textbook

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.

Class Schedule and Outlines:

• Week 1 (05/01): Introduction and organization, Goals (aka why are we here?), and a refresher on relational calculus.

  We introduce a case study of applying relational technology in non-traditional setting, such as embedded systems: 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:

  • Chapters 1 and 2 from the textbook,
  • original paper on relational model by Codd,
  • relational calculus reference (optional: in case you need to get up to speed).

• Week 2 (05/08):
  Queries and Plans.

  Reading for week 2:

  • Chapter 3 and 4 from the textbook,
  • Graefe G. Query evaluation techniques for large databases. ACM Comput. Surv., 25(2):73-170, 1993. (optional, but extensive survey)
  • list of systems for presentations

• Week 3 (05/15): Extra-logical Operations and Updates
  Extra-logical features: duplicates and cuts, updates.

  Reading for week 3:

  • Chapter 5 and 6 from the textbook,
  • Two query optimizers: starburst and volcano,

• Week 4 (05/22): Monday schedule (have to teach another class)

• Week 5 (05/29): Querying Databases through Ontologies: the "open world" case.

  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 5:

  • Rewriting Approach
  • Combined Approach (KR 2010 best paper)
  • Combined Approach with Inverses (ISWC 2013 best paper)
  • Combined Combined Approach

  Projects:

  • Database design for certain answer approaches (EL, DL-Lite)
  • Efficient maintenance of canonical interpretations (EL, DL-Lite)

• Week 6 (06/05): Query Compilation: Interpolation

  Reading for week 6:

  • Chapter 5 from the textbook
  • Sequent Calculus for Propositional Logic,
  • On Enumerating Query Plans Using Analytic Tableau,
  • An Interpolation-based Compiler and Optimizer for Relational Queries
    
  • classical "rewriting using views" paper
  • constant complement approach
  • (optional) Interpolant construction from tableaux and resolution proofs.

• Weeks 7-12 (06/19-07/17): Presentations/Projects
  • TBA

• Week 13 (07/24): Summary and wrap-up.

  ---

  Projects:

  Preferred projects will be related to applying (some) of the ideas presented in this class to your own area of research: this can further your own research and may help you to consider alternative views/approaches to what you have been thinking about already.
  1. project proposal: one page due at the latest on 06/12 (week 7) in class;
  2. project presentation: 20-30 minutes in weeks 10-12(-13);
  3. report (in pdf, up to 10 pages), source code (if applicable)

  If you don't see any relation to your own research, here are a few alternative options.

  ---

  Assessment:

  class participation, including assignments (20%)
  in class presentation either of your project or of a paper from the reading list (30%)
  project (50%)

  ---