2
$\begingroup$

I was looking through my notes on domain relational calculus, and noticed an interesting result in a question about finding the most expensive pizza(s), given a pizza table with schema $\text{pizza}(\underline{id}, size)$. The first idea that came to me was:

$$\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2)\}$$

i.e. A pizza which is at least at big as every other pizza is the most expensive. But the answer given was instead:

$$\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land (\text{pizza}(id2, size2) \to size1 \ge size2))\}$$

The subtle change being that the last $\land$ was switched with a $\to$. I tried converting the if/then to $\lnot pizza(\ldots)\lor size1 \ge size2$ to get an intuitive idea on what exactly causes my former answer to be wrong, but can't seem to put my finger on it. Can anyone grok the differences between both expressions, and why the former isn't the answer? Appreciate it!

$\endgroup$
2
$\begingroup$

Assume $id1$ belongs to the first set. By definition we get that, for some value of $size1$, we have

$$\forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2)$$

The above says that, no matter what values we choose for $id2$ and $size2$, we have $\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2$.

In particular, for any arbitrary value of $size2$, we have $size1 \ge size2$.

But this can't be the case! Indeed, the above implies that, even if we take $size2 = size1 + 1$, we still get a smaller or equal size than $size1$, which is absurd.

Having obtained a contradiction, we have to conclude that out initial assumption, $id1$ belonging to the set, is false. Hence, no value $id1$ can belong to the set -- it is completely empty.

(By the way, the above also implies that any pizza $id2$ has any size $size2$, which is likely not to be the case in your intended model.)

The point is: you don't want to require that $size1$ is larger (or equal) than any number $size2$. That would be requiring too much. You want to require that $size1$ is larger (or equal) than any $size2$, provided $size2$ is the size of some pizza. Or, "if $size2$ is the size of some pizza, then $size1 \ge size2$".

The latter can be written as $$ (\exists size2\ pizza(id2, size2)) \implies size1 \ge size2 $$ or equivalently $$ \forall size2\ (pizza(id2, size2) \implies size1 \ge size2) $$ The latter can then be adapted to also require that $size1$ is indeed the size of $id1$, as the correct solution does.

$\endgroup$
  • $\begingroup$ Ah I see, my misunderstanding was that pizza(id2, size2) was doing a restriction on the domain of values for ids and sizes to those found in the pizza relation for the rest of the expression, as opposed to being plainly evaluated for a T/F value. In that case, would it be accurate to say that for the vast majority of instances, a “for all” would be accompanied by an if/then clause, since I don’t see a case where table(val) could possibly be true for any value of that datatype? $\endgroup$ – LJJ Dec 5 '17 at 6:47
  • 1
    $\begingroup$ @LJJ Yes, it is very common to see the pattern $\forall x\ (\ldots \implies \ldots)$, just to restrict the range of $x$ to some known case. $\endgroup$ – chi Dec 5 '17 at 9:35
2
$\begingroup$

For the first solution suppose, given $id2$ and $size2$ which $\neg pizza(id2, size2)$ and $size1 < size2$. Although, the first solution said $pizza(id1, size1)$ is not maximum (because it is not true for all $id2$ and $size2$), but it can be false. Because, if $(id1, size1)$ is the only member of the table, it is the maximum. Therefore, the first solution have some fallacy.

To correct the case, you should mention that if $(id2,size2)$ is member of $pizza$ relation, then $size1 \geq size2$ and you can write this proposition as $pizza(id2, size2) \rightarrow size1 \geq size 2$.

$\endgroup$
  • $\begingroup$ Thanks for answering! I do prefer chi’s answer though, as it let me get to the heart of my misunderstanding of how DRC operates. $\endgroup$ – LJJ Dec 5 '17 at 6:49

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.