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 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 firstorder 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.
Terminology
Frequently used terms are gathered here for easy reference.
Term  Explanation 

Argument  One of the expressions between the parentheses of a relational application or the brackets of a partial relational application. 
Arity  Number of elements in the tuples of a relation. If a relation contains tuples of various lengths, the relation has multiple arities. If N is the arity of the relation to which an expression E evaluates, then E is also said to have arity N . 
Base relation  A base relation is defined completely by the data it contains. This corresponds to a table in SQL. 
Binary relation  Relation of arity 2. 
Body  The main expression in a definition or a relational abstraction. 
Cardinality  Number of tuples in a relation. 
Column  The kth column of relation R is the set of data values that are the kth elements of the tuples in R . 
Data value  A number, a string, etc. See Values. 
Derived relation  A derived relation is a relation whose content is defined by logical statements. These statements can refer to other relations (base or derived) or refer directly to data values. A derived relation corresponds to a view in SQL. 
Element  A data value in a tuple. Elements are ordered by position from 1 to $N$, where $N$ is the length of the tuple. 
Empty relation  Relation with no tuples (cardinality 0). 
Formula  An expression that evaluates to a relation of arity 0 (i.e., to true or false ). 
Function  Relation with a functional dependency from the initial elements of a tuple to the last element. 
$n$ary relation  Relation of arity $n$. 
Nullary relation  Relation of arity 0. There exist only two nullary relations: the empty set {} (cardinality 0) and the empty tuple {()} (cardinality 1). See Boolean Constant Relations. 
Qualified name  A name that consists of an identifier immediately followed by one or more Symbols, such as foo:bar:baz . Equivalent to a partial relational application, such as foo[:bar, :baz] . 
Parameter  A variable introduced in the head of a definition or in the “bindings” part of a relational abstraction. 
Relation  A relation is a set of tuples. The tuples in a Rel relation may have different lengths or data type signatures. 
Set  An unsorted collection of items, each of which is unique in the collection. 
Singleton  Relation of cardinality 1 and arity 1. 
Ternary relation  Relation of arity 3. 
Tuple  An ordered list of data values. A relation of cardinality 1 (any arity) is often identified with the tuple that it contains, and vice versa. 
Unary relation  Relation of arity 1. 
Values
Every value in Rel is a firstorder relation.
You can write tuples as data 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 
Parentheses are typically left out 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 you can 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,)}
.
A tuple is always a “flat” sequence of data values, even though in Rel you can write expressions within tuples.
So (1, 2 + 1, 2 + 3)
is equivalent to (1, 3, 5)
.
Moreover, additional parentheses don’t matter.
For example, ((1, 3), ((5)))
is equivalent to (1, 3, 5)
.
Similarly, (1, 3, ())
is equivalent to (1, 3)
.
As mentioned above, every value in Rel is a firstorder relation. This means, in particular, that:
 Relations cannot contain relations. Relations can contain tuples whose elements are data values such as integers, floatingpoint numbers, fixedpoint decimals, characters, dates, datetimes, etc. Some of the data values — dates, for instance — have internal structure, but each of them has a fixed size. The Rel system is designed to support data values of arbitrary fixedsize Julia types.
 A standalone data value, such as an integer or a string, always represents a singleton, that is, a relation that contains just 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?",)}
.
Note: Unlike a mathematical relation, a Rel relation can contain tuples of different lengths, that is, its arity does not have to be fixed. A relation whose arity is not fixed can be thought of as a convenient wrapper for several different mathematical relations. In fact, the physical representation of such a relation consists of multiple conventional relations of fixed arity.
Variables, Singletons, and Data Values
Before reading this section, you might want to acquaint yourself with the rest of the manual, in particular with Relational Application.
A variable normally represents a singleton relation that contains a data value. Strictly speaking, the value of a variable x is a singleton, but it is often convenient to say that the value of x is the data value contained in the singleton.
For convenience, conversion between singletons and data 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 data values3
and4
are extracted from the tuple(3, 4)
and converted to singletons. The variablex
now represents{(3,)}
andy
represents{(4,)}
.  In
z = x + y
the data values3
and4
are extracted fromx
andy
and added. The result is converted to the singleton{(7,)}
represented byz
.
Notice that z
is a relation, because equal(z, {(7,)})
evaluates to true
, and equal
is defined only for relations.
Lexical Syntax
Comments
Rel uses /* ... */
for block (multiline) comments and // ...
for endofline comments.
Identifiers
Identifier := ("^")? IdCharInit IdChar*
IdCharInit := [azAZαωΑΩ_]
IdChar := [azAZαωΑΩ_09]
An identifier is a sequence of characters that begins with a Unicode letter, an underscore or a caret (^
).
The first character can be followed by zero or more Unicode letters, underscores, or numbers.
For example, valid identifiers are: x
, a1
, b1c
, θ
, φ
, Σ
, ß
, β1
, β2
, and ^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 Value Types and Entities.
It’s best to avoid using such identifiers for other purposes.
Due to missing features in the parser generator, the definition explicitly lists supported ranges of Unicode letters (hence the Greek ranges). This is currently incomplete, so Rel does 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.
The first letter of a variable is important. Firstorder variables must begin with a lowercase letter, and higherorder variables must begin with an uppercase letter. See HigherOrder Definitions for more information.
Symbols (RelNames)
Symbol := ":" Identifier
A Symbol has the form of an identifier prefixed with a colon.
The term “Symbol” begins with an uppercase “S”, to distinguish it from the usual meaning of the word “symbol”.
For example, +
is a symbol, but :name
is a Symbol.
A Symbol represents itself, that is, it is a literal. It cannot be used to name a relation or a variable.
A Symbol is sometimes called a RelName. The term “RelName” is an abbreviation of “relation name.” You can use Symbols to tag the representations of relations embedded in modules. But this is not the only application of Symbols. You can also use Symbols, for instance, to represent units of measurement in value types.
A Symbol is a specialized form of a string. See Specialization for more information.
Symbols are often combined with identifiers, as in person:address:city
.
Such a combination is often called a qualified name and can be used like an identifier.
This is just a convenient form of a partial relational application: person[:address, :city]
in this case.
When you replace a qualified name with a partial relational application, you may have to enclose the latter in parentheses, because the composition operator .
binds more strongly than partial relational application.
See Precedence for more information.
To check whether the value of a variable is a Symbol, you can use the Library function RelName
.
You can also convert the result to a string by using the Library function: relname_string
or despecialize
.
You can form a Symbol 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 Symbol in this manner.
If the strings are not literals, but are extracted from a relation, you can form the corresponding Symbols by using the specialization operator #
:
// query
def p = 1; 2
def q = "a%p"; "b%p"
def output = #(q)
Infix Symbols
You can use infix symbols for relation names, where the relation represents an operation that can be written in an infix notation (opens in a new tab) with the operator (for example: +
) placed between the arguments.
For instance, the expression 1+2
is the infix notation for (+)[1, 2]
, which is a partial application equivalent to the expression x: (+)(1, 2, x)
.
You can define custom infix notations using the following infix symbols:
⊗
, ⊙
, ⊕
, ⊔
, ⊓
, ∼
, ≼
, ≽
, ≺
, ≻
, →
, ←
, and ≈
.
For example:
@inline def (≈)(a, b) = a + 1 = b
def output = 1 ≈ 2
The infix ∼
used in alglib (Unicode 8764) is not the same character as your keyboard’s ~
(Unicode 126).
These symbols can also be useful as higherorder relational arguments, as this example from alglib 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 Symbol*
FormalParamsBracket := "[" FormalParameterSpecification "]"
FormalParamsParen := "(" FormalParameterSpecification ")"
Both forms of declaration are equivalent.
The part consisting of the name and the optional bracketed or parenthesized formal parameter specifications is often called the head of the definition.
The expression after =
(or between {
and }
) is often called the body of the definition.
You can read a definition as “the head is implied by the body.”
See 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 rule above, especially when Rel can determine that an infinite relation is meant to perform a simple computation.
For instance, the following definition will be inlined by the backend of the system.
From the user’s perspective, it’s as if the definition were annotated with @ondemand
or @inline
:
def P(x, result) {result = x * x}
See also Automatic Inlining.
The name that follows def
can contain Symbols: 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 Examples of Definitions for more information on using square brackets.
This manual calls variables introduced in the formal parameter specifications of a definition parameters. It also calls expressions used in the corresponding positions of relational applications arguments.
Examples of Definitions
Example  Description 

