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

From: Kira Yamato <kirakun_at_earthlink.net>

Date: Wed, 9 Jan 2008 03:29:36 -0500

Message-ID: <2008010903293650073-kirakun_at_earthlinknet>

>> I need help in understanding what is an automorphism of a database instanc

>> Definition: An automorphism of a database instance r is a partial function

>> preserved by 2)? Can someone explain the formalization in 2) more

>> carefully?

Date: Wed, 9 Jan 2008 03:29:36 -0500

Message-ID: <2008010903293650073-kirakun_at_earthlinknet>

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidders_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."

-- -kiraReceived on Wed Jan 09 2008 - 09:29:36 CET