Comments on Norbert's topological extension of relational algebra

[Nicola]

I'd like to start a new thread about the topological extension of RA proposed
by Norbert Paul in this group last January. First of all, let me say that I
find the idea of representing a topology relationally through the
specialization preorder quite attractive for its simplicity. And let me add
that my knowledge of topology is very weak, so please be patient with me.

Before I make a few comments, I think that there are a couple of things to be
corrected, one in the paper and one in a previous post:

1. Example 6.7 from the paper contains a small mistake. The example says that,
given a topological database (X={a,b,c,d}, R={(a,c),(a,d),(c,b),(d,b)}), the
subspace topology on {a,b} does not contain {b}. But the topology generated by
R is {∅, {a,b,c,d}, {b,c,d}, {b,c}, {b,d}, {b}}, so the subspace on {a,b} is
{∅, {a,b}, {b}}, which contains {b}. The subspace is correctly generated by R+
∩ {a,b}^2 = {(a,b)}, but not by R ∩ {a,b}^2 = ∅, so the point of the example
(the necessity of computing the transitive closure) is valid anyway.

2. Norbert made an example using the following instances (copied from a
previous post):

S = sid detail
---------------
int1 interior
door xdoor
garden exterior

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

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

Then, he computed the topological natural join between (S,RS) and (D,RD) and
said that the result is:

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

If I am not mistaken, however, the result should be:

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

Regarding this example, could you provide a geometric intuition about how this
space is organized (ASCII art would be ok)? I understand (S,RS), but (D,RD) is
not clear to me (let alone the join - see below): it seems to me that there
are too many surfaces and too few relationships.

That said, the main issue I have with the approach (which others have raised,
too) is one of interpretability. Topological select (i.e., subspace) is
intuitive, but Cartesian product (i.e., space product), hence join, is not.
Group by (i.e., quotient space) even less. I mean, I understand the
constructs, but I do not clearly see how useful they might be in practice
(people in BIM do not work with Klein bottles that often, I guess). It may be
that the topological algebra is even too expressive for practical purposes:
for example, I can imagine that a useful operation might be "zooming", or a
change in granularity, where you have a topological space containing a point x
and you replace x by embedding another topological space (modeling the
parts x is made of). I am not sure whether "glueing" is the correct term for
it. I think that select (or difference) and union alone may achieve that.

Second, in the example above, the join is made on a detail attribute (that is,
not on a key). Would a join on key attributes between two topological
databases be meaningful? Intuitively, you would keep the points that belong to
both spaces and combine their topology through product... How would you
interpret the result? Would it make sense to think about it as building a
space with more dimensions (e.g., one space gives the topological relations
among points on axis x, the other on axis y, and the join would build
2-dimensional objects)?

Third, something that is not mentioned in the paper is how you would perform
computations with the topological algebra, e.g., answer topological queries
such as: "give me all objects that overlap this region". Say, you have a
topological database (X,R): how do you formulate the previous query (and how
do you model the region of interest)?

Fourth, the example above mentions real objects (doors, gardens, ...). But in
the paper a significant amount of space is devoted to CW-complexes (which I am
not sure I have understood yet). In a "real" application, would the X in a
topological database (X,R) be made of CW-complexes (or simplexes, or something
else)? Or, what would be the place of CW-complexes in the database?

Ok, these are the things off the top of my head that may be asked from the
point of view of a practitioner (from a theoretical point of view, the paper
looks sound to me and, as I said, the underlying idea is appealing).

Nicola


--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Norbert_Paul]

Nicola wrote:
> I'd like to start a new thread about the topological extension of RA
> proposed
> by Norbert Paul in this group last January. First of all, let me say that I
> find the idea of representing a topology relationally through the
> specialization preorder quite attractive for its simplicity. And let me add
> that my knowledge of topology is very weak, so please be patient with me.

I appreciate being noticed, so, of course, I will be patient.

> Before I make a few comments, I think that there are a couple of things
> to be
> corrected, one in the paper and one in a previous post:
>
> 1. Example 6.7 from the paper contains a small mistake. The example says
> that,
> given a topological database (X={a,b,c,d}, R={(a,c),(a,d),(c,b),(d,b)}),
> the
> subspace topology on {a,b} does not contain {b}. But the topology
> generated by
> R is {∅, {a,b,c,d}, {b,c,d}, {b,c}, {b,d}, {b}}, so the subspace on
> {a,b} is
> {∅, {a,b}, {b}}, which contains {b}. The subspace is correctly generated
> by R+
> ∩ {a,b}^2 = {(a,b)}, but not by R ∩ {a,b}^2 = ∅, so the point of the
> example
> (the necessity of computing the transitive closure) is valid anyway.

We have adopted the convention that a topology-defining relation
a R b should be read as b is in the closure of {a}.
This convention is arbitrary.
With this convention {a} is open and, hence member of the topology
and {b} is not open (it is closed). If you transpose the incidence
relation (or use the other convention) {a} is closed and {b} is open.

Note that the example only /illustrates/ the necessity of computing
the transitive closure and does not yet prove it.

> 2. Norbert made an example using the following instances (copied from a
> previous post):

[...]

> Regarding this example, could you provide a geometric intuition about
> how this
> space is organized (ASCII art would be ok)? I understand (S,RS), but
> (D,RD) is
> not clear to me (let alone the join - see below): it seems to me that there
> are too many surfaces and too few relationships.

(S,RS)

---int-------------+----------ext---
door
interior xdoor exterior

door is the common boundary of int and ext. It is of type xdoor.

You are right, there is an error. I hope, you are patient.
I also thought of the tuple

RD(interior,interior, surfacex|,xdoor)

which should express, that an xdoor has one surface
towards the interior of the building. I forgot to put it into
RD. With this tuple in mind (but not in the post, I admit) I constructed
the result.

When you recalculate with the above tuple added to RD then you should
get my result. Note that the xdoor will always be added with correct
orientation: Interior surface towards cozy interior and (weathered)
exterior surface towards rain and sunlight stress.

> That said, the main issue I have with the approach (which others have
> raised,
> too) is one of interpretability. Topological select (i.e., subspace) is
> intuitive, but Cartesian product (i.e., space product), hence join, is not.
> Group by (i.e., quotient space) even less. I mean, I understand the
> constructs, but I do not clearly see how useful they might be in practice
> (people in BIM do not work with Klein bottles that often, I guess). It

Not that often, indeed:
http://en.wikiarquitectura.com/index.php/Klein_Bottle_House

Cartesian product is generalized extrusion:

*-----------*
|\ |\
| \ | \
* | *-----------*
| | | | |
| *-----------* *--|--------* |
| x \ \ = \ | \ |
| \ \ \| \|
* *-----------* *-----------*

CAD Macro-Objects (BLOCKs in AutoCAD) can be considered special
cases of join.

> may be
> that the topological algebra is even too expressive for practical purposes:
> for example, I can imagine that a useful operation might be "zooming", or a
> change in granularity, where you have a topological space containing a
> point x
> and you replace x by embedding another topological space (modeling the
> parts x is made of). I am not sure whether "glueing" is the correct term
> for
> it. I think that select (or difference) and union alone may achieve that.

The (S,RS) and (D,RD) example should illustrate "change in granularity".
(S,RS) is the coarser (less granular) view on (S,RS)JOIN(D,RD).
Topological projection is "zooming out" (with a grain of salt).

Union and pasing are different notions but very closely related:
Pasting is a quotient of a disjoint union. In special cases
union alone is already a pasting. Disjoint union alone is a
pasting: It has the attaching map f:{} -> Y.