def five = 5  five is a unary, singleton relation {(5,)} . 
def numbers = {1; 2; 3; 4}  numbers is a unary relation. 
def first_four = numbers  The 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’s worth noting that the following two definitions are equivalent:
def square_add(x, y, z) { z = x * x + y }
def square_add[x, y] = x * x + y
For more information on square brackets syntax, see Partial Relational Application.
Writing Definitions
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:
 A binding with
where
cannot appear in the head of a definition.  A string in the head of a definition cannot feature string interpolation.
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[1] = "a" : true
def pair[1]("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 square_add
shown in Examples of Definitions could be defined as follows:
def square_add = x, y : x * x + y
The intention is to use this relation for computing the value of the formula, for example, by writing square_add[7, 3.0]
to obtain the value 52.0
.
Given this intention, the preferred form of the definition is:
def square_add[x in Number, y in Number] = x * x + y
If you will use the relation only for numbers of a particular kind, for example integers, then you will make it more efficient by using a more specific type:
def square_add[x in Int, y in Int] = x * x + y
The final example enumerates almost all of the possible ways of writing a definition equivalent to the following:
def output = range[1, 10, 1]
You can also write this as:
def output { range[1, 10, 1] }
def output(x) { x = range[1, 10, 1] }
You can also use relational application instead of partial relational application:
def output(x) = range(1, 10, 1, x)
def output(x) { range(1, 10, 1, x) }
You can write equivalent definitions with relational abstraction:
def output = x: range(1, 10, 1, x)
def output { x: range(1, 10, 1, x) }
If the number of arguments is equal to the arity of the applied relation, then a relational application is equivalent to partial relational application. So the following definitions are also equivalent, though their use is not recommended:
def output(x) = range[1, 10, 1, x]
def output(x) { range[1, 10, 1, x] }
def output = x: range[1, 10, 1, x]
def output { x: range[1, 10, 1, x] }
When the number of parameters in a definition of a relation is equal to the arity of that relation, then it doesn’t matter whether you use round parentheses or square brackets in the head of the definition. The following definitions are all equivalent to the above, though it is recommended that you use square brackets in the head only if the number of parameter specifications is lower than the arity of the relation:
def output[x] { x = range[1, 10, 1] }
def output[x] = range(1, 10, 1, x)
def output[x] { range(1, 10, 1, x) }
def output[x] = range[1, 10, 1, x]
def output[x] { range[1, 10, 1, x] }
The following two definitions are also equivalent to the above, but you are strongly encouraged to avoid these forms, because of the juxtapositions of two =
characters with two completely different meanings:
def output(x) = x = range[1, 10, 1]
def output[x] = x = range[1, 10, 1]
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.”
The definitions for a relation don’t need to be contiguous, and can be separated by definitions of other relations:
// query
def five = 5
def seven = 7
def five = 6
def output = five
However, it is recommended that you keep multiple definitions for the same name together whenever possible.
A definition can give another name to a named relation. This is illustrated by the following example:
// install
def P = 1
def Q = P
According to the definitions above, P
must contain (1,)
and Q
must contain the contents of P
:
// query
def output:P = P
def output:Q = Q
You can assign additional values to P
and Q
:
// query
def Q = 2
def P = 3
def output:P = P
def output:Q = Q
Now, Q
also contains (2,)
, and P
also contains (3,)
.
So Q
will now be the union of two relations: P
and {(2,)}
.
Since the name P
will now refer to {(1,), (3,)}
, Q
will also contain 3
:
You can think of the definition def Q = P
as introducing a onesided dependency: Q
depends on P
, but P
does not depend on Q
.
It’s important to realize that relations defined within the Libraries are in the same name space as your own definitions. So if you define a relation that has the same name as a Library relation, the results may be surprising:
// query
def abs[x] = x
def output = abs[3]
It’s also possible that userdefined relations may be modified when a new relation is added to the Library. Scoping userdefined relations within modules helps avoid this problem.
Entities
See Entities 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 zeroarity 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 range over 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 firstorder logic, a formula with free variables cannot be true
or false
.
In this context it is worth knowing that variables appearing on the lefthand 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, you can read def P(x, y) = Q(x) and R(y)
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))
.
Rel also has another syntax for this: def P(X) = Q(x, y) from 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 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, which is written with square brackets instead of parentheses.
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.
If the arity of P
is 3, then the formula P(x, y)
will evaluate to false
because there is no binary tuple in P
.
Note, however, that in general a Rel relation might not have a fixed arity, that is, it may contain tuples of different lengths.
If the relation P
does not have a fixed arity, then both P(x, y, z)
and P(x, y)
may evaluate to true
.
Examples 

age("Martin", 39) 
parent(x, y) 
foo() 
{(1, 10); (2, 20)}(x, y) 
{v, w : P(x) and w = v + 1}(x, y) 
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 Symbols 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 expression such as x = y
is also a relational application.
It is just a convenient notation 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 Bindings for more information.
A relational application consists of two elements: the expression that identifies the applied relation, and the arguments in parentheses.
The two are combined with an implicit operator.
The precedence of this operator is lower than that of the composition operator, .
.
So an expression such as R . Q(x)
is equivalent to (R . Q)(x)
.
If that is not what you want, you should put the relational application in parentheses: R . (Q(x))
.
Evaluation
The evaluation of a relational application can be described as follows:
 The applied relation is filtered by selecting the subset of tuples that match the arguments.
 If the selected subset is empty, the relational application evaluates to
