Advanced database technology, Spring 2004
[Schedule]
[Course description]
[Course goal]
[Literature]
[Prerequisites]
[Course format]
[Examination]
[Lecturers]
News
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. |
|
|
|
Literature:
- GUW = Database systems - The complete book by Garcia-Molina, Ullman, and Widom.
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.
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:
- analyze and choose among main indexing technologies
- understand and perform query optimization
- explain how to do error recovery
- analyze and apply external memory algorithms
The students should before the course
- be familiar with basic data structures and algorithms, like search trees, sorting algorithms, and hashing.
- have experience analyzing the time and space required by an algorithm using big-O notation.
- be familiar with relational databases and query languages, e.g., SQL.
This can be obtained through the courses introduction to algorithms and data structures (IADS) and introduction to databases (IDBI) or database systems (DBS).
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
Email: pagh@itu.dk
|
Anna Östlin
Office: 1.23
Phone: 38 16 88 21
Email: annao@itu.dk
|