CSIE 7242: Advanced Topics in Database Theory

       

Instructor

  • Name: Tony Tan
  • Room: CSIE 516
  • Office hour: By appointment via email
  • Email: tonytan@csie.ntu.edu.tw
  • Personal website

Venue and time

  • Lecture: Tuesday, 15:30-17:10 in CSIE 546
  • Tutorial: Wednesday, 16:30-17:20 in CSIE 546

Administration

Syllabus (tentative)

Part Week Dates Lesson Remark
A I 22 and 23 February 2016 Lesson 1. First-order logic in database Homework 1 is out.
II 1 and 2 March 2016 Lesson 2. Relational algebra --
III 8 and 9 March 2016 Lesson 3. Ehrenfeucht-Fraïssé games --
IV 15 and 16 March 2016 Lesson 4. Datalog queries --
V 22 and 23 March 2016 -- Homework 1 is due.
B VI 29 and 30 March 2016 Lesson 5. Treewidth Homework 2 is out.
VII 5 and 6 April 2016 Holiday (tomb-sweeping festival) --
VIII 12 and 13 April 2016 Lesson 6. Tree automata --
IX 19 and 20 April 2016 Lesson 7. Query evaluations on bounded treewidth graphs --
C X 26 and 27 April 2016 Lesson 8. Hypergraphs Homework 2 is due. Homework 3 is out.
XI 3 and 4 May 2016 Lesson 9. Acyclic (join) queries --
XII 10 and 11 May 2016 Lesson 10. Width of queries --
XIII 17 and 18 May 2016 -- Homework 3 is due.
D XIV 24 and 25 May 2016 Lesson 11. Entropy Homework 4 is out.
XV 31 May and 1 June 2016 Lesson 12. Linear programming --
XVI 7 and 8 June 2016 Lesson 13. Bounds on join --
XVII 14 and 15 June 2016 Lesson 14. Some recent join algorithms --
XVIII 21 and 22 June 2016 -- Homework 4 is due.

Notes on tutorial

  • Participation in the tutorial will contribute to your final grade.
  • You can also submit your tutorial solutions. It will be counted as participation too.
  • From Lesson 11 onward, there are no separate tutorials on Wednesdays. Instead, they will be combined with the lectures on Tuesdays.

Notes on homeworks

  • Homeworks are always due on Tuesdays at 15:30 in the indicated week.
  • You can submit your homework earlier than the due date by slipping it under the door of my office.
  • Homework can be handwritten or typewritten. If it is handwritten, the writing must be legible.
  • The tidiness of your homework contributes to your grade.
  • Discussions/collaborations are allowed, but be sure that you understand and write down your own solutions. In other words, don't just copy-paste.
  • Points will be deducted if you don't understand your own solutions.