Re: A Topological Relational Algebra in Lisp

On Sunday, January 25, 2015 at 2:30:29 AM UTC-8, Norbert_Paul wrote:
> 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

RS is not transitive. (Later, you mention that it is.)   

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

OK: having composite attributes (such as idid+idetail) allows you to avoid explicit references to tuples with introduction of auxiliary concepts such as FK, which you did in earlier posts.

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

I seem to grasp the high level idea: given the two topologies T(RS) and T(RD), their "natural join" is a lattice meet T(RS)^T(RD): http://en.wikipedia.org/wiki/Comparison_of_topologies#Lattice_of_topologies

[Relational algebra] natural join is lattice operation as well: http://www.dcs.bbk.ac.uk/~szabolcs/ramics-final.pdf This makes it trivial to establish that topology plays well along with Database Relational Algebra: the objects of Norbert Paul algebra are pairs (DatabaseRelation, Topology) with each component defining their own lattice meet and join. The Norbert Paul lattice is just a lattice product.

I might have jumped too far, because we didn't discuss union and projection yet. I simply point out that while natural join covers 3 cases (selection, intersection, and Cartesian product), its dual operation covers 2 cases -- union and projection -- at once.

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

Crystal clear now, thank you for clarifying it.  

> 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)
>
> Now we need the coarsest topology that makey both functions continuous.
> This is generated by the maximal binary relation on SD, that makes ps and pd
> continuous: So I will check each pair (sd1, sd2) of tuples from SD x SD, if
> it satisfies the two donditions
>
> (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

Typo? Did you mean RS^* and RD^* are transitive?

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

Same question here: RS^* and RD^*? I guess this can be easily recovered because "... is in RS" entails "... is in RS^*".

       ps: (int1,interior, door,xdoor) is in RS (and, therefore, in RS^*)

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

OK, this convinces me that the natural join, and the entire algebra is consistent. It would also be helpful to demonstrate that it is meaningful. I have already complained about relation and attribute names. The Sketch can be architectural schema, but what is Detail? Is it mapping of the archeological site as described in the reference in one of your earlier posts?

There are some values in your example, such as door, which intend to appeal to layman intuition. Still, I can imagine database application where home improvement chain store has an inventory of all doors:

Doors(sku,vendor)
DoorsDimensions(doorType,x,y,z)

I can't figure out realistic schema where "door" is a value of some attribute.   Received on Sun Jan 25 2015 - 21:56:25 CET