Advanced Database Systems
EECS 6421
Winter 2017
York University

Semester: Winter 2017
Course/Sect#: EECS 6421
Time: Tu, Th 2:30PM
Location: BC 228
Instructor: Jarek Gryz
Office: 2049 CSB
Office Hours: by appointment
Ph#: 416-736-2100 x70150
e-mail: [my first name]

Final exam is available. It is due (by email) on April 8 at 9AM.


Welcome to the Advanced Database Systems course, CSE-6421. Materials, instructions, and notices for the course will accumulate here over the semester. The lecture slides and student presentations are now available.

Presentation Schedule (subject to change)

Date Topic Presenters




The Course

Required Textbook / Reading

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

Student presentations can be found here.

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, query processing and query optimization. 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
  • physical database design and tuning
III. Query Optimization
  • rewrite optimization
    • semantic query optimization
    • magic sets
    • the COUNT bug
    • ...
  • cost optimization
    • cost model
    • selectivity estimation
    • ...
  • new paradigms in query optimization

Grading Criteria / Course Requirements

Percentage When
Report or Project 30% due on the last day of classes
Presentation 30% second half of the semester
Take-Home Final Exam 40% sometime in April

York University's rules for academic honesty and plagiarism always remain in effect. Discussion is fine on the projects. However, collaboration is not. The work must be your own. Exams, of course, must be done on your own.


Students will design and implement some of the key algorithms and data-structures for a relational database system. Your code will be an extension of Derby, an open source database system. The project will be done individually or in teams (depending on the complexity of the project).

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

Note, the project will require a substantial amount of work and you will need to start it soon to be able to complete it on time.

In addition to coding, the project will require a report describing what has been achieved and a short demostration of the system with and without the added functionality.


Every student will be required to choose a research topic in databases to explore and do a presentation on it. The student will read a few seminal papers on the topic, to be chosen by the instructor and student. (The papers on this list are a good starting point). Then, he or she will prepare and do an oral presentation to present the topic to the class. These presentations will be scheduled in the second half of the course.

Report (The "Proposal")

Each student will write a report. The report topic will be negotiated between the instructor and student. The report will be written as a proposal for research work to be done. (You will not actually do that research. Your work here is to identify a viable research problem in databases that should be addressed.) The task is to identify an unaddressed problem in databases which would be useful to address, to conduct a literature search with respect to the problem, and to propose a methodology by which the problem could potentially be addressed.

The report is to be written in conference-paper format. It should have:

  • an abstract,
  • an introduction which describes and motivates the problem at hand, and demonstrates the importance of the problem,
  • a related works section which demonstrates evidence that the problem is unresolved,
  • a methodologies section in which you propose how the problem might be successfully addressed,
  • conclusions, and
  • a proper bibliograpghy.
Milestones for the report will be:
  • 1. Topic meeting with instructor
  • 2. Initial Proposal (~1 page)
  • 3. Progress Review (meeting)
  • 4. Extended Abstract (~2-3 pages)
  • 5. Final Report ( 10 pages)