D64- Advanced Database Systems
Course Information

Course Content

This class focuses on the implementation of database management systems (DBMSs). We will cover the following topics (plus some other goodies thrown in as well):

• File layout - How can the DBMS map a table onto a file? The simplest approach is to create a fixed size record for each table and map every row into one of these records. The problem is that not all rows need the maximum size, either because some columns are NULL or because they contain varying length data, such as VARCHARs. Also, we'd like any scheme to allow us to add or drop columns without immediately reorganizing the table. This course will present approaches that support both variable length rows and schema modifications.
• Indexing - Most queries only return information about a subset of the rows in a table. Thus we need other ways to find rows of interest besides sequential scans. In-memory indexing techniques, such as binary search trees, are not appropriate since they are very deep and each "pointer" traversal may cost a full disk access. Thus we need other indexing techniques that take traversal costs and the effects of disk page boundaries into consideration.
• Query optimization and processing - How does one go from a declarative SQL query to a plan to evaluate the query. How should tables be joined and in what order. How should the DBMS decide which indexes to use? We'll spend a good portion of the class on this fascinating subject.
• Concurrency control - How can the DBMS allow the greatest number of users to access the database concurrently while still protecting each one from interfering with each other?
• Disaster recovery - Unlike most software systems (like web browsers!), after a machine reboots from a crash, after a software crash, or after a media failure, customers still expect their data to be in the database. This course will cover the mechanisms that can be used to provide these guarantees.
• Transaction management - Transactions are extremely useful from an application programmers perspective - allowing him/her to concentrate on their application logic without worrying about concurrency problems, disasters, or even about cleaning up after themselves. How do DBMSs perform this miracle? Much of the gritty detail will be provived in this course.
• Implementing advanced features such as triggers - Finally, we'll talk a bit about how some of the newer and more advanced features of DBMSs, such as triggers, are implemented. Other possible topics include: extensibility, large object support, and tools for physical database design.

This course is aimed at database system implementation. It does not cover the use of database management systems from the point of view of applications - this topic is covered in C39.

Don't be scared by the big "D" sitting in front of the course number - this course is suitable for advanded undergraduates or beginning graduate students with no knowledge of DBMS implementation.

Time and Place

Monday and Wednesday 4:00-5:30, ILS Classroom.

Course Personnel

Instructor	Brad Adelberg
	Office: 1890 Maple, Room 350
	Phone: 467-2129
	Office hours: By appointment

Prerequisites

CS C11	Data Structures and Data Management (Required)
CS C10	Mathematical Foundations of Computer Science (Recommended)
CS C39	Introduction to Database Systems (Required, or suitable other experience)

Course Text

The primary reading material for the course will be

• Database System Implementation,
  H. Garcia-Molina, J. Ullman, and J. Widom.

Assignments

There will be approximately seven written assignments. There will also be one or two programming assignments.

• Problem Set 1 (due 1/24/00) - Solutions
• Programming Assignment 1 (due 2/16/00)
• Problem Set 2 (due 1/31/00) - Solutions
• Problem Set 3 (due 2/9/00) - Solutions
• Problem Set 4 (due 3/1/00) - Solutions
• Programming Assignment 2 (due 3/10/00)

Examinations

There will be one midterm exam and a final examination. The final is on March 17 at 3pm.

Grading

Assignments	35%
Midterm exam	25%
Final exam	40%

Handouts

All handouts for this course will be distributed via the web.

1. Sample Midterm
2. Sample Midterm Solutions
3. Final Study Questions
4. Final Study Questions Solutions
5. Partial Midterm Solutions (Word)

Tentative Syllabus

Week	Date	Topic	Reading in Text
1	Jan. 5	No class
2	Jan. 10	Intro. to course and subject	1.1-1.6
	Jan. 12	Hardware	2
3	Jan. 17	File and system structure	3
	Jan. 19	File and system structure	3
4	Jan. 24,26	Indexing and hashing	4
5	Jan. 31 Feb 2	Indexing and hashing	4
6	Feb. 7	Query Processing	6
	Feb. 9	Query Processing	7
7	Feb. 14	Midterm exam
	Feb. 16	Disaster recovery	8
8	Feb. 21	Disaster recovery	8
	Feb. 23	Concurrency control	9
9	Feb. 28	Concurrency control	10.1,10.7
	Mar. 1	Physical Database Design
10	Mar. 6	Parallel and Distributed Databases	10.4-10.6
	Mar. 8	TBD
11	Mar. 17	Final exam