Database Readings
The following is a collection of resources to construct databases. My initial line of research is in constructing a database that allows for abstraction and combinators in constructing the search clauses.
Relational Algebra
Tools
Alf
Alf is a modern query language, rooted in relational algebra, and implemented as a Ruby Domain Specific Language.
Datalog UI
An implementation of Datalog with a focus on managing UIs & UI state.
Datalog
Following is a collection of resources for understanding the construction of Datalog:
What You Always Wanted to Know About Datalog (And Never Dared to Ask)
Looks like a neat paper on the internals of Datalog.
Building a Datalog for Fun! and Profit?
Speaker notes on constructing a Datalog in Clojure. https://youtu.be/U4ckAGtv_OI
The Essence of Datalog
A blogpost on constructing a simple Datalog engine in Haskell to understand its semantics.
An Archaeology Inspired Database
A blogpost on building a database with Datalog in Clojure in less than 500 lines of code. h/t Karsten Schmidt
From Datalog Rules to Efficient Programs with Time and Space Guarantees
An article on transforming Datalog queries for maximum efficiency in time and space dimensions.
h/t William Benton
A relatively simple Datalog engine in Rust
Books
Foundations of Databases / Alice Book
Foundations of deductive databases and logic programming
To Investigate
History of Datalog
I kind of know that Datalog have Horn Clauses as their primitives but need to investigate exactly how they figure in terms of representation and generality in logic. What kind of logic are they capable of expressing with them? What kind of lattice/structure is their underlying model? What does this preclude / exclude? How does Blake Canonical Form link with Horn Clauses? Is minimization of boolean algebra somehow related to unification?
Research Materials
Logic and Lattices for Distributed Programming
Programming with Abstract Data Types (1974)
Barbara Liskov, Stephen Zilles
On Understanding Data Abstraction, Revisited (2009)
William Cook
Slides: http://web.cecs.pdx.edu/~black/OOP/slides/Cook%20on%20DataAbstraction.pdf
Seymour Ginsberg
Ginsburg later in his life got interested in Datalog and Object Histories. It could be worthwhile to investigate what he was up to.
Recursive queries
Differential Dataflow
Tabling as a Library with Delimited Control
Use of continuations for enabling tabling support in Prolog
Complexity and Datalog
https://iccl.inf.tu-dresden.de/w/images/3/33/DBT2016-Lecture-10.pdf https://www.scottaaronson.com/democritus/lec19.html
Material on Data Integration from Stanford
http://logic.stanford.edu/dataintegration/
Extension of a Datalog Reasonerwith Top-Down Evaluation
Doop
https://plast-lab.github.io/doop-pldi15-tutorial/
Soufflé
Dedalus
Papers:
Dedalus: Datalog in Time and Space
Bloom
Talks by Peter Alvaro:
I See What You Mean
Bloom: Disorderly Programming for a Distributed World
Datafun
Datafun: a functional query language
Interesting use cases
Type checker
Automatic Type Inference via Partial Evaluation
Datalog Typechecking
Formulog
Programming Synthesis
Constraint-Based Synthesis of Datalog Programs
Syntax-Guided Synthesis of Datalog Programs
Disassembly
Datalog Disassembly
Repo
Application in Neural Networks
Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification
Linked Data
Linked data, triple store, and the RDF movement in the web space is well worth understanding to know how it evolved and failed to garner the traction to become mainstream. I feel there’s some good work done in this field.
Linked Data Book
Book on the ethos of linked data. h/t Karsten Schmidt