Post Format

Finding a Maximum Value with Relational Algebra

I finally coded the correct answer to my maximum value problem in relational algebra. There are plenty of answers out there (see stack overflowcodeblow, stack overflow again, …) but my brain didn’t want to accept that this solution worked. It helps me to visualize what’s happening.

Say we have this simple relation of letters and numbers:

Letter Number
A 1
B 2
C 3
D 4

If we want to identify the maximum value in the number column, we can start by identifying what numbers aren’t the maximum. A number isn’t the maximum if it is less than another number in the relation. In other words, we need to find the theta-join of our relation and itself for Number1 < Number2. Here is the cross-product of the relation and itself (with renamed attributes):

Letter1 Number1 Letter2 Number2
A 1 A 1
A 1 B 2
A 1 C 3
A 1 D 4
B 2 A 1
B 2 B 2
B 2 C 3
B 2 D 4
C 3 A 1
C 3 B 2
C 3 C 3
C 3 D 4
D 4 A 1
D 4 B 2
D 4 C 3
D 4 D 4

 

If we only take the rows where Number1 < Number2 (i.e. a theta-join), we will get the values 1, 2, and 3 (but not 4) for the Number1 attribute. These are all the values that cannot be the maximum:

Letter1 Number1 Letter2 Number2
A 1 B 2
A 1 C 3
A 1 D 4
B 2 C 3
B 2 D 4
C 3 D 4

 

This is where my brain started to object. What about the row A1A1? it insisted. If you subtract this relation from the cross-product relation, that row will still be there! And while that’s true, we can solve that by looking only at the Number1 values, not at the entire rows.

So to get the maximum, we just have to take a projection of Number1 from the theta-join relation above and subtract it from the projection of Number from the original relation. The result:

Number
4

 

4, our maximum.

Advertisements

Posted by

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