A knowledge base: a family tree

Facts as rows, rules as questions

A knowledge base is a pile of small facts you can ask questions of. One fact per relationship, one rule per question: the grandparent rule asks for a parent of a parent, and the two goals share the middle variable so the two facts are joined on the same person.

This is the shape a database query would take, written in logic. Each goal narrows the search, and the variables do the joining without a single mention of how the data is stored.

Each parent fact is a row with two positions. parent(adam, beth). says adam is a parent of beth, and the order matters: the first argument is the parent, the second the child. A rule that swapped them would still run, but it would answer a different question, so the convention has to be kept everywhere.

What is not in the base

A sibling rule finds two people with a shared parent, and then rules out the answer where both names are the same person with a goal that compares them as terms.

Negation has a special job here. The tree only records what was written down, so asking whether somebody has no parent recorded is really asking whether the search for that fact comes up empty. Prolog is honest about the difference between not recorded and not true, and prose about a knowledge base should be too.

The sibling rule finds a shared parent, then removes the case where both names are the same person. parent(P, A), parent(P, B), A \== B says A and B are siblings if some P is a parent of both and they are not the same term. Without the guard, every person would be their own sibling, which is true of the search but not of the family.

A join is two goals sharing a variable

The grandparent rule is a join: two facts are matched on the shared variable P, and the answer is the pair that survives both matches. A database calls this a join; Prolog calls it two goals. There is no special syntax because sharing a variable is already the join.

The order of the goals decides how the search proceeds, not which answers exist. parent(G, P), parent(P, C) first picks a child of G, then looks for that person’s children; reversing the goals produces the same pairs in a different order. A free variable turns the rule into a search, while a fixed name turns it into a test, and the same three lines serve both.

A join with no matching pair simply fails, which is the correct answer when the relationship does not exist.

A rule with a free variable is a search; the same rule with a name is a test. grandparent(adam, C) enumerates grandchildren, while grandparent(adam, dana) succeeds or fails. The body is identical in both calls, because the engine fills whatever is free and checks whatever is bound.

A worked query

Ask grandparent(adam, C). The first goal parent(adam, P) matches parent(adam, beth) and binds P to beth. The second goal then asks parent(beth, C), which matches parent(beth, dana) and binds C to dana. The answer is printed, and on backtracking the engine finds adam’s second child and repeats.

If the second goal has no match, the engine undoes P and tries the next child of adam. When every child has been tried, the rule fails. That is why the order of the goals changes the work but not the answers: the join is the shared variable, and the search visits the same pairs in a different order.

Two generations, two rules

% One fact per relationship, one rule per question.
parent(adam, beth).
parent(beth, dana).

grandparent(G, C) :-
    parent(G, P),
    parent(P, C).

main :-
    findall(C, grandparent(adam, C), Kids),
    write('grandchildren '), write(Kids), nl,
    ( grandparent(adam, dana) -> write('yes')
                              ; write('no') ), nl.
:- initialization(main).

Try these next

• Add an aunt rule: a sibling of a parent.
• Ask grandparent(G, dana) with G free and print every answer.
• Add a person with no recorded parent and ask a negated goal about them.