13.3 Datalog: A Relational Rule Language

13.3.3 Queries with Variables

Queries are used to ask whether some statement is a logical consequence of a knowledge base. With propositional queries, a user can ask yes-or-no queries. Queries with variables allow the users to ask for the individuals that make the query true.

An instance of a query is obtained by substituting terms for the variables in the query. Each occurrence of a variable in a query must be replaced by the same term. Given a query with free variables, an answer is either an instance of the query that is a logical consequence of the knowledge base, or “no”, meaning that no instances of the query logically follow from the knowledge base. Instances of the query are specified by providing values for the variables in the query. Determining which instances of a query follow from a knowledge base is known as answer extraction.

An answer of “no” does not mean that the query is false in the intended interpretation; it simply means that there is no instance of the query that is a logical consequence.

% imm_west(W,E) is true if room W is immediately west of room E.

imm_west(r101,r103).
imm_west(r103,r105).
imm_west(r105,r107).
imm_west(r107,r109).
imm_west(r109,r111).
imm_west(r131,r129).
imm_west(r129,r127).
imm_west(r127,r125).

% imm_east(E,W) is true if room E is immediately east of room W.

imm_east(E,W)
    imm_west(W,E).

% next_door(R1,R2) is true if room R1 is next door to room R2.

next_door(E,W)
    imm_east(E,W).
next_door(W,E)
    imm_west(W,E).

% two_doors_east(E,W) is true if room E is two doors east of room W.

two_doors_east(E,W)
    imm_east(E,M)
    imm_east(M,W).

% west(W,E) is true if room W is west of room E.

west(W,E)
    imm_west(W,E).
west(W,E)
    imm_west(W,M)
    west(M,E).
Figure 13.2: A knowledge base about rooms
Example 13.13.

Consider the clauses of Figure 13.2. The person who wrote these clauses presumably has some meaning associated with the symbols, and has written the clauses because they are true in some, perhaps imaginary, world. The computer knows nothing about rooms or directions. All it knows are the clauses it is given; and it can compute their logical consequences.

The user can ask the following query:

𝘢𝘴𝘬 imm_west(r105,r107).

and the answer is yes. The user can ask the query

𝘢𝘴𝘬 imm_east(r107,r105).

and the answer is, again, yes. The user can ask the query

𝘢𝘴𝘬 imm_west(r205,r207).

and the answer is no. This means it is not a logical consequence, not that it is false. There is not enough information in the database to determine whether or not r205 is immediately west of r207.

The query

𝘢𝘴𝘬 next_door(R,r105).

has two answers. One answer, with R=r107, means next_door(r107,r105) is a logical consequence of the clauses. The other answer is for R=r103. The query

𝘢𝘴𝘬 west(R,r105).

has two answers: one for R=r103 and one for R=r101. The query

𝘢𝘴𝘬 west(r105,R).

has three answers: one for R=r107, one for R=r109, and one for R=r111. The query

𝘢𝘴𝘬 next_door(X,Y).

has 16 answers, including

X=r103,Y=r101
X=r105,Y=r103
X=r101,Y=r103
.