1
$\begingroup$

$ \newcommand{\Set}[2]{% \{\, #1 \mid #2 \, \}% }$

I've been trying to find how to express relational division operation in tuple relational calculus. The only thing I found is this presentation where on the page 4 it is said that for relations $R = (A, B)$ and $S = (B)$ the division is

$$ R \div S \equiv \Set{t}{\exists p \; \forall q \; (R(p) \land S(q) \land (p.B = q.B \Rightarrow t.A = p.A))}. $$

Which I find to be completely wrong. Let me first show why I think it's wrong and then propose my own solution.

Let's have tables

enter image description here

We want to find movies in which all actors played - meaning $\mathrm{CAST} \div \mathrm{ACTORS}$. Correct solution is a relation with only one attribute: $(\mathrm{Babel})$.

If we followed the given interpretation we would quickly run into a problem.

Let $t = (\mathrm{Seven})$ in the first table. We test whether we can find a $p$ from $\mathrm{CAST}$ such that ${(p.\mathrm{name} = q.\mathrm{name} \land p.\mathrm{surname} = q.\mathrm{surname}) \Rightarrow t.\mathrm{title} = p.\mathrm{title}}$ for all $q$'s from $\mathrm{ACTORS}$.

Let $p = (Seven, Brad, Pitt)$ and let's try all the $q$'s:

  1. For $q = (Brad, Pitt)$ we get $true \Rightarrow true$ which is $true$.

  2. For $q = (Peter, Wight)$ we get $false \Rightarrow true$ giving $true$.

So the $t = (Seven)$ will appear in the resulting relation even though it's the incorrect tuple (i found a $p$ such that for all the $q's$ the condition is satisfied).

I first tried to convert the relational algebra equivalent $$ E_{R} \times E_{S} = \Pi_{A}(E_{R}) \setminus \Pi_{A}((\Pi_{A}(E_{R}) \times E_{S}) \setminus E_{R}), $$ but it resulted in an extremely complicated result with 4 bound variables so I ruled that way out as well.

The last thing I resorted to is my intuition. Not only was the implication wrong in the aformentioned formula but also the order of quantifiers - for a given $t$ there cannot be a single $p$ such that $p.B = q.B$ for multiple $q$'s at the same time since the $\mathrm{Actors}$ relation cannot contain duplicit tuples.

My shot at this:

We want to find all tuples $t$ from the $\mathrm{CAST}$ such that for every $q$ from $\mathrm{ACTORS}$ I can find a $p$ in the $\mathrm{CAST}$ having the same $\mathrm{name}$ and $\mathrm{surname}$: \begin{align} \begin{gathered} \Set{t}{\forall q \; \exists p \; (\mathrm{ACTORS}(q) \land \mathrm{CAST}(p) \, \land \\ p.\mathrm{name} = q.\mathrm{name} \land p.\mathrm{surname} = q.\mathrm{surname} \land t.\mathrm{title} = p.\mathrm{title}))} \end{gathered} \end{align} Is that correct?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think that your formula should say $ACTORS(q) \implies CAST(p) ...$ rather than $ACTORS(q) \land CAST(p) ...$, isn't it? $\endgroup$
    – 441Juggler
    Commented Jul 27, 2022 at 16:21
  • $\begingroup$ Yes. I later found out that it's the same reasoning as in predicate logic where if you say that all humans are mortal, you write $\forall x (\mathrm{Human}(x) \implies \mathrm{Mortal}(x)) $ instead of $\forall x (\mathrm{Human}(x) \land \mathrm{Mortal}(x)) $ but I can't really explain it well in terms of TRC. I managed to find this - cs.ulb.ac.be/public/_media/teaching/infoh303/calculnotes.pdf where they talk about it on page 24. $\endgroup$
    – tomashauser
    Commented Jul 28, 2022 at 8:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.