 | |
#121
 
| |||
| |||
|
Re: What is an automorphism of a database instance? -
01-10-2008
, 09:25 AM
|
On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said: On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: BTW, do we need to impose partial ordering preserved too? *Partial ordering defined as A <= B if and only if A = A /\ B. A = A /\ B imply f(A) = f(A /\ B) which implies f(A) = f(A) /\ f(B) which in turn imply f(A) <= f(B) Of course, it's obvious from the definition! Therefore, actually, all we need is an isomorphism of upper (or lower) semi-lattice! Which brings to the point you raised early: quote How do you know that it is not too general? I don't:-( To show that it is not too general, it is enough to show that /\ and \/ can be represented by expressions using the classical relational algebra, no? *Then, the algebra of /\ and \/ and the classical relational algebra are equivalent. /quote The lattice join is trivially expressed via relational algebra join (and we don't even have to bother with rather easy problem of expressing inner union is in terms of classic RA). Unfortunately, I understand Jan's comment differently. An isomorphism is an equivalence relation. How do we know it is not "too coarse"? But this is rather fuzzy idea, unless Jan points out to alternative "finer" definition:-) |
allows relabeling of attribute names. You can probably figure out the
exact definition yourself. Let's call that an Atzeni isomorphism. If
you want to show that your definition indeed means what you claim it
means then you should prove that these are equivalent, i.e., two
databases are Atzeni isomorphic iff they are Nenashi isomorphic.
-- Jan Hidders
#122
| |||
| |||
|
|
On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said: On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: BTW, do we need to impose partial ordering preserved too? *Partial ordering defined as A <= B if and only if A = A /\ B. A = A /\ B imply f(A) = f(A /\ B) which implies f(A) = f(A) /\ f(B) which in turn imply f(A) <= f(B) Of course, it's obvious from the definition! Therefore, actually, all we need is an isomorphism of upper (or lower) semi-lattice! Which brings to the point you raised early: quote How do you know that it is not too general? I don't:-( To show that it is not too general, it is enough to show that /\ and \/ can be represented by expressions using the classical relational algebra, no? *Then, the algebra of /\ and \/ and the classical relational algebra are equivalent. /quote The lattice join is trivially expressed via relational algebra join (and we don't even have to bother with rather easy problem of expressing inner union is in terms of classic RA). Unfortunately, I understand Jan's comment differently. An isomorphism is an equivalence relation. How do we know it is not "too coarse"? But this is rather fuzzy idea, unless Jan points out to alternative "finer" definition:-) |
allows relabeling of attribute names. You can probably figure out the
exact definition yourself. Let's call that an Atzeni isomorphism. If
you want to show that your definition indeed means what you claim it
means then you should prove that these are equivalent, i.e., two
databases are Atzeni isomorphic iff they are Nenashi isomorphic.
-- Jan Hidders
#123
| |||
| |||
|
|
On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said: On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: BTW, do we need to impose partial ordering preserved too? *Partial ordering defined as A <= B if and only if A = A /\ B. A = A /\ B imply f(A) = f(A /\ B) which implies f(A) = f(A) /\ f(B) which in turn imply f(A) <= f(B) Of course, it's obvious from the definition! Therefore, actually, all we need is an isomorphism of upper (or lower) semi-lattice! Which brings to the point you raised early: quote How do you know that it is not too general? I don't:-( To show that it is not too general, it is enough to show that /\ and \/ can be represented by expressions using the classical relational algebra, no? *Then, the algebra of /\ and \/ and the classical relational algebra are equivalent. /quote The lattice join is trivially expressed via relational algebra join (and we don't even have to bother with rather easy problem of expressing inner union is in terms of classic RA). Unfortunately, I understand Jan's comment differently. An isomorphism is an equivalence relation. How do we know it is not "too coarse"? But this is rather fuzzy idea, unless Jan points out to alternative "finer" definition:-) |
allows relabeling of attribute names. You can probably figure out the
exact definition yourself. Let's call that an Atzeni isomorphism. If
you want to show that your definition indeed means what you claim it
means then you should prove that these are equivalent, i.e., two
databases are Atzeni isomorphic iff they are Nenashi isomorphic.
-- Jan Hidders
#124
| |||
| |||
|
|
On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said: On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: BTW, do we need to impose partial ordering preserved too? *Partial ordering defined as A <= B if and only if A = A /\ B. A = A /\ B imply f(A) = f(A /\ B) which implies f(A) = f(A) /\ f(B) which in turn imply f(A) <= f(B) Of course, it's obvious from the definition! Therefore, actually, all we need is an isomorphism of upper (or lower) semi-lattice! Which brings to the point you raised early: quote How do you know that it is not too general? I don't:-( To show that it is not too general, it is enough to show that /\ and \/ can be represented by expressions using the classical relational algebra, no? *Then, the algebra of /\ and \/ and the classical relational algebra are equivalent. /quote The lattice join is trivially expressed via relational algebra join (and we don't even have to bother with rather easy problem of expressing inner union is in terms of classic RA). Unfortunately, I understand Jan's comment differently. An isomorphism is an equivalence relation. How do we know it is not "too coarse"? But this is rather fuzzy idea, unless Jan points out to alternative "finer" definition:-) |
allows relabeling of attribute names. You can probably figure out the
exact definition yourself. Let's call that an Atzeni isomorphism. If
you want to show that your definition indeed means what you claim it
means then you should prove that these are equivalent, i.e., two
databases are Atzeni isomorphic iff they are Nenashi isomorphic.
-- Jan Hidders
#125
| |||
| |||
|
|
On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said: On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: BTW, do we need to impose partial ordering preserved too? *Partial ordering defined as A <= B if and only if A = A /\ B. A = A /\ B imply f(A) = f(A /\ B) which implies f(A) = f(A) /\ f(B) which in turn imply f(A) <= f(B) Of course, it's obvious from the definition! Therefore, actually, all we need is an isomorphism of upper (or lower) semi-lattice! Which brings to the point you raised early: quote How do you know that it is not too general? I don't:-( To show that it is not too general, it is enough to show that /\ and \/ can be represented by expressions using the classical relational algebra, no? *Then, the algebra of /\ and \/ and the classical relational algebra are equivalent. /quote The lattice join is trivially expressed via relational algebra join (and we don't even have to bother with rather easy problem of expressing inner union is in terms of classic RA). Unfortunately, I understand Jan's comment differently. An isomorphism is an equivalence relation. How do we know it is not "too coarse"? But this is rather fuzzy idea, unless Jan points out to alternative "finer" definition:-) |
allows relabeling of attribute names. You can probably figure out the
exact definition yourself. Let's call that an Atzeni isomorphism. If
you want to show that your definition indeed means what you claim it
means then you should prove that these are equivalent, i.e., two
databases are Atzeni isomorphic iff they are Nenashi isomorphic.
-- Jan Hidders
 |
« Previous Thread
|
Next Thread »
| Thread Tools | |
| Display Modes | |
Linear Mode
| |
Powered by vBulletin Version 3.5.3
Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.
Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.