CN103493043A - A hybrid binary xml storage model for efficient xml processing - Google Patents

Abstract

A method for storing XML documents a hybrid navigation/streaming format is provided to allow efficient storage and processing of queries on the XML data that provides the benefits of both navigation and streaming and ameliorates the disadvantages of each. Each XML document to be stored is independently analyzed to determine a combination of navigable and streamable storage format that optimizes the processing of the data for anticipated access patterns.

Description

The mixing binary XML memory model of processing for effective XML

Technical field

The present invention relates to storing X ML document to retrieve and navigation for effective.

Background technology

XML

Extend markup language (XML) is w3c (W3C) standard for meaning data.Many application are designed to export the data of XML document form.Can utilize various technology so that data are stored into relevant database from this XML document.

The XML packet is containing the structural data item that forms level.In XML, the data item that is called key element is delimited by starting label and end-tag.Key element also can be included in the attribute of stipulating in the beginning label of key element.Text between the label of key element can mean the data value such as any type of string, date or integer.Key element can have one or more child.With for discuss family tree aspect similar aspect the hierarchy obtained of XML formatted data is discussed.For example, can say that child's key element gets off from its father's key element or any key element of getting off from its father.Can say that father's key element is any child's key element of self or the ancestors' key element of in its offspring's key element.Key element is collectively referred to as tree or subtree together with its attribute and offspring.Node with father/child's relation is called as and has middle hierarchical relational, and reason is can have direct guidance path between them.

The XML data can be stored in relevant database by using the storage of object relationship type or binary XML BLOB storage or CLOB storage, and reason is these databases service datas very effectively.But, although can from father to child along object search relationship type storage or the binary XML storage effectively downwards of XML level,, these storage organizations are unsuitable for execution requirements and upwards travel through the hierarchical navigation of ancestors' link or compatriot's traversal along level.

Storage and inquiry system for XML

Use various types of storing mechanisms with storing X ML document.Can, by document being chopped into to each single key element and storing key element in each single row of form, XML document be stored in relevant database.In database server, XML document can be stored in the row of table, and, the node of storing X ML document in the independent row in can being expert at.

As an alternative, whole XML document can be used as large object (LOB) and is stored in the row of database table.But the large object of character (CLOB) that large object row store storage is text, or also can be stored as binary large object (BLOB).Binary object can comprise the token crossfire of XML data.This crossfire of the token for XML document alternatively is stored in volatile memory.

XML inquiry and XPATH

