Re: A Topological Relational Algebra in Lisp

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

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. Then R generates a topology T(R) for X this representing the tpological spcae

   (X,T(R)).
I am, hence, thinking of registering such pairs in the database catalog as "spaces".

So I have both: a "multivariant" relation X accompanied by a binary relation R on X. In the ER-model X is usually called an "entity type" and R a "relationship type".

> 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:

   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);

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, 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 --.

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)

>> The bathroom door example topology is derived from the metric space that
>> door and rooms live in.
>

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.

> Regarding Alexandroff topology, you have mentioned that it is a set together
> with binary relation. Is this relation special in any way; what of its
> properties can be expressed formally?
> http://en.wikipedia.org/wiki/Relation_algebra#Expressing_properties_of_binary_relations_in_RA

Usually, the relations are considered preorders (called "specialization preorder"). However this restriction can be dropped (See property (1) below). Besides that, there are no particular restrictions on the binary relation. Some properties of R, however, yield particular topological properties of the topological space (X,T(R)), where T(R) is the topoogiy on X represented by the relation R:

(1) Two relations R and S produce the same topology, iff their transitive and

     reflexive closures R^* and S^* are equal, hence, R^* = S^* <=> T(R) = T(S)
     always holds for arbitrary relations R,S \subseteq X.
     Reflexive closure is always relative to X:
       R^* = R^+ \cup I(X)
     Where R^+ is the transitive closure of R and I(X) the identity on X
     (modelled according to the the schema of R, of course).

(2) Iff the relation has no cycles, the topological space it generates is
     called T_0 separable: http://en.wikipedia.org/wiki/Kolmogorov_space

(3) The pair (X,R) can be considered a directed graph with vertex set X
     and edge set R. All "connectedness" notions of (X,R) matsch the
     corresponding topologigal notions of (X,T(R)). (X,R) is a connected graph
     iff (X,T(R)) is a connected space and the connected components of
     (X,R) (as graphs) represent the connected components of thr topological
     space (X,T(R)).

(4) The space is discrete iff R is coreflexive.

(5) Reflexivity and transitivity have no influence on the topology but may

     affect the costs of query processing.

(6) Iff R^* is an equivalence then the topological space is a disjoint sum of

     trivial spaces: http://en.wikipedia.org/wiki/Trivial_topology
     In particular, iff R^* is the universal relation on X, then
     (X,T(R)) is a trivial space.

(7) The height of R (the length n of the maximal acyclic chain
     x0 R x1 R ... R xn) gives the topological Krull-Dimension
     (http://de.wikipedia.org/wiki/Krulldimension - German link, because the
     English article only contains the algebraic definition) of the space.

... these are the ones I already know. The list you gave me is handy. I could check for each property mentioned there if and how it affects the topology.

Instead of restricting R, one could provide consistency rules for spaces to enforce topological properties of modelled spaces.

Hope this clarifies my idea.

Norbert Received on Mon Jan 19 2015 - 20:58:40 CET