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

TRUE and FALSE values in the relational lattice

 
Goto page 1, 2
   Database Forums (Home) -> Technology and Theory RSS
Next:  Hierarchical query  
Author Message
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 1) Posted: Tue Jun 19, 2007 2:51 pm
Post subject: TRUE and FALSE values in the relational lattice
Archived from groups: comp>databases>theory (more info?)

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 substitute x -> x=0 into R(x,y) and get unary relation
R'(y). The formula for such substitution is

R'(y) = R(0,y) = (R /\ `x=0`) \/ `y`

where `x=0' is unary relation with one tuple {0} and attribute x, and
`y` is the unary empty relation with attribute y. Informally, we
select all the tuples in R such that x=0 and project the result to
column y.

Next, we substitute y -> y=a into R'(y) and obtain "emptiary"
relation R":

R"({}) = R(0,'a') = ( ( (R /\ `x=0`) \/ `y` ) /\ `y=a` ) \/ 00

It is instructive to apply the distributivity criteria (I lost count
how many times I leveraged it!) and simplify the expression to

R(0,'a') = ( R /\ `x=0` /\ `y=a` ) \/ 00

As expected this expression is valued to 00 or 01, so Marshall was
eventually right when interpreting those relations as TRUE and FALSE.

 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 2) Posted: Tue Jun 19, 2007 6:06 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 19, 1:32 pm, Marshall wrote:
> Not to be contrary, but I've revised my thinking in that area.
> I now equate 10 as false rather than 00. Any other relation
> equates to true, especially, of course, 01.

Propositional logic is a predicate calculus of zilliary predicates
(zilliary predicates are the ones that have less arguments than unary
ones:-) Therefore, associating any other relation than 01 and 00 with
TRUE and FALSE, correspondingly, doesn't seem right.

> The relevance that 00 plays is in relation to existential
> quantification.
> I interpret existential quantification as meaning a relation is not
> empty.

Could you please be more specific?

Assuming the domain x = {a,b,c,d,...} the relation "exists(x) R(x,y)"
evaluates to

R(a,y) \/ R(b,y) \/ R(c,y) \/ R(d,y) \/ ...

I don't see any emptiness here.

> We can define exists(X) as:
>
> X | 00 = 01

You lost me here as well. Perhaps, you mean that the relational
equality is an operator that evaluates to a certain relation? Can you
be more specific?

 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 3) Posted: Tue Jun 19, 2007 8:16 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 19, 2:51 pm, Marshall wrote:
> On Jun 19, 2:06 pm, Vadim Tropashko
> wrote:
> > Therefore, associating any other relation than 01 and 00 with
> > TRUE and FALSE, correspondingly, doesn't seem right.
>
> I agree with the feeling; it is why I was saying 00 and 01
> previously....
> Well, I just wrote up an explanation and it wasn't at all convincing.
> I'll have to review my notes. Perhaps I have been overly influenced
> by reading lattice logic papers that don't have 00.

The confusing part is that there are many homomorphisms of relational
lattice into various boolean algebras. And in boolean algebra we
always have TRUE as the top lattice element and the FALSE is the
bottom. Figure 2 of
http://arxiv.org/ftp/cs/papers/0603/0603044.pdf
shows 4. One of them is the 16 element boolean algebra highlighted in
blue, which has the top element 10, and the bottom element 11.

The other important homomorhism is concerned whether relation is empty
or not, so that the lattice is mapped into the boolean algebra of the
two elements 00 (top) and 01 (bottom).

Recently, in the "relational lattice complement" thread you discovered
something, which turned out to be yet another homomorphism:

R -> (R \/ 00) /\ (R \/ 11)

The target boolean algebra has the top element coinsident with the top
lattice one 10, and the bottom element coinsident with the bottom
lattice element 01.

> > Assuming the domain x = {a,b,c,d,...} the relation "exists(x) R(x,y)"
> > evaluates to
>
> > R(a,y) \/ R(b,y) \/ R(c,y) \/ R(d,y) \/ ...
>
> > I don't see any emptiness here.
>
> It seems you are defining existential quantification as something
> that is relation valued, but I am used to thinking of it as truth-
> valued.
>
> Assuming
>
> R(a1,b1)

Let me doublecheck that a1 and b1 are supposed to be some values here.

> Is your definition any different than
>
> R /\ `x=a1`
>
> Here a1 is an attribute name and x is free, aka a parameter
> of the expression.

Now I'm confused. If "a1" is an attribute name (I thought it is
value), what is then "x"?

In the epression from my earlier post:

R(a1,y) \/ R(a2,y) \/ R(a3,y) \/ R(a4,y) \/ ...

each unary relation R(ak,y) is defined as

R(ak,y) =def= (R /\ `x=ak`) \/ `y`

so I kind of see your "R /\ `x=a1`" as a fragment of this
definition...
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Marshall

External


Since: Jun 01, 2007
Posts: 71



(Msg. 4) Posted: Wed Jun 20, 2007 12:32 am
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 19, 10:51 am, Vadim Tropashko
wrote:
> 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 substitute x -> x=0 into R(x,y) and get unary relation
> R'(y). The formula for such substitution is
>
> R'(y) = R(0,y) = (R /\ `x=0`) \/ `y`
>
> where `x=0' is unary relation with one tuple {0} and attribute x, and
> `y` is the unary empty relation with attribute y. Informally, we
> select all the tuples in R such that x=0 and project the result to
> column y.
>
> Next, we substitute y -> y=a into R'(y) and obtain "emptiary"
> relation R":
>
> R"({}) = R(0,'a') = ( ( (R /\ `x=0`) \/ `y` ) /\ `y=a` ) \/ 00
>
> It is instructive to apply the distributivity criteria (I lost count
> how many times I leveraged it!) and simplify the expression to
>
> R(0,'a') = ( R /\ `x=0` /\ `y=a` ) \/ 00
>
> As expected this expression is valued to 00 or 01, so Marshall was
> eventually right when interpreting those relations as TRUE and FALSE.

