Re: database design method

From: Jan Hidders <>
Date: 11 Nov 2002 23:48:47 +0100
Message-ID: <3dd033cf$>

Lauri Pietarinen wrote:
>> >OK, I get the picture. But to me it looks like you are trying to
>> >undermind the original power of the RM by somehow introducing new kinds
>> >of data dependencies, i.e. entities not identified by value but by
>> >"position".
>> No, in fact, that is exactly the problem. If the nodes or subtrees are
>> identified by position then I could easily model it in the flat
>> relational model. But in the examples I gave they are true values and
>> identified by their components.
>They are - in your approach - in fact identified by their parents

Have you been reading my PhD thesis? But seriously, they are not. Two trees are the same if they have the same attributes and set of children, just like two tupels are the same if they have the same attributes. Period. The parent doesn't come into that.

>I think that kind of modeling of trees is a disaster. How do you
>search for nodes that - say - have the value 'x' in some attribute.

By using recursion:

Let's say the type is defined by

  TYPE Tree = TUPLE { Name : STRING,

                      Attr : STRING,
                      Subtrees : RELATION { Tree } }

and we have a relation Trees : RELATION { Tree }

Then you can do (I hope you will forgive me if I use the conventional nested relational algebra):

R1 := Trees UNION (UNNEST[Subtrees](PROJECT[Subtrees](R1)))
R2 := PROJECT[Name,Attr](R1)
R3 := SELECT[Attr="Lauri"](R2)

>Do you need a do-while loop for that??


>What's wrong with the 'traditional' way, say [...]

You are inventing a nodeID that was not in the original data model of the user. Don't forget that we are talking about a *logical* data model here. There's nothing wrong with using surrogate identifiers but that is an implementation issue and the user shouldn't have to be aware of that.

>This requires recursive support (available
>in DB2, and partly Oracle)
>(Needless to say: Dataphor has it)

Good. So everything we need is already there.

>Or, you can take a look at
>"On Accelerating XPath Evaluation in Any RDBMS"

I know that research very well. (It's from the university where I studied.) In fact, part of my current research is about showing how simple relational algebra is enough to implement almost the whole of XPath, axes, filters and all. That shows that even something as complicated and messy as XML (= eXtremely Messy Language) can be effectively tackled by the simple relational model.

>But I want to use my RELATIONAL OPERATORS!!

You can. But I don't think you should be using algebra operators for that but a more declarative type of language. I assume Dataphor has that?

>I don't want to use any stupid loops!

You don't even have to use smart loops. :-)

>They are hard to write and the optimizer won't understand them anyway.

It should be able to deal with recursion. A lot of research has been done in that area, but at the moment very little of that has found its way into real DBMSs. Btw., while-loops can often be simulated with recursion (depends upon the type of recursion that is allowed and what its semantics is) so a good query optimizer should also be able to deal with that kind of construct.

  • Jan Hidders
Received on Mon Nov 11 2002 - 23:48:47 CET

Original text of this message