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

completeness of the relational lattice

 
Goto page 1, 2, 3, 4, 5
   Database Forums (Home) -> Technology and Theory RSS
Next:  TRUE and FALSE values in the relational lattice  
Author Message
Jan Hidders

External


Since: Jun 11, 2007
Posts: 185



(Msg. 1) Posted: Fri Jun 22, 2007 1:06 pm
Post subject: completeness of the relational lattice
Archived from groups: comp>databases>theory (more info?)

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 time I spent on proving things might be lost. I think
it's also important that we settle on notation, because I noticed I
was getting confused. Since it's bascially Vadim's idea I'll try to
stick to his notation as much as possible.

So the syntax of the algebra is as follows: (E is the non-terminal for
algebra expressions)
- R : a relation name
- E /\ E : the natural join
- E \/ E : the inner union
- 00 : the empty relation with empty header
- 01 : the relation with the empty tuple and empty header
- 10 : the empty relation with the set of all attributes as header
- 11 : the relation with all tuples over all attributes
- [x] : the empty relation over header {x} with x a single attribute
- 'x=y' : the binary equality relation with header {x,y} and the
restriction that x<>y

I don't like having 10 and 11 because it clearly steps outside the
relational model and first order logic, but I see no direct reasons to
remove them. There was some doubt on the presence of [x] but I don't
see how we can otherwise define projection. Also I don't see how we
can avoid mentioning attributes since we already have 'x=y' where the
are already mentioned.

So can we agree on this algebra and notation?

-- Jan Hidders

 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 2) Posted: Fri Jun 22, 2007 1:58 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 8:57 am, Marshall wrote:
> (Over in sci.math, they mostly use ^ v for conjunction/disjunction
> instead of /\ \/. Once I got over my horror of seeing a letter
> used as an operator in mostly worked for me. Do we care?)

I was blissfully unaware of ^ v . I'm switching to them and reserve
big ones for quantifiers (if such things would ever make an
apearance)

> Oh, we haven't mentioned precedence. I propose \/ and /\
> have the same precedence, so that when we write
> the dual of an expression, we will never have to add
> any parentheses.

OK

> > So the syntax of the algebra is as follows: (E is the non-terminal for
> > algebra expressions)
> > - R : a relation name
> > - E /\ E : the natural join
> > - E \/ E : the inner union
> > - 00 : the empty relation with empty header
> > - 01 : the relation with the empty tuple and empty header
> > - 10 : the empty relation with the set of all attributes as header
> > - 11 : the relation with all tuples over all attributes
> > - [x] : the empty relation over header {x} with x a single attribute
> > - 'x=y' : the binary equality relation with header {x,y} and the
> > restriction that x<>y
>
> I believe we might be able to get along without the last three.
> (11, [x], and `x=y`.) And if we do need to talk about attributes,
> I think we need to be talking about sets of attributes. (So x
> above would be a set.)

IMO the axioms would drive the notation. If there is no important
axiom that involves 11 (I think there is), then we skip it. I suggest
that the set

{00,01,10,11}

such that

01 < 00 < 10
01 < 11 < 10
00 ^ 11 = 10
00 v 11 = 01
00 != 11

is a smallest nontrivial relational lattice model.

> > There was some doubt on the presence of [x] but I don't
> > see how we can otherwise define projection.
>
> Any expression of the form
>
> E \/ [x]
>
> can be rewritten as
>
> E \/ (X /\ 00)
>
> where X is any relation with the same header as [x]. I don't
> know that we need to be able to say what that header *is*,
> but we need to be able to say "free relation variable with
> fixed header." I think the latter is necessary and sufficient.

Nice observation.

Overall, let's shoot down some axioms, then the rest of the notation
would fall in place.

 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Jan Hidders

External


Since: Jun 11, 2007
Posts: 185



(Msg. 3) Posted: Fri Jun 22, 2007 2:08 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