Not to be contrary, but I've revised my thinking in that area.
I now equate 10 as false rather than 00. Any other relation
equates to true, especially, of course, 01.

The relevance that 00 plays is in relation to existential
quantification.
I interpret existential quantification as meaning a relation is not
empty.

We can define exists(X) as:

X | 00 = 01

Where = is a primitive that returns either 10 or 01 according
the usual meaning.

As far as lattice order goes, it is usually written , meaning

A B iff (A & B = A)

(In case that character doesn't display correctly, it's the usual
single character version of <=.)

However this relations closely corresponds to logical implication,
which is often written =>. It almost looks like a comparison
operator, coincidentally. Since there is some value in writing
the relational operators differently than the scalar ones, it
might make sense to use => as the way to write this relation.
Thus:

10 => A
A => 01

etc.

I know Vadim is not thrilled with my notation, however
we are thinking of different audiences. He is more concerned
with maintaining fidelity with mathematical notation, and I'm
interested in a notation that will be palatable to programmers.
So we naturally reach different results.

I am thinking about formalizing the lattice logic. That would
involve a formal statement of the axioms and the rules of
inference. We would then want a soundness proof, and
a proof of consistency. We would also want to understand
how complete such a logic would be, and how strong it
was relative to FOL. And how decidable. My hope is
that it is decidable even if that means it is weaker than
FOL. We also have to think about what else besides
& and | we're putting in to it. Clearly 00 is a strong
candidate. I'm currently thinking that the negation
operator I defined a week or two ago is *not* a good idea.
The scary one is division/group by.

All this requires a better understanding of logic and proof
theory than I currently possess. So I have some trepidation,
along with a lot of required reading.

It turns out a lot of this work has already been done for
complete lattices, and this work will just be an extension
of that.

It is interesting to consider the question of whether to take
equality or the order relation as primitive. Each can be
defined in terms of the other. However I am finding it
easier to write inference rules against the order than
against equality.


Marshall
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Marshall

External


Since: Jun 01, 2007
Posts: 71



(Msg. 5) Posted: Wed Jun 20, 2007 1:51 am
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 19, 2:06 pm, Vadim Tropashko
wrote:
> On Jun 19, 1:32 pm, Marshall wrote:
>
> > Not to be contrary, but I've revised my thinking in that area.
> > I now equate 10 as false rather than 00. Any other relation
> > equates to true, especially, of course, 01.
>
> Propositional logic is a predicate calculus of zilliary predicates
> (zilliary predicates are the ones that have less arguments than unary
> ones:-) Therefore, associating any other relation than 01 and 00 with
> TRUE and FALSE, correspondingly, doesn't seem right.

