CS345 Assignment #1
Due Monday, April 12, 1999
Some Mechanics for Homeworks
For All Students
Assignments are due at
4:30 PM on Monday. You are allowed one lateness of up to 48
hours; use that privilege carefully.
For OnCampus Students
Assignments should be turned in during class or at
the course secretary's office: Gates Building room 436.
If you want a receipt for your work, Ms. Siroker can give you one.
For SITN students
Assignments due on Monday
must be timestamped by the Tuesday morning courier to be considered
ontime.
Like all students, you have one free 48hour exception.
You should not have to worry about receipts for work, because SITN logs
everything it receives.
Remember: the due time/day of 4:30 PM Monday applies to you too, although
we often cannot verify the exact time you delivered your work to your
local pickup point.
However, please do not imagine, say, that it is OK to handdeliver the
work Tuesday morning.
Problem Set

(25 pts.)
In the class notes, we discussed the problem of ``make files,'' in which
we used the EDB predicates source(F), includes(F,G),
and
create(F,P,G).
We designed a Datalog program to find the set of pairs of files F
and G such that F needs G in some way.
However, this program did not deal with the need for certain programs
(the P in the create predicate) by files.
Write a Datalog program for the predicate needs(F,P), which
means that the program P is needed at some step of the creation
of file F.

(25 pts.)
We can represent integers as terms using the constant 0
and the ``successor'' function
symbol s; e.g., the integers 0, 1, 2, and 3 are represented by
0,,
s(0),
s(s(0)), and
s(s(s(0))).
We can then represent a state of the NIM game, as state(I,J,K),
where I, J, and K are three integers represented as
above.
For example, the initial state of the game, with rows of 3, 5, and 7
markers, is represented by:
state(s(s(s(0))), s(s(s(s(s(0))))), s(s(s(s(s(s(s(0))))))))
Legal moves in NIM take one or two markers from one of the rows.
We can therefore make the move predicate an IDB relation, by
describing the pairs in the relation for predicate
move(S,T) with Datalog rules.
 (a)

Write the win program with an IDB predicate move using
rules for that predicate that you design.
 (b)

Is your program stratified?
Why or why not?
 (c)

Is your program locally stratified?
Why or why not?

(25 pts.)
Below we see a Datalog program.
p(X,Y) : q(X,Y)
p(X,Y) : p(X,A) & p(A,B) & p(B,Y)
where q is an EDB predicate.
 (a)

Write the basis and iterative computations of seminaive evaluation for
this program, expressing your assignments in relational algebra (as in
the class example).
 (b)

Suppose that q represents arcs in a graph.
What does p represent?

(25 pts.)
Consider the following Datalog program:
p0(X) : q(X)
p1(X) : q(X) & NOT p0(X)
p2(X) : q(X) & NOT p1(X)
p3(X) : q(X) & NOT p2(X)
p4(X) : q(X) & NOT p3(X)
p5(X) : q(X) & NOT p4(X)
p6(X) : q(X) & NOT p5(X)
p7(X) : q(X) & NOT p6(X)
p8(X) : q(X) & NOT p7(X)
p9(X) : q(X) & NOT p8(X)
where EDB predicate q has a relation consisting of the one
constant a.
 (a)

How many minimal models are there?
Justify your answer by describing the minimal models.
Don't try to list them; there are too many.
Hint: can a minimal model have an IDB fact with an argument other than
a?
 (b)

Which, if any, of these models is the stratified model?