• Rel
• REFERENCE
• Rel Language

# Rel Language Reference

Reference Guide for the Rel language.

## Introduction

This is the technical reference guide for the Rel language. For an introduction to Rel see the Rel Primer and our Rel Concept Guides.

Rel is a declarative, relational modeling language.

We say that the language is “relational”, because its constructs are geared towards expressing relations, as well as relationships between relations: this will be explained in more detail in the remainder of this document.

Rel is a declarative language, because the meaning of a text written in Rel can be understood by reading it statically: we 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. A variable is, rather, very much like a variable in mathematics. For example, a mathematics student would write an inequality like 13x ≤ 400 to answer the question “If containers cost 13 dollars each, how many can we purchase with a budget of 400 dollars?“. The variable x represents the number of containers purchased, and the inequality represents a constraint on the value of x.

To give another example, 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).

In the remainder of this manual, paragraphs written in italic font contain additional explanations that might be helpful for some readers, especially those with an academic background or a deeper interest in various aspects of computer science. It is not necessary to read or understand them: they can be safely ignored.

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 individuals (x and y) are siblings if they have a common parent (z).

Notice that the above implication succintly expresses what it means to be a sibling. If we are given the relation parent, then we know that relation sibling will be computed correctly: how it will be computed is of no interest to the person who formulated the rule. (The “how” is, of course, not entirely uninteresting, because the computation must be reasonably efficient.)

In Rel our 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.

## Values

Every value in Rel is a first-order relation. We write tuples as values separated by commas (v1, v2, ...), and write relations as tuples separated by semicolons (;) and wrapped in curly braces ({}). For example:

{(1, 2); (3, 4); (5, 6)} is a relation with arity 2 and cardinality 3. It can be visualized as the following table:

 1 2 3 4 5 6

{(1, 2, 3); (4, 5, 6)} is a relation with arity 3 and cardinality 2. It can be visualized as the following table:

 1 2 3 4 5 6

{(1); (2); (3); (4)} is a relation with arity 1 (a unary relation) and cardinality 4. It can be visualized as the following table:

 1 2 3 4

We typically leave out the parentheses for unary relations, so this relation can be written as {1; 2; 3; 4}.

The purpose of this first section is mainly to explain what notation we use for values computed by Rel; but the notation is also supported by the Rel language itself.

In Rel, the parentheses of the tuple are in general optional because , is an operator and it binds more strongly than the ; operator (see Comma and Semicolon). Just as in many other languages, tuples with a trailing comma are allowed, as in {(1,); (2,); (3,); (4,)}.

As mentioned above, every value in Rel is a first-order relation. This means, in particular, that:

• Relations cannot contain relations. Relations can contain simple values such as integers, floating-point numbers, fixed-point decimals, characters, dates, datetimes, etc. Some of the values — dates, for instance — have internal structure, but each of them has a fixed size. The Rel system is designed to support values of arbitrary fixed-size Julia types.
• A stand-alone simple value, such as an integer or a string, is always a trivial relation containing one unary tuple. For example, 5 outside a tuple is just a shorthand notation for {(5,)}. Similarly, "what?" outside a tuple is equivalent to {("what?",)}.

### Variables, Trivial Relations and Simple Values

Note: This subsection is for the curious. You may safely skip it. Before reading, you might want to acquaint yourself with the rest of the manual, in particular with section Relational Application.

A variable normally represents some simple value, that is, a trivial relation.

In the interest of convenience, conversion between trivial relations and simple values is often carried out behind the scenes. Consider, for instance, the following:

// query

def output(x, y, z) = {(3, 4)}(x, y) and z = x + y and equal(z, {(7,)})

In the example above there are several instances of such conversions:

• In {(3, 4)}(x, y) the simple values 3 and 4 are extracted from the tuple (3, 4) and converted to trivial relations. The variable x now represents {(3,)} and y represents {(4,)}.
• In z = x + y the simple values 3 and 4 are extracted from x and y and added. The result is converted to the trivial relation {(7,)} represented by z.

Notice that z is, indeed, a relation, because equal(z, {(7,)}) evaluates to true, and equal is defined only for relations.

### Terminology

TermExplanation
ArityNumber of elements in the tuples of a relation, if each of them contains the same number of elements. In general a relation need not have a fixed arity.
CardinalityNumber of tuples in a relation (size).
RelationA relation of any cardinality, arity, and with any properties. Every relation is a set of tuples, but the tuples may have different arities. Some relations are also functions.
FunctionRelation with a functional dependency from the initial elements of a tuple to the last element.
Empty relationRelation of cardinality 0 (any arity).
TupleOrdered list of values. A relation of cardinality 1 (any arity) is often identified with the tuple that it contains, and vice-versa.
SetA set whose elements are of primitive types is represented by a relation of arity 1 (unary relation).
Nullary relationRelation of arity 0. Nullary relations can only have cardinality 0 or 1. Nullary relations can be thought of as representing the boolean values true and false. See section Boolean Constant Relations for a discussion of how this fits in the language design.
Unary relationRelation of arity 1.
Binary relationRelation of arity 2.
Ternary relationRelation of arity 3.
N-ary relationRelation of arity n.
SingletonRelation of cardinality 1 and arity 1.
Derived relationA derived relation is a relation defined by a computation over derived and base relations. Derived relations may be persisted or not, because they can always be recomputed from data that is already in the database. This corresponds to the definition of a view in SQL.
Base relationA base relation has to be stored in the database because it is not defined by a computation. This corresponds to a table in SQL.

## Lexical syntax

Rel uses /* ... */ for block (multi-line) comments and // ... for end-of-line comments.

### Identifiers

An identifier is a sequence of any Unicode letter or underscore, followed by zero or more Unicode letters, underscores, or numbers.

Identifier := ("^")? IdCharInit IdChar*
IdCharInit := [a-zA-Zα-ωΑ-Ω_]
IdChar     := [a-zA-Zα-ωΑ-Ω_0-9]

For example, valid identifiers are: x, a1, b1c, θ, φ, Σ, ß, β1, β2, ^V.

The optional caret character (^) can appear only at the beginning of an identifier. Identifiers beginning with a caret are used for naming some relations that are automatically generated by Rel. See, for example, the concept guide about Value Types. It is best to avoid using such identifiers for other purposes.

Due to missing features in the parser generator we use, the definition explicitly lists supported ranges of Unicode letters (hence the Greek ranges). This is currently incomplete, so we do not yet support other Unicode letters in identifiers.

Some identifiers are keywords, that is, they are reserved for signifying various constructs in the language. All other identifiers can be used to name relations and variables.

### RelNames

RelName := ":" Identifier

A RelName has the form of an identifier prefixed with a colon: for example, :something. The symbol represents itself, that is, it is a literal. It cannot be used to name a relation or a variable.

The term RelName is an abbreviation of “relation name”. Its use is justified by the fact that RelNames can be used to tag the representations of relations embedded in modules. But this is by no means the only application of RelNames. They can be used, for instance, to represent units of measurement in value types.

To check whether the value of a variable is a RelName, you can use the library function RelName. You can also strip off the initial colon and convert the result to a string by using the library function relname_string.

A RelName can be formed directly from a string literal, even if the string is not an identifier:

// query

def output[:"a b"] = :"c d"

Notice, however, that string interpolation is not allowed in a string literal that is used to form a RelName in this manner.

If the strings are not literals, but are extracted from a relation, the corresponding RelNames can be formed by using specialization:

// query

def p = 1; 2
def q = "a%p"; "b%p"
def output = #(q)

### Infix symbols

Infix symbols that are not defined in the Rel libraries are available to be user-defined: ⊗, ⊙, ⊕, ⊔, ⊓, ∼, ≼, ≽, ≺, ≻, →, ←, ≈ .

For example:

@inline def (≈)(a, b) = a + 1 = b
def output = 1 ≈ 2

Note: the infix ∼ used in alglib.rel (Unicode 8764) is not the same character as your keyboard’s ~ (Unicode 126).

These symbols can also be useful as higher-order relational arguments, as this example from alglib.rel shows:

@inline
def unary_relation(D, ∼) =
equal(arity[∼], 1)

## Declarations

### Definitions

Definitions give names to computed relations.

#### General Forms

Declaration :=
Annotation* "def" Id FormalParamsBracket* FormalParamsParen? "=" Expr
Annotation* "def" Id FormalParamsBracket* FormalParamsParen? "{" Expr "}"

Id = Identifier (Relname)*