I agree with the feeling; it is why I was saying 00 and 01
previously....
Well, I just wrote up an explanation and it wasn't at all convincing.
I'll have to review my notes. Perhaps I have been overly influenced
by reading lattice logic papers that don't have 00.


> > The relevance that 00 plays is in relation to existential
> > quantification.
> > I interpret existential quantification as meaning a relation is not
> > empty.
>
> Could you please be more specific?
>
> Assuming the domain x = {a,b,c,d,...} the relation "exists(x) R(x,y)"
> evaluates to
>
> R(a,y) \/ R(b,y) \/ R(c,y) \/ R(d,y) \/ ...
>
> I don't see any emptiness here.

It seems you are defining existential quantification as something
that is relation valued, but I am used to thinking of it as truth-
valued.

Assuming

R(a1,b1)

Is your definition any different than

R /\ `x=a1`

Here a1 is an attribute name and x is free, aka a parameter
of the expression.


> > We can define exists(X) as:
>
> > X | 00 = 01
>
> You lost me here as well. Perhaps, you mean that the relational
> equality is an operator that evaluates to a certain relation? Can you
> be more specific?

I mean that = could be a binary
relational operator like & and | are. It evaluates to one of only
two possible relation values: 10 or 01. (Presumably if I change my
mind back again it would be "00 or 01.")

Thus:

(00 = 00) evaluates to 01.
(10 = 01) evaluates to 10.
(A = A) evaluates to 01.

etc.


Marshall
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Jon Heggland

External


Since: Mar 23, 2006
Posts: 126



(Msg. 6) Posted: Wed Jun 20, 2007 12:40 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Vadim Tropashko wrote:
> As expected this expression is valued to 00 or 01, so Marshall was
> eventually right when interpreting those relations as TRUE and FALSE.

Not to disparage your contributions or anything, but hasn't the
association between TABLE_DUM / 00 and FALSE, and TABLE_DEE / 01 and
TRUE been known for many, many years?
--
Jon
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Marshall

External


Since: Jun 01, 2007
Posts: 71



(Msg. 7) Posted: Thu Jun 21, 2007 8:21 am
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 19, 11:40 pm, Jon Heggland wrote:
> Vadim Tropashko wrote:
> > As expected this expression is valued to 00 or 01, so Marshall was
> > eventually right when interpreting those relations as TRUE and FALSE.
>
> Not to disparage your contributions or anything, but hasn't the
> association between TABLE_DUM / 00 and FALSE, and TABLE_DEE / 01 and
> TRUE been known for many, many years?

Not sure who the "you" in "your" is here, but I figure it's either
me or Vadim. Yes, in the regular relational algebra, the
correspondence
has been known for years. In the relational lattice, it hasn't
been established whether that's the best choice yet. In fact,
it's not clear what the correspondence *means.* Note that
various authors, such as Dijkstra and D&D (in TTM) advocate
a dedicated two-valued boolean type, despite the correspondence.
I've been thinking for a while that that may not be necessary;
it may be sufficient just to use DEE (aka 01) and some other
value, either 00 or 10 depending on when you ask me. Smile


Marshall
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Jan Hidders

External


Since: Jun 11, 2007
Posts: 185



(Msg. 8) Posted: Thu Jun 21, 2007 2:14 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On 19 jun, 22:32, Marshall wrote:
>
>
>
> I am thinking about formalizing the lattice logic. That would
> involve a formal statement of the axioms and the rules of
> inference. We would then want a soundness proof, and
> a proof of consistency. We would also want to understand
> how complete such a logic would be, and how strong it
> was relative to FOL. And how decidable. My hope is
> that it is decidable even if that means it is weaker than
> FOL. We also have to think about what else besides
> & and | we're putting in to it. Clearly 00 is a strong
> candidate. I'm currently thinking that the negation
> operator I defined a week or two ago is *not* a good idea.
> The scary one is division/group by.

I would assume the following operations: (in yet another notation)
- E * E : natural join
- E + E : generalized union
- {()} : the relation with empty header and a single empty tuple
- [A,B,..D] : the empty relation with header {A, B, ..., D} (possibly
the empty set)
- A=B : the equality relation with header {A, B}
- A=c : the relation with header {A} and tuple (A:c)
- R : a relation with name R (and known header)

