��
Database Management Systems
Assignment 1
Relational Algebra
Question 1
Consider the bank database of the following instance
Branch
branch name
branch city
Newman
Lasalle
Dollard
Lasalle
Senkus
Lasalle
Angrignon
Lasalle
Monk
Emard
Briand
Emard
Sherbrooke
Montreal
Peel
Montreal
St. Catherine
Montreal
St. Laurent
Montreal
St. Martin
Laval
Belanger
Laval
Pelletier
Brossard
Naples
Brossard
Milan
Brossard
�������
�Account
Depositor
a number
b name
balance �
c name
a number
A-001
Senkus
100 �
Albert
A-001
A-002
Senkus
150 �
Beth
A-002
A-003
Briand
120 �
Charles
A-003
A-004
Briand
�60
Albert
A-004
A-005
Peel
200 �
Frank
A-005
A-006
Belanger
240 �
Goofy
A-006
A-007
Belanger
190 �
Nour
A-007
A-008
Naples
�55
Michael
A-008
A-009
Milan
�80
Quentin
A-009
A-010
Dollard
�10
Henry
A-010
A-011
Dollard
300 �
Ivy
A-011
A-012
Newman
210 �
Nour
A-012
A-013
Newman
260 �
Robin
A-013
A-014
Newman
510 �
Ellie
A-014
A-015
Monk
�40
Charles
A-015
A-016
St. Martin
280 �
Jenni
A-016
A-017
Belanger
310 �
Kim
A-017
A-018
Pelletier
�66
Daisy
A-018
Borrower
c name
l number
Lori
L-001
Charles
L-002
Frank
L-003
Michael
L-004
Patrick
L-005
O’Neil
L-006
Beth
L-007
Charles
L-008
Jenni
L-009
Quentin
L-010
Robin
L-011
Albert
L-012
Goofy
L-013
Frank
L-014
Ellie
L-015
Albert
L-016
Jenni
L-017
Patrick
L-018
Calculate the following relational algebra expressions. Show the resluts (includ- ing the schema and the table instance) after each step.
a. πc name (Depositor) – πc name (Borrower)
�
b. πc name (σb name=“Briand// (Account) xK Depositor)
c. c nameϑsum(amount)(Loan xK σc name=“Charles// (Borrower))
d. πc name,b name (Account xK Depositor)÷ (πb name (σb city=“Emard// (Branch)))
Question 2
Consider a database with the following schema:
Students(stu id, stu name, gender, age, gpa, pg name) // stu id is a key Program(pg name,division) // pg name is a key Courses(cs id, cs name, pg name, credit) // cs id is a key
Take(stu id, cs id, score) // [stu id, cs id] is a key Write relational algebra expressions for the following nine queries.
a. Find the names of courses taken by at least one student whose gpa is 4.0.
b. Find the names of all females who have taken the “Database” course or the “Algorithm” course. Databases and Algorithm are course names.
c. Find the names of all females who have taken both of the “Database” course and the “Algorithm” course.
d. Find all programs (name) which offer some courses that Goliath (student name) has taken.
e. Find all courses that are taken by only females or only males.
f. For each student, find all programs such that the student hasn’t taken any course offered by the program. Return all such student (name) / program pairs.
g. Find the names of students who only take the courses offered by his/her program.
h. Find the names of students who have taken at least one course from every program.
i. Assume failing score for a course is below 50. Find the names of students who have failed more courses than all other students. In the case of ties, return all such students.
Question 3
Two more exotic relational algebra operators we didn’t cover are the semijoin and antijoin. Semijoin is the same as natural join, except only attributes of the first relation are returned in the result. For example, if we have relations Student(ID, name) and Enrolled(ID, course), and not all students are enrolled
3
�
in courses, then the query Student K Enrolled returns the ID and name of all students who are enrolled in at least one course. In the general case, E1 K E2 returns all tuples in the result of expression E1 such that there is at least one tuple in the result of E2 with matching values for the shared attributes. Antijoin is the converse: E1 B E2 retuns all tuples in the result of expression E1 such that there are no tuples in the result of E2 with matching values for the shared attributes. For example, the query StudentBEnrolled returns the ID and name of all students who are not enrolled in any courses.
Like some other relational operators (e.g., intersection, natural join), semijoin and antijoin are abbreviations – they can be defined in terms of other relational operators. Define E1 K E2 in terms of other relational operators. That is, give an equation E1 K E2 =??, where ?? on the right-hand side is a relational algebra expression that doesn’t use semijoin. Similarly, give an equation E1 B E2 =??, where ?? on the right-hand side is a relational algebra expression that doesn’t use antijoin.