Architecture and Implementation of Database Systems

Course Topics

Indexing

Tree-structured indices provide fast and scalable access to one- and multi-dimensional data. More specifically, we look into B-trees and various approaches to multi-dimensional indexing (k-d-trees, K-D-B-trees, R-trees, UB-trees).

Query Processing and Optimization

Internally, user input queries are translated into a query execution plan. We look at key operations such as (external) sorting and join processing (block nested loops join, sort-merge join, hash join). The most efficient execution plan is discovered by the system's optimizer, then evaluated by a processing engine such as the "Volcano" iterator model.

Transactions and Recovery

The ACID principle provides a consistent multi-user execution model. We look at techniques to implement it internally, with a focus on two-phase locking and the ARIES protocol for recovery.

Recent Developments

We conclude this lecture with a glimpse into current database research issues, including support for modern computing hardware.

The course serves two purposes: it aids practitioners to gain most out of their database system and gives students the background and tools required to complete their MSc thesis in the area of information systems.

Lecture Slides

Exercise Sheets

Exercise sheets are published here on a weekly basis, a few days ahead of the Thursday exercise session. You do not have to solve any of the exercises before the session (read: no homework), but we do encourage you to look at the questions and maybe revisit the relevant lecture slides. This will make it a more interactive and fun experience :) Solutions will be published weekly, shortly after the Friday session.

Exam

• The exam for this course is on Thursday, December 17, 2009 in Room CAB G 56.
• We would like to start with the exam at 14:30. Please be at CAB G 56 at 14:15 to make sure we can start on time. The exam duration is 60 min.
• You are allowed to bring one (1) piece of paper, DIN A4, hand-written (you can write on both sides). No other material is allowed in the exam. No need to bring a calculator.
• All exam questions will be in English. You can write your answers in English or German.
• Don't forget to bring your Legi and a dark pen (black or blue; no pencils).

Course Evaluation

This course was evaluated on November 26, 2009. Here are the evaluation results:

• Answers to multiple-Choice part of the evaluation
• Free text comments
• Additional questions D1 to D12 (these were added by J. Teubner)
• Comparative Averages

Literature

The material that we discuss in this course is covered in many database text books (though not all of those books focus on implementation details as much as we do). The general advise is thus to browse the library and find the book that you like best.

Some books I personally like:

• Ramakrishnan and Gehrke. Database Management Systems. McGraw-Hill.
• Kemper und Eickler. Datenbanksysteme. Eine Einführung. Oldenbourg-Verlag. (in German)

Course Hours

Lecture

Thu, 14−16h, room CAB G 56 ― Instructor: Jens Teubner

Exercises

Thu, 16−17h, room CAB G 51 ― Instructor: Philipp Unterbrunner

Fri, 13−14h, room CAB G 56 ― Instructor: Philipp Unterbrunner

Additional Information

This course will be taught in english and is listed as course number 251-0365-00 in the ETH course catalog. You'll get 4 credit points for this 2V + 1Ü course.

Important note: This course is going to have significant overlap with the course "Information Systems" (ETH course entry 252-0201-00; Nesime Tatbul is adopting a large part of the slide material I prepared for this course). Therefore, you cannot receive credits for both courses. This only applies if you plan to attend "Information Systems" this semester; there is no problem if you attended "Information Systems" in some earlier semester. If this causes a problem for you, please contact Nesime Tatbul or Jens Teubner.