Continuing from my last post, let me give you an example on how classical programming differs from knowledge-based programming (the example is taken from Prof. Franz Baader’s lecture notes). Consider the acyclic graph in the picture below.

With regards to the above acyclic graph, we would like to solve the following problem: given to node x and y in the graph, determine whether these two nodes are connected.

In the classical programming, this problem can be solved by giving a procedure that gives you precisely the desired answer, namely “yes” if  both nodes are connected, and “no” otherwise. This procedure might be something like this:


procedure connected(x,y)
    if x = a then
        if y = b or y = c then
            return true
        else
            return (connected(b,y) or connected(c,y))
    else
        if x = b then
            if y = d or y = e then
                return true
            else
                return false
        else
            if x = c then
                if y = e then
                    return true
                else
                    return false
            else
                return false

It is straightforward to see that if we ask whether e is connected to any node, the answer would be false. Now, what if the graph is changed, say by adding a new node f and an edge from e to f? Of course, the above procedure will return the wrong answer when we ask whether e is connected to f. We might have to modify the whole program to incorporate this new case.

On the other hand, the knowledge-based programming will solve the above problem in a different way. First, the graph, i.e., the problem description and its restrictions are specified explicitly as the knowledge about graph and the meaning of “connected”. For example, the following knowledge base gives a correct description of the graph and the “connectedness” between nodes in the graph.


directly-connected(a,b).
directly-connected(a,c).
directly-connected(b,d).
directly-connected(b,e).
directly-connected(c,e).

connected(x,y) if directly-connected(x,y).
connected(x,y) if directly-connected(x,z) and connected(z,y).

Next, against the above knowledge base, we give the following query:


connected(a,b)?

To answer the above query, we simply run a general problem solver and get the answer. Thus, classical programming focuses more on “how” to obtain the solution, while knowledge-based programming would focus more on “what” the solution would be like.

In practice, this distinction may not be as strict as what the example illustrated. Classical programming typically also allows parts of the program to contain the data structures that describe the problem specification, whereas some knowledge-based programming applications encode the knowledge about application in the program using procedural rules.

In knowledge representation and reasoning, one of the main research theme is about formulating and specifying languages that allow users to express knowledge symbolically and developing algorithms which can perform as a general problem solver for queries by users to the knowledge base.