CSE 562: Database Systems

Fall 2007

Newsgroup

Please check the newsgroup FREQUENTLY for important announcements and clarifications:

• sunyab.cse.562

Staff

• Instructor: Dr. Michalis Petropoulos
• Teaching Assistant 1: Denis Mindolin
• Teaching Assistant 2: Murtuza Jadliwala

Course Description

The goal of this course is to introduce the students to the following fundamental data management issues: database design, data models, integrity constraints, query languages, database file organization, indexing, query processing and optimization, as well as other advanced topics. Students will also acquire a hands-on experience by implementing a subset of the internal components of a relational database engine.

Schedule

The following is a tentative schedule of lectures. Changes will be posted on the newsgroup.

Prerequisites

Solid background in algorithms and data structures. Significant programming experience in Java or C++. Basic knowledge of database query languages (SQL) and schema design.

Text

• Database System Concepts (5th Edition)
  by Avi Silberschatz, Henry F. Korth and S. Sudarshan

A list of recommended books goes as follows:

• Database Systems: The Complete Book
  by Hector Garcia-Molina, Jeff Ullman, and Jennifer Widom
• Database Management Systems
  by Raghu Ramakrishnan and Johannes Gehrke
• Foundations of Databases
  by Serge Abiteboul, Richard Hull, Victor Vianu

Grade Computation

• Homework Assignments: 10% (set of 2, 5% each)
• Midterm: 20%
• Final: 30%
• Project: 40% (Phase 1 10%, Phase 2 15%, Phase 3 15%)
• Grades

Project

You can work in teams of 2. Please email me 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 Thursday, October 4th @ 2:00pm
  • Code for the storage system and parser components
  • The JavaCC Parser Generator web page
• Phase 2 Specification
  • Due Saturday, November 3rd @ 2:00pm
  • Reference implementation of Phase 1
  • JavaDoc for the reference implementation
    (can also be found in the above .zip file under the doc directory)
• Phase 3 Specification (Updated on Monday, December 3rd @ 5:15pm)
  • Due Sunday, December 9th @ 11:59pm
  • Reference implementation of Phase 2 (Updated on Thursday, November 29th @ 5:00pm)
  • The JavaDoc for the reference implementation can be found in the above .zip file under the doc directory)
  • Source code of the new Storage System for teams using their own implementation
  • New dataset with leading zeros (Added on Thursday, December 6th @ 6:45pm)

Assignments

• Homework 1
• Due Thursday, September 27th @ 5:00pm.
• Solutions
• Homework 2
• Due Tuesday, November 20th @ 5:00pm.
• Solutions

Practice Problems

• Textbook Practice Problems
• Practice Problem Set 1
• Practice Problem Set 2
• Practice Problem Set 3
• Practice Problem Set 4
• Practice Problem Set 5
• Practice Problem Set 6
• Practice Problem Set 7

Reading List

• Chapter 1 Introduction
• Chapter 2 Relational Data Model and Algebra
• Chapter 3 (Sections 3.1 up to 3.10) SQL and Views
• Chapter 4 (Except Section 4.3) Integrity Constraints, Relational Database Programming, Recursion and Other Extensions
• Chapter 11 (Focus on Sections 11.6, 11.7 and 11.8) Storage and File Structure
• Chapter 12 (Except Sections 12.4 and 12.5) Indexing and Hashing

After Midterm


• Chapter 15 (Sections 15.1, 15.2, 15.3, 15.4, 15.5 and 15.6) Query Execution
  From Database Systems: The Complete Book by Garcia-Molina, Ullman, and Widom
• Chapter 16 (Sections 16.2, 16.3, 16.4, 16.5 and 16.6) The Query Compiler
  From Database Systems: The Complete Book by Garcia-Molina, Ullman, and Widom
• Notes on merge sort from Chapter 11
  From Database Systems: The Complete Book by Garcia-Molina, Ullman, and Widom
• A few pages on semantic optimization by using tableaux from Foundations of Databases book
• Chapter 15 Transactions
• Chapter 16 (Sections 16.1.1, 16.1.2, 16.1.3 and 16.6) Concurrency Control
• Chapter 17 (Sections 17.1 up to 17.7) Recovery System

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 the TAs 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. No make-ups are available for homework assignments.

Late Submission Policy

The submissions are due at midnight on the due date. No late submissions are accepted. Exceptions will be made only for medical reasons. Questions about the grading have to be raised with the 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.