In this course we will discuss some advanced database concepts and techniques (besides a recap of basics like SQL and relational algebra), including:
1. Storage Models, Indexing, Views
2. Query Optimization (include Optimal Join Algorithm)
3. Transactions
4. Data Privacy (e.g., Differential Privacy)
5. I/OEfficient Algorithms (e.g., List Ranking)
6. Streaming Algorithms (e.g., CountMin Sketch)
7. MapReduce Algorithms (e.g., Matrix Computation)
Detailed list of topics is available in the course schedule below.
Participants are expected to have a background in algorithms and data structures, and some basic knowledge in databases.
The evaluation will be based on a set of exercises and exams.
Qin Zhang
Email: qzhangcs@indiana.edu
Office hour: Tuesday 2:45pm3:45pm (LH430A)
Week  Date  Section  Content  Slides  Comments 

1  Aug. 26  Touchbase Exam  
1  Aug. 28  0. Introduction  slides models 

2  Sep. 2  1. Basics  SQL  slides  Main Ch. 6 (book chapters all approximate) 
2  Sep. 4  SQL  same  
3  Sep. 9  Relational Algebra / Datalog  same  Main Ch. 5  
3  Sep. 11  Relational Calculus  same  
4  Sep. 16  2. Models and Indexing  Data Models  slides  
4  Sep. 18  Views, Constraints Indexing 
same  Main Ch. 7, 8, 14  
5  Sep. 23  3. Optimization  Query Processing  slides  Main Ch. 15 
5  Sep. 25  Query Processing (cont.)  same  
6  Sep. 30  Query Optimization  same  Main Ch. 16  
6  Oct. 2  Optimal Join Algo  Ré's slides  
7  Oct. 7  4. Trasactions  Recovery  slides  Main Ch. 17 
7  Oct. 9  Recovery (cont.)  same  
8  Oct. 14  Midterm Review  Solution for Ass. 1 & 2 by Yifan Pan 
Midterm preparation: Ass. 1 & 2; RA, RC, SQL, B/B+tree (Ch. 15.6), query rewrite (Ch. 16.2), cost estimation / DP (Ch. 16.4, 16.6), query plan, index (Ch. 15.6), Joins (Ch. 15.3, 15.4, 15.5) 

8  Oct. 16  Midterm  
9  Oct. 21  4. Trasactions (cont.)  Concurrency Control  same  Main Ch. 18 
9  Oct. 23  Concurrency Control (cont.)  same  
10  Oct. 28  5. I/OEfficient Algorithms  Sorting  slides 
Sitchianva's note CACM article Sec. 5 of Vitter's book 
10  Oct. 30  List Ranking  same  Sitchianva's note Sec. 2 of Zeh's survey 

11  Nov. 4  6. Streaming Algorithms  Sampling  slides  Basic probability slides and proofs 
11  Nov. 6  Distint Elements  same  Section 2 of Chakrabarti's notes  
12  Nov. 11  Heavy Hitters  same  Section 1, 4 of Chakrabarti's notes For spacesaving see this paper 

12  Nov. 13  7. Data Privacy  Introduction  slides  
13  Nov. 18  kAnonymity, lDiversity  same  Also see Cormode's slides  
13  Nov. 20  Differential Privacy  Final Review  
14  Nov. 25  Thanksgiving Break  
14  Nov. 27  Thanksgiving Break  
15  Dec. 2  9. Student Presentations  Achanta, Garimella+Adusumilli, Brundavanam+Krukau 
Bellinger, Kumar+Chandrashekharachar, Gaikwad+Shelke 

15  Dec. 4  Chen, Supe+Jagasia, Pathak+Jazayeri 
Gupta, Loya+Ramakrishna, Luo and Peng 

16  Dec. 9  Sureshkumar+Rangarajan, Shivaramakrishnan, Singh, 
Pillai+Modi, Mohsen, Vijaya+Sasikumar 

16  Dec. 11  Final  Final preparation: Transactions, I/O algorithms (time forward processing), Streaming algorithms 
For assignments, students may discuss answers with anyone, including problem approaches and proofs. But all students must write their own proofs, and writeups. The names of all people that you have talked to should be listed at the beginning of the first page. If a solution comes from existing papers/web/books, they must be properly cited, and you must write the solution in a way that demonstrates your understanding (simply copying the solution will be considered as plagiarism). All deadlines are firm. No late assignments will be accepted unless there are legitimate circumstances.
For more details, see Indiana University Code of Student Rights, Responsibilities, and Conduct.