CS 848 Advanced Topics in Database:  

Algorithmic Aspects of Database Query Processing

Fall 2025

Instructor: Xiao Hu

Course Description

    This course provides an in-depth exploration of data management fundamentals, focusing on the algorithmic aspects of query processing in database systems. We will cover topics that include traditional query processing, worst-case optimal join algorithms, conjunctive queries with extensions, sampling, dynamic query processing, and fast matrix multiplication for query processing. While there are no formal prerequisites, a background in undergraduate-level database and algorithm design is recommended. Coursework includes attending lectures, presenting and reviewing papers, and completing projects. Upon completion, students will have a solid understanding of data management concepts and the algorithmic techniques crucial for efficient query processing in various database settings.

Lectures

   10:00-11:20 AM MW    DC 2568    Xiao Hu

Schedule

Week Date Topic (Tentative Schedule) Presenter(s) Notes
1 Sep 3, 2025 Course Overview Xiao Hu lecture-01
2 Sep 8, 2025 Traditional Query Processing (1) Xiao Hu lecture-02
Supplementary Materials
Sep 10, 2025 Traditional Query Processing (2) Xiao Hu lecture-03
3 Sep 15, 2025 Worst-case Optimal Joins (1)
Skew Strikes Back: New Developments in the Theory of Join Algorithms
 Xiao Hu lecture-04
Sep 17, 2025 Worst-case Optimal Joins (2)
Skew Strikes Back: New Developments in the Theory of Join Algorithms
 Xiao Hu lecture-05
4 Sep 22, 2025 Aggregation (1)
Output-Optimal Algorithms for Join-Aggregate Queries
 Xiao Hu lecture-06
Sep 24, 2025 Aggregation (2)
Output-Optimal Algorithms for Join-Aggregate Queries
 Xiao Hu lecture-07
5 Sep 29, 2025 Difference
Computing the Difference of Conjunctive Queries Efficiently
 Desen Sun lecture-08
Oct 1, 2025 Negation
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
 Desen Sun lecture-09
6 Oct 6, 2025 Union
On the Enumeration Complexity of Unions of Conjunctive Queries		 Yuxin Kang lecture-10
Oct 8, 2025
(Guest Lecture Online)		 Comparison
Conjunctive Queries with Comparisons
 Qichen Wang lecture-11
7 Oct 13, 2025 Reading Week – No Class
Oct 15, 2025 Reading Week – No Class
8 Oct 20, 2025 Uniform Sampling (1)
Random Sampling over Joins Revisited
Chunhao Liao
Oct 22, 2025
(Guest Lecture)		 Uniform Sampling (2)
On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms
Guaranteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 		Jinchao Huang
9 Oct 27, 2025 Maintaining Uniform Samples
Reservoir Sampling over Joins
Yuxin Kang
Oct 29, 2025 Online Aggregation
Wander Join: Online Aggregation via Random Walks
Hongxun Xu
Chunhao Liao
10 Nov 3, 2025 Dynamic Yannakakis
The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 		Taebin Kim
Nov 5, 2025 Updates-Dependent Analysis
Change Propagation Without Joins
Taebin Kim
11 Nov 10, 2025 Dynamic Triangles
Maintaining Triangle Queries under Updates
ICDT 2019 		Saba Molaei
Nov 12, 2025 Update Sequences in Query Maintenance
Insert-Only versus Insert-Delete in Dynamic Query Evaluation
Hongxun Xu
12 Nov 17, 2025 FMM for Sparse Matrix Multiplication
Faster join-projects and sparse matrix multiplications
Fast Join-Project Query Evaluation using Matrix Multiplication
Minsi Lu
Nov 19, 2025 FMM for Triangle Queries
Listing triangles
Saba Molaei
13 Nov 24, 2025 FMM for Acyclic Join-Project Queries
Fast matrix multiplication for query processing
Minsi Lu
Nov 26, 2025 Final Project Presentation
14 Dec 1, 2025 Final Project Presentation
Note that the schedule is tentative and subject to change. We may consider online mode for the class for special situations. Supplementary reading materials can be found here.

Paper Presentation

Each student is required to present one paper. Please sign up here for your presentation paper and time. Please submit your slides and accompanying notes by the last Thursday before your presentation date.

For each presentation, you will have one hour to explain the paper’s main results, followed by 20 minutes for open discussion. When you describe an algorithm, start by explaining what it does and why it is useful. Then show a running example to illustrate how it works. After that, explain why the algorithm always produces the correct result. Finally, analyze its running time and overall efficiency. You may also discuss possible improvements and how the algorithm could be applied in your own research.

Paper Reviews

Learn will be used to submit paper reviews. Every week we will present (at most) two related papers, so please read these papers in advance. You are also required to submit reviews and answer questions I posted in advance. The due is 11:59 PM at every Friday.

Collaboration Policy: Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.

Late Policy: No late assignment will be accepted.

Project

Learn will be used to submit the group project. The project is required. Each project includes one or at most two students. You can choose a research problem that is related to the course materials and work on either theoretical or empirical aspects of it.

Milestone Due
Proposal 11:59pm EST, Friday, Oct 10 Oct 17
Presentation Wednesday, Nov 26, or Monday, Dec 1
Final Report 11:59pm EST, Monday, Dec 1

Mark breakdown

Attendance of lectures is required. If you miss more than one lecture without valid reason, you will not be eligible to pass the course.

Course policy and other information

Plagiarism

Plagiarism is a very serious academic offence and is penalized accordingly. When you plagiarize you damage the learning experience for yourself and others. To avoid plagiarism accusations, do not copy other people's work, and cite all references that you use. If you work with others, only discuss general aspects of the course material, not specific solutions. Write up the solutions yourself, not in groups.

Mental Health Resources

Mental Health: If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.

On-campus Resources

Off-campus Resources

Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students’ learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:

University Policies (University required text)

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 ( http://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, https://uwaterloo.ca/math/current-undergraduates/regulations-and-procedures/cheating-and-student-academic-discipline-guidelines.

MOSS (Measure of Software Similarities) is used in this course as a means of comparing students' assignments to ensure academic integrity. We will report suspicious activity, and penalties for plagiarism/cheating are severe. Please read the available information about academic integrity very carefully.

Discipline cases involving any automated marking system such as Marmoset include, but are not limited to, printing or returning values in order to match expected test results rather than making an actual reasonable attempt to solve the problem as required in the assignment question specification.

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, https://uwaterloo.ca/secretariat/policies-procedures-guidelines/policy-72 .