Re: A Topological Relational Algebra in Lisp

Tegiri Nenashi wrote:
> On Thursday, January 22, 2015 at 12:20:12 PM UTC-8, Norbert_Paul wrote:
>> .... Note that the bigger
>> ("finer") Tx (or the smaller ("coarser") Ty) the more likely is it that f
>> is continuous.
>
> Which brings up
> http://en.wikipedia.org/wiki/Comparison_of_topologies#Lattice_of_topologies
>
> Similar in spirit construction -- Lattice of Partitions -- is widely used in
> Database Dependency theory http://liris.cnrs.fr/Documents/Liris-6427.pdf
> (fig.2) Partitions are reflexive, symmetric, transitive binary relations.

Interesting, but I didn't want to populate my post too much with text-book material on topology.

>> When you have queries that involve more than one tables, say Y1, Y2, Y3,
>> you may get
>>
>> X = op(Y1,Y2,Y3) with functions f1:X -> Y1, f2:X -> Y2, f3:X->Y3
>>
>> or you get
>>
>> Z = op(Y1,Y2,Y3) with functions g1:Y1 -> Z, g2:Y2 -> Z, g3:Y3 -> Z
>
> I'm not sure why you are focusing here on operations with three operands.
> Relational algebra operators are dyadic, and operations with higher arity are
> composed from basic operations (natural join, projection, union, etc).

I wanted to express by "say" that three is an arbitrary number. (I don't know if three is always arbitrary but here ist is.) Note that topologists even have operations that operate on infinitely many spaces. For example the Cartesian product space may be applied to infinitely many topologies.

> Now, consider
>
> op(Y1,Y2,Y3) = (Y1 join Y2) union Y3
>
> Is the first operations (join) allowed to be of initial type, and the second
> one (union) be of final type?

Of course the above expression gives a meaningful topology. I admit that my wording was not correct. It is the /basic/ operations of Relational Algebra (except outer join) which are always either initial or final. Compound expressions, however, may have neither property. Maybe it is possible to immediately compute the topology for expressions like

    (Y1 join Y2) union Y3

by looking at the three relations between the the query result amd the input tables. But these relations then aren't functions any more. So you cannot use the standard machinery for topological constructions and have to invent something else. This could be a "further research" question.

>> Note that intersection is a special case of the natural join:
>>
>> (X,R) /\ (Y,S) = (X/\R, R^+ /\ S^+) .
>>
>
> Yes, natural join is ubiquitous because there are 3 special cases: 1.
> Intersection is a join when both operands have the same attributes. 2.
> Selection is a join where the first operand set of attributes is a subset of
> the second operand attributes. (One have to allow relations/predicate of
> infinite content in order to express something like "select * from employees
> where salary> 1000" via natural join) 3. Cartesian product is a join for a
> relations with disjoint set of attributes.

I consider your "selection" argument overly formal. You must then use the trivial topology for your infinite infinite relation to get selection work this way. Usualy I consider the discrete topology the default for "bare" tables without an explicitely given topology. But I found authors who consider the trivial topology a better default. But don't ask me who it was. That was more than ten years ago when I stumbled over that paper.

> In other words, if you convince the reader that topological extension of
> natural join operation is flawless, then most likely the whole algebra is
> well defined.

I guess it is. I am convinced it is correct, and it has been checked by by two mathematicians.

>> Take the example space S (the "sketch"):
...
>> Now the example space S may reference these detail aggregates (via a
>> foreign key from S to I):

Note "foreign key". I meant to extend both relations S and D by an additional attribute "detail". I know, I should have been clearer here. Mea culpa. The relational schemata of S an D are hence

   S(id, detail)
   D(id, detail)

OOPS! I just realize that I have to rename the id-attributtes to get the natural join in the way I had it in mind:

   S(sid, detail)
   D(did, detail)

There is no need for a foreign key into another ("auxiliary") table, but I copied that setup from topological pullback. If this table is omitted, you get a natural join of relational representation of topological spaces. The "auxiliary" table already goes beyon join and was intended to illustrate an application I have in mind.

>> object detail
>> -----------------
>> room1 -> int
>> door -> xdoor
>> outside -> ext .
>
> OK, now you are introducing something new -- aggregation. Are you implying
> that topological extension of a join is not a dyadic operation anymore, and
> requires auxiliary pair (I,RI)?

No, it is a simple natural join on S and D (with the schemata corrected ;) ). The point of table I is to demonstrate yet another feature: "/continuous/ foreign keys" as a topological consistency rule for spatial data. The "aggregation" is an application I have in mind. Natural join also works without all that extra decoration.

> I'm uncomfortable at this stage because, one can explain classic natural join
> between Employees and Departments in a single paragraph and suggest that
> perhaps a more succinct example is wanted. For example, can you amend either
> (S,RS) or (D,RD) with (I,RI) and construct a pair of topologically enhanced
> relations which natural join can be explained without the help of auxiliary
> pair (I,RI)?

Natural join on topological data represented as (S,RS) and (D,RD) works just that simple way on S and D to get, say, SD. But then in order to get a meaningful topology for SD you can compute a binary relation RSD from RS, RD, and SD that represents the initial topology of the two projection mappings

   pi_S : SD -> S and pi_D : SD -> D .

Everything else was decoration to illustrate an application of topological natural join, which I consider interesting. In particular, the additional relation I (or, the space (I, RI)) is no prerequisite. Sorry for the errors in defining the schemta, which give intersection, and sorry for all other sloppiness in my post.

Norbert Received on Fri Jan 23 2015 - 21:32:05 CET