That would be roughly equivalent with unions of conjunctive queries,
for which equivalence is known to be decidable. Adding the set
difference or division would make it relationally complete (so, FOL)
and make this undecidable.

Actually, a (sound and complete) axiomatization would be a small but
publishable result. It doesn't seem that impossible either. You could
start with showing that you have enough rules to bring the thing into
some union normal form, and then show that you also have enough rules
to show a homomorfisme over the conjuncts. Quite interesting indeed.
Anyone interested in thinking about a paper on that?

-- Jan Hidders
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 9) Posted: Thu Jun 21, 2007 2:26 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 21, 3:14 am, Jan Hidders wrote:
> I would assume the following operations: (in yet another notation)
> - E * E : natural join
> - E + E : generalized union

Eh, 3 different people, 3 different notations:-)

> - {()} : the relation with empty header and a single empty tuple

OK

> - [A,B,..D] : the empty relation with header {A, B, ..., D} (possibly
> the empty set)

This is nice proposal. How abotut small letters for attributes and
capital letters for relations?

One of my (yet not realized) goals is to get rid of the attributes
completely. Every time we have some relational lattice identity which
mentions attribute x, the x can always be thought of as a composite
attribute. And in relational terms a composite attribute is either an
empty relation with header x, or a or cartesian product of domains.
Therefore an attribute x, being it composite or not is just a relation
x which satisfies the identity

x /\ 00 = x

(empty relation constraint), or

X \/ 11 = X

(full domain constraint). Therefore, perhaps the distinction between
attributes and relations is not so clear cut to warrant capital and
small letter notation?

> - A=B : the equality relation with header {A, B}
> - A=c : the relation with header {A} and tuple (A:c)

Single tuple element is a relation R such that

R /\ 00 != R

and there is no relation X such that

R < X < R /\ 00

where the "<" operation is understood to be the strict lattice order:
"greater than (and not equal)"

Defining equality relation is an intersting venture by itself. I can
suggest few identities. Assuming R(x,y)

