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.