(moving some of the discussion in "TRUE and FALSE values in the
relational lattice" to this thread)

On 22 jun, 06:52, Vadim Tropashko wrote:
> On 22 Jun 2007, at 03:20, Jan Hidders wrote:
>
>
>
> > On 22 Jun 2007, at 02:51, Vadim Tropashko wrote:
>
> >> Jan Hidders wrote:
>
> >>> On 22 Jun 2007, at 02:36, Vadim Tropashko wrote:
>
> >>>> I doubt a normal form for RL expressions exists. (If you insist otherwise, we can play a little game when I give you an example and you reduce it to a normal form).
>
> >>>> An example may be n-th iteration of transitive closure.
> > So you are telling me to normalize:
>
> > R(x,y) \/ ( ( (R(x,y)/\`y=z`) \/ [x,z] ) /\ ( (R(x,y)/\`x=z` ) \/ [z,y] ) ) \/ ...
>
> > Let me first give you a smaller example. Suppose you have:
>
> > R /\ ( S \/ 'z=y') with R(x,y) and S(y,z)
>
> Careful there! You probably don't want to union anything with equality
> relation. You must have meant:
>
> (R(x,y) /\ `x=z`) \/ [z,y]
>
> where [z,y] is subsequntly generalized to S(y,z).

No, I meant what I wrote. It doesn't do anything that seems
meaningful, but that is besides the point.

> > We cannot distribute in general, but we have a specific distribution rule:
>
> > (1) r /\ ((s \/ [H]) \/ (t\/[H])) = r /\ (s \/ [H]) \/ r*(t \/ [H])
>
> Which is BTW a very limited case embraced by Spight criteria.

Indeed. But it is a simple equation, no premises.

> Once again, we are interested if union distributes over join, not if
> join distributes over union.

?? No, here I'm interested if join distributes over union, because I
want a union normal form.

> BTW, why don't we define square brackets [R] as an unary operator,
> expressed in my notation as
>
> [R] = R /\ 00

What is R? In [R] it is a set of attributes. So a set of attributes is
a valid expression in your syntax? I'm not sure what that means. Could
you give a complete definition of your syntax just like I did?

> What is the (B=B) (e.g. in set builder notation)?

The unary relation with header {B} that contains all possible values:
{ (BMad} | x in Domain }. But as you see in my other posting, I'm ok
with disallowing that.

-- Jan Hidders
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 4) Posted: Fri Jun 22, 2007 2:14 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 9:42 am, Jan Hidders wrote:
> Marshall schreef:
> > Any expression of the form
>
> > E \/ [x]
>
> > can be rewritten as
>
> > E \/ (X /\ 00)
>
> > where X is any relation with the same header as [x].
>
> ?? Either you can express it or you cannot. Either you can give me an
> expression equivalent to [x] or you cannot. An expression that is only
> equivalent under certain circumstances is not good enough. It means
> your expressive power in terms of queries that you can express drops
> below that of the unions of conjunctive queries (UCQ). If the database
> consists of just R(a,b) then how can I project on {a}, or on {c,d}?

You cannot. If the database consists of just a single nonempty
relation R(x,y), then the whole lattice consists just of 4 elements:

00, R(x,y),
00 /\ R(x,y) = 10, and
00 \/ R(x,y) = 01

..
..
..
..
..
..
..
..
..
..
(drumroll)
..
..
..
..
..
..
..
..
..
For all practical purposes here R(x,y) is indistinguisheble from 11.
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 5) Posted: Fri Jun 22, 2007 2:36 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 3:08 am, Jan Hidders wrote:
> > > We cannot distribute in general, but we have a specific distribution rule:
>
> > > (1) r /\ ((s \/ [H]) \/ (t\/[H])) = r /\ (s \/ [H]) \/ r*(t \/ [H])
>
> > Which is BTW a very limited case embraced by Spight criteria.
>
> Indeed. But it is a simple equation, no premises.

Your premise is that H is a set of attributes which is a subset of
attributes of relations s and t -- for me it is no different (although
less general) than Spight criteria.

