SEN2104 · Week 8 · Midterm Exam

Midterm review: DBMS, ER, relational model, algebra and SQL

A one-page summary of the first seven weeks and mixed midterm questions. Start here the evening before the exam, and go back to the week of any topic where you feel weak.

schemainstancedata independenceACIDentity setweak entitymultivalued attributemapping cardinalitysuperkeycandidate keyforeign keyselectionprojectionnatural joindivisionGROUP BYHAVINGouter joinNOT INNOT EXISTS

With a week to go before the midterm, you want to see all of the first seven weeks one more time. This page collects the core of each topic that shows up as an exam question, in tables, and then tests you with mixed questions. If you get stuck on a question, go back to the week of that topic. The midterm usually has this structure: a few definition and concept questions, an ER design or deriving tables from an ER diagram, a few relational algebra expressions, and mostly SQL writing.

Suggested study order:

First read the summary tables below and mark the lines you do not know.
Keep the tables of the sample database in front of you. All questions are on it.
Solve the questions without looking at the answers, then read the explanation.
The four traps that cost the most points: the natural join equating extra columns, NOT IN and NULL, the WHERE vs HAVING confusion, and the difference between COUNT(*) and COUNT(column).

The sample database

The university database we use all semester. All the questions are solved with this data.

student

stu_id	name	dept_name	tot_cred
S1	Ada	CS	60
S2	Bora	CS	30
S3	Cem	EE	45
S4	Defne	MATH	90
S5	Ece	CS	15
S6	Firat	EE	0
S7	Gizem	NULL	10

instructor

inst_id	name	dept_name	salary
I1	Aksoy	CS	95000
I2	Demir	CS	80000
I3	Kaya	EE	85000
I4	Sahin	MATH	70000
I5	Celik	MATH	72000
I6	Yildiz	BIO	60000

course

course_id	title	dept_name	credits
CS101	Intro to Programming	CS	4
CS201	Data Structures	CS	4
CS305	Databases	CS	3
EE210	Circuits	EE	3
MA101	Calculus	MATH	4
MA202	Linear Algebra	MATH	3
BI100	Biology	BIO	3

takes (stu_id, course_id, grade): S1 CS101 A, S1 CS201 B, S1 CS305 A, S1 MA101 B, S2 CS101 B, S2 CS201 C, S3 EE210 A, S3 MA101 C, S3 CS101 NULL, S4 MA101 A, S4 MA202 A, S4 CS305 B, S5 CS101 F, S7 MA202 B. A total of 14 rows.

department: CS (Galata, 500000), EE (Galata, 350000), MATH (Rumeli, 200000), BIO (Kadikoy, 150000). teaches: I1 CS101, I1 CS305, I2 CS201, I3 EE210, I4 MA101, I5 MA202.

Week 1: DBMS basics

Concept	In one sentence
Schema / instance	The schema is the design and rarely changes. The instance is the rows right now and changes constantly.
Three levels	external (view), logical (conceptual), physical (internal)
Physical data independence	The physical layout (index, file structure) changes, and the logical schema and the application stay the same.
Logical data independence	The logical schema changes (splitting a table), and views protect the application. It is harder.
DDL / DML	CREATE, ALTER, DROP change the structure; SELECT, INSERT, UPDATE, DELETE change the data.
ACID	Atomicity, Consistency, Isolation, Durability

Weeks 2-3: ER model and relational model

Every shape in an ER diagram has a counterpart in relational tables. The question that comes up most often in the midterm is “how many tables come out of this ER diagram, and what are the keys?”

ER element	How it becomes tables
Strong entity	Its own table, its own primary key
Weak entity	Its own table. PK = the PK of the owner entity + the discriminator. FK to the owner.
M:N relationship	A separate table. PK = the combination of the PKs of both sides. Relationship attributes go here.
1:N relationship	No separate table. The PK of the other side is added as an FK to the “N” (many) side.
1:1 relationship	An FK is added to one of the sides (preferably the one with total participation).
Composite attribute	Only the leaf parts become columns: first_name, last_name
Multivalued attribute	A separate table: (owner PK, value). Both together are the PK.
Derived attribute	Usually not stored, computed by a query (age from the date of birth).

Keys:

Key	Definition
Superkey	Any set of columns that distinguishes rows uniquely
Candidate key	A minimal superkey: no column can be dropped
Primary key	The one the designer picks among the candidate keys
Foreign key	Column(s) that reference the PK of another table. It provides referential integrity.

