In 2013, the International Conference on Database Theory (ICDT) began awarding the ICDT test-of-time (ToT) award, with the goal of recognizing one paper, or a small number of papers, presented at ICDT a decade earlier that have best met the “test of time”. In 2022, the award recognizes a paper from the ICDT 2012 proceedings that has had the most impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade. The award was presented during the EDBT/ICDT 2022 Joint Conference, March 29-April 1st, 2022.
The ICDT 2022 Test of Time Award committee consists of
After careful consideration and soliciting external assessments, the committee has chosen the following recipient of the 2022 ICDT Test of Time Award:
Factorised Representations of Query Results: Size Bounds and Readability
by
Dan Olteanu and Jakub Závodný.
This paper introduced the fundamental concept of factorized data representations, subsequently studied as factorized databases in database theory. Factorized representations avoid redundancy in relations by building them up from singleton tuples using the union and product operators. The work by Olteanu and Závodný gave a formal definition of these factorized representations and showed their numerous benefits: they are more succinct than flat relations, can be used to evaluate queries more efficiently, and their tuples can be enumerated with linear-time preprocessing and constant delay. Their work further shows size bounds on factorized representations of query results depending on graph-theoretic parameters of the query, and also considers many extensions, such as factorized provenance representations, connections to readability width, and aggregation over factorized representations.
Since then, this concept of factorized databases has had profound impact on several areas of database theory, database systems research, and neighboring areas. Applications include query evaluation over graph databases, improved enumeration results, factorized computation of aggregates, and factorized machine learning. Their work has successfully bridged the gap between theory and practice: it has prompted implementations of its core ideas in subsequent works, and it has also sparked practical research across several independent areas.
Factorized databases are acknowledged as an inspiration within many lines of practical and theoretical research, including the work on aggregate queries by Abo Khamis et al. (PODS 2016 best paper award), the work on SPARQL by Abul-Basher et al. (EDBT 2021 best short paper award), and many others. This conclusively demonstrates the lasting influence of this highly cited paper and of its full version titled “Size Bounds for Factorised Representations of Query Results” which later appeared in ACM Transactions on Database Systems.