# Representing structured knowledge

# 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).