I'm sorry; I meant the word "record" in the sense in which it is used in Xindice's paged file class. I propose to maintain the idea of one disk file for each collection.
In this file, it is true that the actual page containing the data could be anywhere for all the various nodes. But this is the case even now, as the byte array representing the "compressed DOM" of an XML document could be several pages long and thus located at several very different locations in the file. ----- Original Message ----- From: "Matt Liotta" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Tuesday, December 24, 2002 1:34 AM Subject: RE: core development > If you store every node as its own record then you will have spatial > issues reconstructing documents as there is no guarantee that all the > nodes for any particular document will be located in the same area of a > disk. > > If you do in fact want to store each node separately, you will need to > create some sort of container for all the nodes in a document, so that > the disk can access the container as one logical data structure. > > Matt Liotta > President & CEO > Montara Software, Inc. > http://www.montarasoftware.com/ > 888-408-0900 x901 > > > -----Original Message----- > > From: James Bates [mailto:[EMAIL PROTECTED] > > Sent: Monday, December 23, 2002 6:44 PM > > To: [EMAIL PROTECTED] > > Subject: core development > > > > Here's the stuff I think we could get started with in the core > development > > field: > > > > 1) storage: > > ======= > > Currently XML is stored by "compressing it", which in fact involves > > flattening the tree into a byte-array, and replacing > > all element and attribute names with pointers into a symbol table, and > > then > > storing the byte array as one data record ("page" or > > linked list of pages), indexed by its name in the collection paged > file > > using a B-Tree. > > > > This makes for poor scalability, and it also is not particularly > > interesting > > for optimizing queries. I'd like to propose the following storage > scheme: > > > > We could leave the tree structure of the XML as is. We could then > store > > every node in its OWN data record in a "Paged file", and have elements > > POINT > > to their children (i.e. they'd contain the page numbers of the records > > containing their child nodes + the actual attributes for example: not > all > > that much point in storing attributes separately, although this too is > > debatable...). We can maintain the symbol table no problem. In fact we > > could > > improve it by adding pointers to each element node or attribute that > has a > > symbol table entry as name, allowing fast execution of " / / myelement > " > > type XPaths. > > > > The main goal here is to allow for large documents. If nodes are > stored > > separately, they need not all be read in to memory all the time. The > > Xindice > > DOM implementation would only load what it needs. > > > > We can maintain the B-Tree in the same data file for locating the root > > nodes > > of documents, based on names. > > > > Indexes could also benefit: instead of pointing to the complete > document > > that satisfies an XPath, they could point to the actual node that is > the > > result of the XPath. In this manner, XPath searches in a single large > XML > > document could also benefit from indexes. > > > > Same story for updates: selects can resolved as XPath queries (such is > the > > case already!), and then only the required node(s) need be updated. > > > > 2) failure recovery: > > ============ > > This is a necessary prerequisite for transaction support. > > > > For this, it is necessary to maintain a log of all updates to the > > database. > > This log can be "checkpointed" at various times, and these > > checkpoints can be used by a (still-to-be-written) recovery engine > that > > can > > "rollback" to the last checkpoint. This way, consistensy can be > > guaragnteed > > for instance. > > > > There are a few good failure recovery algorithms to be found in any > > database > > theory book. The issue is always chosing the "data unit": how granular > > should the log be? This depends essentially on how fine updates occur. > > Using > > the storage scheme above, this would be "nodes", which are in fact > stored > > as > > records in a paged file. Chosing records in a paged file as log unit > gives > > the advantage of protecting not only the XML trees, but also the > B-Tree > > containing the document names. > > > > > > This groundwork done, we can start thinking about query optimzing and > > transaction support. > > > > It's one scheme, but I'm pretty sure it should work. It should at the > very > > least be fun to have a go at ;) > > > > All other views are abviously welcome. > > > > James > >
