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"]

_{Type: Void}

Each piece children(x)==y means the children of x are y.

children("richard") == ["douglas","daniel","susan"]

_{Type: Void}

This family tree thus spans four generations.

children("douglas") == ["dougie","valerie"]

_{Type: Void}

Say no one else has children.

children(x) == []

_{Type: Void}

We need some functions for computing lineage. Start with childOf.

childOf(x,y) == member?(x,children(y))

_{Type: Void}

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"

_{Type: Void}

And a grandparent of x is just a parent of a parent of x.

grandParentOf(x) == parentOf parentOf x

_{Type: Void}

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]

_{Type: Void}

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)]

_{Type: Void}

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],[]))

_{Type: Void}

Finally, we need a list of people. Since all people are descendants of albert, let’s say so.

people == descendants "albert"

_{Type: Void}

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?

grandchildren "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

\[\]

[“dougie”,”valerie”]

_{Type: List String}

Who are the great-grandparents?

greatGrandParents

Compiling body of rule greatGrandParents to compute value of
   type List String

\[\]

[“albert”]

_{Type: List String}