dbTalk Databases Forums  

What is an automorphism of a database instance?

comp.databases.theory comp.databases.theory


Discuss What is an automorphism of a database instance? in the comp.databases.theory forum.

Reply
 
Thread Tools Display Modes
  #1  
Old   
Kira Yamato
 
Posts: n/a

Default What is an automorphism of a database instance? - 12-28-2007 , 12:15 AM






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




Reply With Quote
  #2  
Old   
Kira Yamato
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 12-28-2007 , 01:13 AM






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

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



Reply With Quote
  #3  
Old   
Tegiri Nenashi
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 12-28-2007 , 01:07 PM



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



Reply With Quote
  #4  
Old   
Bob Badour
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 12-28-2007 , 04:35 PM



Tegiri Nenashi wrote:

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

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.
Does Preparation H work well for that?




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


Reply With Quote
  #5  
Old   
Kira Yamato
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 12-29-2007 , 01:04 AM



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

Quote:
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.
Thank you for that link. It is certainly one direction to look into in
defining morphisms between databases.

--

-kira



Reply With Quote
  #6  
Old   
rpost
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 01-06-2008 , 07:55 PM



Kira Yamato wrote:

Quote:
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".)

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

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?
This is exactly that notion, except that automorphisms are isomorphisms
between a database instance and itself.

Quote:
-kira
--
Reinier


Reply With Quote
  #7  
Old   
rpost
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 01-06-2008 , 07:55 PM



Kira Yamato wrote:

Quote:
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".)

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

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?
This is exactly that notion, except that automorphisms are isomorphisms
between a database instance and itself.

Quote:
-kira
--
Reinier


Reply With Quote
  #8  
Old   
rpost
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 01-06-2008 , 07:55 PM



Kira Yamato wrote:

Quote:
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".)

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

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?
This is exactly that notion, except that automorphisms are isomorphisms
between a database instance and itself.

Quote:
-kira
--
Reinier


Reply With Quote
  #9  
Old   
rpost
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 01-06-2008 , 07:55 PM



Kira Yamato wrote:

Quote:
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".)

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

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?
This is exactly that notion, except that automorphisms are isomorphisms
between a database instance and itself.

Quote:
-kira
--
Reinier


Reply With Quote
  #10  
Old   
rpost
 
Posts: n/a

Default Re: What is an automorphism of a database instance? - 01-06-2008 , 07:55 PM






Kira Yamato wrote:

Quote:
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".)

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

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?
This is exactly that notion, except that automorphisms are isomorphisms
between a database instance and itself.

Quote:
-kira
--
Reinier


Reply With Quote
Reply




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off



Powered by vBulletin Version 3.5.3
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.