Skip to content
REL
REFERENCE
Rel Language

Rel Language Reference

Reference guide for the Rel language.

Introduction

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

Rel is a declarative, relational modeling language.

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

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

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

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

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

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

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

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

In Rel, this example could be written as follows:

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

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

Terminology

Frequently used terms are gathered here for easy reference.

TermExplanation
ArgumentOne of the expressions between the parentheses of a relational application or the brackets of a partial relational application.
ArityNumber 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 relationA base relation is defined completely by the data it contains. This corresponds to a table in SQL.
Binary relationRelation of arity 2.
BodyThe main expression in a definition or a relational abstraction.
CardinalityNumber of tuples in a relation.
ColumnThe k-th column of relation R is the set of data values that are the k-th elements of the tuples in R.
Data valueA number, a string, etc. See Values.
Derived relationA 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.
ElementA data value in a tuple. Elements are ordered by position from 1 to NN, where NN is the length of the tuple.
Empty relationRelation with no tuples (cardinality 0).
FormulaAn expression that evaluates to a relation of arity 0 (i.e., to true or false).
FunctionRelation with a functional dependency from the initial elements of a tuple to the last element.
nn-ary relationRelation of arity nn.
Nullary relationRelation 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 nameA 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].
ParameterA variable introduced in the head of a definition or in the “bindings” part of a relational abstraction.
RelationA relation is a set of tuples. The tuples in a Rel relation may have different lengths or data type signatures.
SetAn unsorted collection of items, each of which is unique in the collection.
SingletonRelation of cardinality 1 and arity 1.
Ternary relationRelation of arity 3.
TupleAn 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 relationRelation of arity 1.

Values

Every value in Rel is a first-order 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:

12
34
56

