CSE233 DATABASE THEORY - Problem Set #2: Relational calculus
CSE 233 Spring 2024
Problem Set #2
Due on Tuesday, April 30, 5pm (in class)
Please typeset your answer (latex recommended).
1. (3 points) Prove that it is undecidable whether a CALC query is mono- tonic (recall that a query Q is monotonic if for all databases D1,D2, if D1 ⊆ D2 then Q(D1) ⊆ Q(D2)).
2. (3 points) Let Q1, Q2, Q3 be conjunctive queries (no equality). Prove that, if Q1 ⊆ (Q2 ∪ Q3), then Q1 ⊆ Q2 or Q1 ⊆ Q3 (recall that the notation P ⊆ R for queries P,R means that P(I) ⊆ R(I) for every database I).
3. (i) (4 points) The language ∃∗∀∗CALC consists of all CALC sentences of the form
∃y1 ...∃yn∀z1 ...∀zm φ(y1,...,yn,z1 ...zm)
where φ is a quantifier-free CALC formula. Prove that satisfiability is decid- able for sentences in ∃∗∀∗CALC. Hint: Come up with a bound on the size of databases one needs to look at in order to check satisfiability. More pre- cisely, show that a sentence Q in this language is satisfiable iff it is satisfied on some database of size bounded by f(Q) for some computable function f. (ii) (3 points) The language CQ− consists of queries of the form φ(x ̄) − ψ(x ̄) where φ and ψ are CQs. Prove that equivalence of CQ− queries is decidable.
4. (5 points) A database consists of the following binary relations: PAB QBC RAC
(P with attributes AB, Q with attributes BC and R with attributes AC). Consider the relational algebra query P I Q I R (equivalent to the formula φ(a,b,c) = P(a,b)∧Q(b,c)∧R(a,c)). Assuming that P,Q and R have size at most n (i.e. they each contain at most n pairs), find the tightest upper boundyoucanonthesizeofP IQIR,asafunctionofn.
Hint: There is an obvious upper bound of n2. Try to do better. 1
5. (2 points) Recall the movie database in Problem 1 of the previous home- work, and the query List the theaters showing only movies by Hitchcock. Express this query in nr-Datalog¬.
2