FormalParamsBracket = "[" FormalParameterSpecification "]"
FormalParamsParen   = "(" FormalParameterSpecification ")"

Both forms of declaration are equivalent.

The part consisting of the name and the optional bracketed or parenthesized formal parameter specificationss is often called the head of the definition. The expression after = (or between { and }) is often called the body of the definition.

A definition can be read as “the head is implied by the body”.

See section Annotations for a discussion of the optional annotations. An unannotated definition of a relation will often cause the relation to be materialized, that is, its representation as a set of tuples is computed and stored. If the definition of a relation R depends on other relations, then R is automatically and incrementally updated whenever those relations change. This update process is referred to as maintenance.

There are some exceptions to the above rule, especially when the Rel system can determine that an infinite relation is meant to perform some simple computation. For instance, the following simple definition will be inlined by the backend of the system. From the user’s perspective, the effect will be as if the definition were annotated with @ondemand or @inline:

def P(x, result) {result = x * x}

The name that follows def can contain RelNames: for example, name:label. This is just convenient notation for a definition with square brackets. Note that def name:label is equivalent to def name[:label], def person:address:city is equivalent to def person[:address][:city] etc.

// query

def person:address:city = ("John", "Tampa"); ("Amy", "Duluth")
def output = person

See the end of section Examples of Definitions for more information about using square brackets.

In this manual the variables introduced in the formal parameter specifications of a definition will be referred to as parameters. The expressions used in the corresponding positions of relational applications will be referred to as arguments.

#### Examples of Definitions

ExampleDescription
def five = 5five is a unary, singleton relation {(5,)}.
def numbers = {1; 2; 3; 4}numbers is a unary relation.
def first_four = numbersThe same relation can be given several names.
def grandparent = a, b: ∃(t: parent(a, t) and parent(t, b))grandparent is a binary relation. See Relational Abstraction.
def grandparent(a, b) { ∃(t: parent(a, t) and parent(t, b)) }grandparent is a binary relation.
def netsales[x, y, z] = sales[x, y, z] - returns[x, y, z]Assuming sales and returns have arity 4, netsales has arity 4. See Partial Relational Application.

Note that in Rel any constant or variable can be used as a relation. For example, in def pi = 3.14 the value of pi is the singleton relation {(3.14,)}.

Definitions are similar to views in SQL, though Rel has fewer restrictions on what computations are supported in a view.

It is worth noting that the following two definitions are equivalent:

def binomial(x, y, z) { z = x * x + y }
def binomial[x, y] = x * x + y

The section Partial Relational Application contains more information about the square brackets syntax.

#### The Many Ways to Write a Definition

In the examples given so far, the head of each definition was either without formal parameter specifications or had formal parameter specifications that are just the names of parameters. In general, a formal parameter specification can be any binding, with two exceptions:

1. A string in the head of a definition cannot feature string interpolation.
2. A binding with where cannot appear in the head of a definition.

In each of the following three examples, all the definitions are equivalent. In some cases the body is a relational abstraction.

def pair = 1, "a"
def pair(1, "a") = true
def pair(1, x) {x = "a"}
def pair = "a" : true
def pair("a") = true
def pq(x in p, y in q) = x < y
def pq(x, y) = p(x) and q(y) and x < y
def pq = x in p, y in q : x < y
def pq = x, y : p(x) and q(y) and x < y
def qr(x in q) = r(x, _)
def qr = x in q where r(x, _) : true
def qr = x : q(x) and r(x, _)

The formal parameter specifications in the head do not provide any additional expressive power. It is always possible to write the definition of a named relation in such a way that the head consists only of the relation’s name. However, using formal parameter specifications can often make the definition easier to read.

For instance, the relation binomial shown in one of the examples in section Examples of Definitions could be defined as follows:

def binomial = x, y : x * x + y

The intention is to use this relation for computing the value of the formula, for example, by writing binomial[7, 3.0] to obtain the value 52.0. Given this intention, the preferred form of the definition is:

def binomial[x in Number, y in Number] = x * x + y

#### Multiple Definitions

If there is more than one definition of a relation with a given name, then the resulting relation is a union of the relations defined in each of the definitions. This is quite natural, because — as mentioned above — each definition can be read as “the body implies the head”.

Here is a very simple example:

// query

def five = 5
def seven = 7
def five = 6
def output = five

It is recommended that multiple definitions for the same name be kept together and not separated by other definitions.

However, it is important to note that the definitions of library functions are in the same name space as your own definitions. So if you happen to define a relation that has the same name as a library function, the results may be surprising:

// query

def abs[x] = -x
def output = abs

It is also possible that some of your own relations may at some point be modified when a new relation is added to the library. These problems will disappear in the near future, when libraries will be wrapped up in modules. In the meantime, you can avoid them by writing your own definitions in modules, which is also good practice for other reasons.

### Entities

See the Entities concept guide for an introduction to using entities in Rel.

## Expressions

### Formulas

Formulas are expressions that evaluate to either true or false. In Rel true and false are zero-arity relations: see Boolean Constant Relations. So the values of formulas, just like the values of other expressions, are relations.

Formulas are often used not only for their values, but also for their effects on variables. For example, if P and Q are unary relations, then the formula P(x) and Q(x) constrains the variable x to be a member of both P and Q. The formula will evaluate to false only if there are no such common members.

Sometimes a formula cannot be evaluated. For example, the formula forall(x in Int : exists(y in Int : y = x + 1)) cannot be evaluated, because its variables are bound to infinite sets. In such cases Rel will typically provide an informative error message.

Formulas are the core of the Rel language. This means that other constructs are compiled to formulas.

Just as in first-order logic, a formula with free variables cannot be true or false. In this context it is worth knowing that variables appearing on the left-hand side of a definition are implicitly universally quantified. This is also the case for variables that appear in the “bindings” part of a relational abstraction.

For example, def P(x, y) = Q(x) and R(y) should be read as “for every x and y, x and y are in relation P if x is in relation Q and y is in relation R“.

To give another example, in def P(x) = Q(x, y), the variable x is universally quantified, but y is free, so the compiler will complain about y being undefined. This can be fixed by quantifying it explicitly: def P(x) = exists(y : Q(x, y)). A more convenient solution is to use an anonymous variable: def P(x) = Q(x, _). The identifier _ represents a fresh variable that is implicitly existentially quantified.

Note: In the example above it was assumed that y is a variable. It could also be a relation: see section Relational Application.

#### Relational Application

Expr := Expr "(" (Expr {"," Expr}*)? ")"

A relational application is sometimes referred to as an atom. It should not be confused with a partial relational application.

The first expression denotes a relation. The other expressions, if any, are the arguments. They often correspond to the parameters of a definition or of a relational abstraction.

The arity of the resulting expression must be 0. For example, if the arity of P is 3, then in P(x, y, z) all three arguments are necessary. The formula P(x, y) would evaluate to false because there is no binary tuple in P.

Note, however, that in general the same relation name — P, say — may be used for several relations, each of which has a different arity. In such cases P is sometimes called a relation without a fixed arity, and it may very well happen that both P(x, y, z) and P(x, y) evaluate to true.

Examples
age("Martin", 39)
parent(x, y)
foo()

The section Partial Relational Application introduces a syntax with square brackets that supports partial application of a relation. For example, age["Martin"] has the value {(39)}.

A name that consists of an identifier immediately followed by one or more RelNames is shorthand for a partial relational application. For example, person:address:city(x, y) is equivalent to person[:address][:city](x, y), which is equivalent to person(:address, :city, x, y).

Some relational applications can be expressed with infix operators. For example, {{5,)}(x) can be written as x = 5, and add(x, y, z) as z = x + y.

An expressions such as x = y is also a relational application. It is syntactic sugar for eq(x, y).

There is also a special form of relational application, x in P, which is conceptually — though not syntactically — equivalent to P(x). See section Bindings for more information.

##### Grounded Variables

A variable v is said to be grounded when the Rel system can determine that v represents an element of a finite — possibly empty — set of values.

If a variable is not grounded, some error messages may inform you that it is “not ground” or “not bound”. These differences currently indicate whether the error was detected by the front-end compiler (“not bound”) or by the back-end optimizer (“not ground”). All these terms refer to the same concept. The term used in this manual is “ungrounded”.

Relational application is the only mechanism through which a variable x can be grounded. If x occurs as an argument of a finite relation, it thereby becomes grounded. If x occurs as an argument of an infinite relation, it will be grounded if there are enough other grounded arguments to make x an element of a finite set. For example, if x occurs only in x = y, then it is grounded if and only if y is grounded. Other examples will be shown below.

