CS2102 Tutorial #1: Relational Model & Relational Algebra Solution

Tutorial #1: Relational Model & Relational Algebra Week 3
1 Discussions
The following questions are to be discussed during tutorial. All answers will be released with explanation.
1. (Superkey) Consider the following relation instance r of the relational schema R(A,B,C,D).
R
A B C D
0 0 0 1
2 1 2 0
1 1 2 0
0 0 1 2
(a) Assuming that r is a valid relation instance of R, write down all the possible superkeys of R.
(b) Additionally, suppose that it is also known that {A,C} is definitely a superkey of R. Based on the additional information, write down all the possible candidate keys of R. (c) Which of these (if any) is likely be the candidate key of R?
2. (Foreign Key) Consider a relational database consisting of two relations with schema R(A,B) and S(W,X,Y,Z) such that A is the primary key of R and W is the primary key of S (for future use, we denote this with R(A,B) and S(W,X,Y,Z) where the attributes being underlined are parts of primary key).
Let r and s be the current instances of R and S, respectively, as shown below.
R S
A B W X Y Z
3
2
1
0 0
1
1
0 0
1
2
3 4
NULL
1
0 0
2
2
1 NULL
NULL
NULL
NULL
1
Based on the current database instance above, write down all the possible foreign keys in S that refer to attribute A in R.
3. (Equivalent) Recap that wwo queries Q1 and Q2 on a relational database with schema R are defined to be (strongly) equivalent (denoted by Q1 ⌘ Q2) if for every valid instance r of R, either:
• both Q1 and Q2 queries produces error, or
• both Q1 and Q2 always compute the same results on r
Consider a database with the following relational schema: R(A,C), S(A,D), and T(X,Y ), with primary key attributes underlined. Assume all the attributes have integer domain. For each of the following pairs of queries Q1 and Q2, state whether or not Q1 ⌘ Q2.
Q1 Q2
(i) ⇡[A]( [A<10](R)) [A<10](⇡[A](R))
(ii) ⇡[A]( [C<10](R)) [C<10](⇡[A](R))
(iii) ⇡[D,Y ](S ⇥ T) ⇡[D](S) ⇥⇡[Y ](T)
(iv) ⇡[D,Y ](S T) ⇡[D,Y ](T S)
⇥ ⇥
4. (Algebra) Consider the following schema:
Relation Description
All the pizzas of interest.
The name and location of each customer.
The name and location of each restaurant.
Recipes(pizza,ingredients)

The ingredients used in each pizza.
Pizzas sold by restaurants and the prices.
Pizzas that customers like.
Additionally, we have the following foreign key constraints on the database schema:
• (Recipes.pizza) (Pizzas.pizza)
• (Sells.rname) (Restaurants.rname)
• (Sells.pizza) (Pizzas.pizza)
• (Likes.cname) (Customers.cname)
• (Likes.pizza) (Pizzas.pizza)
Answer each of the following queries using relational algebra. For those interested, you can try writing the relational algebra query on https://www.comp.nus.edu.sg/~cs2102/Tools/RelAlgebra/. The syntax can be found in https://www.comp.nus.edu.sg/~cs2102/Tools/RelAlgebra/help. html.
(i) Find all pizzas that Moe likes but is not liked by Lisa .
(ii) Find all customer-restaurant pairs (C,R) where C and R both located in the same area and C likes some pizza that is sold by R.
(iii) Suppose the relation Likes contains all information about all customers. In other words, if the pair (cname,pizza) is not in the relation Likes, it means that the customer cname dislikes the pizza pizza. Write a relational algebra expression to find for all customers, the pizza that they dislike. The result should be of the form (cname,pizza).
2 Challenge
The answers to the following questions is given without explanation. Please discuss them on Canvas.
1. (Equivalent) Recap that wwo queries Q1 and Q2 on a relational database with schema R are defined to be (strongly) equivalent (denoted by Q1 ⌘ Q2) if for every valid instance r of R, either:
• both Q1 and Q2 queries produces error, or
• both Q1 and Q2 always compute the same results on r
Consider a database with the following relational schema: R(A,C), S(A,D), and T(X,Y ), with primary key attributes underlined. Assume all the attributes have integer domain. For each of the following pairs of queries Q1 and Q2, state whether or not Q1 ⌘ Q2.
Q1 Q2
(i) (R ⇥⇡[D](S)) ⇥ T R ⇥ (⇡[D](S) ⇥ T)
(ii) ⇡[A](R [ S) ⇡[A](R) [⇡[A](S)
(iii) ⇡[A](R S) ⇡[A](R) ⇡[A](S)
2. (Algebra) Consider the following schema:
Relation Description


All the pizzas of interest.
The name and location of each customer.
The name and location of each restaurant.
The ingredients used in each pizza.
Pizzas sold by restaurants and the prices.
Likes(cname,pizza) Pizzas that customers like.
Additionally, we have the following foreign key constraints on the database schema:
• (Recipes.pizza) (Pizzas.pizza)
• (Sells.rname) (Restaurants.rname)
• (Sells.pizza) (Pizzas.pizza)
• (Likes.cname) (Customers.cname)
• (Likes.pizza) (Pizzas.pizza)
Answer each of the following queries using relational algebra. For those interested, you can try writing the relational algebra query on https://www.comp.nus.edu.sg/~cs2102/Tools/RelAlgebra/. The syntax can be found in https://www.comp.nus.edu.sg/~cs2102/Tools/RelAlgebra/help. html.
(i) For each restaurant, find the price of the most expensive pizzas sold by that restaurant. Exclude restaurants that do not sell any pizza.
(ii) Find all customer-pizza pairs (C,P) where the pizza P sold by some restaurant that is located in the same area as that of the customer C. Include customers whose associated set of pizzas is empty.
3. (Understanding RA) Consider the following relational algebra query expressed on the database schema in Question 4.
R1 := ⇡[pizza]( [cname=’Maggie’](Likes)) R2 := ⇡[rname](Sells) ⇥ R1
R3 := ⇡[rname](R2 ⇡[rname,pizza](Sells))
R4 := ⇡[rname](Sells) R3
R5 := ⇡[pizza]( [cname=’Ralph’](Likes))
R6 := ⇡[rname]( [pizza5=pizza]((Sells⇥⇢[pizza5 pizza](R5))))
R7 := R4 R6
For each of the relational algebra expression Ri, write down a concise English sentence to precisely describe the information retrieved by Ri.