CN100383741C - Consistency Maintenance Method for XML-Oriented Mark Backtracking - Google Patents

Abstract

The prevent invention belongs to the technical field of collaborative work supported by computers, and particularly relates to an XML-facing consistency maintaining method for label backtrack. The prevent invention comprises a control algorithm for programs, a maintenance algorism for history operation records, a maintenance algorism for an inverted index list, a backtracking algorithm, an FLW algorism for attaining an operation executing group, and an executing algorism for Update operation, and also comprises a local maintenance method for state vectors, and a local broadcast method for state vectors. The entire consistency maintaining method is divided into two parts; the prevent invention enables multiple users to edit a same XML data object in a real time, the users can not mutually interfere, and the local operation can instantly respond. The present invention can automatically process operation conflicts among the users, and the consistency maintenance for data among the users can be realized.

Description

Consistency maintaining method towards the mark retrace of XML

Technical field

The invention belongs to computer supported cooperative work (Computer Support Cooperative Work) technical field, be specifically related to a kind of consistency maintaining method of the mark retrace towards XML, this method can so that a plurality of user by existing application software edit one XML data object in real time, by a kind of real-time collaborative technology of not having lock, can not influence each other between a plurality of users.The present invention can support the Query operation and the Update operation of XML data, the operating collision between the automatic process user, the consistency maintenance of realization data between each user.

Background technology

" computer supported cooperative work " (CSCW, Computer Support Cooperative Work) can be defined as: in the environment that computer technology is supported (being Computer Support), a common task (being Cooperative Work) is finished in a groupware collaborative work.Its target is to design the application system of various collaborative works.

The product of CSCW can become groupware (GroupWare).CSCW and groupware have nuance, and CSCW is a subject, and groupware is a concrete technology or an entity, and the CSCW system of specific implementation is considered to the example of groupware one class, but two terms are also used with sometimes.

The formation and development of CSCW has certain certainty.At first, in the information society in modern times, people's life style and labor style have group, interactivity, characteristics such as distributivity and collaborative.Secondly, the develop rapidly of computer technology (comprising parallel and distributed treatment technology, multimedia technology, database technology, cognitive science or the like), communication and computer networking technology has constituted the technical foundation that CSCW realizes.In addition, the proposition of this notion of concurrent engineering (Concurrent Engineering) also plays an important role.Concurrent engineering is the systems approach of integrated, concurrent designing product and correlated process, and it emphasizes Team Work (group work), and is closely-related with the research of CSCW to the technical support of Team Work.Therefore we can say that CSCW is in modern society, is background in people's collaborative work mode, with computing machine and development of Communication Technique be fused to the basis, has application fields and be a precondition and formation naturally.It relates to numerous ambits, as computing machine, and management, communication, compartment system, artificial intelligence, sociology, psychology, theory of organization or the like.

The purpose of CSCW is exactly the support that provides under computer environment people's teamwork, therefore says, communication, cooperation, coordination are the three elements of CSCW.

The basis of CSCW is communication, it is (but local communication can be thought the special case of compartment system) between the user who distributes geographically that the group communication of nature takes place, therefore network service is vital, and handles the multimedia file transmission and Data Control is very complicated in co-operative environment.And computer based or be the communication of medium with the computing machine, not fully and other communication form combine.Asynchronous text based Email and bulletin board are different with synchronous phone and face-to-face talk: people can not transmit file between two telephone numbers arbitrarily.Computer Processing technology and the communication technology combined to help to address this problem.

The form of CSCW is cooperation, and communicates by letter similarly, and cooperation is the important content of group work.In group activity, any activity all must be that multi agent cooperation is finished.Effectively the collaboration requirements people must share information.But current infosystem especially Database Systems is kept apart people mutually under many circumstances.Such as, be that they can not revise the different piece of same design object simultaneously and know his modification that the co-worker made when two designers use same CAD database to operate; They must just can know the work that the other side does by mutual inspection.Many tasks all need good shared environment, in due course the action message of friendly notice group and each user's activity.

The key of CSCW is to coordinate.If the activity of a group is coordinated, its communication and cooperation will be strengthened greatly so.The work group that can not well coordinate will certainly often clash and the duplication of labour between its member.When task of the common composition of several sections, coordination itself is counted as a requisite activity.Current database application provides the visit to shared object, yet most of Software tool only provides the support to single user, to this critical function of coordination of supporting group done but seldom.

