Re: Comments on Norbert's topological extension of relational algebra
Date: Sat, 19 Dec 2015 12:14:52 +0100
Message-ID: <n53e2k$nhq$1_at_dont-email.me>
Nicola wrote:
> On 2015-12-18 19:25:34 +0000, Tegiri Nenashi said:
>
>> I'm still wanting an example that might clarify topological extension
>> of RA. If the proposal is about introducing topological datatype, then
>> the extension is quite intuitive, and can explained to database person
>> in terms of tuples and attributes.
...
> T. The latter has an obvious relational interpretation. Besides, instead
> of using P, we may in fact just use a relation R whose reflexive and
> transitive closure is P. The pair (X,R) is what Norbert calls a
> *topological datatype*.
Exactly
> The above would be an almost trivial observation: what is interesting
> (and far from trivial) is that the most common topological
> constructions, i.e., subspace, space product, space quotient, etc... may
> then be reduced to relational algebra operations (very elegantly, I'd
> say). The second interesting thing is that such operations may be
> performed in many cases directly on (X,R) rather than on (X,P), that is,
> without explicitly computing a reflexive and transitive closure (and it
> is never necessary to build (X,T)).
Thank you for clarifying. That exactly my point.
>> The first question is what are the values of topological datatype. I
>> assume, they are certainly not entire topologies.
>
> Given the equivalence above, they certainly are. Or, to be more precise,
> they are a lossless representation of topological spaces (through what
> are called "specialization preorders").
Yes, a topological data type is a relational representation of an entire topological space.
>> They are geometric objects with "qualitative" description, so that for
>> example cube is not distinguishable from sausage. "Topological
>> datatype" means that those objects are from the same topological
>> space; in the same venue as values from ordinary datatypes are chosen.
>>
>> Consider the following relation FavoriteShapes(name, topological_object):
>>
>> name topological_object
>> -------- ------------------
>> Jan Dohnut
>> Nicola Cube
>> Norbert Sausage
>> Actually, if one agrees how to choose a representative in every class
>> of all topologically equivalent objects, then the FavoriteShapes
>> relation has to be rewritten as
>>
>> name topological_object
>> -------- ------------------
>> Jan Dohnut
>> Nicola Ball
>> Norbert Ball
>
> What you mean here is that Ball, Cube and Sausage are homeomorphic. But
> homeomorphism is a mapping between topological spaces, not between
> elements of topological spaces. So, for that to make sense in the
> topological database context, you should represent Ball, Cube and
> Sausage as topological spaces, or equivalently (as per the above) as
> topological datatypes - not as elements of a topological space (well,
> you might represent Ball, Cube and Sausage each with a singleton space,
> but that would be trivial). One possibility (and a quite natural one,
> once you get by with what on earth a CW-complex is) is to use CW-complexes.
You can also mimic an attribute domain of topological databases by means of disjoint sum of spaces. (See below)
> Let me try a contrived example in 2D using a triangle and a square
> instead of a sausage and a cube. A triangle and a square may be
> represented as topological datatypes using CW-complexes where the
> 0-cells are vertices, the 1-cells are the edges, and 2-cells are the
> surfaces. Let TRIANGLE be the set of (0-, 1-, and 2-)cells of the
> triangle, that is, intuitively, the "parts" of the triangle of dimension
> 0, 1 and 2 respectively:
>
> TRIANGLE
> id dim
> ------
> 1 0
> 2 0
> 3 0
> 4 1
> 5 1
> 6 1
> 7 2
>
> (The geometric coordinates of the points may be stored in a different
> relation, e.g.:
>
> Coords
> id x y
> --------
> 1 0 0
> 2 0 1
> 3 1 0
>
> but they are not relevant for this example.)
>
> Now, (a topological space for) a triangle t may be represented as follows:
>
> R_t
> id1 id2
> ---------
> 4 1
> 4 3
> 5 1
> 5 2
> 6 2
> 6 3
> 7 4
> 7 5
> 7 6
>
> which corresponds to this drawing:
>
> 2 \
> | \
> | \
> 5 6
> | 7 \
> | \
> 1---4---3
>
> The pair (TRIANGLE, R_t) is a topological datatype. The corresponding
> topological space is built by taking the reflexive and transitive
> closure of R_t as the specialization preorder ≼, and taking all the
> upper sets wrt ≼ as the open sets (where the convention is that id2 ≼
> id1). So:
>
> Set X: {1,2,3,4,5,6,7}
> Topology T on X: {∅, {1,2,3,4,5,6,7}, {1,4,5}, {3,4,6}, {4}, {5}, {6},
> {7}, {1,3,4,5,6,7}, {4,5,6,7}, {5,6,7}, ... }
I'd say {1,4,5} and {3,4,6} is wrong with respect of your intention:
B = {{7}, {4,7}, {5,7}, {6,7}, {1,4,5,7}, {2,5,6,7}, {3,4,6,7}} as a basis B such that
T = { ∅,
{7}, {4,7}, {5,7}, {6,7}, {1,4,5,7}, {2,5,6,7}, {3,4,6,7},
{4,5,7}, {4,6,7}, {2,4,5,6,7},
{5,6,7}, {3,4,5,6,7}, {4,5,6,7}
{1,4,5,6,7},
{1,2,4,5,6,7}, {1,3,4,5,6,7},
{2,3,4,5,6,7}, X }
- T(B) .
> It is easy to see, for instance, that the edges are open sets, but the
> edges with their adjacent vertices are closed sets, as expected.
Wrong, I'd say. Whereas teh edges are open with respect to the topology you specified
above, I guess you had a topology in mind where the edges are neither open nor
closed. The minimal open set that contains an edge also contains 7 as an element.
> For a square we may do something similar:
>
> b---g---c
> | |
> f i h
> | |
> a---e---d
>
>
> SQUARE
> id dim
> ------
> a 0
> b 0
> c 0
> d 0
> e 1
> f 1
> g 1
> h 1
> i 2
>
> R_s
> id1 id2
> ---------
> e a
> e d
> f a
> f b
> g b
> g c
> h c
> h d
> i e
> i f
> i g
> i h
>
> The pair (SQUARE, R_s) is another topological datatype. A Cube or a
> Sausage may be represented in a similar fashion (I believe that for the
> sausage you need a finite approximation).
>
> Starting from TRIANGLE, R_t, SQUARE, R_s you may then build new
> topological datatypes (i.e., new topological spaces) that combine the
> triangle and the square in different ways, and to do so you may use RA
> operations as explained in the paper. Exercise for the reader (I am too
> tired to try this myself now): how to build a pair (X,R) that represents
> the following figure?
>
> b---g---c2 \
> | | \
> f i h5 6
> | | 7 \
> a---e---d1--4--3
>
> I think that you should also be able to formulate a query to verify that
> (SQUARE, R_s) and (TRIANGLE, R_t) are homeomorphic (another exercise).
If your square looked like
b---g---2
| |
f i 5
| |
a---e---1
then the query would be (SQUARE \cup TRIANGLE , R_s \cup R_t) . The triangle will then be pasted to the square (and wive versa). The pasing (attaching) map phi is
phi = id {2,5,1} -> {2, 5, 1} .
> A final remark: in practice, it is not feasible to have a separate
> schema for each object of the real world that we want to model. More
> realistically, you might want something along these lines (the following
> schema is just tentative, take it with a grain of salt!):
>
> WORLD
> object attr1 ... attrN
> --------------------------
> sausage ... ...
> cube ... ...
> ball ... ...
> ...
>
> PART
> id dim
> -------
> 1 0
> 2 0
> 3 0
> 4 0
> 5 0
> ...
> n 1
> n+1 1
> ...
> m 2
> m+1 2
> ...
>
> SHAPES
> object part_id
> -----------
> cube 1
> cube 2
> ...
> cube n
> ...
> sausage ...
> ...
>
> R1
> id1 id2 object
> --------------
> n 1 cube
> n 2 cube
> ...
> ... sausage
> ... sausage
> ...
>
> R2
> id1 id2
> -------
> ...
>
> The PART relation (which Norbert has called CELLS elsewhere) would
> contain the data about 0-cells, 1-cells, and so on (these are both the
> "parts" real objects are made of and the points of a topological space).
> The specialization preorders (i.e., the topologies) would be represented
> by R1, R2, ..., possibly storing more than one topological space in each
> relation, with an additional attribute to distinguish among the
> different spaces (as I have done for R1, where each object belongs to a
> different space).
I had a different idea:
WORLD as above
PART
pid id dim
cube 1 0
cube 2 0
cube 3 0
...
cube n 1
...
sausage 1 0
sausage 2 0
...
ball 1 0
ball 2 0
...
with
PRIMARY KEY(pid,id)
and
FOREIGN KEY(pid) references WORLD(object) .
R1
object id1 id2
cube n 1
cube n 2
...
sausage m 1
sausage m 2
...
ball k 1
ball k 2
..
Then consider R1 a binary relation on PART:
FOREIGN KEY(object id1) REFERENCES PART
FOREIGN KEY(object id2) REFERENCES PART
(object, id1, dim1, stuff1) -> (object, id2, dim2, stuff2) in PART. With this schema there cannot be an assocication between different parts. (I mean, this might be useful for a databse designer who exactly needs this property as a consistency rule)
The topological space generated by (PART, R1) is then a sum space with the active domain of "object" as index set: en.wikipedia.org/wiki/Disjoint_union_(topology)
> Your initial relation would correspond to WORLD, and it would *not* be
> part of a topological datatype, but it would provide the description a
> "high-level", or complex, object (a closed set, for instance).
> Topological datatypes in this example are (subsets of) pairs (PART, R1)
> and (PART, R2).
Yes, this is wat i menat by "mimic" topological datatypes as attribute domains.
> Of course, there are ways to build real objects other than with
> CW-complexes, but the notion of a topological datatype does not depend
> on your interpretation of what a point in a topological space is, so the
> approach is completely general. (Please Norbert correct anything wrong I
> may have said.)
Except for the small glitch in the triangle topology, it has all been well explained.
Norbert Received on Sat Dec 19 2015 - 12:14:52 CET