Introduction

This is the technical reference guide for the Rel language. For an introduction to Rel, see the Rel Primer and the Rel concept guides.

Rel is a declarative, relational modeling language.

Rel is “relational”, because its constructs are geared towards expressing relations, as well as relationships between relations.

Rel is a declarative language, because you can understand the meaning of a model expressed in Rel by reading it statically. You need not – and often cannot – know the details of how it is evaluated on a computer.

Another important characteristic of a declarative language is that a variable does not represent a memory location whose content can be changed. Instead, a variable in a declarative language is very much like a variable in mathematics. For example, to answer the question “If containers cost 13 dollars each, how many can you purchase with a budget of 400 dollars?”, a mathematics student would write an inequality like 13x ≤ 400. The variable x represents the number of containers purchased, and the inequality represents a constraint on the value of x.

In many imperative programming languages (C, Python, etc.) x = x + 1 is an assignment statement that increases the value of variable x by one. In a declarative language, by contrast, x = x + 1 is either not admissible or just a complicated way of writing false — because for any number x, the equality x = x + 1 does not hold.

The underlying computational model of Rel is inspired by first-order logic, in particular by implications that specify relations in terms of other relations.

A typical example of such an implication is sibling(x, y) <= x ≠ y, parent(x, z), parent(y, z). This means “for all x, y, and z, sibling(x, y) is implied by x ≠ y and parent(x, z) and parent(y, z),” or, equivalently, “for all x and y, if there exists a z such that x ≠ y and parent(x, z) and parent(y, z), then sibling(x, y).” The most likely intended meaning of this implication is that two distinct individuals (x and y) are siblings if they have a common parent (z).

Such an implication can be treated as a recipe for computing the relation sibling. You can think of it as an implicit iteration over all the values of x, y, and z that satisfy parent(x, z) and parent(y, z). If x ≠ y also holds, then a pair consisting of the values of x and y is included in sibling.

Notice that the implication above succinctly expresses what it means to be a sibling. If you are given the relation parent, then you know that relation sibling will be computed correctly. The implication does not specify how exactly the computation should be performed. To do this in an efficient way is the responsibility of the system, not of the person who formulated the rule.

In Rel, this example could be written as follows:

def sibling(x, y) {
    exists(z: x != y and parent(x, z) and parent(y, z))
}

It must be stressed that Rel is richer, more expressive, and easier to use than the language of logical implications described above.

Next: Values