Efficient Staged Datalog Evaluation
Event details
| Date | 31.01.2022 |
| Hour | 10:00 › 12:00 |
| Speaker | Anna Herlihy |
| Category | Conferences - Seminars |
| Event Language | English |
EDIC candidacy exam
Exam president: Prof. Karl Aberer
Thesis advisor: Prof. Anastasia Ailamaki
Thesis co-advisor: Prof Martin Odersky
Co-examiner: Prof. Sanidhya Kashyap
Abstract
Datalog is a rule-based declarative database query language based on logic programming. Datalog is more expressive than relational algebra as it supports mutually recursive rules, making it a natural way to express fixed point problems like a transitive closure. Many static program analyses, including data-flow, control-flow, and points-to analyses can be expressed as fixed point problems. Yet there are still barriers to more widespread adoption of Datalog, in part because users are forced to choose between inefficient Datalog libraries accessible from general purpose programming languages and external, optimized Datalog engines behind strong architectural boundaries. Datalog solvers are often standalone applications that require facts to be serialized to specialized file format, and do not automatically derive facts from external data sources.
Background papers
Exam president: Prof. Karl Aberer
Thesis advisor: Prof. Anastasia Ailamaki
Thesis co-advisor: Prof Martin Odersky
Co-examiner: Prof. Sanidhya Kashyap
Abstract
Datalog is a rule-based declarative database query language based on logic programming. Datalog is more expressive than relational algebra as it supports mutually recursive rules, making it a natural way to express fixed point problems like a transitive closure. Many static program analyses, including data-flow, control-flow, and points-to analyses can be expressed as fixed point problems. Yet there are still barriers to more widespread adoption of Datalog, in part because users are forced to choose between inefficient Datalog libraries accessible from general purpose programming languages and external, optimized Datalog engines behind strong architectural boundaries. Datalog solvers are often standalone applications that require facts to be serialized to specialized file format, and do not automatically derive facts from external data sources.
Background papers
- S. Ceri, G. Gottlob, and L. Tanca. 1989. What You Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. on Knowl. and Data Eng. 1, 1 (March 1989), 146–166. DOI:https://doi.org/10.1109/69.43410
- Bernhard Scholz, Herbert Jordan, Pavle Subotić, and Till Westmann. 2016. On fast large-scale program analysis in Datalog. In Proceedings of the 25th International Conference on Compiler Construction (CC 2016). Association for Computing Machinery, New York, NY, USA, 196–206. DOI:https://doi.org/10.1145/2892208.2892226
- Nicolas Stucki, Aggelos Biboudis, and Martin Odersky. 2018. A practical unification of multi-stage programming and macros. SIGPLAN Not. 53, 9 (September 2018), 14–27. DOI:https://doi.org/10.1145/3393934.3278139
Practical information
- General public
- Free