Re: Transitive Closure

From: Paul <paul_at_test.com>
Date: Tue, 18 May 2004 10:04:50 +0100
Message-ID: <2lkqc.4558$wI4.534613_at_wards.force9.net>


Mikito Harakiri wrote:
> So we are talking about different algebra, that has a universe with
> elements being unary relational algebra operators only -- selection,
> projection, Cartesian Power (as product is, unfortunately, binary
> operator), transitive closure, and, perhaps, negation. In this tiny 4
> element universe we define one binary operation: composition of unary
> relational operators. So we can speak of this operation commutativity,
> although, it's kind of wierd to say that operation commutes on these 2
> particular elements of the universe, and doesn't commute on those. In
> traditional algebra commutativity is all or nothing proposition: it's
> either commutative on the whole universe, or isn't (if there is at
> least a pair of elements such that ab!=ba).
 >
> Can people familiar with Category Theory comment? (Diagram by "x"
> provoked this thought).

I'm not familiar with category theory, but in group theory it's perfectly reasonable to have a group that is non-commutative, but that has a commutative (or "abelian") subgroup.

For example there is a group normally given the descriptive name of "S3" http://en.wikipedia.org/wiki/Group_(mathematics)#A_finite_nonabelian_group:_permutations_of_a_set This is a group with 6 elements that is non-commutative. But it has a subgroup that *is* commutative. i.e. the restriction of the operator on that subset of the group is commutative.

Now our four relational operators aren't a group under the "composition of operators" operation because, for one thing, the operation isn't closed. E.g. if we combine selection with projection we get something that isn't in our original set of operators. By the same argument they don't form an algebra either, in the sense of this: http://en.wikipedia.org/wiki/Universal_algebra

Also, we think of there being just one selection operator for example, whereas really there are an infinite number of selection operators parameterized by different "WHERE clauses". e.g. Select[foo=3](Relation).

If we compose the Select[foo=3] operator with the Select[bar=2] operator we get the Select[foo=2 and bar=3] operator.

So I think that the fact the transitive closure operator doesn't commute with other operators under the "composition of operators" operation is a bit of a red herring and doesn't really matter.

Paul. Received on Tue May 18 2004 - 11:04:50 CEST

Original text of this message