Re: What is an automorphism of a database instance?

On Dec 27, 9:15 pm, Kira Yamato <kira..._at_earthlink.net> wrote:
> 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?

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. Received on Fri Dec 28 2007 - 19:07:54 CET