What is an automorphism of a database instance?

#**101**

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNenashi (AT) gmail (DOT) com> said:

Quote:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Thanks.

Quote:

AFAIR in lattice theory an order isomorphism is the same as
isomorphism defined in terms of operations /\ and \/.

--

-kira

#**102**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**103**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**104**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**105**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**106**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**107**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**108**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**109**

On Jan 9, 4:02 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:

Quote:

On 2008-01-09 18:53:17 -0500, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> said:

On Jan 9, 3:29 pm, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
BTW, do we need to impose partial ordering preserved too? Partial
ordering defined as
A <= B
if and only if
A = A /\ B.

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

Of course, it's obvious from the definition!

Therefore, actually, all we need is an isomorphism of upper (or lower)
semi-lattice! Which brings to the point you raised early:

<quote>

Quote:

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>

The lattice join is trivially expressed via relational algebra join
(and we don't even have to bother with rather easy problem of
expressing inner union is in terms of classic RA).

Unfortunately, I understand Jan's comment differently. An isomorphism
is an equivalence relation. How do we know it is not "too coarse"? But
this is rather fuzzy idea, unless Jan points out to alternative
"finer" definition:-)

#**110**

On Jan 9, 3:53 pm, Tegiri Nenashi <TegiriNena... (AT) gmail (DOT) com> wrote:

Quote:

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

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

A = A /\ B
imply
f(A) = f(A /\ B)
which implies
f(A) = f(A) /\ f(B)
which in turn imply
f(A) <= f(B)

AFAIR in lattice theory an order isomorphism is the same as
isomorphism defined in terms of operations /\ and \/.

Yes. A lattice isomorphism defined in terms of ^ and v is
equivalent to one defined in terms of <=. There are two
different kinds of homomorphism, though: meet-homomorphism
and join-homomorphism.

Marshall