|< < 27 > >|

Rearranging Relational Algebra Expressions

What are the titles of albums by The Detroit Cobras?


project(
    select(
        join(Artist, Album),
        name == 'The Detroit Cobras')
    [title])

How fast is this?

Suppose there are N Artists and M Albums.

Back-of-the-envelope calculation:

N × M pairs of rows to consider in computing the join.
Output of join has M rows.
As each output row is generated, check select condition.
If true, project on name.

So the time is O(N × M).

Could be reduced to O(M) if both tables are stored in order of artist_id. Which is still pretty bad.

|< < 27 > >|