# 1
| |||

| |||

## |

# 2
| |||

| |||

## |

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

*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

# 3
| |||

| |||

## |

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

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.

# 4
| |||

| |||

## |

On Dec 27, 9:15 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote: |

Quote:

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

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

# 5
| |||

| |||

## |

On Dec 27, 9:15 pm, Kira Yamato <kira... (AT) earthlink (DOT) 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. |

defining morphisms between databases.

--

-kira

# 6
| ||||

| ||||

## |

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

(For instance, the identity. But obviously the non-identities

are more interesting.) Less precise terms that could be used are

"symmetry" or "ambiguity".)

Quote:

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

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.

Quote:

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

between a database instance and itself.

Quote:

-kira |

Reinier

# 7
| ||||

| ||||

## |

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

(For instance, the identity. But obviously the non-identities

are more interesting.) Less precise terms that could be used are

"symmetry" or "ambiguity".)

Quote:

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

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.

Quote:

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

between a database instance and itself.

Quote:

-kira |

Reinier

# 8
| ||||

| ||||

## |

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

(For instance, the identity. But obviously the non-identities

are more interesting.) Less precise terms that could be used are

"symmetry" or "ambiguity".)

Quote:

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

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.

Quote:

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

between a database instance and itself.

Quote:

-kira |

Reinier

# 9
| ||||

| ||||

## |

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

(For instance, the identity. But obviously the non-identities

are more interesting.) Less precise terms that could be used are

"symmetry" or "ambiguity".)

Quote:

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

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.

Quote:

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

between a database instance and itself.

Quote:

-kira |

Reinier

# 10
| ||||

| ||||

## |

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

(For instance, the identity. But obviously the non-identities

are more interesting.) Less precise terms that could be used are

"symmetry" or "ambiguity".)

Quote:

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

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.

Quote:

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

between a database instance and itself.

Quote:

-kira |

Reinier