Re: What is an automorphism of a database instance?

From: Jan Hidders <hidders_at_gmail.com>
Date: Thu, 10 Jan 2008 07:25:29 -0800 (PST)
Message-ID: <d5317152-6151-48dd-99dc-ed7aa1da0586_at_m77g2000hsc.googlegroups.com>


On 10 jan, 01:14, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
> On Jan 9, 4:02 pm, Kira Yamato <kira..._at_earthlink.net> wrote:
>
>
>
> > On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena..._at_gmail.com> said:
>
> > > On Jan 9, 3:29 pm, Kira Yamato <kira..._at_earthlink.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:-)

That would be the Atzeni definition but extended such that is also 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
Received on Thu Jan 10 2008 - 16:25:29 CET

Original text of this message