Re: A Topological Relational Algebra in Lisp

Tegiri Nenashi wrote:
> On Friday, January 23, 2015 at 12:32:12 PM UTC-8, Norbert_Paul wrote:
> Please note that at this moment I'm confused on the meaning of both
>
> S join D
>
> together with
>
> RS join RD
>
> This is because you have introduced common attribute "detail" into both S and
> D while omitting the example. I can make guesses interpreting the id as
> identification of parent object in the aggregation, and detail being child.
> Then, join S with D is finding objects with common set of children. Again, a
> fixed example would be nice.

OK, I will start over again and only do the natjoin part without any decoration:

Assume that there are two topological spaces (S,T(RS)) and (D,T(RD)) represented by the four relations

   S = sid detail

       int1   interior
       door   xdoor
       garden exterior

         <---interior--->|<----boudary--->
   RS =  isid  idetail   -  bdsid  bddetail
         ----------------------------------
         int1   interior -  door   xdoor
         garden exterior -  door   xdoor

for (S,T(RS)) and

   D = did          detail
      ----------------------------------------------------
      interior     interior
      exterior     exterior
      surface1|    idoor
      surface2|    idoor
      surface||    xdoor
      surfacex|    xdoor
      idoormat     idoor
      xdoormat     xdoor

        <-----interior---->|<-----boudary------>
  RD =  idid     idetail      bddid      bddetail
        ---------------------------------------
        interior  interior    surface1|  idoor
        idoormat  idoor       surface2|  idoor
        interior  interior    surfacex|  xdoor
        exterior  exterior    surface||  xdoor
        xdoormat  xdoor       surface||  xdoor

for (D,T(RD)). The labels "interior" and "boundary" denote, how a tuple in D references two tuples in D. The topology-defining binary relations RS on S and RD on D are defined by the rule:

For each pair of tuples d1, d2 in D holds:

    exists r in RD s.t.

        d1.did=r.idid and d1.detail=r.idetail
        and
        d2.did=r.bddid and d2.detail=r.bddetail
   <=>
   d2 in cl({d1})                                           (1)

with respect to the topology T(RD). T(RD) itself is the finest (maximal) topology that satisfies the above rule.
An attribute prefix "i" is mnemonic for "interior" and "bd" for "boundary". The topology T(RS) is defined in a similar manner.

Now we carry out the natural join on S and D:

   SD = S natjoin D

• sid detail did

  ---

  int1 interior interior door xdoor surface|| door xdoor surfacex| door xdoor xdoormat garden exterior exterior .

Then we have the two projections ps and pd:

         ps : SD -> S,
         ps(int1,   interior, interior)  = (int1,   interior)
         ps(door,   xdoor,    surface||) = (door,   xdoor)
         ps(door,   xdoor,    surfacex|) = (door,   xdoor)
         ps(door,   xdoor,    xdoormat)  = (door,   xdoor)
         ps(garden, exterior, exterior)  = (garden, exterior)

         pd : SD -> D,
         pd(int1,   interior, interior)  = (interior,  interior)
         pd(door,   xdoor,    surface||) = (surface||, xdoor)
         pd(door,   xdoor,    surfacex|) = (surfacex|, xdoor)
         pd(door,   xdoor,    xdoormat)  = (xdoormat,  xdoor)
         pd(garden, exterior, exterior)  = (exterior,  exterior)

     (ps(sd1),ps(sd2)) in RS^*
     (pd(sd1),pd(sd2)) in RD^*

(here a mande an error in previous posts (and publications), where I used the transitive closures RS^+ and RD^+ instead of the transitive and reflexive closures RS^* and RD^*).
These pairs as a binary relation on SD generate the topology for the natural join of the spaces. I will not check diagonal entries (sd1,sd1) because it is not necessary. Note that RS and RD are transitive, hence in this example (a,b) in Rx^* <=> a=b or (a,b) in Rx holds for Rx = RS and Rx = RD.

sd1 as first tuple in SD:

       sd1=(int1,     interior, interior) sd2=(door,   xdoor,    surface||)
       ps: (int1,interior,   door,xdoor)           is     in RS
       pd: (interior,interior,   surface||,xdoor)  is not in RD
       So this tuple is not in the result

       sd1=(int1,     interior, interior) sd2=(door,   xdoor,    surfacex|)
       ps: (int1,interior,   door,xdoor)           is in RS
       pd: (interior,interior  surfacex|,xdoor)    is in RD
       So this tuple will be taken into the result relation.


       sd1=(int1,     interior, interior) sd2=(door,   xdoor,    xdoormat)
       ps: (int1,interior,   door,xdoor)           is     in RS
       pd: (interior,interior  xdoormat,xdoor)     is not in RD
       So this tuple is not in the result


       sd1=(int1,     interior, interior) sd2=(garden, exterior, exterior)
       ps: (int1,interior,   garden,exterior)      is not in RS
       pd: (interior,interior  exterior,exterior)  is not in RD
       So this tuple is not in the result

