Menu
▾
▴
springframework-developer
|
From: Cameron B. <ca...@da...> - 2004-04-05 16:57:13
|
I am implementing a system that needs to store a fair bit of hierarchical data. For previous apps that have had this requirement, I stored the hierarchy in relational databases, which worked sufficiently well. BUT, this new application has a lot of operations that deal with deep and wide directed trees (I don't know if that is the correct name for them, but I am sure you get the picture). This would require a LOT of trips to the database to fetch the children each time a transaction runs. I could try and implement this using some complex caches but I though I would see if anyone else has an alternate solution. It will need to be able to participate in a distributed transaction, since some data will be stored in a relational database, and some in the hierarchy store. I have thought of products like * Prevayler http://www.prevayler.org <http://www.prevayler.org/> * seems a little amateur from the wiki * seems to support transactions * needs to keep all data in memory - which probably won't work for this site * doesn't seem to support JTA * Berkeley DB Java Edition - http://www.sleepycat.com/products/je.shtml * Supports transactions * doesn't seem to support JTA * may be too low level * JDBM http://jdbm.sourceforge.net/ * Simple transactional persistent hash map implementation Does anyone have any suggestions on other 'preferably' open source products, or techniques to achieve wish to do. I am also very new to XA and distributed transactions, so if anyone has any hints on using XA with spring please show me where I can find some resources. Also - it is possible to implement XA support for systems like jdbm, prevayler or Berkley db ? Cameron. |
|
From: Eduardo I. I. <zi...@su...> - 2004-04-05 18:12:10
|
You can try using LDAP, it is well suited for hierarchical data, but it is not efficient when doing updates. Another alternative would be an XML database like dbXML or Xindice. It's much easier doing an XPath query than traversing a complex object hierarchy. Cameron Braid wrote: > I am implementing a system that needs to store a fair bit of > hierarchical data. > > > > For previous apps that have had this requirement, I stored the hierarchy > in relational databases, which worked sufficiently well. > > > > BUT, this new application has a lot of operations that deal with deep > and wide directed trees (I don’t know if that is the correct name for > them, but I am sure you get the picture). > > > > This would require a LOT of trips to the database to fetch the children > each time a transaction runs. > > > > I could try and implement this using some complex caches but I though I > would see if anyone else has an alternate solution. > > > > It will need to be able to participate in a distributed transaction, > since some data will be stored in a relational database, and some in the > hierarchy store. > > > > I have thought of products like > > > > * Prevayler http://www.prevayler.org <http://www.prevayler.org/> > o seems a little amateur from the wiki > o seems to support transactions > o needs to keep all data in memory – which probably won’t work > for this site > o doesn’t seem to support JTA > * Berkeley DB Java Edition - http://www.sleepycat.com/products/je.shtml > o Supports transactions > o doesn’t seem to support JTA > o may be too low level > * JDBM http://jdbm.sourceforge.net/ > o Simple transactional persistent hash map implementation > > > > Does anyone have any suggestions on other ‘preferably’ open source > products, or techniques to achieve wish to do. > > > > I am also very new to XA and distributed transactions, so if anyone has > any hints on using XA with spring please show me where I can find some > resources. > > > > Also - it is possible to implement XA support for systems like jdbm, > prevayler or Berkley db ? > > > > Cameron. > |
|
From: Colin S. <col...@ex...> - 2004-04-05 18:29:01
|
Of course LDAP is not transactional (unless wrapped with some sort of=20 transactional wrapper, which I've never seen)... Eduardo Issao Ito wrote: > > You can try using LDAP, it is well suited for hierarchical data, but=20 > it is not efficient when doing updates. > > Another alternative would be an XML database like dbXML or Xindice.=20 > It's much easier doing an XPath query than traversing a complex object=20 > hierarchy. > > > Cameron Braid wrote: > >> I am implementing a system that needs to store a fair bit of=20 >> hierarchical data. >> >> =20 >> >> For previous apps that have had this requirement, I stored the=20 >> hierarchy in relational databases, which worked sufficiently well. >> >> =20 >> >> BUT, this new application has a lot of operations that deal with deep=20 >> and wide directed trees (I don=92t know if that is the correct name fo= r=20 >> them, but I am sure you get the picture). >> >> =20 >> >> This would require a LOT of trips to the database to fetch the=20 >> children each time a transaction runs. >> >> =20 >> >> I could try and implement this using some complex caches but I though=20 >> I would see if anyone else has an alternate solution. >> >> =20 >> >> It will need to be able to participate in a distributed transaction,=20 >> since some data will be stored in a relational database, and some in=20 >> the hierarchy store. >> >> =20 >> >> I have thought of products like >> >> =20 >> >> * Prevayler http://www.prevayler.org <http://www.prevayler.org/> >> o seems a little amateur from the wiki >> o seems to support transactions >> o needs to keep all data in memory =96 which probably won=92= t work >> for this site >> o doesn=92t seem to support JTA >> * Berkeley DB Java Edition -=20 >> http://www.sleepycat.com/products/je.shtml >> o Supports transactions >> o doesn=92t seem to support JTA >> o may be too low level >> * JDBM http://jdbm.sourceforge.net/ >> o Simple transactional persistent hash map implementation >> >> =20 >> >> Does anyone have any suggestions on other =91preferably=92 open source= =20 >> products, or techniques to achieve wish to do. >> >> =20 >> >> I am also very new to XA and distributed transactions, so if anyone=20 >> has any hints on using XA with spring please show me where I can find=20 >> some resources. >> >> =20 >> >> Also - it is possible to implement XA support for systems like jdbm,=20 >> prevayler or Berkley db ? > |
|
From: James C. <jim...@do...> - 2004-04-05 18:12:15
|
Joe Celko's "SQL for Smarties" book introduced me to a "Nested Set Model of Trees in SQL". He has a couple typos in his stored procedures, but he effectively laid out how to store a tree structure in a relational database allowing for fast querying regardless of the hierarchy depth. Really cool stuff and it worked pretty well in practice. It is optimized for reading, not writing. It is basically a left-right tree stored with each node stored as a row in the table. The table is defined as: OBJ_ID INT, OBJ_NAME VARCHAR(50), LFT INT, RGT INT The Left and Right values are renumbered as each item is inserted into the tree. Here is an example of the Skywalker family tree would look like with each person added incrementally. Root object inserted: OBJ_ID OBJ_NAME LFT RGT ------ -------------------- --- --- 1001 SHMI SKYWALKER 1 2 Child inserted: OBJ_ID OBJ_NAME LFT RGT ------ -------------------- --- --- 1001 SHMI SKYWALKER 1 4 1002 ANAKIN SKYWALKER 2 3 Grandchild of root OBJ_ID OBJ_NAME LFT RGT ------ -------------------- --- --- 1001 SHMI SKYWALKER 1 6 1002 ANAKIN SKYWALKER 2 5 1003 LUKE SKYWALKER 3 4 Sibling of grandchild OBJ_ID OBJ_NAME LFT RGT ------ -------------------- --- --- 1001 SHMI SKYWALKER 1 8 1002 ANAKIN SKYWALKER 2 7 1003 LUKE SKYWALKER 3 4 1004 LEIA ORGANA 5 6 You can then execute some crazy-fast queries using LFT and RGT values to determine the relationship between nodes: Descendent of current node: ...where LFT between (CURNODE).LFT and (CURNODE).RGT All ancestors of current node: ...where CURNODE.LFT between LFT and RGT All leaf nodes: ...where RGT - LFT = 1 Etc. As you can see, it is optimized for reads. Inserts require updates to nearly every O/2 rows on average. There may be ways of picking the left and right values to minimize the cost of insert. We thought of allowing a gap of more than one between the numbers, kinda like allowing a block of children. But in the end, I opted for an in-memory representation of our entire hierarchy. Although our objects are still persisted, I recreate the hierarchy when the app starts up. -- jim _____ From: spr...@li... [mailto:spr...@li...] On Behalf Of Cameron Braid Sent: Monday, April 05, 2004 12:56 PM To: spr...@li... Subject: [Springframework-developer] OT : Anyone know of a solution for storing (and retrieving) hierarchical data efficiently? I am implementing a system that needs to store a fair bit of hierarchical data. For previous apps that have had this requirement, I stored the hierarchy in relational databases, which worked sufficiently well. BUT, this new application has a lot of operations that deal with deep and wide directed trees (I don't know if that is the correct name for them, but I am sure you get the picture). This would require a LOT of trips to the database to fetch the children each time a transaction runs. I could try and implement this using some complex caches but I though I would see if anyone else has an alternate solution. It will need to be able to participate in a distributed transaction, since some data will be stored in a relational database, and some in the hierarchy store. I have thought of products like * Prevayler http://www.prevayler.org <http://www.prevayler.org/> * seems a little amateur from the wiki * seems to support transactions * needs to keep all data in memory - which probably won't work for this site * doesn't seem to support JTA * Berkeley DB Java Edition - http://www.sleepycat.com/products/je.shtml * Supports transactions * doesn't seem to support JTA * may be too low level * JDBM http://jdbm.sourceforge.net/ * Simple transactional persistent hash map implementation Does anyone have any suggestions on other 'preferably' open source products, or techniques to achieve wish to do. I am also very new to XA and distributed transactions, so if anyone has any hints on using XA with spring please show me where I can find some resources. Also - it is possible to implement XA support for systems like jdbm, prevayler or Berkley db ? Cameron. |