Replacing x by embedding another object is exactly the application I have
in mind for the natjoin.

> Second, in the example above, the join is made on a detail attribute
> (that is,
> not on a key). Would a join on key attributes between two topological
> databases be meaningful? Intuitively, you would keep the points that
> belong to
> both spaces and combine their topology through product... How would you
> interpret the result? Would it make sense to think about it as building a
> space with more dimensions (e.g., one space gives the topological relations
> among points on axis x, the other on axis y, and the join would build
> 2-dimensional objects)?

The axis example is Cartesian product, a special case of join:
The X-axis has key attribute "x" and the Y-axis has key attribute "y".
The join has Key {"x","y"}.

I don't know if equi-join on key attributes is meaningful. I initially
wanted to carry out topological constructions with database queries.
Only later did I find out, that the basic query operators themselves
can be turned into topological constructions. It now may turn out that
some do not have obvious applications (yet) but the operators are just
there and maybe they are of use.

At the first glance, an equi-join on keys looks to me as if it essentiallly
was an intersection. Note that intersection is a natjoin on superkeys.

> Third, something that is not mentioned in the paper is how you would
> perform
> computations with the topological algebra, e.g., answer topological queries
> such as: "give me all objects that overlap this region". Say, you have a
> topological database (X,R): how do you formulate the previous query (and
> how
> do you model the region of interest)?

"Overlap" involves geometry. I started to work on that but it still is
an open issue. Assuming you have an "INTERSECTS" predicate for tuples the
OVERLAP query is a mere selection

THETA(a) := INTERSECTS(a,this_region) .

> Fourth, the example above mentions real objects (doors, gardens, ...).
> But in
> the paper a significant amount of space is devoted to CW-complexes
> (which I am
> not sure I have understood yet). In a "real" application, would the X in a
> topological database (X,R) be made of CW-complexes (or simplexes, or
> something
> else)? Or, what would be the place of CW-complexes in the database?

We started our work with CW complexes. They have the handy property of
giving orientation (front/rear side, starting/ending vertex, etc) to
elements. This is an important property. However, we found out, for example,
that an OVERLAP query sometimes gives strange (but formally consistent)
orientations:

https://www.researchgate.net/profile/Norbert_Paul/publication/259045737_Signed_Simplicial_Decomposition_and_Intersection_of_n-d-Polytope_Complexes/links/543c15a80cf204cab1db7269.pdf

Note the last sentence in "4 Simplex Intersection"

I think of complexes as an optional feature for relational representations
of spatial objects. It is an important feature but there are still open
issues.

> Ok, these are the things off the top of my head that may be asked from the
> point of view of a practitioner (from a theoretical point of view, the
> paper
> looks sound to me and, as I said, the underlying idea is appealing).

Thanks. There is still much to do. However, I had to quit that buiness.

> Nicola
Norbert

[Tegiri Nenashi]

I wonder if representing topology with binary relations has been investigated. Naively, topology is just a binary relation, that is a bunch of ordered pairs (set_of_points, set_closure). Assuming that algebra of binary relations is good fit for topology, then relations with named attributes (database relations) most likely aren't.

Here is a paper reinforcing that intuition:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.2459&rep=rep1&type=pdf

[Norbert_Paul]

Tegiri Nenashi wrote:
> I wonder if representing topology with binary relations has been investigated.

It has. I did it.

> Naively, topology is just a binary relation, that is a bunch of ordered pairs (set_of_points, set_closure).

Well, this is not so naive:

Every topology T for a point set X can be expressed by
a binary relation between X and PX, where PX is the power set of X:

There are even some alternatives:

INT \subseteq X \times PX = { (p,A) | p \in int A } -- the interior
CL \subseteq X \times PX = { (p,A) | p \in cl A } -- the closure

Those relations must then satisfy certain axioms, that can be derived from the
definition of interior and closure and the properties of a topology.

A special class of topologies can be expressed by a binary relation on the point sets only:
CL \subseteq X \times X = { (p,q) | p \in cl {q} } -- the closure
This is exactly my approach. Only that I use the relation transposed:
(p,q) q \in cl{p}.
and that I have observed, that any relation R will do. CL is then the transitive and
reflexove closure: CL = R^*.

Those topologies are nowadays called Alexandrov topologies.

> Assuming that algebra of binary relations is good fit for topology, then relations with
> named attributes (database relations) most likely aren't.

I don't get that point. What objections are against the names "1" and "2", (or, maybe "one" and "two").

> Here is a paper reinforcing that intuition:
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.2459&rep=rep1&type=pdf

No. This is Egenhofer's "Topological Relations" approach. It is completetly different.

[Nicola]

On 2015-12-10 15:54:21 +0000, Norbert_Paul said:

>
> I also thought of the tuple
>
> RD(interior,interior, surfacex|,xdoor)
>
> which should express, that an xdoor has one surface
> towards the interior of the building.

That is already in RD.

>
> When you recalculate with the above tuple added to RD then you should
> get my result.

I don't, but I'll double-check tomorrow.

> Note that the xdoor will always be added with correct
> orientation: Interior surface towards cozy interior and (weathered)
> exterior surface towards rain and sunlight stress.

Are xdoor and idoor parts of the same door?

interior-----idoor xdoor-----exterior
|---door---|

If so, how can xdoor have a surface in contact with the interior? Could
you draw a diagram for (D,RD)?

>
>> may be
>> that the topological algebra is even too expressive for practical purposes:
>> for example, I can imagine that a useful operation might be "zooming", or a
>> change in granularity, where you have a topological space containing a
>> point x
>> and you replace x by embedding another topological space (modeling the
>> parts x is made of). I am not sure whether "glueing" is the correct term
>> for
>> it. I think that select (or difference) and union alone may achieve that.
>
> The (S,RS) and (D,RD) example should illustrate "change in granularity".
> (S,RS) is the coarser (less granular) view on (S,RS)JOIN(D,RD).
> Topological projection is "zooming out" (with a grain of salt).

Ok, intuitively that may make sense. I can't see that in the example, but
again, that is because I am not able to visualize it yet.

> "Overlap" involves geometry. I started to work on that but it still is
> an open issue. Assuming you have an "INTERSECTS" predicate for tuples the
> OVERLAP query is a mere selection
>
> THETA(a) := INTERSECTS(a,this_region) .

Shouldn't you be able to recover all the topological relations between
objects from a topological database? I think that the point of encoding
the topology in a relation is exactly to avoid the need for additional
predicates like INTERSECTS.

The problem I am considering is this: you are given a topological database
(X,R) and an open (or closed) set A (a subset of X). What are the open sets
that [overlap|contain|are inside|...] A? What is the closure/boundary of A?
In principle, you should be able to answer those queries because R encodes
the topology of the space, shouldn't you? It is not clear to me, however,
how you would represent the output: it would be nice if it would always be
a topological (sub)space (hence, as a topological database). Another
question is how you can compute the output from R (or R*) directly, without
building a topology explicitly. Is this a direction that you have explored?

[Norbert_Paul]

Nicola wrote:
> On 2015-12-10 15:54:21 +0000, Norbert_Paul said:
>
>>
>> I also thought of the tuple
>>
>> RD(interior,interior, surfacex|,xdoor)
>>
>> which should express, that an xdoor has one surface
>> towards the interior of the building.
>
> That is already in RD.
>>
>> When you recalculate with the above tuple added to RD then you should
>> get my result.
>
> I don't, but I'll double-check tomorrow.
>
>> Note that the xdoor will always be added with correct
>> orientation: Interior surface towards cozy interior and (weathered)
>> exterior surface towards rain and sunlight stress.
>
> Are xdoor and idoor parts of the same door?
>
> interior-----idoor xdoor-----exterior
> |---door---|
>
> If so, how can xdoor have a surface in contact with the interior? Could
> you draw a diagram for (D,RD)?

