This course is a graduate-level introduction to the algorithms, core principles, and foundational concepts for managing data at scale. Our goal is to expose students to general abstractions, tools and algorithms developed across various branches of the data management community and to draw relationships between them. The emphasis will be on both, the high-level theoretical intuitions and principles underlying scalable data management, as well as technical details.
Topics include: data models, query languages, worst-case optimal join algorithms, relational algebra, relational calculus, Datalog, query optimization, complexity of big-data analysis, parallel data processing, uncertain and incomplete data, provenance, algebraic structures for factorized representations, linear algebra.
Prerequisites: The course requires standard knowledge of discrete math, algorithms and complexity theory (e.g., from textbooks such as [Ericson'19], [Dasgupta, Papadimitriou, Vazirani'06], [Cormen, Leiserson, Rivest, Stein'09], [Kleinberg, Tardos'05], or [Lehman, Leighton, and Meyer'15].
PhD program: The course fulfills the PhD breath requirements for the Artificial Intelligence and Data Science area.
Instructor: Wolfgang Gatterbauer
Contact: Please use Piazza (via direct access from within Canvas) for all questions related to lectures, coursework, and the project. Notice you can post anonymously to all other students. Alternatively, please use our anonymous feedback form to send me comments anonymously. Please use my email (email@example.com) for scheduling office hours and everything else.
50%: Course project: The main component of this course will be a research project in the latter part of this class. This project can be a new application of one of the techniques presented or theoretically-oriented. The topic will be flexible, allowing students to explore scalable data management and analysis aspects related to their PhD research. This will involve an initial project proposal, an intermediate report, a project presentation and a final report. The final report should resemble a conference paper, and will be evaluated on the basis of soundness, significance, novelty, and clarity. Deliverables and dates are posted on the project page.
20%: Class scribes:
Students take turns in "illustrating" (to be consistent with standard notation we refer to it as "scribing") 7 lectures.
Graduate theory classes often ask students to scribe the lecture content.
Yet since this course provides well-curated lectures slides, we change the rule of the game in this graduate course.
Rather than scribing (repeating and summarizing) the content of the class, the students are asked to "illustrate" the covered topics with
imaginative and ideally tricky illustrating examples. Those in turn can help other students practice and solidify their understanding of
the class material.
Scribes are due 1 week after class at midnight (Tue for Tue classes, Fri for Fri classes) and can be done individually or in teams of two.
If you work in teams of two, you are expected to illustrate classes more often.
We have a signup sheet in Piazza. You can either use PowerPoint or Latex.
For PPTX, please use our PPTX template
For Latex, please use our Overleaf latex template.
In both cases, send me your PPTX or TEX document via email with "7240 class scribe" in the subject, and the lecture number in the body.
15%: Three assignments:
We have three assignments
in the first part of this class.
Like research projects, assignment solutions must be typeset in LaTeX.
15%: Class participation: Classes will be interactive and require participation of the students in class (discussing contributions or shortcomings of algorithms covered, small group break-out sessions with exercises). The class provides extensive readings for those interested, yet those are optional unless otherwise stated in class.
The course is based on papers, lectures, chapters from textbooks, and original presentations on scalable algorithms in data management. Pointers to those works are available on the website on a per-topic basis on the calendar page. This class provides a very broad overview and you aren't expected to read all the texts. Yet for those interested to dig deeper, they will provide useful background.
This course builds upon the structure and content of several existing great database classes. Some content courtesy to Dan Suciu, Benny Kimelfeld, Phokion Kolaitis, Moshe Vardi, Reinhard Pichler, Chris Re, Jeff Ullman, Paris Koutris, and Andreas Pieris.