Advanced database technology, Spring 2006

[News] [Schedule] [Course description]

News

Exam reading list.

In the lecture on March 13 there was some confusion about the last question on the exercise sheet. Here is a (hopefully) clear explanation: Transaction 1 first reads each data element of "Seats". Assuming that the transaction that last wrote to Seats committed long ago, this is fine. (The fact that Transaction 2 also read "Seats" does not matter.) Also, Transaction 1 may write to the data elements of "Seats" without problem (the read timestamp is smaller). However, when Transaction 2 next tries to read or write the data element(s) of "Seats" that were updated (assuming that an update did occur), in statement 4 or 6, it is rolled back beacuse it read something that was written by a "future" transaction.

To provide access to on-line literature from outside ITU, we have put copies in a password protected directory Intranet. The user name and password will be sent by e-mail to the participants.

You may get an impression of what is required of you in the course by looking at previous exams. Here are the exams of June 2003, June 2004, and June 2005.

Schedule

The schedule is preliminary. It will be updated during the course. Slide sets marked "2005" are those from the latest edition of the course, and are subject to change.

Date	Time	Subject	Literature	Exercises / hand-ins	Place
Jan. 30	9.00-12.00	RP: Introduction. Recap of database background (slides). Overview of lectures (slides).	(Based on selected sections of the first part of GUW - not curriculum.)	hand-out	3A 14
Feb. 6	10.00-15.00	RP: Data storage devices, I/O model (slides).	GUW 11.1-11.5; [Sanders03, 1.3-1.5], [MaheshwariZeh03, 3.1-3.2].	hand-out	3A 14
Feb. 13	10.00-15.00	SR: Representing data elements (slides).	GUW 12, 13.0-2, [Pagh03, sec. 1 ], [CLRS01, p. 405-9] (alternatively [CLR90, p. 356-60]).	hand-out	3A 14
Feb. 20	10.00-15.00	SR: Index structures. (slides, slides for paper).	GUW 13.3-13.4, [Pagh03, sec. 2.3.0, 2.3.1, 2.3.2, 2.4], [BrodalFagerberg03, sec. 1 and 3.4]	hand-out	3A 14
Feb. 27	10.00-15.00	SR: Implementation of relational operations I. (slides).	GUW 15.0-15.8	hand-out	3A 14
March 6	10.00-15.00	RP: Implementation of relational operations II (slides, more slides)	GUW 16.2-7, [AGMS99 sec. 1, 2, 4, 5, except proofs]	hand-out	3A 14
March 13	10.00-15.00	RP: Concurrency control (slides).	GUW 18.0-8, 19.3, [RG 16.6.3]	hand-out	3A 14
March 20	10.00-15.00	SR: Geometric index structures (slides).	GUW 14.0-14.1, (14.2-14.3 recommended reading), [Arge01, sec. 1, 2.1 (persistent B-trees), 3-4 (static versions only), 4.1, 9]	hand-out	3A 14
March 27	10.00-15.00	SR: Text indexing (slides)	[KarkkainenRao03, sec. 7.1-7.4]		3A 14
April 3	10.00-15.00	RP: Data mining (slides 1, 2, 3, 4, 5).	GUW 20.6, [AgrawalSrikant94, all except 3.3], [Ullman00], [MehtaAgrawalRissanen96], and [BrinPage98, sec. 1, 2, 4.2]	hand-out	3A 14
April 10	10.00-15.00	SR: Dealing with system failures (slides). Media failures (slides).	GUW 17.0, 17.1, 17.2.4+5, 17.4, 11.6, 11.7.0-3.		3A 14
April 17		Easter
April 24	10.00-14.00;	RP: ITU research in databases (slides). Course summary (slides). Presentation of previous exam problems.	Background literature (not curriculum): [PP06 sec. 1-3], [PPR05 sec. 1-2], [FPP06 sec. 1-2], [PPT04 sec. 1-3]		3A 14
June 8	10.00-12.00	Q&A session - room 4A60			tba.
June 12	9.00-13.00	Exam. Room 2A 12.			tba.

Literature:

• GUW = Database systems - The complete book by Garcia-Molina, Ullman, and Widom.
• [MehtaAgrawalRissanen96] = M Mehta, R Agrawal, and J Rissanen. SLIQ: A fast scalable classifier for data mining. Proceedings of EDBT '96.
• [AgrawalSrikant94] = R Agrawal, R Srikant. Fast Algorithms for Mining Association Rules. Proceedings of the 20th International Conference on Very Large Data Bases, 1994.
• [AGMS99] = N Alon, P Gibbons, Y Matias, M Szegedy. Tracking join and self-join sizes in limited storage. PODS '99.
• [Arge01] = Lars Arge. External memory data structures.
• [BrinPage98] = Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine.
• [BrodalFagerberg03] = Gerth Brodal and Rolf Fagerberg. Lower Bounds for External Memory Dictionaries
• [CLR90] = Cormen, Leiserson, and Rivest. Introduction to Algorithms.
• [CLRS01] = Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition.
• [KarkkainenRao03] = Juha Karkkainen and S. Srinivasa Rao. Full-text Indexes in External Memory. (bibliography.)
• [MaheshwariZeh03] = Anil Maheshwari and Norbert Zeh. A Survey of Techniques for Designing I/O-Efficient Algorithms.
• [RG] = Ramakrishnan and Gehrke. Database Management Systems, 3rd ed.
• [Sanders03] = Peter Sanders. Memory Hierarchies - Models and Lower bounds. (bibliography.)
• [Pagh03] = Rasmus Pagh. Basic External Memory Data Structures. (bibliography.)
• [Ullman00] = Jeff Ullman. Association rules and frequent itemsets. Note for CS345, Stanford University, 2000.

Literature

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.

Supplementary literature: Database Tuning. Principles, Experiments, and Troubleshooting Techniques, by Dennis Shasha and Philippe Bonnet. This book is a more pragmatic introduction to database performance. We will be using excerpts from the book as starting points of discussions, but it is not strictly necessary to buy the book.

Manning of course