PITFALL · instance data does not prove a key. name is not a key just because the names of the current 6 instructors are different. A key is a rule that holds for all possible instances of the schema. Instance data can only refute: CS appears twice in the instructor table, so dept_name is definitely not a key.

Weeks 4-5: Relational algebra

Operator	Symbol	What it does	Number of rows
Selection	$\sigma_p(R)$	rows that satisfy the condition	at most that of R
Projection	$\Pi_{A}(R)$	requested columns, duplicates removed	at most that of R
Union, difference, intersection	$\cup, -, \cap$	two union-compatible relations	depends on the operation
Cartesian product	$R \times S$	every row with every row	rows of R times rows of S
Rename	$\rho_{x}(R)$	a new name for the relation or columns	same as R
Natural join	$R \bowtie S$	equates all columns with the same name	between 0 and the product
Left outer join	R ⟕ S	unmatched R rows stay with NULL	at least that of R
Division	$R \div S$	those that match all rows of S	at most the number of candidates
Grouping (aggregation)	$_{G}\gamma_{F(A)}(R)$	groups and aggregate functions	number of groups

Two small examples. Students who have taken no course are found with a difference:

$\Pi_{stu\_id}(student) - \Pi_{stu\_id}(takes) = \{S6\}$

So are students who took CS101 but not CS201:

$\Pi_{stu\_id}(\sigma_{course\_id='CS101'}(takes)) - \Pi_{stu\_id}(\sigma_{course\_id='CS201'}(takes)) = \{S3, S5\}$

Those who took CS101 are {S1, S2, S3, S5}, and those who took CS201 are {S1, S2}. The difference is {S3, S5}. EXCEPT in SQL gave the same result.

The natural join trap

When you write student ⋈ takes ⋈ course, you expect “every student, every course they took”. But the student and course tables have the dept_name column in common. The natural join equates that too, and only the courses the student took from their own department remain:

stu_id	name	course_id	dept_name
S1	Ada	CS101	CS
S1	Ada	CS201	CS
S1	Ada	CS305	CS
S2	Bora	CS101	CS
S2	Bora	CS201	CS
S3	Cem	EE210	EE
S4	Defne	MA101	MATH
S4	Defne	MA202	MATH
S5	Ece	CS101	CS

9 of the 14 records remained. Ada’s MA101, Cem’s MA101 and CS101, Defne’s CS305 and Gizem’s record dropped. In SQLite, NATURAL JOIN gave 9 rows and equating the keys with JOIN ... ON gave 14 rows.

Weeks 6-7: SQL

The logical execution order of a SELECT query is different from its written order. Knowing this ends the WHERE/HAVING and alias mistakes:

FROM / JOIN  →  WHERE  →  GROUP BY  →  HAVING  →  SELECT  →  DISTINCT  →  ORDER BY

Topic	Rule
`WHERE` vs `HAVING`	WHERE acts on a single row, before grouping. HAVING acts on the group, on the aggregate.
`COUNT(*)` vs `COUNT(column)`	`COUNT(*)` counts all rows, `COUNT(column)` counts the non-NULL ones. In takes, 14 and 13 (S3’s CS101 grade is NULL).
NULL comparison	`x = NULL` is never TRUE, it is UNKNOWN. Use `IS NULL`.
`NOT IN`	If the subquery returns a NULL, the result is empty.
`EXISTS`	TRUE if the subquery returns at least one row. Not affected by NULL.
Outer join	Use `LEFT JOIN` so that unmatched rows are not lost, and `COUNT(column)` when counting
Set operations	`UNION`, `INTERSECT`, `EXCEPT` remove duplicates. `UNION ALL` does not.
“Every / all”	A double `NOT EXISTS` (there is no division operator in SQL)

Average salary by department, with the sample data:

SELECT dept_name, AVG(salary) FROM instructor GROUP BY dept_name;

BIO  | 60000
CS   | 87500
EE   | 85000
MATH | 71000

When HAVING AVG(salary) > 75000 is added, only CS and EE remain.

PITFALL · NOT IN and a single NULL. If you write WHERE dept_name NOT IN (SELECT dept_name FROM student) for “departments with no students”, the result comes out empty, not BIO. Gizem’s NULL department gets into the subquery and makes every comparison UNKNOWN. Write it with NOT EXISTS or add WHERE dept_name IS NOT NULL to the subquery.

