Advanced database technology, Spring 2003

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

News

The exam is in room 0.10, from 9.00 to 13.00 on Thursday, June 12. Remember to bring your study card. Good luck!

The course curriculum can be found in the schedule, where slides and literature is curriculum unless explicitly stated otherwise.

Slides from Gerth Brodal's talk on cache obliviousness can be found here.

You can find project proposals here.

Schedule

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. 6 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.) For Feb. 13 1.60

Feb. 13 10.00-12.00; 13.00-16.00 Data storage devices, I/O model (slides). GUW 11.1-11.5; Handouts: [Sanders03, 1.3-1.5], [MaheshwariZeh03, 3.1-3.2]. For Feb. 20 1.60

Feb. 20 10.00-12.00; 13.00-16.00 Representing data elements (slides). GUW 12, [Pagh03, sec. 1 + 5.2 ], [CLRS01, p. 405-9] (alternatively [CLR90, p. 356-60]). For Feb. 27 1.60

Feb. 27 10.00-12.00; 13.00-16.00 Index structures, B-trees (slides). GUW 13.0-13.3, [Pagh03, sec. 3.0-3.2] For March 6 1.60

Mar. 6 10.00-12.30 Hash indexes (slides). GUW 13.4, [Pagh03, sec. 4]. For March 13 1.60

Mar. 13 10.00-12.00; 13.00-16.00 Implementation of relational operations (slides, more slides). GUW 15.0-15.8 and GUW 16.2-16.3. For March 20 1.60

Mar. 20 10.00-12.00; 13.00-16.00 Implementation of relational operations II (slides). Dealing with system failures (slides). GUW 16.4-16.7, GUW 11.6, and GUW 17 For March 27 1.60

Mar. 27 11.00-12.00; 13.00-16.00 XML in databases (slides).
Guest lecturer: Albrecht Schmidt. GUW 4.6-4.7 (and slides). For April 3 1.60

Apr. 3 10.00-12.00; 13.00-16.00 Text indexing (slides), the Google search engine (slides). [KärkkäinenRao03, sec. 7.1-7.4], and [BrinPage98, sec. 1, 2, 4.2] (not curriculum) For April 10 1.60

Apr. 10 13.00-16.00 External memory geometric data structures (slides photocopied).
Guest lecturer: Joachim Gudmundsson. [Arge01, sec. 1, 2 (only "persistent B-trees"), 3-4 (only static versions, and logarithmic method), 6 (not log. query struct.), 9], [dBGHO03, sec. 1-3.1] For April 24 1.60

Apr. 17 No lecture. Easter.

Apr. 24 10.00-12.00; 13.00-16.00 Cache-oblivious algorithms (slides). [Kumar03, 9.1+2+3+6+7+8] 1.60

May 1 10.00-12.00; 13.00-16.00 Data stream algorithms (p. 2-14, 26-30, and 36-39 of slides1, p. 4-17 of slides2, p. 9-14 and 20 of slides3). Course summary and evaluation. [BabcockEtAl02, 1+2+4+5.3+6] 1.60

June 10 10.00-12.00; Question session 1.09

June 12 9.00-13.00 Exam. 0.10

Literature:

