ACM SIGMOD City, Country, Year
sigmod pods logo

PODS Awards

PODS Best Paper Award

Best Paper Award: Worst-Case Optimal Join Algorithms

Hung Q. Ngo, University at Buffalo, SUNY; Ely Porat, Bar-Ilan University; Christopher Ré, University of Wisconsin-Madison; Atri Rudra, University at Buffalo, SUNY

Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a novel algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a full conjunctive query in terms of the sizes of the individual relations in the body of the query. These bounds, however, are not constructive: they rely on Shearer's entropy inequality which is information-theoretic. Thus, the previous results leave open the question of whether there exist algorithms whose running time achieve these optimal bounds. An answer to this question may be interesting to database practice, as we show in this paper that any project-join plan is polynomially slower than the optimal bound for some queries. We construct an algorithm whose running time is worst-case optimal for all natural join queries. Our result may be of independent interest, as our algorithm also yields a constructive proof of the general fractional cover bound by Atserias, Grohe, and Marx without using Shearer's inequality. In addition, we show that this bound is equivalent to a geometric inequality by Bollobs and Thomason, one of whose special cases is the famous Loomis-Whitney inequality. Hence, our results algorithmically prove these inequalities as well. Finally, we discuss how our algorithm can be used to compute a relaxed notion of joins.

Hung Q. Ngo is an Associate Professor at the Computer Science and Engineering department, State University of New York (SUNY) at Buffalo. He received a Ph.D. in Computer Science and an M.S. in Mathematics from the University of Minnesota, Twin Cities. His main research interests are in the theory of switching networks and algorithmic group testing.

Ely Porat is an Associate Professor at Bar-Ilan University. He received his Doctorate at Bar-Ilan University in 2000. Following that, he fulfilled his military service and, in parallel, worked as a faculty member at Bar- Ilan University. Porat spent the spring 2007 semester as a Visiting Scientist in Google Mountain View. He is a consultor to Google in Tel Aviv, and holds positions as a visiting professor at the University of Michigan and at Tel Aviv University.

Christopher (Chris) Ré is an assistant professor in the department of Computer Sciences at the University of Wisconsin-Madison. The goal of his work is to enable users and developers to build applications that more deeply understand and exploit data. Chris received his PhD from the University of Washington, Seattle under the supervision of Dan Suciu. For his PhD work in the area of probabilistic data management, Chris received the SIGMOD 2010 Jim Gray Dissertation Award. Chris received an NSF CAREER Award in 2011.

Atri Rudra is an Assistant Professor of Computer Science and Engineering at University at Buffalo, State University of New York, Buffalo. Atri received his Bachelor's degree from Indian Institute of Technology, Kharagpur, India in 2000 and his Ph.D. from University of Washington in 2007. From 2000-2002, he was a Research Staff Member at IBM India Research Lab, New Delhi, India. His research interests lie in theoretical computer science and in particular, theory of error-correcting codes, data stream and sub-linear algorithms, game theory and algorithmic mechanism design, approximation algorithms, computational complexity, finite field theory and applications. He is a recipient of an NSF CAREER award (2009), HP Labs Innovation Research Award (2010), ESA best paper award (2010) and the UB Exceptional Scholars - Young Investigator award (2011).

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

Containment and Equivalence for an XPath Fragment

Gerome Miklau, University of Massachusetts, Amherst; Dan Suciu, University of Washington

The paper studied static analysis problems for XPath, a query language at the core of processing XML documents and XML document databases. The results of Miklau and Suciu 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 navigation axes of XPath 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.

Gerome Miklau is an Associate Professor at the University of Massachusetts, Amherst. His primary research interest is the secure management of large-scale data. This includes evaluating threats to privacy in published data, devising techniques for the safe publication of social networks, network traces, and audit logs, as well as designing database management systems to implement security policies. He was awarded a Lilly Teaching Fellowship in 2011, an NSF CAREER Award in 2007, and he won the 2006 ACM SIGMOD Dissertation Award. He received his Ph.D. in Computer Science from the University of Washington in 2005. He earned Bachelor's degrees in Mathematics and in Rhetoric from the University of California, Berkeley, in 1995.

Dan Suciu is a Professor in Computer Science at the University of Washington. He received his Ph.D. from the University of Pennsylvania in 1995, was a principal member of the technical staff at AT&T Labs and joined the University of Washington in 2000. Suciu is conducting research in data management, with an emphasis on topics related to Big Data and data sharing, such as probabilistic data, data pricing, parallel data processing, data security. He is a co-author of two books Data on the Web: from Relations to Semistructured Data and XML, 1999, and Probabilistic Databases, 2011. He is a Fellow of the ACM, holds twelve US patents, received the 2000 ACM SIGMOD Best Paper Award, the 2010 PODS Ten Years Best paper award, and is a recipient of the NSF Career Award and of an Alfred P. Sloan Fellowship. Suciu serves on the VLDB Board of Trustees, and is an associate editor for the VLDB Journal, for ACM TOIS, and for Information Systems. Suciu's PhD students Gerome Miklau and Christopher Re received the ACM SIGMOD Best Dissertation Award in 2006 and 2010 respectively, and Nilesh Dalvi was a runner up in 2008.

Follow our progress: Facebook