LFCS Seminar: Tuesday, 28 March - Dan Suciu
Speaker: Dan Suciu
Title: Optimizing Recursive Queries
Abstract:
Modern data analytics requires iteration, yet relational database
engines are mostly optimized for non-recursive queries. SQL supports
only a limited form of recursion. A better formalism for recursive
queries is datalog, which has some elegant properties (recursion
always terminates), and led to the development of two powerful
optimizations techniques: semi-naive evaluation, and magic set
rewriting. But standard datalog is restricted to monotone queries
over sets and does not support aggregates, which has limited its
adoption.
In this talk I will describe a new approach to recursive queries and
their optimization. First, we extend datalog to semirings, while
preserving some of the elegant properties of datalog, and also
supporting aggregates naturally. Then, I will describe a simple, yet
very powerful optimization rule, called the FGH rule, that rewrites a
recursive program into a different recursive program. The rule
captures many optimizations discussed in the literature, such as
magic set optimization, the PreM rule, and semi-naive evaluation, and
as well as new semantics optimizations. Our implementation of the FGH
rule is based on the egg term rewriting engine, and the Rosette program
synthesizer.
Joint work with: Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q. Ngo,
Reinhard Pichler
Dan Suciu is a Microsoft Endowed Professor in the Paul G. Allen School of
Computer Science and Engineering at the University of Washington.
Suciu is conducting research in data management, on topics such as
query optimization, 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 received the ACM SIGMOD Codd
Innovation Award, received several best paper awards and test of time
awards, and is a Fellow of the ACM. Suciu is currently an associate
editor for the Journal of the ACM. Suciu's PhD students Gerome Miklau,
Christopher Re and Paris Koutris received the ACM SIGMOD Best
Dissertation Award in 2006, 2010, and 2016 respectively, and Nilesh
Dalvi was a runner up in 2008.
LFCS Seminar: Tuesday, 28 March - Dan Suciu
IF G-03