Relational Lattice, what is it good for?
Date: 15 Feb 2006 12:06:30 -0800
Message-ID: <1140033990.018699.9120_at_g44g2000cwa.googlegroups.com>
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). Received on Wed Feb 15 2006 - 21:06:30 CET