Post Format

Using Relational Algebra to Select Based on Query Results

The title of this post is a bit misleading, but it just goes to show how important it is to ask the right question. The other day, I was working on a challenge homework problem that basically proposed this challenge:

Use relational algebra to find all schools that offer every class Spanish majors want to take.

(The actual problem was different, but I don’t want future students to find the answer just by searching for the homework question!) Assume we have two relations:

  • Relation S: A list of schools and the classes they offer.
  • Relation C: A list of students, their majors, and the classes they want to take.

At first, all I could imagine was that I needed to find every class Spanish majors wanted to take, and then use the results of that query to iterate over the list of schools. I couldn’t think of a different way to approach the problem … until I thought back to the approach I used in the maximum value problem I discussed yesterday.

Finally, I came up with this solution:

  1. Select the students from relation C who are Spanish majors.
  2. Use a projection to pull out just the classes those students want to take.
  3. Create a new relation, A, by doing a natural-join of this projection and relation S. (These are all the schools that offer at least one of the desired classes, and the classes that they offer.)
  4. Now create another new relation, B, by doing a cross-product of the projection of the names from relation A with the projection of the classes from relation C. (These are all the schools that offer at least one of the desired classes, combined with all the desired classes. We could call this the “wishful thinking” relation, because it reflects all the possibilities but not reality.)
  5. Subtract relation A from relation B, leaving a relation (D) of the schools that offer at least one desired class but not all desired classes.
  6. Finally, subtract relation D from relation A and project the school names — these are the schools that offer all desired classes.

The basic idea is fairly simple: You need to start by finding all the values that don’t fit the criteria, and then you can subtract those to find the value(s) you are looking for. I’m not sure if this is the most concise answer to the problem, but it works!

Advertisements

Posted by

Happiness Engineer for Automattic, the company behind WordPress.com. Linguaphile and Translator. Tester.