false
.  If the selected subset is not empty, the relational application evaluates to
true
. Additionally, if any of the arguments are variables, then these variables are constrained to the sets of values in the corresponding positions of the selected tuples. If two or more arguments are variables, the variables are constrained together.
This is illustrated with relational applications of the relation P
defined below:
// install
def P = {
(1, 1);
(1, 2);
(2, 2);
(2, 3)
}
The relational application P(x, 1)
selects those tuples whose second element is 1
, and constrains x
to be one of the first elements of the selected tuples.
In this case the only such tuple is (1, 1)
:
// query
def output(x) = P(x, 1)
The relational application P(x, x)
selects the tuples whose two elements are equal, and constrains x
to the set of data values contained in the selected tuples.
In this case the selected tuples are (1, 1)
and (2, 2)
:
// query
def output(x) = P(x, x)
The relational application P(x, x + 1)
selects every tuple whose second element is greater by 1 than the first element, and constrains x
to the set of the first elements of the tuples with that property.
In this case the selected tuples are (1, 2)
and (2, 3)
:
// query
def output(x) = P(x, x + 1)
The relational application P(x  1, x)
selects the same tuples, but constrains x
to the set of the second elements of the selected tuples:
// query
def output(x) = P(x  1 , x)
If x
and y
are not constrained by anything else, then the relational application P(x, y)
selects all the tuples of P
and constrains the pair x
and y
to the set of these tuples.
The variable x
represents the first element of each tuple, while the variable y
represents the second element:
// query
def output(x, y) = P(x, y)
When taken separately, however, each of the variables can be thought of as representing the corresponding column of P
. For instance:
// query
def output(x) = exists(y : P(x, y))
The example below illustrates how constraining several otherwise ungrounded variables may be regarded as a projection of the relation consisting of the selected tuples onto the positions in which those variables appear:
// query
def Q = (1, 2, 3); (1, 3, 3); (2, 2, 4); (2, 3, 5)
def output(x, y) = Q(x, 2, y)
The relational application Q(x, 2, y)
selects the tuples whose second element is 2
, thus forming the intermediate relation {(1, 2, 3); (2, 2, 4)}
.
This relation is then projected onto the positions of x
and y
, that is, the second element of each tuple is removed, forming the relation {(1, 3); (2, 4)}
.
The pair of variables x
and y
is constrained to the set of tuples in this relation.
If the variables are not otherwise ungrounded but are constrained by other relational applications in a conjunction, then those constraints are taken into account.
Here is what happens when you add and P(z, y)
to the previous example:
// query
def Q = (1, 2, 3); (1, 3, 3); (2, 2, 4); (2, 3, 5)
def output(x, y, z) = Q(x, 2, y) and P(z, y)
The relational application Q(x, 2, y)
constrains y
to the set containing 3
and 4
, as before.
The relational application P(z, y)
constrains y
to the set containing 1
, 2
, and 3
.
The only element in both sets is 3
, so y
must be 3
.
The relation P
contains only one matching tuple, namely (2, 3)
, so z
must be 2
.
The relation Q
contains only one tuple whose third element is 3
and second element is 2
, namely (1, 2, 3)
, so x
must be 1
.
Finally, it’s worth noting that an argument of a relational application can be a unary relation. The selected tuples will be those whose corresponding element matches any unary tuple of that relation:
// query
def output(x) = P(x, {2; 3})
Grounded Variables
A variable v
is said to be grounded when Rel can determine that v
represents an element of a finite — possibly empty — set of values.
As noted in Evaluation, v
is then said to be constrained to that 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 frontend compiler (“not bound”) or by the backend 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 arguments — either grounded or nonvariable — 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 to be infinite, even though, strictly speaking, they are just very large.
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 of making 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 square_add[x in small_int, y in small_int] = x * x + y
def output(x, y, z) = square_add(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 square_add[x in Int, y in Int] = x * x + y
def output(x, y, z) = square_add(x, y, z) and y = 1 and z = 1
However, the following is fine:
// query
def square_add[x in Int, y in Int] = x * x + y
def output(x, y, z) { square_add(x, y, z) and x = 1 and z = 1 }
Why does this this example work?
The expression x * x + y
is just convenient notation for add[multiply[x, x], y]
.
The relations add
and multiply
are infinite.
However, the entire definition of square_add
is not recursive, so the compiler inlines it automatically at each point of use.
In this case the definition of output
becomes equivalent to the following:
def output(x, y, z) {
multiply(x, x, v) and add(v, y, z) and x = 1 and z = 1
}
The variable x
is grounded, so v
is also grounded.
The second argument of add
is ungrounded, but the first and third are grounded.
In such a case the compiler’s builtin rules about arithmetic allow it to replace add(v, y, z)
with sub(z, v, y)
.
For each pair of values z
and v
there will be only one possible value of y
that satisfies sub(z, v, y)
, so y
is also grounded.
In the previous example, by contrast, the problem of insufficiently grounded arguments occurs in the context of multiplication.
Unlike in the case of addition, this can’t be easily resolved because of difficulties with 0
: see multiply
.
See also the description of annotations @inline
and @ondemand
in Annotations.
Less Conventional Forms of Relational Application
Note: Most users don’t need to be aware of the details described in this section.
Recall from Values that a freestanding data value represents a singleton relation, and that, accordingly, the value of a variable is also a singleton 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. It 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
.
This also applies if p
is a grounded variable. If x
is otherwise ungrounded, then each of the expressions above 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.
Similarly, given the definitions def P = 5
and def Q = 6
, the expression P(Q)
must be a valid relational application.
An application of a relation to a relation is not restricted only to singletons.
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 the meaning for singletons.
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. It evaluates to true
if and only if both the left and the right expression evaluate to true
.
The arguments of and
must be formulas, that is, both must denote relations that have arity 0.
Examples 

flying(x) and mammal(x) 
The comma operator can be used instead of and
, but is more general in that it doesn’t require arguments of arity 0.
If the arguments both have arity 0, the and
syntax can help catch mistakes and disambiguate overloaded logic.
The arity of e1, e2
can be anything — it depends entirely on the arity of e1
and e2
.
The arity of e1 and e2
, by contrast, is always 0.
If e1
and e2
are used with an incorrect assumption of their arity, then e1 and e2
will result in an error, whereas e1, e2
will not.
The value e1 and e2
depends on the values of e1
and e2
, as follows:
e1  e2  e1 and e2 

false  false  false 
false  true  false 
true  false  false 
true  true  true 
Disjunction
Expr := Expr "or" Expr
Examples 

flying(x) or floating(x) 
The value e1 or e2
depends on the values of e1
and e2
, as follows:
e1  e2  e1 or e2 

false  false  false 
false  true  true 
true  false  true 
true  true  true 
The semicolon operator is a generalization of or
, just like the comma operator is a generalization of and
.
The semicolon operator computes the union of its arguments.
If both the arguments have arity 0, then this is equivalent to disjunction, just as in the case of or
.
For more details, see Semicolon (Union and Disjunction).
Implication
Expr := Expr "implies" Expr
Implication e1 implies e2
is defined as e2 or not e1
.
The value e1 implies e2
depends on the values of e1
and e2
, as follows:
e1  e2  e1 implies e2 

false  false  true 
false  true  true 
true  false  false 
true  true  true 
Negation
Expr := "not" Expr
Examples 

not mammal(x) 
Just like for the other logical operators, the argument of not
must be a formula, that is, an expression that denotes a relation of arity 0.
The value not e
depends on the value of e
, as follows:
e  not e 

false  true 
true  false 
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 zeroarity relation containing its only possible value, i.e., the empty tuple.
The constant false
is equivalent to the arity0 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 firstorder). 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
, "abc" < "abd"
, and 1 < 1.2
.
The comparison operators can be used to compare numbers with numbers, or strings with strings. A number can be compared with a string only for equality and inequality.
Two DateTime
values can be compared only for equality and inequality.
A DateTime
value can be compared with a number or a string only for equality and inequality.
Two unary tuples can be compared if their contents can be compared.
Nonunary tuples cannot be compared even for equality.
The comparison operators can be used to compare unary relations.
For example, 4 > {1; 2; 3}
is true
, because there is a number in the relation that is smaller than 4
.
By contrast, {1; 2; 3} < 1
is false
, because there is no number in the relation that is smaller than 1
.
The example below applies the same principle:
// query
def P = 1; 2
def Q = 0; 3
def output:LT = Q < P
def output:GT = Q > P
Evaluating the comparison Q < P
yields true
, because Q
contains a data value that is smaller than some data value in P
.
Similarly, evaluating Q > P
also yields true
.
The comparison operators cannot be used to compare relations that contain only nonunary tuples.
However, if two relations, P
and Q
, contain unary tuples as well as nonunary ones, then comparison is possible, but will be restricted only to comparing the unary parts of the relations:
// query
def P = 1; 2; (2, 3)
def Q = 2; 1; (1, 2)
def output:EQ = P = Q
def output:LT = P < Q
def output:GT = P > Q
Conditional Expression: IfThenElseEnd
Expr := "if" Expr "then" Expr "else" Expr "end"
The condition must be a formula, that is, an expression of arity 0.
If the condition is true
, then the value of the expression is the value of the expression in the then
branch, and the expression in the else
branch is not evaluated.
Otherwise the value is the value of the expression in the else
branch, and the expression in the then
branch is not evaluated.
The then
and else
branches can have arbitrary arity.
The expression if e1 then e2 else e3 end
has the same meaning as (e1, e2); (not(e1), e3)
.
Examples:
if 1 < 2 then 'a' else 'b' end
This gives ('a',)
.
def p = 1
def q = 2,3
def r = 4,5
def output = if p(1) then q else r end
This gives (2, 3)
.
def output = if p > 1 then q else r end
This gives (4, 5)
.
def p = 1; 2; 3
def output = if x = 1 then 'a' else 'b' end for x in p
This gives the following:
(1, 'a')
(2, 'b')
(3, 'b')
Conditional expressions can be nested, as shown in the example below, which defines a relation that computes the factorial of a positive integer.
The relation is named my_factorial
to avoid conflict with the function factorial
in the Standard Library.
See also the annotation @ondemand
.
// query
@ondemand
def my_factorial[n in Int] =
if n < 0 then false
else if n = 0 then 1
else n * my_factorial[n  1]
end
end
def output = my_factorial[5]
In Rel such definitions are usually expressed in a more idiomatic way:
@ondemand
def my_factorial[n in Int] = 1, n = 0
def my_factorial[n in Int] = n * my_factorial[n  1], n > 0
This version features the infix comma operator, which denotes the Cartesian
product of its arguments.
If n = 0
is true
, then the body of the first definition will be 1
, which is the Cartesian product of {(1,)}
and {()}
.
In that case the body of the second definition will be the empty relation,
because n > 0
will be false
, that is {}
, and a Cartesian product of
anything with an empty relation is an empty relation.
Similarly, if n > 0
, then the body of the first definition will be the empty relation, and the body of the second definition will be the relation produced by the expression that precedes the comma.
You can think of n = 0
and n > 0
as guards that allow each of the two definitions to be used only in some particular situations.
If these guards are mutually exclusive, then the effect is a more concise formulation of what can be achieved with a conditional expression or nested conditional expressions.
Note that, in general, these guards don’t have to be mutually exclusive.
If they are not, then both definitions will contribute to the result for a given value of n
, and the effect may be different from that of a conditional expression.
In this particular example, however, changing n > 0
to n >= 0
will not affect the result, because my_factorial[1]
will produce an empty relation.
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 Boolean Constant Relations) are relations of arity 0.
Integer Constants
Examples: 1
, 2
, and 3
.
FloatingPoint Constants
Expr := [09]+ "." [09]* exponent?
 [09]+ exponent
 "." [09]+ exponent?
