Relix

Relix for fun

Relix is built for joining databases, files and APIs, but relational algebra is a general tool, and it answers some surprising questions. This page runs a spaceship from Conway's Game of Life, a Turing machine, a royal family tree and a Pokémon battle, each in a handful of lines.

Every example here runs on each build, and the tables printed after them are what the engine returns. Within a section the examples build on each other, so the later ones use the relations the earlier ones declared.

The Game of Life

The Game of Life is played on an endless grid of cells, each alive or dead. Every generation, a dead cell with exactly three live neighbours comes to life, a live cell with two or three survives, and every other cell dies. A spaceship is a pattern that returns to its own shape some generations later, shifted across the grid, so it glides forever.

In Relix the live cells are a relation of (x, y) pairs. Rather than typing 30 coordinates, draw the ship, one row of text per line of the grid, and let a query find the Os. Columns numbers the positions along a row, and Mid reads the character at each one:

Query
Ship := [
| y  | row           |
|----|---------------|
| 0  | ....O         |
| 1  | ...OOO        |
| 2  | ..OO.OO       |
| 4  | .O.O.O.O..O   |
| 5  | OO...O...OOO  |
| 6  | OO...O......O |
| 7  | ..........O.O |
| 8  | ........O.O   |
| 9  | .........O..O |
| 10 | ............O |
];

source Columns from generator { name: "Range", lo: "1", hi: "13" };

Gen0 := { π n - 1 → x, y (σ Mid(row, n, 1) = "O" (Ship × Columns)) };

query { γ COUNT(*) → cells (Gen0) };
Result
 cells
 ─────
    30
(1 row)

One generation is two functions. The first counts every cell's live neighbours: pair each live cell with the eight offsets around it, shift, and count how often each position is reached. The second applies the rules: a count of 3 is alive, and a count of 2 is alive only if the cell already was, which is a join with the generation it was given. Each takes the board as a relation parameter, a relation with x and y columns, so the rule is written once and works on any board.

Around := [
| dx | dy |
|----|----|
| -1 | -1 |
| -1 | 0  |
| -1 | 1  |
| 0  | -1 |
| 0  | 1  |
| 1  | -1 |
| 1  | 0  |
| 1  | 1  |
];

def neighbours(G: RELATION(x: NUMBER, y: NUMBER)) : RELATION := {
  γ x, y, COUNT(*) → n (π x + dx → x, y + dy → y (G × Around))
};

def generation(G: RELATION(x: NUMBER, y: NUMBER)) : RELATION := {
  π x, y (σ n = 3 (neighbours(G))) ∪ π x, y (σ n = 2 (neighbours(G)) ⋈ G)
};

Gen1 := { generation(Gen0) };
Gen2 := { generation(Gen1) };
Gen3 := { generation(Gen2) };
Gen4 := { generation(Gen3) };
Gen5 := { generation(Gen4) };

Watch the ship change shape, and its top edge (the smallest y) creep upwards:

Query
query { τ generation (
  π 0 → generation, cells, top (γ COUNT(*) → cells, MIN(y) → top (Gen0))
∪ π 1 → generation, cells, top (γ COUNT(*) → cells, MIN(y) → top (Gen1))
∪ π 2 → generation, cells, top (γ COUNT(*) → cells, MIN(y) → top (Gen2))
∪ π 3 → generation, cells, top (γ COUNT(*) → cells, MIN(y) → top (Gen3))
∪ π 4 → generation, cells, top (γ COUNT(*) → cells, MIN(y) → top (Gen4))
∪ π 5 → generation, cells, top (γ COUNT(*) → cells, MIN(y) → top (Gen5))
) };
Result
 generation  cells  top
 ──────────  ─────  ───
          0     30    0
          1     31    0
          2     30   -1
          3     37   -1
          4     38   -2
          5     30   -2
(6 rows)

After five generations it is back to 30 cells. To show it is the same 30 cells, move the starting ship up two rows and compare it with generation 5. This time the five generations need no views at all: ITERATE applies a step round after round, each round replacing the last, and the step is the generation function applied to the previous round, G. The symmetric difference ∆ returns every cell that is in one and not the other:

Query
query { π x, y - 2 → y (Gen0) ∆ ITERATE G (Gen0, generation(G)) ROUNDS 5 };
Result
 x  y
 ─  ─
(0 rows)

Nothing differs: the ship has flown two cells in five generations, exactly as Paul found it would.

