Midterm 1 review

Overview

Midterm 1 is next week.

In this lab, the TAs will be guiding you through some practice problems related to the exam.

These problems are NOT comprehensive, so make sure to do a thorough review of all of the relevant material.

In-lab practice problems

ER diagrams and the relational model

1. Imagine that you are designing a database for a club that organizes hikes and other outdoor outings. The following is a partial ER diagram for this database:

   

   1. How could we modify this diagram to capture the following constraints?

      • Every outing is attended by at least one member.

        Use a thick line between Outing and Attends.

      • Every outing goes to exactly one location.

        We need two changes:

        • Add an arrow going into Location (i.e., from Outing to Location), which specifies that every outing goes to at most one location.

        • Use a thick line between Outing and GoesTo, which specifies that each outing goes to at least one location.

        These two constraints combine to specify that every outing goes to exactly one location.

      Here’s what the diagram looks like after all of these changes have been made:

      

   2. Given the constraints specified in part (a):

      • What type of relationship set is Attends: many-to-one, one-to-one, or many-to-many? (Note: If it is many-to-one, don’t forget to include a direction.)

        many-to-many

      • What type of relationship set is GoesTo?

        many-to-one from Outing to Location

   3. Turn the ER diagram into the schema for a relational database. Use as few tables as possible. Underline the primary keys and specify any foreign keys.

      We need one table for each entity set:

      • Member(id, name, dob)
      • Location(id, name, city, state)
      • Outing(name, date, time, loc_id), where loc_id is a foreign key that references the id attribute in Location

      We also need one additional table for the Attends relationship set:

      • Attends(member_id, outing_name, outing_date), where:
        • member_id is a foreign key that references the id attribute in Member
        • the combination (outing_name, outing_date) is a foreign key that references the combination (name, date) in Outing

      Notes:

      • We need a separate table for Attends because it is many-to-many, and thus we can’t capture those relationships in the either of the tables for the connected entity sets.

      • The primary key of Attends must be the union of the primary keys of Member and Outing because the fact that Attends is many-to-many means you need the primary-key attributes of both of the connected entity sets in order to uniquely identify each Attends relationship.

      • We don’t need a separate table for GoesTo because that relationship set is many-to-one from Outing to Location. As a result, we are able to capture those relationships by adding an appropriate foreign key to Outing, as we did above.

SQL

In the coursepack, there are a number of SQL practice problems on pages 121-127.

Relational algebra

How would you solve the following problems using relational algebra instead of SQL?

• problem 4 on page 122 of the coursepack

  Here are three possible solutions:

  π_course (σ_{E.student = M.student AND dept = ‘comp sci’} ((Enrolled E) x (MajorsIn M)))

  or

  π_course (σ_{dept = ‘comp sci’} (Enrolled ⨝ MajorsIn))

  or

  π_course ((Enrolled E) ⨝_{E.student = M.student AND dept = ‘comp sci’} (MajorsIn M))

• problem 5 on page 123 (assuming student names are unique)

  First, get the id numbers of students not enrolled in a course, assigning the relation containing the resulting ids to a variable:

  NonEnrolledIDs ← π_id (Student) - π_student (Enrolled)

  Next, take the natural join of that relation and Student, and project out the names of those students:

  π_name (Student ⨝ NonEnrolledIDs)

• problem 7 on page 124, but instead of producing a count for each student, produce tuples of the form (student id, student name, majoring department). If a student has multiple majors, they should have multiple tuples. If a student has no majors, they should have a single tuple in which the majoring department is NULL.

  In order to include students with no majors, we need a left outer join:

  π_{id, name, dept} (Student ⟕_{id = student} MajorsIn)

Record formats

Imagine that we are working with a Course table that has the following schema:

Course(name VARCHAR(10) PRIMARY KEY, start_time CHAR(8), end_time CHAR(8), room_id CHAR(4))

Consider the following tuple from that table:

('CS 460', '13:25:00', '14:15:00', '0003')

1. If we use the fixed-length record format discussed in lecture, what would the record look like for this tuple? What would its length be? Assume that we’re using one-byte characters.

   CS 460#‐‐‐

   13:25:00

   14:15:00

   0003

   Its length would be 10 + 8 + 8 + 4 = 30 bytes.

2. Now assume that we’re using the third type of variable-length record discussed in lecture, in which each record begins with a header of field offsets. What will the record look like for the above tuple, and what will its length be? In addition to one-byte characters, you should assume that we use two-byte integers for integer metadata like offsets.

   0

   2

   4

   6

   8

   10

   16

   24

   32

   10

   16

   24

   32

   36

   CS 460

   13:25:00

   14:15:00

   0003

   Its length would be 36 bytes because:

   • Each offset is 2 bytes, for a total of 10 bytes. That’s also why the first offset is 10!
   • The values take up 6 + 8 + 8 + 4 = 26 bytes.

There are also extra-practice problems on record formats in Lab 4.

B-trees and B+trees

There are extra-practice problems on these topics in Lab 4.

More practice

The midterm 1 info page includes additional practice problems that you can do on your own.

Last updated on February 27, 2025.