CN100383741C - Consistency maintenance method for XML oriented mark retrace - Google Patents
Consistency maintenance method for XML oriented mark retrace Download PDFInfo
- Publication number
- CN100383741C CN100383741C CNB2006100264594A CN200610026459A CN100383741C CN 100383741 C CN100383741 C CN 100383741C CN B2006100264594 A CNB2006100264594 A CN B2006100264594A CN 200610026459 A CN200610026459 A CN 200610026459A CN 100383741 C CN100383741 C CN 100383741C
- Authority
- CN
- China
- Prior art keywords
- execution
- algorithm
- node
- local
- inverted index
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
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
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
0, 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
0, 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
。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
1And U
2, U
1And U
2Be concurrent operations, initial XML document is as shown below.The generation of operation and execution sequence are as shown in Figure 4.U
1Hope contains in child node inserts a new node " D ", U among the sub-tree of value " 3 "
2Wish 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
1For:
FOR $node?in/root/node，
$attr＝$node/attr
WHERE$attr＝″3″
UPDATE$node{
INSERT<value>D</value>
}
Wherein operate U
2For:
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
1Respectively " B " and " C " inserted a child node " D " respectively for the sub-tree of root at its local replica, but at SR
2, owing to carried out U
2, U
1Arrive 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
1During 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
2Operation, and operation U
2The 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
2Operation is revised, and revising type is Update, and this moment, Value was operation U
2Content, and the operation U
2Be operation U
1Concurrent 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
1State during generation is shown in the right part of Fig. 5.Obviously operate U
1Carry 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. consistency maintaining method towards the mark retrace of XML, it is characterized in that making up the consistency maintenance engine of an application program, the state vector maintaining method and the broadcasting method of FLW algorithm that collection obtains, Update operation execution algorithm, a this locality carried out in control algolithm, historical operation record maintenance algorithm, inverted index table maintenance algorithm, back-track algorithm, the operation that comprises program in this engine, 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.
2. consistency maintaining method according to claim 1 is characterized in that:
Said programmed control algorithm is an execution flow process to strange land user operation, 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;
Said historical operation record maintenance algorithm, 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;
Said inverted index table maintenance algorithm, 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, the ancestors between decision node, descendent relationship by the Label between them;
Said back-track algorithm, 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, then in inverted index table, make up a virtual node, and origin node is set to invalid, the state when back-track algorithm dates back to the inverted index table of XML data assigned operation and produces;
The FLW algorithm that collection obtains is carried out in said operation, is the Update operation for a strange land user, obtains 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 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;
Said Update operation execution algorithm is the Update operation for a strange land user, behind the execution collection that obtains operating, obtains identical execution result; 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;
The state vector maintaining method of said this locality, in order to safeguard local state vector, state vector has write down the quantity of carrying out from the operation of different websites, after a new operation is performed, just the operation number of executions with this website adds one, and upgrades local state vector;
Said broadcasting method is that the user of this locality operation and local state vector are notified to all other user as the timestamp of operating, and allows other user know the state of the data trnascription that this operation was carried out.
3. consistency maintaining method according to claim 2, the ordering relation of an operation room that it is characterized in that described TOrder functions specify, for two operations, the TOrder function provides the magnitude relationship of two operations, the TOrder function has transitivity, and any two operations are comparable.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB2006100264594A CN100383741C (en) | 2006-05-11 | 2006-05-11 | Consistency maintenance method for XML oriented mark retrace |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB2006100264594A CN100383741C (en) | 2006-05-11 | 2006-05-11 | Consistency maintenance method for XML oriented mark retrace |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1845076A CN1845076A (en) | 2006-10-11 |
| CN100383741C true CN100383741C (en) | 2008-04-23 |
Family
ID=37064004
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB2006100264594A Expired - Fee Related CN100383741C (en) | 2006-05-11 | 2006-05-11 | Consistency maintenance method for XML oriented mark retrace |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN100383741C (en) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101882078B (en) * | 2010-05-28 | 2013-01-16 | 浙江大学 | Inter-module real-time synchronization method based on internal memory data framework |
| CN103365852A (en) * | 2012-03-28 | 2013-10-23 | 天津书生软件技术有限公司 | Concurrency control method and system for document library systems |
| CN104573078A (en) * | 2015-01-27 | 2015-04-29 | 深圳市中兴移动通信有限公司 | Server and data storage applying method and device therefor |
| CN107295072B (en) * | 2017-06-13 | 2020-07-28 | 复旦大学 | Cache data consistency maintenance method based on private cloud |
| CN111190641B (en) * | 2020-01-23 | 2021-08-17 | 复旦大学 | API analysis-based Java third party library version unified recommendation method |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2000079428A2 (en) * | 1999-06-18 | 2000-12-28 | University College London | Method and apparatus for monitoring and maintaining the consistency of distributed documents |
| US20020049789A1 (en) * | 2000-05-27 | 2002-04-25 | Peter Frolich | Method for generating application specific input files |
| US20020133516A1 (en) * | 2000-12-22 | 2002-09-19 | International Business Machines Corporation | Method and apparatus for end-to-end content publishing system using XML with an object dependency graph |
| US20030200212A1 (en) * | 2002-04-23 | 2003-10-23 | International Business Machiness Corporation | Method, system, and program product for transaction management in a distributed content management application |
| US20050187983A1 (en) * | 2001-10-05 | 2005-08-25 | International Business Machines Corporation | Method of maintaining data consistency in a loose transaction model |
| CN1674583A (en) * | 2005-03-24 | 2005-09-28 | 北京北方烽火科技有限公司 | Method for realizing high-speed Le interface based on asynchronous multi-thread |
| US20050262443A1 (en) * | 2004-05-19 | 2005-11-24 | Eugene Sindambiwe | Word processing with artificial language validation |
-
2006
- 2006-05-11 CN CNB2006100264594A patent/CN100383741C/en not_active Expired - Fee Related
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2000079428A2 (en) * | 1999-06-18 | 2000-12-28 | University College London | Method and apparatus for monitoring and maintaining the consistency of distributed documents |
| US20020049789A1 (en) * | 2000-05-27 | 2002-04-25 | Peter Frolich | Method for generating application specific input files |
| US20020133516A1 (en) * | 2000-12-22 | 2002-09-19 | International Business Machines Corporation | Method and apparatus for end-to-end content publishing system using XML with an object dependency graph |
| US20050187983A1 (en) * | 2001-10-05 | 2005-08-25 | International Business Machines Corporation | Method of maintaining data consistency in a loose transaction model |
| US20030200212A1 (en) * | 2002-04-23 | 2003-10-23 | International Business Machiness Corporation | Method, system, and program product for transaction management in a distributed content management application |
| US20050262443A1 (en) * | 2004-05-19 | 2005-11-24 | Eugene Sindambiwe | Word processing with artificial language validation |
| CN1674583A (en) * | 2005-03-24 | 2005-09-28 | 北京北方烽火科技有限公司 | Method for realizing high-speed Le interface based on asynchronous multi-thread |
Non-Patent Citations (4)
| Title |
|---|
| XML与关系数据集成中的数据同步修改技术. 孙宏伟，张树生，周竞涛，王静，赵寒.西北工业大学学报，第22卷第3期. 2004 * |
| XML的并发加锁协议. 庞引明，谈子敬，汪卫.计算机研究与发展，第41卷第7期. 2004 * |
| 基于XML业务无关的分布式数据库数据同步策略. 龙欣，张旭，席大春，周福平.华中科技大学学报，第31卷第5期. 2003 * |
| 实时协作中基于版本序号的并发控制算法. 黄健斌，武波.计算机工程与应用，第14期. 2002 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN1845076A (en) | 2006-10-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Rosenman et al. | Multidisciplinary collaborative design in virtual environments | |
| US7673282B2 (en) | Enterprise information unification | |
| CN1992728B (en) | Systems and methods for facilitating group collaborations | |
| Kongdenfha et al. | Rapid development of spreadsheet-based web mashups | |
| CN100383741C (en) | Consistency maintenance method for XML oriented mark retrace | |
| US20090049025A1 (en) | System and method for harvesting service metadata from an architecture diagram into a metadata repository | |
| Schleipen et al. | The CAEX tool suite-User assistance for the use of standardized plant engineering data exchange | |
| Isakowitz | Hypermedia, information systems and organizations: A research agenda | |
| Koch | The collaborative multi-user editor project IRIS | |
| Dattolo et al. | Collaborative version control in an agent-based hypertext environment | |
| Zarzour et al. | srCE: a collaborative editing of scalable semantic stores on P2P networks | |
| Aoyama | Distributed concurrent development of software systems: An object-oriented process model | |
| CN1831776A (en) | Consistency maintemance method of marking backtrack | |
| Kleppmann | Thinking in events: from databases to distributed collaboration software | |
| Kim | Version management in computer-aided architectural design | |
| Kramer et al. | Beyond the Whiteboard: synchronous collaboration in shared object spaces | |
| Uehara et al. | Enterprise model-based software architecture with server component integration | |
| Kleppmann | Thinking in events | |
| Antunes et al. | Managing divergent information: enhancing document expressiveness | |
| Zhang | Research on Intelligent Management Model in Distribution Service System: Based on Collaboration FPS Management | |
| Metaxiotis | A framework for knowledge management in E-Government | |
| Spositto et al. | Check for Application Programming Interface Technology to Optimize the Exchange of Information Between Legal Systems | |
| Lin et al. | API design recommendations for facilitating conversion of single-user applications into collaborative applications | |
| Jarke | Experience-Based Knowledge Management | |
| Burrows | Planning, information technology and the post-industrial society |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20080423 Termination date: 20150511 |
|
| EXPY | Termination of patent right or utility model |