13.3 Datalog: A Relational Rule Language

13.3.1 Semantics of Ground Datalog

The first step in giving the semantics of Datalog is to give the semantics for the ground (variable-free) case.

An interpretation is a triple I=D,ϕ,π

  • D is a non-empty set called the domain. Elements of D are individuals.

  • ϕ is a mapping that assigns to each constant an element of D.

  • π is a mapping that assigns to each n-ary predicate symbol a function from Dn into {true,false}.

ϕ is a function from names into individuals in the world. The constant c is said to denote the individual ϕ(c). Here c is a symbol but ϕ(c) can be anything: a real physical individual such as a person or a virus, an abstract concept such as a course, love, the number 2, or a symbol.

π(p) specifies whether the relation denoted by the n-ary predicate symbol p is true or false for each n-tuple of individuals. If predicate symbol p has no arguments, then π(p) is either true or false. Thus, for predicate symbols with no arguments, this semantics reduces to the semantics of propositional definite clauses.

Example 13.4.

Consider the world consisting of three individuals on a table:

 ✢   ✥         ✮  

These are drawn in this way because they are things in the world, not symbols. ✢ is a pair of scissors, is a telephone, and ✮ is a pencil.

Suppose the constants in our language are phone, pencil, and telephone. We have the predicate symbols noisy and left_of. Assume noisy is a unary predicate (it takes a single argument) and that left_of is a binary predicate (it takes two arguments).

An example interpretation that represents the individuals on the table is

  • D={,,}.

  • ϕ(phone)=, ϕ(pencil)=, ϕ(telephone)=.

  • π(noisy): false true false
    π(left_of): , false , true , true , false , false , true , false , false , false

    Because noisy is unary, it takes a singleton individual and has a truth value for each individual.

    Because left_of is a binary predicate, it takes a pair of individuals and is true when the first element of the pair is left of the second element. Thus, for example, π(left_of)(,)=true, because the scissors are to the left of the telephone; π(left_of)(,)=false, because the pencil is not to the left of itself.

Note how the D is a set of things in the world. The relations are among the individuals in the world, not among the names. As ϕ specifies that phone and telephone refer to the same individual, exactly the same statements are true about them in this interpretation.

Example 13.5.

Consider the interpretation of Figure 13.1.

D is the set with four elements: the person Kim, room 123, room 023, and the CS building. This is not a set of four symbols, but it is the set containing the actual person, the actual rooms, and the actual building. It is difficult to write down this set and, fortunately, you never really have to. To remember the meaning and to convey the meaning to another person, knowledge base designers typically describe D, ϕ, and π by pointing to the physical individuals or a depiction of them (as is done in Figure 13.1) and describe the meaning in natural language.

The constants are kim, r123, r023, and cs_building. The mapping ϕ is defined by the gray arcs from each of these constants to an individual in the world in Figure 13.1.

The predicate symbols are person, in, and part_of. The meaning of these are meant to be conveyed in the figure by the arcs from the predicate symbols.

Thus, the person called Kim is in the room r123 and is also in the CS building, and these are the only instances of the in relation that are true. Similarly, room r123 and room r023 are part of the CS building, and there are no other part_of relationships that are true in this interpretation.

Each ground term denotes an individual in an interpretation. A constant c denotes in I the individual ϕ(c).

A ground atom is either true or false in an interpretation. Atom p(t1,,tn) is true in I if π(p)(t1,,tn)=true, where ti is the individual denoted by term ti, and is false in I otherwise.

Example 13.6.

The atom in(kim,r123) is true in the interpretation of Example 13.5, because the person denoted by kim is indeed in the room denoted by r123. Similarly, person(kim) is true, as is part_of(r123,cs_building). The atoms in(cs_building,r123) and person(r123) are false in this interpretation.

Logical connectives, models and logical consequences have the same meaning as in the propositional calculus:

  • A ground clause is false in an interpretation if the head is false and the body is true (or is empty); otherwise, the clause is true in the interpretation.

  • A model of a knowledge base KB is an interpretation in which all the clauses in KB are true.

  • If KB is a knowledge base and g is a proposition, g is a logical consequence of KB, written KBg, if g is true in every model of KB. Thus KB⊧̸g, meaning g is not a logical consequence of KB, when there is a model of KB in which g is false.