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:

ExampleDescription
`def p = 1, 2`Binary relation with one tuple.
`1, 2, 3`Ternary relation with one tuple.
`(1, 2, 3)`Also a ternary relation with one tuple.
`{(1, 2, 3)}`Also a ternary relation with one tuple.
`x^2, x^3 from x in {1; 2; 3}`Binary relation (`x` is not in the result).

The comma can also be used as a generalized conjunction.

Recall from Boolean Constant Relations that `false` is represented by the empty relation `{}` and `true` is represented by `{()}`. So the 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:

LeftRight`Left , Right`
`{}``{} ``{}`
`{()}``{}``{}`
`{}``{()}``{}`
`{()}``{()}``{()}`

Unfortunately the comma character is overloaded by the comma operator and the separator for arguments of applications. In the context of an application, there is a semantic difference between interpreting a comma as a comma operator or 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.