Bring Your Own Data Structures to Datalog

Explore a groundbreaking approach to enhancing Datalog's capabilities in this 17-minute conference talk from OOPSLA2 2023. Learn about the 'Bring Your Own Data Structures' (Byods) methodology, a DSL embedded in Rust that allows engineers to write logical rules parametric on concrete data structure representations. Discover how Byods enables the use of custom data structures to represent relations, potentially improving algorithmic complexity and scalability for various applications. Delve into the formalized semantics of Byods as an extension of Datalog, understanding the key properties required for compatible data structures. Examine real-world applications of this approach, including optimized versions of the Rust borrow checker Polonius, highly-parallel PageRank implementations, and large-scale LLVM analysis. Gain insights into how Byods offers improved algorithmic scalability and competitive runtimes compared to state-of-the-art parallelizing Datalog solvers.

[OOPSLA23] Bring Your Own Data Structures to Datalog