Re: Indexing solution for native XML database
Michael Rys wrote: > I know of at least one that was doing ok: B-Bop. They got bought out when they were not > growing as fast as their VCs where hoping... Some 6 years ago, I was working at B-Bop, when the founders decided we must implement an xml database on top of COTS RDBMS, I told them that it had been tried before with SGML, and the cost of self-joins would be too high. Nevertheless, they insisted. We devised a technique of encoding name and positional context in "tumbler" strings that allowed us to get around the self join performance hit, and leverage the RDBMS's indexes. I'll try to give a simplified description, here: Most of the interesting information was in two tables: XMLNames: nameID int name varchar LeafNodes: docID int nodeID int positionPath varchar namePath varchar reverseNamePath varchar charValue varchar positionPath, namePath and reverseNamePath are the "tumbler" strings. They represent a sequence of numbers as the concatenation of fixed length strings. For instance, if I want to indicate that a node is the third child of the fourth child of the document element, I might represent that as the sequence 0, 4, 3, or in the "tumbler" notation in positionPath as "_0._4._3". Attributes are always assigned the sequence number "0". Likewise, we can assign all XML names in the database to numbers, and encode the names of ancestor elements. Given an XML document: <foo><bar> something <baz blort='yadda'> new </baz></bar></foo> The tables would look like: XML Names nameID name ------ ----- 0 #PCDATA 1 foo 2 bar 3 baz 4 blort LeafNodes docID nodeID positionPath namePath reverseNamePath charValue ----- ----- ------------ ---------- --------------- ---------- 1 1 _0._1._1 _1._2._0 _0._2._1 ' something ' 1 2 _0._1._2._0 _1._2._3._4 _4._3._2._1 'yadda' 1 3 _0._1._2._1 _1._2._3._0 _0._3._2._1 ' new ' This lets us use the RDBMS's indexing facilities to quickly retrieve branches of documents with a given ancestry. /foo/bar//node() --> select * from LeafNodes where namePath like '_1._2%' order by positionPath Finding all values of the attribute 'blort' in a 'baz' element would be: //baz/@blort --> select * from LeafNodes where reverseNamePath like '_4._3%' The resulting rows from these queries contain enough information to allow some procedural code to fire off a sequence of SAX start/end element events or build further queries to bring back related portions of the trees. While many queries had O(log n) performance, space usage was high, inserts were expensive and updates generally meant removing and re-inserting the entire document. -- Bill Lindsey http://www.blnz.com
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format