What is an automorphism of a database instance?

#71

On Jan 9, 1:15 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 11:13 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a database instanc
e.

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?

I only just saw your posting so I wondered if you still needed help
with this.

Thanks for the follow-up. The notion is still somewhat ambiguous in my
mind. I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same information."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

OK, this amounts to additional requirement that f is bijective and
f^-1 is homomorphism as well. Alternatively, given that join and union
define order relation, one may borrow the order isomorphism
definition
http://en.wikipedia.org/wiki/Order_isomorphism
verbatim.

#72

On Jan 9, 1:15 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 11:13 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a database instanc
e.

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?

I only just saw your posting so I wondered if you still needed help
with this.

Thanks for the follow-up. The notion is still somewhat ambiguous in my
mind. I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same information."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

OK, this amounts to additional requirement that f is bijective and
f^-1 is homomorphism as well. Alternatively, given that join and union
define order relation, one may borrow the order isomorphism
definition
http://en.wikipedia.org/wiki/Order_isomorphism
verbatim.

#73

On Jan 9, 1:15 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 11:13 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a database instanc
e.

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?

I only just saw your posting so I wondered if you still needed help
with this.

Thanks for the follow-up. The notion is still somewhat ambiguous in my
mind. I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same information."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

OK, this amounts to additional requirement that f is bijective and
f^-1 is homomorphism as well. Alternatively, given that join and union
define order relation, one may borrow the order isomorphism
definition
http://en.wikipedia.org/wiki/Order_isomorphism
verbatim.

#74

On Jan 9, 1:15 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 11:13 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a database instanc
e.

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?

I only just saw your posting so I wondered if you still needed help
with this.

Thanks for the follow-up. The notion is still somewhat ambiguous in my
mind. I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same information."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

OK, this amounts to additional requirement that f is bijective and
f^-1 is homomorphism as well. Alternatively, given that join and union
define order relation, one may borrow the order isomorphism
definition
http://en.wikipedia.org/wiki/Order_isomorphism
verbatim.

#75

On Jan 9, 1:15 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 11:13 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a database instanc
e.

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?

I only just saw your posting so I wondered if you still needed help
with this.

Thanks for the follow-up. The notion is still somewhat ambiguous in my
mind. I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same information."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

OK, this amounts to additional requirement that f is bijective and
f^-1 is homomorphism as well. Alternatively, given that join and union
define order relation, one may borrow the order isomorphism
definition
http://en.wikipedia.org/wiki/Order_isomorphism
verbatim.

#76

On Jan 9, 1:15 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 11:13 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a database instanc
e.

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?

I only just saw your posting so I wondered if you still needed help
with this.

Thanks for the follow-up. The notion is still somewhat ambiguous in my
mind. I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same information."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

OK, this amounts to additional requirement that f is bijective and
f^-1 is homomorphism as well. Alternatively, given that join and union
define order relation, one may borrow the order isomorphism
definition
http://en.wikipedia.org/wiki/Order_isomorphism
verbatim.

#77

On Jan 9, 1:15 pm, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 11:13 am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a database instanc
e.

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?

I only just saw your posting so I wondered if you still needed help
with this.

Thanks for the follow-up. The notion is still somewhat ambiguous in my
mind. I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same information."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

OK, this amounts to additional requirement that f is bijective and
f^-1 is homomorphism as well. Alternatively, given that join and union
define order relation, one may borrow the order isomorphism
definition
http://en.wikipedia.org/wiki/Order_isomorphism
verbatim.

#78

On 2008-01-09 16:15:46 -0500, Jan Hidders <hidders (AT) gmail (DOT) com> said:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:
On Jan 9, 11:13*am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29*am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a databas
e instanc
e.

The following definition is from the book Relational Database The
ory 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 databa
se
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 t
he
structure of an underlying set. *For example, if in some set wh
ose
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 bein
g
preserved by 2)? *Can someone explain the formalization in 2) m
ore
carefully?

I only just saw your posting so I wondered if you still needed hel
p
with this.

