Skip to main content

Dan Suciu wins ICDT Test of Time Award for a novel construction of a decision diagram called ‘query compilation’

Portrait of Dan Suciu

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, has previously receive the the Association for Computing Machinery (ACM) Principles of Database Systems Alberto Mendelzon Test of Time Award in 2010 and 2012, the VLDB Test of Time Award in 2014 and the ACM Special Interest Group on Management of Data in 2000. He is a Fellow of the ACM and holds 12 U.S. patents and has earned an NSF Career Award and an Alfred P. Sloan Fellowship

Congratulations, Dan and Abhay! 

March 30, 2021