Actually, I never thought of visualizing (D,RD). The space (D,RD) contains the
details that can be used (a "details library") with all connections within a
detail ("intra-detail" connections) and, in addition, the potential connections
between different details ("inter-details" connections).

Let me try:

interior ---------------------------------------+
| | |
| | v
| +-----> surface1| <--- idoormat --> surface2|
| :<-------------idoor ----------------->:
|
+--------> surfacex| <--- xdoormat --> surface|| <--- exterior
:<-------------xdoor ----------------->:


The idea was that you can only choose a detail from the library
to replace some "x" in your database if all connections to and from x
in the space where 2x" lives are represented in the details library.
For example, if you want to carry out road planning and have a crossing
x between two highways you cannot choose a traffic light crossing
for x because in the details library there are no highways that are
connected to a traffic light crossing - you can only choose among
interchanges.

Yes, I misunderstood. Within a topological database you can carry out all of
these queries for subsets of the point set. I thought you wanted overlap in
the geometrical representations of different spaces.

> The problem I am considering is this: you are given a topological database
> (X,R) and an open (or closed) set A (a subset of X). What are the open sets
> that [overlap|contain|are inside|...] A? What is the closure/boundary of A?
> In principle, you should be able to answer those queries because R encodes
> the topology of the space, shouldn't you? It is not clear to me, however,

I have made an SQL-experiment with Egenhofer's 9-intersections concept (which
also falsifies some statements) which does that.


A set A is open in (X[id], R[p,dp]), when it satisfies:

All t in R with t.dp in A satisfy: t.p in A .

The isOpen(A) pedicate (not tested):

NOT EXISTS(
SELECT t.p
FROM R t, A
WHERE t.dp = A.id
AND t.p NOT IN(SELECT id FROM A))

alternatively (also not tested):

NOT EXISTS(
SELECT t.p
FROM R t JOIN A ON (t.dp = A.id)
WHERE t.p NOT IN(SELECT id FROM A))

I have made CLOSURE, INTERIOR and BOUDARY queries in SQL (in the above
mentioned experiment). These are code snippets. They have been
tested with
PostgreSQL 8.4.17 on a Debian Squeeze box with Linux 2.6.32-5-686:

---------------%<---------------%<---------------
create table X(id integer not null primary key);
create table R(
ida integer not null,
idb integer not null,
primary key(ida,idb),
foreign key(ida) references X,
foreign key(idb) references X);

--------------->%--------------->%---------------
[... some code omitted ...]
---------------%<---------------%<---------------

-- Subset A:

create table A
( id integer not null primary key,
foreign key(id) references X);

create view intA(id) as -- interior of A
select A.id from A
where not exists
(select poR.ida from poR
where poR.idb = A.id
and poR.ida not in (select id from A));

create view clA as -- closure of A
select distinct X.id from X, poR, A
where X.id=poR.idb and poR.ida=A.id;

create view bdA as -- boundary of A
select clA.id from clA
where clA.id not in (select id from intA);

create view extA as -- exterior of A
select X.id from X
where X.id not in (select id from clA);

--------------->%--------------->%---------------

Note: The foreign key from A to X forces
A to be a subset of X.

> how you would represent the output: it would be nice if it would always be
> a topological (sub)space (hence, as a topological database). Another
> question is how you can compute the output from R (or R*) directly, without
> building a topology explicitly. Is this a direction that you have explored?

The idea is to extend the query language, say SQL:

create table X(id, .., say, color, ...);
create table R(a,b, FK(a) REF(X.id), FK(b) REF(X.id));
create space spX(X POINTS, R TOPOLOGY(a,b));

The you have ordinary tables, Spaces and can do:

SELECT color FROM X WHERE Stuff;

to get an ordinary result table or you do

SELECT color FROM spX WHERE Stuff;

to get a result /space/.

With object oriented programming (I used CLOS) you can dispatch the
application of a query operator to either the spatial or the ordinary
table method. Note that CLOS dispatches according to /all/ arguments
not only to the first ("implicit" in Java or C++) argument.

When you mix spaces with ordinary tables the tables can be converted
into discrete spaces by trivial wrappers:

This is copied from my prototype (and tested):

---------------%<---------------%<---------------
;;; This makes DIFFERENCE applicable both for spaces and for relations:
(defmethod difference-qop ((space-1 relational-space) (space-2 relational-space))
;; delegate to (space relation):
(difference-qop space-1 (space-points space-2)))

(defmethod difference-qop ((rel relation) (sp relational-space))
;; delegate to (relation relation):
(difference-qop rel (space-points sp)))

(defmethod difference-qop ((sp relational-space) (rel relation))
;; First delegate to (relation relation) and then compute the subspace:
(subspace-qop sp (difference-qop (space-points sp) rel)))
--------------->%--------------->%---------------

difference-qop(relation relation) then actually carries out work and is
defined somewhere else.

.

> Nicola

Norbert

[Norbert_Paul]

[Norbert_Paul]

OOPS!

Norbert_Paul wrote:
> ---------------%<---------------%<---------------
> create table X(id integer not null primary key);
> create table R(
> ida integer not null,
> idb integer not null,
> primary key(ida,idb),
> foreign key(ida) references X,
> foreign key(idb) references X);
>
> --------------->%--------------->%---------------

I forgot to mention that poR is the partial order view on R:

create view poR as
... a query which in general might use "WITH RECURSIVE" ... ;

[Norbert_Paul]

Norbert_Paul wrote:

> Tegiri Nenashi wrote:
>
>> Here is a paper reinforcing that intuition:
>> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.2459&rep=rep1&type=pdf
>>
>
> No. This is Egenhofer's "Topological Relations" approach. It is
> completetly different.

I Took a closer look at the paper. This seems to be one from the RCC8 community:
Note that the classical
"Note that PO,TPP,TPP^T, NTPP, NTPP^T, EC, DC, 1' are
pairwise disjoint, and their sum is 1."
appears on Page 6.

The abstract of
http://www.spatial.maine.edu/~max/RaBTR.pdf
mentions "the eight fundamental topological relations".

It always astonishes me that both communities, RCC8 and Egenhofer, have
extremely similar concepts but almost never does one group cite papers from
the other group. The above paper does not even mention Egenhofer.

So this looks like two rivaling research communities

"Topological Relations" vs. RCC8

working on the same topic, and I am sure they know from each other.

[Nicola]

> Tegiri Nenashi wrote:
>
>> Assuming that algebra of binary relations is good fit for topology,
>> then relations with
>> named attributes (database relations) most likely aren't.
>
> I don't get that point. What objections are against the names "1" and
> "2", (or, maybe "one" and "two").

I too don't fully understand it. You have commented in the past that
the theory of multivariate relations
does not generalize the theory of binary relations. While this is true
in the sense that some operations,
such as transitive closure, cannot be extended (at least, not
straightforwardly), I do not see what
prevents you from using relation algebra (not relational algebra!) in
the context of multivariate
relations, i.e., in databases, as a proper closed subsystem. Is it negation?

[Tegiri Nenashi]

This was a sentiment far from rigorous proposition. People who are aware of Tarski&Givant "A formalization of set theory without variables" would point out that certainly a parallel between binary relations and predicate calculus (and, therefore, database theory) is well established. I will concede this point for now, and just agree that binary relations provide convenient middle ground to meet.

