{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T11:25:14Z","timestamp":1770290714565,"version":"3.49.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-2217037"],"award-info":[{"award-number":["CCF-2217037"]}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["N66001-21-C-402"],"award-info":[{"award-number":["N66001-21-C-402"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,10,16]]},"abstract":"<jats:p>The restricted logic programming language Datalog has become a popular implementation target for deductive-analytic workloads including social-media analytics and program analysis. Modern Datalog engines compile Datalog rules to joins over explicit representations of relations\u2014often B-trees or hash maps. While these modern engines have enabled high scalability in many application domains, they have a crucial weakness: achieving the desired algorithmic complexity may be impossible due to representation-imposed overhead of the engine\u2019s data structures. In this paper, we present the \"Bring Your Own Data Structures\" (Byods) approach, in the form of a DSL embedded in Rust. Using Byods, an engineer writes logical rules which are implicitly parametric on the concrete data structure representation; our implementation provides an interface to enable \"bringing their own\" data structures to represent relations, which harmoniously interact with code generated by our compiler (implemented as Rust procedural macros). We formalize the semantics of Byods as an extension of Datalog\u2019s; our formalization captures the key properties demanded of data structures compatible with Byods, including properties required for incrementalized (semi-na\u00efve) evaluation. We detail many applications of the Byods approach, implementing analyses requiring specialized data structures for transitive and equivalence relations to scale, including an optimized version of the Rust borrow checker Polonius; highly-parallel PageRank made possible by lattices; and a large-scale analysis of LLVM utilizing index-sharing to scale. Our results show that Byods offers both improved algorithmic scalability (reduced time and\/or space complexity) and runtimes competitive with state-of-the-art parallelizing Datalog solvers.<\/jats:p>","DOI":"10.1145\/3622840","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T15:41:29Z","timestamp":1697470889000},"page":"1198-1223","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Bring Your Own Data Structures to Datalog"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3657-093X","authenticated-orcid":false,"given":"Arash","family":"Sahebolamri","sequence":"first","affiliation":[{"name":"Syracuse University, Syracuse, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0190-8912","authenticated-orcid":false,"given":"Langston","family":"Barrett","sequence":"additional","affiliation":[{"name":"Galois, Portland, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0719-1130","authenticated-orcid":false,"given":"Scott","family":"Moore","sequence":"additional","affiliation":[{"name":"Galois, Portland, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8650-0991","authenticated-orcid":false,"given":"Kristopher","family":"Micinski","sequence":"additional","affiliation":[{"name":"Syracuse University, Syracuse, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Program analysis and specialization for the C programming language. Ph. D. Dissertation. DIKU","author":"Andersen Lars Ole","unstructured":"Lars Ole Andersen . 1994. Program analysis and specialization for the C programming language. Ph. D. Dissertation. DIKU , University of Copenhagen. Lars Ole Andersen. 1994. Program analysis and specialization for the C programming language. Ph. D. Dissertation. DIKU, University of Copenhagen."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis. 25\u201330","author":"Antoniadis Tony","year":"2017","unstructured":"Tony Antoniadis , Konstantinos Triantafyllou , and Yannis Smaragdakis . 2017 . Porting doop to souffl\u00e9: a tale of inter-engine portability for datalog-based analyses . In Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis. 25\u201330 . Tony Antoniadis, Konstantinos Triantafyllou, and Yannis Smaragdakis. 2017. Porting doop to souffl\u00e9: a tale of inter-engine portability for datalog-based analyses. In Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis. 25\u201330."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371090"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951948"},{"key":"e_1_2_1_6_1","volume-title":"Static Analysis: 23rd International Symposium, SAS 2016, Edinburgh, UK, September 8-10, 2016, Proceedings 23","author":"Balatsouras George","year":"2016","unstructured":"George Balatsouras and Yannis Smaragdakis . 2016 . Structure-sensitive points-to analysis for C and C++ . In Static Analysis: 23rd International Symposium, SAS 2016, Edinburgh, UK, September 8-10, 2016, Proceedings 23 . 84\u2013104. George Balatsouras and Yannis Smaragdakis. 2016. Structure-sensitive points-to analysis for C and C++. In Static Analysis: 23rd International Symposium, SAS 2016, Edinburgh, UK, September 8-10, 2016, Proceedings 23. 84\u2013104."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4980-1_17"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16859"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428209"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.43410"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116878"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/364099.364331"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_23"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3303084.3309490"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.5643"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_2_1_19_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data \t\t\t\t  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data"},{"key":"e_1_2_1_20_1","unstructured":"LLVM-Authors. 2023. Opaque Pointers \u2013 LLVM documentation. https:\/\/llvm.org\/docs\/OpaquePointers.html \t\t\t\t  LLVM-Authors. 2023. Opaque Pointers \u2013 LLVM documentation. https:\/\/llvm.org\/docs\/OpaquePointers.html"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908096"},{"key":"e_1_2_1_23_1","unstructured":"Nicholas Matsakis and  RustDevelopers. 2023. Rust-Lang\/polonius: Defines the Rust borrow checker. https:\/\/github.com\/rust-lang\/polonius \t\t\t\t  Nicholas Matsakis and  RustDevelopers. 2023. Rust-Lang\/polonius: Defines the Rust borrow checker. https:\/\/github.com\/rust-lang\/polonius"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2692956.2663188"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0299-1"},{"key":"e_1_2_1_26_1","volume-title":"Datalog: Deductive Database Programming. https:\/\/docs.racket-lang.org\/datalog\/ Accessed 04-13-2023","author":"McCarthy Jay","year":"2022","unstructured":"Jay McCarthy . 2022 . Datalog: Deductive Database Programming. https:\/\/docs.racket-lang.org\/datalog\/ Accessed 04-13-2023 Jay McCarthy. 2022. Datalog: Deductive Database Programming. https:\/\/docs.racket-lang.org\/datalog\/ Accessed 04-13-2023"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2019.00015"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428195"},{"key":"e_1_2_1_29_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web.. Stanford InfoLab. \t\t\t\t  Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web.. Stanford InfoLab."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137852"},{"key":"e_1_2_1_31_1","volume-title":"Differential Datalog. In Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0)","author":"Ryzhyk Leonid","year":"2019","unstructured":"Leonid Ryzhyk and Mihai Budiu . 2019 . Differential Datalog. In Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0) . Philadelpha, PA. 56\u201367. Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog. In Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0). Philadelpha, PA. 56\u201367."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3497776.3517779"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556572"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_2_1_35_1","volume-title":"2015 IEEE 31st International Conference on Data Engineering. 867\u2013878","author":"Shkapsky Alexander","year":"2015","unstructured":"Alexander Shkapsky , Mohan Yang , and Carlo Zaniolo . 2015 . Optimizing recursive queries with monotonic aggregates in deals . In 2015 IEEE 31st International Conference on Data Engineering. 867\u2013878 . Alexander Shkapsky, Mohan Yang, and Carlo Zaniolo. 2015. Optimizing recursive queries with monotonic aggregates in deals. In 2015 IEEE 31st International Conference on Data Engineering. 867\u2013878."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_14"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282500"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454026"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Alfred Tarski. 1955. A lattice-theoretical fixpoint theorem and its applications. \t\t\t\t  Alfred Tarski. 1955. A lattice-theoretical fixpoint theorem and its applications.","DOI":"10.2140\/pjm.1955.5.285"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_2_1_42_1","unstructured":"Rijnard van Tonder. 2021. Towards Fully Declarative Program Analysis via Source Code Transformation. arXiv preprint arXiv:2112.12398. \t\t\t\t  Rijnard van Tonder. 2021. Towards Fully Declarative Program Analysis via Source Code Transformation. arXiv preprint arXiv:2112.12398."},{"key":"e_1_2_1_43_1","volume-title":"Worst-Case Optimal Join Algorithm. In International Conference on Database Theory.","author":"Veldhuizen Todd L.","year":"2014","unstructured":"Todd L. Veldhuizen . 2014 . Triejoin: A Simple , Worst-Case Optimal Join Algorithm. In International Conference on Database Theory. Todd L. Veldhuizen. 2014. Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In International Conference on Database Theory."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384677"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201918)","author":"Wang Kai","year":"2018","unstructured":"Kai Wang , Zhiqiang Zuo , John Thorpe , Tien Quang Nguyen , and Guoqing Harry Xu . 2018 . RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on a Single Machine . In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201918) . USENIX Association, USA. 763\u2013782. isbn:978 1931971478 Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018. RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on a Single Machine. In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201918). USENIX Association, USA. 763\u2013782. isbn:9781931971478"},{"key":"e_1_2_1_46_1","volume-title":"Oxide: The essence of rust. arXiv preprint arXiv:1903.00982, https:\/\/doi.org\/10.48550\/arXiv.1903.00982","author":"Weiss Aaron","year":"2019","unstructured":"Aaron Weiss , Olek Gierczak , Daniel Patterson , Nicholas D Matsakis , and Amal Ahmed . 2019 . Oxide: The essence of rust. arXiv preprint arXiv:1903.00982, https:\/\/doi.org\/10.48550\/arXiv.1903.00982 10.48550\/arXiv.1903.00982 Aaron Weiss, Olek Gierczak, Daniel Patterson, Nicholas D Matsakis, and Amal Ahmed. 2019. Oxide: The essence of rust. arXiv preprint arXiv:1903.00982, https:\/\/doi.org\/10.48550\/arXiv.1903.00982"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_8"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 2022 International Conference on Management of Data. 1433\u20131446","author":"Wu Jiacheng","year":"2022","unstructured":"Jiacheng Wu , Jin Wang , and Carlo Zaniolo . 2022 . Optimizing parallel recursive datalog evaluation on multicore machines . In Proceedings of the 2022 International Conference on Management of Data. 1433\u20131446 . Jiacheng Wu, Jin Wang, and Carlo Zaniolo. 2022. Optimizing parallel recursive datalog evaluation on multicore machines. In Proceedings of the 2022 International Conference on Management of Data. 1433\u20131446."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000436"},{"key":"e_1_2_1_51_1","unstructured":"Eric Zhang. 2023. Datalog compiler embedded in Rust as a procedural macro. https:\/\/github.com\/ekzhang\/crepe \t\t\t\t  Eric Zhang. 2023. Datalog compiler embedded in Rust as a procedural macro. https:\/\/github.com\/ekzhang\/crepe"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591239"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622840","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3622840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:27Z","timestamp":1750298247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":51,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2023,10,16]]}},"alternative-id":["10.1145\/3622840"],"URL":"https:\/\/doi.org\/10.1145\/3622840","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"2023-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}