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. The examples throughout the class are naturally biased by the expertise of the instructor and are chosen with an eye towards ongoing research in our research group.
Topics include: data models, query languages, logic & relational calculus, relational algebra, Datalog & recursion, stable model semantics, complexity of query evaluation, acyclic query optimization, variable elimination orders, worst-case optimal join algorithms, provenance, reverse data management, tree decompositions and hypertree decompositions, algebraic structures for factorized representations, linear algebra, iterative propagation algorithms, axiomatic approaches for designing problem solutions, managing uncertain and incomplete data.
Prerequisites: The course is fast-paced and 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'' breath area.
Time/location
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 questions anonymously to all other students, or anonymously even to me. Alternatively, please use our anonymous feedback form to send comments that are anonymous to me and that only I can see. Please use my email (wgatterbauer@northeastern.edu) 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.
35%: Class scribes:
Students take turns in "illustrating" 7 lectures (to be consistent with standard notation we refer to it as "scribes").
Graduate theory classes often ask students to scribe the lecture content.
Yet since I already provide you with well-curated lectures slides, we change the rule of the game.
Rather than scribing (= repeating and summarizing) the content of the class, I ask you to "illustrate" some interesting aspect in the covered topics with imaginative and ideally tricky illustrating examples.
Those illustrations are great if they in turn can help other students practice and solidify their understanding of the topics discussed.
Georg Cantor is quoted as saying: "To ask the right question is harder than to answer it."
In that spirit, our class scribes are closer to research than assignments:
What particular aspect in a class is worthy to be "illustrated"? That's already part of the question.
Scribes are done in PowerPoint and are due 1 week after class at midnight (Tue for Tue classes, Fri for Fri classes).
They can be done individually or in teams of two (if you work in teams of two, you are expected to illustrate 14 classes instead of 7 classes).
Please use our PPTX template, and name your document
"cs7240-sp21-[YOUR NAME]-scribe[NUMBER]-[SOME DESCRIBTIVE TITLE].pptx"
before submitting via Canvas.
For some more pedagogic motivation see videos by
Tim Brown on asking questions and reframing problems being key to creativity,
Dan Meyer on formulating problem being more important than just solving them,
Derek Muller on increasing learning by including possible misconceptions into stories,
and an older text of mine of the educational value of temporarily misleading the spectator before giving the correct answer.
15%: Class participation: Classes will be interactive and require concentration and participation of the students. Participate when we discuss the merits or shortcomings of algorithms covered or small group break-out sessions with exercises. Ask questions, during class or on Canvas. Questions that make me ponder or create new illustrating examples are all great instances of class participation. Also, *never* hesitate to point out to me errors you spot in my slides or any links or other material. It can only count towards class participation. Finally notice that while the class provides extensive readings for those interested, these pointers are almost exclusively optional (unless otherwise stated in class).
The course is based on papers, lectures, chapters from textbooks, and original presentations the topics. 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 are not expected to read all the texts. Yet for those interested to dig deeper, they will provide useful background.
This course builds upon the structure of several existing great database classes. Some content courtesy to Dan Suciu, Benny Kimelfeld, Phokion Kolaitis, Moshe Vardi, Reinhard Pichler, Chris Re, Jeff Ullman, and Andreas Pieris. A more recent and closely related class is by Dan Olteanu. I tried to give credit to the original inspirations on each individual slide. In case I missed something, please let me know. Any errors and non-acknowledged content is the result of me trying to explain concepts to my students and myself with minimal examples necessary, and refining them every time I teach and get student feedback.