ITERATE is the right operator here rather than FIX, Relix's recursion operator. FIX only ever adds rows, which is what guarantees it finishes on a cyclic graph, and in Life cells die. The next section is one that FIX can run.

This section is dedicated to the memory of my brother Paul Tooke. The spaceship in this section is 30P5H2V0, which Paul found on 7 December 2000. It is the smallest known spaceship that travels at 2c/5. Paul found many of the Game of Life's notable spaceships, among them the dragon, the first ever found that travels at c/6.

— David

A Turing machine

A Turing machine is a head moving along a tape of cells. At each step it reads the cell under the head, and a table of rules, keyed by its current state and the symbol it read, says what to write, which way to move, and which state to go to next. It stops when it reaches a state with no rules. Anything a computer can compute, some Turing machine computes.

The rules are a relation. This is the three-state busy beaver: a machine that runs as long as it can, and marks as many cells as it can, before it stops. □ is a blank cell and ■ a marked one, and a move of 1 is a step right, -1 a step left:

Rules := [
| state | read | write | move | next |
|-------|------|-------|------|------|
| A     | □    | ■     | 1    | B    |
| A     | ■    | ■     | 1    | HALT |
| B     | □    | □     | 1    | C    |
| B     | ■    | ■     | 1    | B    |
| C     | □    | ■     | -1   | C    |
| C     | ■    | ■     | -1   | A    |
];

Start := [
| step | state | head | tape |
|------|-------|------|------|
| 0    | A     | 1    | □    |
];

A configuration is one row: the step number, the state, the head's position and the whole tape as a string. FIX starts from Start and applies one step at a time. The inner projection joins the configuration to the rule for its state, keeps the rule whose read is the symbol under the head, and writes, moves and changes state. The outer projection grows the tape by one blank cell whenever the head steps off either end, so the tape is as long as the machine needs. CStr makes the tape's type explicit, so that each step's rows have the same columns and types as Start:

Query
Run := { FIX M (
  Start,
  π step, state, IIf(head = 0, 1, head) → head,
          CStr(IIf(head = 0, "□" + tape,
               IIf(head > Len(tape), tape + "□", tape))) → tape
    (π step + 1 → step, next → state, head + move → head,
       Left(tape, head - 1) + write + Mid(tape, head + 1) → tape
      (σ Mid(tape, head, 1) = read (M ⋈ Rules)))
) };

query { τ step (Run) };
Result
 step  state  head  tape
 ────  ─────  ────  ──────
    0  A         1  □
    1  B         2  ■□
    2  C         3  ■□□
    3  C         2  ■□■
    4  C         1  ■■■
    5  A         1  □■■■
    6  B         2  ■■■■
    7  B         3  ■■■■
    8  B         4  ■■■■
    9  B         5  ■■■■□
   10  C         6  ■■■■□□
   11  C         5  ■■■■□■
   12  C         4  ■■■■■■
   13  A         3  ■■■■■■
   14  HALT      4  ■■■■■■
(15 rows)

The whole run is the answer: fourteen steps, six marks, then HALT, which has no rules, so the join finds nothing more and the fixpoint is complete. At step 5 the head stepped off the left end and the tape grew to meet it.

This is also why FIX is as powerful as a programming language. It can run any Turing machine given its rules, including a machine that never stops. SQL's WITH RECURSIVE is Turing complete for the same reason, and for the same reason no engine can tell in advance whether every recursive query finishes.

A royal family tree

Genealogy programs exchange family trees as GEDCOM files, and Relix reads one directly: connection family from gedcom { path: "tudors.ged" } makes its people and families into relations. The one a family tree query needs is the edge from each parent to each child, which is declared inline here so that the section runs as written — the family history case study works the same shape of problem through the connector, ancestors and all:

Parents := [
| parent               | child                |
|----------------------|----------------------|
| Henry VII            | Arthur Tudor         |
| Henry VII            | Margaret Tudor       |
| Henry VII            | Henry VIII           |
| Henry VII            | Mary Tudor           |
| Elizabeth of York    | Arthur Tudor         |
| Elizabeth of York    | Margaret Tudor       |
| Elizabeth of York    | Henry VIII           |
| Elizabeth of York    | Mary Tudor           |
| Henry VIII           | Mary I               |
| Henry VIII           | Elizabeth I          |
| Henry VIII           | Edward VI            |
| Catherine of Aragon  | Mary I               |
| Anne Boleyn          | Elizabeth I          |
| Jane Seymour         | Edward VI            |
| Margaret Tudor       | James V              |
| James IV             | James V              |
| Margaret Tudor       | Margaret Douglas     |
| Archibald Douglas    | Margaret Douglas     |
| James V              | Mary, Queen of Scots |
| Mary of Guise        | Mary, Queen of Scots |
| Margaret Douglas     | Lord Darnley         |
| Matthew Stewart      | Lord Darnley         |
| Mary, Queen of Scots | James VI and I       |
| Lord Darnley         | James VI and I       |
| Mary Tudor           | Frances Brandon      |
| Charles Brandon      | Frances Brandon      |
| Frances Brandon      | Lady Jane Grey       |
| Henry Grey           | Lady Jane Grey       |
];

