Re: Relational Lattice, what is it good for?

(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).
>
Received on Wed Feb 15 2006 - 23:56:34 CET