For the Database Systems of storing X ML data, can be very important by using the XML query language to carry out inquiry.XML query language (XQuery) and XML path language (XPath) are the major criterions of query language, and they can be combined with to express with SQL various useful inquiries.The XML Path Language(XPath that XPath here adds as a reference and can obtain when writing http://www.w3.org/TR/xpath), version1.0(W3C Recommendation16November1999) and here the XMP Path Language(XPath that adds as a reference and can obtain when writing http://www.w3.org/TR/xpath), 2.0(W3C Recommendation 23 January 2007), be described.The XQuery1.0:An XML Query Language(W3C Recommendation23January2007 that XQuery here adds as a reference and obtains when writing http://www.w3.org/TR/xquery) in, be described.And, have the XQuery script: http://www.w3.org/TR/xquery-sx-10/.

Path expression

Set up father-child's relation between the node of the structure of XML document in XML document.The a series of father of " path " of the node in XML document reflection from " root " node to specific node-child links.For example, in the example document shown in table 1, because " UnitPrice " be " Part " node child, " Part " node is the child of " LineItem " node and child and " LineItems " node that " LineItem " node is " LineItems " node are the children of " PurchaseOrder " node, therefore, the path to " UnitPrice " node is/PurchaseOrder/LineItems/LineItem/Part/UnitPrice.

The particular sections point assessment path expression that is called " linguistic context " about the starting point as navigation.By using the navigation of approach axes (". ", "/", " // " and " .. ") regulation.Each in these axles is selected one or more node, and then these nodes are further followed axle based on the test of what title or node test and be filtered.

Table 1: example purchase order document

The subset of XPath axle and title/node test comprises:

/	Child's axle
		//	Offspring's axle
.	Current axis
		..	Father's axle

*	The test of asterisk wildcard title

Syntax used herein is standard x Path syntax.But, should be appreciated that and can use any syntax that there is suitable semanteme with above axle.

Descend and be called as positive navigation from father to child in tree.Upwards rise and be called as reverse navigation along level from child to father.Another example of reverse navigation is the last compatriot of access.The path started with virgule ("/") starts evaluated at the root node place of level.

Navigation XML data

The action that the support of XPath/Query language can be carried out in the tree.But, store the efficient navigation that above-mentioned XML data and index data can not provide the tree traversal.In order to overcome this problem, can create DOM Document Object Model (DOM) in storer, and, can on DOM, carry out navigation action.A problem of the method is, even only need the several nodes in whole tree to express with assessment, before can carrying out the tree traversal, also must in storer, build whole dom tree.For large document, this expresses aspect needed amount of memory the problem that all has scalability at the time that builds tree and processing XPath.Build DOM in storer and may need 10 times of size of the XML document that means as the DOM spaces more than like that.Therefore, the document of 100MB may need the storer of gigabit to keep dom tree.

For fear of the problems referred to above that build DOM in volatile memory, can use other method with the navigation link of memory hierarchy for good and all together with the XML content.In other words, the XML data can be stored as tree on dish, make each node storage content and navigation link of level.Each node of level can comprise the link that random access is provided to other node in level.But this method may require to store alternately with the content of each node the navigation link of supporting access ancestors, compatriot and child.

Can effectively process larger document to set aligned storing X ML, here, each node in XML document is stored together with the pointer for its father, the first child and compatriot or one or more the combination in these pointers, reason be can be by following storage pointer directly along various XPath spindle guides boats and generally read and process the part of the much less of document.Because relevant pointer has been stored in dish above, therefore, create DOM also faster in storer.But, such memory requirement more for the treatment of storer and more for the disk space (causing thus higher I/O expense, particularly for less document) of storage.It also requires more storer and disposal cost in storing process.

Support each node in navigation request and the father who allows direct access node, the first child, the first compatriot and previous compatriot's document to store explicitly additional information.These pointers for other node allow effectively to process the pointer that uses ancestors' axle and express.But, because allowing the directly adjacent node of access, the pointer be associated with node with node, there is the node of direct layering relation, therefore, and need to be with any specific order memory node.By using the traversal of pointer XM, and the storage order of node is inessential.

Crossfire XML data

The permanent crossfire of XML document means it is the binary representation of XML document of the serial sequence to resolve the order storage token value that token is identical from document.Token value is the compact representation from the character order token of the text representation parsing of document.Here, be called as " document order " from the order of text document parsing token.The crossfire of storage that therefore, can be by reading document means to come the crossfire XML document.

The scale-of-two crossfire that creates XML document means it is highly effective, and reason is only need in storer, keep the sub-fraction of document within any given time.And the scale-of-two crossfire is the file layout of saving the compactness of disk space.Together with document data, do not store navigation hands.For being evaluated at simple XPath on little document and XQery and reading the most action of document and, when not needing ancestors to navigate, the XML memory model of the crossfire of the event based on the SAX class is effective for needs (document) order successively.

Mode treatment is to process with the document order example of whole XML document.The application of mode treatment comprises that the test XML document is for the accordance of its pattern and to the Database Systems enrollment mode.For mode treatment, key element in pattern and the order occurred in XML document be important.The order of the key element in document must mate the order of stipulating them in pattern.For this application, but the crossfire binary representation is useful, and reason is the order of the node in its reserving document.

When document becomes large, by whole document, read in storer and the event that scans in crossfire can form obvious expense aspect I/O and CPU time.When the XML data are stored as the binary XML such as SAX crossfire sequence of tokens, for navigation forward, must read successively token, until find the node of hope.In document, do not exist in the situation that do not read and skip the random access that the offspring of all fronts navigates directly to child nodes.

The XPath expression that assessment need to be stored as the ancestors' navigation on the XML document of scale-of-two crossfire can be expensive especially.Because father in sequence and ancestors occurred before present node, therefore, find father or ancestor node need to from sequence start process.Find node born of the same parents to depend on the compatriot occurs in sequence before or after present node.Although can identify ancestors and compatriot by following by this way forward chaining,, may need a plurality of rounds by document.Crossfire XPath evaluation engine can travel through whole document when the assessment inquiry.If the input XML document is large document, the processing that travels through so whole document is the height poor efficiency, thereby forms the large subtree that the XPath in matching inquiry not expresses.

Need to make I/O expense and storer use minimized more effective memory mechanism and to the convergent-divergent of large-sized document and more complicated inquiry.

The method of describing in this part is the method that can imagine, but may not be the method for front conception or imagination.Therefore, unless otherwise instructed, otherwise, should be not only by be contained in the method that supposition is described in this part in this part any be prior art.

The accompanying drawing explanation

In the accompanying drawings as an example rather than restriction the present invention is shown, in these accompanying drawings, similarly Reference numeral refers to similar key element, wherein,

Fig. 1 means the diagram of content of the node of the storage of can navigating according to an embodiment of the invention.

But Fig. 2 means according to an embodiment of the invention to mix the diagram of can navigate/stream format storage example XML document.

But Fig. 3 is according to an embodiment of the invention for the process flow diagram of the step that creates can navigate/crossfire of mixing storage.

Fig. 4 means the snapshot of the state in the structure of navigated storage of the example XML document introduced in Fig. 2 according to an embodiment of the invention.

Fig. 5 means according to an embodiment of the invention from the example XML document as mixing the table 1 that storage format provides.

Fig. 6 is for realizing the block diagram of computer system of the present invention.

Embodiment

In the following description, for illustrative purposes, set forth a large amount of specific details can understand up hill and dale the present invention.But, obviously, can be in the situation that do not have these specific details to implement the present invention.In other example, for fear of unnecessarily obscuring the present invention, with the form of block diagram, mean known structure and device.

General summary

For comprising the XPath expression that assessment need to be navigated and the various uses of processing whole document or fragment with the document order, need the common store system with storage and retrieval XML data.But provide to provide, can navigate or crossfire is stored both advantages and made each the minimized mixing storage means of shortcoming.

Content Management System can be managed the set of large XML document.With any single leaf node, compare, respectively more high-level node (approaching most the node of root node) can be accessed more continually.But, but in the crossfire of document means, for a large amount of contents, be stored in the document in leaf node, more the node of high-level can away from.Therefore, streaming method can require to read the node of more content with the frequent access of finding document.Provide from father to child and the tree-model of the direct navigation of node born of the same parents can increase the efficiency that finds these nodes.But, in order to create tree-model, all the elements in all leaf nodes may must be loaded in storer.

Some rather than whole nodes of method described herein storing X ML document in the storage of can navigating.In addition, but some and may be that whole nodes is stored in the storage of independent crossfire.In this linguistic context, but independent not meaning need to divide the space that is used in the crossfire memory paragraph from the identical memory section for the storage of can navigating, and, but do not require the crossfire memory paragraph with can the section of navigation adjacency.But differently mean the node with the storage format storage of can navigating with the node with the storage of crossfire storage format.In document, exist the node of the frequent access of many staggered contents to be placed in therebetween can to navigate in storage, but and not frequently the node of the fragment of the node of access and/or travel all over subtree may be stored as crossfire and mean.But can point to and only be stored in the node that crossfire means from the pointer of the node in tree representation.The text data that is stored as the part of crossfire points in tree-model, to avoid the repeated storage of text.For the content that is not stored as crossfire, create for this purpose independent text filed.

The method also comprises for each individual node in document to be determined and should mean with which storage a kind of mode of node.In addition, but once can navigate and the combination of crossfire storage in the node of storage document, the method comprises how using storage to mean to be evaluated at according to the inquiry on one group of XML document of describing method storage here.

But mean navigation nodes

Fig. 1 is the diagram that the node of the storage 100 of can navigating is shown.In the node that means to navigate in launching Figure 110 in a plurality of nodes of storage 120 one 124.Some in the content of the node that illustrating to navigate stores.Each navigation link can be pointer.For example, the father in node 124 links 130 sensing nodes 121, thereby means that node 121 is father's nodes of node 124.Similarly, the first child of node 124 links 132 sensing nodes 126, thereby means the first child nodes of node 126 memory nodes 124.Next link 134 born of the same parents and last compatriot's link 136 are respectively to link with next born of the same parents link with last compatriot of node 124.In an embodiment, but with in the crossfire node or with independent text chunk at the storage outside storage content of text that can navigate.Key element title or content 138 are pointed to content of text 180.

To mean XML document in hybrid navigation/stream format

But Fig. 2 means to mix the diagram of the example XML document of can navigate/stream format storage.In the present example, node level 200 means the diagram of the node level of document.For illustrative purposes, but but crossfire node 220 means the node (actual binary representation may not occur by this way) of the example document of stream formats.But the crossfire node is shown in the serialization of the level meaned in node level 200 to be meaned, makes node by the document order.

But navigation nodes 210 only comprises some node A, B and C with the form storage of can navigating fully.But remaining node D, E and F only are stored with stream format.In addition, for some node that not exclusively can navigate, in the memory paragraph that can navigate, create dummy node.Node occupies the space of the adjacency in the memory paragraph that can navigate, and, but each address of node can be with respect to the beginning of navigation nodes section.But navigation nodes can all have identical size fully, and dummy node can all have identical size, but but dummy node occupies the space fewer than complete navigation nodes.For example, but the node at address x and z place, address is not complete navigation nodes (they are dummy node), owing to storing minimum information (not storing navigation hands) about these nodes.

For illustration purposes, but Fig. 2 in several information of each navigation nodes of conceptive expression storage, (although information may not be expressed as in the drawings, be expressed.For example, label " F ", " P ", " C " etc. may not have as illustratedly word for word to be stored in node)." F " but mean that the indication present node is the mark that has the complete node of navigation hands fully or only point to the dummy node of the Nodes in the crossfire storage.No matter when fully but the first child of navigation nodes not exclusively can navigate, and the dummy node that means this first child all is provided.Child subsequently need to not meaned by dummy node.The identifier of the key element that " Id " indication is meaned by node.Identifier can be the title shown in example, or it can be to occupy the space fewer than title and be stored in explicitly the token--identifier such as the outside of the node in symbol table with title.As an alternative, Id can be the pointer that enters the text chunk of the title that comprises key element.

But the remaining entry in navigation nodes is pointer.Pointer is used to find the data that are stored in the position of pointer indication.Pointer can be offset address, but such as the byte or the word that start skew from navigation nodes 210.Pointer can be any other indication of the position in absolute bit addresses or storage." P " means father's pointer.The root node A of document does not have father, and its father's pointer is empty (null).Node B and C are the children of node A, and, because node A is positioned at u place, address, therefore, their father's pointer comprises address u." C " means the first child pointers.B is the first child of A, and therefore, because Node B is stored in w place, address, so the child pointers of node A comprises address w.The first child of Node B and C is not stored in the storage of can navigating fully, therefore, for them, distributes dummy node (node D and F).The first child of Node B is node D, and its first child pointers is pointed to the dummy node at x place, address.Similarly, the first child of node C is node F, and its first child pointers is pointed to the dummy node at z place, address." S " is next pointer born of the same parents.But Node B is the only navigation nodes in this example, but but should navigation nodes there is the compatriot who also is stored in complete navigation nodes.Next of Node B pointed born of the same parents address y, reason is that its node C born of the same parents is stored in y place, address." PS " means last compatriot.The pointer last born of the same parents of node C, with reference to address w,, is stored its last Node B born of the same parents here.

But but the content of text of navigation nodes is not stored in navigation nodes.If but same node point also is stored in crossfire storage, but but navigation nodes can comprise the pointer for the beginning of the content of text of the node in crossfire storage or text chunk so.This makes does not need the repeated storage content of text.But but content pointers 231～235 illustrates each navigation nodes in the storage of sensing crossfire.In an embodiment, if node does not have content of text, but content pointers can be pointed to the beginning of the crossfire node meaned in this simple example so.When in node, having content of text, content pointers can directly be pointed to text, and does not point to the beginning of node.

Except comprising the binary representation according to the document node of document order, but but crossfire mean to comprise the pointer that enters the storage of can navigating for each crossfire node, but be stored as fully navigation nodes according to the next node of document order with identification.For example, although Fig. 2 do not illustrate,, but the crossfire of Node B mean to comprise for the address y(as in the storage of can navigating comprise node C) pointer, but it is next navigation nodes fully in the Node B back according to the document order.But, if there is not more navigation nodes in document, pointer can be empty so, or pointer can not be prescribed.(but Fig. 5 means to get back to the pointer the storage of can navigating from the crossfire storage).

In the embodiment shown in Figure 2, only by also with some node of the form storage of can navigating with the whole document of storage in stream format.In an alternative embodiment, but as storing substituting of whole document in meaning with crossfire, but can only in the crossfire storage, store some node.In an embodiment, but the node in only having that not being stored in to navigate and meaning be stored in during crossfire means.In an alternative embodiment, can pass through two kinds of form memory nodes (such as node A, B and the C in this example).Having at least one node self with the child of the form storage of can navigating also should be stored with the form that can navigate.Therefore, with the leaf node of level, compare, the top node of document level more may be stored with the form that can navigate.

But determine which node in XML document with can navigate form and stream format storage can depend on the queried access pattern that shares, by relative processing and the I/O speed of the hardware platform of the content of the document stored and top operation storage system.Therefore, but determine that on the basis of each document and on the basis of each system which document node will be can navigate and stream format be stored.A document may not can be stored in the mode identical with another document, even these two documents meet common structure.Similarly, be stored in a document on storage system may be not with from be stored in another storage system with different processing and I/O velocity characteristic on the identical mode of identical document be expressed.

Determine the node that will be stored in the storage of can navigating

For each node of the example document shown in table 1, determine whether to support navigation (expression of can navigating) but the form crossfire mean or both memory nodes.The characteristic of each node of document is evaluated, to determine whether memory node in the storage of can navigating.In an embodiment, take the size of each node of tree subtree that is root evaluated.Can for example, about node counts and size of contents (space, occupied), measure the size of subtree on the dish of the size of content.Node counts is to process the indication of the amount of the needed processing of subtree, and size of contents is to read the indication of the I/O cost of subtree from dish.

Table 2 means to be respectively used to take node counts and the subtree size of each subtree that node is root.Mean the quantity of the character of subtree by counting in the text representation of XML document, determine the subtree size.The quantity of the character of content changes to the next one from a purchase order.Therefore, content-based size determines where memory node means, can make different storages for the different node instance of the identical XPath identification in the purchase order by different and determine.

Determine each node also processing speed based on host platform and the I/O speed of where storing.Processing speed is how soon to process the indication of subtree.I/O speed be can be how soon from the indication of permanent storage reading out data.Therefore, node counts that can be based on subtree and will store the processing power of system of document and the I/O speed of size of contents and system is calculated well-formedness tolerance.When the value of well-formedness tolerance surpasses threshold value, system determines this node of storage in the storage of can navigating.

Exemplary well-formedness tolerance can be calculated as:

Well-formedness tolerance=node counts * processing speed+size of contents * I/O speed

Here, processing speed and I/O speed are that the computer system institute of the conversion of top execution from the text to the binary representation is specific.In an embodiment, the processing speed number is measured with 1,000,000 thousands of instruction per seconds (kMIPS).In example, for the treatment of the processing speed of document, be 10kMIPS.In an embodiment, measure I/O speed with megabyte per second MB/s.In example, the speed of I/O system is 300MB/s.Therefore, the well-formedness tolerance of the example Purchase Order node in the table 2 with node counts 21 and subtree size 535 being calculated is calculated as:

21*10+535*300＝160710

The purchase order that table 2 is explained by the subtree size

For illustration purposes, example document is selected as less.In actual system, can be quite large by the document of storage, and, can with kilobyte (kB) or even megabyte (MB) measure the subtree size.But, for its proper property measure to determine whether node should be stored in threshold value in the storage of can navigating can be by convergent-divergent suitably.For this example, threshold value manually is chosen as 85000.The well-formedness of each in the node in table 3 expression example document is measured and whether is surpassed user's threshold value based on well-formedness tolerance and determines which node is stored in the storage of can navigating.

Table 3 determines that the storage of each node means

All nodes that this processing is applied to the document shown in table 2 can cause selecting paths/PurchaseOrder and/node at PurchaseOrder/LineItems place, and in only having these nodes to be stored in can to navigate and storing.Therefore, for the amount of the storage that keeps navigation hands, for navigation, provide those nodes of minimum benefit to be minimized.

Determine the threshold value of well-formedness tolerance

Determine whether that memory node depends on the threshold value of foundation for the tolerance of the automatic calculating of access module, document node attribute and the system platform property calculation of its comparison based on expectation in the storage of can navigating fully.Select correct threshold value to can be used as exercise and leave the experience of system manager based on the keeper for.In other words, he can be tested and by revising threshold parameter and monitoring query performance adjusted.

But, can the build tool to be conducive to the intelligent selection of useful threshold value.For example, but automation tools analysis of history inquiry log to extract one group of XPath action, and assessed cost balance when the specific collected works (corpus) for document are carried out set.This instrument can be automatically lead to and from the frequency of the navigation action of this node and read and take the frequency of the subtree that this node is root for each document node assessment.By this information, can process and the I/O requirement for each node determination.Once require to be determined, just can compare they and system capability to determine optimal tradeoff.

But determine the node that will store in the crossfire storage

As mentioned above, in one embodiment, but store all document node in the crossfire storage.In another embodiment, but only have the node be not stored in the storage of can navigating to be stored as crossfire storage.In another embodiment, but independently and with this node whether be stored in the storage of can navigating independently for being contained in each node of assessment in crossfire storage with each other node, but in requiring each node at least to be stored in can to navigate storage or crossfire storage.

But can assess whether in the crossfire storage, comprise node by the similar mode of mode with for determining whether memory node description in the storage of can navigating.For example, can combine by the analysis of history operating load, and, if all the number percent of file retrievals, lower than certain threshold value, does not mean but have so node can be stored as crossfire.Can apply in the subtree level identical criterion, but to determine whether storing each individual node of document in the crossfire storage.The analysis of subtree level can consider to retrieve the frequency of complete subtree.But when not meeting the criterion of memory node in crossfire storage, from the text of node, can be placed in independent text chunk, and, but by the node storage pointer on the stack that points to text chunk rather than crossfire storage.

But structure can navigate and the crossfire storage

When storage system receives the XML document for storing, the text representation of document is resolved, and, but create concurrently, can navigate and crossfire storage expression.But Fig. 3 creates can to navigate and the process flow diagram of the processing of crossfire memory node.In step 310, from document, resolve next token.When the token of resolving is identified as the beginning of XML key element in step 312, mean that the stack frame of this key element is pulled on stack in step 314.But to the complete navigation nodes corresponding with this key element, allocation space in the memory paragraph that can navigate.Information about this node is stored in the stack frame, comprise that the pointer of new allocation space that sensing can navigate in storage is together with the value be associated with this node, such as any in the child of the size (being initialized as the size of node) of the quantity (being initialized as 1) of the node in subtree, subtree and instructs node, whether be arranged in the mark (being initialized as vacation) that can navigate and store.When resolving additional token, these values can be updated.When being placed on stack by nodal information, the child of node is also all not processed.

Resolve next token.If next token is child's key element of last node, above-mentioned processing occurs so.Allocation space in the storage of can navigating, and the node corresponding with this key element is pulled on stack, and has initialized value in new stack frame for new node.Value in the stack entry not only covers the pointer of the newly assigned storage of navigating, and the pointer entered in the navigated storage distributed for father is copied in father's pointer of child in the stack frame of child nodes.Usually, it will be understood by those skilled in the art that when creating node, follow the tracks of the navigation hands for the node in the storage of can navigating, and it is stored in stack.In addition, the node counts that is stored in the last key element in stack increases progressively, and the size of child nodes is added to the size of the subtree of last node (it is the father of current node).

In step 316, if next token is not closure element, so, in step 318, but copies in the crossfire node by token and resolve next token (step 310).When the end of next token indicative feature in step 316, determine whether this key element of storage in previous the navigated memory node distributed in step 320.Whether any in the child based on well-formedness tolerance described above and node is arranged in the storage of can navigating is determined.Well-formedness tolerance is used node counts in the stack frame that is stored in key element and the currency of subtree size.

If determine not memory node (that is, well-formedness tolerance is no more than the threshold value of setting up in advance) in the storage of can navigating, discharge so for the previous space of distributing of node.By deallocating the space that is not used to memory node in the storage of can navigating, limited the amount that builds the needed storer of storage that can navigate.Do not need to mean immediately whole document in storer.Even node is the first child of father's node, on this process points, does not also know whether father's node of node is arranged in the storage of can navigating, and therefore do not know whether need to create the dummy node in the storage of can navigating for this node.Data are stored in father's stack frame, but to indicate the first child nodes not to be stored in can to navigate in storage and to comprise the pointer for the first child's crossfire node.If father is stored in after a while as navigating fully, but but will create so illusory navigation nodes to point to the node of the first child in the crossfire storage.

If node will be stored in the memory node that can navigate fully in step 320, so, in step 326, suitable value is copied to the storage of can navigating to mean node from stack.The still father's node on stack of node is updated, and to indicate one in its child nodes, is arranged in the storage of can navigating.In step 328, if be stored in the first child of the information instructs node in node, be not stored in the storage of can navigating fully, so in step 330, for the first child nodes establishment dummy node of node.In step 324, for the stack frame of node, leave stack.

But flow process described above is supposed all nodes and is stored in the crossfire storage.In an alternative embodiment, but can assess whole document to determine whether storing the document in crossfire storage.If but in the crossfire storage, do not store document definite, so all nodes are stored as fully and can navigate, and content pointers is pointed to independent text chunk.In the present embodiment, step 318 can be by content replication to independent text chunk.Need to not distribute text chunk from the identical memory section for the storage of can navigating, and, do not require text chunk with can the section of navigation adjacency.In another embodiment, but can be independently for being contained in each node of assessment in the crossfire storage.But the node be stored in the storage of can navigating fully also can be stored in the crossfire storage, or, but navigation nodes can be pointed to the text chunk of its content.But the node be not stored in the crossfire storage must be stored as fully and can navigate.

But for the node that adds the crossfire storage to, but the pointer of the beginning of sensing crossfire node is stored in the content pointers of node in stack., if but node is not contained in the crossfire storage, the stack contents pointer is set in the interior position of text chunk of the content of node so.

In addition, but the crossfire node can comprise, get back to the pointer of memory paragraph that can navigate, but take, to be positioned on the document order be Next navigation nodes fully.But but exist dummy node the crossfire node retreat the end that pointer can point to illusory navigation nodes.But this will be next position of navigation nodes fully.Otherwise, but in all other crossfire nodes to retreat the pointed storage of can navigating as follows: if the last space of distribution is only temporarily distributed in the storage of can navigating, but the retreating pointer and can or end up being end with the beginning of pointing to this storage of crossfire node so.If be disengaged after a while distribution for can the navigate node of storage of its temporary transient distribution, retreat so pointer and will point to the beginning of storing.If used this storage by permanent the appointment after a while for can the navigate node of storage of its temporary transient distribution, retreat so pointer and will point to the temporarily end of the storage of distribution.But, if the last storage distributed in the storer that can navigate forever is assigned to node, but but so current crossfire node retreat the end that pointer will point to the navigation space of this permanent allocation.In one embodiment, until this pointer that retreats could be inserted in definite correct position.In an alternative embodiment, but but but crossfire node memory storage to next fully the pointer of navigation nodes can initially point to and then last distribution navigation nodes (being adjacent) but navigation nodes.If the space for father is disengaged distribution after a while, can again assign pointer to the beginning in the space deallocated so.In addition, if but there is no node to occupy to distribute to next space of navigation nodes fully, can remove so pointer or it is assigned as to sky.

The snapshot of state when Fig. 4 means to be structured in the navigated storage of the example XML document of introducing in Fig. 2.Below describe until the sequence of the event of the state shown in Fig. 4.The description of some steps is more detailed than other step, still, for each similar node, uses same group of step:

A is shifted onto on stack 490, and can navigate the storage 420 in allocation space.

B is shifted onto on stack 490, and can navigate the storage 420 in for the B distribution node.In the stack frame, storage is for the pointer 430 of the navigated storage of B.Father's link (pointer) of B is initialised, and child's link of A is updated.The size of the node of B is added to the subtree size of A, and the node counts of A increases progressively.Mark 480 is initialised to indicate the child who there is no B to be stored in can to navigate in storage.

D is shifted onto on stack 490, and upgrades the child pointers 450 of B, and, the size of node D is added to for B(472) and the subtree size of A, and, for B(474) and the node counts of A increase progressively.

When these steps finish, mean constructed state in Fig. 4.Step subsequently comprises:

The well-formedness tolerance of determining D is no more than threshold value: make D leave stack and deallocate the navigated storage of D.

With D processing node E in the same manner.

The well-formedness tolerance of determining B surpasses threshold value.The link value of B is copied to the node distributed the storage 420 of can navigating from the stack frame.The the first child D that notes B is not stored in the storage of can navigating, and, but but the illusory navigation nodes of the D of the crossfire memory node of establishment sensing D.

Make B leave stack

Set the child of mark with indication storage A in the storage of can navigating in A.

Now, the subtree of B is processed and the subtree of C is processed by the next one fully.Once the subtree of C is processed, just A is copied to for the navigated storage of its distribution and away from stack.

But mix and can navigate and crossfire storage assessment inquiry by use

But once parse documents and can navigate and the combination of crossfire storage organization in its node of storage, can use these structures for the assessment inquiry.Fig. 5 means as the example XML document of mixing the table 1 that storage format means.Below a series of step for assessment inquiry subsequently on the mixing binary representation shown in Fig. 5:

for?$t?in/PurchaseOrder/LineItems

where?$t/LineItem/Description=“The?Life?of?Brian”

return($t/../Reference)

PurchaseOrder is the root node of known as memory in node 530.LineItems is the node that the next one will find.Travel through the first child pointers 534 location dummy node, thereby indicate the first child (Reference) not to be stored in can to navigate in storage.Dotted line shade in Fig. 5 is used to show dummy node.The pointer of dummy node is traversed, but to find the crossfire node of storage Reference key element.The Reference node is scanned end, and, but pointer 572 points to next navigation nodes 550 that means LineItems.In order to assess " where " statement, the node that the next one will find is the LineItem as the child of LineItems.The first child pointers 554 is pointed to dummy node 560, thereby the first child of indication LineItems is not stored in the storage of can navigating.But the pointer 568 of dummy node 560 points to the beginning of the LineItem node in the crossfire storage.But the LineItem node in the crossfire storage is scanned to find the Description node as the child of LineItem.When finding the Description node, its value (" Robocop ") is compared with " The Life of Brian ", therefore, predicate (predicate) is not met by a LineItem.There is not pointer in end at a LineItem, thereby but means not exist more navigation nodes fully.As an alternative, can there is the pointer with null value.But, but there is another LineItem in crossfire node subsequently.Scan next LineItem node, find Description, and the content of Description is " the Life of Brian " that meets predicate.Owing in meeting one group of LineItems of predicate, finding LineItem, therefore, $ t is set to mean node 550(LineItems).

In order to assess $ t/../Reference, but the father's pointer 552 that uses the LineItems navigation nodes to find the father of LineItems, i.e. node 530(PurchaseOrder).Although be not stored in the storage of can navigating,, can link 534 with the access dummy node and travel through content pointers 548 to find Reference by traveling through the first child, but find at an easy rate the Reference node in the crossfire storage.

The hardware summary

According to an embodiment, by one or more specific use calculation element, realize technology described herein.The specific use calculation element can be by hardwire with execution technique, perhaps, can comprise digital electron device, such as being applied specific integrated circuit (ASIC) or field programmable gate array (FPGA) with one or more of execution technique by permanent programming, or can comprise one or more common hardware processor be programmed to according to the programmed instruction execution technique in firmware, storer, other storage or combination.This specific use calculation element also the programming of customization hardwired logic capable of being combined, ASIC or FPGA and customization to realize technology.The specific use calculation element can be desk side computer system, portable computer system, hand-held device, interconnection device or add hardwire and/or programmed logic to realize any other device of technology.

For example, Fig. 6 is the block diagram that the computer system 600 that can realize embodiments of the invention on it is shown.Computer system 600 comprises bus 602 or for transmitting other communication agency of information, and with the hardware processor 604 of bus 602 couplings for the treatment of information.Hardware processor 604 can be for example general purpose microprocessor.

Computer system 600 also comprises and the information that will be carried out by processor 604 for storage of bus 602 couplings and the primary memory 606 of instruction, such as random-access memory (ram) or other dynamic storage device.Primary memory 606 also can be used to be stored in temporary variable or other intermediate information in the implementation of the instruction that will be carried out by processor 604.These instructions are when being stored in can be in the nonvolatile storage medium of processor 604 access the time, making computer system 600 become the specific use machine that is customized to carry out the action of stipulating in instruction.

Computer system 600 also comprise with bus 602 coupling for storage for the treatment of the static information of device 604 and the ROM (read-only memory) of instruction (ROM) 608 or other static memory.For the memory storage 610 of storage information and instruction, such as disk or CD, be set up and be coupled with bus 602.

Computer system 600 can be coupled by bus 602 and the display such as cathode ray tube (CRT) 612 for show information to the computer user.For the input media that comprises alphanumeric and other key 614 to processor 604 transmission information and command selection and bus 602 couplings.The user input apparatus of another type is for to processor 604 direction of transfer information and command selection and for the cursor of controlling the cursor movement on display 612, controlling 616, such as mouse, trace ball or cursor direction key.This input media has i.e. the first (for example, x) He the second axle (for example, degree of freedom y), the position in this degree of freedom permission device predetermined surface of two axles usually.

Computer system 600 can realize technology described herein by using the hardwired logic, one or more ASIC or FPGA, firmware and/or the programmed logic that cause computer system 600 or it is programmed for to the customization of specific use machine with the computer system combination.According to an embodiment, answer processor 604 carry out one or more instruction of being contained in primary memory 606 one or more sequence, the technology of being carried out here by computer system 600.Can these instructions be read primary memory 606 from another storage medium such as memory storage 610.The instruction sequence that execution is contained in primary memory 606 causes processor 604 to carry out treatment step described herein.In an alternative embodiment, as software instruction substitute or with its combination, can use hard-wired circuitry.

Term used herein " storage medium " refer to the storage cause machine to move in a particular manner data and/or any nonvolatile medium of instruction.These storage mediums can comprise non-volatile media and/or Volatile media.Non-volatile media comprises for example CD or disk, such as memory storage 610.Volatile media comprises dynamic storage, such as primary memory 606.The common version of storage medium comprises for example floppy disk, flexible disk, hard disk, solid-state drive, tape or any other magnetic data storage media, CD-ROM, any other optical data carrier, any physical medium, RAM, PROM and EPROM with the pattern in hole, FLASH-EROM, NVRAM, any other memory chip or box.

Storage medium is different from transmission medium, but can be combined with it.The information that transmission medium participates between storage medium transmits.For example, transmission medium comprises concentric cable, copper cash and optical fiber, comprises the wire that comprises bus 602.Transmission medium also can be taked the form of sound wave or light wave, such as in radiowave and infrared data communication, produce those.

Be carried in the process of processor 604 for execution in one or more sequence by one or more instruction, can comprise various forms of media.For example, can be at first on the disk of remote computer or solid-state drive, carry instruction.Remote computer can be by instruction load in its dynamic storage and by using modulator-demodular unit to send instruction in phone line.The modulator-demodular unit of computer system 600 this locality can receive data on telephone wire, and uses infra-red transmitter so that data-switching is become to infrared signal.Infrared detector can be received in the data of carrying in infrared signal and suitable circuit can be placed in data on bus 602.Bus 602 is carried to primary memory 606 by data, from this primary memory 606, and processor 604 retrievals and execution instruction.The instruction received by primary memory 606 is optionally before being carried out by processor 604 or be stored in afterwards on memory storage 610.

Computer system 600 also comprises the communication interface 618 with bus 602 couplings.Communication interface 618 provides the bidirectional data communication coupling to the network linking 620 be connected with LAN 622.For example, communication interface 618 can be integrated services digital network network (ISDN) card, cable modem, satellite modem or the modulator-demodular unit that the data communication connection is provided for the telephone wire to corresponding type.As another example, communication interface 618 can be LAN (LAN) card that provides data communication to connect for the LAN to compatible.Also can realize wireless link.In any this realization, communication interface 618 sending and receiving carryings mean electric, the electromagnetic or optical signal of the digit data stream of various types of information.

Network linking 620 provides data communication by one or more network to other data set usually.For example, network linking 620 can be provided to host computer 624 or by the connection of the data equipment of ISP (ISP) 626 operation by LAN 622.ISP 626 provides data communication services by the world wide packet communication network that is commonly referred to as now " the Internet " 628 then.Both are all used electric, the electromagnetic or optical signal of carrying digit data stream LAN 622 and the Internet 628.By the signal of diverse network and on network linking 620 and the signal of the communication interface 618 by carrying the logical numerical data to and from computer system 600 are exemplary form of transmission medium.

Computer system 600 can send message and receive data by network, network linking 620 and communication interface 618, comprises program code.In the example of the Internet, server 630 can pass through the request code that the Internet 628, ISP 626, LAN 622 and communication interface 618 transmit for application program.

The code received can be carried out by processor 604 when received, and/or is stored in memory storage 610 or other non-volatile memories for carrying out after a while.

In above instructions, with reference to a large amount of specific detail that can change, embodiments of the invention have been described between realizing.Therefore, instructions and accompanying drawing should be regarded as explaining rather than limited significance.The scope of the present invention that the indication of proprietary scope of the present invention and applicant are intended to is word and the equivalency range from one group of claim of the application's book issue, and this scope is taked the specific form of these claim issues, comprises any correction subsequently.

Claims (20)

1. the method for the XML document of storing a plurality of documents comprises:

For XML document, but store can navigate comprising of described XML document, mean the expression meaned with crossfire in permanent warehouse;

Wherein, described XML document comprises the tree of the node of hierarchical relational, and at least one other node in each node of the tree of described node and the tree of described node has middle hierarchical relational;

Wherein, but described crossfire mean and can navigate to mean to comprise the node from the tree of described node;

Wherein, but described crossfire mean to comprise and be not contained in the described node navigated in meaning from the tree of described node;

Wherein, be contained in described each node that navigates the node in meaning and comprise the pointer that there is the node of middle hierarchical relational for described each node;

Wherein, but at least a portion of the node of described crossfire in meaning according to the document order;

Wherein, carry out these steps by one or more calculation element.

2. according to the process of claim 1 wherein, for one or more node, the described navigation means to comprise at least one in following pointer:

A) for the pointer of father's node, wherein, described father's node is contained in the described expression of navigating;

