Skip to content
Cartesian Product and Conjunction

Product and Conjunction

Expr := Expr "," Expr
      | "{ , }"

The comma operator is a product operator. The product is almost like a Cartesian product, except that the result is a concatenation of tuples, rather than a pair of tuples.

For example:

// read query
def P = (1, 2)
def Q = ("a", "b")
def R = P, Q
def output = R

The relation R contains the quadruple (1, 2, "a", "b"), not the pair ((1, 2), ("a", "b")).

The empty tuple is the neutral element of the product operation, just like the number one 1 in arithmetic multiplication. More precisely, if R is a relation, then the expressions {()} , R and R, {()} both evaluate to R.

In the simplified form { , } the missing operands default to the neutral element. So the expression {,} is equivalent to {{()}, {()}}, that is, {()}.

The following example illustrates the fact that a product of two relations can be much larger than either of the original relations:

// 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 sets that contain unary tuples, it is effectively 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 product of false with any relation is the empty relation, and the product of true with any 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?