473,322 Members | 1,781 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

a position on Treestructure in SQL and request for comments on same

I checked out the

http://c2.com/cgi/wiki?TreeInSql

link and found the following:

Motivation

There are many applications where data is structured as trees. This data
needs to be stored in a database. This data needs to be searched
efficiently. A join operation (set intersection) needs to be efficient.

Forces

a.. Loading an entire tree into memory before searching is not scalable.
b.. Relational tables are two dimensional, so trees must be expressed
using relational linkage.
c.. Fast searching at the database relies on early subsetting against some
index.
(end quote)

This whole "store tree nodes as individual records in an RDBMS" sounds
doomed to irrelevance in the near future because:

1) Loading an entire file into memory wasn't scalable, but it's sure looking
that way now, and specific file <--> string idioms in Python and the
availability of scads of cheap RAM encourage it more with each passing year.
Analogously, maintaining an entire pointery data structure in memory and
dispensing with access through RDBMS key blocks in favor of simple pointer
traversal is cheaper and cheaper as time goes by. Large (64-bit offset)
files and 64-bit OSes are waiting in the wings, too.

2) Virtual memory will also help you in your efforts to cram ever larger
data structures into memory. If you want to persist them easily, they could
be implemented in memory-mapped files with lazy read semantics (i.e. file
portions are only retrieved from disk on demand).

3) Perhaps a felicitous partition of functionality would be appropriate,
such as in-memory tree data structures with leaf node data storage delegated
to an RDBMS or hash table on disk.

I feel a little like a devil's advocate here, because in the past I have
also advocated shoehorning tree-structured stuff into an ISAM file, similar
to the tree-to-RDBMS idea posted here earlier, and, like a good code monkey,
I was excited about doing it. But it seems now that the technological
drivers are rendering this approach outmoded.

Although there are limitations of having stuff in-memory (like, how do you
provide scalable access to it from other processors and checkpoint it to
disk), it's interesting to note that your average RDBMS has already adopted
the approach outlined in 3): key blocks tend to get cached in memory anyway,
since they're on the critical path to the data block leaf nodes, which can
also get cached too. Whoops! Sounds like your RDBMS is already a mugwump
sort of tree, with it's mug in-memory and it's wump on disk. So it sound's
like there is really a continuum of mug/wump distribution, and that the wump
would wither away were it not necessary for persisting data structures.

Comments, please: am I missing anything important here?

Jul 18 '05 #1
1 1405
John Benson:
Although there are limitations of having stuff in-memory (like, how do you
provide scalable access to it from other processors and checkpoint it to
disk), it's interesting to note that your average RDBMS has already adopted
the approach outlined in 3):


And Prevayler has adopted 1 and 2:
http://www.prevayler.org/

--
René Pijlman
Jul 18 '05 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: Thomas Weholt | last post by:
Hi, I need to define tree-like structure for content categories in a simple CMS project. I got a table in a SQLite database which looks like this : CREATE TABLE category ( CAT_ID INTEGER...
5
by: Alexandre | last post by:
Hi, Im a newb to dev and python... my first sefl assigned mission was to read a pickled file containing a list with DB like data and convert this to MySQL... So i wrote my first module which...
3
by: David Hayes | last post by:
I've made tooltips work in Firefox*, but tooltip doesn't appear at the specified location until the SECOND time that the user passes the mouse over the location with the mouseover event. What I...
18
by: Chris Travers | last post by:
Hi all; I have been looking into how to ensure that synchronous replication, etc. could best be implimented. To date, I see only two options: incorporate the replication code into the database...
4
by: clintonG | last post by:
I'm using the intrinsic Request object wrong and need some help with this one. I wrote a class file for some XMLTextWriter tasks and in the class file I want to use a conditional to determine if...
6
by: Ammar | last post by:
Dear All, I'm facing a small problem. I have a portal web site, that contains articles, for each article, the end user can send a comment about the article. The problem is: I the comment length...
7
by: BootNic | last post by:
On Sat, 09 Aug 2008 22:55:52 -0400 sheldonlg <sheldonlgwrote in: <AvSdnSFsRJWNxAPVnZ2dnUVZ_u6dnZ2d@giganews.com> Perhaps you can give me some suggestions. Emulate position fixed example. ...
5
by: Henry Stock | last post by:
I am trying to understand the following error: Any thing you can tell me about this is appreciated. Security Exception Description: The application attempted to perform an operation not allowed...
12
Frinavale
by: Frinavale | last post by:
I think I'm trying to do something impossible. I have a <div> element with a overflow style set to "scroll". In other words my <div> element allows the user to scroll the content within it. ...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.