decimalDigit := [09]
decimalDigits := decimalDigit+
exponent := ('e'  'E') ('+'  '')? decimalDigits
Examples:
0.0
.3.14
.1.5e4
.1e10
.5e4
.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 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 which 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’s not to be interpreted as beginning string interpolation.
In general, the conventions are as in Julia. Note 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 multiline
"string"
constant"""
The example shows that there is no need to escape a double quote inside a triplequoted 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 triplequoted 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 have also been written as:
"""
A multiline
"string"
constant"""
The exact rules are very similar to those found in TripleQuoted String Literals (opens in a new tab) of the language Julia (opens in a new tab). 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:
// query
raw"""
The backslash \ and percent sign % usually have special meanings.
"""
Everything between the opening quotes and the closing quotes is just uninterpreted text.
Neither the backslash \
nor the percent sign %
have any special meaning in a raw string.
Moreover, indentation and any new newline \n
are not ignored, but are included in the string.
Most notably, a newline immediately after the opening sequence such as raw"
is included in the string, in contrast to what happens in “standard” multiline strings.
In the following examples, the two string literals stored in s
and r
are equivalent:
// query
def s = "\n123\n"
def r = raw"
123
"
def output = r, s
With the raw strings syntax, it’s not possible to create a string that begins or ends with a double quote "
.
In the example below, the first quote of the contents is preceded by a newline, and the last quote of the contents is followed by a newline:
// query
raw"""
"A string."
"""
The following examples are all invalid raw string literals:
raw"""
.raw"" "
.raw" ""
.raw"\""
.
Standard string syntax and the sequence \"
must be used to create a string value starting or ending with a double quote. For example, "\""
.
Here are a few more examples of strings that feature the raw syntax and their equivalents written with the standard string syntax:
raw"\"
is equivalent to"\\"
.raw""" " """
is equivalent to" \" "
.raw"ab%c"
is equivalent to"ab\%c"
.
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, the example below is equivalent to a single string, whose contents — without the surrounding quotes — is shown in the output:
// query
raw"""""
"""A multiline
"string"
constant"""
"""""
Other interesting points about raw strings:
 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.  The only way to write an empty raw string is
