relational algebra expression for "is null"

Xtrageik picture Xtrageik · Dec 9, 2013 · Viewed 8.7k times · Source

What is the relational algebra expression of the query below? I couldn't find the expression for "Is Null".

SELECT reader.name
FROM reader LEFT JOIN book_borrow ON reader.cardid = book_borrow.cardid
WHERE book_borrow.cardid Is Null;

Answer

SáT picture SáT · Dec 13, 2013

This task requires a bit of creativity, not a verbatim translation.

What's happening here in this query? First we left join book_borrow on reader. Remember the definition: even if the ON clause matches no rows in the rightmost table, the join will still return a single row such that it contains NULLs in the fields of the right table. Our table looks like this:

reader.name | reader.cardid | book_borrow.cardid | book_borrow.book_id
Alice       | 1             | 1                  | 1
Alice       | 1             | 1                  | 5
Bob         | 2             | 2                  | 5
Charlie     | 3             | NULL               | NULL

We can see that Alice has borrowed two books (of ids 1 and 5), Bob borrowed one (id 5), and Charlie got NULL in his book_borrow fields because he has borrowed none. The query then proceeds to fetch only the rows where book_borrow.cardid is NULL, so the query just says: "get all the people who haven't borrowed any books".

Phrasing the task like this, writing the relational algebra expression is easy:

  • let's make a natural join of reader and book_borrow, that will yield us the unwanted rows, names of the people who borrowed any book.
  • then just subtract these people from the set of all people, and the result is the set of people who haven't borrowed a book.

Here it is, unleashing my Latex:

π(name){ π(name, carddid){Reader} - π(name, cardid){Reader join Book_borrow} }

The morals of the story: even though, as Erwin points out, there's no null in the purest form of relational algebra (since relational algebra builds on first-order logic), we don't always need it to express lack of something; left joins can be expressed by basic operators; left joins were invented to improve the efficiency of the calculation: you can easily see how taking the left join and selecting nulls is a lot more practical.