EECS-4411M
Database Management Systems

York University
Winter 2017
Syllabus

Instructor: Parke Godfrey
Office: Lassonde Building #2050
Office Hours: 3–5pm Wednesdays
& by appointment
Ph#: 416-736-2100 x66671
e-mail: godfrey@yorku.ca
Term: Winter 2017
Time: Tu&Th 10:00-11:30pm
Place: CB #122
Textbook: H. Garcia-Molina, J.D. Ullman, & J. Widom
Database Systems: The Complete Book
2nd edition, 2009
Pearson / Prentice Hall
ISBN: 0-13-187325-3
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
projects 3 × 10% three, due through the semester
test #1 20% 2 February
test #2 20% 9 March
final exam 30% ? April

The grading policy is standard. Collaboration and discussion on the projects is fine. Note however, that unless you do the work of the projects 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

There will be three projects, in sum worth 30% 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. For the project(s) involving programming, your code will be in Java.

Late projects 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
#0 Th 5 Jan Introduction    
I. The Physical Database
#1 Tu 10 Jan the memory hierarchy Ch.13 §1  
  Th 12 Jan storage Ch.13 §2–4  
#2 Tu 17 Jan   I/O model    
  Th 19 Jan paging Ch.13 §5–8  
#3 Tu 24 Jan   the buffer pool    
  Th 26 Jan indexes: B-tree Ch.14 §1–3,7,8  
#4 Tu 31 Jan   hash tables & bitmap    
  Th 2 Feb Test #1  
II. Query Processing
#5 Tu 7 Feb overview of query-plan operators Ch.15 §1  
  Th 9 Feb one-pass algorithms & nest-loop joins Ch.15 §2,3 P1
#6 Tu 14 Feb two-pass algorithms Ch.15 §4,5  
  Th 16 Feb buffer-pool management & multi-pass algorithms Ch.15 §6,7  
reading week (18–25 Feb)
#7 Tu 28 Feb parsing, preprocessing, & query rewrite Ch.16 §1–3  
  Th 2 Mar cost estimation Ch.16 §4,5 P2
#8 Tu 7 Mar join-enumeration & the query plan Ch.16 §6,7  
  Th 9 Mar Test #2  
III. Database Management
#9 Tu 14 Mar graph databases (RDF) & triple-store    
  Th 16 Mar SPARQL    
#10 Tu 21 Mar crash recovery Ch.17 §1–5  
  Th 23 Mar      
#11 Tu 28 Mar concurrency control & transaction management Ch.18 §1–5  
  Th 30 Mar     P3
#12 Tu 4 Apr wrap up    
final exam period (7–24 Apr)
#13 ? Apr Final Exam

P#: Project '#' due.

Projects are due on the Friday of the week indicated above. Specific details for turning in projects will be set. 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.