Re: A Topological Relational Algebra in Lisp
Date: Tue, 27 Jan 2015 19:48:30 +0100
Message-ID: <ma8mgu$fds$1_at_dont-email.me>
Tegiri Nenashi wrote:
> On Sunday, January 25, 2015 at 2:30:29 AM UTC-8, Norbert_Paul wrote:
>> Assume that there are two topological spaces (S,T(RS)) and (D,T(RD)) >> represented by the four relations >> >> S = sid detail >> --------------- >> int1 interior >> door xdoor >> garden exterior >> >> <---interior--->|<----boudary---> >> RS = isid idetail - bdsid bddetail >> ---------------------------------- >> int1 interior - door xdoor >> garden exterior - door xdoor >
> RS is not transitive. (Later, you mention that it is.)
http://en.wikipedia.org/wiki/Transitive_relation :
Forall a,b,c in X : (a R b and b R c) => a R c. (1)
For each tuple t in RS the projection (t.isid, t.idetail) is the "left-hand-side" and = (t,bdsid, t.bddetail) is the "right-hand side" of the binary relation RS on S, hence
(t.isid, t.idetail) RS (t.bdsid, t.bddetail)
is equivalent to t in RS.
Let a,b,c in S be arbitrary chosen, such that a RS b and b RS c hold. Then there must be two tuples (a,b) = t1, (b,c) = t2 in RS such that
b = (t1.bsid, t1.bddetail) = (t2,isid, t2,idetail) holds.
All right-hand sides (t1.bsid, t1.bddetail) of the tupels in RS
look like (door,xdooor).
Hence t2 must have a left-hand-side
b = (t2.isid, t2.idetail) = (door, xdoor).
No such tuple exists in RS, hence the premise (a RS b and b RS c)
ist wrong for all a,b,c in S.
Hence the implication
(a R b and b R c) => a R c.
is true for all a,b,c in RS.
Hence RS satisfies property (1).
Hence RS is transitive.
\qed
> OK: having composite attributes (such as idid+idetail) allows you to avoid
> explicit references to tuples with introduction of auxiliary concepts such as
> FK, which you did in earlier posts.
The "detail" attribute is still a "foreign key" into
select detail from S
uinion
select detail from D;
>
>> The topology-defining binary relations RS on S and RD on D are defined by
>> the rule:
>>
>> For each pair of tuples d1, d2 in D holds: exists r in RD s.t.
>> d1.did=r.idid and d1.detail=r.idetail and d2.did=r.bddid and
>> d2.detail=r.bddetail <=> d2 in cl({d1})
>> (1)
>>
>> with respect to the topology T(RD). T(RD) itself is the finest (maximal)
>> topology that satisfies the above rule.
>
> I seem to grasp the high level idea: given the two topologies T(RS) and
> T(RD), their "natural join" is a lattice meet T(RS)^T(RD):
> http://en.wikipedia.org/wiki/Comparison_of_topologies#Lattice_of_topologies
No, it is the lattice "meet" of the two topologies induced by the projections from the join to the input tables. In general a result relation may also be the lattice "join", depending on the query operator.
> [Relational algebra] natural join is lattice operation as well:
> http://www.dcs.bbk.ac.uk/~szabolcs/ramics-final.pdf This makes it trivial to
> establish that topology plays well along with Database Relational Algebra:
> the objects of Norbert Paul algebra are pairs (DatabaseRelation, Topology)
> with each component defining their own lattice meet and join. The Norbert
> Paul lattice is just a lattice product.
No. it is not that simple:
(A,R) x (B,S) = (A x B, Ia x S + R x Ib)
where Ia is the identity relation (a,a) on A and Ib the identity (b,b) on B.
"+" is set union. It is, for example, an initial topology which can be created
by a relational query expression without transitive closure.
The tuples in Ia x S look like
((a,b1), (a,b2)) where a in A and b1 S b2 holds.
The tuples in R x Ib look like
((a1,b), (a2,b)) where a1 R a2 and b in B holds.
First you have to find induced topologies (or co-induced topologies depending on
the type operator). The result topology is either the infimum or the
supremum topology. The infimum topology is simply achieved by the union of
the relations. The supremum topology, however, requires transitive closure
computation in general. There are exceptions though. For example the topolgoy
for the Cartesian Product "x" can be computed without transitive closure:
> Crystal clear now, thank you for clarifying it.
You are welcome.
>> Now we need the coarsest topology that makey both functions continuous. >> This is generated by the maximal binary relation on SD, that makes ps and >> pd continuous: So I will check each pair (sd1, sd2) of tuples from SD x SD, >> if it satisfies the two donditions >> >> (ps(sd1),ps(sd2)) in RS^* (pd(sd1),pd(sd2)) in RD^* >> >> (here a mande an error in previous posts (and publications), where I used >> the transitive closures RS^+ and RD^+ instead of the transitive and >> reflexive closures RS^* and RD^*). These pairs as a binary relation on SD >> generate the topology for the natural join of the spaces. I will not check >> diagonal entries (sd1,sd1) because it is not necessary. Note that RS and RD >> are transitive, hence in this example >
> Typo? Did you mean RS^* and RD^* are transitive?
No. See proof above: RS and RD /are/ transitive.
> Same question here: RS^* and RD^*? I guess this can be easily recovered
> because "... is in RS" entails "... is in RS^*".
>
> ps: (int1,interior, door,xdoor) is in RS (and, therefore, in RS^*)
The rule to get the topology induced by a function f is, in general
(f(x1),f(x2)) in R^* .
You need noct check (f(x),f(x)) in R^*, because this trivially holds. When you have already verified
(f(x1),f(x2)) in R, then (f(x1),f(x2)) in R^* holds.
>> .... >> on SD. >
> OK, this convinces me that the natural join, and the entire algebra is
> consistent. It would also be helpful to demonstrate that it is meaningful. I
> have already complained about relation and attribute names. The Sketch can be
> architectural schema, but what is Detail? Is it mapping of the archeological
> site as described in the reference in one of your earlier posts?
This concept may not be suitable for archeological sites. I think of a topological generalizaiton of kind of a "details library" which can be referenced from a coarser "sketch" to get a "detailled" plan iff details (say, windows, doors) are repeatedly used.
So imagine you work on a plan where you have an element 0815 of type "door". Then refence that 0815-door object to a family of finer objects aggregated to a description of that door. The details library may then also describe topologically, how a door fits into a wall. The detailled plan (the natjoin) then topologically connects the, say, 0816-wall to the 0815-door, iff this connection is as well present in the sketch as also in the details library.
However, this is still only an idea. There is much work to be done to get this running.
> There are some values in your example, such as door, which intend to appeal
> to layman intuition. Still, I can imagine database application where home
> improvement chain store has an inventory of all doors:
>
> Doors(sku,vendor) DoorsDimensions(doorType,x,y,z)
>
> I can't figure out realistic schema where "door" is a value of some
> attribute.
Actually, this "door" value is only intendet for the small example. If there are many doors, of course, each will get its identifier.
Norbert Received on Tue Jan 27 2015 - 19:48:30 CET