Advanced database technology, Spring 2004

[Schedule] [Course description] [Course goal] [Literature] [Prerequisites] [Course format] [Examination] [Lecturers]


The first lecture is on February 5, 9-12 in room 1.60.

The rest of the lectures will take place in room 1.60, 10-15.


Lectures and exercises on Thursdays. Lectures and exercises will be mixed throughout the time allocated for the course.

The schedule is preliminary. It will be updated during the course. More detailed reading directions will also be provided.

Date Time Subject Literature Exercises / hand-ins Place
Feb. 5 9.00-12.00 Introduction. Recap of database background. (slides) Overview of lectures(slides). (Based on selected sections of the first part of GUW - not curriculum.)   1.60
Feb. 12 10.00-15.00 Data storage devices, I/O model.     1.60
Feb. 19 10.00-15.00 Representing data elements. Index structures.     1.60
Feb. 26   No lecture.      
Mars 4 10.00-15.00 B-trees. Hash indexes.     1.60
Mars 11 10.00-15.00 Implementation of relational operations I.     1.60
Mars 18 10.00-15.00 Implementation of relational operations II.     1.60
Mars 25 10.00-15.00 Dealing with system failures. Concurrency control.     1.60
Apr. 1 10.00-15.00 Geometric index structures.     1.60
Apr. 8   Easter      
Apr. 15 10.00-15.00 Text indexing.     tba
Apr. 22 10.00-15.00 Cache-oblivious algorithms.     tba
Apr. 29 10.00-15.00; Data mining. Course summary.     tba
June 10   Exam.      

Course description

The course will focus on implementation aspects of databases. In particular, we focus on situations where there are large amounts of data, or where advanced queries are needed, and show how to implement efficient data structures to address these needs.

Note that this is a theoretical course. There will not be any implementation or exercises using computers.

See the schedule above for more details.


Database Systems: The Complete Book by Hector Garcia-Molina, Jeff Ullman, and Jennifer Widom, 2002. Copies for the course are on sale from Samfundslitteratur. (Note that the "international edition" is less expensive.) Unless stated otherwise, the example material in the book is not part of the curriculum (however, it could help you understand the main text). In addition to the book there will be handouts, specified for each lecture in the schedule above.

Course goal

The goal of the course is to provide the student with an understanding of the inner workings of modern data storage and retrieval systems. After the course, the student should be able to analyze a given database task, and suggest an alternative implementation if standard database solutions are not efficient. In particular, the student should be able to:


The students should before the course This can be obtained through the courses introduction to algorithms and data structures (IADS) and introduction to databases (IDBI) or database systems (DBS).

Course format

Teaching consists of lectures and exercises in English.

Mandatory hand-ins

There will be 5 mandatory hand-ins during the course to be solved individually or in groups of two students. Assignments are given in connection with the lectures (and announced on the home page) and are due before the lecture in the following week. Every assigment is graded on a scale from A-E (A=very good, B=good, C=acceptable, D=not good enough, E=not handed in/late hand-in), and students must achieve A, B, or C on at least 4 out of 5 assignments. If you are not able to hand in in time, for some reason, inform the teacher as soon as possible. It is allowed to discuss assignments with other students, but the solutions must be prepared in groups of size at most 2. Hand-ins may be in Danish or English, and are to be handed in on paper - either directly to one of the lecturers or in the mail boxes in the information office.


Written exam, 4 hours, scheduled for June 10. Mandatory hand-ins required to enter exam.


Rasmus Pagh
Office: 1.23
Phone: 38 16 89 34
Anna Ístlin
Office: 1.23
Phone: 38 16 88 21