Now, binary relations might provide a vehicle to get Norbert Paul's theory more accessible. For example what is topology in terms of adjacency relation? What queries topological method allows to express which are not expressible with the help of adjacency relation?

[Norbert_Paul]

Tegiri Nenashi wrote:
> On Friday, December 11, 2015 at 4:02:49 AM UTC-8, Nicola wrote:
>>> Tegiri Nenashi wrote:
>>>
>>>> Assuming that algebra of binary relations is good fit for topology, then relations with named attributes (database relations) most likely aren't.
>>>
>>> I don't get that point. What objections are against the names "1" and "2", (or, maybe "one" and "two").
>>
>> I too don't fully understand it. You have commented in the past that the theory of multivariate relations does not generalize the theory of binary relations. While this is true in the sense that
>> some operations, such as transitive closure, cannot be extended (at least, not straightforwardly), I do not see what prevents you from using relation algebra (not relational algebra!) in the
>> context of multivariate relations, i.e., in databases, as a proper closed subsystem. Is it negation?
>
> This was a sentiment far from rigorous proposition. People who are aware of Tarski&Givant "A formalization of set theory without variables" would point out that certainly a parallel between binary
> relations and predicate calculus (and, therefore, database theory) is well established. I will concede this point for now, and just agree that binary relations provide convenient middle ground to
> meet.

Just to clarify: A topological space (X,T) is composed of an /arbitrary/ set X
with a topology T. X can also be the set of records in a relational databas table
with /arbitrary/ arity. If T is represented by a binary relation R on X it should
be modelled accordingly with all reedom relational database design gives you.

> Now, binary relations might provide a vehicle to get Norbert Paul's theory more accessible. For example what is topology in terms of adjacency relation? What queries topological method allows to
> express which are not expressible with the help of adjacency relation?

Again, given a set X with a binary relation R on X (hence R is a subset of X x X).
Then

T(R) := { A is subset of X | every x R a with a in A satisfies x in A }

is a topology for X. This is the "topology in terms of R". Every topology T for a
finite set X (say, of database records in a table X) has such a relation R such
that T(R) = T (There are infinite cases, too).

So for finite sets /everything/ that is "topological" can be expresse with such a
binary relation. If it cannot it is not topological (in the mathematical meaning).

[Tegiri Nenashi]

Egenhofer's approach seems to be sharper than RCC8. For one thing, there is no muddling the water mereologic stuff. Therefore, let's focus on Egenhofer's approach. Can you please expand on differences of your method with Egenhofer's (aside the database angle)?

[Tegiri Nenashi]

On Friday, December 11, 2015 at 9:30:06 AM UTC-8, Norbert_Paul wrote:
> Tegiri Nenashi wrote:
> > On Friday, December 11, 2015 at 4:02:49 AM UTC-8, Nicola wrote:
> >>> Tegiri Nenashi wrote:
> >>>
> >>>> Assuming that algebra of binary relations is good fit for topology, then relations with named attributes (database relations) most likely aren't.
> >>>
> >>> I don't get that point. What objections are against the names "1" and "2", (or, maybe "one" and "two").
> >>
> >> I too don't fully understand it. You have commented in the past that the theory of multivariate relations does not generalize the theory of binary relations. While this is true in the sense that
> >> some operations, such as transitive closure, cannot be extended (at least, not straightforwardly), I do not see what prevents you from using relation algebra (not relational algebra!) in the
> >> context of multivariate relations, i.e., in databases, as a proper closed subsystem. Is it negation?
> >
> > This was a sentiment far from rigorous proposition. People who are aware of Tarski&Givant "A formalization of set theory without variables" would point out that certainly a parallel between binary
> > relations and predicate calculus (and, therefore, database theory) is well established. I will concede this point for now, and just agree that binary relations provide convenient middle ground to
> > meet.
>
> Just to clarify: A topological space (X,T) is composed of an /arbitrary/ set X
> with a topology T. X can also be the set of records in a relational databas table
> with /arbitrary/ arity. If T is represented by a binary relation R on X it should
> be modelled accordingly with all reedom relational database design gives you.