Relations such as Int are considered infinite, even though, strictly speaking, they are not. So x in Int or Int(x) does not ground x.

In the following two examples, x and y are grounded. In the first example both variables occur in relational applications of finite relations. The equality is just an additional constraint. In the second example x is grounded by a relational application of a finite relation, and y is grounded by x = y.

// query

def P {1; 2; 3}
def Q {2; 4; 6}
def output(x, y) {x = y and P(x) and Q(y)}
// query

def P {1; 2; 3}
def Q {2; 4; 6}
def output(x, y) {x = y and P(x)}

In the example below, neither x nor y is grounded, so an error will be raised:

def P {1; 2; 3}
def Q {2; 4; 6}
def output(x, y) {x = y}

The necessity to make variables grounded may make seemingly equivalent models behave differently. For instance, x is grounded here:

// query

def output(x) = {-2; -1; 0; 1; 2}(x) and -2 < x < 2

However, in the following x is ungrounded, which is an error:

def output(x) = Int(x) and -2 < x < 2

Here is a slightly more complicated example:

// query

def small_int = -2; -1; 0; 1; 2
def binomial[x in small_int, y in small_int] = x * x + y
def output(x, y, z) = binomial(x, y, z) and z = -1

Notice that the example above worked, because x and y were constrained to be members of the finite set small_int. If they were not so constrained, there would be an error:

def binomial[x in Int, y in Int] = x * x + y
def output(x, y, z) = binomial(x, y, z) and y = -1 and z = -1

However, the following is fine:

// query

def binomial[x in Int, y in Int] = x * x + y
def output(x, y, z) = binomial(x, y, z) and x = -1 and z = -1

The reason this example works is that z = x * x + y is syntactic sugar for multiply(x, x, v) and add(v, y, z). The relation add is infinite. However, when the last argument of add is grounded and one of the first two is not, the compiler rewrites add to sub: add(v, y, z) to sub(z, v, y) in this case. For each pair of values z and v there will be a finite number — namely: one — of possible values for y that satisfy sub(z, v, y).

In the case of multiply the situation is, in general, not so simple, because multiply(v, w, 0) would have an infinite number of solutions, even if one of the variables — v or w — were grounded. So a rewriting to divide is not applied in the previous example.

See also the description of annotations @inline and @ondemand in section Annotations.

##### Less Conventional Forms of Relational Application

Note: Most users of the language need not be aware of the details described in this section.

Recall from section Values that a free-standing simple value represents a trivial relation, and that, accordingly, the value of a variable is also such a relation.

Since an expression such as {(5,)}(x) is a relational application, so is 5(x). Such an application constrains the value of x to be 5, that is, {(5,)}. So it stands to reason that x(y) is also a relational application. It has the same semantics as x = y, and the latter form is the one that is the most frequently used.

For reasons of general symmetry, x(5) is also a relational application, one that can ground x, just as x = 5.

In general, if p is a relation and x is a variable, then the following expressions are equivalent:

• p(x)
• x(p)
• p = x
• x = p

The above applies also if p is a grounded variable. If x is otherwise ungrounded, then each of these expressions will ground it.

// query

def P = 1; 3; 5; 6
def Q = 2; 3; 4; 6; 8
def output(x, y, z) = P(x) and Q(y) and x(y) and z(x)

As noted above,5(x) is a valid relational application, regardless of whether this is the only relational application that grounds x. If x is also grounded for other reasons, for instance as in 5(x) and 6(x), then 5(x) is an application of a relation to a relation. The principle of referential transparency requires that 5(6) — in other words, {(5,)}({(6,)}) — also be a relational application. By the same token, given the definitions def P = 5 and def Q = 6, the expression P(Q) must be a valid relational application.

It would not do to require that an application of a relation to a relation be restricted only to trivial relations. Indeed, in the case of P(Q) such a restriction might be difficult to enforce at compile time. For general relations P and Q the meaning of P(Q) is a natural extension of that for trivial relations. P(Q) is equivalent to exists(x, y : P(x) and Q(y) and x(y)). In other words, the expression evaluates to true if and only if the intersection of P and Q is not empty.

Similar considerations apply to relations with arity greater than 1. For instance, if P is a binary relation, and both Q and R are unary relations, then the application P(Q, R) is equivalent to exists(x, y : P(x, y) and Q(x) and R(y)).

#### Conjunction

Expr := Expr "and" Expr

This construct is logical conjunction. Evaluates to true if an only if the left and right expression evaluates to true.

The arguments of and must be formulas (arity 0).

Examples
flying(x) and mammal(x)

The comma operator (introduced later) can be used instead of and, but is more general: it does not require arity-0 arguments as and does. Due to this, the and syntax can help catch mistakes and disambiguate overloaded logic. The arity of expression e1, e2 entirely depends on the arity of e1 and e2 (it can be any arity). On the other hand, the arity of e1 and e2 is always 0. If e1 and e2 are used with an incorrect assumption of their arity, then and will give an error, while , will not.

The possible uses of e1 and e2 are:

e1e2e1 and e2
falsefalsefalse
falsetruefalse
truefalsefalse
truetruetrue

#### Disjunction

Expr := Expr "or" Expr
Examples
flying(x) or floating(x)

The possible uses of e1 or e2 are:

e1e2e1 or e2
falsefalsefalse
falsetruetrue
truefalsetrue
truetruetrue

The semicolon operator is a generalization of or, just like the comma operator is a generalization of and (see Section Semicolon (Union and Disjunction)). The semicolon operator is disjunction (like or) for arity 0, and union for relations of an arity bigger than 0. The section about the semicolon operator explains exactly how this matches the semantics of or.

#### Implication

Expr := Expr "implies" Expr

Implication e1 implies e2 is defined as (not e1) or (e1 and e2)

The possible uses of e1 implies e2 are:

e1e2e1 implies e2
falsefalsetrue
falsetruetrue
truefalsefalse
truetruetrue

#### Negation

Expr := "not" Expr
Examples
not mammal(x)

Just like for the other logical operators, the argument of not must be a formula (an arity-0 relation).

The possible uses of not e are:

enot e
falsetrue
truefalse

#### Boolean Constant Relations

Expr := "true"
| "false"

The constants true and false are relations, not scalar values. The constant true is equivalent to {()}, which is the zero arity relation containing its only possible value, i.e., the empty tuple. The constant false is equivalent to the arity-0 relation {}—the empty set. These are the only two relations of arity 0.

Because true and false are relations, there is never a relation persisted in the database that has true or false occurring as a value in the tuples (otherwise that relation would not be first-order). The Rel compiler statically eliminates any occurrences of true and false according to the laws of the language.

#### Comparison Operators

Expr := Expr "<" Expr
| Expr ">" Expr
| Expr "=" Expr
| Expr "!=" Expr
| Expr "≠" Expr
| Expr "<=" Expr
| Expr "≤" Expr
| Expr ">=" Expr
| Expr "≥" Expr

Comparison operators are translated into applications of infinite relations defined in the standard library. For example, e1 = e2 is translated to eq(e1, e2).

Examples: x < 5, x > 5, x != 0.

### Conditional Expression: If-Then-Else-End

Expr := "if" Expr "then" Expr "else" Expr "end"

The condition must be a formula (an arity-0 expression).

If the condition is true, then the value of the expression is the then branch. Otherwise the value is the else branch. The then and else branches can have arbitrary arity.

The semantics of conditional expressions is:

|[ if e1 then e2 else e3 end ]| => |[ (e1, e2); (not(e1), e3) ]|

Examples:

if 1 < 2 then 'a' else 'b' end

gives (‘a’,).

def p = 1
def q = 2,3
def r = 4,5
def output = if p(1) then q else r end

gives (2, 3).

def output = if p > 1 then q else r end

gives (4, 5).

def p = 1; 2; 3
def output = if x = 1 then 'a' else 'b' end for x in p

gives

(1, 'a')
(2, 'b')
(3, 'b')

### Constants

Constants in Rel are semantically equivalent to singleton relations (arity 1, cardinality 1). In Rel, the value of every expression is a relation, and this includes constant expressions. For example, the value of the constant 1 is {(1)}.

Note that true and false (see Section Boolean Constant Relations) are arity-0 relations.

#### Integer Constants

Examples: 1, 2, 3

#### Floating-point Constants

Expr := [0-9]+ "." [0-9]* exponent?
| [0-9]+ exponent
| "." [0-9]+ exponent?