Thanks for the follow-up. *The notion is still somewhat ambiguous
in my
mind. *I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference
in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same in
formation."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

Just to be explicit here: I assume here that /\ and \/ represents
inner union and natural join respectively as defined in the relational
lattice paper you pointed out to me before.

And Q and R can represent not only the actual extensional relations but
also the intensional ones (the infinite relations that represents
algebraic expressions of domains).

In this way, the two operations /\ and \/ can represent all of the
classical relational algebra operations.

Quote:

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

To show that it is not too general, it is enough to show that /\ and \/
can be represented by expressions using the classical relational
algebra, no? Then, the algebra of /\ and \/ and the classical
relational algebra are equivalent.

Quote:

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

Usually in mathematics, a homomorphism is a map that preserves some
algebraic structure of the underlying sets.

An isomorphism is a homomorphism that is 1-1 and onto.

An endomorphism is a homomorphism from a set to itself.

An automorphism is both an endomorphism and an isomorphism.

So, technically, if Tegiri imposes that f be 1-1 and onto too, then it
is automorphism.

To stretch things a bit further using Tegiri's idea, suppose we have
two database instances from two different database schema: say database
A has relations A1, A2, ..., denoted by
A = { A1, A2, ... };
and database B has relations B1, B2, ..., denoted by
B = { B1, B2, ... }.
Here, the relations are not only the extensional ones but also all
possible relations in the closure of the relational algebra.

Now, suppose we have a map
f : A --> B.
We can impose that f satisfies
f(Ai /\ Aj) = f(Ai) /\ f(Aj)
and
f(Ai \/ Aj) = f(Ai) \/ f(Aj)
for any i, j. This could be a candidate for a homomorphism between two
arbitrary database instances.

If we further impose that f be 1-1 and onto, then we have an
isomorphism between two arbitrary database instances. I think this is
what I was aiming at.

And lastly, if B = A, then we have an automorphism.

BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

--

-kira

#79

On 2008-01-09 16:15:46 -0500, Jan Hidders <hidders (AT) gmail (DOT) com> said:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:
On Jan 9, 11:13*am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29*am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a databas
e instanc
e.

The following definition is from the book Relational Database The
ory 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 databa
se
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 t
he
structure of an underlying set. *For example, if in some set wh
ose
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 bein
g
preserved by 2)? *Can someone explain the formalization in 2) m
ore
carefully?

I only just saw your posting so I wondered if you still needed hel
p
with this.

Thanks for the follow-up. *The notion is still somewhat ambiguous
in my
mind. *I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference
in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same in
formation."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

Just to be explicit here: I assume here that /\ and \/ represents
inner union and natural join respectively as defined in the relational
lattice paper you pointed out to me before.

And Q and R can represent not only the actual extensional relations but
also the intensional ones (the infinite relations that represents
algebraic expressions of domains).

In this way, the two operations /\ and \/ can represent all of the
classical relational algebra operations.

Quote:

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

To show that it is not too general, it is enough to show that /\ and \/
can be represented by expressions using the classical relational
algebra, no? Then, the algebra of /\ and \/ and the classical
relational algebra are equivalent.

Quote:

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

Usually in mathematics, a homomorphism is a map that preserves some
algebraic structure of the underlying sets.

An isomorphism is a homomorphism that is 1-1 and onto.

An endomorphism is a homomorphism from a set to itself.

An automorphism is both an endomorphism and an isomorphism.

So, technically, if Tegiri imposes that f be 1-1 and onto too, then it
is automorphism.

To stretch things a bit further using Tegiri's idea, suppose we have
two database instances from two different database schema: say database
A has relations A1, A2, ..., denoted by
A = { A1, A2, ... };
and database B has relations B1, B2, ..., denoted by
B = { B1, B2, ... }.
Here, the relations are not only the extensional ones but also all
possible relations in the closure of the relational algebra.