Reinforcement along with enterprise and mechanism's globalization consciousness (providing its product or service) towards global range, therefore the effect that aspect performance such as can support the system of this cooperation will be at standardized administration, to raise the efficiency, reduce cost can not be substituted also will become requisite information facility.The trend of the extensive cooperation of this trend is bright and clear gradually along with the appearance of some important application patterns.These application models comprise: e commerce transactions, Virtual Organization, collaborative building, long-distance education, tele-medicine or the like, we believe that these application models will be to generation far-reaching influences such as future social people's work, study and lives.

The famous market analysis IDC of mechanism every two years can issue the market analysis and the prediction of a collaboration software, data are pointed out, as far back as calendar year 2001 U.S.'s collaboration software market share reached 3% to 5%, the last report pointed out that global TCA market scale will reach 7,500,000,000 dollars 2009.

The report of Computer World Information (CCW Research) issue shows that Chinese collaboration software market scale reached 5.89 hundred million yuan as far back as 2004, wherein works in coordination with the tool software market scale about 0.6 hundred million yuan, about 5.29 hundred million yuan of collaborative platform and applied software markets; Collaboration software market mainly concentrates on three zones in East China, south China and North China, and wherein the zone, East China accounts for 26.76% of whole markets.2004, the collaborative instrument of China, platform and applied software market total sales were above 5.89 hundred million yuans.Since 2000, along with popularizing of informationalized propelling, internet and IT application, Chinese collaboration software market formed gradually.Especially Email becomes after the tool of communications important in enterprise's day-to-day operations management day by day, and collaboration software market becomes an important component part of applied software market gradually.Expected that collaboration software market will be with 34.45% annual compound growth rate development 2004～2008 years, by 2008, the market total value will reach 19.26 hundred million yuan.

Groupware is a vital classification in CSCW field, promptly supports people to carry out the software systems of collaborative work.Group editor is that the groupware application field is a kind of.It allows a plurality of users to participate in the editor and the modification of a sharing data objects simultaneously by network.Group editor is not limited only to text, can also be applied to the collaborative modification (literal, figure, medium etc.) of various types of data object, is an important technology safeguarding many copy datas object consistency.The research of group editing technique is the top international conference ACM CSCW in CSCW field and the important content on the ACM Group always, and special symposial has also been held five.Group editor's correlation technique has also obtained using widely, is implemented as two systems that support the multi-user to organize editor based on MS Word/MS PowerPoint.

Target the most basic of group editor is to hide the impression of user to network delay.By safeguarding a data copy, realize making an immediate response to local operation at each user side.So consistency maintenance is one of topmost challenge among the group editor.In the past twenty years, many relevant technology have also obtained tremendous development, but the solution that many difficult problems of consistency maintenance aspect still do not improve.In the world on the consistency maintenance problem, mostly be conceived to operate the method for conversion at present.But the operation conversion method still exists very big difficulty in the some difficult problems that solve consistency maintenance and aspect the support of Undo operation.

Summary of the invention

The objective of the invention is to propose a kind of consistency maintaining method of the mark retrace towards XML, specifically is the consistency maintenance engine that makes up an application program, comprises control algolithm, back-track algorithm and the operation execution algorithm of program in this engine.The state vector maintaining method and the broadcasting method that also comprise a this locality in the engine.Wherein, can be so that a plurality of user edit one XML data object in real time, by a kind of real-time collaborative technology of not having lock, can not influence each other between a plurality of users, the present invention can support the Query operation and the Update operation of XML data, operating collision between the automatic process user, the consistency maintenance of realization data between each user.

Introduce some relevant key concepts below earlier.

Group editor is the vital classification in groupware application field.It allows a plurality of users to participate in the editor and the modification of a sharing data objects simultaneously by network, and group editor's a important goal is exactly making an immediate response of local operation, and promptly the nothing of local operation postpones to carry out.The nothing that realizes operation postpones the full copy type structure of an important means of execution with regard to data, be that each user keeps a data trnascription, the user operates in this locality and can carry out immediately, sends to other user then, but full copy type structure can cause the consistency maintenance problem.

