Re: A Topological Relational Algebra in Lisp

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

OK, this example illustrates what your topological objects are (modulo corrections in your followup post). The next question is how do you fit this object into database relation.  

> Note that it does not contain the set {bdoor}.
> This topology tells us, that bdoor is close to the
> bathroom and also close to hallway.
> So it represents the fact, that bdoor connects
> the bathroom to the hallway. (Here also the connection
> to the metric topology of the space in R^3 where these
> three entities live, could be discussed.)
>
> The above topology can be coded as a binary relation on X:
>
> R = bounded boundary
> -----------------
> bathroom bdoor
> hallway bdoor
>
> If you transpose the relation you get
>
> RT = bounded boundary
> -----------------
> bdoor bathroom
> bdoor hallway
>
> This gives a topology
>
> { {}, {bdoor}, X}
>
> the so-called "dual topology".
> In the example case this topology is a graph where bdoor is an edge
> connecting bathroom and hallway. These graphs are often called
> "room adjacency graphs" by planners.
> Example:
> http://www.arch.virginia.edu/insightlab/student.php?postid=68

OK, this is intuitive, but I would like to mention that you are still quite far away from equipping [database] relations with topology. The technical difficulty here is that binary relations are different from multivariate relations studied in database theory. Specifically, the most important algebraic operation among binary relations is composition, while the most important operation among multivariate relations is natural join. The analog of composition in database world is natural join projected to the set of "distinct" attributes (formally symmetric difference). Composition is associative in the world of binary relations, but not associative in general in the database world.

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.

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

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

Thank you for clarification. However, I still don't quite understand what mathematical object that you study. If this is a [database] relation amended with topology, can you please elaborate the details? In your example, do you leave the Rooms table alone, and introduce additional binary RoomNeighbourhood relation? Or you combine the two into some multivariate RoomsWithTopology relation, or even generalize database relation into entirely new object? Perhaps you can elaborate your example and work out the join of two topological relations?

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 Received on Sun Jan 18 2015 - 23:18:46 CET