CSE-4411A
Database Management Systems

York University
Fall 2011
Syllabus
Instructor: Parke Godfrey
Office: CS&E Building #2050
Office Hours: 3-5pm Tuesdays
& by appointment
Ph#: 416-736-2100 x66671
e-mail: godfrey@cse.yorku.ca
Term: Fall 2010
Time: Mo&We 4:00-5:30pm
Place: CB #122
Textbook: Raghu Ramakrishnan & Johannes Gehrke
Database Management Systems
Third Edition, 2003
WCB/McGraw Hill.
ISBN: 0-07-246563-8
URL: http://www.cs.wisc.edu/~dbbook
Class URL: http://www.cse.yorku.ca/course/4411/
  The Course
Description (from the academic calendar)

This course is the second course in database management. It introduces concepts, approaches, and techniques required for the design and implementation of database management systems.

Course Objectives and Content

In this course, we go "under the hood" to learn how a relational database management system is built. Students will learn the issues involved in designing efficient database systems, and the strategies, data-structures, and algorithms used in the implementation of such systems.

The course is designed in three parts: the physical database, the query processor, and database management. Specific contents include the following.

I. The Physical Database
  • file organizations
  • indexes
    • tree-structured indexes
    • hash-based indexes
  • external sorting
II. The Query Processor
  • evaluation of relational operators
    • selection
    • projection
    • joins (the many ways)
    • set operations
    • aggregate operations
  • relational query optimization
    • query evaluation plans
    • translating SQL queries into algebra
    • considering alternative plans
    • cost models and estimations
III. Database Management
  • transaction management
  • concurrency control
  • crash recovery
  • physical database design and tuning

The content of CSE-3421 is assumed.

Required Textbook / Reading

Course materials will be primarily drawn from the assigned readings in the assigned textbook. Some auxiliary readings may be assigned during the course.

 
  Grading Criteria / Course Requirements
Components
  Percentage When
Test #1 20% 19 October
Test #2 20% 16 November
Final Exam 35% ? December
Projects 2 × 7½% two, due through the semester
Assignments 3 × 3 1/3% three, due through the semester

The grading policy is standard. Collaboration and discussion on the assignments is fine. Note however, that unless you work through the exercises yourself, you will not get much benefit from them.

York University's rules for academic honesty and plagiarism are always in effect. ( See below.) Discussion is fine on the assignments and projects. However, collaboration is not. The work must be your own.

Course Projects & Assignments

There will be two projects, in sum worth 10% of the final grade. Students will be required to design and implement some of the key algorithms and data-structures for a relational database system. Your code will be in Java.

The projects will probably consist as follows. We may use the Minibase system. (See appendix B in the textbook.) The Minibase system provides a code base for a simple database system. Your code will augment the Minibase code. The good news is that you do not have to do everything from scratch; the bad news is that you will have to understand the Minibase code to use it.

Late projects will not be accepted, unless prior approval has been obtained with good reason.

There will be three assignment sets through the semester. It is important to put effort into the assignments for understanding of the materials, and because similar problems will appear on the exams. Solutions to assignment sets will be made available after the turn-in dates for study purposes.

All written work for the assignments need not be typed; but if you hand-write them, you must write legibly for credit. Late assignment sets will not be accepted, unless prior approval has been obtained with good reason.

 
  Calendar

The following schedule is tentative, which means we may deviate from it some during the term. We may need to slow down, or speed up, on certain topics, depending on how things go. As well, we might not get to everything on the schedule, though we shall try. It is your responsibility to keep track of due-dates and what we are covering.

Wk# Days Topic Reading Due
#1 We 7 Sep You want me to code what?! Introduction    
I. The Physical Database
  Mo 12 Sep Where can I keep this? Storage & the DSM Ch 8  
#2 We 14 Sep Paging Dr. Codd... Ch 9  
  Mo 19 Sep The Buffer Pool & Formats    
#3 We 21 Sep Disks & Files    
  Mo 26 Sep Yo. Trees are for the birds. Ch 10  
#4 We 28 Sept Tree-structured Indexes    
  Mo 3 Oct Hash-based Indexes Ch 11 A#1
Reading Week: 8-14 Oct
#5 We 5 Oct Take it outside! Ch 13  
  Mo 17 Oct External Sorting   P#1
#6 We 19 Oct Test #1 Arghhh!  
II. The Query Processor
  Mo 24 Oct You ought to see some of my relations! Ch 12  
#7 We 26 Oct Evaluation of The Relational Operators (overview)  
  Mo 31 Oct I once joined these two tables. Ch 14  
#8 We 2 Nov Relational Query Optimization: Algorithms    
  Mo 7 Nov Listen up. Here's the plan... Ch 15 A#2
#9 We 9 Nov Relational Query Optimization: Plans    
  Mo 14 Nov      
#10 We 16 Nov Test #2 Not again!  
III. Database Management
  Mo 21 Nov One at a time, please. Ch 16  
#11 We 23 Nov Transaction Management    
  Mo 28 Nov & Concurrency Control Ch 17 P#2
#12 We 30 Nov Crash & burn. Crash Recovery Ch 18  
  Mo 5 Dec Wrap-up   A#3
final exam period (8-22 Dec)
#13 ? Dec Final Exam

A#: Assignment '#' due.
P#: Project '#' due.

Weeks start on a Wednesday and run through the next Tuesday, just to stay in synch with the fall-term schedule.

Assignments and projects are due on the Tuesday at the end of the "week" indicated above. For example, Assignment #2 due in Week #8 (with lectures on Wednesday 2 November and Monday 7 November) would be due on Tuesday 8 November. Specific details for turning in assignments and projects will be set. For your assignment solutions, they should be dropped off in the class's dropbox next to #1003, the main office for CS&E, in the CS&E building. For your project solutions, they should be submitted online by the submit command on a PRISM machine by 11:59pm.

 
  Policies
Exams & Attendance

Exams must be taken when scheduled unless the student has a medical documentation or can demonstrate special circumstances for a need for a rescheduled exam. The student must obtain approval from the instructor.

Class attendance is important as the student will have an opportunity to ask for clarification of course and text material. There will be problem solving sessions during class period so that students gain experience applying the theory in practice. However, attendance itself is not part of the grade or otherwise enforced.

Academic Integrity / Honesty / Plagiarism

The Department of Computer Science (& Engineering) Academic Honesty Guidelines are in effect for this course, as, indeed, they are for any CS&E course.

Plagiarism is defined as taking the language, ideas, or thoughts of another, and representing them as your own. If you use someone else's ideas, cite them. If you use someone else's words, clearly mark them as a quotation. Note that plagiarism includes using another's computer programs or pieces of a program. All noted instances of plagiarism will be reported.

These policies are not intended to keep students from working with other students. One can learn much working with others, so this is to be encouraged. Should you encounter any situations for which you are uncertain whether the collaboration is permitted or not, please ask.