Real-time CSCW system must satisfy following 3 condition for consistence simultaneously and be only consistent: 1. data consistency (convergence): after executing one group of co-operating, the content of copying data should keep in full accord on each node: 2. cause and effect consistance (causality preservation): any two operation C1, C2, if the cause-effect relationship on their life periods: C1 → C2, then on all nodes, C1 carried out before C2; 3. wish consistance (intentionpreservation): any two operation C1, C2 is if they are separate: C1||C2, then their results of carrying out with any order on any node expected results unanimity of carrying out in this locality of Ying Yuqi.

Based on the timestamp (State Vector based timestamp) of state vector, be widely used for differentiating the causal sequence (Causal Relationship) of operation room.An actual stamp is a vector, website of each dimension expression of vector, and the value representation on this one dimension has been carried out the quantity of the operation in this website in the vector.Because the operation from same website all is that order is carried out, so which operation that timestamp can be illustrated under the state of this timestamp executed, if all executed operations are included in the executed operation of another timestamp in the timestamp, then two timestamps satisfy cause-effect relationship, otherwise are concurrency relations.In the timestamp pattern, each website all can have its state vector, all can together broadcast together with the timestamp of current website after each operation produces.

In order clearly to describe, we claim to operate the local replica of that data trnascription of generation for operation, and other data trnascription is the strange land copy of operation.We claim this to be operating as the local operation of local replica, the strange land operation of strange land copy.

One piece of XML document can be expressed as a rooted tree, and the node of tree is orderly, and each node all has corresponding Label.The example of an XML document can be expressed as:

<Root>

<node@name＝″A″>

<attr>2</attr>

<value>D</value>

</node>

<node@name＝″B″>

<attr>3</attr>

</node>

<node@name＝″C″>

<attr>3</attr>

</node>

</Root>

An XML document can be modeled as a vertex ticks tree, and three category nodes are arranged: (1) node element, the corresponding label of each node is just as " node " in the last example and " attr " etc.In vertex ticks tree, node element for mark be exactly the label of node.(2) attribute node for the value among the XML, is for example gone up the “ @name in the example ", with the difference of node element be that attribute node does not exist nested and sequence independence.(3) value node, the value in the corresponding XML document of value node for example goes up " 2 " in the example, " 3 " etc.The structural relation between node element, attribute node, value node has been represented on limit in the vertex ticks tree.Node element, attribute node, value node in the vertex ticks tree can abstractly be general tree node.XML document in the last example can presentation graphs 1.

The Query operation of an XML can be expressed as the XQuery standard, XQuery is expressed as FLWR (For-Let-Where-Return), the XQuery query script can be divided into the twig patternmatching process of two parts: FLW definition, and the result construction process of R (Return) definition.The FLW process has at first obtained a sub-tree, and R (Return) process is with its re-construction and return then.The return results of XQuery remains a set, and each element among the set is all by the sub-tree after the re-construction.

The Update of XML operation does not also have standard, can expanding XQuery obtains the method for expressing of a kind of FLWU (For-Let-Where-Update).So similar with XQuery, FLWU can be divided into independently two steps: at first obtain a plurality of sub-tree by the FLW process, U (Update) process is revised the corresponding nodes of XML document corresponding among each sub-tree then.For the Update operation, the execution that we require to operate will obtain restrictive conditions all in the operation, and then actual making amendment.

The environment that has a plurality of XML copies, we wish the user is transparent.That XML copy that has only his current accessed that the user sees.For the copy environment, it is concurrent supposing a Query operation and having the Update operation altogether, In the view of the user, a Query operation all can receive with the execution of a Update operation with any order, i.e. the content whether this Query operation comprises the Update operation all is fine.So, consider that a copy receives Query operation of user for many copies environment, can carry out immediately and return results, and need not to consider whether to have before this other concurrent operations to carry out, i.e. Query operation can not constitute concurrency relation with other operation.Under many copies environment, we only need to consider the concurrent situation of Update operation.

Because the existence of concurrent operations, when site-local was received a strange land Update operation, the state of XML document may change, and operation can't be carried out immediately.State exchange (State Transformation) is by the state of the inverted index table of conversion XML document, state when the inverted index table of at first recalling (Retrace) XML document produces to each operation, in the inverted index table after conversion, position when the index structure of XML node produces with operation represents it is consistent, operation can be carried out collection immediately accordingly to carry out in new inverted index table, operation can recover inverted index table after carrying out, to prepare the execution of next operation.

