CS798: Fundamentals of Physical Design and Query Compilation
Spring 2012

LECTURES

Tuesdays, from 3:00pm to not later than 5:50pm in DC2568.

INSTRUCTOR

Grant Weddell
Office: DC3346; Phone: x34463
gweddell@uwaterloo.ca

TEXTBOOK

Fundamentals of Physical Design and Query Compilation, David Toman and Grant Weddell, Synthesis Lectures on Data Management, M. Tamer Özsu, Series Editor, Morgan and Claypool Publishers.

You can obtain a pdf copy of the textbook on campus for free here, or a hardcopy if you prefer from Amazon.

OVERVIEW (from course text)

Query compilation is the problem of translating user requests formulated over purely conceptual and domain specific ways of understanding data, commonly called logical designs, to efficient executable programs called query plans. Such plans access various concrete data sources through their low-level often iterator-based interfaces. An appreciation of the concrete data sources, their interfaces and how such capabilities relate to logical design is commonly called a physical design. This course is an introduction to the fundamental methods underlying database technology that solves the problem of query compilation. The methods are presented in terms of first-order logic which serves as the vehicle for specifying physical design, expressing user requests and query plans, and understanding how query plans implement user requests.

GRADING

Assignments (roughly due every second week; five or six total): weight TBD.
Course participation: weight TBD.
Course project: weight TBD.

READING ASSIGNMENTS

First two chapters of the book by May 15th.
Codd [1970] by May 22nd.
Chapter 3 of the book by May 29th.
Chen [1976] by May 29th.
(recommended) Introduction to description logics (DLs).
(recommended) Relationship of DLs to other formalisms.
Escobar-Molano et al. [1993] by June 19th.
Avron [2008] by June 19th.
Chapter 4 of the book by June 19th.
Chapter 5 of the book by July 10th.
Chapter 6 of the book by July 24th.
The selection of further reading assignments and timing TBD.

PROGRAMMING AND WRITTEN ASSIGNMENTS

There will be four or five written assignments, with the possibility of a sixth programming assignment. Note that all marked assignments will be returned in class at the first opportunity following the assignment due date.

Assignment 1 (ungraded).
Assignment 2.NOTE: The due date for this assignment is extended to 5pm on Friday, June 1st, to give the instructor more time to prepare for Assignment 3! Anyone who submits by the original due date will receive an bonus of 15%. (Resubmissions past the original due date but prior to the new due date are also allowed, but will not receive the 15% bonus.) ANOTHER NOTE: A sample solution for a relational style of design (also called an Option 1 style) is available here. You are free to use this design in Assignment 3, as an alternative to your own design from Assignment 2.
Assignment 3.
Assignment 4 (paper presentation). At the start of class on June 26th, we will follow a selection process to assign each participant one of the following papers for a class presentation.
Nash et al. [2010]
Mendelzon and Wood [1991]
Chaudhuri [1998]
Simmon et al. [1996]
Chandra and Merlin [1977]
Levy et al. [1995]
Keller [1985]
Karabeg and Vianu [1991]
Cosmadakis and Papadimitriou [1984]
Fuchs and Schwitter [1996]

LECTURE MATERIAL

OTHER RESOURCES

TBD.

ACADEMIC INTEGRITY

Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. The Office of Academic Integrity's website (www.uwaterloo.ca/academicintegrity) contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in - and out - of the classroom.

Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.htm

Discipline: A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 - Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 - Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm

Avoiding Academic Offenses: Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy, http://www.math.uwaterloo.ca/navigation/Current/cheating_policy.shtml

Appeals: A student may appeal the finding and/or penalty in a decision made under Policy 70 - Student Petitions and Grievances (other than regarding a petition) or Policy 71 - Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm