Max() in Domain Relational Calculus

Question

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!

Answer 1

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.

Answer 2

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