Allen School professor Dan Suciu was honored for his impact on data management research at the 2021 International Conference on Database Theory (ICDT) with the Test of Time Award for his paper, “Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams.”
In the winning paper, Suciu and then-student Abhay Jha (Ph.D., ‘12), now a senior machine learning scientist at Amazon, explored more efficient ways to construct decision diagrams — tools that simplify the task of computing the probability of a complex event. Their paper was the first to propose “query compilation to decision diagrams” and to identify the connection between static analysis on the query and the complexity of the resulting decision diagrams.
A structured query language (SQL) is a small program designed to find the most efficient results of a database query, sometimes amongst billions of records. When more information than an SQL search is needed, if each record in the relational database is annotated with a probability of being present, the query needs to return probabilities for its answers. The team’s paper uses decision diagrams for this purpose.
“Decision diagrams have been used for many years in formal verification, because they simplify the task of computing the probability of a complex event,” said Suciu, a member of the University of Washington’s Database Group. “We proposed to construct a decision diagram from an SQL query and a relational database, a process called ‘query compilation.’ The challenge in query compilation is to keep the size of the decision diagram small.”
Suciu said a naive construction leads to a decision diagram that is exponentially large in the billions of tuples in the database. This is an unacceptable situation. The paper describes more efficient ways to construct the decision diagram and characterizes precisely for which queries the resulting diagram will be efficient and which will necessarily have an exponential size.
“The determination between ‘good’ queries and ‘bad’ queries can be done only through static analysis on the query without the need to examine the database and can be adapted to several variants of the decision diagram,” Suciu said.
The winning paper was the first to identify the connection between static analysis on the query and the complexity of the resulting decision diagrams. Follow-up work by Suciu and Jha, as well as others, has expanded the study of this important connection.
Suciu, who has been at the UW since 2000, previously received the Alberto O. Mendelzon Test of Time Award in 2010 from the Association for Computing Machinery’s Symposium on Principles of Database Systems (PODS), the VLDB 10-year Best Paper Award from the International Conference on Very Large Databases in 2014, and a SIGMOD Best Paper Award from the ACM Special Interest Group on Management of Data in 2000. He is a Fellow of the ACM and the past recipient of both a National Science Foundation CAREER Award and a Sloan Research Fellowship and holds 12 U.S. patents.
Congratulations, Dan and Abhay!