SIZE BOUNDS FOR JOINS [25%]
[15%] Compute the maximum possible output size for the following join queries. Assume that all relations have the same size N.
q(x, y, z) : R(x), T(y), U(z), S(x, y, z).
q(x, y, z, w, t) : R(x, y), S(y, z), T(z, w), U(w, x), V(x, t).
q(x, y, z, w) : R(x, y, z), S(x, z, w), T(x, y, w), U(y, z, w).
[10%] Suppose that relation Ri has size Ni (in tuples). Compute the maximum out-put size for the following query. (Hint: there will be different cases depending on the given Ni).
q(x1, x2, x3, x4, x5) : R1(x1, x2), R2(x2, x3), R3(x3, x4), R4(x4, x5).
DATALOG [75%]
[15%] Is the following Datalog program equivalent to a UCQ query? If so, write the query. If not, prove why it is not the case.
B(X, Y) : - L(X, Y).
B(X, Y) : - T(X), B(Z, Y).
[20%] A Datalog program P with a singe recursive predicate is said to be bounded if there is a positive integer n0 such that, on every database instance I, the bottom-up evaluation of P terminates within at most n0 steps. Otherwise, we say that P is unbounded.
Prove that transitive closure is unbounded.
Give an example of a Datalog program that is bounded and has at least one recursive predicate.
[10%] Consider the following Datalog program:
1
T(x,y) :- R(x,y).
T(x,t) :- T(x,y),T(y,z),T(z,w),R(w,t).
Can you write an equivalent linear Datalog program? If yes, provide the program; otherwise, explain why this is not the case.
[20%] Perform the magic set transformation for the following Datalog program:
T(x,y) :- F(x,y).
T(x,y) :- up(x,z1),T(z1,z2),F(z2,z3),T(z3, z4),down(z4,y).
q(y) :- T(a,y).
[10%] Find all possible stratifications for the following Datalog program with nega-tion:
T(x)
:- S(x), not R(x).
S(x)
:- T(x), not
R(x).
U(x)
:-
R(x), not
T(x), not S(x).
V(x,y) :-
V(x,y), not U(x), not U(y).
DELIVERABLES
Submit a single PDF document using Canvas (Homework 2). It is strongly suggested to use LATEX to write your solution.