GUW = Database systems - The complete book by Garcia-Molina, Ullman, and Widom.
[Arge01] = Lars Arge. External memory data structures.
[[BabcockEtAl02] = Brian Babcock et al. Models and Issues in Data Stream Systems.
[BrinPage98] = Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine.
[CLR90] = Cormen, Leiserson, and Rivest. Introduction to Algorithms.
[CLRS01] = Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition.
[dBGHO03] = M. de Berg, J. Gudmundsson, M. Hammar, and M. Overmars. On R-trees with low query complexity.
[KärkkäinenRao03] = Juha KärkkäinenRao and S. Srinivasa Rao. Full-text Indexes in External Memory. (bibliography.)
[Kumar03] = Piyush Kumar. Cache Oblivious Algorithms. (bibliography.)
[MaheshwariZeh03] = Anil Maheshwari and Norbert Zeh. A Survey of Techniques for Designing I/O-Efficient Algorithms. (bibliography.)
[Pagh03] = Rasmus Pagh. Basic External Memory Data Structures. (bibliography.)
[Sanders03] = Peter Sanders. Memory Hierarchies - Models and Lower bounds. (bibliography.)

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.

Topics

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.

Among other things, the following topics will be treated:

External memory algorithms
Index structures
Implementation of relational operations
Query optimization
Error recovery
XML queries
GIS (geographic information systems)
Text indexing

Literature

Database Systems: The Complete Book by Hector Garcia-Molina, Jeff Ullman, and Jennifer Widom, 2002. Copies for the course are on sale from Samfundslitteratur. 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:

analyze and choose among main indexing technologies
understand and perform query optimization
explain how to do error recovery
analyze and apply external memory algorithms

Prerequisites

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 database systems (DBS).

Course format

Teaching consists of lectures and exercises in English.

Mandatory hand-ins

There will be 8-11 mandatory hand-ins during the course. 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 0 to 10, and students must achieve 60% of the maximum possible point sum to qualify for the exam. Late hand-ins will under normal circumstances receive 0 points. It is allowed to discuss assignments with other students, but the solutions must be prepared individually. 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.

Examination

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

Lecturers

Rasmus Pagh
Office: 1.09
Phone: 38 16 89 34
Email: pagh@it-c.dk

Anna Östlin
Office: 1.09
Phone: 38 16 88 21
Email: annao@it-c.dk

Date	Time	Subject	Literature	Exercises / hand-ins	Place
Feb. 6	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.)	For Feb. 13	1.60
Feb. 13	10.00-12.00; 13.00-16.00	Data storage devices, I/O model (slides).	GUW 11.1-11.5; Handouts: [Sanders03, 1.3-1.5], [MaheshwariZeh03, 3.1-3.2].	For Feb. 20	1.60
Feb. 20	10.00-12.00; 13.00-16.00	Representing data elements (slides).	GUW 12, [Pagh03, sec. 1 + 5.2 ], [CLRS01, p. 405-9] (alternatively [CLR90, p. 356-60]).	For Feb. 27	1.60
Feb. 27	10.00-12.00; 13.00-16.00	Index structures, B-trees (slides).	GUW 13.0-13.3, [Pagh03, sec. 3.0-3.2]	For March 6	1.60
Mar. 6	10.00-12.30	Hash indexes (slides).	GUW 13.4, [Pagh03, sec. 4].	For March 13	1.60
Mar. 13	10.00-12.00; 13.00-16.00	Implementation of relational operations (slides, more slides).	GUW 15.0-15.8 and GUW 16.2-16.3.	For March 20	1.60
Mar. 20	10.00-12.00; 13.00-16.00	Implementation of relational operations II (slides). Dealing with system failures (slides).	GUW 16.4-16.7, GUW 11.6, and GUW 17	For March 27	1.60
Mar. 27	11.00-12.00; 13.00-16.00	XML in databases (slides). Guest lecturer: Albrecht Schmidt.	GUW 4.6-4.7 (and slides).	For April 3	1.60
Apr. 3	10.00-12.00; 13.00-16.00	Text indexing (slides), the Google search engine (slides).	[KärkkäinenRao03, sec. 7.1-7.4], and [BrinPage98, sec. 1, 2, 4.2] (not curriculum)	For April 10	1.60
Apr. 10	13.00-16.00	External memory geometric data structures (slides photocopied). Guest lecturer: Joachim Gudmundsson.	[Arge01, sec. 1, 2 (only "persistent B-trees"), 3-4 (only static versions, and logarithmic method), 6 (not log. query struct.), 9], [dBGHO03, sec. 1-3.1]	For April 24	1.60
Apr. 17		No lecture. Easter.
Apr. 24	10.00-12.00; 13.00-16.00	Cache-oblivious algorithms (slides).	[Kumar03, 9.1+2+3+6+7+8]		1.60
May 1	10.00-12.00; 13.00-16.00	Data stream algorithms (p. 2-14, 26-30, and 36-39 of slides1, p. 4-17 of slides2, p. 9-14 and 20 of slides3). Course summary and evaluation.	[BabcockEtAl02, 1+2+4+5.3+6]		1.60
June 10	10.00-12.00;	Question session			1.09
June 12	9.00-13.00	Exam.			0.10