Relational E-matching
summary
Transforms e-graphs into relational tables and patterns into conjunctive queries, then runs worst-case optimal joins (generic join) to guarantee asymptotic bounds; proves the first data-complexity bound tying runtime to e-graph size and output size. Prototype inside the egg framework and a SQLite-backed prototype show real speedups—some patterns gain orders of magnitude faster matching (up to six orders in benchmarks), index-build time can reduce wins, and multi-pattern matching is supported for free.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:22Relational Imaging
- 1:04Program Orientation
- 1:41Egraph
- 2:37Imagine
- 3:41Imaging
- 5:12Summary
- 6:18Workflow
- 7:00Relational Database
- 12:02First Theorem
- 12:41Second Theorem
- 13:43Results
- 16:32Future work
- 20:12Questions
- 22:08Service level
- 24:59Nonlinear patterns
related talks
20mGraphiti: Bridging Graph and Relational Database Queries
45mGraph databases, PostgreSQL and SQL/PGQ
01h 01mDatalog and Equality Saturation
17mBetter Together: Unifying Datalog and Equality Saturation
14mA Practitioner's Guide to Graphs
24mGraph-Powered Job Matcher: From SQL Tables to Neo4j RAG in Production
44mIntermediate Relational Algorithm Design
35mElixir's Ecto: Functional Relational Data Access Done Right