TypeDB 3.0: list role players and changes to standard role definitions

[flyingsilverfin]

Problem to Solve

Currently there is no way to operate over ordered collections in TypeDB. We address one aspect of this, which is ordering role players within relations.

Current Workaround

Currently, users explicitly order relations with attributes or with a linked-list style relation.

Proposed Solution

We aim to consistently extend TypeQL to have role player list semantics and make it easy for users by drawing strong parallels with attribute ownership (#7028).

Modifications to existing multi-set semantics

Current multiset-semantics syntax:

traffic-light sub relation,
  relates light;

Currently, this allows a traffic light to have red, red, red as a 3-way reflexive relation representing a traffic light, in other words, each role type restricts to an unordered multiset of players.

We aim to simplify this by introducing defaults and moving to set semantics:

traffic-light sub relation,
  relates light; // default cardinality: @card(1,1)

We will make the default cardinality of roles with set semantics @card(1,1) and also disallow duplicates.

Extension to list semantics

Defining ordered roles

We will allow extending role players to be 'ordered':

traffic-light sub relation,
  relates light[];

We should consider this to be a modification of the existing traffic-light:light roles, excep that now these can be considered a list instead of a set: ordering is provided, duplicates are allowed, and there is no restriction on cardinality. In short, this switches from set semantics to proper list semantics.

Note that this means we cannot easily optimise/index relations with list players, since they can be unbounded, and we should expect them to be in general less performant when traversing from role players to role players without visiting the relation explicitly.

If one requires ordered-set semantics, we can enforce this with an @distinct annotation:

traffic_light sub relation,
  relates light[] @distinct;

Inserting ordered players

Insert role players must use list expression. E.g., we can use the bracket constructor for lists:

insert
  $r isa light, has color 'red';
  $y isa light, has color 'yellow';
  $g isa light, has color 'green';
  (light[]: [$r, $y, $g]) isa traffic_light;

Inserts will always address entire lists at a time. To easily insert individual role players, we provide a @replace annotation. E.g., to append a single role player we may write:

match
  $tl (light[]: $l) isa traffic_light; $x isa ligth, has color 'blue';
insert
  $tl (light[]: $l + [$b]) @replace;  // all traffic lights end with blue!

Deleting and updating ordered player

Similarly to inserts, deletes will always require us to deal with entire lists in each statement relating to the ordered players of a relation.

Reading ordered players (data read)

Set-semantically data can be read as before:

match $tl (light: $light) isa traffic_light;

However, lists can be read as either individual elements of a collection or as an entire ordered list:

match $tl (light: $light) isa traffic_light; // one light at a time, as usual
match $tl (light[]: $lights) isa traffic_light; // an ordered collection of lights

Note that we are now introducing variables that contain an ordered collection of concepts! Eg. the type of $lights is List<Light> or OrderedSet<Light> depending on the annotations provided in the schema.

We should be able to index into the ordered collection as one would expect:

match 
$tl (light[]: $lights) isa traffic_light; 
$lights[0] has color 'red';

Reading ordered roles (schema read)

Ordered roles can by read from schema. The basic principle is that type variables $type will always match simple schema types, but that we may apply the list type operator ([]) to them just as we can apply it to simple types (e.g. string -> string[], edge -> edge[]). Thus, when variabilizing the role type in:

match
  $traffic-light (light[]: $lights) isa traffic_light;

we would obtain:

match
  $traffic-light ($role_type[]: $lights) isa traffic_light;

In this case, $role_type will match the role type traffic-light:light.

[lveillard]

Will array ops be available?
Will dynamic or more complex cardinality rules be available?

Some detailed example: #6327 (comment)

[lveillard]

Right now the default behaviour (and most of your tests are built around this) is @Card(1) which is rare.

WiIl the default @card be @card(0,1) instead?

I think the most two common cardinality configs are @card(0,1) and @card(0,*)