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

Relational Lattice, what is it good for?

 
Goto page 1, 2
   Database Forums (Home) -> Technology and Theory RSS
Next:  Data Redundancy  
Author Message
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 1) Posted: Wed Feb 15, 2006 5:06 pm
Post subject: Relational Lattice, what is it good for?
Archived from groups: comp>databases>theory (more info?)

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 academic journal for two reasons --
insufficient depth and insufficient attention to formal details.

With regards to depth, the question that needs to be answered here is
"so what?", beyond just an interesting and cute reformulation. Can we
now apply results from lattice theory to get striking new results
about relational query languages, or at least novel re-workings of
standard results? Do the operators give us new inights into elusive
problems such as view update or incomplete information? The new
operators may indeed hold such promise, but there is not enough
development to tell at this point.
</review>

Note how insightful the comment was, even though there was no lattice
explicitly mentioned in that paper. I should admit that this evaluation
is still valid. Simplifying algebra is promising in terms of query
optimization, but it's very hard to handle algebraic expresions without
distributivity law.

Consider "folklore" relational algebra rewrite rules (p.56, the Alice
Book). Most of them
trivially follow from lattice axioms e.g. "push-cross-through-select"

sigma_F(q) X q' = # rewrite in lattice terms
(F join q) join q' = # associativity
F join (q join q') = # rewrite back to standard RA
sigma_F(q X q')


"Push-select-through-project"

sigma_x=1( pi_x_y A(x,y,z) ) = pi_x_y ( sigma_x=1 ( A(x,y,z) ) )

is much more chalenging. Let's rewrite it in the lattice terms

("xy" union A(x,y,z)) join "x=1" =
= "xy" union (A(x,y,z) join "x=1")

where "xy" abbreviates an empty relation with two attributes x, y; and
"x=1" is the relation {x|x=1}.

Let's work out this identity step by step too:

("xy" union A(x,y,z) ) join "x=1" =
# Distributivity
# by Marshall's criteria
("xy" join "x=1") union (A(x,y,z) join "x=1") =
# Evaluate ("xy" join "x=1") to "xy"
"xy" union (A(x,y,z) join "x=1")

Please note that if we exchange the predicate "x=1" with, say "z=1"
then Marshall's criteria won't apply.


Likewise, "Push-cross-through-project"

( pi_x A(x,y) ) X B(z) = pi_x_z ( A(x,y,z) join B(z) )

Please note the extra attribute "z" appeared in the projection. There
would be a formal explanation for that below.

Rewrittten in lattice form the law reads

("x" union A(x,y) ) join B(z) =
= "xz" union (A(x,y,z) join B(z))

Step by step proof:

("x" union A(x,y) ) join B(z) =
# Distributivity
# by Marshall's criteria
("x" join B(z)) union (A(x,y) join B(z)) =
# Evaluate ("x" join B(z)) to "xz"
"xz" union (A(x,y,z) join B(z))

Please note that if we exchange the relation B(z) with, say B(y), then
Marshall's criteria won't apply.


If nothing else, it's interesting to see the last two laws, which look
so dissimilar, handled in a very same manner. This is small progress,
however. One of my goals indeed was approaching view updates with
algebraic transformations method. Needless to add, that Marshall
criteria itself is not something firmly established yet. (It would be
as soon as we have a proof).

 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 2) Posted: Wed Feb 15, 2006 5:24 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Mikito Harakiri wrote:
> Likewise, "Push-cross-through-project"
>
> ( pi_x A(x,y) ) X B(z) = pi_x_z ( A(x,y,z) join B(z) )

Typo:

( pi_x A(x,y) ) X B(z) = pi_x_z ( A(x,y) X B(z) )

> ("x" union A(x,y) ) join B(z) =
> = "xz" union (A(x,y,z) join B(z))

Typo:

("x" union A(x,y) ) join B(z) =
= "xz" union (A(x,y) join B(z))

 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 3) Posted: Wed Feb 15, 2006 9:01 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

paul c wrote:
> 1) Marshall said in one of his notes: "Then join and union are
> distributive over each other iff (ab) and (ac) are empty." Later,
> 'Mikito' said it differently (I think): "(a join c) union (b join c)
> union (a join b) == b union c ==> A union (B join C) == (A union B) join
> (A union C)".

I think Spight criteria is sufficient condition for distributivity.
Take

A = "xy"
B = "yz"
C = "zx"

Then, distributivity holds, while the Spight criteria premise doesn't
seem to.

