Year: 2015

Summary

The key goal for the LogicBlox system is to reduce software development (and this is inSIGMOD!) and they achieve this by extending the fun

Design

On the high level:

In order to support sophisticated analytical applications, we have expanded our notion of “database system” to include features and capabilities commonly found in programming languages, spread- sheets, statistical systems, and mathematical optimization systems.

To this end, they propose:

  • T1: Simple, declarative, and uniform language.
  • T2: Clear and easy to understand semantics.
  • T3: Incrementality: incremental materialized view maintenance (think reactive programming and data binding), they use transaction repair to actually implement.
  • T4: Immutability: purely functional data structures. This works nicely with versioning, no need for locking, no cache invalidation needed, and free time-travel or transaction log — aborting means dropping the reference.

Languages

The language consists of the following components:

  • predicates
  • derivation rules: (recursive) view definitions, aggregations
  • integrity constraints: specify the set of legal database states
  • reactive rules: make and detect changes.

Implementation

  • Branching and persistent data structures: since the system provides extensive versioning and function programming style immutability, efficient diffing and branching is critical for overall performance.
  • Incremental maintenance: use sensitivity indices to help identify the parts that needs to be reevaluated. This is done via leapfrog triejoin.
  • Live programming: this could improve programmer experience but is very non trivial to implement with large data sets. This is implemented via a “meta-engine” where a normal engine parses a program as an execution graph, and the meta engine is activates when the execution graph changes and incrementally maintain the result.
  • Transaction Repair: the goal is to support concurrent write-transactions — there is another paper that goes into detail of how this is done. I think it is a fancier merge function with timestamp ordering.