> > Once again, we are interested if union distributes over join, not if
> > join distributes over union.
>
> ?? No, here I'm interested if join distributes over union, because I
> want a union normal form.

I was confused with your example. Aiming for union normal form is
indeed bettr than for join normal form because join over union
distributivity in relational lattice is less restrictive!

> > BTW, why don't we define square brackets [R] as an unary operator,
> > expressed in my notation as
>
> > [R] = R /\ 00
>
> What is R? In [R] it is a set of attributes. So a set of attributes is
> a valid expression in your syntax? I'm not sure what that means.

Set of attributes = empty relation

> Could
> you give a complete definition of your syntax just like I did?

- R : a relation name
- Expr /\ Expr : the natural join
- Expr \/ Expr : the inner union
- 00 : the empty relation with empty header
- 01 : the relation with the empty tuple and empty header
- 10 : the empty relation with the set of all attributes as header
- 11 : the relation with all tuples over all attributes
- E : the "universal" equlity relation

Once again, I'm not convinced about syntax until I see a convincing
set of axioms.
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 6) Posted: Fri Jun 22, 2007 2:56 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 10:36 am, Vadim Tropashko
wrote:
> - R : a relation name
> - Expr /\ Expr : the natural join
> - Expr \/ Expr : the inner union
> - 00 : the empty relation with empty header
> - 01 : the relation with the empty tuple and empty header
> - 10 : the empty relation with the set of all attributes as header
> - 11 : the relation with all tuples over all attributes
> - E : the "universal" equlity relation

Axioms:
01 /\ R = R
10 \/ R = R
R = (R /\ 00) \/ (R /\ 11)
00 /\ (R \/ S) = (00 /\ R) \/ (00 /\ S)
11 \/ (R /\ S) = (11 \/ R) /\ (11 \/ S)

I don't seem to be able to express the properties of equality E in
pure equational settings. The have to be some premises...
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 7) Posted: Fri Jun 22, 2007 3:29 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 10:56 am, Vadim Tropashko
wrote:
> On Jun 22, 10:36 am, Vadim Tropashko
> wrote:
>
> > - R : a relation name
> > - Expr /\ Expr : the natural join
> > - Expr \/ Expr : the inner union
> > - 00 : the empty relation with empty header
> > - 01 : the relation with the empty tuple and empty header
> > - 10 : the empty relation with the set of all attributes as header
> > - 11 : the relation with all tuples over all attributes
> > - E : the "universal" equlity relation
>
> Axioms:
> 01 /\ R = R
> 10 \/ R = R
> R = (R /\ 00) \/ (R /\ 11)
> 00 /\ (R \/ S) = (00 /\ R) \/ (00 /\ S)
> 11 \/ (R /\ S) = (11 \/ R) /\ (11 \/ S)
>
> I don't seem to be able to express the properties of equality E in
> pure equational settings. The have to be some premises...

Before giving the equality axiom let describe informally what the
constant E is. We join all possible equality relations in the system,
so that we have something like this

E = `x=y` /\ `y=z` /\ ... /\ 'a=b' /\ ...

Sure x,y,z have to belong to the same domain, while "a" and "b" may be
from a different domain. This is again an informal definition that is
supposed to drive the intuition.

Now if we take any relation R and if it happens to have attributes
from the same domain, then we are in trouble, because joining R with E
would loose some information. What we need to do is to project E to a
proper set of attributes.

Formally, let X, Y, and Z be a set of disjoint attributes:

X /\ 00 = X
Y /\ 00 = Y
Z /\ 00 = Z

X /\ Y = 00
Y /\ Z = 00
X /\ Z = 00

Let attributes of R be a union of the attributes X and Y:

R /\ 00 = X /\ Y

Finally, let X be an atomic attribute, that is:

00 <= S <= X implies S = 00 or S = X

(where the a <= b is understood to be abbreviation for a /\ b = b)

Then the following identity must hold:

(( (R /\ (E\/(Y/\Z)) ) \/ (X/\Z) ) /\ (E\/(Y/\Z) ) ) /\ (X/\Y) = R

Yes, the axiom looks intimidating, but may I suggest that perhaps we
were over restricted over the properties of the X,Y,Z relations? Maybe
they could be generalized to be not empty and the whole thing would
collapse and simplify to a much nicer form?
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 8) Posted: Fri Jun 22, 2007 4:11 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 11:20 am, Jan Hidders wrote:
> On 22 jun, 19:36, Vadim Tropashko wrote:
>
> > On Jun 22, 3:08 am, Jan Hidders wrote:
>
> > > > > We cannot distribute in general, but we have a specific distribution rule:
>
> > > > > (1) r /\ ((s \/ [H]) \/ (t\/[H])) = r /\ (s \/ [H]) \/ r*(t \/ [H])
>
> > > > Which is BTW a very limited case embraced by Spight criteria.
>
> > > Indeed. But it is a simple equation, no premises.
>
> > Your premise is that H is a set of attributes which is a subset of
> > attributes of relations s and t
>
> No, any set of attributes H will do.

Counterexample:

r(x,y) = {(1,7),(1,4),(2,4),(2,7)}
s(x) = {2}
t(y) = {7}
H = {x,y}

s \/ [H] = {2}
t \/ [H] = {7}
((s \/ [H]) \/ (t\/[H])) = 01
r /\ ((s \/ [H]) \/ (t\/[H])) = *** {(1,7),(1,4),(2,4),(2,7)} ***
r /\ (s \/ [H]) = {(2,4),(2,7)}
r /\ (t \/ [H]) = {(1,7),(2,7)}
r /\ (s \/ [H]) \/ r*(t \/ [H]) = *** {(1,7),(2,4),(2,7)} ***

AFIR you explicitly mentioned that H is a set of attributes which is
intersection of that of s and t -- and that's a premise.

Anyway, let follow Marshall suggestion and move along to axioms.
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 9) Posted: Fri Jun 22, 2007 5:14 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 12:59 pm, Marshall wrote:
> On Jun 22, 12:42 pm, Jan Hidders wrote:
>
> > On 22 jun, 20:36, Marshall wrote:
>
> [lots of agreement snipped]
>
> > > In simplified terms, you're proposing that we allow the
> > > construction of relations with a specific set of attributes
> > > and a specific body (namely: empty.) I'm proposing that
> > > we only allow the construction of relations with a specific
> > > set of attributes. Hence my proposal introduces fewer
> > > concepts, therefore it is simpler, and we should by default
> > > choose the simplest alternative that gets us what we
> > > need.
>
> > Let me see if I understand. So you propose a constructm, say [X] with
> > X a set of attributes, with the semantics that it returns an arbitrary
> > relation with header S.
>
> Ack, no!

May I suggest that there is no concept of relation construction other
than specifying it in terms of other relations via primary lattice
operations? So given any relation we can easily construct an empty
relation with the same set of attributes. On the other hand, given an
empty realtion, there is no way to construct nonempty relation, unless
there are some other relations that we can leverage to.

Also in relational model when we speak and think in terms the set of
the attributes. Sometimes we even have to bring up the concept of
tuple -- a concept that standard RA completely eliminated. What I'm
suggesting is that removing the concept of attributes would benefit us
the same way as abstracting away the concept of tuple. Therefore, I
repeat, the thesis:

"set of attributes" = "empty relation"
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 10) Posted: Fri Jun 22, 2007 7:24 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 2:53 pm, Jan Hidders wrote:
> If you can achieve the expressive power of UCQ that way, I'm all for
> it, but I doubt that you can. And if you cannot then any completeness
> result will become much less interesting and probably not publishable
> in a target that would be interesting for me.

Ok, developing attribute agnostic methods is a separate goal that I
can put aside for a while.

> Maybe a compromise is possible. As you and Marshall already noted it
> holds that
>
> [H] = R /\ 01

typo: [H] = R /\ 00