Are you saying that your contribution is introducing topological datatype? (This would answer Nicola's question why do you need special functions like INTERSECT as opposed to being able to reduce it to logical operator of relational algebra). Please note that in this case the term "topological databases" becomes a little misleading.

> > Now, binary relations might provide a vehicle to get Norbert Paul's theory more accessible. For example what is topology in terms of adjacency relation? What queries topological method allows to
> > express which are not expressible with the help of adjacency relation?
>
> Again, given a set X with a binary relation R on X (hence R is a subset of X x X).
> Then
>
> T(R) := { A is subset of X | every x R a with a in A satisfies x in A }
>
> is a topology for X. This is the "topology in terms of R". Every topology T for a
> finite set X (say, of database records in a table X) has such a relation R such
> that T(R) = T (There are infinite cases, too).
>
> So for finite sets /everything/ that is "topological" can be expresse with such a
> binary relation. If it cannot it is not topological (in the mathematical meaning).

A [binary] relation induces Galois Connection and closure operator. It doesn't necessarily satisfy union axiom
http://mathoverflow.net/questions/35719/when-does-a-galois-connection-induce-a-topology
There are several ways to generate a topology from given binary relation
http://www.emis.de/journals/BMMSS/pdf/v31n1/v31n1p4.pdf

This is interesting stuff indeed.

[Nicola]

On 2015-12-11 17:39:15 +0000, Tegiri Nenashi said:

> Can you please expand on differences of your method with Egenhofer's
> (aside the database angle)?

Norbert may have better arguments, but what I find it intriguing in his
approach is that you store
the *whole* topology of the *whole* space potentially in a cheap and
simple way. As far as I know,
in DE-9IM (based on Egenhofer's ideas) you may model the relationship
between two objects with one
3x3 matrix, but storing a matrix for each possible pair of objects (or
for a subset big enough to
reconstruct the whole topology) is most likely impractical. Hence, such
matrices are usually used
to infer the topological relationships between objects from geometric
data (e.g., see
ST_Relate() in SQL/MM). Besides, Norbert's model provides a way to
build new topological spaces
from existing ones using well-founded well-known constructions. This is
a feature I have not seen
elsewhere (not that I know all models out there, though). It might
still be infeasible in practice,
given that there are transitive closures to compute here and there, but
it has some potential.

Btw, I have found that this paper provides a less formal but way more
accessible introduction to the
topic:

https://www.academia.edu/364355/Geometrical_and_Topological_Approaches_In_Building_Information_Modelling

[Tegiri Nenashi]

On Friday, December 11, 2015 at 10:33:48 AM UTC-8, Tegiri Nenashi wrote:
> A [binary] relation induces Galois Connection and closure operator. It doesn't necessarily satisfy union axiom
> http://mathoverflow.net/questions/35719/when-does-a-galois-connection-induce-a-topology
> There are several ways to generate a topology from given binary relation
> http://www.emis.de/journals/BMMSS/pdf/v31n1/v31n1p4.pdf

Perhaps people are bewildered what Galois Connection has to do with it. One particular way by which Galois connections often arise is relation-generated. It involves posets -- powersets of some set X and Y, induced by a relation R between the elements of the original X and Y. Galois's original example
was of this kind. Wille's Formal Concept Analysis is about relation-generated Galois Connections too.

Now what about closure operator induced by relation-generated Galois Connection? It is still not necessarily Kuratovski closure. Counterexample:

X={a,b,c}
Y={1,2,3}
R={(a,1),(a,3),(b,3),(c,2),(c,3)}

cl({a}) union cl({c}) = {a,c}
cl({a} union {c}) = {a,b,c}

[Norbert_Paul]

Tegiri Nenashi wrote:
> Egenhofer's approach seems to be sharper than RCC8. For one thing,
> there is no muddling the water mereologic stuff. Therefore, let's
> focus on Egenhofer's approach. Can you please expand on
> differences of your method with Egenhofer's (aside the database angle)?

My approach: A data model to store, construct, and query arbitrary
topological spaces (of arbitrary dimension).

Egenhofer: A set of (mostly) 8 predicates that can only be applied to
pairs of "regular" sets in a topological space (mostly R^2).
(A set is "regular" if it is not empty, not the entire point
set, I guess, and if it is the closure of an open set.)

[Norbert_Paul]

Tegiri Nenashi wrote:
> On Friday, December 11, 2015 at 10:33:48 AM UTC-8, Tegiri Nenashi wrote:
>> A [binary] relation induces Galois Connection and closure operator. It doesn't necessarily satisfy union axiom
>> http://mathoverflow.net/questions/35719/when-does-a-galois-connection-induce-a-topology
>> There are several ways to generate a topology from given binary relation
>> http://www.emis.de/journals/BMMSS/pdf/v31n1/v31n1p4.pdf
>
> Perhaps people are bewildered what Galois Connection has to do with it. One particular way by which Galois connections often arise is relation-generated. It involves posets -- powersets of some set X and Y, induced by a relation R between the elements of the original X and Y. Galois's original example
> was of this kind. Wille's Formal Concept Analysis is about relation-generated Galois Connections too.
>
> Now what about closure operator induced by relation-generated Galois Connection? It is still not necessarily Kuratovski closure. Counterexample:

Topological closure is always Kuratovski closure.
So Galois-connection may be of theoretical (and maybe
even practical) interest but it is not part of my model.

On the v31n1p4.pdf paper:

Def. 2.2: /Every/ set of subsets of a set X is a subbase of a topology for X.

My method of generating a topology from an arbitrary relation R is
similar to case (ii), but instead of R I take its preorder R^*.

[Norbert_Paul]

Nicola wrote:
> Btw, I have found that this paper provides a less formal but way more
> accessible introduction to the
> topic:
>
> https://www.academia.edu/364355/Geometrical_and_Topological_Approaches_In_Building_Information_Modelling
>

Hihi.
Also a bit less formal with respect to orthography :) .

[Tegiri Nenashi]

On Saturday, December 12, 2015 at 4:29:41 AM UTC-8, Norbert_Paul wrote:
> Tegiri Nenashi wrote:
> > On Friday, December 11, 2015 at 10:33:48 AM UTC-8, Tegiri Nenashi wrote:
> >> A [binary] relation induces Galois Connection and closure operator. It doesn't necessarily satisfy union axiom
> >> http://mathoverflow.net/questions/35719/when-does-a-galois-connection-induce-a-topology
> >> There are several ways to generate a topology from given binary relation
> >> http://www.emis.de/journals/BMMSS/pdf/v31n1/v31n1p4.pdf
> >
> > Perhaps people are bewildered what Galois Connection has to do with it. One particular way by which Galois connections often arise is relation-generated. It involves posets -- powersets of some set X and Y, induced by a relation R between the elements of the original X and Y. Galois's original example
> > was of this kind. Wille's Formal Concept Analysis is about relation-generated Galois Connections too.
> >
> > Now what about closure operator induced by relation-generated Galois Connection? It is still not necessarily Kuratovski closure. Counterexample:
>
> Topological closure is always Kuratovski closure.
> So Galois-connection may be of theoretical (and maybe
> even practical) interest but it is not part of my model.

However it is interesting to know how much of topological structure can be taken away (generalized) and the result would still be compatible with relational algebra.

True or false?
Proposition. Let σ : 2^X → 2^X be a map (where 2^X is a powerset of X). Then, the following statements are equivalent.
(1) σ is topological closure operator on X,
(2) σ satisfies Kuratovski axiom, and there is a Galois connection (K, L) which satisfies σ = LK.

[Jan Hidders]

Op maandag 14 december 2015 20:36:52 UTC+1 schreef Tegiri Nenashi:

False, I think. The identity would satisfy always (2) but not necessarily (1).

What *I* am interested in is the connection with this work:

http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf

:-)

Jan Hidders

[Norbert_Paul]

I do not know much about Galois connections, but if identity can be constructed from a
Galois conenction in the above manner then it is not a counter-example.
Identity is the closure operator of the discrete topological space.

> What *I* am interested in is the connection with this work:
>
> http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf
>
> :-)

Looks interesting. I'll take a closer look.

[Jan Hidders]

Op dinsdag 15 december 2015 19:53:47 UTC+1 schreef Norbert_Paul:

Ow, had not realised that. So on any discrete topology, the identity is a closure operator? And in fact the only closure operator?

Jan Hidders

[Norbert_Paul]

Jan Hidders wrote:
>>>> True or false?
>>>> Proposition. Let σ : 2^X → 2^X be a map (where 2^X is a powerset of X). Then, the following statements are equivalent.
>>>> (1) σ is topological closure operator on X,
>>>> (2) σ satisfies Kuratovski axiom, and there is a Galois connection (K, L) which satisfies σ = LK.
>>>
>>> False, I think. The identity would satisfy always (2) but not necessarily (1).
>> I do not know much about Galois connections, but if identity can be constructed from a
>> Galois conenction in the above manner then it is not a counter-example.
>> Identity is the closure operator of the discrete topological space.
>
>
> Ow, had not realised that. So on any discrete topology, the identity is a closure operator? And in fact the only closure operator?
>
> Jan Hidders

Yes, each topological space has its unique closure operator.
Different topologies give different closure operators.

The discrete space: https://nl.wikipedia.org/wiki/Discrete_ruimte
When you have an arbitrary set X, then the power set PX is a topology for X:
Axiom 1: {} in PX, and X in PX
Axiom 2: Every A, B in PX satisfies A \cap B \in PX.
Axiom 3: For every subset S of PX the union \bigcap_{A \in S} S is an element of PX.
The space (X, PX) is called the discrete space of X.

The closure operator of the discrete space is
cl(A) = A for all A subset X ,
hence the identity function id: PX -> PX .

Proof (easy):
Let p be an arbitrary point in cl A. (Assumption)
Then every open set Up that contains p as an
element has a non-empty intersection:
Up \cap A \neq {} (Definition of closure)
Up = {p} is an element of PX (Definition of PX, Instanciation of Up)
Hence {p} \cap A \neq {} (Consequence)
Hence p \in {p} \cap A (YA Consequence)
Hence p in A.
Therefore cl A \subseteq A
As A \subseteq cl A always holds we have:

cl A = A . [qed]

If the closure operator is not the identity function its topological space
is not the discrete space.

Other operators of the discrete space:
Interior: int A = A for all A \subseteq X.
Boundary: bd A = {} for all A \subseteq X.

Norbert

[Jan Hidders]

Op donderdag 17 december 2015 12:53:31 UTC+1 schreef Norbert_Paul:

Cool. Clear. Thank you for that explanation.

Jan Hidders

[Nicola]

On 2015-12-15 16:14:14 +0000, Jan Hidders said:

> What *I* am interested in is the connection with this work:
>
> http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf

Do you mean, with the constraint database model (by Kanellakis et al.)
in general or with the results in that specific paper?

I think that constraint databases might be a nice complement to Norbert's
topological model. They might provide an alternative way to represent the
geometry of cw-complexes, for example. Then, you would encode both
geometric and topological information in a purely relational way.

