Introduction to
Logic Programming
What
versus
How
 

Chapter 4 - Examples


4.1 Introduction

In this chapter, we look at some simple examples of queries. We start with some application ares we have already seen - Kinship, Blocks World, University data. Then we look at how we can write queries that define solutions to a few classic constraint satisfaction problems.

4.2 Kinship

Consider a variation of the Kinship application introduced in Chapter 2. In this case, our vocabulary consists of symbols (representing people) and a binary predicate parent (which is true of two people if and only if the person specified as the first argument is the parent of the person specified as the second argument).

Given data about parenthood expressed using this vocabulary, we can write queries to extract information about other relationships as well. For example, we can find grandparents and grandchildren by writing the query shown below. A person X is the grandparent of a person Z if X is the parent of a person Y and Y is the parent of Z. The variable Y here is a thread variable that connects the first subgoal to the second but does not itself appear in the head of the rule.

goal(X,Z) :- parent(X,Y) & parent(Y,Z)

In general, we can write queries with multiple rules. For example, we can collect all of the people mentioned in our dataset by writing the following multi-rule query. In this case the conditions are disjunctive (at least one must be true), whereas the conditions in the grandfather case are conjunctive (both must be true).

goal(X) :- parent(X,Y)
goal(Y) :- parent(X,Y)

In some cases, it is helpful to use built-in relations in our queries. For example, we can ask for all pairs of people who are siblings by writing the query rule shown below. We use the distinct condition here to avoid listing a person as his own sibling.

goal(Y,Z) :- parent(X,Y) & parent(X,Z) & distinct(Y,Z)

While we can express many common kinship relationships using our query language, there are some relationships that are just too difficult. For example, there is no way to ask for all ancestors of a person (parents, grandparents, great grandparents, and so forth). For this, we need the ability to write recursive queries. We show how to write such queries in the chapter on view definitions.

4.3 Blocks World

Once again, consider the Blocks World introduced in Chapter 2. The Blocks World scene described earlier is repeated below.

A
B
D
C
E
 
Figure 1 - One state of Blocks World.

As before, we adopt a vocabulary with five symbols to denote the five blocks in the scene - a, b, c, d, and e. We use the unary predicate block to state that an object is a block. We use the binary predicate on to express the fact that one block is directly on another. We use above to say that a block is somewhere above another block. We use the unary predicate cluttered to a block has other blocks on top of it, and we use the unary predicate clear to say that a block has nothing on top of it. We use the unary predicate supported to say that a block is resting on another block, and we use the unary predicate table to say that a block is resting on the table.

Given this vocabulary, we can describe the scene in Figure 1 by writing ground atomic sentences that state which relations hold of which objects or groups of objects. Let's start with block. There are five blocks in this case, named a, b, c, d, and e.

block(a)
block(b)
block(c)
block(d)
block(e)

Some of these blocks are on top of each other, and some are not. The following sentences capture the relationships in Figure 1.

on(a,b)
on(b,c)
on(d,e)

We can do the same for the other relations. However, there is an easier way. Some of the other relations can be defined as queries written in terms of block and on. Hence, we do not need to store any additional data.

A block is cluttered if and only if there is a block resting on it.

goal(Y) :- on(X,Y)

A block is clear if and only if there is nothing on it.

goal(Y) :- block(Y) & countofall(X,on(X,Y),0)

A block is supported if and only if it is resting on some block.

goal(X) :- on(X,Y)

A block is on the table if and only if it is not resting on some block.

goal(X) :- block(X) & countofall(Y,on(X,Y),0)

Three blocks satisfy the stack< relation if and only if the first is on the second and the second is on the third.

goal(X,Y,Z) :- on(X,Y) & on(Y,Z)

Unfortunately, we cannot define the above relation as a simple query. For that, we need the power of view definitions described in Chapter 7.

4.4 Example - Map Coloring

Consider the problem of coloring planar maps using only four colors, the idea being to assign each region a color so that no two adjacent regions are assigned the same color.

A typical map is shown below. Here we have six regions. Some are adjacent to each other, meaning that they cannot be assigned the same color. Others are not adjacent, meaning that they can be assigned the same color.



We can enumerate the hues to be used as shown below. The constants red, green, blue, purple, stand for the hues red, green, blue, and purple respectively.

hue(red)
hue(green)
hue(blue)
hue(purple)

In the case of the map shown above, our goal is to find six hues (one for each region of the map) such that no two adjacent regions have the same hue. We can express this goal by writing the query shown below.

goal(C1,C2,C3,C4,C5,C6) :-
  hue(C1) & hue(C2) & hue(C3) & hue(C4) & hue(C5) & hue(C6) &
  distinct(C1,C2) & distinct(C1,C3) & distinct(C1,C5) & distinct(C1,C6) &
  distinct(C2,C3) & distinct(C2,C4) & distinct(C2,C5) & distinct(C2,C6) &
  distinct(C3,C4) & distinct(C3,C6) & distinct(C5,C6)

Evaluating this query will result in 6-tuples of hues that ensure that no two adjacent regions have the same color. In problems like this one, we usually want only one solution rather than all solutions. However, finding even one solution is such cases can be costly. In Chapter 6, we discuss ways of writing such queries that makes the process of finding such solutions more efficient.

Exercises

Exercise 4.1: Assume we have a dataset with a binary predicate parent (which is true of two people if and only if the person specified as the first argument is the parent of the person specified as the second argument). Write a query that defines the property of being childless. Hint: use the aggregate operator countofall. And be sure your query is safe. (This exercise is not difficult, but it is slightly tricky.)

Exercise 4.2: For each of the following problems, write a query to solve the problem. Values should include just the digits 8, 1, 4, 7, 3 and each digit should be used at most once in the solution of each puzzle. Your query should express the problem as stated, i.e. you should not first solve the problem yourself and then have the query simply return the answer.

(a) The product of a 1-digit number and a 2-digit number is 284.
(b) The product of two 2-digit numbers plus a 1-digit number is 3,355.
(c) The product of a 3-digit number and a 1-digit number minus a 1 digit number is 1,137.
(d) The product of a 2-digit number and a 3-digit number is between 13,000 and 14,000.
(e) When a 3-digit number is divided by a 2-digit number the result is between 4 and 6.