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

From: Tegiri Nenashi <TegiriNenashi_at_gmail.com>
Date: Wed, 9 Jan 2008 10:10:55 -0800 (PST)

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.

Exersize 1. Show that a mapping of database instance in the example of the rpost message is automorphism in algebraic sence. Received on Wed Jan 09 2008 - 19:10:55 CET

Original text of this message