Under the timestamp pattern, guarantee that cause and effect consistance (Causality Preservation) only needs website of assurance to carry out the executive condition that operation is satisfied in a strange land operation: promptly each is operated all to have under the situation that guarantees causal sequence and carries out.Even but satisfy the causal sequence of operating, the order difference that operation arrives between different websites, the order of execution still can be different.We only need guarantee that it satisfies convergence (Convergence) and wish is safeguarded (Intention Preservation) when the executive condition of operation is satisfied in an operation.

The coherence method that the present invention proposes towards the mark retrace of XML, it is the consistency maintenance engine that makes up an application program, this engine comprises FLW algorithm and the Update operation execution algorithm that control algolithm, historical operation record maintenance algorithm, inverted index table maintenance algorithm, back-track algorithm, the operation execution collection of program obtain, and also comprises the state vector maintaining method and the broadcasting method an of this locality.Whole consistency maintaining method is divided into two parts: to the execution of local user manipulation, to the execution of strange land user operation.Execution flow process to local user manipulation is: program is carried out local operation, revises state vector, then with the state vector of this locality as timestamp attached in the operation, be broadcast to other user.Execution flow process to strange land user operation is: control algolithm is received strange land user's operation, when satisfying executive condition, according to its timestamp that adheres to, the inverted index table of recalling local XML data trnascription produces constantly to it, on this state, operation can obtain identical execution collection by the FLW algorithm that operation execution collection obtains, and obtains correct execution by Update operation execution algorithm, recovers inverted index table then to treat next operation.The present invention can be so that a plurality of user edit one XML data object in real time, can not influence each other between a plurality of users, local operation can make an immediate response, the operating collision between the automatic process user of meeting of the present invention, the consistency maintenance of realization data between each user.

Because the influence of concurrent operations when program is received an operated from a distance, is compared when the state of XML document produces with operation variation has been taken place, operation can't be carried out immediately.For correctness and the consistance that guarantees to operate, we need at first recall the inverted index configuration state of XML document.The process of recalling is according to the subsidiary timestamp of operation, sets gradually in the inverted index structure, and each is provided with the content and the effective/disarmed state of node by the related node of concurrent operations, is consistent when the inverted index structure is produced with operation; Under this inverted index structure, operation can obtain identical execution collection, and modification process thereafter only need carry out according to carrying out collection, revises local state vector then, and recovers the inverted index structure to treat the execution of next operation.

Various algorithms in the engine are kept in following mask body introduction.

1, the control algolithm of program

Control algolithm in its engine is an execution flow process to strange land user operation.Be specifically after receiving a strange land user operation, if the executive condition of operation is satisfied in operation, then engine can send operation to the execution of programmed control algorithm, the timestamp that the programmed control algorithm at first adheres to according to operation, call back-track algorithm and recall the inverted index table of local XML data trnascription to its generation moment, the execution collection that the FLW algorithm that obtains by operation execution collection obtains operating, carry out this operation according to action type then, operate the complete state vector of revising this locality afterwards according to the state vector maintaining method of this locality, the inverted index table that recovers local XML data trnascription at last is to treat the execution of next operation.

Suppose that current website is R, its state vector is SV _XMLDoc, corresponding document is XML _Doc, a strange land operation 0, the timestamp of operation 0 is SV ₀, and satisfy the executive condition of operating, then the programmed control algorithm is as follows in the flow process of the implementation of website R:

A strange land can't directly be carried out, and is because other concurrent operations has been revised the state of XML document.The effect that Update operation is carried out is decided by the set of the subtree that the FLW process is obtained, i.e. its execution collection, and U (Update) process of Update operation only travels through the execution collection that obtains and carries out corresponding modification.So in order to guarantee that Update obtains identical result at all XML copies, we need guarantee that the FLW process of Update operation obtains and its execution collection identical on local replica.When operation will be carried out on a strange land copy, we are by hiding the influence that other concurrent operations causes in the XML copy of strange land, the XML document state is dated back to on-unit, the XML state of the local replica when it produces, we claim that this process is state exchange (ST, State Transformation).Document carries out after the ST, and identical execution collection when the FLW process of Update operation can obtain to carry out on local replica with it in the above is so also just guaranteed the consistance of operating result.

2, historical operation record maintenance algorithm

Historical operation record maintenance algorithm in the engine, be the timestamp subsidiary according to operation, decision operation safeguards that in the executing state of all websites all are not fully in all operations of website execution, when operate in all websites complete after, just deletion in the historical operation record.