B), for the pointer of node born of the same parents, wherein, described node born of the same parents is contained in described navigation means; And

C) for the pointer of child nodes, wherein, described child nodes is contained in the described expression of navigating.

3. according to the process of claim 1 wherein, but described crossfire means to comprise all nodes in described XML document.

4. according to the process of claim 1 wherein, but exist, be not contained in described crossfire at least one node in meaning in described XML document.

5. according to the method for claim 1, wherein, for each node be contained in described one or more node navigated in meaning, the described navigation means to comprise the child pointers for child nodes, wherein, but the described child nodes that is used for described each node of described one or more node is contained in described crossfire and means, and described child nodes is not stored in the described expression of navigating.

6. according to the method for claim 1, wherein, for each node be contained in described one or more node navigated in meaning, the described navigation means to comprise the pointer born of the same parents for node born of the same parents, wherein, but the node described born of the same parents that is used for described each node of described one or more node is contained in described crossfire and means, and described node born of the same parents is not stored in the described expression of navigating.

7. according to the process of claim 1 wherein, but being contained in described the navigation, one or more node means and described crossfire means in both; And,

Wherein, for each node of described one or more node, but described the navigation means to comprise the pointer for being contained in described each node of described crossfire in meaning.

8. according to the process of claim 1 wherein, but one or more node be contained in described navigate mean in and be not contained in during described crossfire means; And,

