I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause.

Example: I have:

  • a table with books (listing the title, year published and ID),
  • a table with authors (listing their name and ID),
  • a table which lists what author wrote what book (through a tuple of the IDs mentioned before).

How could I, in relational algebra, get "All the authors that have published at least one book per year between 2008 and 2010"?

I have figured this so far. At step "b", the Natural join is used since both tables have PublicationID in common. Thus, the resulting table is |PublicationID|AuthorID|Year|. So I'm simply missing the step "c", where I don't understand how to gather a sub-set of the authors that published at least one book per year between 2008 and 2010.

$ a \leftarrow \pi_{PublicationID,Year} (Publication)$

$ b \leftarrow a \bowtie AuthorPublication $

$ c \leftarrow \sigma_{something} $

  • 1
    $\begingroup$ A query like $A.\exists\, T,Y,I,J \; \text{book}(T,Y,I),\text{author}(N,J),\text{authorbook}(J,I),{\lt}(Y,2011),{\lt}(2007,Y)$ should work to return a multiset of author names, using Chandra and Merlin's notation from their 1977 paper. $\endgroup$ May 22, 2013 at 22:42
  • $\begingroup$ @AndrásSalamon Thanks! Unfortunately I was looking for a more "classical" notation (using projections, selections and joins). $\endgroup$
    – Balaam
    May 23, 2013 at 5:58
  • $\begingroup$ Check the definition of natural join. Are there any other attributes common to two relations ? $\endgroup$ May 23, 2013 at 9:00
  • $\begingroup$ @AndrásSalamon Indeed, that is a good idea. A friend gave me a possible solution, I shall edit my post with it. $\endgroup$
    – Balaam
    May 23, 2013 at 10:32
  • $\begingroup$ The FOL answer is not correct as it returns authors who wrote at least one book between 2007 and 2011, not at least a book per year $\endgroup$
    – Romuald
    May 23, 2013 at 12:34

2 Answers 2


A first hint toward a solution is to think about "what's the result of a natural join between $Author$, $Publication$ and $AuthorPublication$?" The answer is "the universal relation" $R(BookID,AuthorID,Title,Year,Name)$ describing who wrote a book and when. Note that a book without any author or an author without any book written won't appear in $R$. So an author in $R$ as written at least one book. The following query gives the authors who wrote at least a book in year 2008: $$ \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2008 = year)}(Publication))$$

For the final answer, compute the intersection of this query with its variants: $$ \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2008 = year)}(Publication)) \cap \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2009 = year)}(Publication)) \cap \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2010 = year)}(Publication))$$

You may provide other equivalent answers with outer $Author \Join$.

  • $\begingroup$ This answer does seem correct, thanks! But for curiosity's sake, is my EDIT2 answer any good? It's another way of doing it no? Or am I totally wrong? $\endgroup$
    – Balaam
    May 23, 2013 at 15:13
  • $\begingroup$ It looks like, but it's a little bit contrived IMHO : Mix2 is (almost) a natural join written from product and selection (almost because redundant attributes are "removed" by $\Join$), moreover you use several distinct intermediate variables which are not that useful (subresult and YXXXX, but i'm ok with "mix2"). $\endgroup$
    – Romuald
    May 26, 2013 at 16:48
  • $\begingroup$ As a side remark, from the computational point of view, $\sigma_{year=X}$ should be done as "early" as possible (and $Author \Join$ should be done as "late" as possible). $\endgroup$
    – Romuald
    May 26, 2013 at 16:55

This is an answer by the OP, which is removed from the question.

A friend gave me a tip and a possible solution appeared:

For Author(Name,AuthorID) | Publication(Title,Year,BookID) | AuthorPublication(BookID,AuthorID)

$ RenamedAP = \alpha_{(AuthorID:linkAuthorID, PublicationID:linkPubID)} (AuthorPublication) $

$Mix \leftarrow RenamedAP \times Author \times Publication $

$Mix2 \leftarrow \sigma_{(AuthorID=linkAuthorID \wedge PublicationID = linkPubID)} (Mix) $

$ Y2008 \leftarrow \sigma_{(Year=2008)} (Mix2)$

$ Y2009 \leftarrow \sigma_{(Year=2009)} (Mix2)$

$Y2010 \leftarrow \sigma_{(Year=2010)} (Mix2) $

$ Subresult \leftarrow Y2008 \cap Y2009 \cap Y2010 $

$ Result \leftarrow \pi_{Name} (Subresult) $ \


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.