CS 277 Principles of Database Systems Spring 2018 Homework Assignment 2 (due Friday May 18, 2018) Problems: 1. Consider the beer drinkers database consi
c/c++代写,java代写,python代写,matlab代写,作业代写,留学生作业代写
CS 277 Principles of Database Systems Spring 2018 Homework Assignment 2 (due Friday May 18, 2018) Problems: 1. Consider the beer drinkers database consisting of relations over the following relational schema: FREQUENTS(drinker, bar), LIKES(drinker, beer), SERVES(bar, beer) Give relational calculus expressions for the following queries: (a) “List all drinkers who frequent at least one bar that serves at least one beer they like”. (b) “List all drinkers who frequent only bars that serve at least one beer they like.” (c) “List all drinkers who frequent every bar that serves ANCHOR STEAM”. Which of these three queries, if any, is equivalent to a conjunctive query? Justify your answer as best as you can. 2. Let R be a relational schema with attributes A, B, C. Consider the relational calculus expression πA(πA,C(R) on πB,C(R)). (a) Give a conjunctive query written as a relational calculus expression that is equivalent to the above expression. (b) Give a conjunctive query written as rule that is equivalent to the above expression. 3. Recall that a 2CNF-formula is a Boolean formula in conjunctive normal form such that each of its conjuncts is the disjunction of two literals, i.e., each conjunct has one of the following forms: (x ∨ y), (¬x ∨ y), (¬x ∨ ¬y). Recall also that 2Sat is the following decision problem: given a 2CNF formula ϕ, does ϕ have a satisfying assignment? (i.e., an assignment of Boolean values to the variables of ϕ so that each conjunct of ϕ evaluates to 1 (“true”)). (a) Show that 2Sat can be viewed as a special case of the Homomorphism Problem. This entails coming up with a suitable relational database schema S and showing that the question of whether a given 2CNF-formula ϕ is satisfiable is the same question as to whether there is a homomorphism between two particular database instances over S. In fact, the homomorphisms between the two database instances should be precisely the satisfying assignments of ϕ. (b) What changes will you have to make to your solution so that 3Sat can be viewed as a special case of the Homomorphism Problem? 4. Consider the following decision problem, called NATURAL JOIN NON-EMPTINESS: given relations R1,…,Rm, is their natural join R1 on · · · on Rm non-empty? In this version, both the number of relations given and the arity of each relation are arbitrary positive integers. (a) Show that NATURAL JOIN NON-EMPTINESS is in NP. 1 (b) Show that NATURAL JOIN NON-EMPTINESS is an NP-hard problem (Hint: Use a reduction from one of the NP-complete problems discussed in class). (c) Show that NATURAL JOIN NON-EMPTINESS is NP-hard even if the given relations are of arity at most 3 (Hint: Use a reduction from one of the NP-complete problems discussed in class). Note that a solution to this part of the problem gives also a solution to the preceding part, so you need only produce a solution for this part. (d) Let M and K be fixed positive integers. Consider the restriction of NATURAL JOIN NON-EMPTINESS in which we are given at most M relations and each relation has arity at most K. What can you say about the computational complexity of this problem? Is it NP-hard? Is it solvable in polynomial time? 5. Let q1 be the Boolean conjunctive query (written as a rule): q1 : −E(x1, x2), E(x2, x1), E(x2, x3), E(x3, x2), E(x3, x4), E(x4, x3), E(x4, x1), E(x1, x4) and let q2 be the Boolean conjunctive query (also written as a rule): q2 : − E(x1, x2), E(x2, x1), E(x2, x3), E(x3, x2), E(x3, x4), E(x4, x3), E(x4, x1), E(x1, x4), E(x1, x3), E(x3, x1). (a) Is q1 ⊆ q2? (Justify your answer) (b) Is q2 ⊆ q1? (Justify your answer) (c) Find a conjunctive query q3 such that q3 is a minimal conjunctive query equivalent to q1 (justify your answer briefly). (d) Find a conjunctive query q4 such that q4 is a minimal conjunctive query equivalent to q2 (justify your answer briefly). 6. As discussed in class, if q is a Boolean conjunctive query, then a Boolean conjunctive query q 0 is a minimal equivalent conjunctive query to q if q 0 is equivalent to q and has as few conjuncts as any conjunctive query q 00 equivalent to q. Fix now a Boolean conjunctive query q. (a) Show that if both q1 and q2 are minimal equivalent conjunctive queries to q, then the canonical database of q1 is isomorphic to the canonical database of q2 (in other words, q1 and q2 are the “same” conjunctive query up to a renaming of their variables). (b) Show that there is a Boolean conjunctive query q 0 that is a minimal equivalent query to q and is obtained from q by removing zero or more conjuncts of q (in other words, one of the “subqueries” of q is a minimal equivalent conjunctive query to q). 7. Let q be a union qi ∪q2 ∪ · · · ∪qm of conjunctive queries q1, q2, . . . , qm. We say that this union is non-redundant if there is no pair (i, j) such that i 6= j and qi ⊆ qj . (a) Is the union E(x, y) ∨ ∃z(E(x, z) ∧ E(z, y)) ∨ ∃z, w(E(x, z) ∧ E(z, w) ∧ E(w, y)) redundant or non-redundant? Justify your answer. 2 (b) Assume now that q is a non-redundant union q1 ∪ q2 ∪ · · · ∪ qm of Boolean conjunctive queries q1, q2, . . . , qm, and that q 0 is a non-redundant union q 0 1 ∪ q 0 2 ∪ · · · ∪ q 0 n of Boolean conjunctive queries q 0 1 , q0 2 , . . . , q0 n such that q is equivalent to q 0 . i. Using results established in class, show that for each i ≤ m, there is j ≤ n such that qi ≡ q 0 j . ii. Show that m = n. iii. (Optional problem) Do the previous two facts remain true without the assumption that the two unions are non-redundant? Justify your answer as best as you can. Note 1: All written assignments, term project report or term paper, and final examination are to be submitted in a typeset format (preferably in LATEX). Note 2: The purpose of the homework assignments is to help you develop a better understanding of the material covered in class and also to expose you to some material that lack of time prevents us from covering in class. You should try to work out these problems on your own using your notes from the class. You may also want to use the “Foundations of Databases” book and the papers posted at the course webpages as references. If you discuss any of the problems with other students in the class, you are still expected to produce your own write-up of the assignment; moreover, you are expected to state the names of all other students with whom you have shared ideas about the problems. Finally, please state what published or online sources you used, if any, in the solutions of the problems. 3
留学生作业代写,cs作业代写,cs代写,作业代写,北美cs作业代写,澳洲cs作业代写,加拿大cs作业代写,cs作业代写价格,靠谱cs作业代写,程序代写