decimalDigit  := /[0-9]/
decimalDigits := decimalDigit+
exponent      := ('e' | 'E') ('+' | '-')? decimalDigits

Examples:

• 0.0
• 3.14
• 1.5e4
• 1e10
• 5e-4
• 5e+4
• .5e4

#### Character Constants

Character constants are enclosed by single quotes. The characters are Unicode characters.

Examples: 'c' and '文'.

#### String Constants

String constants are constant sequences of characters.

As described in section String of Rel Data Types, the number of characters in a string is computed by num_chars. The characters are indexed from 1, and can be accessed by char.

For example, num_chars["中文例子"] = 4 and char["中文例子", 2] = '文'.

A string constant can be written in one of three different forms, described below.

##### Strings in Single Double Quotes

A string constant can be enclosed in double quotes: for example, "a string".

The backslash (\) is an escape character that can be used to specify characters that would normally be illegal in a string, or difficult to input or see. The most frequently used cases are listed below:

• The sequence \" represents a double quote character.
• The sequence \n represents a newline.
• The sequence \t represents a tab character.
• The sequence \\ represents a single backslash character.
• The sequence \% represents the character %, when it is not to be interpreted as beginning string interpolation.

In general, the conventions are as in Julia. It must be noted that, unlike in some other languages, an unrecognized escape sequence — such as a backslash followed by a space — is illegal and will cause the compiler to report an error.

Example:

def quote = "\""
def output = i, c : char[quote, i, c]

