downloadfile

Fall 2023 Midterm CSC 343 H1F Duration: 90 min. Question 1. [11 marks] Part (a) [1 mark] Using bag semantics, what is {8, 4, 4, 2, 10, 10, 10, 1} − {1, 1, 4, 5, 10, 10}? {8, 4, 2, 10} Part (b) [4 marks] Consider this schema: Kitchen(dish, spoon, towel) Office(desk, chair) Kitchen[dish] ⊆ Office[desk] Suppose we know that relation Kitchen has 18 tuples. 1. What is the fewest tuples that Office could have? 18 2. What is the most tuples that Office could have? (write “no limit" if there is no limit) no limit Suppose we know instead that relation Office has 25 tuples. 3. What is the fewest tuples that Kitchen could have? 0 4. What is the most tuples that Kitchen could have? (write “no limit" if there is no limit) 25 Part (c) [3 marks] Consider this schema with two relations and no other constraints: R1(alpha, bravo, charlie ) R2(charlie, echo , foxtrot) Suppose we know that R2 has 5 tuples (but nothing about what’s in them), and that the contents of R1 a alpha bravo charlie 1 2 3 4 2 5 4 6 5 1. What is the most tuples possible from this query? ( 𝜎 𝑏𝑟𝑎𝑣𝑜 = echo ( 1× 2)) 𝑅 𝑅 3 (not 2, as in the original solutio 2. What is the most tuples possible from this query? (Π ℎ 𝑐 𝑎𝑟𝑙𝑖𝑒 𝑅 2) − (Π ℎ 𝑐 𝑎𝑟𝑙𝑖𝑒 𝑅 1) 5 3. What is the most rows possible from the SQL query below? 3 SELECT distinct bravo, charlie FROM R1, R2 WHERE alpha = foxtrot; Part (d) [3 marks] Suppose we have tables Pony with 10 rows, and Cow with 7 rows, and there are no NULL values in t Assume each of the queries below runs without error. This is all you know. For each of the queries below, what is the fewest possible rows it could yield? 1. SELECT * FROM Pony FULL JOIN Cow ON hoof = ear; 10 (not 17, as in the original solution set) 2. SELECT * FROM Pony NATURAL JOIN Cow; 0 3. SELECT * FROM Pony NATURAL RIGHT JOIN Cow; 7 Solution:

Fall 2023 Midterm CSC 343 H1F Duration: 90 min. This space is for any rough work you might like to do. It will not be marked.

Fall 2023 Midterm CSC 343 H1F Duration: 90 min. 2. Π 𝑒𝑖𝑑 [( 𝜎 𝑎𝑚𝑜𝑢𝑛𝑡 >75 𝑆𝑎𝑙𝑒𝑠 ) − ( 𝜎 𝑎𝑚𝑜𝑢𝑛𝑡 >150 𝑆𝑎𝑙𝑒𝑠 )] Invalid Valid but incorrect Correct Explanation below: Instance below: No explanation or instance required This expression is partly correct: We need to use set difference to get rid of people who have had 150.However, it applies the set difference to entire tuples from Sales. So a single tuple with a day over 150 will remove itself from the result of the first select, but isn’t guaranteed to eliminate that person’s e (Trace the example below if you’re not sure about this.) Any instance that has someone who should result, that is someone who never had a day over 150 but did have a day over 75, but also had 150 will demonstrate the problem. (NB: This explanation was NOT required on the test. It’s just for your learning.) Input instance: eid day amount 123 A 78 123 B 153 456 C 145 Expected result: eid 456 Actual result: eid 123 456 3. Π 𝑒𝑖𝑑 [( 𝜎 𝑎𝑚𝑜𝑢𝑛𝑡 >75 𝑆𝑎𝑙𝑒𝑠 ) ∩ ( 𝜎 𝑎𝑚𝑜𝑢𝑛𝑡 6150 𝑆𝑎𝑙𝑒𝑠 )] Invalid Valid but incorrect Correct Explanation below: Instance below: No explanation or instance required This expression intersects rows that have an amount over 75 with rows that have an amount a A tuple will be in the result iff the amount is in the range (75, 150] . The project keeps the eids from these rows, so we end up with the eid of anyone who had a day of sales valued in the range (75, 150] . This does not guarantee that they’ve never had a day over 150! Again, any instance that has a person with a range (75, 150] AND a day over 150 demonstrates the bug. The question also requires a non-empty expected result, so we must include someone who has never had a day over 150 but has had a day over 7 (NB: This explanation was NOT required on the test. It’s just for your learning.) Input instance: eid day amount 123 A 78 123 B 153 456 C 145 Expected result: eid 456 Actual result: eid 123 456

Fall 2023 Midterm CSC 343 H1F Duration: 90 min. Question 3. [13 marks] Below is the University schema that we used extensively in class. Relations Student(sID, surName, firstName, campus, email, cgpa) Course(dept, cNum, name, breadth) Offering(oID, dept, cNum, term, instructor) Took(sID, oID, grade) Integrity constraints Offering[dept, cNum] ⊆ Course[dept, cNum] Took[sID] ⊆ Student[sID] Took[oID] ⊆ Offering[oID] Part (a) [3 marks] Which of the instances of Offering below violate this integrity constraint? Circle one answer for each in Temp ( ) ∶= Π 𝑑𝑒𝑝𝑡 𝑂 1. 𝑑𝑒𝑝𝑡 ( 𝜎 𝑂 1. = 2. = 3. 𝑑𝑒𝑝𝑡 𝑂 𝑑𝑒𝑝𝑡 𝑂 𝑑𝑒𝑝𝑡 ∧ 𝑂 1. = 2. = 3. 𝑐𝑛𝑢𝑚 𝑂 𝑐𝑛𝑢𝑚 𝑂 𝑐𝑛𝑢𝑚 ∧ 𝑂 1. < 2. < 3. 𝑡𝑒𝑟𝑚 𝑂 𝑡𝑒𝑟𝑚 𝑂 𝑡𝑒𝑟𝑚 [ ( 𝜌 𝑂 1 Offering )×( 𝜌 𝑂 2 Offering )×( 𝜌 𝑂 3 Offering ) ] ) (Π 𝑑𝑒𝑝𝑡 Offering )− Temp = ∅ Violates? yes no (not yes) oID dept cnum term instr 922 CSC 343 5 Craig 555 CSC 343 1 Smith 123 CSC 343 4 Craig 444 CSC 148 2 Liu 319 CSC 148 5 Badr Violates? yes no oID dept cnum term instr 922 GEO 100 3 Reid 555 GEO 200 2 Pitt 123 GEO 200 1 Pitt 444 GEO 300 6 Pitt Violates? yes no oID dept cnum term instr 922 HIS 410 1 Gao 555 HIS 200 1 Gries 123 HIS 410 2 Badr 444 HIS 200 2 Liu 319 HIS 410 5 Pitt 819 HIS 200 5 Gao NB: The third instance repeated OID 319 in its final row; this has been corrected here.

Fall 2023 Midterm CSC 343 H1F Duration: 90 min. Part (c) [8 marks] This query is quite unrealistic, but let’s write it anyway. Write a query in relational algebra to find all instructors who have taught a 400-level course in every department that offers one or more 199 courses. A 199 course is any course with course number 199. A department “offers” a course iff the course is in the Offering relation. You must name the attributes on the LHS of each assignment statement you use. Solution: – To be in the answer, this instructor should have taught some 400-level course in this depart ℎ ℎ 𝑆 𝑜𝑢𝑙𝑑𝐻 𝑎𝑣𝑒𝑇𝑎𝑢𝑔 𝑡 ( , ) ∶= (Π 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 𝑑𝑒𝑝𝑡 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 Offering ) × (Π 𝑑𝑒𝑝𝑡 𝜎 𝑐𝑛𝑢𝑚 =199 Offering ) – This instructor did teach a 400-level course in this department. ℎ 𝐷𝑖𝑑𝑇𝑒𝑎𝑐 ( , ) ∶= (Π 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 𝑑𝑒𝑝𝑡 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 , 𝑑 𝑒𝑝𝑡 ( 𝜎 ≥ 𝑐𝑛𝑢𝑚 400 ∧ ≤ 𝑐𝑛𝑢𝑚 499 Offering )) – This instructor is “missing” this department: They did not teach a 400-level course in this de – and they should have in order to be in the answer. 𝑀 𝑖𝑠𝑠𝑖𝑛𝑔 ( , ) ∶= ℎ ℎ − ℎ 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 𝑑𝑒𝑝𝑡 𝑆 𝑜𝑢𝑙𝑑𝐻 𝑎𝑣𝑒𝑇𝑎𝑢𝑔 𝑡 𝐷𝑖𝑑𝑇𝑒𝑎𝑐 – This instructor is missing no department that they should have taught a 400-level course in 𝐴𝑛𝑠𝑤𝑒𝑟 ( ) ∶= (Π 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 Offering ) − (Π 𝑖𝑛𝑠𝑡𝑟 𝑢𝑐𝑡𝑜𝑟 𝑀 𝑖𝑠𝑠𝑖𝑛𝑔 )

Fall 2023 Midterm CSC 343 H1F Duration: 90 min. Question 4. [8 marks] This question continues with the University database. Assume that it has been defined in SQL. Relations Student(sID, surName, firstName, campus, email, cgpa) Course(dept, cNum, name, breadth) Offering(oID, dept, cNum, term, instructor) Took(sID, oID, grade) Integrity constraints Offering[dept, cNum] ⊆ Course[dept, cNum] Took[sID] ⊆ Student[sID] Took[oID] ⊆ Offering[oID] Define a SQL query to find students who (a) have taken courses in at least 6 different departments, and at least three different instructors across all their 300-level and 400-level courses Report just the sID The result should have no duplicates. Solution : -- This student has taken courses in at least 6 different departments. -- Distinct is required in the count. create view ManyDepartments as select sid from Took join Offering on Took.oID = Offering.oID group by sid having count(distinct dept) >= 6; -- This student has had at least 3 different instructors for 300-level or 400-level courses. -- Distinct is required in the count. create view DiverseInstructors as select sid from Took join Offering on Took.oID = Offering.oID where cnum >= 300 and cnum <= 499 group by sid having count(distinct instructor) >= 3; -- Because we group sid by in each of the views above, neither of them can -- have duplicate sids. So the intersection would not produce duplicates if we -- wrote INTERSECT ALL. It would work properly. -- psql accepts this query without the brackets. -- However the "select * from" (or some form of complete query) is required. (select * from ManyDepartments) intersect (select * from DiverseInstructors);

Fall 2023 Midterm CSC 343 H1F Duration: 90 min. Question 5. [6 marks] Below are four similar SQL queries on the same schema about sales from the Question 3: -- Query A: select eid as successful from sales s1 where exists ( select * from manages, sales s2 where manager = s1.eid and junior = s2.eid ); -- Query B: select manager as successful from Manages where junior in (select distinct eid from sales) and manager in (select distinct eid from sales); -- Query C: select manager as successful from Manages, Sales where junior = eid and manager in (select distinct eid from sales); -- Query D: select manager as successful from Manages, Sales where manager = eid and junior in (select eid from sales); Consider a manager (let’s call her Sonia) who meets the following conditions: • She manages ≥ 1 𝑘 juniors. • 𝑗 ≥ 1 of her juniors have had sales (that is, appear in the Sales table). • In total, her juniors appear 𝑚 times in the Sales table. • Sonia herself appears ≥ 1 𝑛 times in the Sales table. For each question, circle one answer and provide the required additional information below. 1. Will Query A run successfully? Yes No If yes, Sonia will appear in the result this many times: 𝑛 If no, this is why there is an error: 2. Will Query B run successfully? Yes No If yes, Sonia will appear in the result this many times: 𝑗 If no, this is why there is an error: 3. Will Query C run successfully? Yes No If yes, Sonia will appear in the result this many times: 𝑚 If no, this is why there is an error: 4. Will Query D run successfully? Yes No If yes, Sonia will appear in the result this many times: 𝑗 × 𝑛 If no, this is why there is an error: