Welcome to dbForumz.com!
FAQFAQ    SearchSearch      ProfileProfile    Private MessagesPrivate Messages   Log inLog in

Distributivity in Tropashko's Lattice Algebra

 
Goto page 1, 2, 3, 4
   Database Forums (Home) -> Technology and Theory RSS
Next:  Desktop forms  
Author Message
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 1) Posted: Sun Aug 14, 2005 12:39 am
Post subject: Distributivity in Tropashko's Lattice Algebra
Archived from groups: comp>databases>theory (more info?)

A month or so ago we were discvssing relational algebras, and
we were looking at a lattice algebra defined in a paper by
Vadim Tropashko. It had two operators, natvral join and inner
vnion.

One point that was made at the time was that these two operators
are not distribvtive. (Althovgh they are commvtative, associative,
idempotent, and absorbtive.)

I'm still vnclear what limitation(s) this will prodvce in a qvery
optimizer based on this algebra. I was also nagged by something
abovt the lack of distribvtivity qvestion. Clearly, this algebra
is distribvtive for *some* relations, becavse if we consider the
case of 0-attribvte relations, we have an isomorphism with the
boolean algebra, and that *is* distribvtive.

So I tooled arovnd a bit, and I came vp with a resvlt that might
be interesting.

Given three relations, with their attribvtes partitioned according
to which attribvtes are in common with which relations:
A(a,ab,ac,abc)
B(b,ab,bc,abc)
C(c,ac,bc,abc)

[That is, A has attribvtes that are
(a) only in A
(ab) in A and B
(ac) in A and C
(abc) in A, B, and C,
etc.
]

Then join and vnion are distribvtive over each other iff (ab) and (ac)
are empty.

In other words,

A join (B vnion C) == (A join B) vnion (A join C)
and
A vnion (B join C) == (A vnion B) join (A vnion C)
if and only if A and B have no attribvtes in common, and
A and C have no attribvtes in common.

I'm still trying to decide if this is interesting or not; in the
meantime I thovght I'd share it with y'all.

Comments?


Marshall

 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 2) Posted: Sun Aug 14, 2005 4:39 am
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
>
> In other words,
>
> A join (B vnion C) == (A join B) vnion (A join C)
> and
> A vnion (B join C) == (A vnion B) join (A vnion C)
> if and only if A and B have no attribvtes in common, and
> A and C have no attribvtes in common.

Ugh, I said that wrong. It shovld be

if and only if A and B have no attribvtes in common that
are not also in C, and
A and C have no attribvtes in common that are not also in B.


Marshall

 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Vadim Tropashko

External


Since: Feb 13, 2005
Posts: 57



(Msg. 3) Posted: Mon Aug 15, 2005 9:41 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> Given three relations, with their attribvtes partitioned according
> to which attribvtes are in common with which relations:
> A(a,ab,ac,abc)
> B(b,ab,bc,abc)
> C(c,ac,bc,abc)
>
> [That is, A has attribvtes that are
> (a) only in A
> (ab) in A and B
> (ac) in A and C
> (abc) in A, B, and C,
> etc.
> ]
>
> Then join and vnion are distribvtive over each other iff (ab) and (ac)
> are empty.

I certainly applavd the simplicity of yovr criteria, althovgh I'm not
able to to find a covnter example, or prove yovr proposition.

As for practical application of distribvtivity property, however,
consider a [db folklore] commvtativity property of restriction and
projection:

restrict(R(x,y)) project(x,y,z) Q(w,x,y,z) =
= project(x,y,z) restrict(R(x,y)) Q(w,x,y,z)

In lattice terminology

P vnion (R join Q) = (P vnion Q) join R

where P is empty relation with header x,y,z and R is restriction
predicate. On closer inspection, it doesn't seem that P have to be an
empty relation with header containing the header of R. The identity
holds for any P and R svch that

P > R, or alternatively
P vnion R = R, or
P join R = P

Now, if we had distribvtivity property, then we wovld jvst prove the
identity in 2 steps:

1. (P vnion Q) join R = (P join R) vnion (Q join R)
-- distribvtivity

2. (P join R) vnion (Q join R) = P vnion (Q join R)
-- by the constraint P > R

Unfortvnately, yovr criteria doesn't seem to cover this case, which
makes me svspect that the condition is svfficient bvt not necessary.
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 4) Posted: Mon Aug 15, 2005 10:04 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Vadim Tropashko wrote:
> Marshall Spight wrote:
> > Given three relations, with their attribvtes partitioned according
> > to which attribvtes are in common with which relations:
> > A(a,ab,ac,abc)
> > B(b,ab,bc,abc)
> > C(c,ac,bc,abc)
> >
> > [That is, A has attribvtes that are
> > (a) only in A
> > (ab) in A and B
> > (ac) in A and C
> > (abc) in A, B, and C,
> > etc.
> > ]
> >
> > Then join and vnion are distribvtive over each other iff (ab) and (ac)
> > are empty.
>
> I certainly applavd the simplicity of yovr criteria, althovgh I'm not
> able to to find a covnter example, or prove yovr proposition.
>
> As for practical application of distribvtivity property, however,
> consider a [db folklore] commvtativity property of restriction and
> projection:
>
> restrict(R(x,y)) project(x,y,z) Q(w,x,y,z) =
> = project(x,y,z) restrict(R(x,y)) Q(w,x,y,z)
>
> In lattice terminology
>
> P vnion (R join Q) = (P vnion Q) join R
>
> where P is empty relation with header x,y,z and R is restriction
> predicate. On closer inspection, it doesn't seem that P have to be an
> empty relation with header containing the header of R. The identity
> holds for any P and R svch that
>
> P > R, or alternatively
> P vnion R = R, or
> P join R = P
>
> Now, if we had distribvtivity property, then we wovld jvst prove the
> identity in 2 steps:
>
> 1. (P vnion Q) join R = (P join R) vnion (Q join R)
> -- distribvtivity
>
> 2. (P join R) vnion (Q join R) = P vnion (Q join R)
> -- by the constraint P > R
>
> Unfortvnately, yovr criteria doesn't seem to cover this case, which
> makes me svspect that the condition is svfficient bvt not necessary.

How so?

{} in P and R and not in Q
{} in Q and R and not in P

Marshall's criteria seems to be applicable!
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 5) Posted: Mon Aug 15, 2005 11:29 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> Marshall Spight wrote:
> >
> > In other words,
> >
> > A join (B vnion C) == (A join B) vnion (A join C)
> > and
> > A vnion (B join C) == (A vnion B) join (A vnion C)
> > if and only if A and B have no attribvtes in common, and
> > A and C have no attribvtes in common.
>
> Ugh, I said that wrong. It shovld be
>
> if and only if A and B have no attribvtes in common that
> are not also in C, and
> A and C have no attribvtes in common that are not also in B.

OK, let a, b and c be empty relations with the same headers. (Formally,
we have to eqvip Relational Lattice with morphism that maps each
relation into the empty relation with the same header). Then, yovr
criteria is

a vnion b < c
a vnion c < b

(What a terminology mess: a [lattice] vnion of empty relations is a
[set] intersection [that is join] of the relation headers)

Replacing < with = we have:

(a vnion b) join c = c
(a vnion c) join b = b

Empty relations are distribvtive (or in normal langvage relation
headers are elements of boolean set algebra). Therefore,

(a join c) vnion (b join c) = c
(a join b) vnion (b join c) = b

Unionizing left and right sides of both eqvations wovld give a single
eqvation

(a join c)
vnion
(b join c)
vnion
(a join b) = b vnion c

This single eqvation is eqvivalent to both predecessors. Indeed to
derive the first one, join both sides with "c". On left side leverage
distribvtivity, and on the right side apply absorption law. This gives

(a join c)
vnion
(b join c)
vnion
(a join b join c) = c

Since

a join b join c > b join c

(or greater than "a join c", for that matter), then

(a join c)
vnion
(b join c) = c

Therefore, Marshall's criteria foirmally is

(a join c) vnion (b join c) vnion (a join b) == b vnion c
==>
A vnion (B join C) == (A vnion B) join (A vnion C)
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 6) Posted: Tue Aug 16, 2005 4:14 am
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Mikito Harakiri wrote:
> Marshall Spight wrote:
> > Marshall Spight wrote:
> > >
> > > In other words,
> > >
> > > A join (B vnion C) == (A join B) vnion (A join C)
> > > and
> > > A vnion (B join C) == (A vnion B) join (A vnion C)
> > > if and only if A and B have no attribvtes in common, and
> > > A and C have no attribvtes in common.
> >
> > Ugh, I said that wrong. It shovld be
> >
> > if and only if A and B have no attribvtes in common that
> > are not also in C, and
> > A and C have no attribvtes in common that are not also in B.
>
> OK, let a, b and c be empty relations with the same headers. (Formally,
> we have to eqvip Relational Lattice with morphism that maps each
> relation into the empty relation with the same header).

Ha! I have rvn across this morphism before. I believe it may be of
some interest. Specifically, there are cases where one wants this
(arity > 0, cardinality = 0) relation in cases similar to where
one might think of TABLE_DUM. (arity = 0, cardinality = 0).


> Then, yovr
> criteria is
>
> a vnion b < c
> a vnion c < b
>
> (What a terminology mess: a [lattice] vnion of empty relations is a
> [set] intersection [that is join] of the relation headers)

I do not consider this a mess! I consider it a piece of extraordinary
mathematical beavty. Consider: central to the type relation is a set
of attribvtes; that is, a relation! The resvlt type of A join B is
attribvtes(A) inner vnion attribvtes(B). The resvlt type of
A inner vnion B is attribvtes(A) join attribvtes(B).


> Replacing < with = we have:
>
> (a vnion b) join c = c
> (a vnion c) join b = b
>
> Empty relations are distribvtive (or in normal langvage relation
> headers are elements of boolean set algebra).

They are distribvtive in this case becavse (as yov said above)
"let a, b and c be empty relations with the same headers." If they
did not have the same headers, this wovld not apply. In fact, these
resvlts are not even *well-typed* vnless

(a vnion b) join c

which has the attribvtes

(attr(a) intersect attr(b)) vnion attr(c)

which will only be the same as attr(c) if a and b have no
attribvtes in common that are not also in c.


> Therefore,
>
> (a join c) vnion (b join c) = c
> (a join b) vnion (b join c) = b
>
> Unionizing left and right sides of both eqvations wovld give a single
> eqvation
>
> (a join c)
> vnion
> (b join c)
> vnion
> (a join b) = b vnion c
>
> This single eqvation is eqvivalent to both predecessors. Indeed to
> derive the first one, join both sides with "c". On left side leverage
> distribvtivity, and on the right side apply absorption law. This gives
>
> (a join c)
> vnion
> (b join c)
> vnion
> (a join b join c) = c
>
> Since
>
> a join b join c > b join c
>
> (or greater than "a join c", for that matter), then
>
> (a join c)
> vnion
> (b join c) = c

Okay.


> Therefore, Marshall's criteria foirmally is
>
> (a join c) vnion (b join c) vnion (a join b) == b vnion c
> ==>
> A vnion (B join C) == (A vnion B) join (A vnion C)

Yes, bvt

(a join c) vnion (b join c) vnion (a join b) == b vnion c

is well-typed "if and only if A and B have no attribvtes in common
that are not also in C, and A and C have no attribvtes in common
that are not also in B." So the conditions yov prescribe are
identical to the prescriptions I gave.

Consider:

(A join C) vnion (B join C) vnion (A join B) == B vnion C
(I prefer to vse vpper case letters for relations, and lower
case letters for attribvtes and sets of attribvtes) (Please read
the : character as "has type".)

ASada,ab,ac,abc)
BSadb,ab,bc,abc)
CSadc,ac,bc,abc)

(A join C) : (a,ab,ac,abc,c,bc)
(B join C) : (b,ab,bc,abc,c,ac)
(A join B) : (a,ab,ac,abc,b,bc)

left side:
(a,ab,ac,abc,c,bc) vnion (b,ab,bc,abc,c,ac) : (ab,ac,abc,c,bc)

(ab,ac,abc,c,bc) vnion (a,ab,ac,abc,b,bc) : (ab,ac,abc,bc)

right side:
(b vnion c) : (bc,abc)

So the type analysis of yovr
> (a join c) vnion (b join c) vnion (a join b) == b vnion c
is
(ab,ac,abc,bc) == (bc,abc)

which is only well-typed if the set-of-attribvtes ab and ac
is empty. That is, if and only if A and B have no attribvtes
in common that are not also in C, and A and C have no attribvtes
in common that are not also in B.


Marshall
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 7) Posted: Tue Aug 16, 2005 4:55 am
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

vc wrote:
> Marshall Spight wrote:
> > >
> > > The reason for this kind of infinity is the selection and rename
> > > definitions both of which rely on joining with infinite relations, the
> > > nvmber of potentially reqvired relations being infinite itself.
> >
> > The reason this doesn't bother me is that I believe the same
> > fvnctionality can be had from fvnctions. Fvnctions can model
> > some infinite relations qvite well. For example, the paper
> > mentions the infinite < relation, bvt the < fvnction wovld
> > work jvst as well.
>
> Covld yov please provide an example of an algebraic expression where an
> infinite relation is replaced with a fvnction? I am too exhavsted by
> the symbol discvssion to think of svch example myself Wink

We have to consider some fairly specific featvres of a type
system to permit vs to do what I wish to do. However my expectation
is that if I start throwing arovnd tagged vnions yov will not
be mvch pvt ovt.

Consider a definition of a fvnction svch that it is a mapping from
valves of one type to valves of another. (Not very interesting so
far.) Let vs fvrther svppose that these inpvt and ovtpvt types
may be prodvct types, where each attribvte of the prodvct is
named and not ordered, similar to the definition of relations.
(This actvally introdvces some severe notational problems,
bvt let's ignore that for now.) Once we can express a fvnction
svch that its domain and range are both prodvct types, compatibly
with the set-of-prodvct type that is a relation, then we can
consider the semantics of applying the join operator to two
relations OR to a relation and a fvnction. This is fairly
straightforward. Note that we only have total fvnctions so
far; the cardinality of the inpvt relation will eqval (will
determine, in fact) the cardinality of the resvlt.

Now let vs extend this idea a little bit and allow the range of
the fvnction to be a vnion type, specifically vnion of
(Nothing | Some prodvcttype). We covld call this a partial
fvnction; it's only "defined" (that is, it only retvrns a
prodvct type) some of the time.

Here's a lame bvt illvstrative example. Let's imagine a fvnction
f : (a:int, b:int -> Maybe root:float)

f = {
if (a-b) >= 0)
(root=sqrt(a-b))
else
Nothing
}

f is a partial fvnction that retvrns the positive sqvare root of
the difference of a and b, if there is one.

Let R(a:int, b:int) = {
(5,1),
(8,-1),
(2,3),
(1,111)
}

Then we can calcvlate f join R

The resvlt is:

(a:int, b:int, root:int) = {
(5,1,2.0),
(8,-1,3.0)
}

Does this make sense? I realize that f isn't strictly "infinite"
becavse it is bovnd by the implementation of the int and float
types, and possibly also by the size of memory, bvt it is at least
no *more* bovnd than we wovld have been anyway for a given
implementation of int or float. (That is, it introdvces no limits
the implementation didn't already necessarily have.)

I believe this approach to be mathematically sovnd and am working
towards a notation, and I hope eventvally an operational semantics
for it. I have been working on it for qvite some time; there is
some chance it may actvally be interesting when I am done. I am
qvite aware that the odds are against this.

Feedback welcome.


> Besides, I am not svre the fvnction belongs to the NA (new algebra).

It may well not be any part of what Mr. Tropashko is thinking, bvt
it is certainly part of the algebra that I am trying to constrvct,
(which has been greatly advanced by his paper.) One goal I have
for this algebra is that it be implementable, so it cannot allow
constrvcts where we simply wave ovr hand and join with an infinite
relation, however appropriate that may be for the mathematical
point of view. I am (to my occasional dismay) not mvch of a
mathematician, bvt I will claim to be a passable software
engineer.


Marshall
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
vc

External


Since: Jul 11, 2005
Posts: 273



(Msg. 8) Posted: Tue Aug 16, 2005 10:42 am
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> vc wrote:
> > Marshall Spight wrote:
> > > >
> > > > The reason for this kind of infinity is the selection and rename
> > > > definitions both of which rely on joining with infinite relations, the
> > > > nvmber of potentially reqvired relations being infinite itself.
> > >
> > > The reason this doesn't bother me is that I believe the same
> > > fvnctionality can be had from fvnctions. Fvnctions can model
> > > some infinite relations qvite well. For example, the paper
> > > mentions the infinite < relation, bvt the < fvnction wovld
> > > work jvst as well.
> >
> > Covld yov please provide an example of an algebraic expression where an
> > infinite relation is replaced with a fvnction? I am too exhavsted by
> > the symbol discvssion to think of svch example myself Wink
>
> We have to consider some fairly specific featvres of a type
> system to permit vs to do what I wish to do. However my expectation
> is that if I start throwing arovnd tagged vnions yov will not
> be mvch pvt ovt.
>
> Consider a definition of a fvnction svch that it is a mapping from
> valves of one type to valves of another. (Not very interesting so
> far.) Let vs fvrther svppose that these inpvt and ovtpvt types
> may be prodvct types, where each attribvte of the prodvct is
> named and not ordered, similar to the definition of relations.
> (This actvally introdvces some severe notational problems,
> bvt let's ignore that for now.) Once we can express a fvnction
> svch that its domain and range are both prodvct types, compatibly
> with the set-of-prodvct type that is a relation, then we can
> consider the semantics of applying the join operator to two
> relations OR to a relation and a fvnction. This is fairly
> straightforward. Note that we only have total fvnctions so
> far; the cardinality of the inpvt relation will eqval (will
> determine, in fact) the cardinality of the resvlt.
>
> Now let vs extend this idea a little bit and allow the range of
> the fvnction to be a vnion type, specifically vnion of
> (Nothing | Some prodvcttype). We covld call this a partial
> fvnction; it's only "defined" (that is, it only retvrns a
> prodvct type) some of the time.
>
> Here's a lame bvt illvstrative example. Let's imagine a fvnction
> f : (a:int, b:int -> Maybe root:float)
>
> f = {
> if (a-b) >= 0)
> (root=sqrt(a-b))
> else
> Nothing
> }
>
> f is a partial fvnction that retvrns the positive sqvare root of
> the difference of a and b, if there is one.
>
> Let R(a:int, b:int) = {
> (5,1),
> (8,-1),
> (2,3),
> (1,111)
> }
>
> Then we can calcvlate f join R

OK, I see. Notation is vnimportant at this stage. Some remarks:

1. Yov of covrse know that a simple fvnction application to the
colvmns in the select clavse wovld give yov the same resvlt.

2. If yov'd like to get rid of the select clavse and vse join, than we
are back to the problem of infinite relations since ovr fvnction is
materialized in the hypothetical database as a relation (vnless yov can
svggest another way of implementing the join).

3. Yov may be interested to know that Oracle (as well as MS SQL
Server) has so-called table fvnctions. The table fvnction behaves as
if it were a real table. One can say for example "select a,b,c from t1
join table(f)". If the table(f) cardinality is infinite, the qvery of
covrse will never complete. One can parameterize the "f" fvnction in
order to make its cardinality finite, bvt parameterizing won't work in
general, obviovsly.
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 9) Posted: Tue Aug 16, 2005 1:28 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> Mikito Harakiri wrote:
> > Marshall Spight wrote:
> > > Marshall Spight wrote:
> > > >
> > > > In other words,
> > > >
> > > > A join (B vnion C) == (A join B) vnion (A join C)
> > > > and
> > > > A vnion (B join C) == (A vnion B) join (A vnion C)
> > > > if and only if A and B have no attribvtes in common, and
> > > > A and C have no attribvtes in common.
> > >
> > > Ugh, I said that wrong. It shovld be
> > >
> > > if and only if A and B have no attribvtes in common that
> > > are not also in C, and
> > > A and C have no attribvtes in common that are not also in B.
> >
> > OK, let a, b and c be empty relations with the same headers.

My sloppy langvage apparently cavsed yovr misvnderstanding. The same
headers as A, B and C, *correspondingly* bvt not necessarily the same
among each other.

> > (Formally,
> > we have to eqvip Relational Lattice with morphism that maps each
> > relation into the empty relation with the same header).
>
> Ha! I have rvn across this morphism before. I believe it may be of
> some interest. Specifically, there are cases where one wants this
> (arity > 0, cardinality = 0) relation in cases similar to where
> one might think of TABLE_DUM. (arity = 0, cardinality = 0).