quote will have length 1, and the output will be (1, ").

##### Strings in Triple Double Quotes

A string constant can also be enclosed in triple double quotes: for example, """a string """. This form of a string constant can span a number of lines.

// query

"""A multi-line
"string"
constant"""

The example shows that there is no need to escape a double quote inside a triple-quoted string, unless the double quote is followed by at least two unescaped double quotes. So, for instance, the string """" """ contains a quote followed by a space, but to obtain a space followed by a quote in a triple-quoted string you must write """ \"""".

For convenience, a newline that is written immediately after the opening """ will be ignored. Furthermore, if the contents are indented, then the indentation will be ignored. So, the example above could also have been written as:

"""
A multiline
"string"
constant"""

The exact rules are very similar to those found in the section Triple-Quoted String Literals of the language Julia. There are two differences:

• An escape character (\) is not allowed at the end of a line.
• Rel strips away leading tabs or leading spaces, but not both.
##### Raw strings

A raw string begins with the identifier raw, immediately followed by N double quotes, where N must be an odd number. The raw string extends until the nearest occurrence of N double quotes. Everything between the opening quotes and the closing quotes is just uninterpreted text. In particular, neither the backslash (\) nor the percent sign (%) have any special meaning, and indentation is not ignored.

For example:

• The raw string raw"\" is equivalent to "\\".
• The sequence raw"\"" is not a properly formed raw string.
• The raw string raw""" " """ contains one double quote character surrounded by spaces.

The ability to use an arbitrary odd number of quotes makes it relatively easy to convert a complicated text into a single string. For instance:

raw"""""
"""A multi-line
"string"
constant"""

is equivalent to

"A multi-line\n \"string\" \n  constant" """""

The above is a single string, equivalent to the following:

"\"\"\"A multi-line\n \"string\"\n  constant\"\"\"\n\nis equivalent to\n\n\"A multi-line\n \"string\" \n  constant\" "

Note:

• The identifier raw is just a normal identifier, and can be used as, say, the name of a relation. It has special meaning only when immediately followed by a double quote.
• While the triple-quoted string """""" is empty, raw"""""" will cause the compiler to raise an error. The only way to write an empty raw string is raw"".
• Although raw strings are often quite convenient, they have their limitations. For instance, it is impossible to write a raw string that contains just one double quote, even though this can be done quite easily with the other forms of string constants: "\"" or """\"""". Perhaps more importantly, raw strings do not support string interpolation.
##### String Interpolation

Rel allows a string to be interpolated into another string, as long as the latter is not a raw string and does not occur in the head of a definition. String interpolation is introduced by an unescaped percent sign, %.

For example, "a%("b")c" is equivalent to "abc".

A more interesting example: If the value of variable v is the string "inner", then "This is the %(v) string" is equivalent to "This is the inner string".

In the case of a simple identifier, the parentheses may be omitted.

The interpolated string can be represented by an arbitrary Rel expression of arity 1, which makes this feature quite powerful. For example, assume that we have the following:

def R = (1, "one"); (2, "two"); (3, "three")

Given the above definition, the string """The number "%(R)".""" will be equivalent to "The number \"two\".".

In the context of interpolation Rel will perform conversions from other types to strings. For instance:

// query

def add_these = 1, 2; 10, 5
def output = "For example: %x + %y = %z"
from x, y, z where add_these(x, y) and z = x + y

Interpolation can be nested:

// query

def from_id = ("user_1", "Alice"); ("user_2", "Bob")
def nums = 1;2;3
def output = "Hello %(from_id["user_%nums"]) and bye"

#### Date Constants

Date constants use the ISO 8601 extended format.

Expr := [0-9][0-9][0-9][0-9] "-" [0-9][0-9] "-" [0-9][0-9]

Examples: 2021-01-01, 2100-04-03

If a Date does not exist (for example 2021-02-30 or 2020-25-01) then a warning is reported and the value of the constant is the unary empty relation.

#### DateTime Constants

DateTime constants use the ISO 8601 extended format. A timezone is required.

Example: 2021-01-01T21:00:00+00:00

Expr := Date "T" Time Timezone

Date = [0-9][0-9][0-9][0-9] "-" [0-9][0-9] "-" [0-9][0-9]
Time = [0-9][0-9] ":" [0-9][0-9] ":" [0-9][0-9]
Timezone = "Z"
| "+" [0-9][0-9] ":" [0-9][0-9]
| "-" [0-9][0-9] ":" [0-9][0-9]

If a DateTime is not valid then a warning is reported and the value of the constant is the unary empty relation.

### Relational Abstractions

#### Bindings

Bindings are the mechanism by which variables are introduced in Rel. It is often useful to immediately specify the expected domain of the new variables, and the binding syntax supports that with where and in.

Bindings := FormalParams
Bindings := FormalParams "where" Expr

FormalParams := FormalParam
FormalParams := "(" FormalParams ")"
FormalParams := FormalParams "," FormalParams

FormalParam := FormalId
| FormalId "in" Expr
| FormalId "∈" Expr
| Constant

FormalId := Id
| Id "..."

Bindings are not expressions themselves, but are used in many language constructs that are expressions. Because the syntax for bindings is somewhat elaborate, it is useful to understand it separately from the language constructs in which it is used.

Examples of bindings:

• x

• Introduces a single variable named x.
• 1

• A constant is also a binding.
• x, y, z

• Introduces three variables: x, y, z.
• x in A

• Introduces a single variable x whose domain is restricted to A.
• x ∈ A

• Equivalent to the previous example.
• x where A(x)

• Equivalent to the previous example.
• x ∈ Int

• Introduces a single variable x, with domain Int. Domains do not have to be finite.
• z in {1; 2; 3; 4; 5}

• Domains can also use literal relations.
• z in 1

• A domain can be a singleton (or even empty, but that’s not often useful).
• t where team(t) and soccer(t)

• A domain can be a more complex logical formula.
• x in A, y in B, z in C or equivalently x ∈ A, y ∈ B, z ∈ C

• Introduces three variables, where x has domain A, y has B, and z has C. A, B, and C must have arity 1.
• x ∈ Red, y ∈ Green where edge(x,y)

• in and where can be combined.
• x, y where edge(x,y) and Red(x) and Green(y)

• Equivalent to the previous example.
• x, y where edge(x, y)

• Introduces two variables x and y in the edge domain.

For the where case, the Expr must be arity 0 (a formula). The formula can use all variables in the binding.

For the in/∈ case, the expression must have arity 1 if a normal variable is used. Varargs are supported though, as in x... in {(1,2,3)} : true. In the varargs case, the arity of the expression — 3 in this example — determines how many variables the vararg represents.

Notice that an expression such as x in P — or x... in P — can also be seen as a kind of relational application. For example, the following three definitions are equivalent:

def Q = x... in P : true
def Q(x... in P) = true
def Q(x...) = P(x...)

#### Relational Abstraction

Relational abstraction defines a relation without a name. This is by far the most important construct in the language. Syntactic variations will be introduced later, but they all translate into relational abstractions.

Expr := Bindings ":" Expr

The arity of a relational abstraction is the number of variables in the bindings + the arity of the expression. If the expression is a formula (arity 0), then only the variables from the bindings remain.

In the following examples, we use:

• def p = {1; 2; 3}
• def q = {2; 3; 4}
• def r = {(1, "a"); (2, "b"); (3, "c")}
• def abc = {"a"; "b"; "c"}
• def parent = {("John", "Mary"); ("Mary", "Felix"); ("Felix", "George")}

It is common for a relational abstraction to have a formula as the expression. This is similar to a Datalog rule, but without a name for the relation that is defined. A formula is used in each of the following examples:

• x: p(x) and q(x)
• Unary relation (one variable x).
• Value: {2; 3}.
• x: p(x) or q(x)
• Unary relation.
• Value: {1; 2; 3; 4}.
• x, s: q(x) and r(x, s)
• Binary relation.
• Value: {(2, "b"); (3, "c")}.
• s: exists(x: q(x) and r(x, s))
• Unary relation. The x is existentially quantified in the body of relational abstraction.
• Value: {"b"; "c"}.
• x, y: p(x) and q(y)
• Binary relation.
• This is the Cartesian product of p and q, which is {(1,2); (1,3); (1,4); (2,2); (2,3); (2,4), (3,2); (3,3); (3,4)}
• x, t, y: parent(x, t) and parent(t, y)
• Ternary relation.
• Value: {("John", "Mary", "Felix"); ("Mary", "Felix", "George")}.
• x, y: parent(x, t) and parent(t, y)
• This is an error because variable t is never introduced.
• x, y: ∃(t: parent(x, t) and parent(t, y))
• Value: {("John", "Felix"); ("Mary", "George")}.
• x: Int(x) and x > 0
• Value is the infinite relation {1; 2; 3; 4; ...}.
• x, y: x = y
• Binary relation of all values that are equal, for example, (1,1) and ('a', 'a').
• x: x = 1
• Singleton relation {(1,)}.
• x: true
• Infinite unary relation (for example, contains 1, and "abc").
• x: false
• Empty unary relation.
• x...: p(x...) and q(x...)
• Varargs are explained in section Advanced Syntax of the Rel Primer. In this case, x... will only represent a single variable, because p and q have arity 1, and the value is {1; 2}.
• {x: p(x) and q(x)}
• As discussed later, the only purpose of curly braces and parentheses is to indicate precedence. Sometimes a relational abstraction is more clear when it is enclosed in curly braces. This does not change the semantics in any way.

The previous examples all use formulas for the body of the relational abstraction. Expressions with arity bigger than 0 are allowed as well. Using the same sample data for p, q, r, and parent as before:

• x, y: x + y
• Ternary, infinite relation.
• Example tuples: (1, 1, 2), (2, 3, 5), (3.5, 1.2, 4.7)
• x: x + 1
• Binary, infinite relation.
• Example tuples: (1, 2), (1.0, 2.0), (3.14, 4.14)
• x in Int: x + 1
• Binary, infinite relation.
• Example tuples: (1, 2), (2,3), (3,4)
• x where Int(x): x + 1
• Equivalent to the previous example.

A few slightly more advanced examples without sample data:

• p: today - date_of_birth[p]
• Binary relation of person and their age. The arity is 1 (for p) plus 1 for the body.
• x: sum[v: scores(x, v)]
• Sum scores v, grouped by x.
• Note that there are two relational abstractions here: one outermost, and one that is an argument of sum.
• Aggregations are explained later in much more detail.
• mean[x, y: (actual[x, y] - prediction[x, y]) ^ 2]
• Compute the mse for a machine learning solution. Note that the standard library defines mse, which can be used as mse[actual, prediction].
• x: edge(x, x)
• Unary relation of all nodes that have a self edge.
• ∃(c ∈ course: ∀(s ∈ student: enrolled(c, s)))
• The arguments to ∃ and ∀ are relational abstractions.
• sum[date store_nbr item_nbr: train_unit_sales[date, store_nbr, item_nbr]]
• Sum up the sales for every unique (date, store_nbr, item_nbr) triple in the train_unit_sales relation.

Bindings can also use constants as an abbreviation for having to introduce a separate variable. Examples of constants in a binding of a relational abstraction:

• x, 1: abc(x)

• Value: {("a", 1); ("b", 1); ("c", 1)}.
• def count_abc = sum[x, 1: abc(x)]

• Sums the last elements of all tuples. Since the last element of each tuple is 1, this defines the count of the number of tuples in abc, which is 3.
• The standard library defines count in this way generically, and it can be used as count[abc] in this example.
• 1: p(_)

• Value: 1 (given that p is not empty).
• Note that the left-hand side of the relational abstraction does not have to contain an explicit variable.
• The underscore expression is syntactic sugar for an anonymous variable. See section Underscore for more details.

It is worth noting that relational abstraction can be nested, and that : associates to the right. Some simple examples:

// query

@inline
def is_true[R] = if R then "yes" else "no" end
def output:A = is_true[equal((1 : 2 : 3), (1 : (2 : 3)))]
def output:B = is_true[equal((1 : 2 : 3), (1, 2, 3))]
// query

def p = 2; 3; 20; 30
def output = x in p where 9 < x : y in p where y < 10 : 0

Finally, it is important to note that a relational abstraction can be used directly in a relational application or a partial relational application:

// query

{x in Int, y in Int : x * x + y}[2, 3]

The bindings play the role of the formal parameter specifications in a definition. It is convenient to think of the variables introduced in the bindings — x and y in this example — as the parameters of the relational abstraction.

If you are familiar with programming languages, you will notice that in some ways relational abstractions are similar to lambda expressions.

#### An Alternative Form of Relational Abstraction

Relational abstractions are often used as a parameter to higher-order abstractions, such as aggregations. In aggregations, typically the most important thing to see first is what value is being aggregated. To make this easier to see immediately, the bindings and expression of a relational abstraction can be inverted. The : becomes a | (or the keyword for) in this case. This syntax is designed to mimic the common mathematical notation.

Expr := Expr "|" Bindings
Expr := Expr "for" Bindings

This is purely a syntactic convenience: e | b is equivalent to e for b which is equivalent to b: e.

Examples:

• x+1 | x in {1; 2; 3}

• Value {(1,2); (2,3); (3,4)}.
• Equivalent to x in {1; 2; 3}: x+1
• x+1 for x in {1; 2; 3}

• Equivalent to the previous example.
• x^2 for x in {1; 2; 3}

• Value {(1,1); (2,4); (3,9)}.
• {x^2 | x ∈ {1; 2; 3}}

• Equivalent to the previous example.
• Just as in normal relational abstraction, optional curly braces can be used for clarity.
• x^2, x^3 for x in {1; 2; 3}

• The initial expression is now a tuple. The value of the entire expression is a ternary relation {(1,1,1); (2,4,8); (3,9,27)}. The comma operator is explained in more detail in section Comma (Cartesian Product and Conjunction).
• (x^2, x^3) for x in {1; 2; 3}

• Equivalent to the previous example. Parentheses are used for precedence and have no other semantic here.

To users familiar with list comprehension in programming languages such as Python, Julia, and Haskell it may appear as strange that the variables introduced in the comprehension (e.g. x in x^2 for x in {1; 2; 3}) are part of the result. In these programming languages, the value of the comprehension is a list of the value before the for.

The distinction with Rel is that in Rel every value is a relation, and a relation is a set of tuples. This means that duplicates are eliminated. For some computations this is the intent, but often it is not. Some examples to illustrate this:

• age[p] for p in employee

• This is a binary relation of Person and Int, not a unary relation of ages (which would contain every age value only once).
• max[age[p] for p in employee]

• This is the previous example used as an argument to the max aggregation. The result is a singleton of the age of the oldest employee. Note that for this particular aggregation it does not matter whether age values are kept for all employees.
• sum[age[p] for p in employee]

• The same example, but now in a sum aggregation. Here it is very important that even if two different persons p1 and p2 have the same age, the age of both persons contributes to the sum. This is ensured by having p be a part of the relation that is being aggregated, and we get the intended result.

Note that max (resp. sum) computes the maximum (resp. sum) of the set of last elements of the tuples in the relation, which can have any arity.

The next section introduces the “from” language construct, which does not keep the variables introduced, more akin to comprehension in programming languages.

#### “From” Expressions

From expressions are similar to relational abstractions, with one important distinction: the variables introduced by the binding are not part of the resulting value. The arity of the expression is entirely determined by the expression.

Expr := Expr "from" Bindings

The key difference between for (introduced in the previous section) and from (introduced here) with some examples:

ExampleDescription
x+1 for x in {1; 2; 3}Binary relation {(1,2); (2,3); (3,4)}
x+1 from x in {1; 2; 3}Unary relation {2; 3; 4}
x, x+1 from x in {1; 2; 3}Binary relation {(1,2); (2,3); (3,4)}
x, x+1 for x in {1; 2; 3}Ternary relation {(1, 1,2); (2, 2,3); (3, 3,4)}

The third example above shows that from can be used in a similar way as the for construct by explicitly including the variables that are introduced in the expression.

ExpressionValue
x+1 from x in {1; 2; 3}{2; 3; 4}
x^2 from x in {1; 2; 3}{1; 4; 9}
{x^2 from x in {1; 2; 3}}{1; 4; 9}
x^2, x^3 from x in {1; 2; 3}{(1,1); (4,8); (9,27)}
(x^2, x^3) from x in {1; 2; 3}{(1,1); (4,8); (9,27)}

The from construct is particularly useful if auxiliary variables are needed in some bigger definition. Typically this comes up in the domain of a binding. For example, suppose that you want to define a binary relation that associates a person x with the name of the father of x. The problem is that you must find the father of x, but the father is not a part of the actual relation.

• def fathers_name = x where exists(f: father(x, f)): name[f] (wrong)

• This definition is incorrect: the variable f is introduced with an existential quantifier in the domain of x, but it cannot be used outside of that scope, so you will get a compilation error with the information that f is undefined in name[f].
• def fathers_name = name[f] | x: exists(f: father(x, f)) (wrong)

• Using the inverse relational abstraction syntax will not solve the problem. There will be an error, because f is not in scope in name[f].
• def fathers_name = x: {name[f] from f where father(x, f)} (correct)

• This correct example introduces the variable f in a separate from. The curly braces are optional, but may help to understand the precedence and scope of f.
• def fathers_name = x, name[f] from x, f where father(x, f) (correct)

• If what is actually computed gets confusing, it can also help to just explicitly list the entire desired result, in this case x, name[f]. The variable x must now be introduced in the from binding (otherwise it would be undefined).
• def fathers_name[x] = name[father[x]] (correct)

• In this example you actually did not need the variable f at all, so it could also have been written this way. The logic is not always this straightforward, though.

The construct from x ... is technically a form of existential quantification. The following two definitions are equivalent:

def fathers_name = x, name[f] from x, f where father(x, f)

def fathers_name = y, nm : exists(x, f: y = x and father(x, f) and nm = name[f])

#### From-Where

To make Rel more accessible to users who are familiar with LINQ or SQL, Rel supports a similar syntax for queries:

Expr := Expr "from" Bindings

Although where does not occur in this grammar rule, it is part of Bindings and leads to a syntax very similar to LINQ (Language-Integrated Query).

s.name from s in students
where s.age > 12 and s.age < 20
p.partkey from p in part
where like[p.name, '@@1%']

This example uses composite relations (e.g., s.age and p.name). The semantics of relational composition, also called navigation, are described in more detail below.

#### Overview of Relational Abstraction Alternatives

The previous sections introduced a few variants of relational abstractions, and it may be hard to remember the variants and when to use which one. When choosing how to write an abstraction, the first thing to consider is whether it is more readable to first introduce variables or state the value that is computed. This splits the options in two categories with only a few alternatives.

The following examples use p = {1; 2; 3}

Abstractions that have Bindings first and Expr second:

     x in p:              x+1       = {(1, 2); (2, 3); (3, 4)}
x in p where x < 3:  x+1       = {(1, 2); (2, 3)}

Abstractions that have Expr first and Bindings second:

       x+1 |    x in p       = {(1, 2); (2, 3); (3, 4)}
x+1 for  x in p       = {(1, 2); (2, 3); (3, 4)}
x+1 from x in p       = {2; 3; 4}
x+1 from x in p where x < 3  = {2; 3}

The first and second are identical. The third variant is more SQL-like and lists the computed value separately.

### Partial Relational Application

Expr := Expr "[" (Expr {"," Expr}*)? "]"

The square bracket syntax is used to project and select a slice of the relation. It is related to currying in functional languages in the sense that relations can be partially applied.

Unlike in an application written with parentheses, in a partial relational application the number of arguments can be smaller than the arity of the relation. For instance, if p is a binary relation then all applications of p must have two arguments: p(x, y) is an example. A normal application with parentheses is a formula, or equivalently a nullary (0-arity) relation.

This is not always the case for partial relational applications, for example, p[x]. The syntax mimicks that of array and matrix indexing from other languages. If relation p is binary, then p[x] is a unary relation, unless it is empty. Notice, however, that p[x, y] — or, equivalently, p[x][y] — is a nullary relation.

In a partial relational application the part of the the expression that is evaluated in the square brackets will not be a part of the result. This behavior is useful, in particular, for accessing information that is stored in a key-value format.

It is also useful for evaluating functions, even those that are not stored in the database. For example, consider the following relation:

   def binomial[x, y] = x * x + y

The result of evaluating binomial2[2, 3] is the relation {(7)}.

The result of a partial relational application is always a relation. For example, p[_] does not just strip away the first element of each triple, but forms a relation from the resulting tuples. As a result, the number of tuples may be decreased.

// query

def p = (1, 2, 3); (10, 2, 3); (10, 2, 4)
def output = p[_]

A partial relational application can be thought of as a combination of two operations: filtering and projection. Here is a very simple example:

// query

{(1, 3); (2, 4); (1, 5); (2, 6)}

You can also use the syntax with square brackets to define relations:

  def name = "Noether", "Emmy"
def name = "Hopper", "Grace"
def name = "Curie", "Marie"

def age = 53
def age = 85
def age = 66

This defines a ternary relation name with tuples such as (3, Curie, Marie) and a binary relation age with tuples such as (1, 53).

The relations can be queried as follows:

ExampleDescription
name{"(Hopper", "Grace")}
name[3, "Curie"]{"Marie"}
name[x-1 from x in {1;2}]{("Noether", "Emmy")}
(name[p], age[p] from p)[_]{("Emmy", 53); ("Grace", 85); ("Marie", 66)}
(age[p], name[p] for p)[(x : x%2 = 1), (x: x>60)]{("Curie", "Marie")}

