[ExamVT13] Block 5: Relational Algebra

[Niklas Broberg]

============================================

Schema reposted from previous block for convenience:

Tracks(trackId, title, length)

 length > 0

Artists(artistId, name)

Albums(albumId, title, yearReleased)

TracksOnAlbum(album, trackNr, track)

 album -> Albums.albumId

 track -> Tracks.trackId

 (album, track) unique

 trackNr > 0

Participates(track, artist)

 track -> Tracks.trackId

 artist -> Artists.artistId

Users(username, email, name)

 email unique

Playlists(user, playlistName)

 user -> Users.username

InList(user, playlist, number, track)

 (user, playlist) -> Playlists.(user, playlistName)

 track -> Tracks.trackId

PlayLog(user, time, track)

 user -> Users.username

 track -> Tracks.trackId

 (user, time) unique

Use the relations for the music site from [above] when answering the following problems.

============================================

5A (3p)

(i) (1p)

What does the following relational algebra expression compute (answer in plain text):

tau[x](pi[playlistName,COUNT( *) -> x](sigma[playlistName=playlist](Playlists × InList)))

(ii) (2p)

Translate the following relational algebra expression(s) to corresponding SQL:

let R1 = gamma[user,track,COUNT( *) -> nrTimes](PlayLog)

sigma[ avgNrTimes>=10](gamma[track,AVG(nrTimes) -> avgNrTimes](R1))

(Check original exam on the course webpage for properly formatted versions.)

============================================

5B (4p)

Translate the following SQL query to relational algebra:

SELECT album, MAX(trackNr) AS nrOfTracks, SUM(length) AS totalLength

FROM Albums, TracksOnAlbum, Tracks

WHERE albumId = album AND trackId = track

GROUP BY albumId

ORDER BY totalLength DESC;

============================================

5C (6p)

Write a relational algebra expression that lists the artist(s) appearing in the highest number

of distinct playlists. In case of a tie for highest number of different playlists, list all such

artists.

============================================

[Niklas Broberg]

Correct answers:

 

============================================

5A (3p)

(i) (1p)

What does the following relational algebra expression compute (answer in plain text):

tau[x](gamma[playlistName,COUNT( *) -> x](sigma[playlistName=playlist](Playlists × InList)))

First, there's a typo in the transcription from the exam paper: it should be a gamma, not a pi. It is printed correctly on the actual exam. I've fixed it above.

The selection (sigma) simply gives the join condition between Playlists and InList, which pairs every track in a list with the playlist they are on. Notably, this removes any empty playlists, i.e. those with no tracks in InList (if we wanted those too, we would have needed an outer join). The gamma groups on playlistName, and counts the rows in each group - i.e. the number of tracks on each (non-empty) list. Finally we order them (tau) in ascending order, i.e. shortest list first.

 

(ii) (2p)

Translate the following relational algebra expression(s) to corresponding SQL:

let R1 = gamma[user,track,COUNT( *) -> nrTimes](PlayLog)

sigma[ avgNrTimes>=10](gamma[track,AVG(nrTimes) -> avgNrTimes](R1))

WITH

  R1 AS (

    SELECT user, track, COUNT(*) AS nrTimes)

    FROM PlayLog

    GROUP BY user, track)

SELECT track, AVG(nrTimes) AS avgNrTimes

FROM R1

GROUP BY track

HAVING avgNrTimes>=10;

 

5B (4p)

Translate the following SQL query to relational algebra:

SELECT album, MAX(trackNr) AS nrOfTracks, SUM(length) AS totalLength

FROM Albums, TracksOnAlbum, Tracks

WHERE albumId = album AND trackId = track

GROUP BY albumId

ORDER BY totalLength DESC;

Here there's a typo on the actual exam paper. The query as printed is not valid - the 'albumId' in the GROUP BY clause must match the 'album' in the SELECT clause. It doesn't help that we equate them in the WHERE clause. We allowed any version when grading.

tau[-totalLength]

 (gamma[album, MAX(trackNr) -> nrOfTracks, SUM(length) -> totalLength]

   (sigma[albumId=album & trackId=track]

    (Albums x TracksOnAlbum x Tracks)))

 

============================================

5C (6p)

Write a relational algebra expression that lists the artist(s) appearing in the highest number

of distinct playlists. In case of a tie for highest number of different playlists, list all such

artists.

let R1 = gamma[artist, COUNT(DISTINCT playlistName) -> x](sigma[Participates.track=InList.track](Participates x InList))

    R2 = pi[MAX(x)](R1)

pi[artist](sigma[x = R2](R1))