> 2) I'm curious what were the "view updates" Mikito had in mind, were
> they ones that are evident in products and elsewhere to be logically
> impossible, such as insert through union, or was the intent merely to
> make a simpler engine? (One reason 'inner' union intrigued me was
> whether its 'assymetry' offered a logical avenue toward more complete
> single-table closure in spite of the distribution as well as what I
> think of, maybe wrongly, as the de Morgan problem, eg. if you can't
> insert to a union, you can't delete from its complement.)

All sort of things: formal basis for query transformations,
formal basis for view updates (as opposed to D&D ad-hock rules),
formal basis for incremental maintenece of materialized views (which is
the easier and the opposite problem to view updates).

When approaching view updates, the critical abstraction IMO is to
remove the concept of update. Update is just a delta of the view (or
several views). Formally we have a set of views {V1,V2,V3} defined in
terms of base relations {R1, R2, R3, R4}. In other words we have a
system of equations

V1 = V1(R1, R2, R3, R4)
V2 = V2(R1, R2, R3, R4)
V3 = V3(R1, R2, R3, R4)

If we can invert these relations and write

R1 = R1(V1,V2,V3)
R2 = R2(V1,V2,V3)
R3 = R3(V1,V2,V3)
R4 = R4(V1,V2,V3)

then the view updates problem is solved, because all that is requred to
do is just plug in the V1+delta1, V2+delta2, V3+delta3 into the right
side of the above system. Of course this is easy to say, but hard to
do. This is where the simplicity of the relational algebra becomes
paramount.

For the record, I never really understood Banchilhon&Spyratos method
(and their followers). How can view update method be agnostic of the
particular databases model where it is appiled (that is the Relational
Model)?
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
paul c

External


Since: Apr 22, 2005
Posts: 879



(Msg. 4) Posted: Wed Feb 15, 2006 11:55 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

(took the liberty of changing the typos below that were mentioned in the
later post.)


I haven't got a grip on the Alice notation yet, but I note with surely
irrelevant interest that it is on page fifty-six, which is my favourite
page in TTM!


This is going to take me some time. In the meantime, two minor
questions if I may:


1) Marshall said in one of his notes: "Then join and union are
distributive over each other iff (ab) and (ac) are empty." Later,
'Mikito' said it differently (I think): "(a join c) union (b join c)
union (a join b) == b union c ==> A union (B join C) == (A union B) join
(A union C)".


Did you mean "if" instead of "iff" Marshall? If you did, then wouldn't
the distribution also hold when a,b and c have only common attributes
(ie., the case in many conventional implementations)?