In the fourth example (name[p], age[p] from p) has tuples such as ("Noether", "Emmy", 53), and the [_] just drops the first element.

The last example is equivalent to (age[p], name[p] for p)[x : x%2 = 1][x: x>60]. The second tuple of (age[p], name[p] for p), namely (2, 85, "Hopper", "Grace"), is filtered away by x: x%2 = 1, so the remaining tuples lose their first element and now begin with age. They are then filtered by x > 60, and age is removed from the remaining tuple.

Some partial relational applications can be written without square brackets. These are the applications of relations whose initial elements are RelNames. For example, person:address:city is shorthand for the partial relational application person[:address][:city].

Partial relational applications are convenient and allow you to write more elegant models. But, strictly speaking, they do not extend the expressive power of the language. It is always possible to rewrite an expression involving a partial relational application as an equivalent expression that does not include a partial relational application.

The following example illustrates the point:

// query

def binomial[x in Number, y in Number] = x * x + y

def output:A = binomial[binomial[2, 3], binomial[3.0, 4]]

def output:B(result) = binomial(2, 3, one) and binomial(3.0, 4, two)
and binomial(one, two, result)
from one, two

The example clearly shows the advantages of using partial relational applications.

If you don’t know the arity of a relation, or if the arity is not fixed, you can simulate partial relational application by using varargs:

// query

def r = (1); (2, 3); (4, 5, 6)
def output = r[_]
// query

def r = (1); (2, 3); (4, 5, 6)
def output(x...) = r(_, x...)

### Comma (Cartesian Product and Conjunction)

The comma operator is technically a Cartesian product operator, but when it is applied to singleton values, it is easier to understand as a tupling operator.

Expr := Expr "," Expr

The comma operator is used in the following examples:

ExampleDescription
def p = 1, 2Singleton, binary relation (tuple)
1, 2, 3Ternary tuple
(1, 2, 3)Also a ternary tuple
{(1, 2, 3)}Also a ternary tuple
x^2, x^3 from x in {1; 2; 3}Binary relation (x is not in result)

The comma operator can also be used in some perhaps surprising ways:

• def soccer_players[t] = players[t], soccer(t)