sd1 as second tuple in SD:
       sd1=(door,   xdoor,    surface||) sd2=(int1,   interior, interior)
       ps: (door,xdoor,  int1,interior)           is not in RS
       pd : need not be tested
       So this tuple is not in the result

       sd1=(door,   xdoor,    surface||) sd2=(door,   xdoor,    surfacex|)
       ps: (door,xdoor, door,xdoor) is a diagonal element, hence it is in RS^*
       pd: (surface||,xdoor, surfacex|,xdoor) is not in RD
       So this tuple is not in the result

       sd1=(door,   xdoor,    surface||) sd2=(door,   xdoor,    xdoormat)
       ps: (door,xdoor,   door,xdoor)           is     in RS^*
       pd: (surface||,xdoor,   xdoormat,xdoor)  is not in RD^*
       So this tuple is not in the result

       sd1=(door,   xdoor,    surface||) sd2=(garden, exterior, exterior)
       ps: (door,xdoor,  exterior,garden)         is not in RS^*
       pd: need not be tested
       So this tuple is not in the result

sd1 as third tuple in SD:
       sd1=(door,   xdoor,    surfacex|) sd2 = (int1,   interior, interior)
       ps: (door,xdoor,   int1,interior) not in RS^*
       So this tuple is not in the result

       sd1=(door,   xdoor,    surfacex|) sd2 = (door,   xdoor,    surface||)
       ps: (door,xdoor,  door,xdoor)  yet another diagonal element in RS^*
       pd: (surfacex|,xdoor, surface||,xdoor)  not in RD^*
       So this tuple is not in the result

       sd1=(door,   xdoor,    surfacex|) sd2 = (door,   xdoor,    xdoormat)
       ps: diagonal
       pd: (surfacex|,xdoor,  xdoormat,xdoor) not in RD^*
       So this tuple is not in the result

       sd1=(door,   xdoor,    surfacex|) sd2 = (garden, exterior, exterior)
       ps: (door,xdoor,    garden,exterior)  not in RS^*
       pd: need not be tested.
       So this tuple is not in the result

sd1 as fourth  in SD:
       sd1=(door,   xdoor,    xdoormat) sd2=(int1,   interior, interior)
       ps: (door,xdoor,    int1,interior) not in RS^*
       So this tuple is not in the result

       sd1=(door,   xdoor,    xdoormat) sd2=(door,   xdoor,    surface||)
       ps: (door,xdoor,  door,xdoor)  is in RS^*
       pd: (xdoormat,xdoor,  surface||,xdoor) is in RD
       So this tuple will be taken into the result relation.

       sd1=(door,   xdoor,    xdoormat) sd2=(door,   xdoor,    surfacex|)
       ps: (door,xdoor,  door,xdoor)  is in RS^*
       pd: (xdoormat,xdoor,  surfacex|,xdoor)  is in RD
       So this tuple will be taken into the result relation.

       sd1=(door,   xdoor,    xdoormat) sd2=(garden, exterior, exterior)
       ps: (door,xdoor,   garden,exterior) is not in RS^*
       So this tuple is not in the result

fifth row:

       sd1=(garden, exterior, exterior) sd2=(int1,   interior, interior)
       ps: (garden,exterior, int1,interior) not in RS^*
       So this tuple is not in the result

       sd1=(garden, exterior, exterior) sd2=(door,   xdoor,    surface||)
       ps: (garden, exterior, door,   xdoor) is in RS
       pd: (exterior, exterior) sd2=(surface||,   xdoor) is in RD
       So this tuple will be taken into the result relation.

       sd1=(garden, exterior, exterior) sd2=(door,   xdoor,    surfacex|)
       ps: (garden,exterior,  door,xdoor) is in RS
       pd: (exterior,exterior,  surfacex|,xdoor) not in RD^*
       So this tuple is not in the result

       sd1=(garden, exterior, exterior) sd2=(door,   xdoor,    xdoormat)
       ps: (garden,exterior,  door,xdoor) is in RS
       pd: (exterior,exterior,  xdoormat,xdoor) is not in RD^*
       So this tuple is not in the result

So the topology of the natural join SD is generated by the binary relation

   RSD = isid    idetail   idid         bdsid  bddetail  bddid
         ---------------------------------------------------------
         int1,   interior, interior,    door,  xdoor,    surfacex|
         door,   xdoor,    xdoormat,    door,  xdoor,    surface||
         door,   xdoor,    xdoormat,    door,  xdoor,    surfacex|
         garden, exterior, exterior,    door,  xdoor,    surface||

on SD.

I hope this exhaustive exapmple helps to understand my approach. (It made me spot an error in a previous post, too :) )

> I moved this part towards the end of the discussion: assuming you helped to
> resolve my confusion over natural join, this is the second issue to clarify.
> Why do you endow the real line interval (1000< x< infinity) with trivial
> topology? Isn't it standard metric space?
> http://en.wikipedia.org/wiki/Real_line#As_a_metric_space

The real line, when considered a topological space, is usually considered metric, not trivial. So the topology is implicitly given by convention. One could search for similar conventions for standard topologies for relational database table. A metric topology would be OK for me, because then we would happen to meet in the special case of finite tables.

Norbert Received on Sun Jan 25 2015 - 11:30:26 CET