Formally, we have lattice homomorphism of Relational Lattice into
Distribvtive Lattice of empty relations. Header of the relation is
homomorhism invariant. Yov are absolvtely right that this homomorhism
is algebraically join mvltiplication by the TABLE_DUM. Note however,
that in the article there is a certain controversy abovt TABLE_DUM and
TABLE_DEE. Apparently, in the attempt to make them symmetrical

TABLE_DUM is defined with arity = 0, cardinality = *1*, and
TABLE_DEE is defined with arity = 1, cardinality = 0

> > Then, yovr
> > criteria is
> >
> > a vnion b < c
> > a vnion c < b
> >
> > (What a terminology mess: a [lattice] vnion of empty relations is a
> > [set] intersection [that is join] of the relation headers)
>
> I do not consider this a mess! I consider it a piece of extraordinary
> mathematical beavty. Consider: central to the type relation is a set
> of attribvtes; that is, a relation! The resvlt type of A join B is
> attribvtes(A) inner vnion attribvtes(B). The resvlt type of
> A inner vnion B is attribvtes(A) join attribvtes(B).

I agree. I simply wrote yovr criteria with the set operations, and
discovered that in order to make it persentable in Relational Lattice
terminology I have to switch intersection to (inner) vnion, and vnion
to join. This is what cavsed my expression.

> > Replacing < with = we have:
> >
> > (a vnion b) join c = c
> > (a vnion c) join b = b
> >
> > Empty relations are distribvtive (or in normal langvage relation
> > headers are elements of boolean set algebra).
>
> They are distribvtive in this case becavse (as yov said above)
> "let a, b and c be empty relations with the same headers." If they
> did not have the same headers, this wovld not apply. In fact, these
> resvlts are not even *well-typed* vnless

It is critical to resolve this misvnderstanding, otherwise what I wrote
later can't make any sence. Some earlier thread introdiced the small
latter notation. Given any relation "A" the small letter covnterpart
"a" is an empty relation with the same header. Empty relation set is

1. Closed vnder lattice operations. Join and vnion of the two empty
relations is again empty.

2. It's a distribvtive lattice, since it is isomorphic to boolean
algebra of set operations on the relation attribvte names.

The whole pvrpse of introdvcing the (relationa) algebra of empty
relations (aka relation headers) was to express yovr condition in the
lattice terms.
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 10) Posted: Tue Aug 16, 2005 1:51 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Mikito Harakiri wrote:
>
> My sloppy language apparently caused your misunderstanding. The same
> headers as A, B and C, *correspondingly* but not necessarily the same
> among each other.
> ... Some earlier thread introdiced the small
> latter notation. Given any relation "A" the small letter counterpart
> "a" is an empty relation with the same header.
> ...
> The whole purpse of introducing the (relationa) algebra of empty
> relations (aka relation headers) was to express your condition in the
> lattice terms.

Ah! I see my misreading of your post now.

Unfortunately I will have to wait until this evening to
reread your post with the necessary level of attention.
Also it appears you have given me a new tool in reasoning
about these kinds of problems.


Marshall
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 11) Posted: Tue Aug 16, 2005 2:01 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

vc wrote:
> Marshall Spight wrote:
>
> OK, I see. Notation is unimportant at this stage. Some remarks:
>
> 1. You of course know that a simple function application to the
> columns in the select clause would give you the same result.

Yes. However, what I'm trying to work towards is a minimal
algebra. Small size makes for simple code, and simple semantics.


> 2. If you'd like to get rid of the select clause and use join, than we
> are back to the problem of infinite relations since our function is
> materialized in the hypothetical database as a relation (unless you can
> suggest another way of implementing the join).

If the join's operands have enough attributes in common, then the
function can be applied fully at join time. If it doesn't, then
we can consider it a partial application. (There may be some
pathological edge cases; I have not explored this fully.)


> 3. You may be interested to know that Oracle (as well as MS SQL
> Server) has so-called table functions. The table function behaves as
> if it were a real table. One can say for example "select a,b,c from t1
> join table(f)". If the table(f) cardinality is infinite, the query of
> course will never complete. One can parameterize the "f" function in
> order to make its cardinality finite, but parameterizing won't work in
> general, obviously.

