gdritter repos datalog / master spec.md
master

Tree @master (Download .tar.gz)

spec.md @master

9490873
 
 
 
 
0effdb0
 
 
 
 
 
 
 
 
 
 
 
9490873
 
0effdb0
9490873
 
0effdb0
 
9490873
 
0effdb0
9490873
 
0effdb0
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9490873
 
0effdb0
9490873
 
0effdb0
 
9490873
 
0effdb0
 
 
9490873
This is a slightly different Datalog variant implemented as an
efficient, FFI-friendly Rust library. The major deviation from
standard Datalog is the existence of a simple type system for rows as
well as a choice of tuple- or record-structured data.

# Deviation 1: Record-Structured Data

Any place where Datalog uses tuple-structured data (i.e. where you
have comma-separated expressions in between parentheses) you can also
use record-structured data, which allow fields to appear in any
order. So the classic example

```
- parent ( terry, austin ).
```

can be expressed nearly equivalently using record-structured data as

```
- parent { parent: terry, child: austin }.
```

Similarly, a query to find all the children of `terry` could be
written as

```
- parent { parent: terry, child: X }?
```

# Deviation 2: Static Types

Datalog facts are usually dynamically typed, but this implementation
requires (in part to support the syntax above) that facts and
predicates have a consistent statically known type. For facts, this
often involves a "table declaration" which dictates the structure of
all future facts in that table. Some table declarations might look
like

```
- @table edge ( integer, integer ).
- @table parent { parent: atom, child: atom }.
```

Queries also have static types, but these can _generally_ be inferred
from context in Datalog, and so do not need to be defined. If
necessary, though, a `query` definition can be used.

```
- @query ancestor { parent: atom, child: atom }.
- ancestor { parent: X, child: Y}
    :- parent { parent: X, child: Y }.
- ancestor { parent: X, child: Y}
    :- parent { parent: X, child: Z},
       ancestor { parent: X, child: Y }.
```

# Deviation 3: Implicit Variables

When defining a table's type signature, we can also include a few
extra annotations about the meaning of that variable. For example, we
might want a particular field of a table to be an auto-incrementing
integer, so that every row would include a fresh value without us
having to discover it first. If we define a table with the
`@autoincrement` keyword, like so

```
- @table person { id: integer @autoincrement, name: string }.
```

then we can use the placeholder `@auto` value, which mean Datalog will
examine the table to find the necessary "next" value.

```
- person { id: @auto, name: "alice" }.
- person { id: @auto, name: "bob" }.
- person { id: @auto, name: "carol" }.
```