How can I find MAX with relational algebra?

Working with databases, how can I find MAX using relational algebra?

Solution 1:

Assuming you have a relation, A, with a single attribute, 'a' (reducing a more complex relation to this is a simple task in relational algebra, I'm sure you got this far), so now you want to find the maximum value in A.

One way to do it is to find the cross product of A with itself, be sure to rename 'a' so your new relation has attributes with distinct names. for example:

(rename 'a' as 'a1') X (rename 'a' as 'a2')

now select 'a1' < 'a2', the resulting relation will have all values except the maximum. To get the max simply find the difference between your original relation:

(A x A) - (select 'a1' < 'a2') ((rename 'a' as 'a1')(A) x (rename 'a' as 'a2')(A))

Then use the project operator to reduce down to a single column as Tobi Lehman suggests in the comment below.

Writing this in relational algebra notation would be (if I remember correctly). Note the final rename (i.e. ρ) is just to end up with an attribute that has the same name as in the original relation:

ρ_a/a1(π_a1((A x A) - σ_{a1 < a2} (ρ_a1/a(A) x ρ_a2/a(A))))

Solution 2:

Just my two cents as I was trying to solve this today myself.

Lets say we have A = 1,2,3

If you use

A x A - (select 'a1' < 'a2') ((rename 'a' as 'a1')(A) x (rename 'a' as 'a2')(A))

you will not get the single max value rather two columns like 1|1, 2|1,3|2,3|1,3|2,3|3

the way to get just 3 is

project(a)A - project(a1)((select 'a1' < 'a2') ((rename 'a' as 'a1')(A) x (rename 'a' as 'a2')(A)))

At least that is what I had to do in a similar situation.

Hope it helps someone

Solution 3:

lets think we have a relation with an attribute A and values 1,2,3

A

1
2
3

so now..

project A values and rename with A1

A1
1
2
3

again project A values and rename with A2

A2
1
2
3

join this with A2<A1 i.e \join_{A2<A1}
so the - Output schema: (A2 integer, A1 integer)

A2<A1

1|2
1|3
2|3

hear always A2 values will be less than A1 because we join like that(a2<a1)

now project A2 the output is like below

A2
1
2

now diff with original attribute

A diff A2

A
1
2
3

 diff

A2
1
2

Output is 3 maximum value

Solution 4:

I've forgotten most of the relational algebra syntax now. A query just using SELECT, PROJECT, MINUS and RENAME would be

SELECT v1.number
FROM values v1
MINUS
SELECT v1.number
FROM values v1 JOIN values v2 ON v2.number > v1.number

Hopefully you can translate!

Solution 5:

I know this is old, but here is a hand-written formula which might be handy!

Relation A: 1,2,3,4

1. First we want to PROJECT and RENAME relation A
2. We then to a THETA JOIN with the test a1<a2
3. We then PROJECT the result of the relation to give us a single set of values 
   a1: 1,2,3 (not max value since a1<a2)

4. We then apply the difference operator with the original relation so: 
   1,2,3,4 --- 1,2,3 returns 4

   4 is the Max value.