167 citations · 215 across the 7 of their papers we have counts for
11 papers
Revisiting the Algebraic Foundation of Relational Data
Yisu Remy Wang, Paul Talma
We revisit Tarski's Algebra of Relations (TAR), an old formalism of relations predating Codd's relational algebra by over 100 years, as a new foundation for relational databases. W…
Semantic foundations of equality saturation
Dan Suciu, Yisu Remy Wang, Yihong Zhang
Equality saturation is an emerging technique for program and query optimization developed in the programming language community. It performs term rewriting over an E-graph, a data…
No More Nulls!
Yisu Remy Wang
Since the inception of SQL, nulls have frustrated database users and builders alike. Those writing SQL must painstakingly guard their queries against surprising results caused by n…
Better Together: Unifying Datalog and Equality Saturation
Yihong Zhang, Yisu Remy Wang, Oliver Flatt +5
We present egglog, a fixpoint reasoning system that unifies Datalog and equality saturation (EqSat). Like Datalog, it supports efficient incremental execution, cooperating analyses…
Free Join: Unifying Worst-Case Optimal and Traditional Joins
Yisu Remy Wang, Max Willsey, Dan Suciu
Over the last decade, worst-case optimal join (WCOJ) algorithms have emerged as a new paradigm for one of the most fundamental challenges in query processing: computing joins effic…
Optimizing Recursive Queries with Program Synthesis
Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q. Ngo +2
Most work on query optimization has concentrated on loop-free queries. However, data science and machine learning workloads today typically involve recursive or iterative computati…
Rewrite Rule Inference Using Equality Saturation
Chandrakana Nandi, Max Willsey, Amy Zhu +6
Many compilers, synthesizers, and theorem provers rely on rewrite rules to simplify expressions or prove equivalences. Developing rewrite rules can be difficult: rules may be subtl…
Relational E-Matching
Yihong Zhang, Yisu Remy Wang, Max Willsey +1
We present a new approach to e-matching based on relational join; in particular, we apply recent database query execution techniques to guarantee worst-case optimal run time. Compa…
Equality Saturation for Tensor Graph Superoptimization
Yichen Yang, Phitchaya Mangpo Phothilimtha, Yisu Remy Wang +3
One of the major optimizations employed in deep learning frameworks is graph rewriting. Production frameworks rely on heuristics to decide if rewrite rules should be applied and in…
egg: Fast and Extensible Equality Saturation
Max Willsey, Chandrakana Nandi, Yisu Remy Wang +3
An e-graph efficiently represents a congruence relation over many expressions. Although they were originally developed in the late 1970s for use in automated theorem provers, a mor…
SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra
Yisu Remy Wang, Shana Hutchison, Jonathan Leang +2
Machine learning algorithms are commonly specified in linear algebra (LA). LA expressions can be rewritten into more efficient forms, by taking advantage of input properties such a…