1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hint: $\forall \equiv \neg \exists \neg$ $\endgroup$ – André Souza Lemos Nov 23 '19 at 0:57
  • $\begingroup$ 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. $\endgroup$ – Iwan Widargo Nov 23 '19 at 3:31
  • $\begingroup$ 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. $\endgroup$ – André Souza Lemos Nov 23 '19 at 3:50
  • $\begingroup$ Ah ok. I think I got it! Thanks. $\endgroup$ – Iwan Widargo Nov 23 '19 at 10:05
  • $\begingroup$ You can answer your own question, there's nothing wrong with that. $\endgroup$ – André Souza Lemos Nov 23 '19 at 19:12

Your Answer

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

Browse other questions tagged or ask your own question.