# Trick-Or-Treating With Rel

What's better than a bag full of candy for Halloween?

Here at RelationalAI, we're passing out knowledge graphs to trick-or-treaters this year. Come and get spooked with us as we solve a Halloween logic puzzle in Rel, our relational modeling language. You'll see how to model a problem, store facts, and infer new knowledge from those facts.

So grab your flashlight, put on your favorite costume, and let's go trick-or-treating with Rel!

## The Setup

Four children --- two girls named Judy and Jessica, and two boys named Frank and Toby --- are going trick-or-treating. The children are all different ages, ranging from seven years old to 10 years old. Each child is accompanied by an adult: either their brother, sister, aunt, or uncle. They wear one of four costumes: a ghost, goblin, vampire, or werewolf. And each child carries a different color flashlight: red, blue, green, or orange.

We'll be given ten clues that we'll have to use to figure out how old each child is, what costume they wear, which flashlight they carry, and which adult accompanies them. But first, let's insert the base data we're working with into our database:

```
// write query
module trick_or_treat_data
def adult = "Brother"; "Sister"; "Aunt"; "Uncle"
def age = 7; 8; 9; 10
def child = "Jessica"; "Judy"; "Frank"; "Toby"
def costume = "Ghost"; "Goblin"; "Vampire"; "Werewolf"
def flashlight = "Red"; "Blue"; "Green"; "Orange"
end
def insert:data = trick_or_treat_data
```

The `trick_or_treat`

module has five member relations: `adult`

, `age`

, `child`

, `costume`

, and `flashlight`

. Each relation is a set containing four values that are separated by semicolons. The `adult`

, `child`

, `costume`

, and `flashlight`

relations all contain strings, and the `age`

relation contains integers.

The `insert`

relation inserts the data from the `trick_or_treat`

module into the database as a base relation named `data`

. With the data inserted we can start to model the problem.

Let's create some entity and value types to represent the various concepts in the model:

```
// model
entity type Adult = String
entity type Child = String
entity type Costume = String
entity type Flashlight = String
value type Age = Int
value type Color = String
value type Name = String
```

You can use entity and value types to create instances of each type. For example, `^Child["Judy"]`

creates a `Child`

instance representing the child named Judy. An entity instance is just a hash --- a unique ID that can be used to identify a specific entity.

Next, let's create entity relations that store instances of each entity in our model:

```
// model
def Adult = ^Adult[name] from name in data:adult
def Child = ^Child[name] from name in data:child
def Costume = ^Costume[name] from name in data:costume
def Flashlight = ^Flashlight[color] from color in data:flashlight
```

We'll also create a relation to store the four ages of each child:

```
// model
def Ages = ^Age[age] from age in data:age
```

Age is a property of a child. Normally, properties are assigned to entities using property edges --- relations containing tuples that pair an entity hash with a value type instance. In this case, however, defining `Ages`

in a way that mimics an entity relation will help simplify our reasoning later on.

Speaking of property edges, let's go ahead and create some to assign properties to each of our entities:

```
// model
def has_name = (^Adult[name], ^Name[name]) from name in data:adult
def has_name = (^Child[name], ^Name[name]) from name in data:child
def has_name = (^Costume[name], ^Name[name]) from name in data:costume
def has_color = (^Flashlight[color], ^Color[color]) from color in data:flashlight
```

Finally, let's define operations on `Age`

instances so that we can compare two `Age`

instances and do some arithmetic with them:

```
// model
// 1
def age_int = transpose[^Age]
// 2
def minimum[x in Age, y in Age] = ^Age[minimum[age_int[x], age_int[y]]]
def maximum[x in Age, y in Age] = ^Age[maximum[age_int[x], age_int[y]]]
// 3
def (<)[x in Age, y in Age] = age_int[x] < age_int[y]
def (>)[x in Age, y in Age] = age_int[x] > age_int[y]
def (-)[x in Age, y in Int] = ^Age[age_int[x] - y]
def (+)[x in Age, y in Int] = ^Age[age_int[x] + y]
```

Here's a breakdown of what each numbered group of code does:

The `^Age`

relation maps integers to instances of the`Age`

value type. So,`^Age[9]`

returns the`Age`

instance`(:Age, 9)`

. The`age_int`

relation inverts this map so that`age_int[^Age[9]]`

returns the integer`9`

.The built-in `minimum`

and`maximum`

relations can return the minimum and maximum of two integers, but don't know how to work with`Age`

instances. These lines define the right behavior, so that the minimum of two`Age`

instances is the one with the smaller corresponding integer value, and the maximum of two`Age`

instances in the one with the larger integer value.These lines define the `<`

and`>`

operators so that they can be used to compare two`Age`

instances. The`+`

and`-`

operators are defined between`Age`