[Norbert_Paul]

Nicola wrote:
> On 2015-12-15 16:14:14 +0000, Jan Hidders said:
>
>> What *I* am interested in is the connection with this work:
>>
>> http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf
>
> Do you mean, with the constraint database model (by Kanellakis et al.)
> in general or with the results in that specific paper?
>
> I think that constraint databases might be a nice complement to Norbert's
> topological model. They might provide an alternative way to represent the
> geometry of cw-complexes, for example. Then, you would encode both
> geometric and topological information in a purely relational way.

I is funny that you mention complexes.

Actually our (Patrick's and my) initial concept was (after a generalization
of Jan's PLA structure) a data model for complexes:

To model an n-complex we collected i-cells in i-tables:

Cells_n(idn,...)
Cells_[n-1](idm,...)
...
Cells_1(id1,...)
Cells_0(id0,...)

Then we modelled the boundary operator by i-boundary tables
(foreign keys from Bd_i to Cells_i and Cells_j are straightforward):

Bd_n(idn, idm, alpha : integer)
Bd_[n-1](idm, id[m-1], alpha : integer)
...
Bd_1(id1, id0, alpha : integer)

with the restriction that for two consecutive boundary tables Bd_i, Bd_j
with k + 2 = j + 1 = i the predicate
not exists(
select Bd_i.idi, Bd_j.idk
from Bd_i, Bd_j
where Bd_i.idj = Bd_j.idy
group by Bd_i.idi, Bd_j.idk
having sum(Bd_i.alpha * Bd_j.alpha) != 0
)

must be true. Note that the inner select without the "having" clause
carries out matrix multiplication and hence is the composition of
two consecutive (linear) boundary operators. The having clause
only returns non-zero entries. As the boundary of the boundary must be
the zero map, such non-ero entries must not occur in this composition.

We then realized that you can collect all cells into one table X and the
boundary into one another table R and thereby get a point-set topological space
(X, T) associated to the complex and modelled by (X,R). You can then store
the dimension of the cells by a "dim" attribute for X and, eventually, if
"dim" is a key attribute, by two dimension attributes, say, "dim" and "bddim",
in R.

Conversely it is still possible to extend a topological data type (X,R)
by an attribute R.alpha to get a complex. Then you can consider R an square
matrix with index set X and multiply it to itself. When R^2 = 0 (a partial null matrix)
the space is a complex. You can also add dimension attributes if you wish so.

Norbert




















>
> Nicola

[Tegiri Nenashi]

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.

The first question is what are the values of topological datatype. I assume, they are certainly not entire topologies. 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

Here is what projection of this relation to {topological_object} might look like:

topological_object
------------------
Dohnut
Ball

I suspect this is not direction where Norbert is going. For once he considers interactions between two topological spaces (e.g. product topology) and I fail to see how this can be cast in relational terms.

[Tegiri Nenashi]

Here is less sloppy way to express my discomfort.

When describing relational model (and its extensions) you are required to describe the following.

1. What are the objects that we operate with.

In classic relational theory they are -- relations. Next, we describe relation structure in terms of attributes, and tuples.

In Kanellakis generalized relational model the objects are semi-algebraic sets, although the importance of attribute naming is glossed over.

One can also operate algebraic sets (geometric varieties) and their counterparts (algebraic ideals). My impression is that algebraic geometry is far more advanced compared to the theory of semi-algebraic sets.

Please note that in all three cases given a relation, one can easily tell what attributes of that relation are. I'm not sure I can confidently exhibit attributes in the examples provided by Norbert.

2. What are relational operators between the objects.

This is usually accomplished in terms of relations structure, for example natural join in classic relational theory produces a relation with a set of attributes which is the union. Next, the tuples of the resulting relation are constructed as ...

In case of algebraic sets there are operations that mimic classic relational algebra, and this is why such extension of relational model is possible.

In the case of topological extension Norbert listed operations which are counterparts of relational, but those are operations over entire topologies. My understanding is that topology is dimension unaware; so when working with topologies how does one identifies attributes/variables?

[Nicola]

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.

Yes, I think that the extension is quite intuitive. The underlying idea
is very simple: there is a well-known correspondence between a certain
class of topological spaces (Alexandrov spaces), which includes the
finite topological spaces, and the class of preorders (reflexive and
transitive relations). There are effective procedures to build a
preorder on a set X given a topology on X, and vice versa. So, instead
of considering a set X with a topology T, i.e. a topological space
(X,T), one may equivalently use X equipped with a preorder P induced by
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*.

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

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

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

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

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.

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

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

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

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

[Norbert_Paul]

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.

You can also mimic an attribute domain of topological databases by
means of disjoint sum of spaces. (See below)

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.

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

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
Each tuple (object, id1, id2) is an association
(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

[Nicola]

On 2015-12-19 11:14:52 +0000, Norbert_Paul said:
>>
> 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

Ah, right.
I had written a slightly different example in a first draft of my post,
and then changed it. But I forgot to update the topology and the remark
about the open/closed edges.

Thanks for the correction!

[Nicola]

On 2015-12-19 11:14:52 +0000, Norbert_Paul said:

> 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

The term "relation" is used to denote

A. a mathematical relation (the subset of a Cartesian product);
B. a named relation (a set of tuples);
C. an association defined by foreign keys.

Although it is clear from the context what you mean, calling R1
a "binary relation" (in the sense C) is a bit confusing because
R1 is a relation of degree 3 (in the sense B). On the other hand,
R1 represents a specialization preorder, which is a binary relation
(in the sense A). In this specific example "binary relationship" or
"binary association" might be a better term.

In general, I wish that we could use a less ambiguous terminology,
especially to distinguish between A and B (but I am not fond of
"relvar"...).

[Tegiri Nenashi]

Agree: "Relvar" is just awful.

1. Mathematical relations are indeed binary relations (with "anonymous" attributes).

2. Relational database theory studies relations with named attributes. Although there is named vs. unnamed perspective described in very beginning of the Alice book, it is the named perspective that reigns supreme in database practice. Please also note that "unnamed" perspective is not really "unnamed" -- it is better called "indexed", where attribute names are natural numbers.

The proper name for a relation with named attributes is "multivariate relation". As our discussion have already touched semi-algebraic sets, this motivation for that name
https://vadimtropashko.wordpress.com/2014/01/02/relations-as-finite-varieties
would be not entirely out of place.

3. Association defined by foreign key is not a relation. It is a "relationship", at best. Formally, it is a constraint, which is quite easy to formulate algebraically. It can even be expressed as equality, e.g.
https://www8.cs.fau.de/_media/litak:rellat-jlamp-final.pdf (page 2)


Getting back to discussion of topology, I agree that fibre product corresponds to natural join. Spivak is saying the same thing in his "Categorical databases". And if you know what join operation is, then you have nailed half of relational algebra (cartesian product, selection, set intersection).

I still don't get the idea that topology can be viewed as [multivariate] relation. Your example shows a database schema that formally describes topology via CW-complexes. This is "implementation" (also known in religious database community as "physical level"). As you and Norbert have already explained, this topology is considered to be topological datatype on logical level. Then, I don't see how Norbert's topolology - relational algebra dictionary is relevant. For example, to compute natural join of relation FavoriteShapes(person, topology) with ShapeCosts(topology, price) the only thing we care about is identity of topologies. It seems to me that in order to leverage Norbert's topolology - relational algebra dictionary one needs to declare that topological object (topological space) is more general than relation. For example, ordinary [multivariate] relations are some trivial topologies. Next, if we have mixed information in a relation (like in FavoriteShapes), then just by examining the topology we can reconstruct:
1. How many attributes are there
2. What are non-topological attributes
3. What are the values of non-topological attributes

[vadi...@gmail.com]

On Tuesday, December 15, 2015 at 8:14:17 AM UTC-8, Jan Hidders wrote:
> What *I* am interested in is the connection with this work:
>
> http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf

Do you prefer to work with algebraic or semi-algebraic constraints?

Here is how Heath's theorem from database dependency theory is made obvious in algebraic settings. Basically we have:
1. A system of constraints in 3 variables x,y,z
2. A function x->y
We need to reorganize the system's constraints into two parts: the ones expressed in variables x and y only, on one hand, and the other in x and z. For the first system we take the equation that defines the active domain x together with the equation that explicitly defines FD x->y. For the second system, we take the whole original system, and eliminate y by substitution its formula in terms of x.
https://vadimtropashko.wordpress.com/2014/01/03/analytic-view-of-functional-dependency/

I struggle to prove Heath's theorem for semialgebraic sets. For example, is it possible to have functional dependency which is a function but not expressible polynomially?

[Norbert_Paul]

Nicola wrote:
> On 2015-12-19 11:14:52 +0000, Norbert_Paul said:
>
>> 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
>
> The term "relation" is used to denote
>
> A. a mathematical relation (the subset of a Cartesian product);
> B. a named relation (a set of tuples);
> C. an association defined by foreign keys.

OK, but (roughly) A = B = C:

(A) is a set of tuples.
B and C are, in the mathematical sense, just families of relations.
(B)
R \subset D1 \times D2 \times D3 may be called "unnamed" relation.
Then the pair nR := (name, R) may be a "named" relation.
The "named" membership t \in nR is defined by t \in nR := t \in R.
A set DB := { (n1, R1), (n2, R2), ...,(nm, Rm) } of "named" relations
is a set of pairs, hence, a set of tuples, hence a relation.
One might then wish, that the name uniquely determines the relation.
Then DB is a (partial) funtion from names to relations. Note that
functions are only special cases of relations.
(C)
An association defined by foreign keys is the usual way of expressing
a realtion on another relation in database modelling. It just consists
of a set of relations that are designed to express yet another relation
(the "association"). So there are the relations involved in the model
(implementation) and then there is the resulting relation ("association")
that the database practitioner wanted to express. But these are all
"relations".

> Although it is clear from the context what you mean, calling R1
> a "binary relation" (in the sense C) is a bit confusing because
> R1 is a relation of degree 3 (in the sense B). On the other hand,
> R1 represents a specialization preorder, which is a binary relation
> (in the sense A). In this specific example "binary relationship" or
> "binary association" might be a better term.

R1 "is" a relation of degree 3 on its domains, say, integer, integer, integer.
The "foreign key" clauses reinterpret that into a relation of degree 2
(hence, "binary") on PART.

> In general, I wish that we could use a less ambiguous terminology,
> especially to distinguish between A and B (but I am not fond of
> "relvar"...).

The terminology is OK. "relation" is a generic mathematical notion with
many practical applications.

Norbert

[Jan Hidders]

Op zondag 20 december 2015 10:27:17 UTC+1 schreef vadi...@gmail.com:

In principle yes, but that was already the case in the algebraic setting where it is also not a priori the case that all functional dependencies are expressible by a polynomial, unless that is how you define them, as you apparently do. You are anyway looking here at restricted classes of relations and dependencies, so it's up to you to say how you want to restrict them.

-- Jan Hidders

[Jan Hidders]

Op vrijdag 18 december 2015 17:15:53 UTC+1 schreef Nicola:

> On 2015-12-15 16:14:14 +0000, Jan Hidders said:
>
> > What *I* am interested in is the connection with this work:
> >
> > http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf
>
> Do you mean, with the constraint database model (by Kanellakis et al.)
> in general or with the results in that specific paper?

Both, really.

In my mind (but I have not fully wrapped my head around it yet) Norbert's proposal amounts to proposing a special new domain (or rather a class of domains) with some special predicates such as "is contained in" and "is a border of", and operators that seem similar to those of the relational algebra. In addition he has a special new aggregation operators (such as generalized union and generalized intersection) that can aggregate bags of values of that domain again into a value of that domain. The results of the references paper help us understanding to what extent such operators would actually be computable.

Btw. I'm not sure why it would be such a big deal that the operators of this domain are similar to relational algebra operators. What practical benefit would come from that? Would that make things easier for an optimizer? For human beings trying to specify / understand a query? I don't see that at the moment.

About constraint databases: when allowing in this new (class of) domain(s) any set of points that can be defined in some appropriate constraint language, the idea would actually start to make more sense to me. Of course the relations defined by constraints would the be domain values, and not necessarily top-level relations as they usually are in the literature, but that I do not consider a fundamental problem.

-- Jan Hidders

[vadi...@gmail.com]

There is no requrement for functional dependency to be polynomial -- this has been inferred. Let me explain why it is not a vacuous statement. I can easily see how a reader can be confused, because first I say that a relation is a system of polynomial conatraints, and then go on to discuss constraints of another kind: database dependencies. The fact that one can express functional dependency as a explicit polynomial expression is not a trivial consequence of the fact that we have polynomial system. One has to refer to polynomial interpolation as a method to recover this expression, at least, because this function was originally not in the constraint system. It suddenly appeared when I calculated Grobner basis in this particular example. In general case, it existence follows from inerpolation.

There is more to the idea of constraint databases in algebraic perspective. One really has to study ideals, not varieties. Please note that geometrically ideals formally describe roots of polynomial system together with their multiplicities. Essentially, we have coherent theory of multisets (relations with duplicate tuples).

Finally, it is easy to see how researchers with logic and set theory background are not convinced. It requires to become versatile with topics they have probably have forgotten since their undegraguate school time. However, please note that semi algebraic methods promoted by Kannecalis require even more sophisticated machinery. Ideals, Varieties, and Grobner Basis is so well established that are taught at undergraduate level today. Semialgebraic geometry and Sturm method are not.

[Jan Hidders]

Op maandag 21 december 2015 17:30:20 UTC+1 schreef vadi...@gmail.com:

> On Monday, December 21, 2015 at 4:24:36 AM UTC-8, Jan Hidders wrote:
> > Op zondag 20 december 2015 10:27:17 UTC+1 schreef vadi...@gmail.com:
> > > On Tuesday, December 15, 2015 at 8:14:17 AM UTC-8, Jan Hidders wrote:
> > > > What *I* am interested in is the connection with this work:
> > > >
> > > > http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf
> > >
> > > Do you prefer to work with algebraic or semi-algebraic constraints?
> > >
> > > Here is how Heath's theorem from database dependency theory is made obvious in algebraic settings. Basically we have:
> > > 1. A system of constraints in 3 variables x,y,z
> > > 2. A function x->y
> > > We need to reorganize the system's constraints into two parts: the ones expressed in variables x and y only, on one hand, and the other in x and z. For the first system we take the equation that defines the active domain x together with the equation that explicitly defines FD x->y. For the second system, we take the whole original system, and eliminate y by substitution its formula in terms of x.
> > > https://vadimtropashko.wordpress.com/2014/01/03/analytic-view-of-functional-dependency/
> > >
> > > I struggle to prove Heath's theorem for semialgebraic sets. For example, is it possible to have functional dependency which is a function but not expressible polynomially?
> >
> >
> > In principle yes, but that was already the case in the algebraic setting where it is also not a priori the case that all functional dependencies are expressible by a polynomial, unless that is how you define them, as you apparently do. You are anyway looking here at restricted classes of relations and dependencies, so it's up to you to say how you want to restrict them.
>
> There is no requrement for functional dependency to be polynomial -- this has been inferred. Let me explain why it is not a vacuous statement. I can easily see how a reader can be confused, because first I say that a relation is a system of polynomial conatraints, and then go on to discuss constraints of another kind: database dependencies. The fact that one can express functional dependency as a explicit polynomial expression is not a trivial consequence of the fact that we have polynomial system. One has to refer to polynomial interpolation as a method to recover this expression, at least, because this function was originally not in the constraint system. It suddenly appeared when I calculated Grobner basis in this particular example. In general case, it existence follows from inerpolation.

I don't follow you here. In your construction for Heath's theorem you are taking a set of polynomial equations and in them you substitute a variable with a function over the other variables. Are you now claiming that there is always an equivalent set of polynomial equations for this new system, no matter what that function is?

Btw. I find it a bit misleading to call this a proof of Heath's theorem, since in the relational model a functional dependency does not really imply there is a function to derive the dependent value. Also here you are introducing additional restrictions that did not exist in the original relational model.

> Finally, it is easy to see how researchers with logic and set theory background are not convinced.

Not convinced of what, exactly?

-- Jan Hidders

[vadi...@gmail.com]

On Tuesday, December 22, 2015 at 1:49:12 AM UTC-8, Jan Hidders wrote:
> I don't follow you here. In your construction for Heath's theorem you are taking a set of polynomial equations and in them you substitute a variable with a function over the other variables. Are you now claiming that there is always an equivalent set of polynomial equations for this new system, no matter what that function is?
>

When we substitute a polynomial expression into polynomial expression we get yet another polynomial expression. Initially we had a system over x,y,z. We have eliminated y, and have gotten the system over x,z. It corresponds to projection of original relation

[x y z]
1 1 1
2 1 1
3 2 1
3 2 2

to x,z:

[x z]
1 1
2 1
3 1
3 2

The second system consists of the two equations, the one constraining the domain of x, and another is functional dependency itself (in explicit analytical form). It corresponds to relation/finite variety

x=1,y=1
x=2,y=1
x=3,y=2

It is not obvious to me what to do if variety is not finite (generalized relation).

> Btw. I find it a bit misleading to call this a proof of Heath's theorem, since in the relational model a functional dependency does not really imply there is a function to derive the dependent value.

For centuries function has been considered as a set of rules which describes a procedure how to transform an input to output. Mathematicians simply refused to believe in (or saw no purpose for) functions which can't be described via nice analytic formulas. Modern (20th century) treatment is that a function is a relation (set of ordered pairs). Going back to classic treatment (of functions), isn't it cute?

> Also here you are introducing additional restrictions that did not exist in the original relational model.

At the end of the day, theory's worth is determined by what predictions it gives. Cantor set theory would be unnoticed without discovery that transcendental numbers vastly outnumber algebraic ones. Tarski&Givant set theory without variables is still nowhere today because, despite much effort, it doesn't say anything new about sets. As for ideal-variety theory of relations, just two observations (Heath theorem analytic interpretation/proof and multirelations) are running thin on the application side yet.

[Norbert_Paul]

vadi...@gmail.com wrote:
> On Tuesday, December 22, 2015 at 1:49:12 AM UTC-8, Jan Hidders wrote:
>> I don't follow you here. In your construction for Heath's theorem you are taking a set of
>> polynomial equations and in them you substitute a variable with a function over the other
>> variables. Are you now claiming that there is always an equivalent set of polynomial equations
>> for this new system, no matter what that function is?
>>
>
> When we substitute a polynomial expression into polynomial expression we get yet another
> polynomial expression. Initially we had a system over x,y,z. We have eliminated y, and have
> gotten the system over x,z. It corresponds to projection of original relation

To get your point it would be helpful to write down the polynomil expression
and to /explicitly/ specify the transformation rules between polynomial expressions
and their "corresponding" relations.

> [x y z]
> 1 1 1
> 2 1 1
> 3 2 1
> 3 2 2

What does that mean?

1x + 1y + 1z (1 1 1)
+ 2x + 1y + 1z (2 1 1)
+ 3x + 2y + 1z (3 2 1)
+ 3x + 2y + 2z (3 2 2)

or else

x^1 + y^1 + z^1 (1 1 1)
+ x^2 + y^1 + z^1 (2 1 1)
+ x^3 + y^2 + z^1 (3 2 1)
+ x^3 + y^2 + z^2 (3 2 2)

or, mwaybe,

(x^1 + y^1 + z^1) (1 1 1)
* (x^2 + y^1 + z^1) (2 1 1)
* (x^3 + y^2 + z^1) (3 2 1)
* (x^3 + y^2 + z^2) (3 2 2)

or something completetly different?

> The second system consists of the two equations, the one constraining the domain of x, and
> another is functional dependency itself (in explicit analytical form). It corresponds to
> relation/finite variety
>
> x=1,y=1 x=2,y=1 x=3,y=2

So merely a set of three discrete points?
What is so interesting about storing a finite point set
S \subset R^n (or Q^n, or double^n) into an n-ary relation?

[vadi...@gmail.com]

On Wednesday, December 23, 2015 at 2:49:21 AM UTC-8, Norbert_Paul wrote:
> To get your point it would be helpful to write down the polynomil expression
> and to /explicitly/ specify the transformation rules between polynomial expressions
> and their "corresponding" relations.
>
> > [x y z]
> > 1 1 1
> > 2 1 1
> > 3 2 1
> > 3 2 2
>
> What does that mean?
>
> 1x + 1y + 1z (1 1 1)

...

> or else
>
> x^1 + y^1 + z^1 (1 1 1)
> + x^2 + y^1 + z^1 (2 1 1)
> + x^3 + y^2 + z^1 (3 2 1)
> + x^3 + y^2 + z^2 (3 2 2)
>
> or, mwaybe,
>
> (x^1 + y^1 + z^1) (1 1 1)

...
>
> or something completetly different?

It means

x=1,y=1,z=1
x=2,y=1,z=1
x=3,y=2,z=1
x=3,y=2,z=2

Less sloppily it means

x=1 & y=1 & z=1
|
x=2 & y=1 & z=1
|
x=3 & y=2 & z=1
|
x=3 & y=2 & z=2

The polynomial system (of constraints) which roots we have just listed can be written in many ways. The basic idea how to construct it is start with one tuple, which is constrained with a system of three linear equations

x-1=0
y-1=0
z-1=0

and use union of varieties rule to add more tuples. The details:

https://vadimtropashko.wordpress.com/2014/01/02/relations-as-finite-varieties/

> > The second system consists of the two equations, the one constraining the domain of x, and
> > another is functional dependency itself (in explicit analytical form). It corresponds to
> > relation/finite variety
> >
> > x=1,y=1 x=2,y=1 x=3,y=2
>
> So merely a set of three discrete points?

Yes.

> What is so interesting about storing a finite point set
> S \subset R^n (or Q^n, or double^n) into an n-ary relation?

n-ary relation is a finite point set (of roots of multivariate polynomial system). Why is it interesting?
1. If we drop adjective "finite" as in "finite varieties" we'll get generalized relations
2. We can leverage analytic methods as just have been illustrated with proof of Heath's theorem
3. Instead of geometric objects (varieties) we can study dual algebraic objects (ideals). Ideals formalize multi-relations and this is one direction to go. Algebra of ideals is relational lattice (this has not been rigorously proven yet).