Relational Algorithms for Top-k Query Evaluation

Qichen Wang*, Qiyao Luo, Yilei Wang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review


The evaluation of top-k conjunctive queries, a staple in business analysis, often requires evaluating the conjunctive query prior to filtering the top-k results, leading to a significant computational overhead within Database Management Systems (DBMSs). While efficient algorithms have been proposed, their integration into DBMSs remains arduous. We introduce relational algorithms, a paradigm where each algorithmic step is expressed by a relational operator. This allows the algorithm to be represented as a set of SQL queries, enabling easy deployment across different systems that support SQL. We introduce two novel relational algorithms, level-k and product-k, specifically designed for evaluating top-k conjunctive queries and demonstrate that level-k achieves optimal running time for top-k free-connex queries. Furthermore, these algorithms enable easy translation into an oblivious algorithm for secure query evaluations. The presented algorithms are not only theoretically optimal but also exhibit eminent efficiency in practice. The experiment results show significant improvements, with our rewritten SQL outperforming the baseline by up to 6 orders of magnitude. Moreover, our secure implementations not only achieve substantial speedup compared to the baseline with secure guarantees but even surpass those baselines that have no secure guarantees.
Original languageEnglish
Pages (from-to)1–27
Number of pages27
JournalProceedings of the ACM on Management of Data
Issue number3
Early online date30 May 2024
Publication statusPublished - Jun 2024

User-Defined Keywords

  • conjunctive query
  • top-k query
  • secure multi-party computation
  • relational algorithm


Dive into the research topics of 'Relational Algorithms for Top-k Query Evaluation'. Together they form a unique fingerprint.

Cite this