6.18 Example: A Database¶
This example shows how you can use FriCAS to organize a database of lineage data and then query the database for relationships.
The database is entered as assertions that are really pieces of a function definition.
children("albert") == ["albertJr","richard","diane"]
Each piece children(x)==y means the children of x are y.
children("richard") == ["douglas","daniel","susan"]
This family tree thus spans four generations.
children("douglas") == ["dougie","valerie"]
Say no one else has children.
children(x) == 
We need some functions for computing lineage. Start with childOf.
childOf(x,y) == member?(x,children(y))
To find the parentOf someone, you have to scan the database of people applying children.
parentOf(x) == for y in people repeat (if childOf(x,y) then return y) "unknown"
And a grandparent of x is just a parent of a parent of x.
grandParentOf(x) == parentOf parentOf x
The grandchildren of x are the people y such that x is a grandparent of y.
grandchildren(x) == [y for y in people | grandParentOf(y) = x]
Suppose you want to make a list of all great-grandparents. Well, a great-grandparent is a grandparent of a person who has children.
greatGrandParents == [x for x in people | reduce(_or, [not empty? children(y) for y in grandchildren(x)],false)]
Define descendants to include the parent as well.
descendants(x) == kids := children(x) null kids => [x] concat(x,reduce(concat,[descendants(y) for y in kids],))
Finally, we need a list of people. Since all people are descendants of albert, let’s say so.
people == descendants "albert"
We have used == to define the database and some functions to query the database. But no computation is done until we ask for some information. Then, once and for all, the functions are analyzed and compiled to machine code for run-time efficiency. Notice that no types are given anywhere in this example. They are not needed.
Who are the grandchildren of richard?
Compiling function children with type String -> List String Compiling function descendants with type String -> List String Compiling body of rule people to compute value of type List String Compiling function childOf with type (String,String) -> Boolean Compiling function parentOf with type String -> String Compiling function grandParentOf with type String -> String Compiling function grandchildren with type String -> List String
Type: List String
Who are the great-grandparents?
Compiling body of rule greatGrandParents to compute value of type List String
Type: List String