Advanced database technology, Spring 2003
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. Among other things,
the following topics will be treated: Index structures, error
recovery, relational operations, query optimization, external memory
algorithms, XML queries, GIS (geographic information systems)
databases, and text indexing.
The course will consist of two main parts. The first part will treat
traditional database implementation topics covered in database
textbooks. The second part will focus on algorithmic aspects of large
data sets and will be based on surveys and research papers.
Note that this is a theoretical course. There will not be any
implementation or exercises using computers.
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
- analyze and choose among main indexing technologies
- understand and perform query optimization
- explain how to do error recovery
- analyze and apply external memory algorithms
This can be obtained through the courses introduction to algorithms and data structures (IADS) and database systems (DBS).
Teaching consists of lectures and exercises.
- 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.
Mandatory hand-ins every week, at least 60% of which must be
satisfactory to enter the exam.
Oral (25 minute) or written (4 hour) exam depending on the number of
students. (Up to 20 means oral, otherwise written.)
Mandatory hand-ins required to enter exam.
Lectures and exercises on Thursdays.
Phone: 38 16 89 34
Phone: 38 16 88 21