TIP · are you translating the question to algebra or to SQL? First break the sentence into parts: “which table(s)” → FROM and joins, “which condition” → WHERE / σ, “what to show” → SELECT / π, “for each” → GROUP BY / γ, “all of them” → division or a double NOT EXISTS, “none that …” → difference or NOT EXISTS.

Common mistakes

Wrong idea	The truth
No repeats in the instance, so it is a key	An instance can only say “not a key”
A 1:N relationship gets a separate table	An FK is added to the N side, no separate table is needed
The PK of a weak entity is just the discriminator	owner PK + discriminator
A multivalued attribute is kept in one column with commas	A separate table (owner PK, value). 1NF requires this
`student ⋈ takes ⋈ course` gives all records	`dept_name` is equated too: 9 rows, not 14
The number of columns of $R \times S$ is multiplied	The number of rows is multiplied, the number of columns is added
An aggregate condition is written in WHERE	It is written in HAVING
`NOT IN` is always the same as `NOT EXISTS`	If the subquery has a NULL, NOT IN returns empty
`LEFT JOIN` + `COUNT(*)` shows zeros	The NULL row is counted, giving 1. Write `COUNT(column)`

Test yourself

Exam-style questions. Solve them on paper first, then reveal the answer.

Question 1easy

Which ACID property guarantees that concurrently running transactions do not see each other's intermediate (uncommitted) results?

Show answer

Isolation

Isolation: each transaction behaves as if it were running alone. Atomicity is undoing half-done work, consistency is the preservation of constraints, and durability is a COMMITted piece of work surviving a crash.

Question 2easy

In Chen-style ER notation, what does a double ellipse represent?

Derived attribute
Multivalued attribute
Composite attribute
Key attribute

Show answer

Multivalued attribute

A double ellipse means a multivalued attribute, for example an instructor's several phone numbers. A dashed ellipse is derived, an ellipse that branches into sub-ellipses is composite, and an underlined name is a key attribute.

Question 3medium

section is a weak entity set identified by course through the identifying relationship sec_course. Its discriminator is sec_id. What is the primary key of the relation section?

Show answer

(course_id, sec_id)

A weak entity has no key of its own. Its primary key = the primary key of the identifying (owner) entity + the discriminator. That way section 1 of CS101 and section 1 of MA101 are separate rows, but a second section 1 cannot be added for CS101. In SQLite, inserting a second ('CS101', 1) gave a UNIQUE error.

Question 4medium

An ER design has entity sets student, instructor, course; an M:N relationship takes between student and course with attribute grade; a 1:N relationship advisor (an instructor advises many students, a student has at most one advisor); and a multivalued attribute phone of instructor. Using the standard mapping with no redundant tables, how many relations do you get?

Show answer

Three strong entities → 3 tables (student, instructor, course). The M:N takes → a separate table takes(stu_id, course_id, grade). The 1:N advisor needs no separate table: an advisor_id foreign key is added to the N side (student). The multivalued phone → inst_phone(inst_id, phone). Total 3 + 1 + 1 = 5. The schema was built in SQLite and the tables were counted.

Question 5medium

In the current instance of instructor, no two rows have the same name. Can we conclude that name is a candidate key of instructor?

Show answer

An instance cannot prove that something is a key, it can only show that it is not. A key is a rule that holds for all valid instances of the schema. A second 'Demir' may be hired tomorrow. Conversely, for dept_name the instance is enough: CS and MATH each appear twice, so it is definitely not a key (verified in SQLite with GROUP BY).

Question 6easy

student has 7 tuples and 4 attributes; department has 4 tuples and 3 attributes. How many tuples does $student \times department$ have?

Show answer

In a Cartesian product every row is paired with every row: 7 · 4 = 28 rows. The column counts are added (4 + 3 = 7) and the row counts are multiplied. Because dept_name is on both sides, the result has two separate columns, student.dept_name and department.dept_name. SQL CROSS JOIN also gave 28.

Question 7medium

Give the result of $\Pi_{name}(\sigma_{salary > 75000}(instructor))$ .

Show answer

Aksoy, Demir, Kaya

First the selection: the rows with salary above 75000 are I1 Aksoy (95000), I2 Demir (80000), I3 Kaya (85000). Sahin 70000, Celik 72000 and Yildiz 60000 are dropped. Then only the name column is taken. The SQL equivalent SELECT name FROM instructor WHERE salary > 75000 gave the same three names.

Question 8hard

How many tuples does $student \bowtie takes \bowtie course$ (natural joins) return on the sample data?

Show answer

