supporting expressions

[Geal]

do we need operations like these:

• integers: + - * / %
• strings: concat
• aggregates: count, sum, min, max, average

they would not be too hard to implement, but integrating them to the syntax might be complex

[Geal]

This is a proposal to add a new term type to hold expressions over values, like addition, string concatenation, list intersection, etc.

We would define that new term type as follows:

enum Expression {
  Unary(Operation, Term),
  Binary(Operation, Term, Term),
}

The terms inside he expression could be normal values (numbers, strings, etc) or variables, or even other expressions, that could be resolved when applying a rule.

as an example, if we had the facts num(1), num(2) and the rule result($a + $b) <- num($a), num($b), we would get the facts result(2), result(3), result(4).

Unfortunately, with the current (naive) approach of pregenerating all of the facts by applying rules over and over, we could get into an infinite loop with this rule: num($a + $b) <- num($a), num($b)

To support this, we could either allow expressions only in the body of rules, or switch to a more conventional top down evaluation of rules and facts, ie applying rules only if the generate facts we are looking for in our queries and caveats

[meh]

Question, has there been any cross-pollination from Ddlog?

[Geal]

Not really. It seems that every project that integrates a Datalog starts an implementation from scratch 😆
Differential Datalog's implementation is in bottom up mode, like biscuit does for now, but its focus is on databases where we trust the queries. In biscuit we need to assume some tokens will try to crash the engine

[meh]

Yeah, but I'm wondering if taking some syntax and semantics from there might be interesting.

I like the way the language feels there.

[Geal]

Which ones, more specifically?

[meh]

Mainly the richer atom types provided and pattern matching.

[Geal]

I've given this more thought, and I think we should instead evolve the constraints to be expressions. This would allow most of the interesting cases, but without unbounded generation of new values. This would also provide an easy upgrade path, as current constraints are a subset of expressions (only one variable, comparison with a constant).

[meh]

Sounds like a good plan.

[Geal]

I'd like to add support for aggregates too, but it can significantly increase the complexity of datalog evaluation. There are great use cases there, though, like generating the intersection of sets: each block comes with a fact containing a set of accepted values, we have a verifier rule that generates the set of accepted values from all blocks

[Geal]

Current list of operations that should be supported (the schema will be updated):

Unary operations:
any subexpression: (expression) Parens

Boolean:

• ! negate

String, Bytes, set:

• .length() length

Binary operations:

Integer:

• < less than
• > greater than
• <= less or equal
• >= greater or equal
• == equal

Date:

• < less than
• > greater than
• <= less or equal
• >= greater or equal
• == equal
• + add (with overflow check)
• - sub (with overflow check)
• * mul (with overflow check)
• / div (with overflow check)

Date:

• < less than
• > greater than
• <= less or equal
• >= greater or equal
• == equal

String:

• .starts_with(value: string) prefix
• .ends_with(value: string) suffix
• .matches(value: string) regex
• == equal

Symbol:*

• == equal

Byte array:

• == equal

Boolean:

• && and
• || or

Set:

• .contains(value) Contain. If the value is a set, the operation is .is_superset(value)
• == equal
• .intersection(set) intersection
• .union(set) union

There is now a sample for those operations: 1c09f36