Now, suppose we have a map
f : A --> B.
We can impose that f satisfies
f(Ai /\ Aj) = f(Ai) /\ f(Aj)
and
f(Ai \/ Aj) = f(Ai) \/ f(Aj)
for any i, j. This could be a candidate for a homomorphism between two
arbitrary database instances.

If we further impose that f be 1-1 and onto, then we have an
isomorphism between two arbitrary database instances. I think this is
what I was aiming at.

And lastly, if B = A, then we have an automorphism.

BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

--

-kira

#80

On 2008-01-09 16:15:46 -0500, Jan Hidders <hidders (AT) gmail (DOT) com> said:

Quote:

On 9 jan, 20:57, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:
On Jan 9, 11:13*am, Jan Hidders <hidd... (AT) gmail (DOT) com> wrote:

On 9 jan, 19:10, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

On Jan 9, 12:29*am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 28 dec 2007, 06:15, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
I need help in understanding what is an automorphism of a databas
e instanc
e.

The following definition is from the book Relational Database The
ory 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 databa
se
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 t
he
structure of an underlying set. *For example, if in some set wh
ose
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 bein
g
preserved by 2)? *Can someone explain the formalization in 2) m
ore
carefully?

I only just saw your posting so I wondered if you still needed hel
p
with this.

Thanks for the follow-up. *The notion is still somewhat ambiguous
in my
mind. *I sort of feel where I want to end up, but it is somewhat
difficult to formulate it in rigorous formalism.

What I want to formalize is the notion that two databases are
"essentially" containing the "same information" modulo a difference
in
labelings of the names of the relations/attributes/values.

The difficulty is in formalizing the term "essentially" and "same in
formation."

I suggest defining automorphism of database instance (where "database
instance" is understood to be a set of relations) algebraically as a
mapping f such that for any relations Q and R

f(Q /\ R ) = f(Q) /\ f(R)
f(Q \/ R ) = f(Q) \/ f(R)

Just to be explicit here: I assume here that /\ and \/ represents
inner union and natural join respectively as defined in the relational
lattice paper you pointed out to me before.

And Q and R can represent not only the actual extensional relations but
also the intensional ones (the infinite relations that represents
algebraic expressions of domains).

In this way, the two operations /\ and \/ can represent all of the
classical relational algebra operations.

Quote:

this is general enough to cover both domain value permutations and
column/relation renamings.

How do you know that it is not too general?

I don't:-(

To show that it is not too general, it is enough to show that /\ and \/
can be represented by expressions using the classical relational
algebra, no? Then, the algebra of /\ and \/ and the classical
relational algebra are equivalent.

Quote:

Btw. didn't you mean "homomorphism" rather than "automorphism"?

Automorphism is a homomorphism of a database instanse into itself,
isn't it?

It's usually defined as a kind of isomorphism.

Usually in mathematics, a homomorphism is a map that preserves some
algebraic structure of the underlying sets.

An isomorphism is a homomorphism that is 1-1 and onto.

An endomorphism is a homomorphism from a set to itself.

An automorphism is both an endomorphism and an isomorphism.

So, technically, if Tegiri imposes that f be 1-1 and onto too, then it
is automorphism.

To stretch things a bit further using Tegiri's idea, suppose we have
two database instances from two different database schema: say database
A has relations A1, A2, ..., denoted by
A = { A1, A2, ... };
and database B has relations B1, B2, ..., denoted by
B = { B1, B2, ... }.
Here, the relations are not only the extensional ones but also all
possible relations in the closure of the relational algebra.

Now, suppose we have a map
f : A --> B.
We can impose that f satisfies
f(Ai /\ Aj) = f(Ai) /\ f(Aj)
and
f(Ai \/ Aj) = f(Ai) \/ f(Aj)
for any i, j. This could be a candidate for a homomorphism between two
arbitrary database instances.

If we further impose that f be 1-1 and onto, then we have an
isomorphism between two arbitrary database instances. I think this is
what I was aiming at.

And lastly, if B = A, then we have an automorphism.

BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

--

-kira