{(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 first-order relation. This means, in particular, that:

  • Relations cannot contain relations. Relations can contain tuples whose elements are data values such as integers, floating-point numbers, fixed-point 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 fixed-size Julia types.
  • A stand-alone 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 values 3 and 4 are extracted from the tuple (3, 4) and converted to singletons. The variable x now represents {(3,)} and y represents {(4,)}.
  • In z = x + y the data values 3 and 4 are extracted from x and y and added. The result is converted to the singleton {(7,)} represented by z.

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 end-of-line comments.

Identifiers

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

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. First-order variables must begin with a lower-case letter, and higher-order variables must begin with an upper-case letter. See Higher-Order 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 upper-case “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 higher-order 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

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

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

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

It’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:

  1. A binding with where cannot appear in the head of a definition.
  2. 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 one-sided 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 user-defined relations may be modified when a new relation is added to the Library. Scoping user-defined 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 zero-arity relations: see Boolean Constant Relations. So the values of formulas, just like the values of other expressions, are relations.

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

Sometimes a formula cannot be evaluated. For example, the formula forall(x in Int : exists(y in Int : y = x + 1)) cannot be evaluated, because its variables 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 first-order logic, a formula with free variables cannot be true or false. In this context it is worth knowing that variables appearing on the left-hand side of a definition are implicitly universally quantified. This is also the case for variables that appear in the “bindings” part of a relational abstraction.

For example, 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 front-end compiler (“not bound”) or by the back-end optimizer (“not ground”). All these terms refer to the same concept. The term used in this manual is “ungrounded.”

Relational application is the only mechanism through which a variable x can be grounded. If x occurs as an argument of a finite relation, it thereby becomes grounded. If x occurs as an argument of an infinite relation, it will be grounded if there are enough other 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 built-in 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 free-standing 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 e2are 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:

e1e2e1 and e2
falsefalsefalse
falsetruefalse
truefalsefalse
truetruetrue

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:

e1e2e1 or e2
falsefalsefalse
falsetruetrue
truefalsetrue
truetruetrue

The semicolon operator is a generalization of or, just like the comma operator is a generalization of and. 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:

e1e2e1 implies e2
falsefalsetrue
falsetruetrue
truefalsefalse
truetruetrue

Negation

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

Just like for the other logical operators, the argument of not must be a formula, that is, an expression that denotes a relation of arity 0.

The value not e depends on the value of e, as follows:

enot e
falsetrue
truefalse

Boolean Constant Relations

Expr := "true"
      | "false"

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

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

Comparison Operators

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

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

Examples: x < 5, x > 5, x != 0, "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.

Non-unary 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 non-unary tuples. However, if two relations, P and Q, contain unary tuples as well as non-unary 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: If-Then-Else-End

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.

Floating-Point Constants

Expr := [0-9]+ "." [0-9]* exponent?
      | [0-9]+ exponent
      | "." [0-9]+ exponent?
 
decimalDigit  := [0-9]
decimalDigits := decimalDigit+
exponent      := ('e' | 'E') ('+' | '-')? decimalDigits

Examples:

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

Character Constants

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

Examples: 'c' and '文'.

String Constants

String constants are constant sequences of characters.

As described in 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 multi-line
 "string"
  constant"""

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

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

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

The exact rules are very similar to those found in Triple-Quoted 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 multi-line
 "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 triple-quoted 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 := [0-9][0-9][0-9][0-9] "-" [0-9][0-9] "-" [0-9][0-9]

Constants of type Date are written in the ISO 8601 extended format.

Examples: 2021-01-01 and 2100-04-03.

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

DateTime Constants

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

Constants of type DateTime use the ISO 8601 extended format. A time zone is required.

Example: 2021-01-01T21: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.
  • 1

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

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

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

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

    • Equivalent to the previous example.
  • x ∈ Int

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

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

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

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

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

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

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

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

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

For the in/ case, the expression must have arity 1 if the left-hand 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}.
  • 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"}.
  • x, y: p(x) and q(y)
    • Binary relation.
    • This is the Cartesian product of p and q, which is {(1, 2); (1, 3); (1, 4); (2, 2); (2, 3); (2, 4), (3, 2); (3, 3); (3, 4)}
  • x, t, y: parent(x, t) and parent(t, y)
    • Ternary relation.
    • Value: {("John", "Mary", "Felix"); ("Mary", "Felix", "George")}.
  • x, y: parent(x, t) and parent(t, y)
    • This is an error because variable t is never introduced.
  • x, y: ∃(t: parent(x, t) and parent(t, y))
    • Value: {("John", "Felix"); ("Mary", "George")}.
  • x: Int(x) and x > 0
    • Value is the infinite relation {1; 2; 3; 4; ...}.
  • x, y: x = y
    • Binary relation of all values that are equal, for example, (1, 1) and ('a', 'a').
  • x: x = 1
    • Singleton relation {(1,)}.
  • x: true
    • Infinite unary relation (for example, contains 1 and "abc").
  • x: false
    • Empty unary relation.
  • x...: p(x...) and q(x...)
  • {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.
  • x: sum[v: scores(x, v)]
    • Sum scores v, grouped by x.
    • Note that there are two relational abstractions here: one outermost, and one that’s an argument of sum.
    • See Aggregation for more details.
  • mean[x, y: (actual[x, y] - prediction[x, y]) ^ 2]
    • Compute the mse for a machine learning solution. Note that the Standard Library defines mse, which can be used as mse[actual, prediction].
  • x: edge(x, x)
    • Unary relation of all nodes that have a self edge.
  • ∃(c ∈ course: ∀(s ∈ student: enrolled(c, s)))
    • The arguments to and are relational abstractions.
  • sum[date, store_nbr, item_nbr: train_unit_sales[date, store_nbr, item_nbr]]
    • Sum up the sales for every unique (date, store_nbr, item_nbr) triple in the train_unit_sales relation.

Bindings can also 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)}.
  • def count_abc = sum[x, 1: abc(x)]

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

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

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 higher-order 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.
  • x+1 for x in {1; 2; 3}

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

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

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

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

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

To users familiar with list comprehension in programming languages such as Python, Julia, 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 and Int, not a unary relation of ages. The latter would contain every age value only once.
  • max[age[p] for p in employee]

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

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

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:

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

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

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

The from construct is particularly useful if auxiliary variables are needed in some bigger definition. Typically this comes up in the domain of a binding. For example, suppose that you want to define a binary relation that associates a person x with the name of the father of x. The problem is that you must find the father of x, but the father is not a part of the 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 that f is undefined in name[f].
  • 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 in name[f] isn’t in the scope of the existential quantifier.
  • def fathers_name = x: {name[f] from f where father(x, f)} (correct)

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

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

    • In this example you actually 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.

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)

From-Where

To make Rel more accessible to users who are familiar with LINQ (Language-Integrated 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 SQL-like and lists the computed value separately.

Partial Relational Application

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

The square bracket syntax is used to project and select a slice of the relation. It’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 key-value 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:

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

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

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

Some partial relational applications can be written without square brackets. These are the applications of relations whose initial elements are 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:

ExampleDescription
def p = 1, 2Binary relation with one tuple.
1, 2, 3Ternary 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 point-wise variant def soccer_players(t, p) = players(t, p) and soccer(t).
  • def order_price[pos] = order[pos, :price], not exists order[pos, :load_errors]

    • Similarly, the comma introduces a filter here. 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 a sum aggregation actually computes the count.

Note that comma is really an operator and there is no dedicated syntax for tuples in the language. For example, (1, 2, 3) is an expression that uses parentheses: Expr := "(" Expr ")"). 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 arity-4 relation {(1, 2, 3, 4)}.

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

LeftRightLeft , 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] or foo[{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 invoke foo with two arguments, then use either foo[x: y][z] or foo[{x: y}, z].

  • foo[a, b: c, d]

    • A similar problem exists in the bindings of the abstraction, because a comma is also used there to separate formal parameters. In this case, the possible interpretations are foo[{a, b: c, d}], foo[{a, b: c}, d], foo[a, {b: c}, d], and foo[a, {b: c, d}]. Just as in the previous example, precedence rules select foo[{a, b: c, d}]. It is recommended that you use curly braces to clarify the intent.
  • 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 relation R, and the second is the number 1. The intent of the logic is to count the number of tuples in R by appending 1 to all its tuples and then applying sum to the relation. To achieve this, the relation argument must be put in parentheses or curly braces: sum[{R, 1}].

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

The compiler raises a warning for cases where the interpretation is ambiguous. The warning is triggered by an expression that has a comma as the 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 to p.
  • 1; 3 is equivalent to x: x = 1 or x = 3.
  • If p and q are unary relations, then:
    • p(x); q(x) is equivalent to p(x) or q(x).
    • p; q is equivalent to x: 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:

LeftRightLeft ; 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:

  1. _, variables, names of relations, qualified names, literals, (), and {}.
  2. ..
  3. Relational application and partial relational application.
  4. ^ (associates to the right).
  5. Unary -.
  6. /, %, *, ÷, ×, , and .
  7. -, +, , , and .
  8. and .
  9. =, !=, , , , <, >, <=, , >=, , , , , , , , , , , and .
  10. ¬ and not.
  11. forall, , exists, and .
  12. and and.
  13. and or.
  14. , (associates to the right), and implies (associates to the right).
  15. , , , , , xor, and iff.
  16. <: and :>.
  17. <++ and ++>.
  18. ,.
  19. ;.
  20. : (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.

ExampleDescription
{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, then parent.parent is equivalent to x, y: ∃(t: parent(x, t) and parent(t, y)).
  • If players is a binary relation and t is a unary relation, then t.players is equivalent to p: players(t, p).
  • If, additionally, age is a binary relation, then t.players.age is equivalent to v: ∃(p: players(t, p) and age(p, v)).
  • If brand_name is a binary relation, then brand_name."Tesla" is equivalent to b: 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:

OperatorLibrary 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.

ExamplesDescription
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 higher-order 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:

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

Variable Scope

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

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.

Higher-Order Definitions

Higher-order 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 higher-order parameter, or a higher-order variable.

A higher-order 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 higher-order, 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 higher-order 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]