18.7.3. Transitive Closure

Next let us define what we call as closure of a relation. So, what do we mean by this? So, imagine you are given a set A that may be finite or infinite and you are given a relation R over the set A that means a relation R is a subset of A x A and I have some abstract property P, it is some abstract property and I am interested to check whether the relation R over the set A satisfies this property P or not? If it is satisfies the property well and good. But, that may not be the case R that is given to you need not satisfy the property. So, the closure of the relation R is defined with respect to this property P. If you change the property P, the closure will change. So, what is that is the closure of the relation R with the property P. Well, it is the smallest superset of R which has the property P. Pictorially what I am trying to do here is if my relation R already satisfies the property P, I do not need to add anything to the relation R. I do not need to actually add any extra element to the relation R to satisfy the property P. But if my relation R does not satisfy the property P then I will be interested to introduce new ordered pairs in the relation R and convert it into another relation S, so that the expanded relation S satisfies the property P that is what I am trying to do here, this S you can imagine as expanded version of R and this S is also going to be a relation over the set A itself. I am including the original relation R that is carried as it is. On top of that I am adding or I may add few extra elements and try to ensure that expanded R which is S satisfies the property P, but I am not going to do the expansion arbitrarily; I am interested in the least possible expansion, least expanded version, what I mean by least? That means this is the minimal expansion which I need to do in order to ensure that the relation S satisfies the property P that is important. Otherwise, what is a big deal in expanding the relation R? You keep on adding any arbitrary number of elements definitely you will more or less soon get an expanded version which will satisfy the property P. So, we are interested in the smallest possible expansion.

The closure of a relation is defined as an expansion of the relation that meets a specific property, denoted as P. If a relation R does not satisfy property P, we create a new relation S that is a superset of R and includes the minimal elements needed to meet property P. This means we're not haphazardly adding elements but instead only adding what's necessary to fulfill the defined property while maintaining the integrity of the original relation.

Think of a relationship between friends as a social circle (the relation R). If you want this circle to have a criterion, such as everyone needing to know each other (property P), then you might need to introduce new friendships (add new pairs) to ensure that everyone is connected. The closure is like saying, 'Let’s make sure everyone knows everyone, but we’ll only add friends who are essential to make this happen.'

So, let us see some examples of this abstract property P and how the resulting closure looks like. So, my first abstract property is the reflexive property and this gives us what we call as reflexive closure of a relation. So, you are given a relation R over the set A and I am interested to see whether this relation R satisfies the reflexive property or not, reflexive over the set A, so that is what is the reflexive closure of the relation R. So, how can you construct a reflexive closure of R? Well you just take the union of R with all ordered pairs of the form (a, a) where a is present in your set A. If your, (a, a) is already there in the relation R then as per the union definition, you will not be including it again. Remember, union means if (a, a) is present in R as well as in this new relation, so this new relation I am calling it as Δ relation. So, this Δ relation you can imagine it is consisting of all ordered pairs of the form (a, a) such that a is present in A. So, if (a, a) is already there in R, it will not be included again but if (a, a) is not present in R then due to the union, due to taking union with this Δ, it will be now added to the relation R and now you can see that this is your expanded R that may be same as R itself, in case if your relation R is already reflexive then you are not going to add any extra elements. So, this expanded R will have the original elements of the relation R plus this expanded R will satisfy the reflexive property.

To construct the reflexive closure of a relation R, we form a new relation by adding pairs of the form (a, a) for every element a in the set A. This will ensure that every element is related to itself, which is a requirement of a reflexive relation. If an element already has this self-pairing in R, it won't be duplicated in the new relation. Hence, the reflexive closure is simply a union of R and these new pairs, guaranteeing that any missing reflexive pairs are added without disrupting the existing relations.

Imagine a classroom where each student (elements of A) has their own desk and personal space, which represents them being 'reflexive' about themselves. If a student does not maintain a relationship with themselves (i.e., do not acknowledge their own desk), then the classroom needs to add this relationship. The reflexive closure is about ensuring everyone is aware of their own space, reinforcing a sense of belonging.

