Could someone please explain the expression for division in tuple relational calculus in words? I do not understand how the multiple operators (existential and universal quantifiers) are to be interpreted.
My question is almost the same as Division in tuple relational calculus but there is no response to this.
Since you aren't clear on how to interpret the quantifiers lets start with them.
The existential quantifier ∃ means there is atleast one object in a set(finite/infinite) that satisfies some given condition/property. For example if we consider the set of all people alive on earth(PE) we can say that there exist some people(P) such that they are females, which using quantifiers would be written as follows
∃ P ∈ PE | P=female or ∃ P ∈ PE (P=female)
which literally translates to
there exist people P(∃ P)
belonging to the set of all people alive on earth (∈ PE)
such that (|)
P is a female (P=female)
Similarly it goes for the universal quantifier ∀, in which case the property has to be followed by all the members of the set. Even if one member doesnt follow, the statement loses its truth value (universal quantifier doesn't hold true, existential may hold depending on the property). For example the closure property on the set of integers for the addition operation
∀ X,Y ∈ Z (X + Y ∈ Z)
which means
For all X,Y belonging to integers, X + Y belongs to integers.
Now coming to tuple relational calculus the division operator is defined as
{t | ∃ p ∈ R ∀ q ∈ S (p[B] = q[B] ⇒ t[A] = p[A])}
Over the relations(tables) R(A,B) and S(B)
which means
t is a tuple such that there exists p belonging to R and if p[B] = q[B] then t[A] = p[A] (assuming you know how to interpret other symbols)
that is if the condition p[B] = q[B] becomes true the tuple p[A] gets added to the result set of division operation.
One thing can be known from this. For a division operation R ÷ S to be meaningful the set of attributes of S should be a subset of R (think what would happen if its not a subset).
Now this operation be simply understood as
For all tuples in S, search for such tuples in R which have all tuples of S as a part of them and they have the same value for attributes except those that belong to S i.e same value for R[attributes(R)-attributes(S)]. Think of it as a group by in SQL.
Consider the following tables R and S
| R | R |
|---|---|
| A | B |
| 1 | a |
| 1 | b |
| 2 | b |
| 3 | c |
| 4 | d |
| 5 | d |
| 6 | b |
| 6 | c |
| 6 | a |
| 2 | c |
| S |
|---|
| b |
| c |
| R ÷ S |
|---|
| A |
| 6 |
| 2 |
now lets see how we got here, S has b,c as its tuples, so you look for such tuples in R which have all the values of S and the same value for R[(A, B) - (B)] = R[A]. Clearly, 1, 3, 4, 5 don't match this criterion and hence are rejected. 2 matches exactly so it is included in the result set. What about 6? it matches too, it has an extra tuple associated with a but that doesn't break the definition and hence, is a part of the result set. 1 is associated with b but not c and hence, rejected.
