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

Blogpost

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.

prathyvsh/database-readings