# Relational query for universally quantified formula

My university is participating in the implementation of a library borrowing managing system at Richelieu National Library in France.

I received the order to formulate the query: "find all users having borrowed every book" in relational Algebra, in relational Calculus and in SQL (which would probably not happen, probably librarians want to test the limits of the database).

The database has the following pattern (the primary keys are in bold):

Borrowing(People, Book, DateBorrowing, ExpectedReturnDate, EffectiveReturnDate)
Lateness(People, Book, DateBorrowing, LatenessFee)

I tried

$$\Pi_{People}(Borrowing)\div\Pi_{People}(\sigma_{Book} (Borrowing))$$

But It seemed to be wrong as far as to do $r\div s$, $S\subseteq R$ is needed, which seems not to be the case, but why? I'm still talking about people, isn't it?

I then tried the following relational calculus formula:

$$\{t.People|Borrowing(t)\wedge(\forall u Borrowing(u)\Rightarrow t.DateBorrowing)\}$$

To find every books that have a borrowing date. I know this calcuation is false but I don't know how to do better...

Then in SQL:

SELECT People FROM Borrowing
WHERE FORALL Books EXISTS DateBorrowing


That is what I tried and I know that is not the right way to "find all users having borrowed every book". Can you help me expressing correctely such a querry?

SQL does not have a universal quantifier, but an equivalent can be constructed from the existential one, through a normalization process similar to Skolemization: $$\forall x P(x) \iff \nexists x \neg P(x)$$

In your case, you want the users for which there does not exist a book that they have not borrowed:

select * from people p
where not exists
(select * from books b
where b.id not in
(select book_id
from borrowings
where people_id=p.id)
)


(Note that I have assumed tables for people and books to represent their existence separately from the borrowings table, which, for instance, may be empty at the inception of the system.)

• This a very nice answer, I perfectly understand the link you do between the $\forall$ with the Skolemization in SQL! And I upvoted consequently. But I was looking for one in Relational algebra and relational calculus... Mar 12, 2016 at 15:35

For the SQL part:

First, you want to determine how many books there are:

SELECT COUNT(DISTINCT book) FROM Borrowing)


Next, you want to SELECT those people who have Borrowed every different book - so one way to do this is by checking that the COUNT of DISTINCT books for each person is the same as the COUNT of all DISTINCT books:

 SELECT people
FROM Borrowing
GROUP BY people
HAVING COUNT(DISTINCT Book) = (SELECT COUNT(DISTINCT Book) FROM Borrowing);

• Welcome to Computer Science. This site is a computer science site, not a code writing site. Please explain why this query answers the question. On this site, the explanation is the important part, not the code. Feb 8, 2016 at 8:51
• @Gilles I will edit
– 3SAT
Feb 8, 2016 at 8:52

select distinct people from borrowing group by people having count(book) in (select count(book) from borrowing);

• Welcome to Computer Science. This site is a computer science site, not a code writing site. Please explain why this query answers the question. On this site, the explanation is the important part, not the code. Feb 8, 2016 at 8:51