In trace-back process, have only concurrent operation just can exert an influence to trace-back process.And operate in after all websites all have been performed when one, just can not constitute concurrency relation with other operation again.In order to handle trace-back process, we only need safeguard those not operations of all websites execution more still.Because adopted the timestamp based on vector, we also use the method for State Vector Table (SVT) to judge.Operation store in (OperationHistory List), is received new strange land operation at every turn in the historical operation record, all pass through its subsidiary SV and upgrade SVT, and upgrade OHL.As shown in Figure 2.

3, inverted index table maintenance algorithm

Inverted index table maintenance algorithm in the engine, it is inverted index table of XML data trnascription structure for this locality, set up an incidence relation between each XML node content and the node Label, know a deterministic content, can retrieve the identical node of all the elements rapidly, then relatively, ancestors, descendent relationship between can decision node by the Label between them.The inverted index table maintenance algorithm has safeguarded that also each operates with it related internodal incidence relation in the historical operation record.

No matter be Query operation or Update operation, its core all is the FLW process, and the core of FLW process is the tree schema coupling.In order to handle the tree schema coupling, we need retrieve the respective nodes in the XML document apace.This paper has adopted the disposal route of native XML query, by safeguarding the inverted index table of all XML nodes, as Fig. 2.Can retrieve the node (element/property/value) that designs in the FLW process fast by inverted index table, again by the various axle relations among the connection procedure coupling FLW, with its combination, the subtree that obtains at last set.The all changes of XML document state all can be reflected in its inverted index table.In order to quicken trace-back process, we safeguard the index of node in inverted index table that this operation is related, as Fig. 2 for each operation among the OHL.

Receive a strange land operation when an XML copy, at first it added among the OHL that this operation of virtual then execution according to the execution collection that its FLW process obtains, concentrates related node to set up index at inverted index table with carrying out.Be inserted in and insert node in the inverted index table, also node is inserted in the XML document.But deletion only is that the node in the inverted index table is done delete flag, and actual modification XML document not.Trace-back process only need travel through this concordance list, hides the influence of all concurrent operations, has operated and need not to travel through whole XML or re-execute these.

When the method for using SVT can judge that a operation among the OHL has been carried out in all websites after, we can carry out this operation is actual.Promptly in inverted index table, reality is deleted the node that all these operations will be deleted, and the index structure of deletion action on inverted index table.This operation of deletion in OHL at last.When the node of the deletion action of an actual execution of needs, the operation in other OHL also has and relates to, and when we only needed deletion of node, it was just passable also to delete all index that point to this node.Because the SVT method has indicated that this operates in all websites and all carries out, so no longer including other operation operates concurrent therewith, so this node of deletion can not exert an influence to follow-up back tracking operation, and no matter among the current OHL other operation what kind of this node carried out handle, final effect is also just deleted this node.

When a node in the inverted index table by OHL in operation when relating to, can set up an index structure of operating node, we claim it by among the OHL one be operatively connected.Node hereto, we set up a re-linked tabulation simultaneously, write down it and by which operation among the OHL are related to simultaneously, also write down the modification type (Insert/Delete/Update and corresponding contents) of this operation to present node.Even because same operation, a plurality of nodes that relate to are also had different modifications, as after the re-linked tabulation, no matter be that trace-back process might as well, still the execution of U (Update) process might as well, to the processing of a node, only need the re-linked tabulation of this node of traversal just enough.

4, back-track algorithm

Back-track algorithm in the engine, it is timestamp according to appointment, recall the concordance list structure of local XML data trnascription, each operated in the Object node that relates in the XML data trnascription concordance list during the historical operation of investigating back-track algorithm write down, for certain Object node wherein, consider all operations at this Object node, content recorder is set, inquire about the content of an operation of TOrder functional value maximum in the operation that continues before all causes and effects on this Object node, if the final structure of last content recorder is different with initial results, it is invalid that then virtual node of structure in inverted index table, and origin node is set to.State when back-track algorithm can date back to the inverted index table of XML data the assigned operation generation.

If the document linear structure of website R is expressed as XML _Doc, wherein the state vector of R is expressed as SV _R, establishing any one timestamp that satisfies causal sequence is SV ₀, then trace-back process can be expressed as following flow process:

The purpose of recalling is the influence of hiding among the OHL with other concurrent operations of current on-unit, keeps the influence of the operation of other and this first order relation of operation formation, the state the when document status of XML is dated back to this and operates in its local replica execution.Trace-back process only need travel through those and current operation concurrent operate in node related in the inverted index table.Because have only these nodes just can change.

We are summed up as insert/delete/update three classes to operation, if a node that relates to is inserted by a concurrent operations, after then recalling, insertion is invalid, and it is invalid that this node should be labeled as; If a node that relates to, all delete operations at this node are concurrent operations, are effectively and insert, and then node should be labeled as effectively.For Update, a plurality of operations while Update can constitute conflict during a node, and we wish to keep the part that all do not conflict, in the process of implementation, the node of conflict is taked the processing policy of Multi-Version/Single Display (MVSD), and this point will specifically be discussed in the back.So recall the result who obtains, should if the result is different with original node,, need in inverted index table, set up the node of mere formalities for all non-concurrent operations result under the MVSD strategy according to the result who obtains for the FLW process.

TOrder function in the algorithm, we specifically introduce in U (Update) process.A plurality of operations relate to same node among the OHL because have, and whether we were visited by current back tracking operation by the record node, in guaranteeing to recall at every turn, and the visit of the node that repeats to relate to a time.We only handle those concurrent operations, and only come again identical node, so efficient is still very high.

5, the FLW algorithm that collection obtains is carried out in operation

The FLW algorithm that collection obtains is carried out in operation in the engine, is the Update operation for a strange land user, can obtain a unified execution collection on all data trnascriptions.Update operation can split into four processes of FLWU, and the execution collection that the content of U (Update) process obtains in the FLW process before depending on.Before a strange land user operates execution, state when earlier the inverted index table of local XML data trnascription being dated back to this strange land operation and produces by back-track algorithm, operation is carried out and is collected the result that the FLW algorithm that obtains passes through to consider trace-back process then, can obtain identical execution collection.

The FLW process of a complexity can be decomposed into the inquiry of a plurality of ancestors, descendent relationship.We have improved the method for Stack-Tree-Desc, make it can support the mark that obtains in the trace-back process, and the difference of it and original algorithm is that it will consider hiding the concurrent operations effect in the trace-back process.Algorithm can be described as:

On the other hand, because the process of XML change also needs to revise simultaneously node corresponding Label.In order to support the modification of XML, the range coding that we have used the start/end of headspace to represent.

6, Update operation execution algorithm

Update operation execution algorithm in the engine is the Update operation for a strange land user, behind the execution collection that obtains operating, can obtain identical execution result.Owing to there are a plurality of concurrent operations, may there be conflict in operation room, Update operation execution algorithm adopts the Multi-version/Single-display strategy to handle all conflicting nodes, for the operation on all conflicting nodes, the content of choosing an operation of TOrder functional value maximum shows, thereby obtains unified version of display.

A plurality of Update operations may produce conflict, and the method for ST wishes to keep as much as possible the effect of user Update operation.Two concurrent operations insert node at same position simultaneously, and we keep two and insert the result; Two concurrent operations are deleted a node simultaneously, and we only need this node of deletion; Have only when two concurrent operations are revised a node simultaneously, we think that these two operations have produced conflict.Revising a plurality of other nodes because update operates in when producing conflict also, for the part of not conflicting, we wish to keep two operation results separately.Only for the part of nodes of conflict, we adopt the strategy of Multi-Version/Single-Display (MVSD).We duplicate all conflicting nodes, choose the content demonstration of the maximum operation of TOrder value then by the TOrder function, as shown in Figure 3.Only on conflicting nodes, this makes us can preserve the effect of operation as much as possible in the application of MVSD.

Insert operation and can compare for two, our definition of T order function, be used for representing two insert characters about relation, TOrder () less in the left side.Consider two operation O _aAnd O _b, the operation of its correspondence produces respectively from website a and b, and timestamp is respectively SV _aAnd SV _b, TOrder (O then _a)＜TOrder (O _b), and if only if (1) sum (SV _a)＜sum (SV _b); Perhaps (2) are as sum (SV _a)=sum (SV _b) time a＜b, wherein $\mathrm{sun}\left(\mathrm{SV}\right)=\underset{i=0}{\overset{N-1}{\mathrm{\&Sigma;}}}\mathrm{SV}\left[i\right]$ 。Be the Torder functions specify ordering relation of operation room (Total ordering), for two operations, the Torder function can provide the magnitude relationship of two operations.The Torder function has transitivity (Transitivity), and any two operations are comparable.Then Cao Zuo implementation is as follows:

Local state vector maintaining method is in order to safeguard local state vector.In consistency maintaining method, can judge which operation executed by the state vector of this locality.State vector has write down the quantity of carrying out from the operation of different websites, and after a new operation was performed, just the operation number of executions with this website added one, and upgrades local state vector.

Broadcasting method in the engine, be to give all other user with user's operational notification an of this locality, because which operation executed is local state vector can judge, represented that equally also these operations and the new local operation of carrying out satisfy cause-effect relationship, so broadcasting method together is notified to other user with this state vector as the timestamp of operating, and can allow other user know the state of the data trnascription that this operation was carried out.

Description of drawings

Fig. 1 is the vertex ticks tree.

Fig. 2 is the historical operation record, inverted index table and XML document node Label.

Fig. 3 is Multi-Version/Single-Display.

Fig. 4 is the generation and the execution sequence of operation.

Fig. 5 is the implementation of operation.

Embodiment

Be described in further detail the inventive method below in conjunction with an example.This example has been described towards the processing procedure of the consistency maintenance engine of the mark retrace of XML.

Suppose that a system has two user U ₁And U ₂, U ₁And U ₂Be concurrent operations, initial XML document is as shown below.The generation of operation and execution sequence are as shown in Figure 4.U ₁Hope contains in child node inserts a new node " D ", U among the sub-tree of value " 3 " ₂Wish to investigate the sub-tree for " B ", the attr " 3 " of the child node of sub-tree is revised as " 2 " with the name of Node.

<Root>

<node@name＝″A″>

<attr>2</attr>

<value>D</value>

</node>

<node@name＝″B″>

<attr>3</attr>

</node>

<node@name＝″C″>

<attr>3</attr>

</node>

</Root>

Wherein operate U ₁For:

FOR $node?in/root/node，

$attr＝$node/attr

WHERE$attr＝″3″

UPDATE$node{

INSERT<value>D</value>

}

Wherein operate U ₂For:

FOR $node?in/root/node，

$name＝$node/name，

$attr＝$node/attr

WHERE$name＝″B″

UPDATE$node{

REPLACE$attr?WITH<attr>2</attr>

}

Two operations are at first all carried out immediately at its local replica, are transferred to other strange land copy then.Our target operates in when the strange land copy is carried out can obtain the implementation effect identical with its local replica.U ₁Respectively " B " and " C " inserted a child node " D " respectively for the sub-tree of root at its local replica, but at SR ₂, owing to carried out U ₂, U ₁Arrive the back and directly carry out, only can insert child node " D ", can't obtain the execution result identical with its local replica at the sub-tree that with " C " is root.Shown in the top of Fig. 5.

In order to obtain the execution architecture identical, need at first carry out state exchange (StateTransformation) state the when inverted index table of promptly recalling XML document is operated generation to the strange land to XML document with its local replica.At first, work as U ₁During arrival, satisfied executive condition, so can directly carry out in ST, implementation is at first carried out back tracking operation.Trace-back process will consider the operation among the OHL, and have only a U among the OHL this moment ₂Operation, and operation U ₂The XML node that relates to is: Label is＜0.53,0.57〉the attribute attribute node.Trace-back process is visited this attribute node mark earlier.The attribute attribute node is at this moment also only by a U ₂Operation is revised, and revising type is Update, and this moment, Value was operation U ₂Content, and the operation U ₂Be operation U ₁Concurrent operations, then on the attribute attribute node, the result that all non-concurrent operations constitute is the initial content of attribute attribute node, so recalling the value of attribute attribute node, back-track algorithm is " 3 ", correspondingly, the position of attribute attribute node also can change in the inverted index table, and we add Label in the index chained list of " 3 " be＜0.53,0.57 a dummy node, the value of this dummy node is " 3 ".As shown in Figure 2.

After trace-back process was finished, the inverted index table of XML document had returned to operation U ₁State during generation is shown in the right part of Fig. 5.Obviously operate U ₁Carry out under this state, its FLW process can obtain " B " and " C " and be two sub-tree of root, i.e. Cao Zuo execution collection operates in this and carries out collection and carry out U (Update) process down, can obtain with its at the identical execution result of local replica.Operate complete after, can cancel the influence of all back tracking operations, to treat the execution of next operation, shown in the bottom of Fig. 5.

