# "At least one" clause in Relational Algebra

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}$

• 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. May 22 '13 at 22:42
• @AndrásSalamon Thanks! Unfortunately I was looking for a more "classical" notation (using projections, selections and joins). May 23 '13 at 5:58
• Check the definition of natural join. Are there any other attributes common to two relations ? May 23 '13 at 9:00
• @AndrásSalamon Indeed, that is a good idea. A friend gave me a possible solution, I shall edit my post with it. May 23 '13 at 10:32
• 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 May 23 '13 at 12:34

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$.

• 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? May 23 '13 at 15:13
• 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"). May 26 '13 at 16:48
• 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). May 26 '13 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)$ \