|< < 23 > >|

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.

|< < 23 > >|