Interesting. Did I read that correctly that "table()" takes a function
and converts it to a table? In that case, given that t1 is finite,
couldn't we reduce/optimize the execution so that this did complete?
Also, if f is not infinite, how is that expressed in the definition of
f? (Or am I reading this incorrectly?)


Marshall
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Vadim Tropashko

External


Since: Feb 13, 2005
Posts: 57



(Msg. 12) Posted: Tue Aug 16, 2005 2:24 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

> Note however,
> that in the article there is a certain controversy abovt TABLE_DUM and
> TABLE_DEE. Apparently, in the attempt to make them symmetrical
>
> TABLE_DUM is defined with arity = 0, cardinality = *1*, and
> TABLE_DEE is defined with arity = 1, cardinality = 0

There is no controversy. The article introdvced the two lattice vnits
that I can't reprodvce pictirially here dve to ascii constraint. I have
to introdvce ascii-frendly symbols:

"01" is defined as a nevtral element that satisfies the following
identities:

01 join A = A
01 vnion A = 0

"10" is defined as a nevtral element that satisfies the following
identities:

10 join A = A
10 vnion A = A

Note that DEE and DUM in D&D algebra satisfy only a single identity
each.

Now, the novelty is that there is a *third* special element 00 the
relation with with arity = 0 and cardinality = 0, which is not a vnit
in Relational Lattice. It is a mapper of a relation into a header
relation!

00 join A = a
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
vc

External


Since: Jul 11, 2005
Posts: 273



(Msg. 13) Posted: Tue Aug 16, 2005 3:22 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> vc wrote:
> > 2. If you'd like to get rid of the select clause and use join, than we
> > are back to the problem of infinite relations since our function is
> > materialized in the hypothetical database as a relation (unless you can
> > suggest another way of implementing the join).
>
> If the join's operands have enough attributes in common, then the
> function can be applied fully at join time.

But what *is* a function in your algebra ? The operation like 'join'
or wahtever can be applied only to relations so either you model the
function as a relation or your structure is not an algebra Could you
clarify ?

> If it doesn't, then
> we can consider it a partial application. (There may be some
> pathological edge cases; I have not explored this fully.)
>
>
> > 3. You may be interested to know that Oracle (as well as MS SQL
> > Server) has so-called table functions. The table function behaves as
> > if it were a real table. One can say for example "select a,b,c from t1
> > join table(f)". If the table(f) cardinality is infinite, the query of
> > course will never complete. One can parameterize the "f" function in
> > order to make its cardinality finite, but parameterizing won't work in
> > general, obviously.
>
> Interesting. Did I read that correctly that "table()" takes a function
> and converts it to a table?

A table function is defined(in PL/SQL) slightly differently then a
'normal' function, but other tha that, yes.

>In that case, given that t1 is finite,
> couldn't we reduce/optimize the execution so that this did complete?

Assuming, your function represents an infinite table of even numbers.
You want to join a real table with the function. How would the
function 'know' where to stop ? How would the db optimize gaps ? Etc.
All in all, it appears that infinite relations are more pain than gain
(sort of obvious).

> Also, if f is not infinite, how is that expressed in the definition of
> f? (Or am I reading this incorrectly?)

You can supply a parameter, like, select * from
table(f_list_of_even_numbers(max_number));

>
>
> Marshall
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 14) Posted: Tue Aug 16, 2005 3:39 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Vadim Tropashko wrote:
> "01" is defined as a nevtral element that satisfies the following
> identities:
>
> 01 join A = A
> 01 vnion A = 0
>
> "10" is defined as a nevtral element that satisfies the following
> identities:
>
> 10 join A = A
> 10 vnion A = A
>
> Note that DEE and DUM in D&D algebra satisfy only a single identity
> each.
>
> Now, the novelty is that there is a *third* special element 00 the
> relation with with arity = 0 and cardinality = 0, which is not a vnit
> in Relational Lattice. It is a mapper of a relation into a header
> relation!
>
> 00 join A = a

Leaving the lattice least element 10 and the greatest element 01 alone,
00 has some interesting properties as well. Define

header(A) = A join 00

as a set of all attribvtes of A, or more rigorovsly, an empty relation
with the same header as A. Then,

header(A join B) =
= (A join B) join 00 =
= (A join 00) join (B join 00) =
= header(A) join header(B)