raw""
. While the triplequoted string""""""
is empty,raw""""""
will cause the compiler to raise an error.  Raw strings are often convenient, but since their contents are taken literally, raw strings don’t support string interpolation.
String Interpolation
Rel allows a string to be interpolated into another string, as long as the latter isn’t a raw string and doesn’t 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:
// query
def R = (1, "one"); (2, "two"); (3, "three")
def output = """The number %(R[2])."""
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
Expr := [09][09][09][09] "" [09][09] "" [09][09]
Constants of type Date
are written in the ISO 8601 extended format.
Examples: 20210101
and 21000403
.
If a date does not exist (for example, 20210230
or 20202501
) then a warning is reported and the value of the constant is the unary empty relation.
DateTime Constants
Expr := Date "T" Time Timezone
Date := [09][09][09][09] "" [09][09] "" [09][09]
Time := [09][09] ":" [09][09] ":" [09][09]
Timezone := "Z"
 "+" [09][09] ":" [09][09]
 "" [09][09] ":" [09][09]
Constants of type DateTime
use the ISO 8601 extended format. A time zone is required.
Example: 20210101T21:00:00+00:00
.
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 := 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 the mechanism by which variables are introduced in Rel. It’s often useful to immediately specify the expected domain of the new variables, and the binding syntax supports that with where
and in
.
Bindings aren’t expressions themselves, but are used in many language constructs that are expressions. It’s best to understand the bindings syntax separately from the language constructs where it’s used.
Examples of bindings:

x
 Introduces a single variable named
x
.
 Introduces a single variable named

1
 A constant is also a binding.

x, y, z
 Introduces three variables:
x
,y
, andz
.
 Introduces three variables:

x in A
 Introduces a single variable
x
whose domain is restricted toA
.
 Introduces a single variable

x ∈ A
 Equivalent to the previous example.

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

x ∈ Int
 Introduces a single variable
x
, with domainInt
. Domains don’t have to be finite.
 Introduces a single variable

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 equivalentlyx ∈ A, y ∈ B, z ∈ C
 Introduces three variables, where
x
has domainA
,y
hasB
, andz
hasC
.A
,B
, andC
must have arity 1.
 Introduces three variables, where

x ∈ Red, y ∈ Green where edge(x, y)
in
andwhere
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
andy
in theedge
domain.
 Introduces two variables
For the where
case, the Expr
must be arity 0 (a formula).
The formula can use all the variables in the binding.
For the in
/∈
case, the expression must have arity 1 if the lefthand side is just an identifier, that is, the name of a variable rather than a vararg.
If it’s an identifier followed by three dots, that is, a vararg, then the arity of the expression can be greater.
For example, in x... in {(1, 2, 3)} : true
the expression has arity 3.
If a vararg is used, the arity of the expression determines how many variables the vararg represents.
This is illustrated by the example below.
The body of the relational abstraction is equivalent to true
:
// query
def P = 1; 2, 3; 4, 5, 6
def output = x... in P : ()
You can also consider an expression such as x in P
— or x... in P
— 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
Expr := Bindings ":" Expr
If :
is followed by an identifier, you should separate the two with white space.
Otherwise the colon will be interpreted as beginning a Symbol.
For example, def output {x: x = 7}
will produce 7
, but def output {x:x = 7}
will result in an error message.
Relational abstraction defines a relation without a name. It’s the most important construct in the language. You will see later that all syntactic variations translate into relational abstractions.
The expression that follows the colon is often called the body of the relational abstraction. The arity of a relational abstraction is the number of variables in the bindings plus the arity of the body. If the body is a formula — that is, has arity 0 — then only the variables from the bindings remain.
The examples in this section are based on the following definitions:
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’s 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’s defined. Each of the following examples use a formula:
x: p(x) and q(x)
 Unary relation (one variable
x
).  Value:
{2; 3}
.
 Unary relation (one variable
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 the relational abstraction.  Value:
{"b"; "c"}
.
 Unary relation. The
x, y: p(x) and q(y)
 Binary relation.
 This is the Cartesian product of
p
andq
, 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.
 This is an error because variable
x, y: ∃(t: parent(x, t) and parent(t, y))
 Value:
{("John", "Felix"); ("Mary", "George")}
.
 Value:
x: Int(x) and x > 0
 Value is the infinite relation
{1; 2; 3; 4; ...}
.
 Value is the infinite relation
x, y: x = y
 Binary relation of all values that are equal, for example,
(1, 1)
and('a', 'a')
.
 Binary relation of all values that are equal, for example,
x: x = 1
 Singleton relation
{(1,)}
.
 Singleton relation
x: true
 Infinite unary relation (for example, contains
1
and"abc"
).
 Infinite unary relation (for example, contains
x: false
 Empty unary relation.
x...: p(x...) and q(x...)
 Varargs are explained in Rel Primer: Advanced Syntax.
In this case,
x...
will only represent a single variable, becausep
andq
have arity 1. The value is{1; 2}
.
 Varargs are explained in Rel Primer: Advanced Syntax.
In this case,
{x: p(x) and q(x)}
 If an expression contains curly braces that aren’t used to form a relation literal or parentheses that aren’t used to form a relational application, then the curly braces or parentheses are used solely to indicate precedence. Sometimes a relational abstraction is more clear when it’s enclosed in curly braces. This doesn’t 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:
x, y: x + y
 Ternary, infinite relation.
 Example tuples:
(1, 1, 2)
,(2, 3, 5)
, and(3.5, 1.2, 4.7)
.
x: x + 1
 Binary, infinite relation.
 Example tuples:
(1, 2)
,(1.0, 2.0)
, and(3.14, 4.14)
.
x in Int: x + 1
 Binary, infinite relation.
 Example tuples:
(1, 2)
,(2, 3)
, and(3, 4)
.
x where Int(x): x + 1
 Equivalent to the previous example.
Here are some more advanced examples:
p: today  date_of_birth[p]
 Binary relation of person and their age.
The arity is 2: 1 for
p
plus 1 for the body.
 Binary relation of person and their age.
The arity is 2: 1 for
x: sum[v: scores(x, v)]
 Sum scores
v
, grouped byx
.  Note that there are two relational abstractions here: one outermost, and one that’s an argument of
sum
.  See Aggregation for more details.
 Sum scores
mean[x, y: (actual[x, y]  prediction[x, y]) ^ 2]
 Compute the
mse
for a machine learning solution. Note that the Standard Library definesmse
, which can be used asmse[actual, prediction]
.
 Compute the
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.
 The arguments to
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 thetrain_unit_sales
relation.
 Sum up the sales for every unique
Bindings can also be constants, as an alternative to introducing a separate variable. Examples of constants in a binding of a relational abstraction:

x, 1: abc(x)
 Value:
{("a", 1); ("b", 1); ("c", 1)}
.
 Value:

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 inabc
, which is3
.  The Standard Library defines
count
in this way, and that relation can be used ascount[abc]
in this example.
 Sums the last elements of all tuples.
Since the last element of each tuple is

1: p(_)
 Value:
1
(given thatp
is not empty).  Note that the lefthand side of the relational abstraction doesn’t have to contain an explicit variable.
 The underscore expression is syntactic sugar for an anonymous variable. See Underscore for more details.
 Value:
Note 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 : x * y
Finally, it’s 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.
You can think of the variables introduced in the bindings — x
and y
in this example — as the parameters of the relational abstraction.
If you’re familiar with programming languages, you’ll notice that in some ways relational abstractions are similar to lambda expressions.
An Alternative Form of Relational Abstraction
Relational abstractions are often used as parameters to higherorder abstractions, such as aggregations.
Typically the most important thing to see first in an aggregation is the value that’s being aggregated.
To make this easier to see immediately, the order of the bindings and the body 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
.
 Value

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)}
.
 Value