(((R /\ (y=y') ) \/ [x,y'] ) /\ (y=y') ) \/ [x,y] = R

Again, for this to become a true axion it better be transformed into
attribute agnostic form, something like this:

(( (R /\ E) \/ (X /\ Y') ) /\ E ) \/ (X /\ Y) = R
X /\ 00 = X
Y /\ 00 = Y
Y' /\ 00 = Y'
E /\ 00 = X /\ Y /\ 00
R /\ 00 = X /\ Y /\ 00
X \/ Y = 00
X \/ Y' = 00
Y \/ Y' = 00

Clearly, the straightforward translation produced such an unwieldy
mess that there has to be a more concise axioms.

> - R : a relation with name R (and known header)

Yes! Again, this is how algebraic identity should look like: relation
variables (no attributes in parenthesis!), constant relation symbols,
and algebraic operations.

> That would be roughly equivalent with unions of conjunctive queries,
> for which equivalence is known to be decidable. Adding the set
> difference or division would make it relationally complete (so, FOL)
> and make this undecidable.
>
> Actually, a (sound and complete) axiomatization would be a small but
> publishable result. It doesn't seem that impossible either. You could
> start with showing that you have enough rules to bring the thing into
> some union normal form, and then show that you also have enough rules
> to show a homomorfisme over the conjuncts. Quite interesting indeed.
> Anyone interested in thinking about a paper on that?

This is nice research program. If the other exchange taught any
lessons, then spelling out every minute detail would be one of them:-)
Could you please clarify (with an example!) what "homomorfism over the
conjuncts" you have in mind?
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 10) Posted: Thu Jun 21, 2007 2:46 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 21, 2:25 am, Jon Heggland wrote:
> Heh. If you ask me, it would be nice if R /\ TRUE = R, R /\ FALSE =
> FALSE, R \/ TRUE = TRUE and R \/ FALSE = R. That requires 01 for TRUE
> and 10 for FALSE, right?

This shows once again how evasive the concepts of truth and falseness
are:-)

Thanks for supporting my notation, BTW;-)
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 11) Posted: Thu Jun 21, 2007 2:51 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 21, 7:12 am, Marshall wrote:
> I would be interested to have the axioms for division
> especially.

Here is a cute identity involving set equality join (not division!),
and equality relation:

((R /=\ E) /=\ E ) = R

where the "/=\" is a symbol for set equality join.
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Jon Heggland

External


Since: Mar 23, 2006
Posts: 126



(Msg. 12) Posted: Thu Jun 21, 2007 3:25 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall wrote:
> On Jun 19, 11:40 pm, Jon Heggland wrote:
>> Vadim Tropashko wrote:
>>> As expected this expression is valued to 00 or 01, so Marshall was
>>> eventually right when interpreting those relations as TRUE and FALSE.
>> Not to disparage your contributions or anything, but hasn't the
>> association between TABLE_DUM / 00 and FALSE, and TABLE_DEE / 01 and
>> TRUE been known for many, many years?
>
> Not sure who the "you" in "your" is here, but I figure it's either
> me or Vadim.

Or both. Smile

> Yes, in the regular relational algebra, the correspondence
> has been known for years. In the relational lattice, it hasn't
> been established whether that's the best choice yet.

Do (either of) you expect the lattice to produce anything genuinely new
and/or different from the regular algebra? (Has it already? I haven't
been paying all that much attention, since my initial impression was
that it was a clever notation, but not really different from the old
algebra. In particular, the original post in this thread seemed to me
merely a restatement that projection is existential quantification,
selection and join is the same, and so on.)

> In fact,
> it's not clear what the correspondence *means.* Note that
> various authors, such as Dijkstra and D&D (in TTM) advocate
> a dedicated two-valued boolean type, despite the correspondence.

Why? Is this an important point for them? Anyway, I'd say there is a
difference in that a relation is the set of variable bindings that make
a given predicate true, and the DEE/DUM relations are the one to use if
the predicate in question is in fact a proposition---whereas a truth
value is just a trust value. I don't know if it matters much, though.
Perhaps one could have a relation-valued possrep for type BOOLEAN? That
might satisfy everybody ... Smile

> I've been thinking for a while that that may not be necessary;
> it may be sufficient just to use DEE (aka 01) and some other
> value, either 00 or 10 depending on when you ask me. Smile

Heh. If you ask me, it would be nice if R /\ TRUE = R, R /\ FALSE =
FALSE, R \/ TRUE = TRUE and R \/ FALSE = R. That requires 01 for TRUE
and 10 for FALSE, right? Or perhaps some magic X0-FALSE that grabs its
attribute set from the context ...
--
Jon
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 13) Posted: Thu Jun 21, 2007 6:08 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 21, 10:51 am, Vadim Tropashko
wrote:
> Here is a cute identity involving set equality join (not division!),
> and equality relation:
>
> ((R /=\ E) /=\ E ) = R
>
> where the "/=\" is a symbol for set equality join.

More about equality relation. Equality relation is defined as
antisymmetric equivalence relation. Unfortunately, the definition is
circular because antysymmetry is defined via equality! So let's focus
on equivalence relation axioms, first. We have

x=x

which can't be interpeted in any meninful way in the relational
theory. Then we have

x=y implies y=x

which isn't again a meaningful statement in the relational theory,
because any binary relation is symmetric in a sense that the order of
attributes doesn't really matter.

This can be contrasted to Tarski relation algebra where both
properties can be expressed.

Transitivity, however can be expressed. We can use set join /=\ or
natural join /\ followed by projection in order to exclude "middle"
column. So we have

`x=y` /=\ `y=z` = `x=z`

This again defines equivalence only, not equality. In order to define
equality transitivity has to be strengthened into the following law:

R(x,y) /=\ `y=z` = R(x,z)

Again, attribute agnostic expression would require to use relation R
with the same set of attributes. We therefore join the both sides of
the above identity with equality `y=z` to get

R(x,y) /=\ `y=z` /=\ `y=z` = R(x,y)

Notice that atrributes of the relation R and `y=z` "overlap" in a
certain way. Clearly the identity

R(x,y) /=\ `x=y` /=\ `x=y` = R(x,y)

is wrong.

On the other, hand we can generalize the above identity to hold for a
ternary equality relation!

R(x,u,v,w) /=\ `x=y=z` /=\ `x=y=z` = R(x,u,v,w)

