responsive.png

When processing join queries over big data, a DBMS can become unresponsive, i.e., it takes very long until any output tuples appear. Ranked enumeration addresses this problem by attempting to return the most important answers as quickly as possible, ideally in time that is linear (or quasilinear) in input size, even if the complete output is much larger. Aside from its practical usefulness, ranked enumeration is closely related to, and in a way unifies, many other problems involving joins. The common goal is the design of optimal algorithms that are guaranteed to avoid large intermediate results and thus achieve time or space complexity close to a lower bound. Arguably, avoiding query plans that produce huge intermediate results has been an overarching goal of database optimizers, which is part of the reason why optimal join algorithms, enumeration, and factorized representations have generated a lot of excitement. In this tutorial, we embark on an exploration of these topics with ranked enumeration as our guide, showing how they are intimately connected with a wide range of fundamental problems in computer science.

Part 1: Introduction (Nikos)

Part 2: Cycles and Tree Decompositions (Mirek)

Part 3: Acyclic queries & Enumeration (Wolfgang)

Part 4: Factorization (Nikos)

Part 5: Dynamic programming & Semirings (Wolfgang)

Part 6: Any-k or Ranked Enumeration (Nikos)

Part 7: Decomposition of Inequality Predicates and Conclusions (Mirek)

Authors from the DATA Lab at Northeastern University

Northeastern University, Khoury College of Computer Sciences

Bibliography

Toward Responsive DBMS: Optimal Join Algorithms, Enumeration, Factorization, Ranking, and Dynamic Programming
Nikolaos Tziavelis, Wolfgang Gatterbauer, Mirek Riedewald

Related papers authored by the presenters

Any-k Algorithms for Enumerating Ranked Answers to Conjunctive Queries
Nikolaos Tziavelis, Wolfgang Gatterbauer, Mirek Riedewald
Beyond Equi-joins: Ranking, Enumeration and Factorization
Nikolaos Tziavelis, Wolfgang Gatterbauer, Mirek Riedewald
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, Xiaofeng Yang
Optimal Join Algorithms meet Top-k
Nikolaos Tziavelis, Wolfgang Gatterbauer, Mirek Riedewald

Longer Bibliography

A longer list of related work is available on the website from our SIGMOD 2020 tutorial and in the related work section of arXiv:2205.05649.

Funding

This work has been supported in part by the National Science Foundation (NSF) under award numbers CAREER IIS-1762268 and IIS-1956096, by the Office of Naval Research (Grant#: N00014-21-C-1111), and by the National Institutes of Health (NIH) under award number R01 NS091421. Any opinions, findings, and conclusions or recommendations expressed in this presentation are those of the authors and do not necessarily reflect the views of the funding agencies.

National Science Foundation ONR National Institutes of Health

Citation

To cite this tutorial, please use following bibtex entry:

@article{TziavelisGR:2022,
	  author = {Nikolaos Tziavelis and Wolfgang Gatterbauer and Mirek Riedewald},
	  title = {Toward Responsive DBMS: Optimal Join Algorithms, Enumeration, Factorization, Ranking, and Dynamic Programming},
	  booktitle = {ICDE},
	  year = {2022},
	  doi = {10.1109/ICDE53745.2022.00299},
	  url = {https://northeastern-datalab.github.io/responsive-dbms-tutorial}
}