{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 Comma (Cartesian Product and Conjunction).
 The initial expression is now a tuple.
The value of the entire expression is a ternary relation

(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, or Haskell it may seem strange that the variable introduced in the comprehension (for example, x
in x^2 for x in {1; 2; 3}
) is a part of the result.
In these programming languages, the value of the comprehension is a list of the values of the expression 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
andInt
, not a unary relation of ages. The latter would contain every age value only once.
 This is a binary relation of

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.
 This is the previous example used as an argument to the

sum[age[p] for p in employee]
 The same example, but now in a
sum
aggregation. Here it’s very important that even if two different personsp1
andp2
have the same age, the age of both persons contributes to the sum. This is ensured by havingp
be a part of the relation that is being aggregated.
 The same example, but now in a
Note that max
and sum
compute, respectively, the maximum and the sum of the set of last elements of the tuples in the relation.
The relation can have any arity, or even contain tuples of different arities.
The next section introduces “from” expressions, which do not add the introduced variables to the result, and are thus more similar to comprehensions in programming languages.
“From” Expressions
“From” expressions are similar to relational abstractions, but the variables introduced by the binding are not a 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:
Example  Description 

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 that precedes the from
.
Expression  Value 

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 resulting 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, but it can’t be used outside the scope of the quantifier, so you will get a compilation error with the information thatf
is undefined inname[f]
.
 This definition is incorrect. The variable

def fathers_name = name[f]  x: exists(f: father(x, f))
(wrong) Using the reversed syntax for relational abstraction won’t solve the problem.
There will be an error, because the occurrence of
f
inname[f]
isn’t in the scope of the existential quantifier.
 Using the reversed syntax for relational abstraction won’t solve the problem.
There will be an error, because the occurrence of

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

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

def fathers_name[x] = name[father[x]]
(correct) In this example you actually didn’t need the variable
f
at all, so it could also have been written this way. The logic isn’t always this straightforward, though.
 In this example you actually didn’t need the variable
The construct from x ...
is technically a form of existential quantification.
The following two definitions are equivalent:
def fathers_name = x, f from x, f where father(x, f)
def fathers_name = y, nm : exists(x, f: father(x, f) and y = x and nm = f)
FromWhere
To make Rel more accessible to users who are familiar with LINQ (LanguageIntegrated Query) or SQL, Rel supports a similar syntax for queries:
Expr := Expr "from" Bindings
Although where
doesn’t occur in this grammar rule, it’s a part of Bindings
and leads to a syntax very similar to LINQ.
s.name from s in students
where s.age > 12 and s.age < 20
p.partkey from p in part
where like[p.name, filename]
This example uses composite relations (for example, s.age
and p.name
).
For more details on the semantics of relational composition, also called navigation, see Composition.
Relational Abstraction Alternatives
Since there are a few variants of relational abstractions, it’s important to know which one to use. When writing an abstraction, first consider what would be more readable: introducing the variables first, or beginning with the value that is computed. This splits the options into two categories with only a few alternatives.
In the following examples p
is defined by def 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 SQLlike 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’s 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 relational application with parentheses is a formula, that is, a nullary relation.
This isn’t always the case for partial relational applications, for example, p[x]
.
The syntax mimics that of array and matrix indexing from other languages.
If relation p
is binary, then p[x]
is a unary relation, unless it’s empty.
Note, however, that p[x, y]
— or, equivalently, p[x][y]
— is a nullary relation.
In this case p[x, y]
is equivalent to p(x, y)
, i.e., a partial relational application can sometimes be a relational application.
How you evaluate a relational application also applies largely to how you evaluate a partial relational application.
The main difference is that if the number of arguments is M
, and some of the selected tuples are longer than M
, then the result will be a relation containing the selected tuples stripped of their first M
elements.
This is further discussed in the remainder of this section.
In a partial relational application, the part of the the expression that’s 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 keyvalue format.
It’s also useful for evaluating functions, even those that aren’t stored in the database. For example, consider the following relation:
def square_add[x, y] = x * x + y
The result of evaluating square_add[2, 3]
is the relation {(7,)}
.
The result of a partial relational application is always a relation.
For example, p[_]
doesn’t 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[_]
You can think of a partial relational application as a combination of two operations: filtering and projection. Here’s an example:
// query
{(1, 3); (2, 4); (1, 5); (2, 6)}[2]
You can also use the syntax with square brackets to define relations:
def name[1] = "Noether", "Emmy"
def name[2] = "Hopper", "Grace"
def name[3] = "Curie", "Marie"
def age[1] = 53
def age[2] = 85
def age[3] = 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:
Example  Description 

name[2]  {"(Hopper", "Grace")} . 
name[3, "Curie"]  {"Marie"} . 
name[x1 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 Symbols.
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 don’t extend the expressive power of the language. It’s always possible to rewrite an expression involving a partial relational application as an equivalent expression that doesn’t include a partial relational application.
Here’s an example:
// query
def square_add[x in Number, y in Number] = x * x + y
def output:A = square_add[square_add[2, 3], square_add[3.0, 4]]
def output:B(result) = square_add(2, 3, one) and square_add(3.0, 4, two)
and square_add(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 isn’t 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...)
A partial relational application consists of two elements: the expression that identifies the applied relation, and the arguments in square brackets.
The two are combined with an implicit “application operator.”
The precedence of this invisible operator is lower than that of the composition operator, .
.
So an expression such as R . Q[x]
is equivalent to (R . Q)[x]
.
If that’s not what you want, you should put the partial relational application in parentheses: R . (Q[x])
.
Comma (Cartesian Product and Conjunction)
Expr := Expr "," Expr
The comma operator is a Cartesian product operator.
For example:
// query
def P = (1, 2); (3, 4); (5, 6)
def Q = ("a", 41, "A", 61 ); ("b", 42, "B", 62)
def output = P, Q
When the comma operator is applied to singleton values, it is easier to understand it as a tupling operator, as shown below:
Example  Description 

def p = 1, 2  Binary relation with one tuple. 
1, 2, 3  Ternary relation with one tuple. 
(1, 2, 3)  Also a ternary relation with one tuple. 
{(1, 2, 3)}  Also a ternary relation with one tuple. 
x^2, x^3 from x in {1; 2; 3}  Binary relation (x is not in the result). 
The comma can also be used as a generalized conjunction.
Recall from Boolean Constant Relations that false
is represented by the empty relation {}
and true
is represented by {()}
.
So the Cartesian product of false
with any relation is the empty relation.
Recall from Values that (1, 3, ())
is equivalent to (1, 3)
.
In general, adding an empty tuple as an element of another tuple does not change the latter.
So the Cartesian product of true
with a relation R
is R
.
This means that the comma operator may be used to add conditions to expressions, and in particular to expressions that are not formulas:
// query
def P = (1, 2); (3, 4); (5, 6)
def output = P[x], x < 4 from x
The definition of output
above could have been replaced by one with conjunction, after converting the first expression in the body to a formula:
def output(y) = P(x, y) and x < 4 from x
Here are some more examples:

def soccer_players[t] = players[t], soccer(t)
 The comma serves here as a conjunction with an additional condition that selects only the soccer players.
This is simpler than writing out the logic in the pointwise variant
def soccer_players(t, p) = players(t, p) and soccer(t)
.
 The comma serves here as a conjunction with an additional condition that selects only the soccer players.
This is simpler than writing out the logic in the pointwise variant

def order_price[pos] = order[pos, :price], not exists order[pos, :load_errors]
 Similarly, the comma introduces a filter here. As a result, those rows from a CSV file that contain errors will be skipped.

def count[R] = sum[{R, 1}]
 Every tuple of
R
is extended with a 1, so that computing asum
aggregation actually computes the count.
 Every tuple of
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 ")"
).
The expression inside the parentheses consists of two applications of the comma operator: (1, 2), 3
.
Tuples never occur as elements of tuples, so (1, 2), 3
represents the ternary relation {(1, 2, 3)}
.
Similarly, (1, 2), (3, 4)
represents the arity4 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 combinations of two relations with arity 0:
Left  Right  Left , Right 

{}  {}  {} 
{()}  {}  {} 
{}  {()}  {} 
{()}  {()}  {()} 
Unfortunately the comma character is overloaded by the comma operator and the separator for arguments of applications. In the context of an application, there is a semantic difference between interpreting a comma as a comma operator or interpreting it as a 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]
orfoo[{x: y, z}]
. 
Whenever commas and relational abstractions are involved, you should not rely on the default interpretation, and write your expression in a way that makes the intent clear.

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 invokefoo
with two arguments, then use eitherfoo[x: y][z]
orfoo[{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]
, andfoo[a, {b: c, d}]
. Just as in the previous example, precedence rules selectfoo[{a, b: c, d}]
. It is recommended that you use curly braces to clarify the intent.
 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

sum[R, 1]
 In this incorrect example,
sum
is required to have at least two arguments (which is not the case). The first argument is the relationR
, and the second is the number1
. The intent of the logic is to count the number of tuples inR
by appending1
to all its tuples and then applyingsum
to the relation. To achieve this, the relation argument must be put in parentheses or curly braces:sum[{R, 1}]
.
 In this incorrect example,
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 rightmost operand and is not written in curly braces or parentheses.
Semicolon (Union and Disjunction)
Expr := Expr ";" Expr
The semicolon is a generalized union operator.
For example:
// query
def P = (1, 2); (3, 4); (5, 6)
def Q = ("a", 41, "A", 61 ); ("b", 42, "B", 62)
def output = P; Q
Examples:
 For any relation
p
,{}; p
is equivalent top
. 1; 3
is equivalent tox: x = 1 or x = 3
. If
p
andq
are unary relations, then:p(x); q(x)
is equivalent top(x) or q(x)
.p; q
is equivalent tox: p(x) or q(x)
.
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 combinations of two relations with arity 0:
Left  Right  Left ; Right 

{}  {}  {} 
{()}  {}  {()} 
{}  {()}  {()} 
{()}  {()}  {()} 
Precedence
Expr := "{" Expr "}"
Expr := "(" Expr ")"
Precedence can be indicated with either curly braces or parentheses. The two are exactly equivalent.
For readability, it can be helpful to always use (...)
for singleton relations (scalars) and {...}
for relations that are not singletons.
For example, (x + y) * z
versus {x, y, z: p(x, y, z)}
.
All binary operators associate to the left, unless otherwise stated below.
For example, x  y + z
is equivalent to (x  y) + z
.
From highest precedence to lowest:
_
, variables, names of relations, qualified names, literals,()
, and{}
..
. Relational application and partial relational application.
^
(associates to the right). Unary

. /
,%
,*
,÷
,×
,⊗
, and⊙
.
,+
,⊕
,∩
, and⊓
.∪
and⊔
.=
,!=
,≈
,∼
,≠
,<
,>
,<=
,≤
,>=
,≥
,⊆
,⊇
,⊂
,⊃
,≼
,≽
,≺
,≻
,→
, and←
.¬
andnot
.forall
,∀
,exists
, and∃
.∧
andand
.∨
andor
.⇐
,⇒
(associates to the right), andimplies
(associates to the right).≡
,⇔
,⊻
,≢
,⇎
,xor
, andiff
.<:
and:>
.<++
and++>
.,
.;
.:
(associates to the right).
Note that relational application and partial relational application are created with an implicit operator.
The precedence of this operator is lower than that of the composition operator .
, so an expression such as P . Q[x]
is parsed as (P . Q)[x]
.
If this isn’t what you want, you should use explicit parentheses, for example P . (Q[x])
.
This is illustrated by the following example:
// query
def P = (1, 2)
def Q = {("a", 1); ("a", 2)}
def output:A = Q . P
def output:B = Q . P["a"]
def output:BB = (Q . P)["a"]
def output:BBB = Q . (P["a"])
def output:C = Q . P[1]
def output:CC = (Q . P)[1]
def output:CCC = Q . (P[1])
def output:D = Q . P("a", 2)
def output:DD = (Q . P)("a", 2)
def output:DDD = Q . (P("a", 2))
Relation Literals
Relation literals don’t have a dedicated syntax, but are by convention written with outer curly braces, parentheses around tuples, commas in the tuples, and semicolons between the tuples.
Example  Description 

{1}  Singleton relation (arity 1, cardinality 1). 
{1; 2; 3; 4}  Unary relation (arity 1, cardinality 4). 
{(1, 2); (3, 4); (5, 6)}  Binary relation (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. The tuples can contain variables and other expressions.
For example, {(friend, 1); (family, 2); (partner, 3)}
for binary friend
, family
and partner
has arity 3 and unknown cardinality.
It can be defined explicitly as:
x, y, v:
(friend(x, y) and v = 1) or
(family(x, y) and v = 2) or
(partner(x, y) and v = 3)
Here is a slightly more complicated example.
The second element of the tuple in the relation literal that is the body of the definition for output
is an expression that involves another relation literal and a partial relational application:
// query
def name = {"Bob"; "Jill"; "Joe"}
def father = {("Bob", "Jill"); ("Bob", "Joe")}
def output = {(">", {(1, father, 2)}[_])}
Composition (Navigation)
Expr := Expr "." Expr
The meaning 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 this meaning can be presented more simply.
In particular, since a variable is a singleton relation, x.R
is R[x]
, and R.x
is y... : R(y..., x)
.
The composition operator is sometimes called the dot join operator.
Examples:
 If
parent
is a binary relation, thenparent.parent
is equivalent tox, y: ∃(t: parent(x, t) and parent(t, y))
.  If
players
is a binary relation andt
is a unary relation, thent.players
is equivalent top: players(t, p)
.  If, additionally,
age
is a binary relation, thent.players.age
is equivalent tov: ∃(p: players(t, p) and age(p, v))
.  If
brand_name
is a binary relation, thenbrand_name."Tesla"
is equivalent tob: brand_name(b, "Tesla")
.
The precedence of the composition operator .
is quite high, so an expression such as R . Q(x)
is equivalent to (R . Q)(x)
.
If that is not what you want, you should put the relational application in parentheses: R . (Q(x))
.
The same caveat applies to partial relational applications: R . Q[x]
is equivalent to (R . Q)[x]
.
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
Arithmetic operators allow you to use conventional infix notation in order to invoke arithmetic relations from the Standard Library.
For example, a  b  c * d
is equivalent to subtract[subtract[a, b], multiply[c, d]]
.
The correspondence between arithmetic operators and Library functions is shown in the following table:
Operator  Library Relation 

+  add 
  subtract 
*  multiply 
/  divide 
%  remainder 
÷  trunc_divide 
^  power 
The arithmetic operators have conventional precedence with respect to each other.
The exponentiation operator ^
associates to the right, the others associate to the left.
See Precedence for details.
If the right operand of the exponentiation operator ^
is an identifier, you should separate the two with white space.
Write a^ b
or a ^ b
, but not a^b
.
If ^
is immediately followed by a letter, the operator is interpreted as beginning an identifier, so a^b
will be a sequence of two identifiers — a
followed by ^b
.
Underscore
Expr := "_"
Underscore is a variable without a name.
The compiler rewrites it into the relation x: true
, which is the infinite relation of all values.
After further rewriting, this typically becomes an existentially quantified variable with a unique name.
Underscore is mostly useful if you do not care about certain arguments of a 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[_]]
// Get the second column of a ternary relation `P`:
def Q(x) = P(_, x, _)
You can achieve the same effect by replacing the underscore with Any
.
Existential Quantification
Expr := "exists" Expr
 "∃" Expr
The value of an existential quantification is false
if the argument evaluates to the empty relation, and true
otherwise.
The argument can be an expression of any arity.
The argument of an existential quantification is often a relational abstraction. The effect is very similar to conventional existential quantification. Consider the following example:
// query
def P = 1; 3; 5
def Q = (2, 4); (6, 8)
def output:RA = x, y : P(x), Q[y], x > y
def output:EX = exists(x, y : P(x), Q[y], x > y)
You can read the body of the definition of output:EX
as “there exist x
and y
such that x
belongs to P
, y
belongs to the first column of Q
, and x
is greater than y
.”
This evaluates to true
, as expected.
What really happens here is that the relational abstraction that is the argument of exists
evaluates to a nonempty relation.
You could get exactly the same result with def output:EX = exists output:RA
.
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 ")"
The argument of universal quantification consists of one or more bindings, followed by a colon and an expression. The expression must be a formula, that is, it must evaluate to a relation of arity 0.
The universal quantification is true
if the expresssion that follows the :
is true for all values of the variables specified in the bindings.
In other words, the universal quantification is true
if there is no combination of values for the variables specified in the bindings such that the expression that follows the :
is false.
To put it more succinctly: forall(bindings : E)
is equivalent to not exists(bindings : not E)
.
An important consequence of this is that if the domain of any of the variables is empty, the universal quantification evaluates to true
.
Consider the following example:
// query
def P = 1; 3; 5; 7
def Q = (6, 8); (7, 9)
def R = x : P(x) and Q(_, x)
def output:A = forall(x in P, y in Q[_] : x < y)
def output:B = forall(x in P, y where Q(y, _) : x < y)
def output:C = forall(x in R, y where Q(y, _) : x < y)
def output:D = not exists(x in R, y where Q(y, _) : not(x < y))
def output:E = R
For every x
in P
and every y
in the second column of Q
, x
is smaller than y
, so relation output:A
is true
.
Relation output:B
is false
, because it is not true that, for every x
in P
and every y
in the first column of Q
, x
is smaller than y
.
However, relation output:C
is true
, because the domain of x
is empty, as shown by the fact that output:E
is false
.
Relation output:D
is true
, because there does not exist any x
in R
, so the existential quantification evaluates to false
.
The definition of output:D
is equivalent to the definition of output:C
.
The bindings usually define the domains of the variables, but this is not required:
// query
def P = 1; 3; 5; 7
def Q = (6, 8); (7, 9)
def output = forall(x, y: P(x) and Q[_] = y implies x < y)
The definition of output
is equivalent to the definition of output:A
in the previous example.
In general, you should prefer forall x, y,... where E1(x, y,...) : E2
to forall x, y,... : E1(x, y,...) implies E2
.
For many people the first form is much easier to read.
Examples  Description 

forall(p in person: age[p] > 99)  Are all persons older than 99? 
∀(p in person: centenarian(p))  Are all persons centenarians? This expression features 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 some year enrolled. 
Aggregation
There is no dedicated syntax for aggregations.
Instead, there is a higherorder primitive operation similar to the reduce
function of functional languages.
That operation is used to define various aggregations in the Standard Library.
The underlying primitive operation should not be invoked directly, and is not documented here.
A few examples of aggregations:
Example  Description 

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 ∈ team  Max age by team 
max[Σ[salary[p] for p in member[t]]] for t in team  Max 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.
Every variable is introduced by a binding. The formal parameter specification in the head of a definition is also a form of binding.
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.
HigherOrder Definitions
Higherorder definitions are definitions of relations whose arguments can be relations that are not singletons. A parameter that represents such a relation must begin with an uppercase letter. Such a parameter is often called a higherorder parameter, or a higherorder variable.
A higherorder definition must be annotated with @outline
or @inline
, the former being usually preferable.
Note that @inline
cannot be used for definitions that are directly or indirectly recursive.
In the example below, rotate
is higherorder, because its parameter is intended to be a relation of arbitrary arity.
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
@outline
def rotate[R] {y, x... : R(x..., y)}
def once = rotate[ {1, 10, 100; 2, 20} ]
def output:A = once
def output:B = rotate[once]
def output:C = rotate[rotate[once]]
See section Varargs in Advanced Syntax for an explanation of x...
.
In the example above you could have replaced @outline
with @inline
.
In the following example @outline
is necessary, because the higherorder relation is recursive.
The example computes the transitive closure of a binary relation.
If the binary relation R
contains edges between the nodes of a graph, then nodes A
and B
are in the transitive closure of R
if and only if B
is reachable from A
:
// query
// Compute the transitive closure of a binary relation
@outline
def transitive_closure[R] = R
@outline
def transitive_closure[R] = x, y : R(x, z) and transitive_closure[R](z, y) from z
def edges = (1, 2); (2, 1); (3, 4); (4, 5)
def output = transitive_closure[edges]