Ex: Relational Logic and Databases
You have just been promoted to the position of Chief Database Manager for the Cat Fanciers
Association of the Bay Area. As part of your new job, you must maintain a number of
relational databases containing information about cats, their owners, and cat shows. Here are a
few tables from one of your databases:
Cats
Cat Name
coontrane
Breed
Age Owner Last Name
maineCoon 1
crossMaverick persian
godel
turing
devilWoman
maineCoon 4
frege
fedor
maineCoon 1
rakitine
felicia
persian
turing
fruitLoop
abyssinian 2
tarski
ghostbuster
abyssinian 3
enderton
puddy
abyssinian 3
skolem
sirLancelot
persian
godel
Owners of Cats
First Name Last Name
City
Phone Number
herbert
enderton
paloAlto
1758112
gottlob
frege
paloAlto
2134720
kurt
godel
menloPark
2215412
dimitri
rakitine
larkspur
4643842
thoralf
skolem
redwoodCity 7812187
alfred
tarski
sanFrancisco 4555559
alan
turing
menloPark
1417162
Show Participation
Cat Name
Year
Prize
fedor
1999 goldMedal
fruitLoop
1999 silverMedal
devilWoman
1999 none
crossMaverick 1999 none
felicia
1999 none
devilWoman
1998 goldMedal
puddy
1998 silverMedal
coontrane
1998 mostOriginal
sirLancelot
1998 none
devilWoman
1997 bestNewcomer
ghostbuster
1997 mostOriginal
From your background in logic, you know that every row of a database table can be
written in the form of a relation. For example, we could rewrite the first row of the
"Show Participation" table as:
showParticipation(fedor, 1999, goldMedal)
Once we express our databases in terms of such relations, we can then use relational
resolution to perform queries on that database. For example, we might want to
answer the query, "What are ages of all cats whose owners live in Palo Alto?,
which we can express as the following logical sentence:
query(Age) cats(X,Y,Age,Z)
ownersOfCats(W,Z,paloAlto,T)
We then convert this sentence to clausal form and apply resolution until we get all
possible answers:
{ query(3) }
{ query(4) }
The sentence above uses only reverse implication and conjunction (AND); queries
expressible by such sentences are called conjunctive queries. It is possible to write
queries for questions involving not only ANDs, but ORs as well. The format for
questions involving ORs (in other words, disjunctions) is called disjunctive queries;
disjunctive queries are traditionally expressed by several sentences, each of which
uses only conjunctions (besides reverse implication). For example, we could modify
our question above, to ask "What are ages of all cats whose owners live in Palo Alto
or in San Francisco?; this question can be expressed as two logical sentences:
query(Age) cats(X,Y,Age,Z)
ownersOfCats(W,Z,paloAlto,T)
query(Age) cats(X,Y,Age,Z)
ownersOfCats(W,Z,sanFrancisco,T)
To answer this question, we convert each of the sentences into clausal form and
apply resolution. In our example, all possible answers to the question are:
{ query(2) }
{ query(3) }
{ query(4) }
Now you've been handed some queries in English. Convert each query into one or
more sentences of relational logic similar to the example given above, using only the
<= and operators. You may assume that you have a greater-than relation
gt(X,Y), where gt(a,b) means a is greater than b, and a not-equal relation
neq(X,Y), where neq(a,b) means a and b are not equal.
(a) Who are the owners of all Maine Coon cats who have gold medals? (It is
enough to give last names of owners.)
query(Owner) cats(X,maineCoon,Y,Owner)
showParticipation(X,Z,goldMedal)
(b) List all ages of cats who got prizes in 1999, together with their prizes.
(Here you may assume that all possible prizes are listed in the
ShowParticipation table, i.e., any prize is either a gold medal, a silver
medal, a best newcomer prize or the most original prize.)
There is more than one way to write this query. One variant is:
query(Age,Prize)
showParticipation(X,1999,Prize)
neq(Prize,none) cats(X,Y,Age,Z)
You could also write this query as follows:
query(Age,goldMedal)
showParticipation(X,1999,goldMedal)
cats(X,Y,Age,Z)
query(Age,silverMedal)
showParticipation(X,1999,silverMedal)
cats(X,Y,Age,Z)
query(Age,bestNewcomer)
showParticipation(X,1999,bestNewcomer)
cats(X,Y,Age,Z)
query(Age,mostOriginal)
showParticipation(X,1999,mostOriginal)
cats(X,Y,Age,Z)
(c) What are the cities of participants in the shows in years 1997 and 1998?
Again, there is more than one way to write this query. One variant is:
query(City) showParticipation(X,1997,T)
cats(X,Z,Q,W)
ownersOfCats(U,W,City,R)
query(City) showParticipation(X,1998,T)
cats(X,Z,Q,W)
ownersOfCats(U,W,City,R)
This query can also be written as:
query(City) showParticipation(X,Y,T)
gt(Y,1996)
gt(1999,Y)
cats(X,Z,Q,W)
ownersOfCats(U,W,City,R)
(d) Now suppose you define the following view on your databases:
winnerCatIn1999(CatName,CatBreed,OwnerName)
cats(CatName,CatBreed,X,OwnerName)
showParticipation(CatName,1999,goldMedal)
winnerCatIn1999(CatName,CatBreed,OwnerName)
cats(CatName,CatBreed,X,OwnerName)
showParticipation(CatName,1999,silverMedal)
Use this new winnerCatIn1999 relation (as well as any of the original
relations you need) to write a logical sentence for the query,
What are the first names and phone numbers of owners of all abyssinians
who were show winners in 1999?
query(FirstName,PhoneNumber)
winnerCatIn1999(X,abyssinian,OwnerName)
ownersOfCats(FirstName,OwnerName,Y,PhoneNumber)
Ex: Relational Logic Syntax and Semantics
Given the following premises:
The intersection of two convex regions is a convex region.
Q R(region(Q) region(R) convex(Q)
convex(R) region(int(Q,R)) convex(int(Q,R)))
The intersection of two polygons is a polygon.
X Y(polygon(X) polygon(Y)
polygon(int(X,Y)))
Polygons are regions.
Z (polygon(Z) region(Z))
Prove the following statement is correct:
The intersection of two convex polygons is a convex polygon.
B C(polygon(B) polygon(C) convex(B)
convex(C) polygon(int(B,C)) convex(int(B,C)))
(a) Translate each of the premises into clausal form using INSEADOR.
ANSWER:
{region(Q1), region(R1), convex(Q1), convex(R1),
region(int(Q1,R1))}
{region(Q2), region(R2), convex(Q2), convex(R2),
convex(int(Q2,R2))}
{polygon(X3), polygon(Y3), polygon(int(X3,Y3))}
{polygon(Z4), region(Z4)}
(b) Negate the conclusion, and translate it into clausal form using INSEADOR.
ANSWER:
{polygon(badB)}
{polygon(badC)}
{convex(badB)}
{convex(badC)}
{polygon(int(badB,badC)), convex(int(badB,badC))}
(c) Prove that the conclusion is correct by deriving the empty clause
using first-order resolution. This should take about 10 steps.
ANSWER:
1. {region(Q1), region(R1), convex(Q1), convex(R1),
region(int(Q1,R1))}
Premise
2. {region(Q2), region(R2), convex(Q2), convex(R2),
convex(int(Q2,R2))}
Premise
3. {polygon(X3), polygon(Y3), polygon(int(X3,Y3))}
Premise
4. {polygon(Z4), region(Z4)}
Premise
5. {polygon(badB)}
Neg. goal
6. {polygon(badC)}
Neg. goal
7. {convex(badB)}
Neg. goal
8. {convex(badC)}
Neg. goal
9. {polygon(int(badB,badC)), convex(int(badB,badC))}
Neg. goal
10. {polygon(Y10), polygon(int(badB,Y10))}
3,5
11. {polygon(int(badB,badC))}
6,10
12. {region(badB)}
4,5
13. {region(badC)}
4,6
14. {region(R13), convex(badB), convex(R13),
convex(int(badB,R13))}
2,12
15. {convex(badB), convex(badC), convex(int(badB,badC))}
13,14
16. {convex(badC), convex(int(badB,badC))}
7,15
17. {convex(int(badB,badC))}
8,16
18. {convex(int(badB,badC))}
9,11
19. { }
17,18
Ex: MGU
Find a most general unifier for each of the following pairs of sentences if one
exists; otherwise, write NONE. Variables may not be renamed prior to
unification.
(a) races(ascot, X, Z), races(X, Y, sunday)
ANSWER: {X<-ascot, Y<-ascot, Z<-sunday}
(b) cozy(A, timid, F, H, D, D),
cozy(B, C, C, G, B, nice)
ANSWER: {A<-nice, B<-nice, C<-timid, D<-nice, F<timid, G<-H}
(c) party(champagne, Y, Z, songs), party(X, Y,
cheers, Z)
ANSWER: NONE
(d) puzzle(A, tough, funny, H, C, F, easy),
puzzle(A, C, A, boring, tough, B, G)
ANSWER: {A<-funny, B<-F, C<-tough, G<-easy, H<boring}
(e) refreshing(X, Y, try, X),
refreshing(X, again, Y, Y)
ANSWER: NONE
