Encapsulation theory: radial encapsulation.
Edmund Kirwan*
www.EdmundKirwan.com
Abstract
This paper introduces the concept of radial encapsulation, whereby dependencies are constrained to act from subsets towards supersets. The paper shows how hierarchically encapsulated sets can be viewed as trees and investigates how potential coupling changes as the branches of these trees are manipulated.
Keywords
Encapsulation theory, radial encapsulation, potential coupling.
1. Introduction
In [1] an encapsulation context was defined as a set of constraints on the formation of potential ordered pairs within an encapsulated set. The absolute information-hiding context was introduced whereby a violational element is accessible to all elements in all other disjoint primary sets. Arguably the simplest and most widely-employed, this context is not, however, the only context imaginable. Others exist.
The key point of these other contexts is that they enable that which is forbidden by absolute information-hiding: they allow violational elements which are accessible to some but not all of the elements in other disjoint primary sets. Violational access becomes a relative - rather than an absolute - property: hence these are the relative information-hiding contexts, or simply, "Relative contexts."
Relative contexts differ from one another only in the means they employ to manifest this relative element access, and there is no limit to number of such manifestations. To take the computing environment, for example, we can imagine that the program units of a system are named (as they usually are) and therefore we could contemplate the constraint that dependencies between program units must flow alphabetically. Program unit Arnold may depend on program unit Melissa; program unit Zebra may not depend on program unit Brenda. Despite the crassness of this example, such an unusual dependency constraint nevertheless establishes a relative context: violational elements accessible to some are not accessible to others (those alphabetically, "Up-stream").
When faced with multiple relative contexts, one must usually choose between suitors; seldom do the constraints of one relative context overlap with those of another to the degree that both may reign consistently over the same system. Occam's razor is invoked: all else being equal, the relative context defined by the simplest, most economic constraints might be considered the best choice.
This paper introduces such a relative context, the radial encapsulation context, defined by a single constraint: dependencies may only form from subsets to supersets.
2. Radial encapsulation
First, let us look at an absolute information-hiding context. Figure 1 shows two primary sets, a and b, both containing two elements, one violational (the black element) and one hidden (the white element) - note that the secondary sets V and H are not shown but understood. Also shown are the potential dependencies from the elements in set a on those elements in set b, thus we see two dependencies on the violational element in b.
Figure 1: An absolute information-hiding context with two primary sets.
Recall that the absolute context is embodied in the definition of the external potential coupling set (see definition [D1.9] in [1]):
(i)
This tells us that, in the absolute context, dependencies may form from the elements of any disjoint primary set to the violational elements of every other disjoint primary set. In terms of software, this says that all program units of any given subsystem may form dependencies on all the public program units of all other subsystems in the system. Hence the two dependencies shown in figure 1 are perfectly legal.
How would this simple configuration look in a radial encapsulation context? The defining constraint of radial encapsulation is also embedded in the definition of the external potential coupling set (see definition [D8.1]):
(ii)
Despite
the apparent similarity between equations (i) and (ii), these sets
are very different. In (i), as mentioned, dependencies may form
towards every other disjoint primary set; in (ii), however,
dependencies may form on towards those disjoint primary sets that are
not subsets of the primary set in question, Qi.
To put it another way, dependencies may only flow from subsets into
supersets, or more formally that an ordered pair
represents
a legal dependency if and only if
.
It thus appears that the two dependencies portrayed in figure 1,
though legal in the absolute context, would be illegal in the
relative context. The potential dependencies from b to a,
also, would be illegal: b is not a subset of a nor is a
a subset of b; this would leave us with two sets which could
not interact and a trivially degenerate system.
So how can we allow interaction between these two sets whilst respecting radial encapsulation? The answer is to hierarchically construct the two sets, as shown in figure 2.
Figure 2: Radial encapsulation with two primary sets.
In figure 2, set a is defined as a subset of set b. Now, the elements in a are free to form potential dependencies on the violational elements in b without transgressing the constraint that dependencies can only form from subset to superset. Of course, the elements in b may not, still, form potential dependencies towards the elements in a, as those dependencies would form from superset into subset, but a degree of interaction is now possible.
Encapsulation contexts whose dependency constraints are realised by the partial- or hierarchical-ordering of sets are called hierarchical encapsulation contexts, a subcategory of the relative encapsulation contexts; the radial encapsulation context is a yet further subcategory of the hierarchical encapsulation contexts. (The, "Radial," term, incidentally, comes from the pattern made by the potential dependency arrows in figures such as the one above: the arrows always radiate outwards, never inwards.)
Before we examine the properties of radially-encapsulated sets, and how they differ from those of, "Normal," absolute information-hiding contexts, let us look at an alternative representation of the set in figure 2. Purely for convenience, instead of drawing set a inside set b, we can depict a as being on top of b, as shown in figure 3.
Figure 3: Radial encapsulation with a defined within b.
In figure 3, it is understood that drawing a on top of b implies that a is a subset of b, and b is a superset of a. Viewed so, the radial encapsulation context allows only those dependencies that flow, "Downwards."
3. Radial branches
Figure 4a shows three sets radially encapsulated.
Figure 4a: Three radially-encapsulated sets.
The arrows of figure 4a now show the general direction in which potential dependencies form between violational elements contained with each of the sets (not shown), though note that elements in a may form dependencies not just towards elements in the superset b, but towards elements in c too, thus the arrows represent a simplified view of the potential dependencies. The organisation of sets shown in figure 4a is called a branch and the length of the branch is the number of its comprised sets.
Let us now populate the branch of figure 4a with elements and attempt to calculate its potential coupling, see figure 4a.
Figure 4b: Three radially-encapsulated sets populated with elements.
The internal potential coupling in the relative context is the same as that in the absolute context. The potential couplings of the three sets are:
Set c: The internal potential coupling is 5x4=20. This set has no external potential coupling, as there is not set "below" it to which it can form dependencies. Thus the potential coupling of c is 20.
Set b: The internal potential coupling of this set is 3x2=6. The external potential coupling is the number of elements in this set multiplied by the number of all the violational elements (the black elements) it can see in all other sets. As the only set on which this set can form dependencies on is set c and there are only two violational elements in c, then the external potential coupling is 3x2=6. Thus the potential coupling of b is 6+6=12.
Set a: The internal potential coupling of a is 3x2=6. The external potential coupling is the number of elements in a multiplied by the number of violational elements in b and c, which is 2+2=4; so the external potential coupling is 3x4=12.
Summing the potential couplings of all three sets, we find that the potential coupling of this branch is 44. Noting that there are 11 elements in this branch, we might also ask whether we could reduce the potential coupling of this branch by changing the number of sets and re-distributing the elements. Does there exists a specific number of sets per branch that minimises the potential coupling of that branch? This question is answered in the next section.
4. Minimised branches
Consider a branch of 100 elements. Let us plot the potential coupling of this branch as the elements are uniformly distributed over increasing numbers of disjoint primary sets (i.e., over an increasingly long branch) subject to the constraint of a specific violation of one (i.e., there must be one and only one violational element per disjoint primary set, d=1). Thus, the first branch will consist of a single set with a potential coupling of 9900. Next, the 100 elements will be spread over a branch of two sets, giving a potential coupling of 4950, and so on.
Figure 5: Potential coupling of an increasingly long, branch (d=1).
From figure 5, we can see that that potential coupling of this branch of 100 elements is minimised when the length of the branch is slightly less than twenty. It can be proved that the potential coupling of a uniformly-distributed branch occurs when the number of disjoint primary sets in the branch is given by (see proposition 8.3):
For n=100 and d=1, the number of disjoint primary sets is 14.
A significant difference arises here between the absolute and the radial encapsulation contexts. Given that all disjoint primary sets must contain at least one violational element, the minimum potential coupling of any number of elements occurs when there is just one violational element per disjoint primary set; having one violational element per disjoint primary set further implies that the set is uniformly distributed in violational elements. Within the absolute encapsulation context, it was proved that a set uniformly distributed in violational elements has a minimised potential coupling when it is also uniformly distributed in hidden elements (see proposition 1.11 in [1]). This, however, is not the case in the radial encapsulation context consisting of a single, branch: given a branch uniformly distributed in violational elements, it is possible to reduce that branch's potential coupling by distributing its hidden elements non-uniformly. Deriving the equation for the configuration which offers this minimum potential coupling is described in [3]; this paper will concern itself with uniformly-distributed configurations.
5. Radial trees
We have thus far considered only single branches. A set, of course, may have many immediate subsets, thus forming multiple branches, or a tree, see figure 6.
Figure 6: Multiple branches.
Figure 6 shows a tree of two branches sharing the same root set. The two branches are {a, b, e} and {c, d, e}. The arrows in figure 6 again show the general direction of dependencies from elements within the sets to elements in others sets, thus elements in a can depend on elements in both b and e.
We wish to calculate the potential coupling of such multi-branch sets. The inclusion-exclusion formula of set theory describes how to calculate the total number of elements given a number of intersecting sets; a similar equation applies to branches, too (branches being sets themselves), and given that the potential coupling of a set is defined in terms of the number of its elements, then it can be shown that the potential coupling of a tree of a branches is given by:
This gives us the means to investigate how multiple branches affect overall potential coupling and raises two, general questions concerning a set of multiple branches.
The first question is: how does the potential coupling of a single branch change as it is split into two branches where the split occurs at ever lower sets?
Let us take 500 elements evenly distributed over a branch of 10 disjoint primary sets, where we shall number the root set as 1 and the leaf set as 10; throughout these experiments, we shall keep the specific violation of 1, d=1. We shall then record its potential coupling. We shall then consider two branches, the first being 10 sets long, the second being a branch of only 1 set, and shall join this branch to the first branch by adding it as a subset of the ninth set; thus we will have two branches 10 sets long, both having 9 sets in common and differing only in their leaf set. Again, we shall record the potential coupling. We shall then consider the first branch again of 10 sets and a second branch of 2 sets, adding this second branch to the first as a subset of its eighth set, and so on. The procedure is illustrated in figure 7. Note that, with each iteration, we evenly redistribute all the elements over all sets.
Figure 7: Redistributing elements over two branches.
Plotting the potential coupling at each iteration then shows how this splitting of a branch in two affects the system, see figure 8.
Figure 8: Potential coupling as the branch-split moves down the first branch.
The x-axis of figure 8 shows not the set at which the split between the two branches occurs, but the distance from the leaf set; thus as x=0, there is only one branch; at x=1, the second branch (one set long) is split from the first branch at ninth set; at x=2, the second branch (two sets long) is split from the first branch at the eighth set, etc. We can see from figure 8 that the potential coupling falls monotonically as the two branches are split further down the sets of the first branch. In other words, to minimise the potential coupling of the two branches, branches should be joined at the root set.
The second question we face concerning a set of multiple branches is: how does the potential coupling of a set change as we increase the number of branches into which the elements are distributed?
Let us take 500 elements evenly distributed over a branch of 5 disjoint primary sets, again with d=1. This branch has a potential coupling of 50500. Let us then take two branches of 5 sets each, again with 500 elements uniformly distributed over both branch and disjoint primary set, and with both branches joined at the root set. This has a potential coupling of 25750. Let us continue like this, increasing the number of branches but maintaining both the number of elements and the number of disjoint primary sets per branch; figure 9 shows the potential coupling as the number of branches increases.
Figure 9: Potential coupling as a function of increasing number of branches.
Figure 9 shows that the more branches we have, the lower the potential coupling. Unlike the number of sets per branch, as shown in figure 5, there is no specific number of branches that minimises the potential coupling of our system.
Certainly, at least concerning the application of encapsulation theory, an arbitrarily large number of branches may not be practical. As applied to software development, for example, the above graph suggests splitting a system into as many branches as possible, yet each branch can only communicate with others via the single disjoint primary set of elements at the root of all branches, and in the experiment above, the number of elements in the root set fell as more and more branches were added, thus rendering the experiment slightly unrealistic.
Nevertheless, the above shows that, in general, branching is a good strategy for reducing potential coupling, as can be shown by a simple comparison: proposition 1.14 of [1] shows that the minimum, isoledensal potential coupling achievable within the absolute encapsulation context is given by:
If we substitute into this equation the figures used in the experiment above (n=500, d=1) we find that the minimum potential coupling achieved is 21360. As can be seen from figure 9, radial encapsulation can achieve a potential coupling far below anything possibly achievable by absolute encapsulation.
6. Conclusion.
This paper introduced radial encapsulation and showed how the potential coupling of an encapsulated set, radially encapsulated, changed by splitting the set into branches.
7. Appendix A
Many of the propositions presented here necessarily contrast the potential coupling of absolute information-hiding with that of radial information-hiding. To avoid confusion we must adapt notation slightly. Wherever absolute information-hiding is concerned, we shall append the word, "Absolute;" wherever radial information-hiding is concerned, no extra words shall be appended. Thus, the potential coupling within the radial context is simply called, "Potential coupling," whereas the potential coupling within absolute information-hiding is called, "Absolute potential coupling."
Similarly, wherever s is
used to denote potential coupling we shall introduce the superscript,
"ab," to indicate potential coupling of an absolute
information-hiding context; the absence of such a superscript will
indicate potential coupling of radial information-hiding. For
example, the radial information-hiding external potential coupling of
encapsulated set G will be denoted
;
the absolute information-hiding external potential coupling will be
denoted
.
7.1 Definitions
[D8.1] Let sex(Qi) be the set of ordered pairs formed by the Cartesian product of all elements in the disjoint primary set of Qi with all elements of V that are not also members of the primary set Qi. This is called the external potential coupling set of Qi; the external potential coupling of Qi is cardinality of this set. Thus:
[D8.2] Given primary set Qi, tree Tr of Qi, written Tr(Qi), is set of all disjoint primary sets that are subsets of Qi. Thus:
For
example, if
and
,
then
.
Tr (Qi) is
represented in figure 10.
Figure 10: The tree Tr (Qi).
The primary set Qi of Tr(Qi) is also called the root primary set. A primary set of a branch with no subsets is called a leaf set.
A branch Qi, written B(Qi), is a tree whose every primary set is the root set, a leaf set or has only one "parent" superset and one "child" subset, or:
Thus figure 10 is also a branch.
7.2 Propositions
Proposition 8.1
Given an encapsulated set G and given that the ith primary set is Qi, the external potential coupling of Qi is a subset of the absolute potential coupling of Qi, or:
Proof:
By definition [D1.9] in [1], the absolute potential coupling set of Qi is the set of ordered pairs formed by the Cartesian product of all elements in the disjoint primary set of Qi with all elements of V that are not also members of the disjoint primary set of Qi:
(i)
By definition [D8.1], the potential coupling set of Qi is the set of ordered pairs formed by the Cartesian product of all elements in the disjoint primary set of Qi with all elements of V that are not also members of the primary set Qi:
(ii)
By definition [D1.5] the disjoint primary set Ki is the set of all elements in Qi but not in any primary subset of Qi, thus Ki is a subset of Qi:
(iii)
From (iii) it follows that:
(iv)
Take the Cartesian product of Ki with both sides (iv) gives:
(v)
Substituting (i) and (ii) into (v) gives:
QED
Proposition 8.2
Given an encapsulated set G and given that the ith primary set is Qi, the external potential coupling set of Qi is disjoint the external potential coupling set of all other primary sets, or:
Proof:
By proposition 1.3.10 in [1], the external potential coupling set of Qi is disjoint the external potential coupling set of all other primary sets, or:
(i)
By proposition 8.1, the external potential coupling of Qi is a subset of the absolute potential coupling of Qi, or:
(ii)
Substituting (ii) into (i) gives;
QED
Proposition 8.3
Given
an encapsulated set G
and given that the ith
primary set Qi,
the external potential coupling of G,
,
is given by:
Proof:
By definition [D1.12] of [1], the external potential coupling of G is:
(i)
Taking the cardinality of both sides of (i) gives:
=
(ii)
By proposition 8.2, the external potential coupling set of any primary set is disjoint from every other external potential coupling set, thus:
(iii)
Substituting (iii) into (ii) gives:
QED
Proposition 8.4
Given an encapsulated set G and given that the ith primary set Qi, the external potential coupling set of Qi is disjoint from the internal potential coupling set of Qi, or:
Proof:
By proposition 1.3.13 of [1], the external potential coupling set of Qi is disjoint from the internal potential coupling set of Qi, or:
(i)
As there is no difference between the internal potential coupling and the absolute internal potential coupling, then:
(ii)
From proposition 8.1, the external potential coupling of Qi is a subset of the absolute potential coupling of Qi, or:
(iii)
Substituting (ii) and (iii) into (i) gives:
QED
Proposition 8.5
Given an encapsulated set G and given that the ith primary set is Qi, the external potential coupling set of Qi is disjoint from the internal potential coupling set of all other primary sets, or:
Proof:
By proposition 1.3.14 of [1], the external potential coupling set of Qi is disjoint from the internal potential coupling set of all other primary sets, or:
(i)
As there is no difference between the internal potential coupling and the absolute internal potential coupling, then:
(ii)
From proposition 8.1, the external potential coupling of Qi is a subset of the absolute potential coupling of Qi, or:
(iii)
Substituting (ii) and (iii) into (i) gives:
QED
Proposition 8.6
Given an encapsulated set G and given that the ith primary set is Qi, all external potential coupling sets are disjoint from all internal potential coupling sets, or:
Proof:
From proposition 8.4, the external potential coupling set of Qi is disjoint from the internal potential coupling set of Qi, or:
(i)
From proposition 8.5, the external potential coupling set of Qi is disjoint from the internal potential coupling set of all other primary sets, or:
(ii)
From (i) and (ii) it follows that:
QED
Proposition 8.7
Given an encapsulated set G of r primary sets, and given that the ith primary set is Qi, the potential coupling of Qi is the sum of the external potential coupling sets of Qi and the internal potential coupling of Qi, or:
Proof:
By proposition [D1.10] of [1], the potential coupling set of Qi is given by:
(i)
Taking the cardinality of both sides of (i) gives:
=
(ii)
By proposition 8.6, all external potential coupling sets are disjoint from all internal potential coupling sets, or:
(iii)
Substituting (iii) into (ii) gives:
QED
Proposition 8.8
Given
an encapsulated set G of r primary sets, the potential
coupling
of
G is the sum of the internal potential coupling of G and
the external potential coupling of G, or:
Proof:
By definition [D1.13] of [1], the potential coupling set of G is given by:
(i)
Taking the cardinality of both sides gives of (i) gives:
=
(iii)
By definition [D1.11] of [1], the internal potential coupling set of G is given by:
(iv)
By definition [D1.12] of [1], the external potential coupling set of G is given by:
(v)
Thus from (iv) and (v):
(vi)
From proposition 8.6, all external potential coupling sets are disjoint from all internal potential coupling sets, or:
(vii)
Substituting (vii) into (vi) gives:
(viii)
Substituting (viii) into (iii) gives:
QED
Proposition 8.9
Given
an encapsulated set G of r primary sets and given that
the ith primary set is Qi,
the potential couplingof
G is the sum of the internal potential coupling of all Qi
and the external potential coupling of all Qi,
or:
Proof:
By
proposition 8.8, the potential couplingof
G is the sum of the internal potential coupling of G and
the external potential coupling of G, or:
(i)
By
proposition 1.3.11 of [1],
the internal potential coupling of
G,
,
is given by:
(ii)
By
proposition 8.3, the external
potential coupling of G,,
is given by:
(iii)
Substituting (ii) and (iii) into (i) gives:
=
QED
Proposition 8.10
Given
an encapsulated set G of r primary sets and given that
the ith primary set is Qi,
the potential couplingof
G is the sum of the potential couplings of all Qi,
or:
Proof:
By
proposition 8.9, the potential couplingof
G is the sum of the internal potential coupling of all Qi
and the external potential coupling of all Qi,
or:
(i)
By proposition 8.7, the potential coupling of Qi is the sum of the external potential coupling sets of Qi and the internal potential coupling of Qi, or:
(ii)
Substituting (ii) into (i) gives:
QED
Proposition 8.11.
Given
a uniformly-distributed branch B in encapsulated set G
of r disjoint primary sets and given that the ith
disjoint primary set Ki contains
elements
and has an information-hiding violation of d, the external
potential coupling of B,
,
is given by:
Proof:
By definition [D8.1], the external potential coupling of Qi is the number of ordered pairs that may be formed from this disjoint primary set towards the violational elements of all other disjoint primary sets that are not a subset of Qi, or:
(i)
Consider the root primary set Q1.
As Q1 is the root primary set, however, all other disjoint primary sets in this branch are subsets of Q1, thus the external potential coupling of the root disjoint primary set is 0.
The external potential coupling of the Q2 is then the number of ordered pairs that may be formed towards K1.
The external potential coupling of the Q3 is the number of ordered pairs that may be formed towards K1 and K2, etc.
Thus:
(i)
As B is a uniformly-distributed set then by definition [D1.14] in [1]:
(ii)
Substituting (ii) into (i) gives:
(iii)
By proposition 1.3.12 in [1],
the external potential coupling of set B, written,
is the sum of the external potential coupling of Qi,
or:
(iv)
Substituting (iii) into (iv) gives:
(v)
As B is a uniformly-distributed set then by definition [D1.14] in [1]:
(iv)
Substituting (iv) into (v) gives:
=
=
=
=
QED
Proposition 8.12.
Given
a uniformly-distributed branch B in encapsulated set G
of n elements and of r disjoint primary sets, with each
disjoint primary set having an information-hiding violation of d,
the potential coupling of B,
,
is given by:
Proof:
By
proposition 1.3.17 in [1], the
potential coupling of set
B, written
,
is the sum of the internal and external potential coupling of B,
or:
(i)
By proposition 1.6 in [1], the
internal potential coupling of B,
,
is given by:
(ii)
By proposition 8.11, the
external potential coupling of B,,
is given by:
(iii)
Substituting (ii) and (iii) into (i) gives:
=
QED
Proposition 8.13.
Given a uniformly-distributed branch B in encapsulated set G of n elements and of r disjoint primary sets, with each disjoint primary set having an information-hiding violation of d, the number of disjoint primary sets rild that isoledensally minimises the branch's potential coupling is given by:
Proof:
By proposition 8.12, the potential coupling of B is given by:
(i)
To find the number of disjoint primary sets that isoledensally minimise the potential coupling, differentiate (i) with respect to r and set to zero:
QED
Proposition 8.14.
Given a uniformly-distributed branch B in encapsulated set G of n elements and of r disjoint primary sets, with each disjoint primary set having an information-hiding violation of d, the branch's minimum isoledensal potential coupling is given by:
Proof:
By proposition 8.12, the potential coupling of a uniformly-distributed branch is given by:
(i)
By proposition 8.13, the number of disjoint primary sets rild that isoledensally minimises this branch's potential coupling is given by:
(ii)
Substituting (ii) into (i) gives:
=
=
=
=
QED
8. References
[1] - "Encapsulation theory fundamentals," Ed Kirwan, www.EdmundKirwan.com/pub/paper1.pdf
[2] - "Encapsulation theory: radial encapsulation," Ed Kirwan, www.EdmundKirwan.com/pub/paper8.pdf
[3] - "Encapsulation theory: the minimised, uniformly violational radial branch," www.EdmundKirwan.com/paper9.pdf
*© Edmund Kirwan 2009. Revision 1.0, December 20th 2009. (Revision 1.0: December 20th, 2009.) All entities may republish, but not for profit, all or part of this material provided reference is made to the author and title of this paper. The latest revision of this paper is available at [2].