Syntax of Datalog
A variable starts with upper-case letter or with underscore (’ ’)
A constant is a sequence of letters, digits or underscore (’ ’) and starts with lower-case letter
or is a sequence of digits (numeral)
or is any sequence of characters between single quotes.
CPSC 312 — Lecture 22 1 / 13
©D. Poole 2021
Syntax of Datalog
A variable starts with upper-case letter or with underscore (’ ’)
A constant is a sequence of letters, digits or underscore (’ ’) and starts with lower-case letter
or is a sequence of digits (numeral)
or is any sequence of characters between single quotes.
A predicate symbol starts with lower-case letter. A term is either a variable or a constant.
An atomic symbol (atom) is of the form p or p(t1, . . . , tn) where p is a predicate symbol and ti are terms.
CPSC 312 — Lecture 22 1 / 13
©D. Poole 2021
Syntax of Datalog (cont)
A definite clause is either
— an atomic symbol (a fact) or — a rule of the form:
a :-b1,···,bm
head body
where a and bi are atomic symbols.
[A fact is treated as a rule with an empty body (m=0).]
CPSC 312 — Lecture 22 2 / 13
©D. Poole 2021
Syntax of Datalog (cont)
A definite clause is either
— an atomic symbol (a fact) or — a rule of the form:
a :-b1,···,bm
head body
where a and bi are atomic symbols.
[A fact is treated as a rule with an empty body (m=0).]
A knowledge base is a set of definite clauses. A query is of the form ?b1, ···, bm.
CPSC 312 — Lecture 22 2 / 13
©D. Poole 2021
Semantics: General Idea
A semantics specifies the meaning of sentences in the language. An interpretation specifies:
what objects (individuals) are in the world
the correspondence between symbols in the computer and objects and relations in world
constants denote individuals
predicate symbols denote relations
CPSC 312 — Lecture 22 3 / 13
©D. Poole 2021
Formal Semantics
An interpretation is a triple I = ⟨D, φ, π⟩, where
D, the domain, is a nonempty set. Elements of D are individuals.
CPSC 312 — Lecture 22 4 / 13
©D. Poole 2021
Formal Semantics
An interpretation is a triple I = ⟨D, φ, π⟩, where
D, the domain, is a nonempty set. Elements of D are
individuals.
φ is a mapping that assigns to each constant an element of D. Constant c denotes individual φ(c).
CPSC 312 — Lecture 22 4 / 13
©D. Poole 2021
Formal Semantics
An interpretation is a triple I = ⟨D, φ, π⟩, where
D, the domain, is a nonempty set. Elements of D are
individuals.
φ is a mapping that assigns to each constant an element of D. Constant c denotes individual φ(c).
π is a mapping that assigns to each n-ary predicate symbol a relation: a function from D n into {TRUE, FALSE}.
CPSC 312 — Lecture 22 4 / 13
©D. Poole 2021
Example Interpretation
Constants: phone, pencil, telephone.
Predicate Symbol: noisy (unary), left of (binary).
D = {,,}.
CPSC 312 — Lecture 22 5 / 13
©D. Poole 2021
Example Interpretation
Constants: phone, pencil, telephone.
Predicate Symbol: noisy (unary), left of (binary).
D = {,,}.
φ(phone) = , φ(pencil) = , φ(telephone) = .
CPSC 312 — Lecture 22
5 / 13
©D. Poole 2021
Example Interpretation
Constants: phone, pencil, telephone.
Predicate Symbol: noisy (unary), left of (binary).
D = {,,}.
φ(phone) = , φ(pencil) = , φ(telephone) = .
π(noisy ): π(left of ): ⟨, ⟩
⟨, ⟩ ⟨, ⟩
FALSE ⟨⟩ TRUE
FALSE
TRUE TRUE FALSE
⟨⟩ FALSE
FALSE FALSE
⟨⟩ TRUE ⟨, ⟩
FALSE ⟨, ⟩ FALSE ⟨, ⟩
⟨, ⟩ ⟨, ⟩ ⟨, ⟩
CPSC 312 — Lecture 22
5 / 13
©D. Poole 2021
Important points to note
The domain D can contain real things (entities, objects). (e.g., a person, a room, a course). D can’t necessarily be stored in a computer.
CPSC 312 — Lecture 22 6 / 13
©D. Poole 2021
Important points to note
The domain D can contain real things (entities, objects). (e.g., a person, a room, a course). D can’t necessarily be stored in a computer.
π(p) specifies whether the relation denoted by the n-ary predicate symbol p is true or false for each n-tuple of individuals.
CPSC 312 — Lecture 22 6 / 13
©D. Poole 2021
Important points to note
The domain D can contain real things (entities, objects). (e.g., a person, a room, a course). D can’t necessarily be stored in a computer.
π(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.
CPSC 312 — Lecture 22 6 / 13
©D. Poole 2021
Truth in an interpretation
A constant c denotes in I the individual φ(c).
CPSC 312 — Lecture 22 7 / 13
©D. Poole 2021
Truth in an interpretation
A constant c denotes in I the individual φ(c). Ground (variable-free) atom p(t1, . . . , tn) is
true in interpretation I if π(p)(⟨φ(t1), . . . , φ(tn)⟩) = TRUE in interpretation I and
false otherwise.
CPSC 312 — Lecture 22 7 / 13
©D. Poole 2021
Truth in an interpretation
A constant c denotes in I the individual φ(c). Ground (variable-free) atom p(t1, . . . , tn) is
true in interpretation I if π(p)(⟨φ(t1), . . . , φ(tn)⟩) = TRUE in interpretation I and
false otherwise.
Ground clause h :- b1, . . . , bm is false in interpretation I if hisfalseinI andeachbi istrueinI,andistruein interpretation I otherwise.
CPSC 312 — Lecture 22 7 / 13
©D. Poole 2021
Models and logical consequences (recall)
A knowledge base, KB, is true in interpretation I if and only if every clause in KB is true in I.
CPSC 312 — Lecture 22 8 / 13
©D. Poole 2021
Models and logical consequences (recall)
A knowledge base, KB, is true in interpretation I if and only if every clause in KB is true in I.
A model of a set of clauses is an interpretation in which all the clauses are true.
CPSC 312 — Lecture 22 8 / 13
©D. Poole 2021
Models and logical consequences (recall)
A knowledge base, KB, is true in interpretation I if and only if every clause in KB is true in I.
A model of a set of clauses is an interpretation in which all the clauses are true.
If KB is a set of clauses and g is a conjunction of atoms, g is a logical consequence of KB, written KB |= g, if g is true in every model of KB.
That is, KB |= g if there is no interpretation in which KB is true and g is false.
CPSC 312 — Lecture 22 8 / 13
©D. Poole 2021
User’s view of Semantics
1. Choose a task domain: intended interpretation.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
3. For each relation you want to represent, associate a predicate symbol in the language.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
3. For each relation you want to represent, associate a predicate symbol in the language.
4. Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
3. For each relation you want to represent, associate a predicate symbol in the language.
4. Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
5. Ask questions about the intended interpretation.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
3. For each relation you want to represent, associate a predicate symbol in the language.
4. Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
5. Ask questions about the intended interpretation.
6. If KB |= g, then g must be true in the intended interpretation.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
3. For each relation you want to represent, associate a predicate symbol in the language.
4. Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
5. Ask questions about the intended interpretation.
6. If KB |= g, then g must be true in the intended interpretation.
The computer doesn’t know the intended interpretation and meaning of symbols, but it is important to convey the intended interpretation in comments for other people and for you in the future.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
3. For each relation you want to represent, associate a predicate symbol in the language.
4. Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
5. Ask questions about the intended interpretation.
6. If KB |= g, then g must be true in the intended interpretation.
The computer doesn’t know the intended interpretation and meaning of symbols, but it is important to convey the intended interpretation in comments for other people and for you in the future.
When we say “give the intended interpretation” means specify in comments what objects exist and the mappings of steps 2 and 3.
©D. Poole 2021
CPSC 312 — Lecture 22 9 / 13
Computer’s view of semantics
The computer doesn’t have access to the intended interpretation.
CPSC 312 — Lecture 22 10 / 13
©D. Poole 2021
Computer’s view of semantics
The computer doesn’t have access to the intended interpretation.
All it knows is the knowledge base.
CPSC 312 — Lecture 22 10 / 13
©D. Poole 2021
Computer’s view of semantics
The computer doesn’t have access to the intended interpretation.
All it knows is the knowledge base.
The computer can determine if a formula is a logical consequence of KB.
CPSC 312 — Lecture 22
10 / 13
©D. Poole 2021
Computer’s view of semantics
The computer doesn’t have access to the intended interpretation.
All it knows is the knowledge base.
The computer can determine if a formula is a logical consequence of KB.
If KB |= g then g must be true in the intended interpretation.
CPSC 312 — Lecture 22 10 / 13
©D. Poole 2021
Computer’s view of semantics
The computer doesn’t have access to the intended interpretation.
All it knows is the knowledge base.
The computer can determine if a formula is a logical consequence of KB.
If KB |= g then g must be true in the intended interpretation. If KB ̸|= g then there is a model of KB in which g is false.
This could be the intended interpretation.
CPSC 312 — Lecture 22 10 / 13
©D. Poole 2021
Variables
Variables are universally quantified in the scope of a clause.
CPSC 312 — Lecture 22 11 / 13
©D. Poole 2021
Variables
Variables are universally quantified in the scope of a clause.
A variable assignment is a function from variables into the domain.
CPSC 312 — Lecture 22 11 / 13
©D. Poole 2021
Variables
Variables are universally quantified in the scope of a clause. A variable assignment is a function from variables into the
domain.
Universal quantification means the clause is true for all variable assignments.
CPSC 312 — Lecture 22 11 / 13
©D. Poole 2021
Variables
Variables are universally quantified in the scope of a clause. A variable assignment is a function from variables into the
domain.
Universal quantification means the clause is true for all variable assignments.
Given an interpretation and a variable assignment, each term denotes an individual and
each clause is either true or false.
CPSC 312 — Lecture 22 11 / 13
©D. Poole 2021
Queries and Answers
A query is a way to ask if a body is a logical consequence of the knowledge base:
?b1, ···, bm. An answer is either
an instance of the query that is a logical consequence of the knowledge base KB, or
no (or false) if no instance is a logical consequence of KB.
CPSC 312 — Lecture 22 12 / 13
©D. Poole 2021
©D. Poole 2021
CPSC 312 — Lecture 22 13 / 13