0

So in a DB course I am taking there is a practice problem, which states "Which authors co-authored at least 1 paper with every other author (without using aggregate functions)?"

The relations given are Author(authorid, name), Authoring(articleid, authorid), and Article(articleid, title). I can reduce this using relational algebra operations to a relation of tuples Authoring_Self_Join(authorid1, authorid2), which consists of author id's joined to themselves under the constraint that they authored with someone else who is not themselves without repetition i.e. unique tuple values only such that (i, j) will not have another relation in the table (j, i) and there is no (i, i) for all i, j.

So {(1, 2), (1, 3), (2, 3), (1, 4)} might be an example set representing this relation. I don't know a good approach toward finding an answer that the author "1" co-authored with every other author "2", "3" and "4".

If I were to use aggregate functions, I could make a count of each individual authorid in this table and select on those which equal the total number of authors (also using an aggregate).

However, the constraint of the problem is that you can not use aggregates. So I'm a bit lost as to where to go from here. If anyone could suggest an approach?

Nelson
  • 111

1 Answers1

1

Got it after I showed it to a friend, got me the rest of the way. Trick was to not filter the resultant relation so that it was still reflexive and symmetric that way it would work with the division operation.

Again, with a relation Authoring(articleID, authorID) we can make two new relations A1 and A2 with renamed columns:

$$ A1 \leftarrow \rho_{(articleID, A1_{id})}(Authoring) $$

$$ A2 \leftarrow \rho_{(articleID, A2_{id})}(Authoring) $$

Now we project the natural join between $A1$ and $A2$ to remove the article associations and just get those who authored an article with someone else (and themselves). This would also be a symmetric relation.

$$ R \leftarrow \pi_{A1_{id}, A2_{id}}(A1 * A2)$$

The set of all authors is a projection of either one of these columns (or the authorID attribute of the original Authoring relation).

$$ ALLAUTHORS \leftarrow \pi_{A1_{id}}( R )$$

We can now use division to find the answer:

$$ AuthorIds \leftarrow R รท ALLAUTHORS $$

This will return a relation of AuthorIds with an attribute $A2_{id}$, which you could rename and join with the Author table to get author names.

Nelson
  • 111