Dedalus: Datalog in Time and Space

---

There is an interesting talk related to this paper[1].

This paper introduces the idea of creating a Datalog-derived language which allows specifying when a as well as what.

In this paper, the authors extend datalog atoms by appending temporal information.

p(1,2)@101; 

Would be a fact at time step 101.

This temporal suffix allows ordering facts so that changes can be explicitly reasoned about through time. This allows the creation of rules which enforce temporal relations between facts. To make this simpler, Dedalus explicitly forbids refering to more than one time suffix in the body of rule, and limits rules to the current or next timestep.

In the context of modeling a data structure like a distributed queue, this makes sense. The big issue that needs to be solved is to provide rules that coordinate changes to the system so that they happen in an order that makes sense. As such, the current step and next one are the only ones that are required.

This strategy makes this type of modeling signifigantly simpler because, syntatic sugar asside, it is completely within the recognized semantics of datalog. Previous efforts have added to datalog's semantics which brings additional complexity.

However, the limitation to the current and present timestep hides a lot of the potential of this approach.

Dedalus is certainly as inspiration for Datomic which extends the idea into a general database system.

Where one could create an EAV store from triples:

(entity, attribute, value)

Datomic is built on quads:

(transaction, entity, attribute, value)

Where Dedalus appends, Datomic prepends.

A datomic database also addresses cases explicitly forbidden by Dedalus. For example, transactions can be freely used in joins.

Bonus

© Ethan Soutar-Rau. Site proudly generated by Hakyll