# Re: What is an automorphism of a database instance?

Date: Wed, 9 Jan 2008 13:15:46 -0800 (PST)

Message-ID: <02829179-be61-4f7d-afe3-e5fc1ee0f73a_at_v29g2000hsf.googlegroups.com>

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:

> On Jan 9, 11:13 am, Jan Hidders <hidd..._at_gmail.com> wrote:

*>
**>
**>
**> > On 9 jan, 19:10, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
**>
**> > > On Jan 9, 12:29 am, Kira Yamato <kira..._at_earthlink.net> wrote:
**>
**> > > > On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd..._at_gmail.com> said:
**>
**> > > > > On 28 dec 2007, 06:15, Kira Yamato <kira..._at_earthlink.net> wrote:
**> > > > >> I need help in understanding what is an automorphism of a database instanc
**> > > > > e.
**>
**> > > > >> The following definition is from the book Relational Database Theory by
**> > > > >> Atzeni and De Antonellis:
**>
**> > > > >> Definition: An automorphism of a database instance r is a partial function
**>
**> > > > >> h : D --> D
**> > > > >> where D is the domain of the database r such that
**> > > > >> 1) the partial function h is a permutation of the active domain D_r, and
**> > > > >> 2) when we extend its definition to tuples, relations, and database
**> > > > >> instances, we obtain a function on instances that is the identity on r,
**> > > > >> namely
**> > > > >> h(r) = r.
**>
**> > > > >> I can understand 1), but I cannot understand 2).
**>
**> > > > >> In mathematics, an automorphism is a 1-1 mapping that preserves the
**> > > > >> structure of an underlying set. For example, if in some set whose
**> > > > >> members x, y and z obeys
**> > > > >> z = x + y,
**> > > > >> then we expect an automorphism f on that set to also obey
**> > > > >> f(z) = f(x) + f(y).
**> > > > >> So, the structure of "addition" is preserved.
**>
**> > > > >> Now, back to relational database theory, what "structure" is being
**> > > > >> preserved by 2)? Can someone explain the formalization in 2) more
**> > > > >> carefully?
**>
**> > > > > I only just saw your posting so I wondered if you still needed help
**> > > > > with this.
**>
**> > > > Thanks for the follow-up. The notion is still somewhat ambiguous in my
**> > > > mind. I sort of feel where I want to end up, but it is somewhat
**> > > > difficult to formulate it in rigorous formalism.
**>
**> > > > What I want to formalize is the notion that two databases are
**> > > > "essentially" containing the "same information" modulo a difference in
**> > > > labelings of the names of the relations/attributes/values.
**>
**> > > > The difficulty is in formalizing the term "essentially" and "same information."
**>
**> > > I suggest defining automorphism of database instance (where "database
**> > > instance" is understood to be a set of relations) algebraically as a
**> > > mapping f such that for any relations Q and R
**>
**> > > f(Q /\ R ) = f(Q) /\ f(R)
**> > > f(Q \/ R ) = f(Q) \/ f(R)
**>
**> > > this is general enough to cover both domain value permutations and
**> > > column/relation renamings.
**>
**> > How do you know that it is not too general?
**>
**> I don't:-(
**>
**> > Btw. didn't you mean "homomorphism" rather than "automorphism"?
**>
**> Automorphism is a homomorphism of a database instanse into itself,
**> isn't it?
*

It's usually defined as a kind of isomorphism.

- Jan Hidders