Re: A Topological Relational Algebra in Lisp

On Monday, January 19, 2015 at 11:58:42 AM UTC-8, Norbert_Paul wrote:
> Tegiri Nenashi wrote:
> > On Sunday, January 18, 2015 at 1:03:27 AM UTC-8, Norbert_Paul wrote:
> >> Take a set
> >>
> >> X = {bathroom, bdoor, hallway}.
> >>
> >> Each element can be considered a subset of the 3D real space R^3 (its
> >> "geometry"). The set could be coded as a database table
> >>
> >> X = roomid name floor department
> >> --------------------------------------------
> >> bathroom "Bathroom 007" 2nd 007
> >> hallway "Hall 007" 2nd 007
> >> bdoor "Bathroom door" 2nd 007.
> >>
> >> A topology could be
> >>
> >> T = { {}, {bathroom}, {hallway}, X}.
> >>
> >> The above topology can be coded as a binary relation on X:
> >>
> >> R = bounded boundary
> >> -----------------
> >> bathroom bdoor
> >> hallway bdoor
> >
> > ... The technical difficulty here is that binary relations
> > are different from multivariate
> > relations studied in database theory...
>
> Just a the pair (X,T) is called "topological space", I call the pair (X,R)
> a topological data type, because I consider the relation R a binary relation
> R \subseteq X \times X
> on X where, by abuse of notion, R will only contain primary key attributes from
> X...

OK, now it is clear: the objects you are focusing on are pairs of multivariate relation X in the first component, and binary relation R in the second.

Now you can define operations in Norbert algebra "component-wise". For example you can define "multiplication" as natural join in the first component and composition in the second. This would be not entirely without merit, because multiplication would be commutative and associative operation. However, natural join in [multivariate] relational algebra is idempotent, while composition in algebra of binary relations is not. Therefore, I'm not certain how well defined your algebra is. Can you please describe each and every of the following operations: natural join (as it might be something other than my guess), projection, and union?

> So I have both: a "multivariant" relation X accompanied by a binary relation
> R on X...

Multivariate, not "multivariant". Algebraic geometry studies systems of multivariate polynomials. If you think about zeroes of multivariate polynomials, they are exactly the tuples from database relations. I simply prefer the shorter term "multivariate relation" compared to more verbose "relation with named attributes". Again, it is important to clarify what mathematical structure are we talking about: Pierce-Tarski algebra of binary relations, or Codd's algebra of relations with named attributes (AKA "multivariate" relations).  

> > Many people in database community disagree, insisting that binary relations
> > are just special case of multivariate relations. This is one of the most
> > glossed over topics in [database] relational theory. Here is the challenge.
> > Take a relation R with three attributes x,y,z and define transitive closure.
> > Even simpler problem: define composition of this relation with itself.
>
> I am only interested in topology and, hence a binary relation is sufficient.
> However I can imagine a binary relation with three attributes:

You lost me: binary relation with three attributes?

>
> create table PointSet
> planid integer not null,
> objectid integer not null,
> -- ... additional attributes ...
> primary key (planid, objectid)
> -- ... additional constraints ...
> );
>
> create table Topology(
> planid integer not null,
> bounded integer not null,
> boundary integer not null,
> primary key(planid, bounded, boundary),
> foreign key (planid, bounded) references point_set,
> foreign key (planid, boundary) references point_set);

You defined topology as binary relation. Here you exhibited ternary relation. Granted you may recover topology as a binary relation from it, that is not the same as "binary relation with three attributes". Perhaps, if we dwell little more on this idea I would be able to express my discomfort with more precision.

> Then the pair (PointSet, Topology) represents topological space that is a
> so-called direct sum, a disjoint union of topological spaces each indexed by
> planid: http://en.wikipedia.org/wiki/Disjoint_union_(topology)
> The ineresting thing is, that the above construction would enforce the
> "dircet sum" property as a consistency rule.
>
> Also a ternary relation can be used to model a binary relation where each
> association has an integer attribute denoting the orientation of the boundary.
> But this is future work. I want also be able to model complexes.
> http://en.wikipedia.org/wiki/Chain_complex
>
> >> The relational representaion of a topology is an old and well-established
> >> fact in mathematics. The innovation is (IMHO) to combine it with the
> >> relational model.
> >
> > Again, you are referring to the theory of binary relations
> > http://en.wikipedia.org/wiki/Relation_algebra which is different from
> > relational model used in database theory.
>
> Again, I am always talking of a /pair/ (X,R) of relations where X is arbitrary
> and R a binary relation on X (thereby, of course, omitting all non-key
> attribute values from X).
>
> If you register such space in a hypothetical catalogue of spaces, say by
> sort of
>
> create space OuterSpace(
> PointSet, -- the point set
> Topology, -- the relation
> (planid, bounded) -- the FK on the "bounded side".
> );
>
> I willl give an example query to illustrate the idea: When the pair
> (PointSet, Topology) is registered as a space you could query OuterSpace
> just like an ordinary relation:
>
> select *
> from OuterSpace
> where planid = 9;
>
> would give a pair (X9, R9) which would represent plan 9 from OuterSpace
> as a tpopological space (X9, T9) and which then would consist of the two
> relations
>
> X9 = select * from PointSet where planid = 9;
>
> R9 = select R.planid, R.bounded, R.boundary
> from cltopology R, X9 bded, X9 bdry
> where R.planid = bded.planid and R.bounded = bded.objectid
> and R.pplanid = bdry.pplanid and boundary = bry.objectid --.

This gives me a flavor how you define selection. However, selection can be considered as a special case of natural join. Here I see that my earlier guess about natural join defined as composition in the second component is simply wrong.  

> Here cltopology is the transitive closure on topology. R9 then generates the
> "subspace topology" of X9 in OuterSpace:
> http://en.wikipedia.org/wiki/Subspace_topology
> In the above example, the transitive closure is not necessary but in general,
> correct subspace topology computation requires transitive closure. Its
> efficient use requires a good query optimizer.
>
> The entire Relational Algebra can be "topologized" this way. Every operator
> of Relational Algebra can be applied to such a space and will then return a
> correct result space. Some examples:
>
> group by: http://en.wikipedia.org/wiki/Quotient_space_(topology)
> cross join: http://en.wikipedia.org/wiki/Product_topology
> projection: http://en.wikipedia.org/wiki/Final_topology
> equijoin: http://en.wikipedia.org/wiki/Pullback_(category_theory)

"group by" generalizes projection. Does Quotient Space generalize Final Topology?

Since you offered definition of topological relation as ordered pair of multivarite relation together with binary relation, you can specify operations in your algebra without referring to topology. Again, I'm interested to see formal definitions of natural join, projection, and union.  

> It is a RoomsWithTopology object that is represented by a pair of relations
> just as described above. I am thinking of expanding the relational catalog to
> register topological spaces. Then a query on spaces always uses the topological
> counterparts of each relational operator involved. A mix of spatial and
> non-spatial operators combining "ordinary" database relations with "spaces" is
> also possible.

Again, can you please take the (Rooms,RoomNeighbourhood) pair from your example, then introduce one more pair and, next, work out the natural join of these two pairs (is it something meaningful)?   Received on Mon Jan 19 2015 - 23:53:03 CET