ONT Re: Relations And Their Divisitudes
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
RATD. Note 7
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
TJ = Tom Johnston
We need to be clear about one thing before we proceed any further.
We are now talking about the "projective" reducibility of relations,
and this is a weaker sort of reducibility than the "compositional"
reducibility, which is the fundamental type of reduction. You can
tell that it's weaker because it requires a crutch, and the crutch
is shaped like this:
x y
o o
\ /
&
|
o
x&y
For example, when a 3-adic relation L is projectively reducible
to a set of 2-adic relations {L_j}, it doesn't really count as
reducing L to nothing else but the {L_j}, as one is effectively
given a 3-adic relation to use in the construction, namely, the
3-adic relation corresponding to the connective & : B x B -> B,
where B = {0, 1} and "&" is "and".
As always, it remains true that no 3-adic relation can be written
as a composition of 2-adic relations, because 2-adic relations are
closed under relational composition.
o---------------------------------------------------------------------o
| Living Inferential Metaboly Of Symbols |
o-----------------------------o---------------------------------------o
| Standard Math Language, | Tom's translation into the language |
| A La Descartes | of relational databases |
o-----------------------------o---------------------------------------o
| k-adic relation | table with k columns |
o-----------------------------o---------------------------------------o
| k-tuple | row of a table with k columns |
o-----------------------------o---------------------------------------o
| relation(s) | table(s) in a relational database |
o-----------------------------o---------------------------------------o
| 1-adic projection | result of a relational PROJECT |
| | operation on a table, that |
| | leaves just one column |
o-----------------------------o---------------------------------------o
| a k-tuple is defined | a row of a table with k columns |
| to be determined by its | is defined to be determined by the |
| 1-adic projection data, | (ordered) set of relational PROJECT |
| but a k-adic relation in | operations, each of which results in |
| general is not determined | a single column instance of the table,|
| by its m-adic projection | but a table with k columns in general |
| data for any m < k. | is not determined by the (ordered) set|
| | of m PROJECT operations on that table,|
| | for any m > k. |
o-----------------------------o---------------------------------------o
TJ: I should be comfortable with Jon's language here, since I am
comfortable with the language in which the mathematical basis
of Codd's relational theory is stated. But since I found myself
scratching my head over that last instance of Jon's language listed
above, I thought I'd translate into a less rigorous but more comfortable
language, that of working relational databases. However, it didn't help.
Let's adopt the strategy that has always been recommended to me,
that of picking a few concrete and simple examples, applying our
several forms of language to them, and trying to see in this way
whether we are talking about the same things.
Here are some examples that I have discussed before in this forum.
L_0 and L_1. Examples of 2-projectively irreducible 3-adic relations.
The first two relations, L_0 and L_1, are examples of 3-adic relations
that are not reconstructible from their 2-adic projection data, and
so they are called 2-projectively irreducible 3-adic relations.
In this discussion, given a 3-adic relation L c X x Y x Z,
L_XY = p_12 (L) is the 2-adic projection of L on the XY-plane,
L_XZ = p_13 (L) is the 2-adic projection of L on the XZ-plane,
L_YZ = p_23 (L) is the 2-adic projection of L on the YZ-plane.
In order to show what a projectively irreducible 3-adic relation
looks like, I now present a pair of 3-adic relations that have the
same 2-adic projections, and thus cannot be distinguished from each
other on the basis of this data alone. As it happens, these examples
of triadic relations can be discussed independently of sign relational
concerns, but structures of their basic ilk are found frequently arising
in signal-theoretic applications, and they are no doubt keenly associated
with questions of redundant coding and therefore of reliable communication.
Consider the triadic relations L_0 and L_1
that are specified in the following set-up:
| B = {0, 1}, with the "+" signifying addition mod 2,
| analogous to the "exclusive-or" operation in logic.
|
| B^k = {<x_1, ..., x_k> : x_j in B for j = 1 to k}.
In what follows, the space X x Y x Z is isomorphic to B x B x B = B^3.
For lack of a good isomorphism symbol, I will often resort to writing
things like "X x Y x Z iso B x B x B" or even "X x Y x Z ~=~ B^3".
| Relation L_0
|
| L_0 = {<x, y, z> in B^3 : x + y + z = 0}.
|
| L_0 has the following four triples
| of the form <x, y, z> in B^3:
|
| <0, 0, 0>
| <0, 1, 1>
| <1, 0, 1>
| <1, 1, 0>
| Relation L_1
|
| L_1 = {<x, y, z> in B^3 : x + y + z = 1}.
|
| L_1 has the following four triples
| of the form <x, y, z> in B^3:
|
| <0, 0, 1>
| <0, 1, 0>
| <1, 0, 0>
| <1, 1, 1>
Those are the relations,
here are the projections:
Taking the 2-adic projections of L_0
we obtain the following set of data:
| (L_0)_XY has these four pairs
| of the form <x, y> in X x Y:
|
| <0, 0>
| <0, 1>
| <1, 0>
| <1, 1>
| (L_0)_XZ has these four pairs
| of the form <x, z> in X x Z:
|
| <0, 0>
| <0, 1>
| <1, 1>
| <1, 0>
| (L_0)_YZ has these four pairs
| of the form <y, z> in Y x Z:
|
| <0, 0>
| <1, 1>
| <0, 1>
| <1, 0>
Taking the 2-adic projections of L_1
we obtain the following set of data:
| (L_1)_XY has these four pairs
| of the form <x, y> in X x Y:
|
| <0, 0>
| <0, 1>
| <1, 0>
| <1, 1>
| (L_1)_XZ has these four pairs
| of the form <x, z> in X x Z:
|
| <0, 1>
| <0, 0>
| <1, 0>
| <1, 1>
| (L_1)_YZ has these four pairs
| of the form <y, z> in Y x Z:
|
| <0, 1>
| <1, 0>
| <0, 0>
| <1, 1>
Now, for ease of verifying the data, I have written
these sets of pairs in the order that they fell out
on being projected from the given triadic relations.
But, of course, as sets, their order is irrelevant,
and it is simply a matter of a tedious check to
see that both L_0 and L_1 have exactly the same
projections on each of the corresponding planes.
To summarize:
The relations L_0, L_1 c B^3 are defined by the following equations,
with algebraic operations taking place in the "Galois Field" GF(2),
that is, with 1 + 1 = 0.
1. The triple <x, y, z> in B^3 belongs to L_0 iff x + y + z = 0.
L_0 is the set of even-parity bit-vectors, with x + y = z.
2. The triple <x, y, z> in B^3 belongs to L_1 iff x + y + z = 1.
L_1 is the set of odd-parity bit-vectors, with x + y = z + 1.
The corresponding projections of L_0 and L_1 are identical.
In fact, all six projections, taken at the level of logical
abstraction, constitute precisely the same dyadic relation,
isomorphic to the whole of B x B and expressible by way of
the universal constant proposition 1 : B x B -> B. In sum:
1. (L_0)_XY = (L_1)_XY = 1_XY ~=~ B x B = B^2,
2. (L_0)_XZ = (L_1)_XZ = 1_XZ ~=~ B x B = B^2,
3. (L_0)_YZ = (L_1)_YZ = 1_YZ ~=~ B x B = B^2.
Therefore, L_0 and L_1 form an indiscernible couplet
of "triadic relations irreducible over projections"
or "projectively irreducible triadic relations".
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o