Re: What is an automorphism of a database instance?

Kira Yamato wrote:

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

It is an isomorphism of a database instance onto itself. (For instance, the identity. But obviously the non-identities are more interesting.) Less precise terms that could be used are "symmetry" or "ambiguity".)

>> 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?

The structure being preserved is that of the database: e.g., tuples and tables map to tuples and tables of the same size.

E.g. on the table

  A B

  x y
  y z
  y w

the automorphisms are the identity and the swapping of w and z.

>On a different but related question, is there a notation of
>*isomorphism* between two database instances?
>In another word, is there a way to formalize the notation that two
>databases are essentially containing the same information, except for a
>difference in the labeling of the attribute names and domain-value
>names?

This is exactly that notion, except that automorphisms are isomorphisms between a database instance and itself.

>-kira

-- 
Reinier