For each node of described one or more node, the described navigation means to comprise for described the navigation, meaning to separate the pointer of the text chunk of storing.

9. according to the method for claim 1,

Wherein, described XML document is the second XML document that meets the first XML document of XML scheme and meet described XML scheme;

Wherein, for specific XPath, express, with at least one node of specific XPath expression matching in described the first XML document, be contained in the navigated expression of described the first XML document, and, in described the second XML document with at least one node specific XPath expression matching, be not contained in the navigated expression of described the second XML document.

10. according to the method for claim 1, also comprise the assessment path expression, wherein, but the assessment path expression comprises the pointer of described certain node in meaning to mean for described crossfire with retrieval that navigates of traversal, but but and use the pointer of certain node in meaning for described crossfire to visit the described node of described crossfire in meaning.

11. the method according to claim 10, wherein, the assessment path expression also comprises: but after certain node in the described crossfire of access means, but mean the pointer of retrieval for described another node meaning that navigates from described crossfire, use the described node navigated in meaning further to travel through the described expression of navigating.

12. the method meaned for the storage of the node in the XML document of determining a plurality of XML document comprises:

For each node in described node, at least based on take the characteristic of the subtree that described each node is root, determine that the storage of described each node means;

Wherein, the storage of determining described each node means also to comprise:

