ACM PODS Alberto O. Mendelzon Test-of-Time Award

Alberto O. Mendelzon was an international leader in the principles of database systems. His pioneering work on database dependencies has been influential in both the theory and practice of data management. His work has inspired research and practice in database design, query processing, and data integration. He made fundamental contributions in the areas of graphical and visual query languages, knowledge-base systems, and online-analytic processing. His work has provided the foundation for languages used to search web data. The volume of these applications is a testament to the truly foundational nature of his results.

Mendelzon was a Professor of Computer Science at the University of Toronto and a Fellow of the Royal Society of Canada. He was selected by the top organizations in database research to chair or co-chair ten program committees of major conferences that span the entire spectrum of database research, from theory (including PODS), to systems (for example, VLDB), to emerging areas (for example, the WWW conference). Mendelzon served as General Chair of the PODS conference from 1997 to 1999. In addition to being a leader of the database community, Mendelzon was an outstanding educator, who guided the research of 19 doctoral students and of numerous postdoctoral fellows until he passed away in June 2005.

The ACM PODS Alberto O. Mendelzon Test-of-Time Award was established in 2007 and was awarded for the first time in 2008. It is awarded every year to a paper or a small number of papers published in the PODS proceedings ten years prior that had the most impact in terms of research, methodology, or transfer to practice over the intervening decade. Each year, the winner(s) of the ACM PODS Alberto O. Mendelzon Test-of-Time Award receive plaques and the sum of $1,000 (divided equally among the winners, if more than one). The award is funded by a generous gift from IBM.

Recipients ACM PODS Alberto O. Mendelzon Test-of-Time Award:

2008

The 2008 Award Committee consisted of Catriel Beeri (Chair), Georg Gottlob, and Jan Paredaens. The Award Committee selected the following two papers from the 1998 PODS proceedings as the award winners for 2008: Serge Abiteboul and Oliver M. Duschka. Complexity of Answering Queries Using Materialized Views. This paper dealt with a central problem in database research, with numerous applications in data management. It provided a conceptual framework and a terminology for the problem, and presented a comprehensive analysis of its complexity. Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. This paper investigated the relationship between two fundamental and extensively studied problems from the database and artificial intelligence areas, respectively. It showed that the two problems are equivalent, and investigated conditions that guarantee polynomial-time solutions, explaining in particular, many previously known polynomial time solutions. Both papers are extensively cited in the literature, and both had a major influence on the methodology and direction of subsequent research. Hence, the committee has found both to be worthy of the Award. The committee notes that the nomination of these two papers as first winners of the Alberto O. Mendelzon Award is particularly appropriate, since both deal with problems very closely related to his research interests.

2009

The 2009 Award Commitee consisted of Catriel Beeri (Chair), Phokion G. Kolaitis, and Christos H. Papadimitriou and decided to award the following paper from the 1999 PODS proceedings: Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree Decompositions and Tractable Queries The paper deals with a central problem in database research, namely finding classes of conjunctive queries for which problems, such as the evaluation of Boolean queries and query containment, are in polynomial time. This problem has attracted a lot of attention since the pioneering work of Yanakakis on acyclic queries. The paper shows that the earlier notion of bounded query width (introduced by Chekuri and Rajaraman in ICDT 97) is NP-hard, introduces the notion of bounded hypertree width, then shows that this notion properly generalizes earlier notions of acyclicity, that constant hypertree width is efficiently recognizable, and that Boolean queries with constant hypertree width can be efficiently evaluated. The results of the paper are applicable to both conjunctive query evaluation and to constraint satisfaction. The paper is extensively cited in the literature, and had an impact on subsequent research on these two problems. Hence, the committee has found it to be worthy of the Award.

Top of Page