Skip to content
Cartesian Product and Conjunction

Cartesian Product and Conjunction

Expr := Expr "," Expr

The comma operator is a Cartesian product operator.

For example:

// read 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:

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:

// read query
def P = (1, 2); (3, 4); (5, 6)
def output = P[x], x < 4 from x

You could replace the definition of output above with one that uses 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 the 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 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. Write your expression in a way that clarifies the intent.

    • 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 you write this without curly braces, the compiler will report a warning.

    • 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 best to 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.

Next: Union and Disjunction

Was this doc helpful?