Deconstructing Datalog
4 hours ago
- #PhD Dissertation
- #Datalog
- #Functional Programming
- The author submitted their PhD dissertation titled 'Deconstructing Datalog' in September 2022 after revisions.
- Datalog is a logic programming language from the 1980s that extends relational algebra with recursive queries, known for its simplicity and efficiency.
- The dissertation introduces Datafun, which integrates Datalog's features into a typed functional language by working backward from semantics.
- A key insight is representing recursive queries as least prefix points using a fix operator, turning predicates and logic into sets and functions.
- Datafun's type system tracks monotonicity to ensure well-defined recursive queries, inspired by Datalog's stratification condition.
- The implementation of fix is optimized using seminaïve iteration to avoid redundant work, incrementalizing deduction functions for efficiency.
- The dissertation acknowledges essential contributors, including the advisor, examiners, and individuals who influenced the author's academic journey.