Question 1

(Source: Stanford open classroom)

Consider a database with the following schema:

Person (name: str, age: int, gender: str)

Frequents (name: str, pizzeria: str)

Eats (name: str, pizza: str)

Serves (pizzeria: str, pizza: str, price: float)

Write relational algebra expressions for the following queries.

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.

d. Find all pizzerias that serve at least one pizza that Amy eats for less than $10.00.

e. Find all pizzerias that are frequented by only females or only males.

f. For each person, find all pizzas the person eats that are not served by any pizzeria the person frequents. Return all such person (name) / pizza pairs.

g. Find the names of all people who frequent only pizzerias serving at least one pizza they eat.

h. Find the names of all people who frequent every pizzeria serving at least one pizza they eat.

i. Find the pizzeria serving the cheapest pepperoni pizza. In the case of ties, return all of the cheapest pepperoni pizzerias.

Solutions

a. πpizzeria(σage<18(Person) ▷◁ Frequents)

b. πname(σgender = ’female’AND (pizza = ’mushroom’ OR pizza = ’pepperoni’)(Person ▷◁ Eats))

c. πname(σgender = ’female’AND pizza = ’mushroom’(Person ▷◁ Eats)) U πname(σgender = ’female’AND pizza = ’pepperoni’(Person ▷◁ Eats))

d. πpizzeria(σname = ’Amy’(Eats) ▷◁ σprice<10(Serves))

e. (πpizzeria(σgender = ’female’(Person) ▷◁ Frequents) − πpizzeria(σgender = ’male’(Person) ▷◁ Frequents)) n(πpizzeria(σgender = ’male’(Person) ▷◁ Frequents) − πpizzeria(σgender = ’female’(Person) ▷◁ Frequents))

f. Eats − πname, pizza(Frequents ▷◁ Serves)

g. πname(Person) − πname(Frequents − πname, pizzeria(Eats ▷◁ Serves))

h. πname(Person) − πname(πname, pizzeria(Eats ▷◁ Serves) − Frequents)

i. πpizzeria(σpizza = ’pepperoni(Serves)) − πpizzeria(σprice>price2(πpizzeria, price(σpizza = ’pepperoni’(Serves)) × ρpizzeria2, price2(πpizzeria, price(σpizza=’pepperoni’(Serves)))))

Question 2

Consider a schema with two relations, R(A, B) and S(B, C), where all values are integers. Make no assumptions about keys. Consider the following three relational algebra expressions:

a. πA,C(R ▷◁ σB=1(S))

b. πA (σB=1 (R)) × πC (σB=1 (S))

c. πA,C(πA (R) × σB=1 (S))

Two of the three expressions are equivalent (i.e., produce the same answer on all databases), while one of them can produce a different answer. Which query can produce a different answer? Give the simplest database instance you can think of where a different answer is produced.

Solution

Query (c) is different.

Question 3

Given the following relations:

Student(ID: int, Name: str, Age: int)

Course(CourseID: int, CourseName: str)

Enrollment(StudentID: int, CourseID: int, Grade: str)

Find the names of students who have taken the course with CourseName ’Mathematics’ and received a grade of ’A’ .

Solution

σCourseName=’Mathematics’ (Course) ▷◁Course.CourseID = Enrollment.CourseID σGrade=’A’(Enrollment) ▷◁Enrollment.StudentID = Student.ID Student

Quesiton 4