instances and integers so that, for example,`^Age[7] + 1`

returns`^Age[8]`

.

Our setup is done. It's time to take a look at the clues.

## The Clues

There are ten clues. Each clue expresses one or more fact about the childrens' relationships with adults, costumes, ages, and flashlights. We'll create two relations to store two kinds of facts:

The `has`

relation holds facts of the form "X has Y."The `not_has`

relation holds facts of the form "X does not have Y."

For example, if the nine-year-old is wearing the ghost costume, then the `has`

relation contains the tuple `(^Age[9], ^Costume["Ghost"])`

. If the child accompanied by their sister does not carry the blue flashlight, then `(^Adult["Sister"], ^Flashlight["Blue"])`

is contained in `has_not`

.

## Clue One

Of the four children, there was the eight-year old, the child who dressed as a werewolf, the child who was accompanied by their sister, and the one who carried the red flashlight.

This clue tells us that the eight-year-old does not wear the werewolf costume, was not accompanied by their sister, and did not carry the red flashlight.

Similarly, the child wearing the werewolf costume is not eight years old, was not accompanied by their sister, and did not carry the red flashlight. And so on and so forth.

We can express this concisely in Rel:

```
// model
def clue1 = ^Age[8]; ^Costume["Werewolf"]; ^Adult["Sister"]; ^Flashlight["Red"]
def not_has(x in clue1, y in clue1) = x != y
```

This adds all pairs `(x, y)`

of distinct elements of the `clue1`

set to the `not_has`

relation.

## Clue Two

Between the nine-year-old and Frank, who is older than Toby, one was dressed as a goblin and the other carried the green flashlight. First of all, clue two tells us that Frank is not nine years old.

```
// model
def not_has = (^Child["Frank"], ^Age[9])
```

You might look at the above line of code and think that that we've just overwritten the `not_has`

relation. That is not the case. Relations in Rel are defined additively, so that the preceding definition adds the tuple `(^Child["Frank"], ^Age[9])`

to the existing `not_has`

relation.

Clue two also tells us that Frank is older than Toby. In other words, Toby can't have any age that is greater than or equal to Frank's age.

```
//install
def not_has(child, age in Ages) {
has(^Child["Frank"], age_frank)
and age >= age_frank
and child = ^Child["Toby"]
from age_frank in Ages
}
```

Lastly, we can write "between the nine-year-old and Frank, one was dressed as a goblin and the other carried the green flashlight" as an `if`

-`then`

-`else`

clause:

```
// model
def has {
if has(^Age[9], ^Costume["Goblin"])
then (^Child["Frank"], ^Flashlight["Green"])
else if has(^Age[9], ^Flashlight["Green"])
then (^Child["Frank"], ^Costume["Goblin"])
else {} // No tuple is added if neither if condition is true
end
end
}
```

## Clue Three

Neither Frank nor Judy were accompanied by their sister while trick or treating. Judy did not carry an orange flashlight. Clue three tells us three facts that go in the `not_has`

relation:

```
// model
def not_has {
(^Child["Frank"], ^Adult["Sister"]);
(^Child["Judy"], ^Adult["Sister"]);
(^Child["Judy"], ^Flashlight["Orange"])
}
```

## Clue Four

Toby's mother was upset that he cut up one of her favorite sheets to create his ghost costume.

Okay, so Toby wore the ghost costume:

```
// model
def has = (^Child["Toby"], ^Costume["Ghost"])
```

## Clue Five

The child who dressed as a werewolf was accompanied by a male and did not carry a green flashlight. The child dressed as a werewolf must be accompanied by either their brother or their uncle.

So, if we know that a child wearing some costume other than the werewolf costume is accompanied by their brother, we know the child dressed as a werewolf must be accompanied by their uncle, and `vice versa`

:

```
// model
def has {
if has(costume, ^Adult["Brother"]), costume != ^Costume["Werewolf"]
then (^Costume["Werewolf"], ^Adult["Uncle"])
else if has(costume, ^Adult["Uncle"]), costume != ^Costume["Werewolf"]
then (^Costume["Werewolf"], ^Adult["Brother"])
else {}
end
end
from costume in Costume
}
```

We also know that the child wearing the werewolf costume is not accompanied by their sister or their aunt, and doesn't carry the green flashlight:

```
// model
def not_has {
(^Costume["Werewolf"], ^Adult["Aunt"]);
(^Costume["Werewolf"], ^Adult["Sister"]);
(^Costume["Werewolf"], ^Flashlight["Green"])
}
```

## Clue Six

The nine-year-old was quite happy with her goblin costume, which she spent an entire week designing.

First, we know that the nine-year-old wore the gobline costume:

```
// model
def has = (^Age[9], ^Costume["Goblin"])
```