• The comma serves here as an additional condition on the value of soccer players, without having to write out the logic as the point-wise variant def soccer_players(t, p) = players(t, p) and soccer(t).
• def order_price[pos] = order[pos, :price], not exists order[pos, :load_errors]

• Similarly, the comma introduces a filter here, skipping rows from a CSV file with any errors.
• def count[R] = sum[{R, 1}]

• Every tuple of R is extended with a 1, so that computing a sum aggregation actually computes the count.

Note that comma is really an operator and there is no dedicated syntax for tuples in the language. For example, (1, 2, 3) is an expression that uses parentheses (Expr := "(" Expr ")") and two applications of the comma operator. Tuples never occur as elements of tuples in a relation. For example, ((1, 2), 3) represents the ternary relation {(1, 2, 3)}, and (1, 2), (3, 4) represents the arity 4 relation {(1, 2, 3, 4)}.

The comma operator is equivalent to and when its arguments are restricted to relations of arity 0. To illustrate this, here is the table of all possible arguments of arity-0 relations:

LeftRightLeft , Right
{}{} {}
{()}{}{}
{}{()}{}
{()}{()}{()}

Unfortunately the comma character is overloaded by the comma operator and the arguments of applications. In the context of an application, there is a semantic difference whether the comma is interpreted as a comma operator or separator of arguments.

• foo[x: y, z]

• In the absence of precedence rules, this example is ambiguous. It can be interpreted as either foo[{x: y}, z] or foo[{x: y, z}]

• Independent of what the default interpretation is, it is advisable to be clear about the intent when any commas and relational abstractions are involved.

• The comma operator binds more strongly than relational abstraction, which means that foo[{x: y, z}] is the chosen representation in the absence of parentheses. If this is written without curly braces, then a warning will be reported.

• As a general guideline, unless there is only a single relational argument (as in sum, count etc), it is best to always use curly braces or separate the arguments. For example, if the intent is to invoke foo with two arguments, then use either foo[x: y][z] or foo[{x: y}, z].

• foo[a, b: c, d]

• A similar problem exists in the bindings of the abstraction, because a comma is also used there to separate formal parameters. In this case, the possible interpretations are foo[{a, b: c, d}], foo[{a, b: c}, d], foo[a, {b: c}, d], foo[a, {b: c, d}]. Just as in the previous example, precedence rules select foo[{a, b: c, d}]. It is recommended that curly braces be used to clarify the intent.
• sum[R, 1]

• In this incorrect example, sum is required to have two arguments (which is not the case). The first argument is the relation R, and the second is the number 1. The intent of the logic is to count the number of tuples in R by appending 1 to all its tuples and then applying sum to the relation. To achieve this, the relation argument must be put in parentheses or curly braces: sum[{R, 1}].

As a general rule, if a relation is used as an argument of an application, then it should be wrapped in curly braces ({...}) unless it is the only argument and no commas are involved.

The compiler raises a warning for cases where the interpretation is ambiguous. The warning is triggered by an expression that has a comma as the right-most operand and is not written in curly braces or parentheses.

### Semicolon (Union and Disjunction)

The semicolon is a generalized union operator.

Expr := Expr ";" Expr
ExampleNormalized
p(x); q(x)p(x) or q(x)
p;qx: p(x) or q(x)
1;3x: x=1 or x=3
{};pp

The semicolon operator is equivalent to or when its arguments are restricted to relations of arity 0. To illustrate this, here is the table of all possible arguments of arity-0 relations:

LeftRightLeft ; Right
{}{} {}
{()}{}{()}
{}{()}{()}
{()}{()}{()}

The semicolon operator does not require its arguments to have the same arity. The compilation of expressions without a single arity is not entirely implemented yet though.

### Precedence

Precedence can be indicated with either curly braces or parentheses. The two are exactly equivalent.

Expr := "{" Expr "}"
Expr := "(" Expr ")"

For readability, it can be helpful to always use {...} for non-singleton relations, and (...) for singleton relations (scalars). For example, (x + y) * z vs {x, y, z: p(x, y, z)}.

All binary operators are left-associative unless otherwise stated below.

From highest precedence to lowest:

1. _, variables, qualified names, literals, (), {}
2. .
3. relational application
4. ^ (right assoc)
5. unary -
6. /, %, *, ÷, ×, ⊗, ⊙
7. -, +, ⊕, ∩, ⊓
8. ∪, ⊔,
9. =, !=, ≈, ∼, ≠, <, >, <=, ≤, >=, ≥, ⊆, ⊇, ⊂, ⊃, ≼, ≽, ≺, ≻, →, ←
10. ¬, not
11. forall, ∀, exists, ∃
12. ∧, and
13. ∨, or
14. ⇒ (right assoc), implies (right assoc), ⇐
15. ≡, ⇔, ⊻, ≢, ⇎, xor, iff
16. <:, :>
17. <++, ++>
18. ,
19. ;
20. : (right assoc)

### Relation Literals

Relation literals do not have a dedicated syntax, but are by convention written using curly braces (outer), parentheses (around tuples), comma (in the tuples) and semicolon (between the tuples).

ExampleDescription
{1}Singleton relation (arity 1, cardinality 1)
{1; 2; 3; 4}Unary relation (arity 1, cardinality 4)
{(1, 2); (3, 4); (5, 6)}Arity 2, cardinality 3
{1; 2; 1; 2}Arity 1, cardinality 2 (duplicates are eliminated)
{()}Unit relation (cardinality 1, arity 0)
{}Empty relation (cardinality 0, any arity)

Note that the arguments do not have to be constants, so the relation literal is not a relation constant. It can contain variables, and the tuples do also not have to be written explicitly with scalar variables.

For example, {(friend, 1); (family, 2); (partner, 3)} for binary friend, family and partner has arity 3 and unknown cardinality. It can explicitly be defined as

x, y, v:
(friend(x, y) and v = 1) or
(family(x, y) and v = 2) or
(partner(x, y) and v = 3)

Expr := Expr "." Expr

The semantics of R.S is x..., y... : exists(t: R(x..., t) and S(t, y...)). Note that the arguments must have at least arity 1.

For specific cases, the semantics is simplified a little. In particular,x.R is R[x].

ExampleNormalized
parent.parentx, y: ∃(t: parent(x, t) and parent(t, y))
t.playersp: players(t, p)
t.players.agev: ∃(p: players(t, p) and age(p, v))
brand_name."Tesla"b: brand_name(b, "Tesla")

### Restriction

Expr := Expr "<:" Expr
Expr := Expr ":>" Expr

Prefix join (or prefix restriction) R <: S is syntax for prefix_join[R, S] defined in the standard library.

Suffix join (or suffix restriction) R :> S is syntax for suffix_join[R, S] defined in the standard library.

### Override

Expr := Expr "<++" Expr
Expr := Expr "++>" Expr

Left override operator R <++ S is syntax for left_override[R, S] defined in the standard library.

Right override operator R ++> S is syntax for right_override[R, S] defined in the standard library.

### Arithmetic Operators

Expr := Expr "+" Expr
| Expr "-" Expr
| Expr "*" Expr
| Expr "/" Expr
| Expr "%" Expr
| Expr "÷" Expr
| Expr "^" Expr

### Underscore

Expr := "_"

Underscore is a variable without a name. It desugars into the relation x: true, which is the infinite relation of all values. After further rewriting, this typically becomes an existential quantification of a variable with a unique name. Underscore is mostly useful if you do not care about certain arguments of relation and want to avoid introducing a named variable and quantifier.

For example:

// Unary relation of all orders with a line item:
o: line_item(o, _)

// There does not exist an order for customer c:
not(order_customer(_, c))

// Count the number of distinct values of a function or relation f:
count[f[_]]

### Splat

Expr := Expr "..."

### Existential Quantification

Expr := "exists" Expr
| "∃" Expr

The argument of existential quantification can be an expression of any arity. This is because the expression includes the variables that are quantified over (they are not syntactically associated with the quantifier). For example:

def foo = 1;2;3
def output = exists(x, y : foo(x), foo(y), x > 2)

which evaluates to true.

The value of an existential quantification is false if the argument is the empty relation, and true otherwise.

Examples
exists(p: person(p) and age[p] > 99)
exists(centenarian)
∃(centenarian)
c: course(c) and not ∃(s: enrolled(c, s))
c: course(c) and not ∃(enrolled[c])
def grandparent(a, b) = exists(t: parent(a, t) and parent(t, b))

### Universal Quantification

Expr := "forall" "(" Bindings ":" Expr ")"
| "∀"      "(" Bindings ":" Expr ")"

