University at Buffalo, The State University of New York


CSE 562: Database Systems

Spring 2010


Please check the newsgroup daily for important announcements and clarifications:

  • sunyab.cse.562


Course Description

The goal of this course is to introduce the students to the following fundamental database system implementation issues: algebraic query languages, database file organization, indexing, query compilation, query execution, query optimization (both rule-based and cost-based), as well as other advanced topics on recovery, concurrency and other transaction management issues. Students acquire hands-on experience by implementing the internal components of a relational database engine. The course will cover Chapters 13 through 20 of the textbook, and selectively parts of other chapters.


A list of recommended books goes as follows:


Solid background in algorithms and data structures, database query languages (SQL) and schema design. Chapters 2 through 8 of the textbook should have been covered in an undergraduate (or equivalent) course, otherwise you won't be able to follow the material in this course. Significant programming experience in Java or C++ is required for the project.

Grade Computation

  • Homework Assignments: 15%
  • Midterm: 20%
  • Final: 30%
  • Project: 35%
  • Grades


. Mon Tue Wed Thu Fri
Lectures . 12:30 - 1:50pm
220 Natural Sciences Complex
. 12:30 - 1:50pm
220 Natural Sciences Complex
Recitations 9:00 - 9:50am
337 Bell Hall
. 10:00 - 10:50am
214 Norton Hall
. .
Instructor's Office Hours . 2:00 - 3:00pm
210 Bell Hall
. 2:00 - 3:00pm
210 Bell Hall
TA's Office Hours . . 12:00 - 2:00pm
329 Bell Hall
. .

The following is a tentative schedule of lectures.

Week Tuesday
Topic of
1 01/11 Introduction
Relational Algebra & SQL
No Recitations
No Office Hours
2 01/18 Relational Algebra & SQL More Relational Model
3 01/25 Database Design
SQL & PostgreSQL
4 02/01 Record and Block Organization
Indexing & B+ Trees
5 02/08 Project Phase 1 Discussion Indexing & B+ Trees Project Phase 1
6 02/15 Hashing & Other Indexes
Query Processing:
Project Phase 1
7 02/22 Query Processing:
Algebraic Optimization
Query Processing:
Cost Analysis
8 03/01 Query Processing:
Physical Operators
Midterm Indexing
9 03/08 No Lectures (Spring Recess) No Recitations
10 03/15 Query Processing:
Physical Operators
Project Phase 2 Discussion Query Processing
11 03/22 Midterm Discussion Query Processing:
Plan Enumeration & Selection
Project Phase 2
12 03/29 Recovery
Recovery Query Processing
13 04/05 Concurrency Control
14 04/12 Concurrency Control More on Transaction Processing
Concurrency Control
15 04/19 Final Preparation Databases as a Service (DaaS) Transaction Processing
Final Thursday, April 29 2010
03:30 PM - 06:30 PM
Knox 109



You can work in teams of 2. Please email the instructor your name and the name of your teammate asap. You can use the newsgroup to find a teammate. Also, please read the rules and policies below and be aware that anti-plagiarism software will be used while grading your submissions.

  • Teams
  • Phase 1 Specification
  • Phase 2 Specification
    • Due Sunday, April 25th @ 11:59pm
    • Reference implementation of Phase 1
    • The JavaDocs for the reference implementation can be found under the doc directory in the above .zip file

Reading List

From Database Systems: The Complete Book (Second Edition) by Garcia-Molina, Ullman, and Widom:

  • Chapter 2 The Relational Model of Data (Only Section 2.4)
  • Chapter 4 High-Level Database Models (Only Sections 4.1, 4.2, 4.3, 4.5.1, 4.5.2, 4.5.3 and 4.6)
  • Chapter 5 Algebraic and Logical Query Languages (Only Sections 5.1 and 5.2)
  • Chapter 6 The Database Language SQL (Except Section 6.6)
  • Chapter 7 Constraints and Triggers (Except Section 7.1.3)
  • Chapter 10 Advanced Topics in Relational Databases (Only Section 10.2)
  • Chapter 13 Secondary Storage Management (Except Sections 13.4, 13.6.3, 13.6.4 and 13.6.5)
  • Chapter 14 Index Structures (Except Sections 14.6.6, 14.6.7, 14.6.8 and 14.7)

After Midterm

  • Chapter 15 Query Execution (Except Sections 15.7, 15.8 and any material on duplicate elimination, grouping and aggregation)
  • Chapter 16 The Query Compiler (Except Section 16.7 and any material on duplicate elimination, grouping and aggregation)
  • Chapter 17 Coping With System Failures
  • Chapter 18 Concurrency Control (Except Section 18.8)
  • Chapter 19 More About Transaction Management (Except Sections 19.1.6, 19.1.7, 19.1.8, and 19.3)

Rules & Policies

Zero tolerance on plagiarism/cheating: consult the University Code of Conduct for details on consequences of academic misconduct, and see also the academic integrity policy of the CSE department.

Project Rules

For coding assignments, if you use a piece of code which you borrowed from elsewhere and therefore did not write yourself, make sure you let the instructor and a TA know before you start using it.

Make-Up Policy

The request should be made sufficiently in advance of the test, for valid reasons. The make-up should be scheduled before the next class.

Late Submission Policy

The submissions are due at midnight on the due date. Submissions after the deadline but less than 24 hours late will be accepted but penalized 10%, and submissions more than 24 hours but less than 48 hours late will be penalized 25%. No submissions will be accepted more than 48 hours late. Exceptions will be made only for medical reasons. Questions about the grading have to be raised with a TA within a week after the graded assignment has been returned.

Grading Policies

Write clear arguments. Be neat and precise. Getting the right answer may not be enough. The derivation and quality of writing counts! Don't write many different things in hope that you'll get the points if one of them is the right one. Indeed, you will lose points if you follow such a policy.