But we also know, since the nine-year-old is referred to as "her," that neither Frank nor Toby are nine years old:

```
// model
def not_has = (^Child["Frank"], ^Age[9]); (^Child["Toby"], ^Age[9])
```

## Clue Seven

Either Frank or Toby carried a green flashlight. We can encode clue seven as an `if`

-`then`

-`else`

clause. If Frank doesn't carry the green flashlight, then we know that Toby does, and vice versa:

```
// model
def has {
if not_has(^Child["Frank"], ^Flashlight["Green"])
then (^Child["Toby"], ^Flashlight["Green"])
else if not_has(^Child["Toby"], ^Flashlight["Green"])
then (^Child["Frank"], ^Flashlight["Green"])
else {}
end
end
}
```

## Clue Eight

The child who was accompanied by their brother was exactly two years older than the child who went with their sister.

If we know the age of the child accompanied by their sister, then we know the age of the child acompanied by their brother, and vice versa:

```
// model
def has {
if has(age, ^Adult["Sister"])
then (age + 2, ^Adult["Brother"])
else {}
end
from age in Ages
}
def has {
if has(age, ^Adult["Brother"])
then (age - 2, ^Adult["Sister"])
else {}
end
from age in Ages
}
```

We also know that the child who went with their brother must be at least two years older than the youngest child. In other words, their age can't be less than the minimum age plus two.

Similarly, the child who went with their sister can't be older than the maximum age minus two:

```
// model
def not_has = (age, ^Adult["Brother"]), age < min[Ages] + 2 from age in Ages
def not_has = (age, ^Adult["Sister"]), age > max[Ages] - 2 from age in Ages
```

## Clue Nine

Jessica caught her uncle sneaking candy from her bag while they walked!

All right, then. Jessica was accompanied by her uncle:

```
// model
def has = (^Child["Jessica"], ^Adult["Uncle"])
```

## Clue Ten

The child dressed as a ghost carried a blue flashlight.

Our last clue is another easy one. Let's add `(^Costume["Ghost"], ^Flashlight["Blue"])`

to the `has`

relation:

```
// model
def has = (^Costume["Ghost"], ^Flashlight["Blue"])
```

## Visualizing What We Know So Far

Now that we've encoded all of the clues, let's take a moment to see what we know so far.

We can do this by wrapping our `has`

and `not_has`

relations into two knowledge graphs.

The nodes of each graph are the `Child`

, `Ages`

, `Costume`

, `Adult`

, and `Flashlight`

entity relations, and the edges of each graph are the `has`

and `not_has`

relations, respectively:

```
// model
def show(e, string) {
(Child(e) or Adult(e) or Costume(e)) and has_name(e, ^Name[string])
or Flashlight(e) and has_color(e, ^Color[string])
or Age(e) and string = "%(age_int[e])"
}
def Things = Adult; Ages; Child; Costume; Flashlight
module HasKG
def node = show[x] from x in Things
def edge = (show[x], show[y]), has(x, y) from x, y
end
module NotHasKG
def node = show[x] from x in Things
def edge = (show[x], show[y]), not_has(x, y) from x, y
end
```

The `show`

relation maps entity hashes and value type instances to string representations. Children, adults, and costumes are mapped to their name. Flashlights are mapped to their color. Ages are mapped to a string containing their integer value. The `Things`

relation is the union of the `Adult`

, `Ages`

, `Child`

, `Costume`

, and `Flashlight`

relations, expressed in Rel using the semicolon.

The nodes in each knowledge graph are the string representations of each thing in `Things`

. In the `HasKG`

, each edge is pair of strings representing pairs from the `has`

relation. The `HasNotKG`

pairs representations of pairs from the `not_has`

relation.

We can visualize these knowledge graphs using the graphviz library, which is included with Rel:

```
// read query
def output = graphviz[HasKG]
```

Here's what the `HasKG`

graph looks like:

We don't know much about who has what. But we can tell, for example, that since Toby has the ghost costume and the ghost cosutme has the blue flashlight, then Toby has the blue flashlight.

In general, the `has`

relation should be transitive. That is, if `(x, y)`

is in `has`

and `(y, z)`

is in `has`

, then `(x, z)`

should also be in `has`

. Right now, the `has`

relation, as we've defined it, is not transitive.

We'll fix that in a moment, but first let's take a look at the `NotHasKG`

graph:

```
// read query
def output = graphviz[NotHasKG]
```

Here's what it looks like:

We know a lot more about what things don't have. Some of the edges are symmetric --- that is, for some values of `x`

and `y`

, both `(x, y)`

and `(y, x)`

are in `not_has`

. In fact, the entire `not_has`

relation should be symmetric since, if `x`

does not have `y`

, the `y`

also does not have `x`