2) I'm curious what were the "view updates" Mikito had in mind, were
they ones that are evident in products and elsewhere to be logically
impossible, such as insert through union, or was the intent merely to
make a simpler engine? (One reason 'inner' union intrigued me was
whether its 'assymetry' offered a logical avenue toward more complete
single-table closure in spite of the distribution as well as what I
think of, maybe wrongly, as the de Morgan problem, eg. if you can't
insert to a union, you can't delete from its complement.)


thanks,
pc


Mikito Harakiri wrote:
> 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 academic journal for two reasons --
> insufficient depth and insufficient attention to formal details.
>
> With regards to depth, the question that needs to be answered here is
> "so what?", beyond just an interesting and cute reformulation. Can we
> now apply results from lattice theory to get striking new results
> about relational query languages, or at least novel re-workings of
> standard results? Do the operators give us new inights into elusive
> problems such as view update or incomplete information? The new
> operators may indeed hold such promise, but there is not enough
> development to tell at this point.
> </review>
>
> Note how insightful the comment was, even though there was no lattice
> explicitly mentioned in that paper. I should admit that this evaluation
> is still valid. Simplifying algebra is promising in terms of query
> optimization, but it's very hard to handle algebraic expresions without
> distributivity law.
>
> Consider "folklore" relational algebra rewrite rules (p.56, the Alice
> Book). Most of them
> trivially follow from lattice axioms e.g. "push-cross-through-select"
>
> sigma_F(q) X q' = # rewrite in lattice terms
> (F join q) join q' = # associativity
> F join (q join q') = # rewrite back to standard RA
> sigma_F(q X q')
>
>
> "Push-select-through-project"
>
> sigma_x=1( pi_x A(x,y) ) X B(z) = pi_x_z ( A(x,y) X B(z) )
>
> is much more chalenging. Let's rewrite it in the lattice terms
>
> ("xy" union A(x,y,z)) join "x=1" =
> = "xy" union (A(x,y) join "x=1")
>
> where "xy" abbreviates an empty relation with two attributes x, y; and
> "x=1" is the relation {x|x=1}.
>
> Let's work out this identity step by step too:
>
> ("xy" union A(x,y,z) ) join "x=1" =
> # Distributivity
> # by Marshall's criteria
> ("xy" join "x=1") union (A(x,y,z) join "x=1") =
> # Evaluate ("xy" join "x=1") to "xy"
> "xy" union (A(x,y,z) join "x=1")
>
> Please note that if we exchange the predicate "x=1" with, say "z=1"
> then Marshall's criteria won't apply.
>
>
> Likewise, "Push-cross-through-project"
>
> ( pi_x A(x,y) ) X B(z) = pi_x_z ( A(x,y,z) join B(z) )
>
> Please note the extra attribute "z" appeared in the projection. There
> would be a formal explanation for that below.
>
> Rewrittten in lattice form the law reads
>
> ("x" union A(x,y) ) join B(z) =
> = "xz" union (A(x,y,z) join B(z))
>
> Step by step proof:
>
> ("x" union A(x,y) ) join B(z) =
> # Distributivity
> # by Marshall's criteria
> ("x" join B(z)) union (A(x,y) join B(z)) =
> # Evaluate ("x" join B(z)) to "xz"
> "xz" union (A(x,y,z) join B(z))
>
> Please note that if we exchange the relation B(z) with, say B(y), then
> Marshall's criteria won't apply.
>
>
> If nothing else, it's interesting to see the last two laws, which look
> so dissimilar, handled in a very same manner. This is small progress,
> however. One of my goals indeed was approaching view updates with
> algebraic transformations method. Needless to add, that Marshall
> criteria itself is not something firmly established yet. (It would be
> as soon as we have a proof).
>
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 5) Posted: Thu Feb 16, 2006 1:25 am
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Argh! This thread will clearly demand an hour or two a day
from me for at least a few days. But I'm still catching up from
my last busy-period; I am reviewing a book for someone
and after that I have another book review, that I will probably
just have to give up on. Meanwhile I can do tiny amounts of
usenet posting, since I have a laptop with wireless that I can
use while I'm supervising toddler's baths. Not the best
environment for this sort of deep discussion.

I hope to post something on how I came up with the distributivity
guidelines when I'm done with the book review. I have a lot of
other stuff I want to discuss as well.

In the short term I just want to address one point.


paul c wrote:
>
> 1) Marshall said in one of his notes: "Then join and union are
> distributive over each other iff (ab) and (ac) are empty." Later,
> 'Mikito' said it differently (I think): "(a join c) union (b join c)
> union (a join b) == b union c ==> A union (B join C) == (A union B) join
> (A union C)".

Unfortunately Mikito and I have been using different syntax, and
sometimes I have managed to confuse myself quite a bit because
of that, so I'm not surprised it confuses others.

In the above quote, "(ab)" and "(ac)" represent the set of
attributes in common between relations A and B, or A and C,
respectively. This necessarily *excludes* attributes from
C and B, respectively.

("ab" is a single token, not "a" and "b" together. I share
with most programmers a distaste for the mathematical
trend towards pushing symbols together with juxtaposition;
I want an explicit operator most of the time.)


> Did you mean "if" instead of "iff" Marshall? If you did, then wouldn't
> the distribution also hold when a,b and c have only common attributes
> (ie., the case in many conventional implementations)?

I did mean "iff". But again, "(ac)" means those attributes in A and
in C and NOT in B. So if A, B, and C have *only* common attributes,
then (ab) and (ac), and further (bc), will be emtpy, so we should
expect distributivity to hold.


> 2) I'm curious what were the "view updates" Mikito had in mind, were
> they ones that are evident in products and elsewhere to be logically
> impossible, such as insert through union, or was the intent merely to
> make a simpler engine?

The simpler engine will be quite nice, but my expectation is that
the Tropashko algebra will be the key to unlocking the full
power of view updating, and that's why it's An Important Discovery.


Marshall
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
paul c

External


Since: Apr 22, 2005
Posts: 879



(Msg. 6) Posted: Thu Feb 16, 2006 5:55 am
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> Argh! This thread will clearly demand an hour or two a day
> from me for at least a few days. But I'm still catching up from
> my last busy-period; I am reviewing a book for someone
> and after that I have another book review, that I will probably
> just have to give up on. Meanwhile I can do tiny amounts of
> usenet posting, since I have a laptop with wireless that I can
> use while I'm supervising toddler's baths. Not the best
> environment for this sort of deep discussion.
> ...

Marshall, I hope you will be able to spend some time on it. You are in
a good position to do that if you ask me. Toddlers give a good
perspective on some of this bumpf. If not, thanks anyway.


pc
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Jan Hidders1

External


Since: Sep 22, 2003
Posts: 206



(Msg. 7) Posted: Fri Feb 17, 2006 12:55 am
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Mikito Harakiri wrote:
>
> For the record, I never really understood Banchilhon&Spyratos method
> (and their followers). How can view update method be agnostic of the
> particular databases model where it is appiled (that is the Relational
> Model)?