One more case is when attributes don't overlap, but it is valid for
any relation S(x,y,z), not just equality:

R(u,v,w) /=\ S(x,y,z) /=\ S(x,y,z) = R(u,v,w)
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
Marshall

External


Since: Jun 01, 2007
Posts: 71



(Msg. 14) Posted: Thu Jun 21, 2007 6:12 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 21, 3:14 am, Jan Hidders wrote:
> On 19 jun, 22:32, Marshall wrote:
>
> > I am thinking about formalizing the lattice logic. That would
> > involve a formal statement of the axioms and the rules of
> > inference. We would then want a soundness proof, and
> > a proof of consistency. We would also want to understand
> > how complete such a logic would be, and how strong it
> > was relative to FOL. And how decidable. My hope is
> > that it is decidable even if that means it is weaker than
> > FOL. We also have to think about what else besides
> > & and | we're putting in to it. Clearly 00 is a strong
> > candidate. I'm currently thinking that the negation
> > operator I defined a week or two ago is *not* a good idea.
> > The scary one is division/group by.
>
> I would assume the following operations: (in yet another notation)
> - E * E : natural join
> - E + E : generalized union
> - {()} : the relation with empty header and a single empty tuple
> - [A,B,..D] : the empty relation with header {A, B, ..., D} (possibly
> the empty set)
> - A=B : the equality relation with header {A, B}
> - A=c : the relation with header {A} and tuple (A:c)
> - R : a relation with name R (and known header)
>
> That would be roughly equivalent with unions of conjunctive queries,
> for which equivalence is known to be decidable.

Hmm. But without generalized distributivity, we can't always
reduce an expression to conjunctive normal form nor
disjunctive normal form. We might have a conjunction of
a disjunction of a conjunction that we can't reduce. Doesn't
that mean we can't always decide equivalence? Mightn't
there be two irreducible expressions that are always
equal but we can't prove it?


> Adding the set difference or division
> would make it relationally complete (so, FOL)
> and make this undecidable.

I would be interested to have the axioms for division
especially. (Have you seen the stuff Vadim's written
on the relationship between division and group-by?)
Earlier I was playing around with complement, but
it introduces infinities into what can otherwise be
a completely finite system.


> Actually, a (sound and complete) axiomatization would be a small but
> publishable result. It doesn't seem that impossible either. You could
> start with showing that you have enough rules to bring the thing into
> some union normal form, and then show that you also have enough rules
> to show a homomorfisme over the conjuncts. Quite interesting indeed.
> Anyone interested in thinking about a paper on that?

Yes.

These are the papers I've found that come closest to this sort
of thing:

http://citeseer.ist.psu.edu/437168.html

http://consequently.org/writing/gndl/

As an aside, I wrote a modest expression simplifier, that
took advantage of all the lattice axioms. I want to add
inference rules to it and make it in to a theorem prover.
Perhaps just one rule is sufficient? With lattice order
as implication, a rule that takes A & (A=>B) into
A & (A => B) & B, perhaps?

This is also motivating my interest in division--what are
its axioms?

Going further, I am working on a system for allowing
join to work with functions, and include aggregators,
generators, and many-to-many functions, and to
build a programming language capable of executing
all of this. (Aggregators are applied with division.)


Marshall
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
Back to top
Login to vote
David Cressey

External


Since: Mar 19, 2007
Posts: 550



(Msg. 15) Posted: Thu Jun 21, 2007 10:39 pm
Post subject: Re: TRUE and FALSE values in the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

"Vadim Tropashko" wrote in message

> On Jun 21, 3:14 am, Jan Hidders wrote:
> > I would assume the following operations: (in yet another notation)
> > - E * E : natural join
> > - E + E : generalized union
>
> Eh, 3 different people, 3 different notations:-)
>
> > - {()} : the relation with empty header and a single empty tuple
>
> OK
>
> > - [A,B,..D] : the empty relation with header {A, B, ..., D} (possibly
> > the empty set)
>
> This is nice proposal. How abotut small letters for attributes and
> capital letters for relations?
>

Why not the following?

{A,B,..D ()}
 >> Stay informed about: TRUE and FALSE values in the relational lattice 
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..

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



[ Contact us | Terms of Service/Privacy Policy ]