Universal quantification is true if the range (the Expr expression) is true for the entire domain (the domain specified in the bindings). For the empty domain, universal quantification evaluates to true.

The range (right-hand side) of universal quantification must be a formula (that is, an arity-0 relation).

ExamplesDescription
forall(p in person: age[p] > 99)Are all persons older than 99?
∀(p in person: centenarian(p))Are all persons centenarians? Here we use a Unicode “forall” quantifier.
exists(c in course: forall(s in student: enrolled(c, s))Does there exist a course where all students are enrolled?
∃(c in course: ∀(s in student: enrolled(c, s))Same, with Unicode quantifiers.
c: course(c) and ∀(y in year: ∀(s where class[s] = y: enrolled(c, s)))Courses that have, for every year, all students from that year enrolled.
c: course(c) and ∃(y in year: ∀(s where class[s] = y: enrolled(c, s)))Courses that have all students from one year enrolled.

Writing forall x,y,... where E1(x,y,...) : E2 is preferred to forall x,y,... : E1(x,y,...) implies E2.

### Aggregation

There is no dedicated syntax for aggregations. Instead, there is one higher-order native called reduce that is used to define various aggregations in stdlib.rel.

A few examples of aggregations:

ExampleDescription
sum[salary]Sum all salaries
sum[p in employee: salary[p]]Sum employee salaries
Σ[salary[p] | p ∈ employee]Sum employee salaries
Σ[employee.salary]Wrong: duplicates eliminated
d in dept: Σ[salary[p] | p ∈ member[d]]Sum salaries by department
d in dept: Σ[d.member.salary]Wrong: duplicates eliminated
count[employee]Count number of employees
d in dept: count[d.member]Count number of employees by department
d, v: dept(d) and count[d.member](v)Aggregations can be used in formulas
max[age[p] | p ∈ person]Max age of all persons
max[age[p] for p in person]Max age of all persons
max[t.member.age] | t ∈ teamMax age by team
max[Σ[salary[p] for p in member[t]]] for t in teamMax sum of salaries by team
argmax[Σ[salary[p] for p in member[t]] for t in team]Team with max sum of salaries
argmin[Σ[salary[p] for p in member[t]] for t in team]Team with min sum of salaries
t: max[age[p] for p in member[t]]Max age by team (again)

### Variable Scope

All variables have to be explicitly introduced to clarify their scope.

There is no implicit quantification as in Datalog.

All variables are introduced by Bindings (although definitions support a subset of Bindings, FormalParams).

A local scalar variable x shadows relation definitions, schema, and natives with name x.

For example, in the definition of foo, the local variable nation shadows the previous definition of nation.

def nation = ...
def foo = nation: ...

Variable scope is static, not dynamic. This means that the local variable nation only shadows variables that are lexically in its scope.

## Annotations

A definition can be preceded by a number of optional annotations. An annotation consists of the character @, immediately followed by an identifier: for example, @inline.

By convention, the annotations of a definition are written on a separate line.

This section briefly describes the most commonly used annotations, which are listed in lexicographic order below. The list of annotations is not complete and is likely to change over time. You may wish to bookmark this page for future reference. Most of the omitted ones have very specialized purposes, such as displaying the intermediate results of compilation or suppressing a particular optimization.

### @function

This annotation asserts that the annotated relation is a function. A relation is a function if there is only one value for a given tuple of keys. By default, the value is the last element of a tuple and the keys are all the other elements.

At runtime, when a new tuple is added to a relation whose definition has been annotated with @function, the addition is preceded by deleting any existing tuples that have the same keys and a different value.

// query

def F { 1, 10; 2, 20 }
def F { 1, 11 }
def output = F
// query

@function
def F { 1, 10; 2, 20 }
def F { 1, 11 }
def output = F

If the function has several definitions, it is enough to annotate one of them, not necessarily the first.

// query

def F { 1, 10; 2, 20 }
@function
def F { 1, 11 }
def output = F

It must be noted that all the tuples that are to be inserted into a relation in a given transaction are sorted before being inserted, and it is the latest one that prevails. This is demonstrated by the following example:

// query

@function
def F { 1, 10; 2, 20 }
def F { 1, 11; 2, 19 }
def F { 1, 9 }
def output = F

Finally, if the defined name happens to refer to several different relations — as is the case when there are several definitions of the name with different types or arities — then the annotation must be repeated at least once for each of these relations.
For instance, in the following example, @function applies only to the relation with arity 3, not to the relation with arity 2.

// query

@function
def F {1, 10, 100}
def F {1, 10, 110}
def F {1, 11}
def F {1, 12}
def output = F

### @inline

When a definition of relation R is annotated with @inline, the annotation makes Rel treat the definition differently. The relation R is not materialized; instead, its definition is inlined, or expanded at every place where it is used. More precisely, a copy of the body of the definition of R replaces every relational application of R, after replacing the parameters with the appropriate arguments.

Consider the following example:

@inline
def P[x, y] = x * x + y
def Q[x] = P[x, x] + P[2.0, 3.0]

The annotation makes the definition of Q equivalent to:

def Q[x] = x * x + x + 2.0 * 2.0 + 3.0

An inlined definition — or a series of such definitions — cannot be recursive. Such direct or indirect recursion would lead to an infinite expansion.

The following example features indirect recursion: P uses Q, and Q uses P.

// query

@ondemand
def P[x in Int] = Q[x] * 2
@ondemand
def Q[x in Int] = if x > 1 then P[x - 1] else 1 end
def output = P

If you change the annotations on either P or Q to @ondemand @inline — or, equivalently, @inline @ondemand — the result will be the same. But if you add @inline to both the definitions, the compiler will raise an error.

An inlined definition can have occurrences of variables that are not grounded, as long as they are grounded in the definitions in which it is expanded. One consequence of this is that an inlined definition that appeared to be correct may suddenly cause an error when used in a new way.

For instance, in the example above, either one of the occurrences of @ondemand could have been replaced with @inline. If the definition of P and/or Q is deprived of annotations, x will be ungrounded and Rel will raise an error.

The annotation @inline is currently necessary for higher-order definitions, that is, definitions of relations whose parameters are other relations. In the example below, rotate is higher-order, because its parameter is intended to be some relation. As you can see, it can be used for a number of different relations:

// query

// Move the last element of each tuple to the first position
@inline
def rotate[R] {y, x... : R(x..., y)}

def once = rotate[ {1, 10, 100; 2, 20, 200} ]
def output:once = once
def output:twice = rotate[once]
def output:thrice = rotate[rotate[once]]

The annotation @inline is also necessary in the definitions of parameterized modules.

### @ondemand

This annotation prevents Rel from materializing the defined relation. Rel will compute only those parts of the relation that are actually used.

In the example below, the relation factorial is infinite, so without the annotation Rel would produce an error message informing you that n is ungrounded. The annotation makes the definition behave quite like a similar recursive definition in a conventional programming language, that is, to compute the factorial for a given argument.

// query

// Yields 1 for negative arguments.
@ondemand
def factorial[n in Int] = if n > 0 then n * factorial[n - 1] else 1 end
def output = factorial

Notice that in this case @ondemand cannot be replaced with @inline, because the definition is recursive.

### @static

This annotation can be used in integrity constraints to avoid repeated evaluation. See @static annotation in the Integrity Constraints guide.

## Other Topics

### Types

To learn more about for types in Rel, see the Data Types Reference. The Rel standard library includes a number of predicates that test for a given type, such as the Number relation and the ones that follow.

### Mixing Arities and Types

The value of a Rel expression is a set of tuples that can have different arities and types. For example:

def myrel = 1; 2 ; "a" ; ("b", "c")

Technically, myrel is three separate relations, sharing the same name: {1; 2} is unary and has integers; {"a"} is unary and has strings, and {("b", "c")} is binary and has strings. The language treats them as a single relation. For example, first[x] is {1; 2; "a"; "b"}.

### Integrity Constraints

Rel supports expressive Integrity Constraints, written using the Rel language itself. See the IC Concept Guide for an introduction to ICs, and the Integrity Constraint Reference for technical IC reference.

### Modules

Rel modules, which group together definitions and can be parameterized by relations, are relations as well. See the Rel Modules Guide.

### Base relations: insert and delete

Base relations can be persisted and updated with the transaction control relations insert and delete. See the guide on Working with Base Relations.

### Rel Libraries

When a database is created, a number of libraries are installed automatically as part of the database, including the Rel Standard Library (stdlib). See the Library Overview for more details.