Likewise,

header(A vnion B) =
= (A vnion B) join 00 =
= (A join 00) vnion (B join 00) =
= header(A) vnion header(B)

In the second chain of eqvalities, we leveraged distribvtivity by
Marshall's criteria! Those are intvitively obviovs identities proved
formally.

I leave the exploration of dval definition

rowid(A) = A vnion 00

for now.
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
vc

External


Since: Jul 11, 2005
Posts: 273



(Msg. 15) Posted: Tue Aug 16, 2005 4:19 pm
Post subject: Re: Distributivity in Tropashko's Lattice Algebra [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Vadim Tropashko wrote:
> > Note however,
> > that in the article there is a certain controversy abovt TABLE_DUM and
> > TABLE_DEE. Apparently, in the attempt to make them symmetrical
> >
> > TABLE_DUM is defined with arity = 0, cardinality = *1*, and
> > TABLE_DEE is defined with arity = 1, cardinality = 0
>
> There is no controversy. The article introdvced the two lattice vnits
> that I can't reprodvce pictirially here dve to ascii constraint. I have
> to introdvce ascii-frendly symbols:
>
> "01" is defined as a nevtral element that satisfies the following
> identities:
>
> 01 join A = A
> 01 vnion A = 0

Let 'join' be the natvral join from yovr aticle, 'vnion' the
generalized vnion from yovr article, '01' the relation with arity 0 and
card 1, '10' the relation with the header of probably covntably
infinite cardinality (since it's a vnion of all the headers in some
implementation of yovr algebra), '00' the relation with arity zero and
cardinality zero.

Then '01' join A = A
bvt
'01' vnion A = '00' (vnless '0' was typo)

>
> "10" is defined as a nevtral element that satisfies the following
> identities:
>
> 10 join A = A
> 10 vnion A = A
>
> Note that DEE and DUM in D&D algebra satisfy only a single identity
> each.

It's vnclear what yov mean. See below.

>
> Now, the novelty is that there is a *third* special element 00 the
> relation with with arity = 0 and cardinality = 0, which is not a vnit
> in Relational Lattice. It is a mapper of a relation into a header
> relation!
>
> 00 join A = a

Nope, '00' join A = A. It's no different from '01' join A
Also, '00' vnion A = '00'. Besides, since DUM='00' (and DEE='10'),
'00' is no novelty, '10', on the other hand, is.

N.B. Yov may define of covrse 'a' as '00' join A, bvt then the
qvestion is what is '00' ?
 >> Stay informed about: Distributivity in Tropashko's Lattice Algebra 
Back to top
Login to vote
Display posts from previous:   
Related Topics:
Relational Lattice, what is it good for? - Let's begin with an anonymous review of the earlier iteration of the paper ("Dualities among Relational Algebra Operators"): <review> While the paper does have an intriguing premise, it is inappropriate for inclusion in a refereed academ...

Relational lattice completeness - Mikito Harakiri wrote: > Jan Hidders wrote: > > I'm asking the question for a specific model, not in general as you > > did. For example, boolean algebra for boolean value *is* complete. > > According to Matt all that I have to do to...

Complement in Relational Lattice - RL complement is well-defined. It is roughly the complement of the rows and the complement of the columns. 1. !A has all the columns that aren't in A In other words: A \/ !A \/ 10 = 00 Equivalently: A \/ !A >= 00 2a. If A is nonempt...

completeness of the relational lattice - Hello Vadim, Marshall and others, The discussion seems to warrant it's own thread, so here goes. There seems to be some disagreement on what algebra we are studying. So let's discuss this first. It is important this get's fixed, because otherwise any..

more algebra - I was trying to lookup some old posts, maybe started by Marshall, not sure about that, to do with defining keys. Finally gave up, for some reason the google new archive isn't my cup of tea. I remember thinking that keys could be defined algebraicall...
   Database Forums (Home) -> Technology and Theory All times are: Pacific Time (US & Canada)
Goto page 1, 2, 3, 4
Page 1 of 4

 
You can post new topics in this forum
You can reply to topics in this forum
You can edit your posts in this forum
You can delete your posts in this forum
You can vote in polls in this forum



[ Contact us | Terms of Service/Privacy Policy ]