Re: database design method

From: Jan Hidders <>
Date: 13 Nov 2002 16:39:05 +0100
Message-ID: <3dd27219$>

In article <>, Lauri Pietarinen <> wrote:
>> >With user defined types, one can define whatever type one wants.
>> That depends upon what the minimal requirements are for defining it. If I
>> have to define a function that outputs the representation of the value then
>> there is a problem. It also depends on how exactly you can denote or create
>> new values. As long as these things are not exactly specified it is not
>> clear if you can use abstract identifiers or not.
>Is there a theoretical problem with just using plain
>integers as surrogates or "object id's"? Or is it just that we
>want to prevent the user from comparing apples and oranges?

No, there is a deeper problem here. Suppose you use numbers to represent the nodes of a nested value like a tree. Normally in a query in a model with explicit nested values you can ask a query that transforms the given nested values into another nested value, e.g., it transforms the trees into other trees. If you want to do that in your surrogate-identifier simulation you have to generate new identifiers in your query. There are theoretical results that prove that whatever computation on numbers you use you cannot simulate every query that you could do with explicit nested values.

However, these results also apply to abstract identifiers if you only have a new_id() constructor and only flat relations. But it is also known that you can remedy this by either allowing 1 level of nesting (no more is needed) or introduce a special algebra operator that creates new abstract identifiers for each of the sets defined by a (flat) binary relation.

Sorry that this is so abstract, but it takes a lot of time to explain this properly. If you want to know more:  

  Jan Van den Bussche, Dirk Van Gucht, Marc Andries, and Marc Gyssens. On   the completeness of object-creating query languages (extended abstract). In   33rd Annual Symposium on Foundations of Computer Science, pages 372-379,   Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

Btw., they use the term "object-oriented" a lot in their paper, but if you look closely you will see that what they are talking about is in fact the (flat) relational model extended with object identifiers.

  • Jan Hidders
Received on Wed Nov 13 2002 - 16:39:05 CET

Original text of this message