# Relational E-Matching

arXiv: https://arxiv.org/abs/2108.02290 · HTML: https://mlsanity.com/paper/2108.02290/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2021.

## Built on by (most cited first, 1 of 1)

- [rEGGression: an Interactive and Agnostic Tool for the Exploration of Symbolic Regression Models](https://mlsanity.com/paper/2501.17859/) (2025)

## Abstract (arXiv)

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. Compared to the conventional backtracking approach that always searches the e-graph "top down", our new relational e-matching approach can better exploit pattern structure by searching the e-graph according to an optimized query plan. We also establish the first data complexity result for e-matching, bounding run time as a function of the e-graph size and output size. We prototyped and evaluated our technique in the state-of-the-art egg e-graph framework. Compared to a conventional baseline, relational e-matching is simpler to implement and orders of magnitude faster in practice.