A concrete method cannot, but you can reason at an abstract level about
the desirable properties of such a method and what the consequences of
that are such Georg Gottlob, Paolo Paolini and Roberto Zicari do in
their paper. It adds to the understanding of what actually the problem
is that you should solve, and why there are different solutions with
different properties that might or might not be what you want.

Btw. Francois Bancilhon, who also founded O2 technologies, is now chief
executive officer of Mandriva.

-- Jan Hidders
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 8) Posted: Fri Feb 17, 2006 4:19 am
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Mikito Harakiri wrote:
> One of my goals indeed was approaching view updates with
> algebraic transformations method. Needless to add, that Marshall
> criteria itself is not something firmly established yet. (It would be
> as soon as we have a proof).

[Best viewed in a fixed width font.]

Background

I was rocked by the Tropashko paper, because I had been searching
for an ideal design for a minimal relational algebra, and had been
unable to get much handle on the algebraic issues up to that point.
(My working algebra had 3 operators: natural join, outer union, and
projection, but it was distinctly unsatisfying, in part because
projection
was such an out-of-left-field thing compared to the other two.)

When I read the paper, I immediately threw out my old algebra and
replaced
it with the Tropashko algebra, since (among other reasons) it had
the desirable algebraic properties. But not distributivity.

I observed that the two operators, over operands of relations with
zero attributes, was isomorphic to the boolean algebra. Hence, it
was clear there were at least *some* conditions over which that
algebra was distributive, since the boolean algebra is distributive.
But was it distributive only in that one degenerate case, or most
of the time, or what? How to tell?


Conventions

Relations are named with capital letters: A, B, C

Sets of attributes are given with lower case letters, according
to which relations these attributes appear in. Thus, (ab) is the
set of attributes that are common to A and B. This set may be empty.
The letters of the name are normalized to be in alphabetical order.

The two operators of the Tropashko Algebra are written "&&" (natural
join)
and "||" (inner union.)

We use set builder notation.


Definitions

A relation's attributes are unordered; we consider a relation (a,ab) to
be the same type as a relation (ab,a) without further comment.


Given
ASada, ab)
BSadb, ab)

The Natural Join, A && B is:

{ (a, b, ab) | (a, ab) in A and (b, ab) in B }

The Inner Union, A || B is:

{ (ab) | (ab) in A or (ab) in B }

Above, when we speak of the (ab) in A, we mean the projection of A
over the attributes in (ab).

The two operators && and || have boolean operators at their heart,
and we leverage known properties of the boolean algebra accordingly.

What are all the possible partitions of attributes between A, B, and C?
There are seven partitions: a, b, c, ab, ac, bc, abc. (Draw the Venn
diagram
if you need to convince yourself.)


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

Distributive

Does natural join distribute over inner union?

Q: Under what circumstances does the below hold?

A && (B || C) = (A && B) || (A && C)


First, let's fully expand the left side.

1) A && (B || C) = A && ( { (bc,abc) | (bc,abc) in B or (bc,abc) in C }
)

2) = { (a,ab,ac,bc,abc) | (a,ab,ac,abc) in A and
((bc,abc) in B or (bc,abc) in C
) }

Then let's fully expand the right side.

3) (A && B) || (A && C) = ( { (a,ab,ac,abc,b,bc) |
(a,ab,ac,abc) in A and (ab,b,bc,abc) in B
}
||
{ (a,ab,ac,abc,c,bc) |
(a,ab,ac,abc) in A and (c,ac,bc,abc) in C
} )

4) = { (a,ab,ac,abc,bc) |
( (a,ab,ac,abc) in A and (ab,bc,abc) in B )
or
( (a,ab,ac,abc) in A and (ac,bc,abc) in C )
}

5) = { (a,ab,ac,abc,bc) |
(a,ab,ac,abc) in A and
((ab,bc,abc) in B or (ac,bc,abc) in C) }

Now let's push the expansion of A && (B || C) in 2 against the
expansion of
(A && B) || (A && C) in 5. The formatting goes a little crazy here.

6) { (a,ab,ac,bc,abc) | = { (a,ab,ac,abc,bc) |
(a,ab,ac,abc) in A and (a,ab,ac,abc) in A and
((bc,abc) in B or ((ab,bc,abc) in B or
(bc,abc) in C ) } (ac,bc,abc) in C) }

The right side has an additional constraint.

Can we describe this constraint precisely? Clearly, the constraint
is satified when ab and ac are empty, my original conjecture. In
that case, the two sides of the equasion are identical and the
equality holds. (Hence: ab, ac empty => join distributes over union.)

But there appear to be other circumstances that will satisfy the
equality.
(That is, I was wrong about the "if and only if" part.)

