# Using relational algebra to express all with a condition

I encountered this question while revising for my finals exam on database theory.

The following database contains information about car repair workshops. The following tables are used:

$$Workshop(\underline{rname})\\ Car(\underline{cname},make,model)\\ Repairs(\underline{rname,cname},price)$$

Given two workshops $$W_1$$ and $$W_2$$, $$W_1$$ is more expensive than $$W_2$$ if for every car $$C$$ that is repaired by both $$W_1$$ and $$W_2$$, the repair price for $$W_1$$ is higher than the repair price for $$W_2$$ for $$C$$. Write a relational algebra query to find all workshops $$(W_1, W_2)$$ where $$W_1$$ is more expensive than $$W_2$$. Exclude workshops that do not repair any common cars.

I attempted to use a join naively:

1. $$\rho_{(w1,car,c1)}(Repairs) \bowtie_{car} \rho_{(w2,car,c2)}(Repairs) \rightarrow A$$
2. $$\sigma_{c1 > c2}(A) \rightarrow B$$

And then simply project out the $$rname$$ on a join with $$Workshop$$. However, I realised that there would exist some Repairs where $$c1 < c2$$ and $$c1 > c2$$ are both present, and it would still indicate that $$W_1$$ is more expensive than $$W_2$$.

I am thinking of using the division $$\text{\\}$$ operator, but I am not sure how to proceed.

Update 1: I tried it out in SQL and managed to get the following query.

SELECT * FROM Workshop w1
WHERE NOT EXISTS (
SELECT * FROM Workshop w2
INNER JOIN Workshop w3
ON w3.cname = w2.cname
AND w2.rname = w1.rname
AND w2.cname = w2.cname
WHERE w2.price < w3.price);


I belive this is the correct answer, but my problem now is translating this back into relational algebra.

Update 2 (Solution): Instead of using a division, the subtraction operator is used.

1. $$\sigma_{car_1 = car_2}(Repairs \times Repairs) \rightarrow All$$
2. $$\sigma_{\text{price}_1 \leq \text{price}_2}(All) \rightarrow B$$
3. The answer is selecting all $$w1$$ from $$All - B$$

This will find all pairs in which $$price_1$$ is greater than $$price_2$$ for all $$C$$.

• Hint: $\forall \equiv \neg \exists \neg$ – André Souza Lemos Nov 23 '19 at 0:57
• That is, $\forall C \in a$ where $a \subset A$ (from above), the condition $c1 > c2$ should hold true. Thus, I invert it to become $\neg \exists C \in A \ni c1 < c2$. However, would this require relational calculus? There seems to be no way to express existential quantifiers in relational algebra. – Iwan Widargo Nov 23 '19 at 3:31
• You select the pairs that fulfill the existential criterion. That's a way to translate universals to algebra. Your SQL is close to the solution. Consider using subtraction then, not division. – André Souza Lemos Nov 23 '19 at 3:50
• Ah ok. I think I got it! Thanks. – Iwan Widargo Nov 23 '19 at 10:05
• You can answer your own question, there's nothing wrong with that. – André Souza Lemos Nov 23 '19 at 19:12