When Elizabeth I died childless in 1603, the crown passed to James VI of Scotland, because he descended from her grandfather, Henry VII. He descended from him twice, in fact. PATH walks the tree and counts the generations to every relative it reaches: Down walks from parents to children, and Up from children to parents. Everyone who lies between Henry and James is both a descendant of one and an ancestor of the other, which is a join of the two walks:

Query
Down := { PATH parent, child HOPS 1 TO 10 AS generations (Parents) };
Up   := { PATH child, parent HOPS 1 TO 10 AS generations (Parents) };

query { τ generations, person (
  π child → person, generations (σ parent = "Henry VII" (Down))
  ⋈ π parent → person (σ child = "James VI and I" (Up))
) };
Result
 person                generations
 ────────────────────  ───────────
 Margaret Tudor                  1
 James V                         2
 Margaret Douglas                2
 Lord Darnley                    3
 Mary, Queen of Scots            3
(5 rows)

Two people in each generation after the first: the two lines of descent, side by side. Margaret Tudor, Henry VIII's sister, is the grandmother of both of James's parents, Mary, Queen of Scots, and Lord Darnley.

How were Elizabeth and James related? Walk up from each of them, and join the two walks on the ancestors they share:

Query
query { τ common (
  π parent → common, generations → elizabeth (σ child = "Elizabeth I" (Up))
  ⋈ π parent → common, generations → james (σ child = "James VI and I" (Up))
) };
Result
 common             elizabeth  james
 ─────────────────  ─────────  ─────
 Elizabeth of York          2      4
 Henry VII                  2      4
(2 rows)

Their nearest common ancestors are two generations above Elizabeth and four above James. Two generations each way would make them first cousins, and James is two further down, so he was Elizabeth's first cousin twice removed.

Pokémon

Pokémon battles turn on types: a water attack is super effective against a fire Pokémon, doing double damage. The data here comes from PokeAPI, a free public API. On this page it is declared inline, so that the examples run without a network connection on every build, but each inline relation has exactly the columns the live version has, and the http statements that fetch it are shown after it. Put those in place of the inline table and the same queries run against the live data.

SuperEffective pairs each attacking type with every type it does double damage to. These are all the rows PokeAPI returns for the eight attacking types listed:

SuperEffective := [
| attack   | defend   |
|----------|----------|
| fire     | bug      |
| fire     | steel    |
| fire     | grass    |
| fire     | ice      |
| water    | ground   |
| water    | rock     |
| water    | fire     |
| grass    | ground   |
| grass    | rock     |
| grass    | water    |
| electric | flying   |
| electric | water    |
| ground   | poison   |
| ground   | rock     |
| ground   | steel    |
| ground   | fire     |
| ground   | electric |
| rock     | flying   |
| rock     | bug      |
| rock     | fire     |
| rock     | ice      |
| ice      | flying   |
| ice      | ground   |
| ice      | grass    |
| ice      | dragon   |
| flying   | fighting |
| flying   | bug      |
| flying   | grass    |
];

Charizard := [
| name      | type1 | type2  |
|-----------|-------|--------|
| charizard | fire  | flying |
];

The live version reads one document per type and one per Pokémon. Each type's double_damage_to is a list of { "name": … } objects, and declaring that shape in the schema, rather than leaving it untyped, is what gives defend the same type as the inline column. μ unnests the list into one row per type hit:

