(ch:4)=
# Representing structured knowledge #
In this chapter we will discuss various ways to represent structured knowledge in Prolog. The central notion is that of a *graph*, which is the mathematical abstraction of the graphical representation of structured knowledge. A graph consists of *nodes*, and *arcs* between nodes. Nodes are identified by their name, and arcs are identified by the pair of nodes they connect. By convention, arcs are taken to be *directed*, which means that an arc from $n_1$ to $n_2$ is not the same as an arc from $n_2$ to $n_1$. Undirected arcs (as in the London Underground example of {numref}`Chapter %s`) can be viewed as consisting of two directed arcs, one in each direction. If an arc is directed from $n_1$ to $n_2$, then $n_1$ is called the *parent* of $n_2$, and $n_2$ is called the *child* of $n_1$.
+++
A *path* in a graph is a sequence of nodes, such that for each consecutive pair $n_i$, $n_j$ in the sequence the graph contains an arc from $n_i$ to $n_j$. If there is a path from $n_k$ to $n_l$, then $n_k$ is called an *ancestor* of $n_l$, and $n_l$ is called a *descendant* of $n_k$. A *cycle* is a path from a node to itself. Obviously, when a path from $n_i$ to $n_j$ passes through a node which is also on a cycle, there are infinitely many different paths from $n_i$ to $n_j$. Thus, a graph consisting of a limited number of nodes and arcs can generate infinite behaviour. This is something to keep in mind when searching such cyclic graphs!
+++
A *tree* is a special kind of graph which contains a *root* such that there is a **unique** path from the root to any other node. From this it follows that for any two nodes in a tree, either there is no path between them, or there is exactly one. Thus, trees are necessarily non-cyclic or *acyclic*. A *leaf* is a node without children. Often, leaves are goal nodes in search spaces like SLD-trees. Strictly speaking, an SLD-tree is not a tree, because there might be several ways to construct the same resolvent. By convention, however, resolvents constructed in a different way are considered to be distinct nodes in the SLD-tree. Usually, trees are drawn upside down, with the root node at the top; arcs are implicitly understood to be directed from top to bottom. Note that, if $n$ is the root of a tree, each of its children is the root of a *subtree* ({numref}`fig:4.1`).
```{figure} /src/fig/part_ii/image000.svg
---
name: 'fig:4.1'
width: 50%
---
A tree with two subtrees.
```