> for all relations R with header H. This means several things. First it
> means that if you have a complete axiomatization for the algebra
> without [H] you will automatically get a complete axiomatization for
> the algebra with [H] if you add this rule. The procedure for proving
> e_1 = e_2 would be to convert all the occurrences of [H_i] to R_i /\
> 01 with R_i the header H_i, obtaining e'_1 = e'_2, then prove the
> equivalence. It also works the other way around. If we find a complete
> axiomatization for the algebra with [H] and need a certain rule
> involving [H] then the counterpart with [H] replaced should be
> derivable in the axiomatization without [H]. So it is actually
> unlikely that there are fundamental different difficulties in proving
> the completeness of with or without [H].

Agreed, the issue if the [] is requitred is not essential. Again this
notation is handy (see below).

Could we work out an example in order to make comfortable with your
method? Assume R(x,y) and consider the following two expressions:

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

and

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

Are they equivalent or not?

One of the methods you suggested is some kind of distributivity axiom
(in pure equational form). This issue is still hanging, right?

> So we could do the following. I start from the algebra with [H] and
> you start from the algebra without [H] and we both try to prove
> completeness. You tell me the rules that you think you need (because I
> will need those anyway) and I will tell you the rules I think I need
> in addition for [H] (because you will need to check if you have the
> corresponding rule with [H] replaced).

OK

> Deal? Smile

No cliche phrases, please:-)
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Marshall

External


Since: Jun 01, 2007
Posts: 71



(Msg. 11) Posted: Fri Jun 22, 2007 7:57 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 2:06 am, Jan Hidders wrote:
> 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 time I spent on proving things might be lost. I think
> it's also important that we settle on notation, because I noticed I
> was getting confused. Since it's bascially Vadim's idea I'll try to
> stick to his notation as much as possible.

Okay.

(Over in sci.math, they mostly use ^ v for conjunction/disjunction
instead of /\ \/. Once I got over my horror of seeing a letter
used as an operator in mostly worked for me. Do we care?)

Anyway, as mentioned elsewhere, Vadim's notation is a good
mathematic notation, but it makes a poor one for a programming
language, which is my larger interest. I can use his notation for
the newsgroup, but the software that I write will use my own,
since my notation was carefully designed and optimized for
language use.

Oh, we haven't mentioned precedence. I propose \/ and /\
have the same precedence, so that when we write
the dual of an expression, we will never have to add
any parentheses.


> So the syntax of the algebra is as follows: (E is the non-terminal for
> algebra expressions)
> - R : a relation name
> - E /\ E : the natural join
> - E \/ E : the inner union
> - 00 : the empty relation with empty header
> - 01 : the relation with the empty tuple and empty header
> - 10 : the empty relation with the set of all attributes as header
> - 11 : the relation with all tuples over all attributes
> - [x] : the empty relation over header {x} with x a single attribute
> - 'x=y' : the binary equality relation with header {x,y} and the
> restriction that x<>y

I believe we might be able to get along without the last three.
(11, [x], and `x=y`.) And if we do need to talk about attributes,
I think we need to be talking about sets of attributes. (So x
above would be a set.)

I didn't see (relational) = mentioned in there. Is that just assumed?
We need either relational equality or the relational comparator.

Also I don't see division in there yet. We were talking about
including that, weren't we?


> I don't like having 10 and 11 because it clearly steps outside the
> relational model and first order logic, but I see no direct reasons to
> remove them.

10 seems required, because without it, the lattice is neither
bounded nor complete, whereas with it it is both. Complete
lattices are much nicer to work with. Also, 10 can be thought
of a just an atom, rather than having any infinite properties.
And looking at these equations it appears quite benign:

10 /\ R = 10
10 \/ R = R

11 is more problematic, not only because of its infinity of
infinities,
but also because its infinities are "contagious."

11 /\ R

has an infinite number of attributes and an infinite number of rows,
but some (few) projections of it have a finite number of rows.

11 \/ R
is more tractable, in that it has the same (finite) attributes as R
but infinite rows.


