Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 40 ยท Facts, Rules and Queries

Worked Example: A Family Tree in Prolog

Build a complete Prolog family tree: facts for parents and gender, rules for father, sibling, uncle, cousin and more, with queries in every direction and common pitfalls.

The family tree is the classic first Prolog program for a good reason: relatives are relations, relations are what Prolog is about, and the rules build on each other in layers. In this lesson you will design a small knowledge base, derive a dozen relationships, and learn the lessons that come from the mistakes people usually make.

The Prolog listings are read-only here; they run unchanged in SWI-Prolog. The runnable blocks use the Python mini-Prolog stand-in on exactly the same program text.

The family

Three generations, drawn as a tree:

flowchart TD
    abe["abe"] --- ida["ida"]
    abe --> tom["tom"]
    abe --> liz["liz"]
    tom --- mia["mia"]
    liz --- sam["sam"]
    tom --> bob["bob"]
    tom --> ann["ann"]
    liz --> kim["kim"]
    liz --> leo["leo"]
    bob --- eve["eve"]
    bob --> zed["zed"]

Abe and Ida are the grandparents. Tom and Liz are their children, and so on.

Step 1: basic facts

Store only what is fundamental and cannot be derived: who is a parent of whom, and who is male or female. Everything else will be a rule.

PROLOG
male(abe).  male(tom).  male(sam).  male(bob).  male(leo).  male(zed).
female(ida). female(liz). female(mia). female(ann). female(kim). female(eve).

% parent(Parent, Child)
parent(abe, tom).  parent(ida, tom).
parent(abe, liz).  parent(ida, liz).
parent(tom, bob).  parent(mia, bob).
parent(tom, ann).  parent(mia, ann).
parent(liz, kim).  parent(sam, kim).
parent(liz, leo).  parent(sam, leo).
parent(bob, zed).  parent(eve, zed).

Using one parent/2 predicate plus male/1 and female/1 is better than separate mother/2 and father/2 facts: the data is stored once, and mother and father become rules.

Step 2: first-level rules

PROLOG
father(F, C)  :- parent(F, C), male(F).
mother(M, C)  :- parent(M, C), female(M).
child(C, P)   :- parent(P, C).
son(S, P)     :- child(S, P), male(S).
daughter(D, P):- child(D, P), female(D).
grandparent(G, C) :- parent(G, P), parent(P, C).

Each rule is one line and reads like a definition. Queries now work in any direction: father(F, bob) finds Bob's father, father(tom, C) lists Tom's children, and father(F, C) enumerates all father-child pairs.

Step 3: siblings and extended family

PROLOG
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.
brother(B, X) :- sibling(B, X), male(B).
sister(S, X)  :- sibling(S, X), female(S).

uncle(U, N)   :- parent(P, N), brother(U, P).
aunt(A, N)    :- parent(P, N), sister(A, P).
cousin(X, Y)  :- parent(P, X), parent(Q, Y), sibling(P, Q).

The cousin rule says: X and Y are cousins if X's parent and Y's parent are siblings. Each rule builds on the one before: uncle uses brother, which uses sibling, which uses parent. This layering is the main design technique in Prolog.

Run it

Python The whole family (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look closely at uncle(U, kim). The answer U = tom appears twice. Why? Kim's mother is Liz, and brother(U, liz) needs sibling(U, liz). Tom and Liz share two parents, Abe and Ida, so the sibling rule finds Tom twice, once via each shared parent. Prolog reports every proof, and there are two. The same duplication shows up in cousin(bob, C).

Fixing duplicate answers

Three tools handle duplicates. We introduce them briefly; each is covered later.

  1. Collect and deduplicate with setof/3: setof(U, uncle(U, kim), Us) gives Us = [tom].
  2. Ask for the first answer only with once/1: once(uncle(U, kim)).
  3. Change the design so a sibling pair is proved only once, for example by requiring that a shared parent is the father: sibling(X, Y) :- father(P, X), father(P, Y), X \= Y. This works when every child has a recorded father, but it is less general.

In the real world, half siblings share only one parent, which is why the rule uses "some shared parent". Honest modelling usually creates a few duplicates, and setof/3 or distinct/1 is the clean answer.

Querying in every direction

The same program answers many kinds of questions:

PROLOG
?- grandparent(abe, G).     % who are Abe's grandchildren?
?- grandparent(G, zed).     % who are Zed's grandparents?
?- grandparent(G, C).       % list all grandparent-grandchild pairs
?- father(tom, C), mother(mia, C).   % children of both Tom and Mia

The last query is a conjunction: it finds children whose father is Tom and whose mother is Mia, so C = bob ; C = ann.

What the model cannot do yet

Try to write ancestor/2, meaning a parent, grandparent, great-grandparent and so on without limit. With only the tools so far you would need one rule for every depth: parent, then grandparent, then great_grandparent. The family may have any number of generations, so this does not scale. The tool you need is recursion, introduced in Recursion in Prolog.

Exercise

Add these rules to the database and test them with the stand-in:

  • great_grandparent(G, C).
  • niece(N, X): N is a child of one of X's siblings and female.
  • half_sibling(X, Y): they share exactly one parent. (Hint: you need a check for "not both parents the same". Think about \+, which the next lessons introduce.)
Python Add great_grandparent (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

great_grandparent is defined with grandparent, which shows how layered rules shorten new definitions.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why store parent/2 and male/female facts instead of father and mother facts?

    Keeping basic facts minimal avoids duplication. Derived relationships belong in rules.
  2. 2. Why did uncle(U, kim) return tom twice?

    sibling(X, Y) succeeds once for each shared parent. Prolog returns every proof.
  3. 3. Which rule correctly defines cousin?

    Cousins are children of siblings.
  4. 4. What problem needs recursion rather than more rules?

    The number of generations is unbounded, so ancestor must refer to itself.

Summary

  • Keep the base facts minimal (parent/2, male/1, female/1) and derive other relations with rules.
  • Layered rules (sibling, brother, uncle) keep each definition short.
  • One program answers questions in every direction.
  • Several proofs give duplicate answers; setof/3, once/1 or a better design removes them.
  • Unlimited depth (ancestors) needs recursion.

Next: The Closed-World Assumption and Negation