Now, let us take the case when my abstract property P is the symmetric property. So, again, I am given a relation R defined over the set A and I am interested to form a symmetric closure of R. Why I am calling it closure? Because I am trying to put a layer over, I am trying to enclose the original relation R and get a relation which has the original R as well as it satisfies the property P that is why it is called a closure. So, how do I form the Symmetric Closure? So, if you recall the property of symmetric relation then the requirement here is that if (a, b) or if (a, a) is present in R, then I need the guarantee that (a, a) should also be present in R, this is the requirement from a symmetric relation and I need to include the original relation R, what I am going to do is, I am going to take the union of R with what I call as the inverse of the relation R. So, this is the inverse relation and what is this inverse relation? It is defined to consist of all ordered pairs of the form (a, a) such that a is related to a in the original relation. So, if in your original relation a is related to a then in the R-1 relation a will be related to a and it is easy to see that if you take the union of R with its inverse then the resultant relation will be symmetric and it will have the original relation R and this will be the smallest possible expansion of your relation R which satisfies the symmetric property.

To create a symmetric closure of a relation R, we add pairs that represent the symmetric property. For instance, if (a, b) is in R, we must ensure that (b, a) is also included in the new relation. This is accomplished by taking the union of R and its inverse relation, which consists of all pairs (b, a) for each (a, b) in R. Essentially, the symmetric closure ensures that all necessary pairs are added without redundant operations, forming the smallest relation that meets the symmetry requirement.

Consider the way friendships work. If Alice is friends with Bob (relation R has (Alice, Bob)), then in a symmetric environment, Bob must also be considered a friend of Alice (we would need to add (Bob, Alice)). The symmetric closure of friendship is about ensuring that if one person is connected, then that connection is mutual, forming a supportive and balanced relationship.

Now, what about the transitive closure? So, it turns out that finding transitive closure is not that simple, why so? Let me demonstrate that with an example. So, you might say that intuitively to find the transitive closure I add all ordered pairs of the form (a, c). Such that a is related to b as well as b is a related to c in the relation R because only when I add such order tuples of the form (a, c) in the relation R, it will ensure that the transitive property is satisfied. So, let us try to do that, you are given the original relation R and, I am forming, I am taking the union of the original R and I am adding all the ordered pairs of the form (a, c) which are needed to ensure the transitivity property. For instance, I need to add (1, 2), if you are wondering why I need to add (1, 2)? Because I have (a, b) present here, I have (b, c) present here. So, I need (a, c) which is (1, 2) also to be present which is not there in R so I say let me add it. In the same way I have (2, 1) present, which is your (a, b) and you have (1, 3) also present which is (b, c). So, you should add (2, 3) and so on. So, these are the new things which I add and my R’ will be this new relation. It has my original relation R, but now let us stop here and ask whether R’ is transitive or not. It turns out that R’ is not transitive. So, for instance, you have (2, 3) present here which is your (a, b) and you have (3, 2) present but you do not have (a, c) namely (2, 2) present in the relation R’...

Finding the transitive closure requires adding pairs to a relation R based on existing connections. If (a, b) and (b, c) are both in R, then we must add (a, c) to satisfy transitivity. However, this process might not end with a single addition, as adding one pair may lead to the need for further additions. This iterative approach means we must continuously apply the transitive property until no new connections can be established, highlighting that achieving transitive closure is not a one-step process, but an ongoing activity of ensuring all implied connections are captured.

Think of a social network where knowing someone indirectly (like knowing a friend's friend) should ideally create a connection too. If Alice knows Bob, and Bob knows Charlie, then ideally, Alice should also know Charlie. This may seem straightforward, but real-life connections can be complex; Alice might not directly know Charlie even though there’s an indirect connection through Bob. Thus, finding a transitive closure in this network requires carefully examining all relationships and ensuring every possible direct connection is accounted for, much like how friends bring acquaintances into the circle.

--