Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
12.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,φ,π⟩, where
- 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 object such as a person or a virus, an abstract concept such as a course, love, or the number 2, or even 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.
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 objects 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 objects in the world, not among the names. As φ specifies that phone and telephone refer to the same object, exactly the same statements are true about them in this interpretation.
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 12.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 object in the world in Figure 12.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.
It is important to emphasize that the elements of D are the real physical individuals, and not their names. The name kim is not in the name r123 but, rather, the person denoted by kim is in the room denoted by r123.
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.