A trap question. student and takes share only stu_id as a common column: 14 rows. But between this result and course the common columns are course_id and dept_name. The natural join equates both, so only the courses the student took from their own department remain: Ada 3 (CS101, CS201, CS305; MA101 is dropped), Bora 2, Cem 1 (EE210), Defne 2 (MA101, MA202; CS305 is dropped), Ece 1. Cem's CS101 and Gizem's (dept_name NULL) course are dropped too. Total 9. If you want all records, equate only the keys with JOIN ... ON (14 rows).

Question 9hard

Write a relational algebra expression for the names of students who have taken every course offered by the CS department, and give the result.

Show answer

Π_name( (Π_{stu_id,course_id}(takes) ÷ Π_course_id(σ_{dept_name='CS'}(course))) ⋈ student ) → Ada

The word "every" means division. The dividend: which student took which course, $\Pi_{stu\_id, course\_id}(takes)$ . The divisor: the CS courses {CS101, CS201, CS305}. Division gives the stu_ids that match all three: only S1. Bora did not take CS305, and Ece did not take CS201 and CS305. Then we join with student and take the name: Ada. In SQL the same query is written with a double NOT EXISTS.

Question 10medium

Write an SQL query that lists each department name and its average instructor salary, but only for departments whose average salary exceeds 75000. Give the result.

Show answer

SELECT dept_name, AVG(salary) FROM instructor GROUP BY dept_name HAVING AVG(salary) > 75000; → (CS, 87500), (EE, 85000)

Groups: CS {95000, 80000} avg. 87500; EE {85000} avg. 85000; MATH {70000, 72000} avg. 71000; BIO {60000} avg. 60000. A condition on an aggregate function is written in HAVING, not in WHERE, because WHERE is applied to individual rows before grouping. Those above 75000 are CS and EE.

Question 11hard

What does the following query return on the sample data?

SELECT dept_name
FROM department
WHERE dept_name NOT IN (SELECT dept_name FROM student);

Show answer

Empty result (no rows)

The expected answer looks like BIO, because the BIO department has no students. But the subquery also returns Gizem's NULL. The expression 'BIO' NOT IN ('CS','EE','MATH',NULL) contains the comparison 'BIO' <> NULL, which is UNKNOWN. With an UNKNOWN in an AND chain the result is never TRUE, so no row comes back. Fix: add WHERE dept_name IS NOT NULL to the subquery or use NOT EXISTS. Both returned BIO in SQLite.

Question 12medium

Write an SQL query that lists every student's name with the number of courses they have taken, including students who have taken none. Give the result.

Show answer

SELECT s.name, COUNT(t.course_id) FROM student s LEFT JOIN takes t ON s.stu_id = t.stu_id GROUP BY s.stu_id, s.name; → Ada 4, Bora 2, Cem 3, Defne 3, Ece 1, Firat 0, Gizem 1

An inner join loses Firat, who has taken no course. LEFT JOIN keeps him with NULLs. When counting, you must use COUNT(t.course_id): it does not count NULL, so Firat comes out as 0. If you had written COUNT(*), Firat's NULL row would be counted too and he would show 1 (tried in SQLite). Adding s.stu_id to the grouping is a good habit to tell apart two students with the same name.

Verification: All result tables and answers were computed with verify/SEN2104/08.mjs: SQL queries ran on node:sqlite (SQLite 3.53), relational algebra expressions ran with the JS set operations in lib.mjs (sigma, pi, njoin, divide, minus) and were compared with their SQL equivalents. The ER mapping was built as tables in SQLite and its constraints were tried.

Review card

schema = design, instance = the data right now. Physical independence: index; logical: splitting a table + view ACID: Atomicity (all/nothing), Consistency, Isolation (intermediate state invisible), Durability (a commit stays) ER: double ellipse = multivalued, dashed = derived, double rectangle = weak entity, double diamond = identifying rel. Weak entity PK = owner PK + discriminator M:N → separate table 1:N → FK on the N side Multivalued → separate table (owner PK, value) Composite → sub-parts as separate columns An instance does not prove a key, it only refutes it R × S: rows multiply, columns add σ filters rows, π selects columns (removes duplicates) Natural join equates ALL columns with a common name (student ⋈ takes ⋈ course → dept_name trap) "every / all" → ÷ (division) or double NOT EXISTS WHERE acts on rows before grouping, HAVING on aggregates after the group NOT IN (... NULL ...) → empty result. Use NOT EXISTS or IS NOT NULL LEFT JOIN + COUNT(column) → zeros are visible; COUNT(*) counts the NULL row too