Problem Set 1

Part I due by 11:59 p.m. on Tuesday, September 15, 2026
Part II due by 11:59 p.m. on Tuesday, September 22, 2026

Preliminaries

If you haven’t already done so, you should complete Lab 0 before beginning this assignment.

In your work on this assignment, make sure to abide by the collaboration policies of the course. Unless they are labeled pair-optional, the problems in this assignment are individual-only problems that you must complete on your own.

If you have questions, please come to office hours, post them on Piazza, or email cs460-staff@cs.bu.edu.

Make sure to submit your work on Gradescope, following the procedures found at the end of Part I and Part II.

---

Part I

30 points total

Creating the necessary folder

1. If you haven’t already created a folder named cs460 for your work in this course, follow these instructions to do so.

2. Then create a subfolder called ps1 within your cs460 folder, and put all of the files for this assignment in that folder.

Recommended: Configure your browser so that it asks you where each downloaded file should be saved. Both Chrome and Edge allow you to do this as follows:

• Click the menu button (which consists of three dots) in the upper-right corner.
• Choose the Settings option from the menu.
• Choose Downloads from the left-hand navigation bar in Settings.
• Turn on the option for Ask where to save each file before downloading.

Creating the necessary file

The problems from Part I will all be completed in a single PDF file. To create it, you should do the following:

1. Make sure you are signed into your BU Google Drive account. Note that signing into BU Google Mail should accomplish the same thing.

2. Access the template that we have created by clicking on this link.

3. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

4. Select File->Rename, and change the name of the file to ps1_partI.

5. Add your work for the problems from Part I to this file.

6. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file in your ps1 folder. The resulting PDF file (ps1_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: ER diagram basics

10 points total

Before going any further, make sure to follow the instructions above to create your own copy of the Google Drive document that you should use for Part I of the assignment.

The ER diagram shown below is part of the design of a database that includes information about actors and the parts that they perform in plays, musicals, movies and TV shows. Each actor has a name and a unique id. Each part can be uniquely identified by the combination of the id of the corresponding show and the name of the role, and the database also keeps track of how many lines of dialogue that each part has (the attribute called line count).

In the above version of the ER diagram, there are no constraints on the relationships between actors and parts.

In the ps1_partI template that we’ve provided on Google Drive (see above), we’ve included the beginnings of three separate versions of this ER diagram.

1. (2 points) Edit the first version of the diagram, adding the connections needed to create an ER diagram whose only constraint is that every actor performs at most one (i.e., 0 or 1) part. To do so, you should:

   • Click on the diagam and then click the Edit link that appears below the diagram.

   • From the collection of eight connectors that we have provided below the diagram, select the appropriate connectors and use them to connect the two entity sets to the relationship set. Adjust the connectors as needed to make the connections.

   • Click the Save & Close button.

2. (2 points) Edit the second version of the diagram, adding the connections needed to create an ER diagram whose only constraint is that every actor performs exactly one part.

3. (2 points) Edit the third version of the diagram, adding the connections needed to create an ER diagram whose only constraints are (1) that every actor performs at least one part, and (2) that every part is performed by at most one actor.

4. (4 points) Consider your answer to part 1—the ER diagram for the situation in which every actor performs at most one part.

   Is it possible to convert that diagram into a relational schema that has only two tables/relations, or would three be needed? Explain your answer briefly, and then specify the schema of the two or three tables.

   • Give the schema of each table in the form relation_name(attr_name1, attr_name2, ...).

   • Indicate the primary-key attribute(s) of each relation by underlining them.

Problem 2: Database design

12 points total

The ER diagram shown below in Figure 2-1 represents information that is to be stored in a database for a literary agency—i.e., a company that provides agents for authors.

Figure 2-1:

Note that the diagram includes relationship sets for three types of relationships:

• Authors write books (or, expressed in the opposite direction, books are written by authors), and they receive roylaties for each book that they write.
• Authors are managed by agents (or: agents manage authors).
• Books are published by publishers (or: publishers publish books).

Answer the following questions about this diagram:

1. (2 points) At least one of the relationship sets captures a many-to-one relationship. Which one(s)? In your answer, you should specify the direction of each such relationship (e.g., ________ is many-to-one from _________ to ___________).

2. (4 points) Fill in the table that we have provided to describe, for each relationship set in the diagram, any constraints on the relationships associated with that relationship set. Use words that describe the problem domain (e.g., Each course meets in at most one room...) rather than technical terminology.

3. (6 points) Transform this diagram into a relational schema by following the procedure discussed in lecture and fill in the table that we have provided. Here are some additional guidelines:

   • When appropriate, you should combine relations as discussed in lecture.

   • In the first column of the table, give the schema of each relation in the form relation_name(attr_name1, attr_name2, ...). Feel free to rename attributes as needed to make them easier to understand. However, if you do so, make sure that you do not use a period or space in an attribute name. Rather, you should use a combination of letters and underscore (_) characters.

   • Indicate the primary-key attribute(s) of each relation by underlining them.

   • If a relation has one or more foreign-key attributes, specify them in the second column of the table, and specify which attribute each foreign key refers to. For example, if you were working with the MajorsIn relation from the university database covered in lecture, its foreign keys would be specified as follows:

     • student, which refers to Student.id
     • department, which refers to Department.name

Problem 3: Combining relations using relational algebra

8 points total; 2 pts. each part

We will finish the material needed for this problem in lecture on Friday, September 11.

Relation R has attributes a, b and c. Relation S has attributes a, b, and d. You are given the following instances of these relations:

Relation R

a	b	c
1	2	3
3	4	3
7	6	5

Relation S

a	b	d
2	3	1
3	4	9
7	6	4

For each of the following questions, use the Insert->Table menu option in Google Drive to insert an appropriately sized table for the answer, and then fill in the cells of the table with the correct values.

Make sure that each table includes a header row with appropriate column names.

1. What is the Cartesian product of R and S?
2. What is the natural join of R and S?
3. What is the left outer join of R and S?
4. What is the right outer join of R and S?

Submitting your work for Part I

1. Once you have completed Part I in Google Drive, choose File->Download->PDF document, and save the resulting file (ps1_partI.pdf) in your ps1 folder.

2. Login to Gradescope by clicking the link in the left-hand navigation bar. When logging in, make sure that you use the School Credentials option and select Boston University.

3. Once you are in logged in, click on the box for CS 460. (If you don’t see that box, email cs460-staff@bu.edu ASAP and ask to be added to the course on Gradescope. If the deadline is fast approaching and you don’t have access to CS 460 on Gradescope, email your PDF to cs460-staff@cs.bu.edu before the deadline.)

4. Click on the name PS 1: Part I in the list of assignments. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

5. Choose the Submit PDF option, and then click the Select PDF button and find the ps1_partI.pdf that you created in step 1. Then click the Upload PDF button.

6. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

7. Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

8. You can use the Resubmit button at the bottom of the page to resubmit your work as many times as needed before the final deadline.

---

Part II: Coming soon!

70 points total

Last updated on September 9, 2026.

