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

  1. PODS
  2. 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:

2017

The 2017 Award Committee consisted of Leonid Libkin and Moshe Y. Vardi. After careful consideration and having solicited external nominations and advice, they have decided to select the following paper as the award winner for the 2017 ACM PODS Alberto. O. Mendelzon Test-of-Time Award:

  • Todd J. Green, Grigoris Karvounarakis, and Val Tannen: Provenance Semirings. In the mid 1990s, Stefano Bistarelli, Ugo Montanari, and Francesca Rossi discovered an elegant framework for constraint solving based on assigning constraints values in a semiring; it accounted, in a uniform way, for several hitherto different approaches to constraint solving. In their PODS 2007 paper, titled ``Provenance semirings'', Green, Karvounarakis, and Tannen demonstrated, via a collection of well chosen examples, that the same idea is applicable in database theory: they used the semiring approach to capture in a uniform way a variety of scenarios where unions of conjunctive queries or datalog queries are posed over relational databases. These included incomplete and probabilistic databases, and computing provenance of tuples by using well known and studied semirings. After the publication of PODS 2007 paper, the semiring approach was adopted by the database community; it was extended to more expressive queries and was used in provenance applications as well as in applications related to incomplete and probabilistic data and causality in databases. The paper has gathered over 500 citations, giving evidence to its broad impact.

2016

The 2016 Award Committee consisted of Marcelo Arenas, Peter Buneman, and Jan Van den Bussche. After careful consideration and listening to external nominations and advice, they have decided to select the following paper, which was published in PODS 2006, as the award winner for 2016 ACM PODS Alberto. O. Mendelzon Test-of-Time Award:

  • Mikołaj Bojańczyk, Claire David, Anca Muscholl, Thomas Schwentick, and Luc Segoufin. Two-variable logic on data trees and XML reasoning. The authors introduced an influential new approach to the modeling of XML trees with data values. This means that not only purely structural queries, but also queries involving joins can be modeled. The new approach unifies earlier results, and has led to many new results, on the automated verification of XML queries under integrity constraints. The paper has been highly influential both in database and automata theory. Because database theory research on XML has greatly benefitted from an automata-theoretic approach, it is satisfying to see the circle completed in this respect. 

2015

The 2015 Award Committee consisted of Foto Afrati, Frank Neven, and Dan Suciu and decided to award the following papers from the 2005 PODS proceedings:

  • Michael Benedikt, Wenfei Fan, and Floris Geerts. XPath Satisfiability in the Presence of DTDs. The paper studies the satisfiability problem for XPath queries under schema constraints. The satisfiability problem is a classical problem associated with query languages, and the query languages considered in this paper represent tree pattern languages of universal interest. The paper considers an exhaustive combination of query languages and schema formalism, establishing tight complexity bounds for the satisfiability problem.
    The conference paper, and its full version published in the Journal of the ACM three years later, contain a treasure trove of complexity results and proof techniques, most of which are state of the art today. The proofs are technically sophisticated, yet a pleasure to read. The paper has a large number of citations, has influenced many researchers, and it is considered today the standard reference for complexity results on the satisfiability problem for XPath expressions.
  • Luc Segoufin and Victor Vianu. Views and Queries: Determinacy and Rewriting. Prior to this paper there had been considerable research activity on rewriting queries using views, which is a fundamental problem in databases. But all prior work had been confined to algorithms for finding such rewritings. This paper marks a complete conceptual shift in looking at the problem, focusing attention for the first time on the question of when rewritings exist, regardless of whether one can find them. The paper introduces the right conceptual framework for studying one of the most important problems in database theory, by defining formally the notion of determinacy. It also establishes several key theoretical results, demonstrating both the elegance and the depth of the notion of determinacy, and pointing to the general direction of how determinacy should be studied in the future. Today, the notion of determinacy, as defined by this paper, has been widely adopted by the theoretical database community, and has motivated several followup studies, ranging from work on the problem of decidability of FO rewritability to decidability results for restricted classes of queries.

2014

The 2014 Award Committee consisted of Wenfei Fan (chair), Floris Geerts, and Dan Suciu and decided to award the following papers from the 2004 PODS proceedings:

  • Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang Chiew Tan. Composing schema mappings: Second-order dependencies to the rescue.The paper proposed a general semantics for composing schema mappings. Schema mappings study how the data from one application is to be mapped to another with a different data format, typically specified  by source-to-target tuple-generating dependencies (st-tgds). The paper proved that the composition of st-tgd mappings is not necessarily an st-tgd mapping. In light of this impossibility result, it introduced the language of second-order st-tgds (SO-tgds), and showed that the class of mappings defined by SO-tgds is closed under composition. Moreover, it showed that this class preserves good properties of st-tgds for data exchange. It also proved that every SO-tgd defines the composition of a finite number of st-tgd mappings. This definition of the composition operator for schema mappings has been adopted as a standard in the area of data exchange.
  • Claudio Gutierrez, Carlos A. Hurtado, and Alberto O. Mendelzon. Foundations of semantic web databases.This paper was the first paper in PODS about semantic Web databases, and was among the first efforts to study fundamental problems associated with RDF graphs pre-dating SPARQL. It provided clean, elegant and simple formalizations of the main concepts related to the use of blank nodes and  RDFS vocabulary in RDF, formalized the inference and query answering problems for RDF in this general context, and established the computational complexity of these problems. This paper was instrumental in bringing traditional database techniques into semantic Web, showing how fundamental theoretical results in database theory can be carried over to an important domain.

