12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688 1/12
Q1 General Instructions for COMS W4111.001 Midterm Exam
0 Points
Date and time of exam: Thursday October 29, 1:10-2:25 p.m. ET (you need explicit permission from Professor Gravano to take the exam at a different time)
Duration of exam: 75 minutes
Exam is closed book, closed notes; no calculators or electronic devices are allowed, other than (1) the web browser tab for Gradescope where you will complete the exam and (2) your Zoom window (see below).
You can have a blank piece of scrap paper with you to work out the solutions to the questions if you want, but you need to enter all your answers online on Gradescope; you will not be submitting your scrap paper.
You must join the regular Zoom meeting for the class and turn on your video for the duration of the exam, unless you are taking the exam (with explicit permission from Professor Gravano) at a time other than Thursday October 29, 1:10-2:25 p.m. ET.
Bathroom breaks are not allowed, except for true emergencies, which you should communicate to Professor Gravano via the Zoom chat function with a private message directed to the “host.”
Professor Gravano will be answering questions via the Zoom private chat function during the first 30 minutes of the regular time of the exam only (i.e., until 1:40 p.m. ET on Thursday October 29); please use only private messages directed to the “host.”
If you experience any technical difficulties during the regular time of the exam, please contact Professor Gravano via the Zoom chat function with a private message directed to the “host”; Professor Gravano will be connected to Zoom for the duration of the exam. You can also send an email to gravano@cs.columbia.edu during or after the exam.
Finally, please read the following Honor Code (which is also available at https://www.cc-seas.columbia.edu/integrity):
“I affirm that I will not plagiarize, use unauthorized materials, or give or receive illegitimate help on assignments, papers, or examinations. I will also uphold equity and honesty in the evaluation of my work and the work of others. I do so to sustain a community built around this Code of Honor.”
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
If you commit to this Honor Code, please answer “YES” below; otherwise please answer “NO” and email Professor Gravano after the exam is over to kindly explain your answer:
YES NO
Best of luck with the exam!
Q2 Definitions 10 Points
In at most two short sentences each, explain the meaning of the following terms as they relate to database systems:
Q2.1
2 Points
SQL aggregate operators
Q2.2
2 Points
Renaming operator
Q2.3
2 Points
It combines numerical values.
Reassign names to relations and their attributes in RA.
Outer join
2/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
Q2.4
2 Points
Identifying relationship set
Q2.5
2 Points
Assertion
Q3 E/R Diagrams 6 Points
Consider the following E/R diagram, representing students and the courses in which they are enrolled:
For the next 3 items, you will get 2 points for each correct answer, -1 points for each incorrect answer, and 0 points for each answer left blank. Note that the only double line in the diagram connects Students to Enrolled.
3/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
Q3.1
2 Points
According to the diagram, can a course be empty (i.e., not have any students enrolled in it)?
YES
NO
NO ANSWER
Q3.2
2 Points
According to the diagram, can a student be enrolled in no course?
YES
NO
NO ANSWER
Q3.3
2 Points
According to the diagram, can a student be enrolled in the same course in multiple semesters?
YES
NO
NO ANSWER
Q4 Mapping of E/R Diagrams to SQL 12 Points
Consider the same E/R diagram as in Question 3, representing students and the courses in which they are enrolled:
4/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
Consider also the following SQL schema:
CREATE TABLE StudentsEnrolled ( sid INTEGER,
cid INTEGER,
sname CHAR (30),
PRIMARY KEY (sid));
CREATE TABLE Courses ( cid INTEGER,
cname CHAR (30), PRIMARY KEY (cid));
List and briefly explain the four most important problems that you find with this schema, in terms of how well it models the E/R diagram above. Do not base your answer on comparing this schema with other possible schemas. Instead, just compare the schema against the E/R diagram to identify what is not captured from the diagram, etc. in the schema. You will be graded on the importance of the problems that you identify.
Q4.1
3 Points
Problem 1:
Q4.2
3 Points
5/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
Problem 2:
Q4.3
3 Points
Problem 3:
Q4.4
3 Points
Problem 4:
Q5 SQL Query 17 Points
Consider the following database, consisting of two relations, whose schemas are:
CREATE TABLE Employees( ssn CHAR(11),
name CHAR(30),
salary REAL,
PRIMARY KEY (ssn));
CREATE TABLE Manages( employee_ssn CHAR(11), manager_ssn CHAR(11) NOT NULL, PRIMARY KEY (employee_ssn),
6/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
FOREIGN KEY (employee_ssn) REFERENCES Employees(ssn), FOREIGN KEY (manager_ssn) REFERENCES Employees(ssn));
The Manages relation keeps track of the manager (manager_ssn) of each employee (employee_ssn), if any. Note that managers are also regular employees, as indicated in the last line of the CREATE TABLE statement for the Manages table.
Write a SQL query that returns the ssn and name of each manager together with the average salary of the employees that they manage (i.e., for each manager m, return m’s ssn and name, and the average salary of the employees that m manages).
Q6 Relational Algebra Query 15 Points
Consider the relational schema in Question 5, with relations Employees and Manages. We are interested in detecting “cycles” in the management. For simplicity, we will focus on cycles of length exactly two. Write a relational algebra expression that returns the ssn of each employee e such that:
e has employee m as manager, with e = m, and m has employee e as manager.
(Note that your expression will return both e’s ssn and m’s ssn, as separate rows.) The schema of the output of your relational algebra expression must consist of a single attribute named ssn. (The attribute name is important.)
To write relational algebra operators in your answer, you have
three options:
Option 1: Use (LaTeX-style) formatting by enclosing your relational algebra expression inside $$ … $$, as follows:
π (projection): $$\pi$$
σ (selection): $$\sigma$$ ρ (renaming): $$\rho$$ ⋈ (join): $$\bowtie$$
7/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
× (cross product): $$\times$$ ∪ (union): $$\cup$$
∩ (intersection): $$\cap$$
∧ (and): $$\wedge$$
∨ (or): $$\vee$$
You can add a subscript to an operator by using underscore followed by the subscript enclosed in curly braces. For example, you can write
πA (σA=3∧B>4 (R)) as follows: $$\pi_{A}(\sigma_{A=3 \wedge B>4}(R))$$
Option 2: Use plain text, with minimal formatting (please make sure it is fully clear how your answer maps to relational algebra as discussed in class). For example, you can write πA (σA=3∧B>4 (R)) simply as: projection_A(selection_{A=3 and B>4}(R)).
Option 3: You can write your relational algebra expression on your piece of scrap paper and upload a photo:
No files uploaded
Q7 Equivalence of Queries 15 Points
In this problem, you will get 3 points for each correct answer, -1.5 points for each incorrect answer, and 0 points for each answer left blank.
Each item below shows two queries, Q1 and Q2. Answer “YES” if the two queries are equivalent, and “NO” if they are not equivalent. Two queries are equivalent if they always return exactly the same tuples on all databases having the R and S relations as defined below. The names of the attributes in the query results are unimportant for this problem: focus instead on the tuples that the queries return.
All queries refer to a schema containing two relations:
R(A, B, C) where {A, B} is the primary key and {C} is a candidate key S(A, B, C) where {A} is the primary key (and only key)
8/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
You may assume that R and S are union-compatible and that the relations do not contain NULL values, but do not make any other assumptions about the relations.
Q7.1
3 Points
Q1: πA,B (R) ⋈ πA,B (S) Q2: πA,B (R ⋈ S)
Are Q1 and Q2 equivalent?
YES
NO
NO ANSWER
Q7.2
3 Points
Q1: R − S
Q2: R − (R ⋈ S)
Are Q1 and Q2 equivalent?
YES
NO
NO ANSWER
Q7.3
3 Points
Q1: (πA,B (R) × πC (R)) ⋈ R Q2: R
Are Q1 and Q2 equivalent?
9/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688
YES
NO
NO ANSWER
Q7.4
3 Points
Q1:
SELECT MAX(R.A), R.B, R.C FROM R
GROUP BY R.B, R.C
Q2:
SELECT DISTINCT R.A, R.B, R.C FROM R
Are Q1 and Q2 equivalent?
YES
NO
NO ANSWER
Q7.5
3 Points
Q1:
SELECT S.A, AVG(S.B), AVG(S.C) FROM S
GROUP BY S.A
Q2:
SELECT S.A, AVG(S.B), AVG(S.C) FROM S
GROUP BY S.A
HAVING COUNT(*)=1
10/12
12/16/2020 View Submission | Gradescope
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688 11/12
Sample Midterm Exam
STUDENT
Weijie Cai
TOTAL POINTS
– / 75 pts
QUESTION 1
General Instructions for COMS W4111.001 Midterm Exam
QUESTION 2
Definitions
2.1 (no title)
2.2 (no title)
2.3 (no title)
2.4 (no title)
2.5 (no title)
QUESTION 3
E/R Diagrams
3.1 (no title)
3.2 (no title)
3.3 (no title)
UNGRADED
0 pts
10 pts 2 pts
2 pts 2 pts 2 pts 2 pts
6 pts 2 pts
2 pts 2 pts
Are Q1 and Q2 equivalent?
YES
NO
NO ANSWER
12/16/2020 View Submission | Gradescope
QUESTION 4
Mapping of E/R Diagrams to SQL
4.1 (no title)
4.2 (no title)
4.3 (no title)
4.4 (no title)
QUESTION 5
SQL Query
QUESTION 6
Relational Algebra Query
QUESTION 7
Equivalence of Queries
7.1 (no title)
7.2 (no title)
7.3 (no title)
7.4 (no title)
7.5 (no title)
12 pts 3 pts
3 pts 3 pts 3 pts
17 pts
15 pts
15 pts 3 pts
3 pts 3 pts 3 pts 3 pts
https://www.gradescope.com/courses/177736/assignments/780489/submissions/52273688 12/12