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.

翻译：我们提出了基于关系连接的新的电子匹配方法;特别是,我们应用了最近数据库查询执行技术来保证最坏情况的最佳运行时间。与总是搜索电子绘图“向下”的常规回溯跟踪方法相比,我们新的关系电子匹配方法可以通过根据优化查询计划搜索电子地图来更好地利用模式结构。我们还建立了电子匹配的第一批数据复杂性结果,将运行时间作为电子绘图规模和产出大小的函数来捆绑在一起。我们在最先进的鸡蛋电子绘图框架中对技术进行了原型和评估。与传统的基线相比,关系电子匹配比较简单,实际执行速度更快。