> There was some doubt on the presence of [x] but I don't
> see how we can otherwise define projection.

Any expression of the form

E \/ [x]

can be rewritten as

E \/ (X /\ 00)

where X is any relation with the same header as [x]. I don't
know that we need to be able to say what that header *is*,
but we need to be able to say "free relation variable with
fixed header." I think the latter is necessary and sufficient.


> Also I don't see how we can avoid mentioning attributes
> since we already have 'x=y' where the are already mentioned.

Will go looking for where we use that and respond there.


> So can we agree on this algebra and notation?

Sure, modulo the questions above.


Marshall
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Vadim Tropashko

External


Since: Jun 01, 2007
Posts: 69



(Msg. 12) Posted: Fri Jun 22, 2007 8:05 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 3:31 pm, Jan Hidders wrote:
> I can probably simplify using Marshall's rule. Assuming I
> have a function A(e) that gives the header of the result of e:
>
> r /\ (s \/ t) = (r /\ s) \/ (r /\ t) if (A(r) * (A(s)) - A(t) is
> empty and (A(r) * A(t)) - A(s) is empty

OK, to summarize we have 2-sorted algebra:
1. Relations (which is lattice)
2. Relation headers (which is standard BA)
The function A maps relations to headers, and enjoys the following
rule
A(R \/ B) = A(R) intersect A(B)
Note that function A is not a homomorhism, that is the dual identity
A(R /\ B) = A(R) union A(B)
doesn't hold.

Please also note, that in my notation the algebra is not many sorted.
I want to emphasize not this fact, however, but that the "crippled
homomorphism" rule above becomes an identity
00 /\ (R \/ B) = (00 /\ A) \/ (00 /\ B)
which is a special case of distributivity. So you try to formulate the
premise for the Spight criteria and distributivity in a limited
context of the 00 element shows up -- I find it remarkable.

Let me also reiterate that some cases can't be cracked even with
Spight criteria, and

(00 /\ R) \/ (11 /\ R)

is one of them. If Marhall casts doubts here on the existance of the
11 element, my reply would be take any relation "big enough" instead
of 11.

BTW, if you have finction A, then we probably don't need element 00,
right? (The element A(01) is just an empty set in the boolean algebra
of headers, not the lattice element 00)
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Marshall

External


Since: Jun 01, 2007
Posts: 71



(Msg. 13) Posted: Fri Jun 22, 2007 8:32 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Expanding a bit...

On Jun 22, 8:57 am, Marshall wrote:
>
> 11 is more problematic, not only because of its infinity of
> infinities, but also because its infinities are "contagious."

(Note that 10 doesn't have any contagions.)

The one loss if we leave out 11 is the fundamental
decomposition identity. However, it hasn't been established
yet that there's anything we can do with it that we can't
do without it. We may also be able to still find it useful
without bringing it in to the formal system. That is,
it can show us what to look for.


Marshall
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Marshall

External


Since: Jun 01, 2007
Posts: 71



(Msg. 14) Posted: Fri Jun 22, 2007 8:42 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

On Jun 22, 8:57 am, Marshall wrote:
> On Jun 22, 2:06 am, Jan Hidders wrote:
>
> Also I don't see division in there yet. We were talking about
> including that, weren't we?

Oh, duh, you already said adding division makes it undecidable.
Okay.


Marshall
 >> Stay informed about: completeness of the relational lattice 
Back to top
Login to vote
Jan Hidders

External


Since: Jun 11, 2007
Posts: 185



(Msg. 15) Posted: Fri Jun 22, 2007 8:42 pm
Post subject: Re: completeness of the relational lattice [Login to view extended thread Info.]
Archived from groups: per prev. post (more info?)

Marshall schreef:
> On Jun 22, 2:06 am, Jan Hidders wrote:
> > 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 time I spent on proving things might be lost. I think
> > it's also important that we settle on notation, because I noticed I
> > was getting confused. Since it's bascially Vadim's idea I'll try to
> > stick to his notation as much as possible.
>
> Okay.
>
> (Over in sci.math, they mostly use ^ v for conjunction/disjunction
> instead of /\ \/. Once I got over my horror of seeing a letter
> used as an operator in mostly worked for me. Do we care?)

I care about fixing a notation. Which one is of minor importance for
me. Of course I like mine the best. Smile

> Oh, we haven't mentioned precedence. I propose \/ and /\
> have the same precedence, so that when we write
> the dual of an expression, we will never have to add
> any parentheses.

Agreed.

> > So the syntax of the algebra is as follows: (E is the non-terminal for
> > algebra expressions)
> > - R : a relation name
> > - E /\ E : the natural join
> > - E \/ E : the inner union
> > - 00 : the empty relation with empty header
> > - 01 : the relation with the empty tuple and empty header
> > - 10 : the empty relation with the set of all attributes as header
> > - 11 : the relation with all tuples over all attributes
> > - [x] : the empty relation over header {x} with x a single attribute
> > - 'x=y' : the binary equality relation with header {x,y} and the
> > restriction that x<>y
>
> I believe we might be able to get along without the last three.
> (11, [x], and `x=y`.) And if we do need to talk about attributes,
> I think we need to be talking about sets of attributes. (So x
> above would be a set.)
>
> I didn't see (relational) = mentioned in there. Is that just assumed?
> We need either relational equality or the relational comparator.

Because this is the syntax for the algebra. So the expressions defined
are queries, not propositions. The propositions will all be of the
form e1 = e2 where e1 and e2 are expresssions in the algebra but
sometimes with variables instead of relations.

> Also I don't see division in there yet. We were talking about
> including that, weren't we?

Yes. I strongly suggest to postpone adding division and difference
until we have a completeness result without them. I'm fairly certain
they will make our task impossible, so I first want to try without
them.

> > I don't like having 10 and 11 because it clearly steps outside the
> > relational model and first order logic, but I see no direct reasons to
> > remove them.
>
> 10 seems required, because without it, the lattice is neither
> bounded nor complete, whereas with it it is both.

Well, as I said, I accept them, so I'm not going to argue against
them. But if we run into trouble because of them during the
completeness proof, I reserve the right to say "See! I told you!". Smile

> > There was some doubt on the presence of [x] but I don't
> > see how we can otherwise define projection.
>
> Any expression of the form
>
> E \/ [x]
>
> can be rewritten as
>
> E \/ (X /\ 00)
>
> where X is any relation with the same header as [x].

?? Either you can express it or you cannot. Either you can give me an
expression equivalent to [x] or you cannot. An expression that is only
equivalent under certain circumstances is not good enough. It means
your expressive power in terms of queries that you can express drops
below that of the unions of conjunctive queries (UCQ). If the database
consists of just R(a,b) then how can I project on {a}, or on {c,d}?

What your argument does show however is that reasoning over
projections is going to be similar to reasoning over relations for
which we know certain equations hold. So the equations we need for [x]
can probably be readily derived from that. There is probably not
really something fundamentally new here and the soundness of the extra
rules can be easily proved using the usual laws. But proving that can
only be done by allowing the construct and proceeding with the proof.

> > Also I don't see how we can avoid mentioning attributes
> > since we already have 'x=y' where the are already mentioned.
>
> Will go looking for where we use that and respond there.

You need to be able to express simple equality selections which are in
UCQ. Also here you need to show that you can come up with an
expression that is always equivalent. I don't think you can without
introducing another construct. In fact, it is not hard to proof that
there are queries you cannot express without 'x=y' and [x] since you
can only express only projections (and not even all of them) of the
natural join of all relations in the database, which is a very weak
class indeed.

> > So can we agree on this algebra and notation?
>
> Sure, modulo the questions above.

Great! Progress! Smile

-- Jan Hidders
 >> Stay informed about: completeness of 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...

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, 3, 4, 5
Page 1 of 5

 
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 ]