Re: A Topological Relational Algebra in Lisp

On Thursday, January 22, 2015 at 12:20:12 PM UTC-8, Norbert_Paul wrote:
> Given two topological spaces (X,Tx) and (Y,Ty).
> A function f:X->Y from a set X to a set Y is called /continuous/,
> from (X,Tx) to (Y,Ty) if and only if ("iff") the original image
>
> f^(-1)(B) = { a in X | f(a) in B }
>
> of every element B in Ty is an element in Tx. 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.

> Now when you have a query operation op(Y) on a database table Y may get
> a result table
>
> X = op(Y) with a function f : X -> Y
>
> that maps each the query result tuple tx in X to its input tuple f(tx) in Y
> or you get a result table
>
> Z = op(Y) with a function g : Y -> Z
>
> that maps each input tuple to a result tuple.
> In the first case I say, the query operator is of /initial/ type, because the
> result is at the starting side of the function arrow. The second case is, hence,
> of /final/ type.
>
> 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).

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?  

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

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.

> Take the example space S (the "sketch"):
>
> ----------|--------- < this is an "ascii-art" sketch
> room1 door outside
>
> As tables
> S = id
> ----
> room1
> door
> outside
>
> RS = iid bdid
> --------------
> room1 door
> outside door
>
> such that (S,RS) represents a topological space. Attributes prefixed by "bd"
> denote elements that are in the topological closure of those having the
> attribute prefixed with "i". Hence each pair (iid, bdid) in RS specifies that
> bdid in cl({iid})
> holds.
>
> You may specify yet another space D, I call "details", such as in ascii-art:
>
> interior--> |1 <--innerDoorMaterial--> 2| <--interior
>
> interior--> |x <--entranceDoorMaterial--> || <--exterior
>
> where the vertical bar denotes a database object that represents the
> material that may be used as surface towards an interior room.
> The innerDoorMaterial is bounded by two different surfaces which are also in
> the boundary of interior.
> The arrows --> denote the relation
> a-->b :<=> b in cl({a}) .
> Two vertical bars || denote a surface that must be used on teh exterior side
> of entrance doors which is exposed to weathering.
>
> These are the tables:
>
> D = id comment
> ----------------------------------------------------
> interior an interior room
> exterior the exterior
> surface1| Surface towards interior
> surface2| Opposite surface towards interior
> surface|| Surface towards exterior
> surfacex| Exterior door's surface towards interior
> idoormat material of interior doors
> xdoormat material for entry doors
>
> RD = ii bdid
> ------------------
> interior surface1|
> idoormat surface2|
> interior surfacex|
> exterior surface||
> xdoormat surface||

If I join S with D, the result is not particularly illuminating, partially because their sets of ids are disjoint. Which prompts

> Now a third table may define aggregations I (the "index") among details D:
>
> I = id comment
> --------------------------
> int an interior space
> idoor an interior door
> xdoor an entry door
> ext the exterior
>
> with relations
>
> RI = iid bdid
> ------------
> int idoor
> int xdoor
> ext xdoor
>
> Now the example space S may reference these detail aggregates
> (via a foreign key from S to I):
>
> 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)?

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)?   Received on Thu Jan 22 2015 - 23:38:01 CET