3
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 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$ – András Salamon May 22 '13 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 '13 at 5:58
  • $\begingroup$ Check the definition of natural join. Are there any other attributes common to two relations ? $\endgroup$ – András Salamon May 23 '13 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 '13 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 '13 at 12:34
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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 '13 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 '13 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 '13 at 16:55
0
$\begingroup$

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) $ \

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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