\n","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"What's better than a bag full of candy for Halloween?"}]},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"So grab your flashlight, put on your favorite costume, and let's go trick-or-treating with Rel!"}]},{"type":"h2","children":[{"type":"text","text":"The Setup"}],"id":"the-setup"},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"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:"}]},{"type":"code_block","lang":"rel","value":"// write query\n\nmodule trick_or_treat_data\n def adult = \"Brother\"; \"Sister\"; \"Aunt\"; \"Uncle\"\n def age = 7; 8; 9; 10\n def child = \"Jessica\"; \"Judy\"; \"Frank\"; \"Toby\"\n def costume = \"Ghost\"; \"Goblin\"; \"Vampire\"; \"Werewolf\"\n def flashlight = \"Red\"; \"Blue\"; \"Green\"; \"Orange\"\nend\n\ndef insert:data = trick_or_treat_data","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"trick_or_treat","code":true},{"type":"text","text":" module has five member relations: "},{"type":"text","text":"adult","code":true},{"type":"text","text":", "},{"type":"text","text":"age","code":true},{"type":"text","text":", "},{"type":"text","text":"child","code":true},{"type":"text","text":", "},{"type":"text","text":"costume","code":true},{"type":"text","text":", and "},{"type":"text","text":"flashlight","code":true},{"type":"text","text":". Each relation is a set containing four values that are separated by semicolons. The "},{"type":"text","text":"adult","code":true},{"type":"text","text":", "},{"type":"text","text":"child","code":true},{"type":"text","text":", "},{"type":"text","text":"costume","code":true},{"type":"text","text":", and "},{"type":"text","text":"flashlight","code":true},{"type":"text","text":" relations all contain strings, and the "},{"type":"text","text":"age","code":true},{"type":"text","text":" relation contains integers."}]},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"insert","code":true},{"type":"text","text":" relation inserts the data from the "},{"type":"text","text":"trick_or_treat","code":true},{"type":"text","text":" module into the database as a base relation named "},{"type":"text","text":"data","code":true},{"type":"text","text":". With the data inserted we can start to model the problem."}]},{"type":"p","children":[{"type":"text","text":"Let's create some "},{"type":"a","url":"https://docs.relational.ai/rel/concepts/entities","title":null,"children":[{"type":"text","text":"entity"}]},{"type":"text","text":" and "},{"type":"a","url":"https://docs.relational.ai/rel/concepts/value-types","title":null,"children":[{"type":"text","text":"value types"}]},{"type":"text","text":" to represent the various concepts in the model:"}]},{"type":"code_block","lang":"rel","value":"// model\n\nentity type Adult = String\nentity type Child = String\nentity type Costume = String\nentity type Flashlight = String\n\nvalue type Age = Int\nvalue type Color = String\nvalue type Name = String","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"You can use entity and value types to create instances of each type. For example, "},{"type":"text","text":"^Child[\"Judy\"]","code":true},{"type":"text","text":" creates a "},{"type":"text","text":"Child","code":true},{"type":"text","text":" 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."}]},{"type":"p","children":[{"type":"text","text":"Next, let's create "},{"type":"text","text":"entity relations","italic":true},{"type":"text","text":" that store instances of each entity in our model:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef Adult = ^Adult[name] from name in data:adult\ndef Child = ^Child[name] from name in data:child\ndef Costume = ^Costume[name] from name in data:costume\ndef Flashlight = ^Flashlight[color] from color in data:flashlight","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"We'll also create a relation to store the four ages of each child:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef Ages = ^Age[age] from age in data:age","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Age is a property of a child. Normally, properties are assigned to entities using "},{"type":"text","text":"property edges","italic":true},{"type":"text","text":" --- relations containing tuples that pair an entity hash with a value type instance. In this case, however, defining "},{"type":"text","text":"Ages","code":true},{"type":"text","text":" in a way that mimics an entity relation will help simplify our reasoning later on."}]},{"type":"p","children":[{"type":"text","text":"Speaking of property edges, let's go ahead and create some to assign properties to each of our entities:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has_name = (^Adult[name], ^Name[name]) from name in data:adult\ndef has_name = (^Child[name], ^Name[name]) from name in data:child\ndef has_name = (^Costume[name], ^Name[name]) from name in data:costume\ndef has_color = (^Flashlight[color], ^Color[color]) from color in data:flashlight","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Finally, let's define operations on "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instances so that we can compare two "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instances and do some arithmetic with them:"}]},{"type":"code_block","lang":"rel","value":"// model\n\n// 1\ndef age_int = transpose[^Age]\n\n// 2\ndef minimum[x in Age, y in Age] = ^Age[minimum[age_int[x], age_int[y]]]\ndef maximum[x in Age, y in Age] = ^Age[maximum[age_int[x], age_int[y]]]\n\n// 3\ndef (<)[x in Age, y in Age] = age_int[x] < age_int[y]\ndef (>)[x in Age, y in Age] = age_int[x] > age_int[y]\ndef (-)[x in Age, y in Int] = ^Age[age_int[x] - y]\ndef (+)[x in Age, y in Int] = ^Age[age_int[x] + y]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Here's a breakdown of what each numbered group of code does:"}]},{"type":"ol","children":[{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"The "},{"type":"text","text":"^Age","code":true},{"type":"text","text":" relation maps integers to instances of the "},{"type":"text","text":"Age","code":true},{"type":"text","text":" value type. So, "},{"type":"text","text":"^Age[9]","code":true},{"type":"text","text":" returns the "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instance "},{"type":"text","text":"(:Age, 9)","code":true},{"type":"text","text":". The "},{"type":"text","text":"age_int","code":true},{"type":"text","text":" relation inverts this map so that "},{"type":"text","text":"age_int[^Age[9]]","code":true},{"type":"text","text":" returns the integer "},{"type":"text","text":"9","code":true},{"type":"text","text":"."}]}]},{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"The built-in "},{"type":"text","text":"minimum","code":true},{"type":"text","text":" and "},{"type":"text","text":"maximum","code":true},{"type":"text","text":" relations can return the minimum and maximum of two integers, but don't know how to work with "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instances. These lines define the right behavior, so that the minimum of two "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instances is the one with the smaller corresponding integer value, and the maximum of two "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instances in the one with the larger integer value."}]}]},{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"These lines define the "},{"type":"text","text":"<","code":true},{"type":"text","text":" and "},{"type":"text","text":">","code":true},{"type":"text","text":" operators so that they can be used to compare two "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instances. The "},{"type":"text","text":"+","code":true},{"type":"text","text":" and "},{"type":"text","text":"-","code":true},{"type":"text","text":" operators are defined between "},{"type":"text","text":"Age","code":true},{"type":"text","text":" instances and integers so that, for example, "},{"type":"text","text":"^Age[7] + 1","code":true},{"type":"text","text":" returns "},{"type":"text","text":"^Age[8]","code":true},{"type":"text","text":"."}]}]}]},{"type":"p","children":[{"type":"text","text":"Our setup is done. It's time to take a look at the clues."}]},{"type":"h2","children":[{"type":"text","text":"The Clues"}],"id":"the-clues"},{"type":"p","children":[{"type":"text","text":"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:"}]},{"type":"ol","children":[{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"The "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation holds facts of the form \"X has Y.\""}]}]},{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"The "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation holds facts of the form \"X does not have Y.\""}]}]}]},{"type":"p","children":[{"type":"text","text":"For example, if the nine-year-old is wearing the ghost costume, then the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation contains the tuple "},{"type":"text","text":"(^Age[9], ^Costume[\"Ghost\"])","code":true},{"type":"text","text":". If the child accompanied by their sister does not carry the blue flashlight, then "},{"type":"text","text":"(^Adult[\"Sister\"], ^Flashlight[\"Blue\"])","code":true},{"type":"text","text":" is contained in "},{"type":"text","text":"has_not","code":true},{"type":"text","text":"."}]},{"type":"h2","children":[{"type":"text","text":"Clue One"}],"id":"clue-one"},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"We can express this concisely in Rel:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef clue1 = ^Age[8]; ^Costume[\"Werewolf\"]; ^Adult[\"Sister\"]; ^Flashlight[\"Red\"]\ndef not_has(x in clue1, y in clue1) = x != y","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"This adds all pairs "},{"type":"text","text":"(x, y)","code":true},{"type":"text","text":" of distinct elements of the "},{"type":"text","text":"clue1","code":true},{"type":"text","text":" set to the "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation."}]},{"type":"h2","children":[{"type":"text","text":"Clue Two"}],"id":"clue-two"},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef not_has = (^Child[\"Frank\"], ^Age[9])","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"You might look at the above line of code and think that that we've just overwritten the "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation. That is not the case. Relations in Rel are defined additively, so that the preceding definition "},{"type":"text","text":"adds","italic":true},{"type":"text","text":" the tuple "},{"type":"text","text":"(^Child[\"Frank\"], ^Age[9])","code":true},{"type":"text","text":" to the existing "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation."}]},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"code_block","lang":"rel","value":"//install\n\ndef not_has(child, age in Ages) {\n has(^Child[\"Frank\"], age_frank)\n and age >= age_frank\n and child = ^Child[\"Toby\"]\n from age_frank in Ages\n}","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"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 "},{"type":"text","text":"if","code":true},{"type":"text","text":"-"},{"type":"text","text":"then","code":true},{"type":"text","text":"-"},{"type":"text","text":"else","code":true},{"type":"text","text":" clause:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has {\n if has(^Age[9], ^Costume[\"Goblin\"])\n then (^Child[\"Frank\"], ^Flashlight[\"Green\"])\n else if has(^Age[9], ^Flashlight[\"Green\"])\n then (^Child[\"Frank\"], ^Costume[\"Goblin\"])\n else {} // No tuple is added if neither if condition is true\n end\n end\n}","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Three"}],"id":"clue-three"},{"type":"p","children":[{"type":"text","text":"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 "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef not_has {\n (^Child[\"Frank\"], ^Adult[\"Sister\"]);\n (^Child[\"Judy\"], ^Adult[\"Sister\"]);\n (^Child[\"Judy\"], ^Flashlight[\"Orange\"])\n}","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Four"}],"id":"clue-four"},{"type":"p","children":[{"type":"text","text":"Toby's mother was upset that he cut up one of her favorite sheets to create his ghost costume."}]},{"type":"p","children":[{"type":"text","text":"Okay, so Toby wore the ghost costume:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has = (^Child[\"Toby\"], ^Costume[\"Ghost\"])","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Five"}],"id":"clue-five"},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"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 "},{"type":"text","text":"vice versa","code":true},{"type":"text","text":":"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has {\n if has(costume, ^Adult[\"Brother\"]), costume != ^Costume[\"Werewolf\"]\n then (^Costume[\"Werewolf\"], ^Adult[\"Uncle\"])\n else if has(costume, ^Adult[\"Uncle\"]), costume != ^Costume[\"Werewolf\"]\n then (^Costume[\"Werewolf\"], ^Adult[\"Brother\"])\n else {}\n end\n end\n from costume in Costume\n}","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"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:"}]},{"type":"code_block","lang":"rel","value":"// model\ndef not_has {\n (^Costume[\"Werewolf\"], ^Adult[\"Aunt\"]);\n (^Costume[\"Werewolf\"], ^Adult[\"Sister\"]);\n (^Costume[\"Werewolf\"], ^Flashlight[\"Green\"])\n}","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Six"}],"id":"clue-six"},{"type":"p","children":[{"type":"text","text":"The nine-year-old was quite happy with her goblin costume, which she spent an entire week designing."}]},{"type":"p","children":[{"type":"text","text":"First, we know that the nine-year-old wore the gobline costume:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has = (^Age[9], ^Costume[\"Goblin\"])","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"But we also know, since the nine-year-old is referred to as \"her,\" that neither Frank nor Toby are nine years old:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef not_has = (^Child[\"Frank\"], ^Age[9]); (^Child[\"Toby\"], ^Age[9])","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Seven"}],"id":"clue-seven"},{"type":"p","children":[{"type":"text","text":"Either Frank or Toby carried a green flashlight. We can encode clue seven as an "},{"type":"text","text":"if","code":true},{"type":"text","text":"-"},{"type":"text","text":"then","code":true},{"type":"text","text":"-"},{"type":"text","text":"else","code":true},{"type":"text","text":" clause. If Frank doesn't carry the green flashlight, then we know that Toby does, and "},{"type":"text","text":"vice versa","italic":true},{"type":"text","text":":"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has {\n if not_has(^Child[\"Frank\"], ^Flashlight[\"Green\"])\n then (^Child[\"Toby\"], ^Flashlight[\"Green\"])\n else if not_has(^Child[\"Toby\"], ^Flashlight[\"Green\"])\n then (^Child[\"Frank\"], ^Flashlight[\"Green\"])\n else {}\n end\n end\n}","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Eight"}],"id":"clue-eight"},{"type":"p","children":[{"type":"text","text":"The child who was accompanied by their brother was exactly two years older than the child who went with their sister."}]},{"type":"p","children":[{"type":"text","text":"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 "},{"type":"text","text":"vice versa","italic":true},{"type":"text","text":":"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has {\n if has(age, ^Adult[\"Sister\"])\n then (age + 2, ^Adult[\"Brother\"])\n else {}\n end\n from age in Ages\n}\n\ndef has {\n if has(age, ^Adult[\"Brother\"])\n then (age - 2, ^Adult[\"Sister\"])\n else {}\n end\n from age in Ages\n}","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"Similarly, the child who went with their sister can't be older than the maximum age minus two:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef not_has = (age, ^Adult[\"Brother\"]), age < min[Ages] + 2 from age in Ages\ndef not_has = (age, ^Adult[\"Sister\"]), age > max[Ages] - 2 from age in Ages","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Nine"}],"id":"clue-nine"},{"type":"p","children":[{"type":"text","text":"Jessica caught her uncle sneaking candy from her bag while they walked!"}]},{"type":"p","children":[{"type":"text","text":"All right, then. Jessica was accompanied by her uncle:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has = (^Child[\"Jessica\"], ^Adult[\"Uncle\"])","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Clue Ten"}],"id":"clue-ten"},{"type":"p","children":[{"type":"text","text":"The child dressed as a ghost carried a blue flashlight."}]},{"type":"p","children":[{"type":"text","text":"Our last clue is another easy one. Let's add "},{"type":"text","text":"(^Costume[\"Ghost\"], ^Flashlight[\"Blue\"])","code":true},{"type":"text","text":" to the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has = (^Costume[\"Ghost\"], ^Flashlight[\"Blue\"])","children":[{"type":"text","text":""}]},{"type":"h2","children":[{"type":"text","text":"Visualizing What We Know So Far"}],"id":"visualizing-what-we-know-so-far"},{"type":"p","children":[{"type":"text","text":"Now that we've encoded all of the clues, let's take a moment to see what we know so far."}]},{"type":"p","children":[{"type":"text","text":"We can do this by wrapping our "},{"type":"text","text":"has","code":true},{"type":"text","text":" and "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relations into two knowledge graphs."}]},{"type":"p","children":[{"type":"text","text":"The nodes of each graph are the "},{"type":"text","text":"Child","code":true},{"type":"text","text":", "},{"type":"text","text":"Ages","code":true},{"type":"text","text":", "},{"type":"text","text":"Costume","code":true},{"type":"text","text":", "},{"type":"text","text":"Adult","code":true},{"type":"text","text":", and "},{"type":"text","text":"Flashlight","code":true},{"type":"text","text":" entity relations, and the edges of each graph are the "},{"type":"text","text":"has","code":true},{"type":"text","text":" and "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relations, respectively:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef show(e, string) {\n (Child(e) or Adult(e) or Costume(e)) and has_name(e, ^Name[string])\n or Flashlight(e) and has_color(e, ^Color[string])\n or Age(e) and string = \"%(age_int[e])\"\n}\n\ndef Things = Adult; Ages; Child; Costume; Flashlight\n\nmodule HasKG\n def node = show[x] from x in Things\n def edge = (show[x], show[y]), has(x, y) from x, y\nend\n\nmodule NotHasKG\n def node = show[x] from x in Things\n def edge = (show[x], show[y]), not_has(x, y) from x, y\nend","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"show","code":true},{"type":"text","text":" 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 "},{"type":"text","text":"Things","code":true},{"type":"text","text":" relation is the union of the "},{"type":"text","text":"Adult","code":true},{"type":"text","text":", "},{"type":"text","text":"Ages","code":true},{"type":"text","text":", "},{"type":"text","text":"Child","code":true},{"type":"text","text":", "},{"type":"text","text":"Costume","code":true},{"type":"text","text":", and "},{"type":"text","text":"Flashlight","code":true},{"type":"text","text":" relations, expressed in Rel using the semicolon."}]},{"type":"p","children":[{"type":"text","text":"The nodes in each knowledge graph are the string representations of each thing in "},{"type":"text","text":"Things","code":true},{"type":"text","text":". In the "},{"type":"text","text":"HasKG","code":true},{"type":"text","text":", each edge is pair of strings representing pairs from the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation. The "},{"type":"text","text":"HasNotKG","code":true},{"type":"text","text":" pairs representations of pairs from the "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation."}]},{"type":"p","children":[{"type":"text","text":"We can visualize these knowledge graphs "},{"type":"a","url":"https://docs.relational.ai/rel/how-to/data-visualization-graphviz","title":null,"children":[{"type":"text","text":"using the graphviz library"}]},{"type":"text","text":", which is included with Rel:"}]},{"type":"code_block","lang":"rel","value":"// read query\n\ndef output = graphviz[HasKG]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Here's what the "},{"type":"text","text":"HasKG","code":true},{"type":"text","text":" graph looks like:"}]},{"type":"mdxJsxFlowElement","name":"ImgFig","children":[{"type":"text","text":""}],"props":{"src":"/blog/trick-or-treating-with-rel/has-kg-graph.png","width":"80%","alt":"has-kg-graph"}},{"type":"p","children":[{"type":"text","text":"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."}]},{"type":"p","children":[{"type":"text","text":"In general, the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation should be transitive. That is, if "},{"type":"text","text":"(x, y)","code":true},{"type":"text","text":" is in "},{"type":"text","text":"has","code":true},{"type":"text","text":" and "},{"type":"text","text":"(y, z)","code":true},{"type":"text","text":" is in "},{"type":"text","text":"has","code":true},{"type":"text","text":", then "},{"type":"text","text":"(x, z)","code":true},{"type":"text","text":" should also be in "},{"type":"text","text":"has","code":true},{"type":"text","text":". Right now, the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation, as we've defined it, is not transitive."}]},{"type":"p","children":[{"type":"text","text":"We'll fix that in a moment, but first let's take a look at the "},{"type":"text","text":"NotHasKG","code":true},{"type":"text","text":" graph:"}]},{"type":"code_block","lang":"rel","value":"// read query\n\ndef output = graphviz[NotHasKG]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Here's what it looks like:"}]},{"type":"mdxJsxFlowElement","name":"ImgFig","children":[{"type":"text","text":""}],"props":{"src":"/blog/trick-or-treating-with-rel/not-has-kg-graph.png","width":"80%","alt":"not-has-kg-graph"}},{"type":"p","children":[{"type":"text","text":"We know a lot more about what things don't have. Some of the edges are "},{"type":"text","text":"symmetric","italic":true},{"type":"text","text":" --- that is, for some values of "},{"type":"text","text":"x","code":true},{"type":"text","text":" and "},{"type":"text","text":"y","code":true},{"type":"text","text":", both "},{"type":"text","text":"(x, y)","code":true},{"type":"text","text":" and "},{"type":"text","text":"(y, x)","code":true},{"type":"text","text":" are in "},{"type":"text","text":"not_has","code":true},{"type":"text","text":". In fact, the entire "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation should be symmetric since, if "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"y","code":true},{"type":"text","text":", the "},{"type":"text","text":"y","code":true},{"type":"text","text":" also does not have "},{"type":"text","text":"x","code":true},{"type":"text","text":"."}]},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation should be symmetric as well. Let's build on what we've modeled so far and solve the puzzle."}]},{"type":"h2","children":[{"type":"text","text":"Inferring the Solution to the Puzzle"}],"id":"inferring-the-solution-to-the-puzzle"},{"type":"p","children":[{"type":"text","text":"First, let's make sure "},{"type":"text","text":"has","code":true},{"type":"text","text":" is symmetric and transitive:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef has = transpose[has] // make sure has is symmetric\ndef has = has.has // make sure has is transitive","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"transpose","code":true},{"type":"text","text":" relation swaps the order of the pairs in "},{"type":"text","text":"has","code":true},{"type":"text","text":". So if "},{"type":"text","text":"(x, y)","code":true},{"type":"text","text":" is in "},{"type":"text","text":"has","code":true},{"type":"text","text":", then "},{"type":"text","text":"(y, x)","code":true},{"type":"text","text":" is in "},{"type":"text","text":"transpose[has]","code":true},{"type":"text","text":"."}]},{"type":"p","children":[{"type":"text","text":"The second line uses the dot join operator to calculate the "},{"type":"text","text":"transitive closure","italic":true},{"type":"text","text":" of "},{"type":"text","text":"has","code":true},{"type":"text","text":"."}]},{"type":"code_block","lang":"rel","value":"// read query\n\ndef output = graphviz[HasKG]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Here's what the "},{"type":"text","text":"HasKG","code":true},{"type":"text","text":" looks like after installing the preceding Rel code:"}]},{"type":"mdxJsxFlowElement","name":"ImgFig","children":[{"type":"text","text":""}],"props":{"src":"/blog/trick-or-treating-with-rel/has-kg-after.png","width":"90%","alt":"has-kg-after"}},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation is also symmetric, but it isn't transitive since if "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"y","code":true},{"type":"text","text":" and "},{"type":"text","text":"y","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"z","code":true},{"type":"text","text":", we can't conclude that "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"z","code":true},{"type":"text","text":"."}]},{"type":"p","children":[{"type":"text","text":"However, there is a transitive dependence on the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation. In other words, if "},{"type":"text","text":"x","code":true},{"type":"text","text":" has "},{"type":"text","text":"y","code":true},{"type":"text","text":" and "},{"type":"text","text":"y","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"z","code":true},{"type":"text","text":", then "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"z","code":true},{"type":"text","text":". Similarly, if "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"y","code":true},{"type":"text","text":", and "},{"type":"text","text":"y","code":true},{"type":"text","text":" has "},{"type":"text","text":"z","code":true},{"type":"text","text":", then "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"z","code":true},{"type":"text","text":"."}]},{"type":"p","children":[{"type":"text","text":"Let's encode that in Rel:"}]},{"type":"code_block","lang":"rel","value":"// model\n\ndef not_has = transpose[not_has]\ndef not_has(x, y) = has.not_has(x, y), x != y\ndef not_has(x, y) = not_has.has(x, y), x != y","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"We have to make sure that "},{"type":"text","text":"x != y","code":true},{"type":"text","text":". If "},{"type":"text","text":"(x, x)","code":true},{"type":"text","text":" were in "},{"type":"text","text":"not_has","code":true},{"type":"text","text":", it would mean that "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have itself. It would be like saying that the child dressed as a ghost was not dressed as a ghost."}]},{"type":"code_block","lang":"rel","value":"// read query\n\ndef output = graphviz[NotHasKG]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Here's what the "},{"type":"text","text":"NotHasKG","code":true},{"type":"text","text":" looks like after updating "},{"type":"text","text":"not_has","code":true},{"type":"text","text":":"}]},{"type":"mdxJsxFlowElement","name":"ImgFig","children":[{"type":"text","text":""}],"props":{"src":"/blog/trick-or-treating-with-rel/not-has-kg-updated.png","width":"80%","alt":"not-has-kg-updated"}},{"type":"p","children":[{"type":"text","text":"We're starting to get a bunch of new facts!"}]},{"type":"p","children":[{"type":"text","text":"Next, we can infer more edges that should be in "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" from what we know is in the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation. If "},{"type":"text","text":"x","code":true},{"type":"text","text":" has "},{"type":"text","text":"y","code":true},{"type":"text","text":", then "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have "},{"type":"text","text":"z","code":true},{"type":"text","text":" for every "},{"type":"text","text":"z != y","code":true},{"type":"text","text":" of the same type as "},{"type":"text","text":"y","code":true},{"type":"text","text":"."}]},{"type":"p","children":[{"type":"text","text":"In other words, if Toby wears the ghost costume, the we know Toby doesn't wear the goblin, vampire, and werewolf costumes."}]},{"type":"p","children":[{"type":"text","text":"Here's how to model that in Rel:"}]},{"type":"code_block","lang":"rel","value":"// model\n\n@inline\ndef infer_not_has[Type](x, z) {\n has(x, y)\n and Type(z)\n and Type(y)\n and z != y\n from y\n}\n\ndef not_has = infer_not_has[Adult]\ndef not_has = infer_not_has[Ages]\ndef not_has = infer_not_has[Child]\ndef not_has = infer_not_has[Costume]\ndef not_has = infer_not_has[Flashlight]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"infer_not_has","code":true},{"type":"text","text":" relation is a "},{"type":"a","url":"https://docs.relational.ai/rel/ref/higherorder","title":null,"children":[{"type":"text","text":"higher-order relation"}]},{"type":"text","text":". It takes another relation as input, represented by the "},{"type":"text","text":"Type","code":true},{"type":"text","text":" parameter. Higher-order relations are marked with the "},{"type":"a","url":"https://docs.relational.ai/rel/primer/advanced-syntax#inline-definitions","title":null,"children":[{"type":"text","text":"@inline","code":true}]},{"type":"text","text":" annotation."}]},{"type":"p","children":[{"type":"text","text":"We can also infer edges that should be in the "},{"type":"text","text":"has","code":true},{"type":"text","text":" relation based off what we know is in the "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" relation. If "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have three things of the same type, then it must have whatever the fourth thing of that type is."}]},{"type":"p","children":[{"type":"text","text":"Here's what that looks like in Rel:"}]},{"type":"code_block","lang":"rel","value":"// model\n\n// Helper relation that selects not_has pairs based on the\n// type of the second element\n@inline\ndef not_has_type[Type](x, y) = not_has(x, y) and Type(y)\n\n@inline\ndef infer_has[Type](x, y) {\n count[not_has_type[Type, x]] = 3\n and y = diff[Type, not_has_type[Type, x]]\n and x != y\n}\n\ndef has = infer_has[Adult]\ndef has = infer_has[Ages]\ndef has = infer_has[Child]\ndef has = infer_has[Costume]\ndef has = infer_has[Flashlight]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"First, we create a "},{"type":"text","text":"not_has_type","code":true},{"type":"text","text":" relation that selects pairs from "},{"type":"text","text":"not_has","code":true},{"type":"text","text":" that have the same type in the second element of each pair. The "},{"type":"text","text":"infer_has","code":true},{"type":"text","text":" relation counts the number of things of some "},{"type":"text","text":"Type","code":true},{"type":"text","text":" that are related to "},{"type":"text","text":"x","code":true},{"type":"text","text":", and returns the tuple "},{"type":"text","text":"(x, y)","code":true},{"type":"text","text":" where "},{"type":"text","text":"y","code":true},{"type":"text","text":" is the remaining "},{"type":"text","text":"Type","code":true},{"type":"text","text":" instance that "},{"type":"text","text":"x","code":true},{"type":"text","text":" does not have."}]},{"type":"p","children":[{"type":"text","text":"These two relations, "},{"type":"text","text":"infer_not_has","code":true},{"type":"text","text":" and "},{"type":"text","text":"infer_has","code":true},{"type":"text","text":" are enough for Rel to compute the entire solution."}]},{"type":"p","children":[{"type":"text","text":"You can see that by visualizing the "},{"type":"text","text":"HasKG","code":true},{"type":"text","text":" knowledge graph again:"}]},{"type":"code_block","lang":"rel","value":"// read query\n\ndef output = graphviz[HasKG]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"It now looks like this:"}]},{"type":"mdxJsxFlowElement","name":"ImgFig","children":[{"type":"text","text":""}],"props":{"src":"/blog/trick-or-treating-with-rel/four-cliques.png","width":"80%","alt":"four-cliques"}},{"type":"p","children":[{"type":"text","text":"The "},{"type":"text","text":"HasKG","code":true},{"type":"text","text":" graph has four "},{"type":"text","text":"cliques","italic":true},{"type":"text","text":" --- i.e., subgraphs containing every possible edge. Each clique represents the complete solution for each child."}]},{"type":"p","children":[{"type":"text","text":"We can also display this solution as a table:"}]},{"type":"code_block","lang":"rel","value":"// read query\n\n@inline\ndef show_solution(Type, name, solution) {\n has(child, e)\n and Child(child)\n and Type(e)\n and name = show[child]\n and solution = show[e]\n from child, e\n}\n\ndef solution:costume = show_solution[Costume]\ndef solution:flashlight = show_solution[Flashlight]\ndef solution:age = show_solution[Age]\ndef solution:accompanied_by = show_solution[Adult]\n\ndef output = table[solution]","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"Here's what that looks like:"}]},{"type":"mdxJsxFlowElement","name":"ImgFig","children":[{"type":"text","text":""}],"props":{"src":"/blog/trick-or-treating-with-rel/solution_table.png","width":"80%","alt":"solution_table"}},{"type":"p","children":[{"type":"text","text":"This little logic puzzle shows off a number of interesting features of Rel and RelationalAI's "},{"type":"a","url":"https://docs.relational.ai/rkgms/why-rkgs","title":null,"children":[{"type":"text","text":"Relational Knowledge Graph System"}]},{"type":"text","text":"."}]},{"type":"p","children":[{"type":"text","text":"You saw how to:"}]},{"type":"ul","children":[{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"Model entites and entity properties using entity and value types."}]}]},{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"Define custom operators that work on value types."}]}]},{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"Model facts as tuples in relations."}]}]},{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"Create and visualize knowledge graphs."}]}]},{"type":"li","children":[{"type":"lic","children":[{"type":"text","text":"Infer new facts by computing symmetric and transitive closures and encoding logic."}]}]}]},{"type":"p","children":[{"type":"text","text":"That's a pretty tasty treat, if you ask me!"}]}],"_content_source":{"queryId":"src/content/resources/trick-or-treating-with-rel.mdx","path":["resource","body"]}},"_content_source":{"queryId":"src/content/resources/trick-or-treating-with-rel.mdx","path":["resource"]}}},"errors":null,"query":"\n query resource($relativePath: String!) {\n resource(relativePath: $relativePath) {\n ... on Document {\n _sys {\n filename\n basename\n breadcrumbs\n path\n relativePath\n extension\n }\n id\n }\n ...ResourceParts\n }\n}\n \n fragment ResourceParts on Resource {\n __typename\n title\n description\n date\n image\n categories\n authors {\n __typename\n name\n link\n }\n seo {\n __typename\n keywords\n description\n image\n image_alt\n canonical_url\n author\n published\n modified\n language\n robots\n site_name\n content_type\n }\n body\n}\n ","variables":{"relativePath":"trick-or-treating-with-rel.mdx"}},"src/content/meta/meta.md":{"data":{"meta":{"_sys":{"filename":"meta","basename":"meta.md","breadcrumbs":["meta"],"path":"src/content/meta/meta.md","relativePath":"meta.md","extension":".md"},"id":"src/content/meta/meta.md","__typename":"Meta","banner":{"__typename":"MetaBanner","enabled":true,"content":{"type":"root","children":[{"type":"p","children":[{"type":"text","text":"Check out "},{"type":"a","url":"/resources/highlights-of-relationalai-at-snowflake-data-cloud-summit-2024","title":"SF summit highlights","children":[{"type":"text","text":"highlights"}]},{"type":"text","text":" of RelationalAI at "},{"type":"text","text":"Snowflake's Data Cloud Summit 2024!","bold":true}]}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","banner","content"]}},"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","banner"]}},"header":{"__typename":"MetaHeader","links":[{"__typename":"MetaHeaderLinks","text":"Product","url":"/product","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",0]}},{"__typename":"MetaHeaderLinks","text":"Company","url":"/company","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",1]}},{"__typename":"MetaHeaderLinks","text":"Docs","url":"/docs","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",2]}},{"__typename":"MetaHeaderLinks","text":"Resources","url":"/resources/all/1","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",3]}},{"__typename":"MetaHeaderLinks","text":"Get Started","url":"/get-started","style":"cta","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",4]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header"]}},"footer":{"__typename":"MetaFooter","sections":[{"__typename":"MetaFooterSections","name":"Product","links":[{"__typename":"MetaFooterSectionsLinks","text":"Overview","url":"/product","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"Use Cases","url":"/product#for-problems-that-matter","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Capabilities","url":"/product#a-new-toolset","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",2]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0]}},{"__typename":"MetaFooterSections","name":"Resources","links":[{"__typename":"MetaFooterSectionsLinks","text":"Documentation","url":"/docs/getting_started","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"News","url":"/resources/news/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Research","url":"/resources/research/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",2]}},{"__typename":"MetaFooterSectionsLinks","text":"Releases","url":"/resources/releases/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",3]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1]}},{"__typename":"MetaFooterSections","name":"About Us","links":[{"__typename":"MetaFooterSectionsLinks","text":"Our Company","url":"/company","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"Contact Us","url":"/get-started","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Careers","url":"/careers","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",2]}},{"__typename":"MetaFooterSectionsLinks","text":"Legal","url":"/legal","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",3]}},{"__typename":"MetaFooterSectionsLinks","text":"GDPR","url":"/gdpr","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",4]}},{"__typename":"MetaFooterSectionsLinks","text":"Security & Trust","url":"https://trust.relational.ai/","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",5]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2]}}],"socials":[{"__typename":"MetaFooterSocials","text":"GitHub","url":"https://github.com/RelationalAI","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/github.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",0]}},{"__typename":"MetaFooterSocials","text":"LinkedIn","url":"https://www.linkedin.com/company/relationalai/about","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/linkedin.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",1]}},{"__typename":"MetaFooterSocials","text":"Twitter","url":"https://twitter.com/relationalai","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/twitter.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",2]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer"]}},"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta"]}}},"errors":null,"query":"\n query meta($relativePath: String!) {\n meta(relativePath: $relativePath) {\n ... on Document {\n _sys {\n filename\n basename\n breadcrumbs\n path\n relativePath\n extension\n }\n id\n }\n ...MetaParts\n }\n}\n \n fragment MetaParts on Meta {\n __typename\n banner {\n __typename\n enabled\n content\n }\n header {\n __typename\n links {\n __typename\n text\n url\n style\n }\n }\n footer {\n __typename\n sections {\n __typename\n name\n links {\n __typename\n text\n url\n }\n }\n socials {\n __typename\n text\n url\n icon\n }\n }\n}\n ","variables":{"relativePath":"./meta.md"}}};
globalThis.tina_info = tina;
})();
Trick-Or-Treating With Rel · RelationalAI
Check out highlights of RelationalAI at Snowflake's Data Cloud Summit 2024!
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:
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:
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:
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 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]