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

Date: Wed, 9 Jan 2008 01:29:02 -0800 (PST)

Message-ID: <11fa0483-c98f-489a-8323-ac7bf3910f20_at_u10g2000prn.googlegroups.com>

On 9 jan, 09:29, 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 notion of auto/isomorfism as presented by Atzeni et al. assumes that you only relabel values. If you also want to relabel relation names you extend the function h such that it also permutes relation names and attribute names, and generalize its application to a database accordingly.

> The difficulty is in formalizing the term "essentially" and "same information."

Whether a formalization is appropriate depends on what you want to use the notion for. What did you have in mind?

- Jan Hidders