Starting from:
$30

$24

Homework #2 Solution

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.





































































More products