source FireType from http { url: "https://pokeapi.co/api/v2/type/fire",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };
source WaterType from http { url: "https://pokeapi.co/api/v2/type/water",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };
source GrassType from http { url: "https://pokeapi.co/api/v2/type/grass",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };
source ElectricType from http { url: "https://pokeapi.co/api/v2/type/electric",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };
source GroundType from http { url: "https://pokeapi.co/api/v2/type/ground",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };
source RockType from http { url: "https://pokeapi.co/api/v2/type/rock",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };
source IceType from http { url: "https://pokeapi.co/api/v2/type/ice",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };
source FlyingType from http { url: "https://pokeapi.co/api/v2/type/flying",
    schema: { attack: STRING at "$.name",
              double_damage_to: [{ name: STRING }] at "$.damage_relations.double_damage_to" } };

SuperEffective := { π attack, double_damage_to.name → defend (μ double_damage_to (
    FireType ⊎ WaterType ⊎ GrassType ⊎ ElectricType
  ⊎ GroundType ⊎ RockType ⊎ IceType ⊎ FlyingType)) };

source Charizard from http { url: "https://pokeapi.co/api/v2/pokemon/charizard",
    schema: { name: STRING, type1: STRING at "$.types[0].type.name",
              type2: STRING at "$.types[1].type.name" } };

Charizard is both fire and flying, and an attack that is super effective against both of its types does four times the damage. "Which attacking types beat every one of these types" is relational division, ÷, an operator SQL does not have:

Query
CharizardTypes := { π type1 → defend (Charizard) ∪ π type2 → defend (Charizard) };

query { SuperEffective ÷ CharizardTypes };
Result
 attack
 ──────
 rock
(1 row)

Water puts out fire but not a flying Pokémon, and electric grounds a flyer but does nothing special to fire. Only rock does both.

Pokémon also evolve, some more than once, and Eevee in eight different directions. Evolves is the evolution edge list. Here it is inline:

Evolves := [
| species    | evolves_into |
|------------|--------------|
| pichu      | pikachu      |
| pikachu    | raichu       |
| charmander | charmeleon   |
| charmeleon | charizard    |
| eevee      | vaporeon     |
| eevee      | jolteon      |
| eevee      | flareon      |
| eevee      | espeon       |
| eevee      | umbreon      |
| eevee      | leafeon      |
| eevee      | glaceon      |
| eevee      | sylveon      |
];

PokeAPI publishes each family as a nested evolution chain: the first species, a list of what it evolves into, and for each of those a list of what it evolves into. The schema declares those two levels, and the live version flattens them into the same edge list, one level at a time:

source PichuChain from http { url: "https://pokeapi.co/api/v2/evolution-chain/10",
    extract: json("$.chain"),
    schema: { species: STRING at "$.species.name",
              evolves_to: [{ species: { name: STRING },
                             evolves_to: [{ species: { name: STRING } }] }] } };
source CharmanderChain from http { url: "https://pokeapi.co/api/v2/evolution-chain/2",
    extract: json("$.chain"),
    schema: { species: STRING at "$.species.name",
              evolves_to: [{ species: { name: STRING },
                             evolves_to: [{ species: { name: STRING } }] }] } };
source EeveeChain from http { url: "https://pokeapi.co/api/v2/evolution-chain/67",
    extract: json("$.chain"),
    schema: { species: STRING at "$.species.name",
              evolves_to: [{ species: { name: STRING },
                             evolves_to: [{ species: { name: STRING } }] }] } };

StageTwo := { π species, evolves_to.species.name → evolves_into, evolves_to.evolves_to → later
    (μ evolves_to (PichuChain ⊎ CharmanderChain ⊎ EeveeChain)) };
StageThree := { π evolves_into → species, later.species.name → evolves_into (μ later (StageTwo)) };

Evolves := { π species, evolves_into (StageTwo) ∪ StageThree };

Everything a Pokémon can eventually become is the transitive closure of the edge list:

Query
query { σ species = "pichu" (CLOSURE species, evolves_into (Evolves)) };
Result
 species  evolves_into
 ───────  ────────────
 pichu    pikachu
 pichu    raichu
(2 rows)

Read the edges both ways, with ↔, and the closure joins up whole families. Jolteon's family is Eevee and all eight of its evolutions, Jolteon included:

Query
query { τ evolves_into (σ species = "jolteon" (CLOSURE species ↔ evolves_into (Evolves))) };
Result
 species  evolves_into
 ───────  ────────────
 jolteon  eevee
 jolteon  espeon
 jolteon  flareon
 jolteon  glaceon
 jolteon  jolteon
 jolteon  leafeon
 jolteon  sylveon
 jolteon  umbreon
 jolteon  vaporeon
(9 rows)

Pokémon is a trademark of Nintendo, Creatures and Game Freak. This page is not affiliated with them.