So, it's late and I'm exhausted from the effort so far, so I'm going
to take my best stab and then go watch Smallville. Tonight's episode
has a cyborg.

If,
for all (ab,ac) in A, (ab) in B or (ac) in C,
then the equality holds.

Ugh, I don't think I got that quite right, but my brain is sending
me the "I'm done for the night" signal.

(ab,ac) empty trivially satisfies the above. It would also be
satisfied if ab was a foreign key from A to B, or ac from A to C.


Suggestions, comments, and particularly
corrections/refutations/confirmations
welcome.


Marshall
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
paul c

External


Since: Apr 22, 2005
Posts: 879



(Msg. 9) Posted: Fri Feb 17, 2006 1:55 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> Mikito Harakiri wrote:
>
>>One of my goals indeed was approaching view updates with
>>algebraic transformations method. Needless to add, that Marshall
>>criteria itself is not something firmly established yet. (It would be
>>as soon as we have a proof).
>
>
> [Best viewed in a fixed width font.]
>
> Background
>
> I was rocked by the Tropashko paper, because I had been searching
> for an ideal design for a minimal relational algebra, and had been
> unable to get much handle on the algebraic issues up to that point.
> (My working algebra had 3 operators: natural join, outer union, and
> projection, but it was distinctly unsatisfying, in part because
> projection
> was such an out-of-left-field thing compared to the other two.)
>
> When I read the paper, I immediately threw out my old algebra and
> replaced
> it with the Tropashko algebra, since (among other reasons) it had
> the desirable algebraic properties. But not distributivity.
>
> I observed that the two operators, over operands of relations with
> zero attributes, was isomorphic to the boolean algebra. Hence, it
> was clear there were at least *some* conditions over which that
> algebra was distributive, since the boolean algebra is distributive.
> But was it distributive only in that one degenerate case, or most
> of the time, or what? How to tell?
>
>
> Conventions
>
> Relations are named with capital letters: A, B, C
>
> Sets of attributes are given with lower case letters, according
> to which relations these attributes appear in. Thus, (ab) is the
> set of attributes that are common to A and B. This set may be empty.
> The letters of the name are normalized to be in alphabetical order.
>
> The two operators of the Tropashko Algebra are written "&&" (natural
> join)
> and "||" (inner union.)
>
> We use set builder notation.
>
>
> Definitions
>
> A relation's attributes are unordered; we consider a relation (a,ab) to
> be the same type as a relation (ab,a) without further comment.
>
>
> Given
> ASada, ab)
> BSadb, ab)
>
> The Natural Join, A && B is:
>
> { (a, b, ab) | (a, ab) in A and (b, ab) in B }
>
> The Inner Union, A || B is:
>
> { (ab) | (ab) in A or (ab) in B }
>
> Above, when we speak of the (ab) in A, we mean the projection of A
> over the attributes in (ab).
>
> The two operators && and || have boolean operators at their heart,
> and we leverage known properties of the boolean algebra accordingly.
>
> What are all the possible partitions of attributes between A, B, and C?
> There are seven partitions: a, b, c, ab, ac, bc, abc. (Draw the Venn
> diagram
> if you need to convince yourself.)
>
>
> Given:
> ASada, ab, ac, abc)
> BSadb, ab, bc, abc)
> CSadc, ac, bc, abc)
>
> Distributive
>
> Does natural join distribute over inner union?
>
> Q: Under what circumstances does the below hold?
>
> A && (B || C) = (A && B) || (A && C)
> ...

Although I've been using truth tables instead of your set builder
notation, I believe the above distribution is true when A, B and C have
common columns, including when the common columns are just the empty
set, which I think you've already pointed out. To put it another way
that might be more useful, it's true when A, B and C are first projected
on their common columns, that the distribution as well as de Morgan's
laws seem to work okay.


I'm not crazy about calling it 'inner union' because that tempts me to
compare it to 'inner join' which usually has a different context. I
think of it as 'projection union'. So if there were an analogous
'projection join', (for want of imagination, let me use ||| and &&&
instead of || and &&),


A &&& (B ||| C) = (A &&& B) ||| (A &&& C)
and also
A ||| (B &&& C) = (A ||| B) &&& (A ||| C)

seem true to me.

I imagine an analogous kind of equality would give the same effect, eg.,

A && (B || C) === (A && B} || (B && C)

which seems sort of reminiscent of the 'semi-' mods to difference and join.

Maybe semi-union is what it is, I don't know if that term is already in use.


I suppose another way of describing it is that if one distributes
projection as well as join and union, ie., existentially quantify before
applying the other operators, the distribution is true.


