[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: hierarchical XML in a relational DB structure - moving nod

• To: "xml-dev" <xml-dev@l...>
• Subject: Re: hierarchical XML in a relational DB structure - moving nodes
• From: "Ken North" <kennorth@s...>
• Date: Mon, 29 May 2006 10:56:01 -0700
• References: <07D2490E9E33124B8ED67F01E828B9E701341A6A@R...>

"Michael Rys" <mrys@m...> wrote
>> There is a paper by Shankar Pal and the O'Neils on ORDPATH in SIGMOD
2004 (I think or was it VLDB 2004) that shows you a way to represent
hierarchy using a special binary key that abstracts a variance of the
Dewey Decimal categorization system. If you are willing to manage these
keys yourself, that may be an option, another option is the approach
taken by T. Grust's team which basically uses range keys.

Other interesting approaches:

1. An Efficient XML Node Identification and Indexing Scheme (Jan-Marco Bremer,
Michael Gertz). Introduces path IDs (PID). They number nodes with a
memory-resident Extended DataGuide and encode the complete data path as a PID.

2. The BIRD Numbering Scheme for XML and Tree Databases -- Deciding and
Reconstructing Tree Relations using Efficient Arithmetic Operations (Felix
Weigel, Klaus U. Schulz,  Holger Meuss). This paper discusses number-based
schemes, path-based schemes and comparative performance of several approaches
(ORDPATH, BIRD, PID, Virtual Nodes). In the authors' tests, BIRD and PID
delivered better performance than ORDPATH and Virtual Nodes.


======== Ken North ===========
www.WebServicesSummit.com
www.SQLSummit.com
www.GridSummit.com


----- Original Message ----- 
From: "Michael Rys" <mrys@m...>
To: "Michael Kay" <mike@s...>; "Robert Koberg" <rob@k...>;
"xml-dev" <xml-dev@l...>
Sent: Friday, May 26, 2006 2:20 PM
Subject: RE:  hierarchical XML in a relational DB structure - moving
nodes



There are ways on how to do it in a relational database, but today the
best way to do it in a relational database is using one of the following
approaches:


1. Need frequent, independent access to individual item and order in the
tree is not important:

Use primkey,foreignkey,properties... and use recursive SQL queries
(which are part of SQL-99) to get the set back. There are ways to map
them back into XML even.

2. Don't need frequent independent access at individual item level or
order in the tree is important:

Use an XML datatype (like Oracle, SQL Server or other databases
provide).

There is a paper by Shankar Pal and the O'Neils on ORDPATH in SIGMOD
2004 (I think or was it VLDB 2004) that shows you a way to represent
hierarchy using a special binary key that abstracts a variance of the
Dewey Decimal categorization system. If you are willing to manage these
keys yourself, that may be an option, another option is the approach
taken by T. Grust's team which basically uses range keys.

Best regards
Michael

> -----Original Message-----
> From: Michael Kay [mailto:mike@s...]
> Sent: Thursday, May 25, 2006 2:45 AM
> To: 'Robert Koberg'; 'xml-dev'
> Subject: RE:  hierarchical XML in a relational DB structure -
> moving nodes
>
> Relational databases are a horrible way of storing recursive data.
Apart
> from anything else, recursive queries cannot be done using first order
> predicate logic (i.e. SQL, without extensions). If you must do it, Joe
> Celko
> seems to have made a career out of telling people how to do it, but
it's
> no
> picnic. Better to choose a container that fits the shape of your data.
>
> Michael Kay
> http://www.saxonica.com/
>
> > -----Original Message-----
> > From: Robert Koberg [mailto:rob@k...]
> > Sent: 24 May 2006 20:53
> > To: xml-dev
> > Subject:  hierarchical XML in a relational DB
> > structure - moving nodes
> >
> > Hi,
> >
> > I want to use a relational database to store data that is
> > nested and where the order is preserved. I am having a hard
> > time wrapping my head around how to do the following mostly
> > because I don't have much experience with relational databases.
> >
> > I am looking at mapping a structure like so:
> >
> > <node id="1">
> >    <node id="11">
> >      <node id="111">
> >        <node id="1111"/>
> >        <node id="1112"/>
> >        <node id="1113"/>
> >      </node>
> >      <node id="112"/>
> >      <node id="113"/>
> >      <node id="114"/>
> >    </node>
> >    <node id="12">
> >      <node id="121"/>
> >      <node id="122"/>
> >      <node id="123"/>
> >    </node>
> > </node>
> >
> > To a relational database that might have a table representing it
like:
> >
> > Node
> > -------
> > id
> > parentId
> > parentIndexPosition
> >
> > First question: Is using an index position the best way to
> > maintain the position? (or is preceding and/or following
> > sibling better? or something
> > else?)
> >
> > OK, lets say I have imported some data/XML into the above
> > table, giving appropriate parents and index positions.
> >
> > Next, say I want to move /node/node[2]/node[@id=121] to the
> > position /node/node[1]/node[1].
> >
> > How do you handle updating the index position of other nodes?
> > All children of /node/node[@id=12] will need their
> > parentIndexPosition moved down one. And all children of
> > /node/node[@id=11] will need their parentIndexPosition moved
> > up one. (the ID attributes where abritrarily created and
> > should not indicate position)
> >
> > Is there a built in mechanism to do this type of thing in
> > relational databases? If not how would an UPDATE look?
> >
> > Are there any java libraries or articles out there that
> > handle this type of thing? (I am having a hard time finding
> > anything with google)
> >
> > thanks,
> > -Rob
> >
> >
> > -----------------------------------------------------------------
> > The xml-dev list is sponsored by XML.org
> > <http://www.xml.org>, an initiative of OASIS
> > <http://www.oasis-open.org>
> >
> > The list archives are at http://lists.xml.org/archives/xml-dev/
> >
> > To subscribe or unsubscribe from this list use the subscription
> > manager: <http://www.oasis-open.org/mlmanage/index.php>
> >
>
>
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
>
> The list archives are at http://lists.xml.org/archives/xml-dev/
>
> To subscribe or unsubscribe from this list use the subscription
> manager: <http://www.oasis-open.org/mlmanage/index.php>


-----------------------------------------------------------------
The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
initiative of OASIS <http://www.oasis-open.org>

The list archives are at http://lists.xml.org/archives/xml-dev/

To subscribe or unsubscribe from this list use the subscription
manager: <http://www.oasis-open.org/mlmanage/index.php>

• References:
  • RE: hierarchical XML in a relational DB structure - moving nodes
    • From: "Michael Rys" <mrys@m...>

• Prev by Date: Re: Re: [ubl-dev] UBL 2.0 and Schema Extensibility
• Next by Date: Re: Still banging on about extensibility and validation
• Previous by thread: RE: hierarchical XML in a relational DB structure - moving nodes
• Next by thread: RE: hierarchical XML in a relational DB structure - moving nodes
• Index(es):
  • Date
  • Thread