{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:42:59Z","timestamp":1780994579021,"version":"3.54.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1749570"],"award-info":[{"award-number":["1749570"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Applications Driving Architectures (ADA) Research Center"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,1,16]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3498696","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T17:03:12Z","timestamp":1642006992000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Relational e-matching"],"prefix":"10.1145","volume":"6","author":[{"given":"Yihong","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yisu Remy","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8066-4218","authenticated-orcid":false,"given":"Max","family":"Willsey","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zachary","family":"Tatlock","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n.d.]. Glean System for collecting deriving and querying facts about source code. https:\/\/glean.software Accessed: 2021-10-12.  [n.d.]. Glean System for collecting deriving and querying facts about source code. https:\/\/glean.software Accessed: 2021-10-12."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_2_3_1","unstructured":"Andreas Amler. 2017. Evaluation of Worst-Case Optimal Join Algorithm. Master\u2019s thesis.  Andreas Amler. 2017. Evaluation of Worst-Case Optimal Join Algorithm. Master\u2019s thesis."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088515.3088522"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_2_6_1","volume-title":"30th European Conference on Object-Oriented Programming (ECOOP","author":"Avgustinov Pavel","year":"2016","unstructured":"Pavel Avgustinov , Oege De Moor , Michael Peyton Jones , and Max Sch\u00e4fer . 2016 . QL: Object-oriented queries on relational data . In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Pavel Avgustinov, Oege De Moor, Michael Peyton Jones, and Max Sch\u00e4fer. 2016. QL: Object-oriented queries on relational data. In 30th European Conference on Object-Oriented Programming (ECOOP 2016)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_14"},{"key":"e_1_2_2_8_1","volume-title":"Deriving Production Rules for Incremental View Maintenance. In 17th International Conference on Very Large Data Bases","author":"Ceri Stefano","year":"1991","unstructured":"Stefano Ceri and Jennifer Widom . 1991 . Deriving Production Rules for Incremental View Maintenance. In 17th International Conference on Very Large Data Bases , September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings, Guy M. Lohman, Am\u00edlcar Sernadas, and Rafael Camps (Eds.). Morgan Kaufmann, 577\u2013589. isbn:1-55860-150-3 http:\/\/www.vldb.org\/conf\/ 1991\/P577.PDF Stefano Ceri and Jennifer Widom. 1991. Deriving Production Rules for Incremental View Maintenance. In 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings, Guy M. Lohman, Am\u00edlcar Sernadas, and Rafael Camps (Eds.). Morgan Kaufmann, 577\u2013589. isbn:1-55860-150-3 http:\/\/www.vldb.org\/conf\/1991\/P577.PDF"},{"key":"e_1_2_2_9_1","volume-title":"Automated Deduction \u2013 CADE-21","author":"de Moura Leonardo","unstructured":"Leonardo de Moura and Nikolaj Bj\u00f8rner . 2007. Efficient E-Matching for SMT Solvers . In Automated Deduction \u2013 CADE-21 , Frank Pfenning (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg . 183\u2013198. isbn:978-3-540-73595-3 Leonardo de Moura and Nikolaj Bj\u00f8rner. 2007. Efficient E-Matching for SMT Solvers. In Automated Deduction \u2013 CADE-21, Frank Pfenning (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 183\u2013198. isbn:978-3-540-73595-3"},{"key":"e_1_2_2_10_1","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"de Moura Leonardo","unstructured":"Leonardo de Moura and Nikolaj Bj\u00f8rner . 2008. Z3: An Efficient SMT Solver . In Tools and Algorithms for the Construction and Analysis of Systems , C. R. Ramakrishnan and Jakob Rehof (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 337\u2013340. isbn:978-3-540-78800-3 Leonardo de Moura and Nikolaj Bj\u00f8rner. 2008. Z3: An Efficient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems, C. R. Ramakrishnan and Jakob Rehof (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 337\u2013340. isbn:978-3-540-78800-3"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066102"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803406"},{"key":"e_1_2_2_14_1","unstructured":"Amine Mhedhbi and Semih Salihoglu. 2019. Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins. arxiv:1903.02076v2.  Amine Mhedhbi and Semih Salihoglu. 2019. Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins. arxiv:1903.02076v2."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.04.078"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386012"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2019.00015"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28717-6_28"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335393"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_2_2_25_1","unstructured":"Raoul-Gabriel Urma and Alan Mycroft. 2013. Expressive and Scalable Source Code Queries with Graph Databases.  Raoul-Gabriel Urma and Alan Mycroft. 2013. Expressive and Scalable Source Code Queries with Graph Databases."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_2_2_27_1","volume-title":"Yisu Remy Wang, Max Willsey, Sudip Roy, and Jacques Pienaar.","author":"Yang Yichen","year":"2021","unstructured":"Yichen Yang , Phitchaya Mangpo Phothilimtha , Yisu Remy Wang, Max Willsey, Sudip Roy, and Jacques Pienaar. 2021 . Equality Saturation for Tensor Graph Superoptimization. arXiv e-prints, Article arXiv:2101.01332, Jan., arXiv:2101.01332 pages. arxiv:2101.01332. Yichen Yang, Phitchaya Mangpo Phothilimtha, Yisu Remy Wang, Max Willsey, Sudip Roy, and Jacques Pienaar. 2021. Equality Saturation for Tensor Graph Superoptimization. arXiv e-prints, Article arXiv:2101.01332, Jan., arXiv:2101.01332 pages. arxiv:2101.01332."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223848"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498696","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498696","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:28Z","timestamp":1750188628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":28,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2022,1,16]]}},"alternative-id":["10.1145\/3498696"],"URL":"https:\/\/doi.org\/10.1145\/3498696","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"assertion":[{"value":"2022-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}