Whether this all has any useful purpose and why I should be titillated
by it, I don't know, maybe it is just relational masturbation. I
believe the 'generalized union' is the same as Hugh Darwen's BS12's
common column union, even though Mikito seems to have had a different
starting point. Do you think I've got this wrong?


I must admit that I've forgotten whether I had any strong reasons for
being intrigued by it (as I said in an earlier note, I didn't pay much
attention to the lattice idea as I don't have a good understanding of it
and that isn't to say that it mightn't be useful) but a minor one I
remember is that it seemed just a little more general than having the
usual restriction of limiting union to common columns. (I take it that
the really basic reason for having union is so that one can add a tuple
to a 'relvar'.) I haven't tried to see how it might help optimizations.
Also, I found it easier to visual materialized disjuntions in my head
and am still wondering if it gives any aid when handling keys in views
or in having an indirect way to know which columns are column (the
projection union's heading would always be the common columns). Maybe
it's all just a curiousity and Codd knew this and discarded it long ago
- I don't know.


pc











>
> First, let's fully expand the left side.
>
> 1) A && (B || C) = A && ( { (bc,abc) | (bc,abc) in B or (bc,abc) in C }
> )
>
> 2) = { (a,ab,ac,bc,abc) | (a,ab,ac,abc) in A and
> ((bc,abc) in B or (bc,abc) in C
> ) }
>
> Then let's fully expand the right side.
>
> 3) (A && B) || (A && C) = ( { (a,ab,ac,abc,b,bc) |
> (a,ab,ac,abc) in A and (ab,b,bc,abc) in B
> }
> ||
> { (a,ab,ac,abc,c,bc) |
> (a,ab,ac,abc) in A and (c,ac,bc,abc) in C
> } )
>
> 4) = { (a,ab,ac,abc,bc) |
> ( (a,ab,ac,abc) in A and (ab,bc,abc) in B )
> or
> ( (a,ab,ac,abc) in A and (ac,bc,abc) in C )
> }
>
> 5) = { (a,ab,ac,abc,bc) |
> (a,ab,ac,abc) in A and
> ((ab,bc,abc) in B or (ac,bc,abc) in C) }
>
> Now let's push the expansion of A && (B || C) in 2 against the
> expansion of
> (A && B) || (A && C) in 5. The formatting goes a little crazy here.
>
> 6) { (a,ab,ac,bc,abc) | = { (a,ab,ac,abc,bc) |
> (a,ab,ac,abc) in A and (a,ab,ac,abc) in A and
> ((bc,abc) in B or ((ab,bc,abc) in B or
> (bc,abc) in C ) } (ac,bc,abc) in C) }
>
> The right side has an additional constraint.
>
> Can we describe this constraint precisely? Clearly, the constraint
> is satified when ab and ac are empty, my original conjecture. In
> that case, the two sides of the equasion are identical and the
> equality holds. (Hence: ab, ac empty => join distributes over union.)
>
> But there appear to be other circumstances that will satisfy the
> equality.
> (That is, I was wrong about the "if and only if" part.)
>
> So, it's late and I'm exhausted from the effort so far, so I'm going
> to take my best stab and then go watch Smallville. Tonight's episode
> has a cyborg.
>
> If,
> for all (ab,ac) in A, (ab) in B or (ac) in C,
> then the equality holds.
>
> Ugh, I don't think I got that quite right, but my brain is sending
> me the "I'm done for the night" signal.
>
> (ab,ac) empty trivially satisfies the above. It would also be
> satisfied if ab was a foreign key from A to B, or ac from A to C.
>
>
> Suggestions, comments, and particularly
> corrections/refutations/confirmations
> welcome.
>
>
> Marshall
>
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
vc

External


Since: Jul 11, 2005
Posts: 273



(Msg. 10) Posted: Fri Feb 17, 2006 8:17 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
[...]
> Conventions
>
> Relations are named with capital letters: A, B, C
>
> Sets of attributes are given with lower case letters, according
> to which relations these attributes appear in. Thus, (ab) is the
> set of attributes that are common to A and B. This set may be empty.
> The letters of the name are normalized to be in alphabetical order.
>
> The two operators of the Tropashko Algebra are written "&&" (natural
> join)
> and "||" (inner union.)
>
> We use set builder notation.
>
>
> Definitions
>
> A relation's attributes are unordered; we consider a relation (a,ab) to
> be the same type as a relation (ab,a) without further comment.
>
>
> Given
> ASada, ab)
> BSadb, ab)
>
> The Natural Join, A && B is:
>
> { (a, b, ab) | (a, ab) in A and (b, ab) in B }

That does not make any obvious sense. What is '(a, b, ab)' ? Is it
the union of sets of attributes [of their respective relations] or
something else ? You did not define the expression.
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 11) Posted: Fri Feb 17, 2006 8:55 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

