What Is Datalog?

Datalog is a declarative programming language that originated as a query language for deductive databases in the late 1970s. It uses a syntax rooted in Prolog and is built on first-order predicate logic with Horn clauses. In Soufflé, Datalog programs describe what to compute — relations and rules — rather than how to compute it. The Soufflé engine then synthesizes a parallel C++ program from the specification.

Relations

Relations are the central data structure in Soufflé Datalog. Each relation represents a set of tuples, and relations can be declared as input (extensional database, or EDB), output, or intermediate (intensional database, or IDB). A relation declaration specifies its name and the types of its attributes.

.decl edge(x:number, y:number)
.decl path(x:number, y:number)

Types

Soufflé enforces a static type system at compile time. The two primitive types are symbol and number. Users can define custom base types, union types, and domains to model domain-specific values. Type checking catches mismatches before synthesis, helping ensure correctness in large analysis specifications.

.type Node <: number
.type Color = Red | Green | Blue

Type Definitions

Type definitions in Soufflé support sub-typing via <: and union types via =. Base types can be constrained to a range of numbers or a set of symbols. These definitions appear at the top of a Datalog program and inform the compiler's type inference across all relation declarations and clause bodies.

Clauses

Clauses (rules) express logical inferences. A clause has a head — a single relation atom — and a body consisting of one or more literals joined by commas (conjunction). Soufflé supports stratified negation, meaning negated literals are permitted as long as the program contains no cycles through negation.

path(x, y) :- edge(x, y).
path(x, z) :- edge(x, y), path(y, z).

The first clause is a base case; the second is a recursive rule that computes the transitive closure of edge.

Identifier Naming & Pre-processing

Relation and variable names must begin with a letter and may contain letters, digits, and underscores. Soufflé's pre-processor supports C-style comments (// and /* */) and #include directives for composing larger programs from multiple source files. Identifiers are case-sensitive.