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

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?

Thanks.

--

-kira

On 2007-12-28 00:15:49 -0500, Kira Yamato <kirakun (AT) earthlink (DOT) net> said:

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?

--

-kira

On Dec 27, 9:15 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
Well, in mathematics you rarely find an algebra with 7 (or 8?)
operations. Moreover, the operations are syntactically unattractive.
The elements of the algebra are relations, and yet
some operations like projection and selection take an additional
parameter, which is outside of the realm of
the relation objects. Some operations like union can't be applied to
any pair of relations. The explicit
renaming operation is like nothing else in mathematics, where renaming
variables has never been a big deal.

If this line of thought resonates with you, please check up
http://arxiv.org/ftp/cs/papers/0603/0603044.pdf
There are 2 homomorhisms of relational algebra into boolean algebras
there.

Tegiri Nenashi wrote:

[snip]

Does Preparation H work well for that?




(Sorry, just kidding, I couldn't resist.)

On 2007-12-28 13:07:54 -0500, Tegiri Nenashi <TegiriNenashi (AT) gmail (DOT) com> said:

Thank you for that link. It is certainly one direction to look into in
defining morphisms between databases.

--

-kira

Kira Yamato wrote:

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

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

--
Reinier

Kira Yamato wrote:

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

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

--
Reinier

Kira Yamato wrote:

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

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

--
Reinier

Kira Yamato wrote:

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

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

--
Reinier

Kira Yamato wrote:

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

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

--
Reinier