CS 632: Advanced DBMS

Suraj Shetiya

Spring 2025  

Previous offerings: 2018, 2017, 2016, 2015, 2014, 2013, 2011, 2010, 2009, 2007, 2006, 2004, 2003, 2002, 2001, 2000, 1999.

About The Course

Reading material will consist primarily of research papers. All students will have to present a research paper of their choice, either from the list below or other papers subject to instructors approval. There will also be two exams (midsem/endsem), assignments, and a course project.

Grading scheme: Anyone who does an exceptional course project that has the potential to be a publishable paper is eligible for a straight AA grade. Otherwise the grading breakup would be midsem 25, endsem 40, project 20 and assignments plus seminar presentation 15 (the breakup of these will depend on whether we have individual or joint seminars, which depends on the final enrollment).

Assignments To be decided.

Project The project is mandatorily an implementation oriented project. You may still need to do some literature survey to figure out your project though. Projects should be done in groups of 2. A basic project will take any of the papers we study in the course, or other related papers, and implement the algorithms in the paper, and do a very basic performance study. However, I would expect most projects to improve upon existing techniques. A more advanced project would take a problem specification for which no solution is publicly available, figure out how to solve it, and implement the solution.

Project List To be decided

Textbook (for background material only): Database System Concepts, 7th Ed. Avi Silberschatz, Hank Korth, and S. Sudarshan. McGraw Hill, 2020. (book home page)

List of papers: NOTE: The list of topics below is subject to change during the semester, especially those later in the semester

  1. Fagin, R., Lotem, A., & Naor, M. (2001, May). Optimal aggregation algorithms for middleware. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (pp. 102-113).
  2. Fagin, R. (2002). Combining fuzzy information: an overview. ACM SIGMOD Record, 31(2), 109-118.
  3. Das, G., Gunopulos, D., Koudas, N., & Tsirogiannis, D. (2006, September). Answering top-k queries using views. In Proceedings of the 32nd international conference on Very large data bases (pp. 451-462).
  4. Chazelle, Bernard, Leo J. Guibas, and Der-Tsai Lee. "The power of geometric duality." BIT Numerical Mathematics 25.1 (1985): 76-90.
  5. Chester, S., Thomo, A., Venkatesh, S., & Whitesides, S. (2014). Computing k-regret minimizing sets. Proceedings of the VLDB Endowment, 7(5), 389-400.
  6. Shetiya, S., Asudeh, A., Ahmed, S., & Das, G. (2019). A unified optimization algorithm for solving" regret-minimizing representative" problems. Proceedings of the VLDB Endowment, 13(3).
  7. Zeighami, Sepanta, and Raymond Chi-Wing Wong. "Finding average regret ratio minimizing set in database." 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 2019.
  8. Asudeh, A., Nazi, A., Zhang, N., Das, G., & Jagadish, H. V. (2019, June). RRR: Rank-regret representative. In Proceedings of the 2019 International Conference on Management of Data (pp. 263-280).
  9. Chen, Qixu, and Raymond Chi-Wing Wong. "Robust Best Point Selection under Unreliable User Feedback." Proceedings of the VLDB Endowment 17.11 (2024): 2681-2693.
  10. Shetiya, S., Swift, I. P., Asudeh, A., & Das, G. (2022, May). Fairness-aware range queries for selecting unbiased data. In 2022 IEEE 38th International Conference on Data Engineering (ICDE) (pp. 1423-1436). IEEE.
  11. Zheng, J., Ma, Y., Ma, W., Wang, Y., & Wang, X. (2022). Happiness Maximizing Sets under Group Fairness Constraints (Technical Report). arXiv preprint arXiv:2208.06553.
  12. Asudeh, A., Jagadish, H. V., Stoyanovich, J., & Das, G. (2019, June). Designing fair ranking schemes. In Proceedings of the 2019 international conference on management of data (pp. 1259-1276).
  13. Asudeh, A., Nazi, A., Zhang, N., & Das, G. (2017, May). Efficient computation of regret-ratio minimizing set: A compact maxima representative. In Proceedings of the 2017 ACM International Conference on Management of Data (pp. 821-834).
  14. Asudeh, A., Jagadish, H. V., Miklau, G., & Stoyanovich, J. (2018). On obtaining stable rankings. arXiv preprint arXiv:1804.10990.
    15. Yang, K., & Stoyanovich, J. (2017, June). Measuring fairness in ranked outputs. In Proceedings of the 29th international conference on scientific and statistical database management (pp. 1-6).
  15. Islam, M. M., Wei, D., Schieber, B., & Roy, S. B. (2022). Satisfying complex top-k fairness constraints by preference substitutions. Proceedings of the VLDB Endowment, 16(2).
  16. Wei, D., Islam, M. M., Schieber, B., & Basu Roy, S. (2022, June). Rank aggregation with proportionate fairness. In Proceedings of the 2022 international conference on management of data (pp. 262-275).
  17. Li, J., Moskovitch, Y., Stoyanovich, J., & Jagadish, H. V. (2023). Query Refinement for Diversity Constraint Satisfaction. Proceedings of the VLDB Endowment, 17(2), 106-118.Campbell, F. S., Silberstein, A., Stoyanovich, J., & Moskovitch, Y. (2024).
  18. Query Refinement for Diverse Top-k Selection. Proceedings of the ACM on Management of Data, 2(3), 1-27
  19. Chen, Z., Manolios, P., & Riedewald, M. (2024). Finding Linear Explanations for a Given Ranking. arXiv preprint arXiv:2406.11797.
  20. In Search of an Understandable Consensus Algorithm Diego Ongaro and John Ousterhout Proc ATC14, USENIX Annual Technical Conference (2014), USENIX (This is the Raft paper)
  21. Spanner: Google's Globally-Distributed Database James C. Corbett et al., OSDI 2012
  22. Pregel: a system for large-scale graph processing Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, Grzegorz Czajkowski, SIGMOD 2010.
  23. Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age Viktor Leis, Peter Boncz, Alfons Kemper, Thomas Neumann, SIGMOD 2014
  24. Plan bouquets: query processing without selectivity estimation. Anshuman Dutt, Jayant R. Haritsa, SIGMOD Conference 2014: 1039-1050
  25. Generating Test Data for Killing SQL Mutants: A Constraint-based Approach, Shetal Shah, S. Sudarshan, Suhas Kajbaje, Sandeep Patidar, Bhanu Pratap Gupta, Devang Vira, ICDE 2011
  26. Program Transformations for Asynchronous and Batched Query Submission, Karthik Ramachandra, Mahendra Chavan, Ravindra Guravannavar, and S. Sudarshan, IEEE Trans. on Knowledge and Data Engineering (TKDE), pp. 531-544, Vol. 27, No. 2, Feb 2015
  27. Extracting Equivalent SQL from Imperative Code in Database Applications K. Venkatesh Emani, Karthik Ramachandra, Subhro Bhattacharya, S. Sudarshan SIGMOD Conference 2016, pp. 1781-1796