Both papers have received hundreds of citations, and have had an impact on subsequent research on data exchange and semantic Web databases, respectively. In particular, the Test-of-Time Award for the second paper is a posthumous recognition of the great work of the late Alberto O. Mendelzon.

2013

The 2013 Award Committee consisted of Michael Benedikt, Tova Milo, and Dirk Van Gucht and decided to award the following paper from the 2003 PODS proceedings:

  • Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy.This paper dealt with the following fundamental question: given a system holding a database with sensitive data, how many queries can it permit to be answered, and with what accuracy, while preserving the privacy of the data?

    A database is modelled by an n-bitstring d1,..,dn with a query being a subset q of {1,…,n}. The answer to q is defined as the sum of all database entries specified by q. When q is issued, the system itself will return this answer perturbed by some random noise. Relative to this setting, Dinur and Nissim established the following fundamental, but negative, result: If, for each query, the system’s added noise is bounded by o(sqrt(n)), then an adversary can almost entirely reconstruct the database from the answers of just O(n log^2(n)) randomly selected queries. Furthermore, the reconstruction can be done in polynomial time. Fortunately, for very large n, obtaining answers to O(n log^2(n)) queries may be prohibitively expensive. What would happen if only a sublinear number of queries is allowed? This problem was addressed in the second part of the paper. This led to positive results for a very strong notion of privacy, which would, through the work of additional researchers, evolve into what is now known as “differential privacy.” The Dinur-Nissim paper has received hundreds of citations. It has had a fundamental impact on the theory and practice of private data analysis. Furthermore, it was the seed for the development of differential privacy.

2012

The 2012 Award Committee consisted of Richard Hull, Phokion G. Kolaitis, and Dirk Van Gucht and decided to award the following paper from the 2002 PODS proceedings:

  • Gerome Miklau and Dan Suciu. Containment and Equivalence for an XPath Fragment.The paper studied static analysis problems for XPath, a query language at the core of processing XML documents and XML document databases. XPath, an important paradigm of a query language for semi-structured data, is designed with tree-navigation in mind and supports such navigation along three axes: ancestor-descendant, branching, and wildcards.
    In this paper, Miklau and Suciu established that if all three axes are allowed, then the query containment problem for XPath queries is coNP-complete. Furthermore, this intractability persists even when certain tight bounds on the number of wildcards and the number of branches are imposed. These results shed light on the boundary between tractability and intractability for XPath query containment, since it was previously known that the containment problem was solvable in polynomial time for XPath queries in which any two of the three axes are allowed. Both the paper in the PODS 2002 proceedings and its subsequent full version in the Journal of the Association for Computing Machinery have received hundreds of citations each. Moreover, this work initiated a fruitful line of research on the static analysis of XML query languages that
    brought together researchers from database theory and automata theory.

2011

The 2011 Award Committee consisted of Peter Buneman, Meral Ozsoyoglu, and Jianwen Su and decided to award the following paper from the 2001 PODS proceedings:

  • Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal Aggregation Algorithms for Middleware.The paper investigates a very important problem that originates in multimedia databases: Given a set of objects with grades (rankings) on many attributes, find the objects with the best overall combined grades under some monotone combining function such as min or average. The paper presents a very simple algorithm, called Threshold Algorithm, and proves that it is essentially optimal (in finding the best overall grades) for all monotone functions and over every database. Furthermore, the algorithm only requires a small constant-size buffer. The paper also gives adaptation of the algorithm for situations such as no random accesses. The Threshold Algorithm has been used in a wide range of applications where the problem naturally occurs, from databases with traditional and non-traditional types of data (music, video, text, uncertain data, etc.) to social networks, sensor networks, etc. The paper is among the most highly cited papers in PODS 2001, and perhaps all time.

The paper has clearly had a major influence on the database and other research communities. Hence, the committee found it to be entirely worthy of this Award.

2010

The 2010 Award Commitee consisted of Phokion G. Kolaitis and Jianwen Su and decided to award the following papers from the 2000 PODS proceedings:

  • Tova Milo, Dan Suciu, and Victor Vianu. Typechecking for XML Transformers.The paper studied the problem of checking whether or not an XML transformation (e.g., specified in XSLT and in other languages) is well typed: for every input document of a given DTD, the result document always conforms to another specified DTD. The problem is essential for manipulating XML documents. The main result of the paper is that the problem is decidable. A key ingredient in obtaining this result was the introduction and study of a new tree-transducer model with pebbles that serves as an abstraction of XML transformations.
  • Wenfei Fan and Jerome Simeon. Integrity Constraints for XML.The paper investigated integrity constraints for XML DTDs, including keys, foreign keys, inverse constraints, and inclusion dependencies. The technical results concern the implication and finite implication problems for the constraints. Clearly, integrity constraints and, in particular, the types studied in this paper, are an essential part of XML data modeling in a variety of contexts, including data management and software engineering. The undecidability, decidability, and complexity results provide a guidance and basis for dealing with integrity constraints in practice.

Both papers are extensively cited in the literature, and both had a major influence on the methodology and direction of subsequent research on XML data modeling and management. Hence, the committee has found both to be worthy of this Award.

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 generalises 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.

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.