CS 333 Introduction to Databases
Midterm Review
Maria Daltayanni
part of the slides is credited to the Complete Book authors
Outline
• Relational Algebra
• Database Design
• Query Language
2
Outline
• Relational Algebra
• Database Design
• Query Language
3
RA example questions
1) For the following queries:
a) write their RA expression
b) draw their tree
c) write their SQL equivalent
2) For two RA expressions:
a) are they are equivalent?
b) find a counterexample with toy data to prove it
3) For an RA diagram:
a) Find syntax errors and correct them
4
Example: 1) Queries to RA
Consider a database with the following schema:
Person ( name, age, gender )
Frequents ( name, pizzeria )
Eats ( name, pizzeria )
Serves ( pizzeria, pizza, price )
Write relational algebra expressions for the
following queries.
5
Example: 1) Queries to RA
a) Find all pizzerias frequented by at least one
person under the age of 18.
b) Find the names of all females who eat
either mushroom or pepperoni pizza (or both).
c) Find the names of all females who eat both
mushroom and pepperoni pizza.
6
Example: 1) Queries to RA
Draw their RA trees…
7
Example: 1) Queries to RA
SQL equivalents…
a) select pizzeria
from person, frequents
where age < 18;
b) select name
from person, eats
where gender=‘f’ and (pizza = ‘m’ or pizza = ‘p’;
c) (select name from person, eats where gender=‘f’ and pizza=‘p’)
intersect
(select name from person, eats where gender=‘f’ and pizza=‘m’);
8
Example: 2) RA plans equivalent?
Lab 2!!
9
Outline
• Relational Algebra
• Database Design
• Query Language
10
Database Design example questions
1) You are given a DB design problem
a) Design its E/R diagram
i) without or ii) with weak entity sets
b)Translate to the DB relational schema
2)There is one error on a given diagram
a) find the error and
b) correct it.
11
Example: 1) DB design problem
a) E/R diagram for university exams
• Suppose you were to design the DB system for a
university’s exams data:
• course offerings, including course number, year,
semester, section number, time, and classroom
• students, including student id, name, and program
• exams, including exam id, name, place, and time.
• Suppose also that your DB should record the marks
that students get in different exams of different
course offerings.
12
i) Construct an E-R diagram that models exams as
entities, and uses a ternary relationship, for the above
database.
13
ii) Construct an E-R diagram that uses only a binary
relationship between students and course-offerings.

Make sure that only one relationship exists between a particular student and
course-offering pair, yet you can represent the marks that a student gets in
different exams of a course offering.
14
takes
b) Translate to DB relational schema
i)
student(sid, name,program)
c-offerings(courseno, secno, room,
semester, year, time)
exam(eid, time, place, name)
takes(eid, sid, courseno, secno, marks)
15
b) Translate to DB relational schema
ii)
student(sid, name,program)
c-offerings(courseno, secno, room, semester,
year, time)
exam(courseno, secno, exname, time, place)
takes(sid, courseno, secno)
marks(sid, exname)
16
Example 2) E/R Design with errors
• cases of error may include:
• connecting relationships
• wrong many-one types
• decision:
• should we design an entity or an
attribute for a concept,

e.g. phone number
17
Example 2) E/R Design with errors
Decision: should we design an entity or an attribute for a concept
Suppose you want to design a database where you save the data of an
apartments complex. For each tenant, you should save their name,
landline number, apt number, whether the apt has a balcony, the ids
of the garage spots reserved for the particular apt and the type of
garage spot (ev, compact, etc), how long the tenant lives in the apt
Entities in this example:
- tenant(name, landline)
- apartment(nr, has_balcony, garage_id, garage_type)
Relationships:
- lives(tenant_name, apt_nr, years)
18
Example 2) E/R Design with errors
a) What is wrong in this design?
Logically the above example is not correct:
In the above example, an apt is not allowed to have more than one
garage spots assigned, otherwise you would have to enter two rows
for two garage spots
(apt_11, ***, 23, ev)
(apt_11, ***, 24, carpool)
That would violate the primary key constraint (name) of entity set
apartment!
19
Example 2) E/R Design with errors
b) How would you correct it?
Entities:
- tenant(name, landline)
- apartment(nr, has_balcony)
- garage(id, type)
Relationships:
- lives(tenant_name, apt_nr, years)
- has(apt_nr, garage_id)
20
Outline
• Relational Algebra
• Database Design
• Query Language
21
SQL example questions
1) You are given a db schema, some toy data and a
query on it.
a) write an equivalent query without using a
subquery
b) Draw the tables of the intermediate steps of
your query and the original query, in this order:
1. subquery(if any) 2. from, 3. where, 4. select
c) How are they different? Which is better with
regards to space consumption and why? Suppose
your memory can fit tables up to 5 rows each.
22
Example 1) Sub-query
• Schema: 