vc wrote:
> Marshall Spight wrote:
> [...]
>
> That does not make any obvious sense. What is '(a, b, ab)' ? Is it
> the union of sets of attributes [of their respective relations] or
> something else ? You did not define the expression.

Under Conventions, I wrote:

"Sets of attributes are given with lower case letters, according
to which relations these attributes appear in. Thus, (ab) is the
set of attributes that are common to A and B. This set may be empty.
The letters of the name are normalized to be in alphabetical order."

So '(a, b, ab)' contains all the attributes that are only in A,
all the attributes that are only in B, and all the attributes
that in in both A and B.


HTH


Marshall
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 12) Posted: Fri Feb 17, 2006 9:56 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> Sets of attributes are given with lower case letters, according
> to which relations these attributes appear in. Thus, (ab) is the
> set of attributes that are common to A and B. This set may be empty.
> The letters of the name are normalized to be in alphabetical order.

This is fine, as long as (ab) is the set of attributes. Below, however,
you use it in tuple set notation.

> Definitions
> The Inner Union, A || B is:
>
> { (ab) | (ab) in A or (ab) in B }

I understand this as abbreviation of

{ (ab) | (ab) in pi_a_b A or (ab) in pi_a_b B }

Alternatively, you have to use existential qualifier, as Jon written in
the old exchange.

> 4) = { (a,ab,ac,abc,bc) |
> ( (a,ab,ac,abc) in A and (ab,bc,abc) in B )
> or
> ( (a,ab,ac,abc) in A and (ac,bc,abc) in C )
> }
>
> 5) = { (a,ab,ac,abc,bc) |
> (a,ab,ac,abc) in A and
> ((ab,bc,abc) in B or (ac,bc,abc) in C) }

This step is not obvious. Again, careful manipulation would involve
projection.

> Suggestions, comments, and particularly
> corrections/refutations/confirmations
> welcome.

You aren't reading Imre Lakatos, by any chance? Anyhow, that's an
outstanding effort (by this group standards) that has a chance to be
repaired.

A similar manipulation for dual law (with jon and union swapped)
reveals a that it has to meet the same criteria. Although I seem to
have (a pathological?) counterexample.

Let

`1` := {x=1}
`2b` := {x=2, y=b}

00,01,10, and 11 are defined as before. Then

00 || (`1` && `2b`) = 00
(00 || `1`) && (00 || `2b`) = 01 && 01 = 01
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
vc

External


Since: Jul 11, 2005
Posts: 273



(Msg. 13) Posted: Fri Feb 17, 2006 10:16 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall Spight wrote:
> vc wrote:
> > Marshall Spight wrote:
> > [...]
> >
> > That does not make any obvious sense. What is '(a, b, ab)' ? Is it
> > the union of sets of attributes [of their respective relations] or
> > something else ? You did not define the expression.
[...]
> So '(a, b, ab)' contains all the attributes that are only in A,
> all the attributes that are only in B, and all the attributes
> that in in both A and B.

Assuming 'contains' means 'is the union of', '(a, b, ab)' is obviously
'a union b' and 'ab' is clearly redundant. Is that what you mean ?

>
>
> HTH
>
>
> Marshall
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Mikito Harakiri

External


Since: Apr 05, 2005
Posts: 191



(Msg. 14) Posted: Fri Feb 17, 2006 10:46 pm
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Mikito Harakiri wrote:
> ...has a chance to be
> repaired.

Indeed. Withoul loss of generality, we could focus on relations with
headers

A(x,u,w,t)
B(y,u,v,t)
C(z,v,w,t)

They don't satisfy Spight criteria, however. The relations that satisfy
are

A(x,t)
B(y,v,t)
C(z,v,t)

Working out the left side of distributivity equation we have:

A && (B || C) = { (x,v,t) | A(x,t) and ( exists y B(y,v,t) or exists z
C(z,v,t) ) }

while the right side is

(A && B) || (A && C) =
{ (x,v,t) | (exists y A(x,t) and B(y,v,t)) or (exists z A(x,t) and
C(z,v,t)) }

They are equivalent since existential quantifier can be moved into the
outer most scope.

On the other hand, if we consider the relations, that don't satisfy
spight criteria, say

A(x,u,t)
B(y,u,v,t)
C(z,v,t)

Then we'll have the the u variable stuck under existential quantifier
in the left side expression and free on the right side.
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Marshall Spight

External


Since: Jun 04, 2005
Posts: 349



