CSE 562: Database Systems

Spring 2010

Newsgroup

Please check the newsgroup daily for important announcements and clarifications:

• sunyab.cse.562

Staff

• Instructor: Dr. Michalis Petropoulos
• Teaching Assistant: Xinglei Zhu

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.

Text

• Database Systems: The Complete Book (2nd Edition)
  by Hector Garcia-Molina, Jeff Ullman, and Jennifer Widom

A list of recommended books goes as follows:

• Database System Concepts (5th Edition)
  by Avi Silberschatz, Henry F. Korth and S. Sudarshan
• Database Management Systems
  by Raghu Ramakrishnan and Johannes Gehrke
• Foundations of Databases
  by Serge Abiteboul, Richard Hull, Victor Vianu

Prerequisites

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

Schedule

The following is a tentative schedule of lectures.

Assignments

• Teams
• Assignment 1
• Due Sunday, February 7th @ 11:59pm
• Assignment 2
• Due Thursday, April 22nd @ 1:50pm (in class)
• Solution

Project

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
  • Due Sunday, February 28th @ 11:59pm
  • Code for the storage system and parser components
  • An example union query and the result of its execution
  • An example 2-way join query and the result of its execution
  • The JavaCC Parser Generator web page
• 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.