.

The `has`

relation should be symmetric as well. Let's build on what we've modeled so far and solve the puzzle.

## Inferring the Solution to the Puzzle

First, let's make sure `has`

is symmetric and transitive:

```
// model
def has = transpose[has] // make sure has is symmetric
def has = has.has // make sure has is transitive
```

The `transpose`

relation swaps the order of the pairs in `has`

. So if `(x, y)`

is in `has`

, then `(y, x)`

is in `transpose[has]`

.

The second line uses the dot join operator to calculate the transitive closure of `has`

.

```
// read query
def output = graphviz[HasKG]
```

Here's what the `HasKG`

looks like after installing the preceding Rel code:

The `not_has`

relation is also symmetric, but it isn't transitive since if `x`

does not have `y`

and `y`

does not have `z`

, we can't conclude that `x`

does not have `z`

.

However, there is a transitive dependence on the `has`

relation. In other words, if `x`

has `y`

and `y`

does not have `z`

, then `x`

does not have `z`

. Similarly, if `x`

does not have `y`

, and `y`

has `z`

, then `x`

does not have `z`

.

Let's encode that in Rel:

```
// model
def not_has = transpose[not_has]
def not_has(x, y) = has.not_has(x, y), x != y
def not_has(x, y) = not_has.has(x, y), x != y
```

We have to make sure that `x != y`

. If `(x, x)`

were in `not_has`

, it would mean that `x`

does not have itself. It would be like saying that the child dressed as a ghost was not dressed as a ghost.

```
// read query
def output = graphviz[NotHasKG]
```

Here's what the `NotHasKG`

looks like after updating `not_has`

:

We're starting to get a bunch of new facts!

Next, we can infer more edges that should be in `not_has`

from what we know is in the `has`

relation. If `x`

has `y`

, then `x`

does not have `z`

for every `z != y`

of the same type as `y`

.

In other words, if Toby wears the ghost costume, the we know Toby doesn't wear the goblin, vampire, and werewolf costumes.

Here's how to model that in Rel:

```
// model
@inline
def infer_not_has[Type](x, z) {
has(x, y)
and Type(z)
and Type(y)
and z != y
from y
}
def not_has = infer_not_has[Adult]
def not_has = infer_not_has[Ages]
def not_has = infer_not_has[Child]
def not_has = infer_not_has[Costume]
def not_has = infer_not_has[Flashlight]
```

The `infer_not_has`

relation is a higher-order relation. It takes another relation as input, represented by the `Type`

parameter. Higher-order relations are marked with the `@inline`

annotation.

We can also infer edges that should be in the `has`

relation based off what we know is in the `not_has`

relation. If `x`

does not have three things of the same type, then it must have whatever the fourth thing of that type is.

Here's what that looks like in Rel:

```
// model
// Helper relation that selects not_has pairs based on the
// type of the second element
@inline
def not_has_type[Type](x, y) = not_has(x, y) and Type(y)
@inline
def infer_has[Type](x, y) {
count[not_has_type[Type, x]] = 3
and y = diff[Type, not_has_type[Type, x]]
and x != y
}
def has = infer_has[Adult]
def has = infer_has[Ages]
def has = infer_has[Child]
def has = infer_has[Costume]
def has = infer_has[Flashlight]
```

First, we create a `not_has_type`

relation that selects pairs from `not_has`

that have the same type in the second element of each pair. The `infer_has`

relation counts the number of things of some `Type`

that are related to `x`

, and returns the tuple `(x, y)`

where `y`

is the remaining `Type`

instance that `x`

does not have.

These two relations, `infer_not_has`

and `infer_has`

are enough for Rel to compute the entire solution.

You can see that by visualizing the `HasKG`

knowledge graph again:

```
// read query
def output = graphviz[HasKG]
```

It now looks like this:

The `HasKG`

graph has four cliques --- i.e., subgraphs containing every possible edge. Each clique represents the complete solution for each child.

We can also display this solution as a table:

```
// read query
@inline
def show_solution(Type, name, solution) {
has(child, e)
and Child(child)
and Type(e)
and name = show[child]
and solution = show[e]
from child, e
}
def solution:costume = show_solution[Costume]
def solution:flashlight = show_solution[Flashlight]
def solution:age = show_solution[Age]
def solution:accompanied_by = show_solution[Adult]
def output = table[solution]
```

Here's what that looks like:

This little logic puzzle shows off a number of interesting features of Rel and RelationalAI's Relational Knowledge Graph System.

You saw how to:

Model entites and entity properties using entity and value types. Define custom operators that work on value types. Model facts as tuples in relations. Create and visualize knowledge graphs. Infer new facts by computing symmetric and transitive closures and encoding logic.

That's a pretty tasty treat, if you ask me!