Claims (3)

1. A consistency maintenance method for XML-oriented tag backtracking, characterized in that it builds a consistency maintenance engine of an application program, including a control algorithm of a program, a historical operation record maintenance algorithm, and an inverted index list maintenance algorithm in the engine , backtracking algorithm, FLW algorithm for obtaining operation execution sets, Update operation execution algorithm, a local state vector maintenance method and broadcast method, the entire consistency maintenance method is divided into two parts: the execution of local user operations, and the remote user operation implement; The execution flow of the local user operation is: the program executes the local operation, modifies the state vector, then attaches the local state vector as a timestamp to the operation, and broadcasts it to other users; The execution flow of remote user operations is as follows: the control algorithm receives the remote user’s operation, and when the execution condition is satisfied, according to the attached timestamp, the inverted index table of the local XML data copy is traced back to the generation time, in this state , the operation can obtain the same execution set through the FLW algorithm obtained by operating the execution set, and the execution algorithm can be executed correctly through the Update operation, and then restore the inverted index table for the next operation. 2. The consistency maintenance method according to claim 1, characterized in that: The so-called program control algorithm is an execution process for remote user operations. After receiving a remote user operation, if the operation meets the execution conditions of the operation, the engine will send the operation to the program control algorithm for execution. Operate the attached timestamp, call the backtracking algorithm to trace the inverted index table of the local XML data copy to its generation time, obtain the execution set of the operation through the FLW algorithm obtained by the operation execution set, and then execute the operation according to the operation type. After the operation is completed Modify the local state vector according to the local state vector maintenance method, and finally restore the inverted index table of the local XML data copy to wait for the execution of the next operation; The so-called historical operation record maintenance algorithm is to judge the execution status of the operation at all sites based on the timestamp attached to the operation, and maintain all the operations that are not completely executed at all sites. delete from the record; The so-called inverted index table maintenance algorithm is to build an inverted index table for the local XML data copy, establish an association relationship between the content of each XML node and the node Label, and know a deterministic content, which can be retrieved quickly Go to all the nodes with the same content, and then judge the ancestor and descendant relationship between the nodes through the Label comparison between them; The so-called backtracking algorithm is to look back at the index table structure of the local XML data copy according to the specified timestamp. The backtracking algorithm examines the object nodes involved in each operation in the XML data copy index table in the historical operation records. An object node, consider all the operations on this object node, set the content recorder, query the content of the operation with the largest TOrder function value among all causal previous operations on this object node, and finally if the final structure of the content recorder is the same as the initial If the results are different, a virtual node is constructed in the inverted index table, and the original node is set as invalid, and the backtracking algorithm backtracks the inverted index table of XML data to the state when the specified operation occurs; The FLW algorithm for obtaining the operation execution set is to obtain a unified execution set on all data copies for the Update operation of a remote user; an Update operation can be split into four processes of FLWU, and the content of the Update process depends on The execution set obtained in the previous FLW process; before a remote user operation is executed, the inverted index table of the local XML data copy is traced back to the state when the remote operation occurred through the backtracking algorithm, and then the FLW algorithm obtained by the operation execution set is passed Considering the results of the backtracking process, the same set of executions can be obtained; The so-called Update operation execution algorithm refers to the Update operation of a remote user. After obtaining the execution set of the operation, the same execution result is obtained; the Update operation execution algorithm uses the Multi-version/Single-display strategy to handle all conflicting nodes. For the operations on all conflicting nodes, select the content of the operation with the largest TOrder function value to display, so as to obtain a unified display version; The so-called local state vector maintenance method is used to maintain the local state vector. The state vector records the number of operations executed from different sites. When a new operation is executed, the number of operations executed by the site is increased by one , and update the local state vector; The so-called broadcast method is to notify all other users of a local user operation and local state vector as the timestamp of the operation, so that other users know the status of the data copy that has been executed by the operation. 3. The consistency maintenance method according to claim 2, characterized in that the TOrder function specifies a total order relationship between operations, for two operations, the TOrder function provides the magnitude relationship of the two operations, and the TOrder function is transitive, and any two operations are comparable.

Images