Re: What is an automorphism of a database instance?

From: Kira Yamato <kirakun_at_earthlink.net>
Date: Wed, 9 Jan 2008 18:29:06 -0500
Message-ID: <2008010918290616807-kirakun_at_earthlinknet>

On 2008-01-09 16:15:46 -0500, Jan Hidders <hidders_at_gmail.com> said:

> On 9 jan, 20:57, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:

>> On Jan 9, 11:13 am, Jan Hidders <hidd..._at_gmail.com> wrote:
>>
>>
>>

>>> On 9 jan, 19:10, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:

>>

>>>> On Jan 9, 12:29 am, Kira Yamato <kira..._at_earthlink.net> wrote:

>>

>>>>> On 2008-01-08 09:45:19 -0500, Jan Hidders <hidd..._at_gmail.com> said:

>>

>>>>>> On 28 dec 2007, 06:15, Kira Yamato <kira..._at_earthlink.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.

>>

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

>>

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

Received on Thu Jan 10 2008 - 00:29:06 CET