Determine whether take the characteristic of the subtree that described each node is root meets the first criterion;

Response determines that take the characteristic of the subtree that described each node is root meets the first criterion, determines described each node of storage in the storage of can navigating;

Wherein, carry out these steps of described method by one or more calculation element.

13., according to the method for claim 12, wherein, determine whether take the characteristic of the subtree that described each node is root meets the first criterion and also comprise determining whether surpass threshold value take on the subtree that described each node is root the well-formedness tolerance of assessing.

14., according to the method for claim 13, wherein, described well-formedness tolerance is the amount in the quantity based on being contained in the node in subtree and the space that occupied by the content of described subtree at least.

15., according to the method for claim 13, wherein, described well-formedness is measured in computer based processing speed at least or I/O speed.

16., according to the method for claim 13, wherein, described threshold value is based at least one in following aspect:

A) manual configuration; With

B) characteristic of the node of the set based on evaluation history queried access pattern and the document of accessing in described historical query access module determines automatically.

17. a method of for the navigation storage, adding node comprises:

The response analyzing XML file, receive the first token from the XML document of a plurality of XML document;

Determine that described the first token is the beginning of an XML key element;

Distribute the first amount of space for the first node that means a described XML key element in the storage of can navigating;

Receive the second token from described XML document;

Response determines that described the second token means the beginning of the 2nd XML key element, in the described storage of navigating, for Section Point, distributes the second space amount;

Response determines that described the second token means the end of a described XML key element, determines whether the described first node of storage in the storage of can navigating;

The not described first node of storage in the described storage of navigating is determined in response, from the described storage of navigating, deallocates described the first amount of space;

Wherein, carry out these steps of described method by one or more calculation element.

18. the method according to claim 17 also comprises:

Determine that the second token is the beginning of the second key element, and receive the 3rd token as the end of described the second key element;

Determine that described Section Point should be stored in the storage of can navigating.

19. according to the method for claim 17, also comprise the data of upgrading in described first node, with the size of the subtree of the counting of the quantity that comprises node and described Section Point.

20. a computer-readable recording medium of storing instruction, wherein, the method that described instruction is put down in writing in causing carrying out any one in claim 1～19 when being carried out by one or more processor.

Images