(Msg. 15) Posted: Sat Feb 18, 2006 2:33 am
Post subject: Re: Relational Lattice, what is it good for? [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Mikito Harakiri wrote:
> Marshall Spight wrote:
> > Sets of attributes are given with lower case letters, according
> > to which relations these attributes appear in. Thus, (ab) is the
> > set of attributes that are common to A and B. This set may be empty.
> > The letters of the name are normalized to be in alphabetical order.
>
> This is fine, as long as (ab) is the set of attributes. Below, however,
> you use it in tuple set notation.

Yes. I guess what I am saying is ab is the set of attributes, and
(ab) is a tuple with (only) those attributes from the set ab.


> > Definitions
> > The Inner Union, A || B is:
> >
> > { (ab) | (ab) in A or (ab) in B }
>
> I understand this as abbreviation of
>
> { (ab) | (ab) in pi_a_b A or (ab) in pi_a_b B }

If I may correct this last line a bit:

{ (ab) | (ab) in pi_ab A or (ab) in pi_ab B }

The name "ab" is atomic, so I'm uncomfortable with putting the
underscore between the a and the b.

Let me try to be more precise. "(ab) in A" means that (ab) is a
a tuple whose set-of-attributes equals the set ab, and furthermore,
this tuple is constraint to be in the set that is the projection of the
relation A over the set-of-attributes ab.


> Alternatively, you have to use existential qualifier, as Jon written in
> the old exchange.

I only vaguely recall this exchange, and I seem to remember that
I didn't understand it at the time.


> > 4) = { (a,ab,ac,abc,bc) |
> > ( (a,ab,ac,abc) in A and (ab,bc,abc) in B )
> > or
> > ( (a,ab,ac,abc) in A and (ac,bc,abc) in C )
> > }
> >
> > 5) = { (a,ab,ac,abc,bc) |
> > (a,ab,ac,abc) in A and
> > ((ab,bc,abc) in B or (ac,bc,abc) in C) }
>
> This step is not obvious. Again, careful manipulation would involve
> projection.

I don't understand the problem. This step relies only on the
distributivity of the boolean algebra; note that the operands of the
boolean operators ("and", "or") in the expressions are syntactically
unchanged between steps 4 and 5. I assumed I could rely on
boolean distributivity; was that an unjustified assumption?


> > Suggestions, comments, and particularly
> > corrections/refutations/confirmations
> > welcome.
>
> You aren't reading Imre Lakatos, by any chance?

No. Should I be?


> Anyhow, that's an
> outstanding effort (by this group standards) that has a chance to be
> repaired.

My current crazy idea is to learn Coq and see if it can't help
me with these sorts of questions. It is called a "proof assistant"
isn't it? I could use an assistant right about now. And probably
a personal trainer as well.


> A similar manipulation for dual law (with jon and union swapped)
> reveals a that it has to meet the same criteria.

I think so. I have spent significantly less time looking at this
one. But we would expect the results to be the same because
of the duality.


> Although I seem to
> have (a pathological?) counterexample.
>
> Let
>
> `1` := {x=1}
> `2b` := {x=2, y=b}
>
> 00,01,10, and 11 are defined as before. Then
>
> 00 || (`1` && `2b`) = 00
> (00 || `1`) && (00 || `2b`) = 01 && 01 = 01

Very interesting.

I really haven't finished my examination of the situation, and
I don't think I've drawn the right conclusion yet from step six.
I think I begin to perceive why this counterexample does
what it does.

More work to do. My book on Coq just showed up from Amazon
yesterday. We'll see if it can help.


Marshall
 >> Stay informed about: Relational Lattice, what is it good for? 
Back to top
Login to vote
Display posts from previous:   
Related Topics:
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..

TRUE and FALSE values in the relational lattice - Given a relation R(x,y) with domains x={0,1,2}, y={'a','b'} we know from classic predicate theory that the expression R(x=0, y='a') evaluates to true or false. Here is how we establish this siumple fact in the relational lattice. First, lets substitut...

Proof of Completeness of Algebraic Properties of Relationa.. - The Relational Lattice algebra ("RL") consists of two generic operations on relations: natural join, written "&&", and inner &#117;nion, written "||". It has been shown that the RL operations possess the followi...
   Database Forums (Home) -> Technology and Theory All times are: Pacific Time (US & Canada)
Goto page 1, 2
Page 1 of 2

 
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

Warning: fopen(/home/adsense_reject.txt) [function.fopen]: failed to open stream: Permission denied in /home/autoforu/public_html/Giga/GigaFunctions.php on line 1142

Warning: fwrite(): supplied argument is not a valid stream resource in /home/autoforu/public_html/Giga/GigaFunctions.php on line 1143

Warning: fclose(): supplied argument is not a valid stream resource in /home/autoforu/public_html/Giga/GigaFunctions.php on line 1144



[ Contact us | Terms of Service/Privacy Policy ]