Re: A Topological Relational Algebra in Lisp

On Tuesday, January 27, 2015 at 10:48:33 AM UTC-8, Norbert_Paul wrote:
> Tegiri Nenashi wrote:
> > On Sunday, January 25, 2015 at 2:30:29 AM UTC-8, Norbert_Paul wrote:
> >> <---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.)
> ...
> Hence RS is transitive.

Oops, what a trivial mistake I made: RS^2 is empty, therefore RS^2+RS^3+... is also empty, thus RS = RS+RS^2+RS^3+... .

> > 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
>
> No, it is the lattice "meet" of the two topologies induced by the projections
> from the join to the input tables. In general a result relation may also be the
> lattice "join", depending on the query operator.

Proposition. Natural join is of /final/ type; Inner union is of /initial/ type.

Corollary. Intersection, Cartesian product, and Selection is of /final/ type. Projection and Union is of /initial/ type.

I still stand by my assertion that behind your construction is cross product of two lattices. More specifically, you extend natural join of two database relations with lattice meet operation of two corresponding topologies. Likewise, you extend inner union-like operation (projection&union) with join of two lattice 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.
>
> No. it is not that simple:
> First you have to find induced topologies (or co-induced topologies depending on
> the type operator). The result topology is either the infimum or the
> supremum topology. The infimum topology is simply achieved by the union of
> the relations. The supremum topology, however, requires transitive closure
> computation in general.

Isn't transitive closure is just an implementation detail? If I wanted to work with partitions instead of topologies, the situation would be very similar. Lattice meet operation is partition intersection. In example of partitions of the set {1,2,3}:

1 | 2 3
^
1 2 | 3
=
1 | 2 | 3

Lattice join definition is a little more involved, so that partitions are the equivalence classes of element reachable via transitive closure. In example of partitions of the set {1,2,3,4,5,6}:

1 2 | 3 4 | 5 | 6
v
1 | 2 3 | 4 5 | 6
=
1 2 3 4 5 | 6

Here 5 is reachable from 1 via the chain 1->2->3->4->5: both 1 and 2 are in the same equivalence class of the first partition set, then, 2 and 3 are in the same equivalence class of the second partition set, and so on.

In other words [partition] lattice meet is just set intersection, while lattice join requires transitive closure. The fact that transitive closure was used can be ignored, and further development can be hinged on join and meet satisfying lattice algebraic laws.

> There are exceptions though. For example the topolgoy
> for the Cartesian Product "x" can be computed without transitive closure:
>
> (A,R) x (B,S) = (A x B, Ia x S + R x Ib)
>
> where Ia is the identity relation (a,a) on A and Ib the identity (b,b) on B.
> "+" is set union. It is, for example, an initial topology which can be created
> by a relational query expression without transitive closure.
> The tuples in Ia x S look like
> ((a,b1), (a,b2)) where a in A and b1 S b2 holds.
> The tuples in R x Ib look like
> ((a1,b), (a2,b)) where a1 R a2 and b in B holds.

This just reinforces my impression that transitive closure is not fundamental to the issue how you match relational algebra operations against topological lattice join and meet.  

> > 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?
>
> This concept may not be suitable for archeological sites. I think of a
> topological generalizaiton of kind of a "details library" which can be
> referenced from a coarser "sketch" to get a "detailled" plan iff details
> (say, windows, doors) are repeatedly used.
>
> So imagine you work on a plan where you have an element 0815 of type "door".
> Then refence that 0815-door object to a family of finer objects aggregated to a
> description of that door. The details library may then also describe
> topologically, how a door fits into a wall. The detailled plan (the natjoin)
> then topologically connects the, say, 0816-wall to the 0815-door, iff this
> connection is as well present in the sketch as also in the details library.

More explanation (detail:-) is wanted. Say, I'm working on home improvement project changing the entrance door (any Ask This Old House fans here?). I could have a spec what features are wanted: the door thermal/sound insulation properties, is it a glass door (genus-1 surface), what door knob should it have, etc. I might also be concerned about the door fitting the door entrance, so this has to be also a part of my query against improvement home store catalog. What is entirely escaping my intuition is that the door topological neighbors (rooms) are also relevant in such an application. Received on Tue Jan 27 2015 - 23:00:49 CET