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 Chapter 1) 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 (Figure 4.1).

Figure 4.1 A tree with two subtrees.