Beers(name, manf)

Bars(name, city, license)

Drinkers(name, addr, phone) 

Likes (drinker, beer) 

Sells (bar, beer, price) 

Frequents (drinker, bar)
• Query: 

Find beers which Sam likes and are sold for less than $6.
select beer
from likes
where drinker = ‘Sam’ and beer in (
select beer from sells where price < 6)
23
Toy Data
Sells Likes
The_bar Bud 5 Sam Bud
The_bar Corona 6 Sam Corona
Nightlife Amstel 4 Fred Bud
Nightlife Bud 4.5 Fred Amstel
Example 1) Sub-query
select beer
from likes
where drinker = ‘Sam’ and beer in (
select beer from sells where price < 6)
b) Intermediate steps:
1.select beer from sells where price < 6
The_bar Bud 5 Bud

Nightlife Amstel 4 Amstel

Nightlife Bud 4.5
24
Example 1) Sub-query
select beer
from likes
where drinker = ‘Sam’ and beer in (
select beer from sells where price < 6)
b) Intermediate steps:
2.from, 3. where 4. select
Sam Bud 

Sam Corona Bud Sam Bud Bud 

Fred Bud Amstel 

Fred Amstel
25
beer in
Example 1) Sub-query
• Schema: 

Beers(name, manf)

Bars(name, city, license)

Drinkers(name, addr, phone) 

Likes (drinker, beer) 

Sells (bar, beer, price) 

Frequents (drinker, bar)
• a) write an equivalent query without using a subquery 

Find beers which Sam likes and are sold for less than $6.
select beer
from likes, sells
where drinker = ‘Sam’ and price < 6
26
Example 1) Sub-query
select beer
from likes, sells
where drinker = ‘Sam’ and price < 6
b) Intermediate steps:
1.from , 2. where 3. select
The_bar Bud 5 Sam Bud 

The_bar Bud 5 Fred

The_bar Corona 6 Sam

Nightlife Bud 4.5 Sam 

Nightlife Bud 4.5 Fred

Nightlife Amstel 4 Fred
27
Example 1) Sub-query
c) How are they different?
Which is better with regards to space consumption and
execution time and why?
Suppose your memory can fit tables up to 5 rows each.
The query that uses a subquery is preferred, since the
intermediate tables used to reach the final output dot not
exceed 4 rows worst case;
having a join instead of a subquery, gives 6 rows, and there is
no capacity for a table with that size.
Also, it takes longer to compute the results of a join, as
opposed to plain selections and filtering!
28
SQL example questions
2a) You are given a query that includes sorting:
write its SQL syntax
2b) You are given a query that includes
grouping: write its SQL syntax, show the groups
in the intermediate step.
2c) Extra credit: Write the SQL syntax of a query
that sorts by the computed aggregate attribute.
29
Example 2) Sorting and grouping
2a) Find the top 2 pricier beers sold at
Nightlife.
2b) Find all the beers whose average price
does not exceed 5.
2c) Find the top 2 beers that are priced no
more than 5 on average.
30
Example 2) Sorting and grouping
2a) Find the top 2 pricier beers sold at
Nightlife.
select beer, price
from sells
where bar = ‘Nightlife’
order by price desc
limit 5;
31
Example 2) Sorting and grouping
2b) Find all the beers whose average price does
not exceed $4.5 .
select beer
from
( select beer, avg(price) as av
from sells
group by beer
) t
where t.av <= 4.5;
32
Example 2) Sorting and grouping
2c) Extra credit! Find the top 2 beers that are priced no
more than $4.5 on average.
select beer
from
( select beer, avg(price) as av
from sells
group by beer
) t
where t.av <= 4.5
order by t.av desc
limit 2;
33





















































































































































































































































































































学霸联盟