Database Management Systems
York University
Fall 2008

Semester: Fall 2008
Course/Sect#: CSE-4411
Time: Mon 1-2:20pm
Wed 1-2:20pm
Location: BC 202
Instructor: Jarek Gryz
Office: 2049 CSB
Office Hours: Mon 3-5PM
or by appointment
Ph#: 416-736-2100 x70150
Class URL:

Books / Reading

Required Textbook / Reading

Database Management Systems.
Third Edition, 2003.
Raghu Ramakrishnan and Johannes Gehrke
WCB/McGraw Hill.
ISBN: 0-07-232206-3

We will cover (at least) chapters: 8, 9, 10, 11, 12, 13, 14, 15, 22, 25, 26 from the textbook.

Additional lecture slides and student presentations can be found here. (Note, they are only accessible from York CS machines).

Presentation Schedule (subject to change)

Date Topic Presenters
Feb 2 Cardinality estimation using sample views with quality assurance Jenna Lau
Bitmap Indexes Chao Tan
Feb 4 Accurate Estimation of the Number of Tuples Satisfying a Condition Yinchun Zhang
Plan Optimization Alexandra Teslya
Feb 9 Recursive queries and magic sets Víctor González Amarillo
Efficient Detection of Empty-Result Queries Nikolay Yakovets
Consistently Estimating the Selectivity of Conjuncts of Predicates Vladimir Perisic
Feb 11 Practical Selectivity Estimation through Adaptive Sampling Chuntang Li
Automated Statistics Collection in DB2 Ioulia Vaxenguisser
Feb 18 Dynamic Query Evaluation Afshin Bayati Kermanshahi


Homework Assignments

HW1: Due Sep 22 in class: 8.10 (b,c,d), 9.6, 10.2 Solutions

HW2: Due Oct 6 in class: 10.8, 11.6, 11.10, 13.4-2(a)(e) Solutions

HW3: Due Oct 20 in class: 14.6, 15.2(5), 15.4(2) Solutions

HW4: Due Feb 4 in class: 22.4 (1, 4, 6), 22.8 (a, b, g), 26.6 Solutions

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. Additionally, we shall also explore some advanced topics in databases.

The course is designed in three parts: the physical database, query processing, and advanced topics. Specific contents include the following.

I. The Physical Database
  • file organizations
  • indexes
    • tree-structured indexing
    • hash-based indexes
  • external sorting
II. Query Processing
  • 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
  • physical database design and tuning
III. Advanced Topics
  • deductive and active databases
  • object-relational and object-oriented databases
  • decision support systems
  • cutting-edge (research) topics (to be determined)
    • semantic query optimization
    • mediation and heterogeneous databases
    • cooperative query answering
    • databases and the web
    • ...

Grading Criteria / Course Requirements

Percentage When
Midterm Exam 30% Oct 20 in class
Final Exam 40% Feb 22, 3:30 PM in CB 120
Presentation 20% in the second half of the semester
Homework Assignments 10% 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 always remain in effect.

Homework Assignments & Presentations

There will be assignment sets through the semester. You will get a check-mark for turning in each assignment. The assignments, however, will not be graded. It is important to put effort into the assignments, however, 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 be accepted with 25% credit reduction for each day overdue.

Choose a topic for your presentation or report from the provided list. The class presentation should be prepared as a 30 minute presentation to be made to the class. Thus the audience for the presentation is the rest of the class. The objective is to introduce them to the topic that you are covering (for example, object-oriented databases) so they have an understanding of what the subject is about. So a general overview is appropriate. For the presentation, do not go into any of the details of the paper(s). These details would be too in-depth for the class presentation.


Exams & Attendance

Exams must be taken when scheduled. If a student misses the midterm and has a medical documentation or can demonstrate special circumstances, his/her final exam will count for 70% of the total grade.

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 each class period so that students gain experience applying the theory in practice.

Academic Integrity / Honesty / Plagiarism

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 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 other, so this is to be encouraged. Should you encounter any situations for which you are uncertain whether such collaboration is permitted or not, please ask.