Method and system for processing documents through document history encapsulation

A computer-implemented system and method for processing a markup language document and its change history are provided. The method includes receiving first and second versions of the same target document into computer memory. One of the first and second versions of the target document is encapsulated within an encapsulating document. A change history corresponding to a difference between the first version and the second version of the target document is encoded. The change history is encapsulated within the encapsulating document. The encapsulated document can then be output. As each new version of the target document is created, the encapsulating document can be modified to reflect the changes, enabling prior versions of the target document which have been encapsulated to be extracted at any time.

BACKGROUND

The exemplary embodiment relates to a system and method for encoding and handling self-contained and incremental document history for documents encoded in a markup language such as Extensible Markup Language (XML).

XML is a widely used standard for encoding document information. For example, many word processing programs save documents in an XML format as a way of preserving the content and arrangement of the document. Additionally, XML documents (or XML files) may be passed between distinct software applications as a way of exchanging data in a universal format. These XML documents may change over time through the addition and deletion of information in the document. However, there is currently no universal way of keeping track of these changes within the document in a manner that allows any application or user to determine the history of changes in the document (“history”). Change history of an XML document may be useful for numerous reasons. Among other things, an application or user may wish to view a prior version of the document or merge a version of the document with another version of the same or a different document. Currently, such XML document management requires a content management system or database separate from the XML document itself. Models and operations pertaining to document change history are therefore hidden from view, and there exists no universal and reliable mechanism to allow for making this information manageable across diverse platforms. Additionally, many versioning systems are compatible and optimized only from the implementing application's point of view. Therefore, some basic universal functionality relating to the encoding and management of the incremental change history of an XML document within the XML document itself is of interest as XML documents become more prevalent within the user community.

BRIEF DESCRIPTION

In one aspect of the exemplary embodiment, a computer-implemented method for processing a markup language document is provided. The method includes receiving a first and second version of a target document into computer memory. Using a computer processor, either the first or second version of the target document is encapsulated within an encapsulating document. The method then encodes a change history corresponding to a difference between the first version and second version of the target document, and encapsulates the change history within the encapsulating document. The encapsulated document is output.

In another aspect, a storage medium containing, in a computer readable form, an encapsulating document is provided. The encapsulating document includes a version of a target document and an encoded change history corresponding to a difference between versions of the target document. The encoded change history includes at least one versioning point which includes a version difference expressed in a change description language.

In yet another aspect, a computer-based system for encoding a target document and its change history within an encapsulating document is provided. The system includes a computer processor and computer memory which stores an encapsulation module. The encapsulation module is configured to receive a first and a second version of a target document in computer memory and, using the computer processor, encapsulate one of the first and second versions of the target document within an encapsulating document. The encapsulation module is further configured to encode a change history corresponding to a difference between the first version and second version of the target document, encapsulate the change history within the encapsulating document, and output the encapsulating document.

DETAILED DESCRIPTION

Disclosed herein are a system and method for encoding and managing self-contained and incremental document history for markup language documents, which are referred to herein for convenience as XML documents.

The exemplary method and system encapsulate together an XML document (target XML document) and its change history. A target XML document's change history contains descriptions of one or more significant states (versioning points) a document adopted during its existence. This change history is encapsulated as a section within a single standalone XML document along with a version of the target XML document itself. Moreover, the exemplary method and system focuses on the coherence of this change history information which allows for the processing of the encapsulated change history within the XML document and retrieval of prior or subsequent versions. For example, the exemplary method and system include a change history section within the standalone XML document suited to capture and encapsulate document versioning information and to allow for operations that enable basic usage of such encapsulated data. Specifically, the change history section describes a set of transformations between versioning points that allow for navigation within the history of the target XML document and consistent extraction of document versions. The change history section also allows for the creation of new versioning points and branches, as well as the merging of existing version branches. Each of the above operations produces novel and consistent encapsulations of a version of a target XML document and its change history within the encapsulating XML document.

Characteristics of the change history data model include the use of a universal XML data structure and related transformations that allow for the abstraction of the change history from the underlying storage system and execution model. These characteristics favor long term preservation of XML documents, infrastructure and vendor independence, and open the way to interoperable processing of XML versioning information.

The exemplary system and method utilize a particular namespace in order to embed a target XML document (which may itself use any syntax and vocabulary) without any change content and tag/attribute set of the target XML document. The document change history is encoded using a specific vocabulary that captures change operations in a formal and universal way such that an XML diff-enabled processor can generate differences between document versions (version differences). An XML diff-enabled processor (“diff engine”) is any application or processor that computes differences between XML documents. The output from a diff engine is generally in the form of a change description language that describes, in a formalistic manner, the differences between any two documents. A “delta” (Δ), as used herein, is the difference between two document versions described in a change description language. Any of the several commercially or publicly available XML diff engines that can be adapted to generate formal and reliable deltas may be used in conjunction with the exemplary method and system.

With reference toFIG. 1, a target XML document2to be encapsulated is shown. The target XML document2may be any XML document using any XML namespace4. The content of the target XML document2includes all content including and between the first opening tag8and the last closing tag10.

FIG. 2illustrates an encapsulating XML document20that encapsulates the target XML document2as well as the change history22of the target XML document2. By “encapsulates,” it is meant that the target XML document2and its change history form a single standalone XML document. The change history references one or more versioning points28. Each versioning point28corresponds to a version of the same target XML document2which differs, in content, from that of an immediately prior or subsequent version. In the exemplary embodiment, the target XML document2is encapsulated within the body24of the encapsulating document20. In alternate embodiments, the target XML document2may be encapsulated within any other part or section of the encapsulating document20. The body24of the encapsulating document20includes an attribute26that gives a focused version (state)27embodied by the target XML document2. The attribute26acts as a consistent link between the focused state of the target document2and a versioning point28in the change history22. In the document illustrated byFIG. 2, the focused version27provided by attribute26is version0(“v0”). The body24is consistently and explicitly related to the version27in the change history22for the target XML document2. The focused version27is not necessarily the most recent version for the document2. For example, a change history22for a target XML document2may contain versioning points v0, v1, and v2. The focused version27for the document2may be v1, even though the latest versioning point28available in the change history22is v2. Version differences and versioning points thus represent changes between the document as it existed in the focused version27and corresponding prior or subsequent versions.

Data Model

The encapsulating XML document20is represented logically as a tree of interconnected nodes:
x-version[x-bodyvi[d],x-history[v0. . . vi. . . vn-1]]  (1)
The x-bodyvinode contains a version viof target XML document d, and the x-history node begins a subtree containing a change history that includes versioning points v0to vn-1. The full syntax of the encapsulating document20may be provided through a RelaxNG Schema (see Appendices A and B for an example), or through other suitable markup language mechanism.

FIG. 3illustrates the logical tree structure22afor the change history22of a target XML document2.FIG. 3shows a directed acyclic graph22awith interrelated nodes30. Each node30in the graph22arepresents a distinct version of the target XML document2described in the change history22of the encapsulating XML document20. That is to say, each node30of the graph22ais a versioning point, i.e. a particular significant state that the target XML document2has reached during its lifetime which has been recorded as a version. The significance of any versioning point with respect to the document lifecycle may be application dependent. For instance, certain applications may determine that a given state of a target XML document is significant when an agent, at some point in the document lifecycle, decides that the given state is significant. Other applications may determine significant states based on the passage of time or other factors. Optionally, supplemental information may be attached to the versioning points, such as user meta-information, universal date/time of version creation, optimization data such as a hash-code or digest number.

With respect to the directed graph22aofFIG. 3, arcs (edges)32that connect the nodes30represent version differences (deltas or Δ's)34that enumerate changes between the nodes (versioning points). Δ's34are combinations of basic operations (δ) on the target XML document tree, such as the deletion and/or insertion of subtrees. The combination of arcs32and version differences Δ's34model the transformations that occur from one versioning point30to another versioning point30. Thus, the arcs32are oriented since they each pair one earlier versioning point with a later (in time) versioning point, differentiated by the corresponding version difference Δ34. For example, in the exemplary tree illustrated, a first version V0of a target document is created by an author. This is is encapsulated together with its change history, which at this stage is empty, since there are no other versions encapsulated. Later, a second version V1of the same target document is encapsulated, which differs from the first version by a first set of changes (Δ), such as additions or deletions to the text content of the first version of the target document. Subsequently, a third version V2of the same target document is created by modifications to the second version and is encapsulated. Here, Δ represents the changes between V1and V2. Thereafter, the target document is worked on by two different authors, each creating a new version denoted V2.1and V2.2, respectively, which are encapsulated in the same encapsulating document (or in two separate encapsulating documents). The second author makes some further changes, resulting in V2.2.2, which is encapsulated. Later, he decides to merge this version with V2, which results in V3, which is encapsulated in the encapsulation document. Further changes to this merged document result in V4. All of these versions can be encapsulated in a single encapsulating document from which they can later be extracted, producing an output target document which is in the same form as it was at the time it was encapsulated.

Diff Engine

The exemplary system may utilize a diff engine that operates to formalize the changes between versions of a target document. The signature for the diff engine can be represented as:
diff(config,d,d′)→Δ  (2)
where config is a set of parameters used to configure the diff engine (e.g., filter to apply, mode commutative/non-commutative, algorithm, etc), d is a first document, and d′ is a second document. In the exemplary embodiment, d and d′ are different versions of the same target XML document. The output of the diff engine (Δ) represents a set of basic operations (δ) described in a change description language. The basic operations6are selected from a predetermined set of basic operations available to the diff engine. The output has the following properties:

δ denotes a basic operation that modifies an XML document. Examples of δ include the insert, insert-attr, and delete operations shown above, and are discussed in more detail below. A series of basic operations δ with commutative properties are denoted as a “commutative snapshot.” A commutative snapshot is a series of basic operations δ performed on an XML tree (such as a version of the target XML document) that, when performed in any order, consistently produce the same resultant XML tree. As indicated above, Δ can represent a null (empty) set (i.e., no change between the versions), a commutative snapshot, or a sequence of commutative snapshots. It will be appreciated that, in general, not all versions have an empty set as the Δ.

The basic operations δ specify paths, denoted p or pp, to designate the tree location where the modification should be applied. The paths can be described by the following grammar:
p::=pp|pp/@nm
pp::=i/pp|i(5)
where i is a positive integer and nm is an attribute name. The paths are interpreted relative to the root of the encapsulating document (i.e., the x-body element), and are easily translated to XPath expressions. XPath expressions are expressions formed in a query language that are used to select nodes from an XML document. For example, the path p 1/2/1 translates into the XPath expression *[1]/*[2]/*8 1], and path p 1/3/@id into *[1]/*[3]/@id. In these examples, the *[n] notation refers to a node level within a document and the @id notation refers to an element attribute. The basic operations listed above all require a path pp as an operand in order to perform their particular function. The insert and insert-attr operations additionally require a tree A as an operand. The tree A may be a single XML node such as a <p> (paragraph) node or a tree containing multiple nodes (such as a <p> element containing multiple <p> children). Specifically, the insert operation receives two parameters, a path pp and tree A, and inserts the tree A at location pp in the target XML document. The insert-attr operation performs in a manner similar to the insert operation, except that the tree A is inserted in the target XML document at the path designated by pp and the attribute value of nm. In order for the target XML document to be considered well-formed, the tree A must be a leaf within the target XML document. The delete operation simply deletes whatever tree is found at path pp.

In order to increase the generality of basic operations δ capable of being processed by the exemplary method and system, the following supplemental operations extend the existing basic operations δ through definitions based on the fundamental δ operations described above:
d>{move(pp1,pp2)}>d′<==>
d>{insert(pp2,get(d,pp1))delete(pp1)}d′(6)
d>{copy(pp1,pp2)}>d′<==>
d>{insert(pp2,get(d,pp1))}>d′(7)
d>{replace(pp1,A)}>d′<==>
d>{insert(pp1,A)delete(pp1⊕§pp1)}>d′(8)
Thus, the move operation simply inserts the tree at path pp1at path pp2and deletes the tree at path pp1. The copy operation inserts tree pp1at the path designated by pp2, and the replace operation inserts tree A at path pp1and then deletes the tree previously at path pp1in original document d.

FIG. 4illustrates the path expressions (i.e., expressions of tree locations within an XML document) as applied by the exemplary method and system to an encapsulating document20. In other words, paths provide location information to the basic operations so that the operations may be performed on the correct operands. The x-body element40is considered the root node for the purposes of path expressions since it is the innermost node that encapsulates the target XML document2. Paths within the target XML document2are navigated with respect to the root node40. Each number in the path denotes which child of the parent is chosen. Each child node becomes the parent for the next level in the path. InFIG. 4, the first node level down from the root node40is denoted, for illustration purposes, by a circle containing the respective child number. The second node level is denoted by squares containing child node numbers and the third node level is denoted by stars containing child node numbers. For example, the path “1/2/2” points to the <p> element42since the <p> element42is within the first child of the root node (i.e., the <html> element), second child of the <html> element (i.e., the <body> element) and the second child of the <body> element.

Encoding Version Changes (Deltas) in XML

FIG. 4also illustrates the encoding of the insert and delete basic operations δ described above. Basic operations δ are encoded within version difference Δ elements54,56. For example, XML element52is an encoding of the delete basic operation and is contained within version difference (delta) element54. In this case, the delete operation operand is the path “1/1/1” which means that the node located at path 1/1/1 will be deleted. InFIG. 4, the node that would be deleted is the <p> element42. XML element44is an encoding of the insert operation (contained within delta element56) which will insert the <p> element46at path “1/2/3”. InFIG. 4, the <p> element46would be inserted after the <p> element42.

The encapsulating document20shown inFIG. 4contains three separate versioning points58,60and62, representing versions v0, v1and v2of target XML document2, respectively. The encapsulating document20inFIG. 4is “focused” on version v1of the target XML document2. The focused version27can be found in the x-body tag40of the encapsulating document20. All target XML documents within encapsulating documents are focused on a single respective version. Focusing a target XML document refers to encoding the target XML document2within an encapsulating document20with respect to the focused version.

Versioning points58,60,62within an encapsulating document20are represented through the use of a dedicated XML element (e.g. <version>) associated with an id attribute that uniquely identifies the version. Each version element may contain from zero to multiple delta elements. InFIG. 4, version element60has an id attribute of “v1” and contains delta elements54and56. This denotes that the deltas contained within version element60pertain to version1of the target XML document2. Version elements58and62contain no delta elements. A naming scheme of the form “v0” . . . “v3” may be used to denote versions of the target XML document. Names for diverging branches use a dot, e.g. “v1.1”, “v1.2”. However, any version naming scheme may be implemented.

The delta elements54,56capture the transition from the focused versioning point27to another versioning point. This information is conveyed by an attribute (e.g., “fwd” for forward links from an earlier version to a later version and “bwd” for backward links) contained in the version element58,60,62. A forward link links a prior version to a later version, and a backward link links a later version to a prior version. As noted above, each Δ contains at least one non order-significant sequence of δ operations, or “snapshot”. Sequences of delta elements with the same orientation correspond to the Δ1; . . . ; Δksyntactic form.

Each basic operation δ is described using a dedicated element name according to its semantics (insert, insert-attr, delete, move, copy, etc). The path information may be concisely encoded, e.g. through an “ipath” attribute in the delta element. Copies of subtrees may be expressed through a “copy” attribute attached to the delta element. In that case, the latter copy attribute is an ipath with respect to the focused versioning point.

Since basic operations δ all require at least a path operand, basic operations δ may be written as δpto express that a basic operation δ is realized on a path p. Each basic operation δ belonging to a snapshot complies with a structural constraint that ensures orthogonality such that the snapshot is indeed commutative. In order to ensure orthogonality, it is assumed that both paths in every pair of δpdo not designate sibling trees, and that one path does not designate a sibling tree of the parent node designated by the other path. This assumption is in place to avoid conflicting δp's.

Version differences Δ can be encoded in a document change history in multiple ways. The version differences Δ can be encoded with respect to the focused version of the target XML document, or they can be encoded in a “linear” mode. A change history with version differences Δ encoded in linear mode chronologically describes each incremental change between versions starting at the earliest version and ending with the latest version. In a linear mode encoding, all the delta elements only have “fwd” encodings and no “bwd” encodings since each delta is encoded with respect to the next version chronologically. For example, the delta change elements54and56ofFIG. 4show the changes that need to be made to change from version v1to v0and v2, respectively. The change history ofFIG. 5has encoded the change history in linear mode. The Δ's for v066provide instructions for changing the target XML document2from v0to v1, and the version element v168contains Δ's describing how to change from v1to v2. There are no Δ's contained in the v2version element70since there is no subsequent version v3. Note that the change history shown inFIG. 5contains some content redundancy since the target XML document2is focused on v1which contains <p> element72. The redundancy occurs because of the linear mode requiring that version element66include the insertion of <p> element74in order to describe how to change from v0to v1.

To help remedy this redundancy,FIG. 6illustrates the use of the copy operation80that conveys the same information within the Δ element without requiring that the <p> element be copied word for word.

Properties of Version Differences

The output from the diff engine describes the changes that occur between versions within an XML tree. The changes are described in a change description language such that the changes can be performed on the original XML document to produce the changed XML document. The analytical transformation of document d into a changed document d′ is noted by applying Δ as follows:
d>Δ>d′(9)

In other words, the description (6) above is a logical assertion saying that a well-formed document d is changed into a well-formed document d′ after the application of the well-formed Δ operation. A Δ operation is well-formed if it adheres to the properties listed below.

Formally, for any subtree A, path p, document d and d′, version differences Δiand δi, the document transformations can have the following abstract properties:

The definitions of the (a-ins) and (a-ins-@) properties make use of function get, which extracts the subtree rooted at a given location p. The invar property used in (a-ins), (a-ins-@) and (a-del) expresses that the subtree defined by the operand path pp is not modified by the Δ operation performed on original document d. Mathematically, the invar property is defined as:

The ⊕, and §functions used in the properties above are inductively defined. Specifically, the path addition function ⊕ is defined over pure paths (noted pp), is commutative, and operates on paths of any depth. In other words, the path addition function ⊕ combines two given paths into a single path for evaluation. Mathematically, the path addition function ⊕ is defined as follows:
i/pp⊕j/pp′=(i+j)/(pp⊕pp′)  (10)
i/pp⊕j=(i+j)/pp(11)
i⊕j/pp′=(i+j)/pp′(12)
i⊕j=(i+j)  (13)

The fingerprint extraction function §calculates the depth level of a given path. Mathematically, the fingerprint extraction function § is defined as follows:
§(i/pp)=0/§(pp)  (14)
§(i)=1  (15)
Thus, §(1/2/3)=0/0/1 and 1/2/3⊕ §(1/2/3)=1/2/4.

The (a-seq) property states that there exists an intermediate document d″ such that when Δ1is applied to original document d, d″ is produced, and when Δ2is applied to the intermediate document d″, then the changed document d′ is produced.

The (a-snap) property states that when a snapshot (i.e., a series of basic operations δ) is applied to an original document d, then changed document d′ is produced, no matter what order the basic operations δ were performed. This supports the notion of a commutative property. In other words, all deltas Δ (which may comprise one or more snapshots) are pair wise orthogonal.

The (a-void) property states that if a version difference Δ containing no changes is applied to original document d, then the changed document d′ will be the same as original document d,

The (a-ins) property states that after an insert operation is performed on original document d, (by inserting tree A at path pp), then the changed document d′ will contain the new tree A at path pp. The (a-ins-@) property is the same as the (a-ins) property, except that it applies when the insert-attr operation inserts tree A in original document d at the path with the attribute value denoted by operand pp/@nm.

The (a-del) property states that after the delete operation is performed on original document d at path pp, the tree previously at path pp in d will no longer exist in changed document d′.

The (a-del-@) property states that after a delete operation is performed on original document d (by deleting the tree at path pp), the get function will return a null value for the changed document d′ at path pp/@nm.

Inversion of Version Differences and Snapshots

An inverted delta (Δ) describes the changes that will restore an operand (i.e., a target XML document) to a prior state before a change was made. Inverted version differences Δ's are used to increase operational optimization in the exemplary method and system. The inversion of a version difference Δ requires knowing the original operand on which changes will be applied.

The inversion function can be inductively defined by the following:

Delta inversion is characterized by the following property:
d>Δ>d′===>d′>invert(d,Δ)>d(22)

The inversion of version differences Δ provides useful functionality which allows for optimal navigation within an XML tree. Moreover, it allows for a more compact representation of changes, especially when successive versions represent documents which contain only incremental changes, which is common in a standard document life-cycle.

Indeed, in such cases, subgraphs of the form:
vi→insert(p,A)vj→insert(p′B)vk(23)
can be rewritten using delta inversion as:
vi←delete(p)vj←delete(p′)vk(24)

In other words, description (23) describes changing from version i to version j to version k using the insert operations. Description (24) uses an inverted Δ to illustrate going from version k to version j to version i by working backwards from version k. This allows the system to move efficiently between versions without having to recalculate a very long list of changes. Thus, one benefit of using inverted Δ's is that subtrees A and B are redundantly stored: once inside the history and once inside the current instance itself. In case the focus is set to a non-terminal versioning point (e.g. version j in the example above), deltas and inverted deltas may be combined to form:
vi←delete(p)vj→insert(p′,B)vk(25)
which is still quite meaningful as the subtree B is only stored once inside the delta (indeed, the target XML document is conformant to vjand does not comprise the B subtree.

Note that inversion of operands of a diff operation also lead to reversed deltas (or a delta operationally equivalent to reversed delta):
diff(c,d,d′)=Δ===>diff(c,d′,d)=invert(d,Δ)  (26)
Fundamental Operations Over Encapsulated Documents

The encapsulation of change history data for a target XML document within an encapsulating XML document allows for multiple management operations to be performed. The operations performed by the exemplary method and system allow for the creation of an encapsulating document, the versioning of a modified target XML document, the merging of two separate versions of a target XML document, the focusing of a target XML document on a specified version, and the extraction of a target XML document from an encapsulating document.

FIG. 7illustrates an exemplary system100for encapsulating document history within an ecapsulating XML document20implemented in a computer device. The system100includes an input device102, for receiving a target XML document2to be encapsulated. The system100may also be configured to receive a previously generated encapsulating document20′ containing a target XML document and change history, and/or a user-selected version number106, or other identifier for a previously encapsulated version of the target document, that is used for certain operations. Prior to inputting, the target XML document2, encapsulating document20′ and version number106may be stored in any suitable tangible media such as a ROM or RAM drive or may be input into the system100in the form of a carrier wave, e.g., via the Internet. Alternatively, the target XML document2, encapsulating document20′ and the version number106may be generated within the system100, itself. The input device102may include a modem link, a wired or wireless connection, USB port, floppy or hard disk receiver, or the like and may be separated or combined with other components of the system100.

The system100includes data memory104for storing the target XML document2and the version number106while the document2is being processed. Main memory108of the system100stores an encapsulation module110, versioning module112, merging module114, focusing module116, extraction module118, and diff engine120. Outputs from modules110,112,114,116,118,120may be stored in memories104,108or output via an output device124to a client terminal40, optionally through a network132such as the internet.

The encapsulation module110receives as input the target XML document2via the input device102, and encapsulates the target XML document2within a newly created encapsulating document20. The encapsulation module110then outputs the encapsulating document20via output device124, or stores it in memory104. The versioning module112receives as input an encapsulating document20or20′ and a modified target XML document2′ (which may have been created by a user through modifications to target XML document2). The versioning module112creates a versioning point within the input encapsulating document20with the assistance of the diff engine120. The versioning module112then outputs the modified encapsulating document20via output device124, or stores it in memory104. The merging module114receives as input an encapsulating document20(or20′) and a version number or other user-selected identifier106. The merging module114merges the target XML document within the encapsulating document20with a versioning point identified by the input version number106. The merging module114then encapsulates and outputs the merged target XML document within an encapsulating document20for output. The focusing module116receives as input an encapsulating document20(or20′) and a selected version number106. The focusing module116then re-encodes the focused encapsulating document20such that the target XML document and history contained within the encapsulating document reflect the version state indicated by the input version number106. The focusing module116then outputs the re-encoded encapsulating document20. The extraction module118receives as input an encapsulating document20(or20′) and extracts the encapsulated target XML document2from within the encapsulating document20. The extraction module118then outputs the extracted target XML document126.

The encapsulation module110, versioning module112, merging module114, focusing module116, extraction module118, and diff engine120may be implemented as hardware or a combination of hardware and software thereof. In the exemplary embodiment, the components110,112,114,116,118,120comprise software instructions stored in main memory108, which are executed by a computer processor128. The processor128, such as the computer's CPU, may control the overall operation of the computer system100by execution of processing instructions stored in memory108. Components102,104,108,110,112,114,116,118,120,124,128may be connected by a data control bus130. As will be appreciated, system100may include fewer components. For example, the merging and focusing modules114,116may be omitted.

As will be appreciated, the document history encapsulation and management system100may comprise one or more computing devices, such as a personal computer, PDA, laptop computer, server computer, or combination thereof. Memories104,108may be integral or separate and may represent any type of computer readable medium such as random access memory (RAM), read only memory (ROM), magnetic disk or tape, optical disk, flash memory, or holographic memory. In one embodiment, the memories104,108comprise a combination of random access memory and read only memory. In some embodiments, the processor128and memory104and/or108may be combined in a single chip.

FIG. 8illustrates an overall document processing method which may be performed with system100. The method may include some or all of the following processing steps A, B, C, D, and E. As described inFIG. 8, step A encapsulates an original version of a target XML document2into an encapsulating document20. This step may be performed by the encapsulation module110. Step B performs a versioning operation by modifying the encapsulating document20to reflect additional version(s)2′ of the target XML document2. This step may be performed by the versioning module112. Step C performs a merging operation that merges two or more versions of the target XML document2within an encapsulating document20into a new version. The new version of the target XML document2is then encoded into the encapsulating document20. This step may be performed by the merging module114of system100. Step D performs a focusing operation that transforms the target XML document2within an encapsulating document20to a version specified by an input version number. This step may be performed by the focusing module116of system100. Step E performs an extraction operation that extracts and outputs the focused version of the target XML document2from within the encapsulating document20. This step may be performed by the extraction module118.

Method for Creating an XML Document History (Step A)

With reference toFIG. 9, an exemplary method for encapsulating a target XML document2is illustrated. The method may employ the system100illustrated inFIG. 7. It is to be appreciated that the exemplary method may include fewer, more, or different steps from those shown and need not proceed in the order illustrated. The method illustrated inFIG. 9and all subsequent methods disclosed may be implemented in a computer program product that may be executed on a computer. The computer program product may be a tangible computer-readable recording medium on which a control program is recorded, or may be a transmittable carrier wave in which the control program is embodied as a data signal. The illustrated methods may be entirely automated or may include some user input, as noted herein.

As a general overview, the encapsulation operation can be represented by the following signature:
create-history(d)→x-version[x-bodyv0[d],x-history[v0]]  (27)

where d is a target XML document2. The signature reflects that target XML document d is encapsulated inside the <x-body> element (as shown inFIG. 2) of the encapsulating document20, and that an initial versioning point v0is created inside the <x-history> element. The link that relates the embedded target XML document with the consistent versioning point is inserted in the x-body subtree, as illustrated by code27(FIG. 2).

The method begins at step S2. At step S4, a version of target XML document2is received into data memory104.

At step S6, an initial version number is assigned to the target XML document2, as shown by26(FIG. 2). In the exemplary method presented herein, the initial version of a document is “v0”, but any other version numbering system may be used.

At step S8, an initial change history element22(FIG. 2) is created. The initial history22will contain only a versioning point for v028, since v0is the only version that exists and no changes have been made to the target XML document2.

At step S10, the original version of the target XML document2and initial change history22(FIG. 2) are encapsulated within a new encapsulating document20. In one alternative embodiment, instead of encoding the entire target XML document, an inclusion link or external reference is used in lieu of encoding the entire target XML document. For instance, inFIG. 2, the original version of target XML document2may be replaced by an URL or other link to a document or file containing the target XML document.

At step S12, the encapsulating document20is output to memory104, or to another output device such as client terminal140via the output device124.

The method ends at step S14.

With reference toFIG. 10, the encapsulation method ofFIG. 9is illustrated graphically. Notably, the original version of target XML document2is input into the document encapsulation module110which produces an encapsulating document20containing both the original version of target XML document2, version history22and a link to the currently focused version27embodied by the target XML document2.

Method for Versioning a Modified Target Document (Step B)

With reference toFIGS. 11 and 12, an exemplary method for versioning a modified target XML document2′ is illustrated. This may be performed when an encapsulating document20(or20′) has already been generated and the original target document2has been modified to create a new version2′. This method may employ the system100illustrated inFIG. 7.

As a general overview,FIG. 11illustrates the versioning method in a graphical manner. The versioning method requires two operands: an encapsulating document20(e.g., as created at S10) and a modified variant (new version) of the target XML document2′ which is to be considered as a novel versioning point. The output of the versioning method is a modified encapsulating document20including a new versioning point60, a consistent link in the form of code26indicating which version of the target XML document2is encoded, and a transition from the previous versioning point to the new one. The resulting target XML document2and consistent link26may correspond to a version of the target XML document2that is not the latest version (i.e., viinstead of vi+1as shown). In this case, only the change history22would be altered by the versioning method. This transition (Δ) encompasses the basic operations computed by the diff engine120. The versioning operation may be represented by the following signature:
create-version(x-version[x-bodyvi[d],x-history[vi],d′)→x-version[x-bodyvj[d],x-history[vi→Δvj]] with diff(c,d,d′)=Δ  (28)

where d is a target XML document, viis the version62of the input target XML document2, and vjis the new versioning point27, c is a set of parameters used to configure the diff engine, d is the original target XML document2, and d′ is a modified target XML document2′ (i.e., a new version of the original document2).

With reference toFIG. 12, the method begins at step S20. At step S22, an encapsulating document20, containing a first version of target XML document2, and a modified version of target XML document2are received into data memory104, via input device102(if not already stored in memory104,108).

At step S24, the diff engine120computes basic operations δ between the original version (e.g., v0) of the target XML document2within the encapsulating document20and the modified version (e.g., v1) of the target XML document2′. In the exemplary method, the previous version number62is increased by one (i.e., from v0to v1) to create the new version number26.

At step S30, the calculated basic operations δ for the new target XML document are encoded into the history22of the modified encapsulating document20with respect to the new version number26.

At step S32, the new modified encapsulating document20is output to memory104, or to another output device such as client terminal140via the output device124.

The method ends at S34.

Method for Merging Two Versions of a Target XML Document (Step C)

With reference toFIGS. 13 and 14, an exemplary method for merging a modified target XML document2′ is illustrated. This method may employ the system100illustrated inFIG. 7.

As a general overview,FIG. 13illustrates the merging method in a graphical manner. The merging operation requires two operands: the encapsulating document20containing a target XML document2and a version number106that is part of the version history22contained in the encapsulating document20. The merging module114implements a merging algorithm that creates a novel versioning point26and two transitions (version differences Δ) that relate the two original versioning points62,106to the new one26. The object is to perform a maximum preserving merge (no deletion in the respective version differences). However, in the event that merging conflicts arise, one aspect of the exemplary method handles conflicts through the use of a dedicated annotation inside the target XML document. This annotation may be based on a foreign namespace which does not conflict with namespaces used by target XML document. The merging operation has the following abstract signature:
merge(x-version[x-bodyvi[d],x-history[vi]),vj→x-version[x-bodyvk[d′],x-history[vi→Δivk,vj→Δjvk]] withdvi>Δi>d′ anddvj>Δj>d′(29)

where d is the target XML document2, viis the focused version2′ of the target XML document, vjis the input version number106to merge with version vi, d′ is the merged target XML document, and vkis the new merged version60of the target XML document2′. Basically, the merge creates a new version vkwith a set of deltas (Δiand Δj) such that if Δiis applied to the target XML document focused on version viand Δjis applied to version vjof the target XML document, then the merged document version vkis produced in both cases.

With reference toFIG. 14, the method begins at step S40. At step S42, an encapsulating document20containing a versioned target XML document2and corresponding change history22, as well as a version number106are input into memory104via input device102(if not already created and/or stored in memory104,108). Version number106may be selected by a user, e.g. via client terminal140(FIG. 7).

At step S44, the merging module114extracts the focused version62(FIG. 13) of target XML document2from the encapsulating document20and stores it in memory104(FIG. 7). The merging module114may utilize the extraction module118to perform this step.

At step S46, the merging module114focuses the encapsulating document20onto the version corresponding to input version number106. This step provides for easier extraction of the version of the target document2corresponding to the input version number106. As explained below, once the newly focused version (corresponding to the input version number106) is extracted, it is easily merged with the previously extracted version62of the target XML document2. The merging module114may utilize the focusing module116for this step.

At step S48, the merging module114extracts the focused version of target XML document2(which is focused on the input version number106) from the encapsulating document20and stores this version of target XML document2in memory. The merging module114may utilize the extraction module118to perform this step.

At step S50, the merging module114creates a new version of target XML document2by merging the two extracted target XML document versions (one version corresponding to the input version number106and the other version corresponding to the previously focused version number62) into a new target XML document2. Any merging algorithm which is capable of merging XML document trees may be used. The merging module114also creates a new version number26that will be used for the versioning point in the change history60.

At step S52, the merging module114replaces the target XML document2in the encapsulating document20with the merged target XML document2′, to form a new encapsulating document20.

At step S54, the merging module114re-encodes the versioning points in the encapsulating document20change history60relative to the new version number26created in step S50. As discussed above, the previous versioning points62,106include new deltas which will allow transformation from the previous versioning points62,106to the new versioning point26. Optionally, the new versioning point26may contain deltas to allow for transformation backwards to the previous versioning points62,106.

At step S56, the newly modified encapsulating document20is output to memory104, or to another output device such as client terminal140via the output device124.

The method ends at step S58.

Method for Focusing an Encapsulating Document to a Specified Version of a Target XML Document (Step D)

With reference toFIGS. 15 and 16, an exemplary method for focusing an encapsulated target XML document2to an input version106number is illustrated. This method may employ the system100illustrated inFIG. 7.

As a general overview,FIG. 15illustrates the focusing method in a graphical manner. The focusing operation allows for the modification of a target XML document2embedded in an encapsulating document20in order to be compliant with a given version106stored in the document history22. This involves applying the appropriate version differences Δ to the target XML document2that connect the current versioning point vi62to the input versioning point vj106. The focusing operation has the following abstract signature:
focus(x-version[x-bodyvi[d],x-history[vi]),vj)→x-version[x-bodyvj[d′],x-history[vj]] withvi→Δi. . . →Δjvjandd>Δ; . . . ;Δj>d′.(30)

where d is the target XML document2, viis the originally focused version62of the target XML document2, vjis the input version number106on which to focus, and d′ is the focused target document corresponding to focused version vj. Specifically, the focus operation finds and applies the set of deltas (Δito Δj) that will transform the target XML document2from version vito version vj. Note that the set of deltas may contain deltas of the form vn←Δnvmwhich requires the computation of one or more inverse deltas.

With reference toFIG. 16, the method begins at step S70. At step S72, an encapsulating document20containing a target XML document2focused on version vi62and a change history22, as well as a version number vj106are input into memory104via input device102(if not already stored in memory104,108)

At step S74, the focusing module116applies the appropriate deltas contained within the document change history22to the target XML document2such that the target XML document2is in the state corresponding to the input version number106. For example, with reference toFIG. 4, the current version link26is v1. If the input version number106is “v2”, then the focusing module116would apply delta56to the target XML document2since delta56will transform the target XML document2from v1to v2. At step S76, the focusing module116re-encodes the versioning points in the document change history60relative to the newly focused target XML document2version26. For example, with respect toFIG. 4, once the target XML document2is focused to v2, versioning point v262may have delta elements added to transition “bwd” (backward) to v1. Many delta encodings are possible, and may depend on the diff engine120used to encode the encapsulating document20originally. For example, in one aspect of the exemplary method and system, the diff engine output is normalized to condense a set of possibly many equivalent deltas to a unique reference delta that expresses the same resulting target XML document.

At step S78, the focusing module116sets the focused version point (i.e., the version link)26to the input version number106so that the focused target XML document2is directly tied to a versioning point in the change history20.

At step S80, the focusing module116outputs the encapsulating document20containing the focused target XML document2and re-encoded change history60to memory104, or to another output device such as client terminal140via the output device124.

The method ends at step S82.

Method for Extracting a Target XML Document from within an Encapsulating Document (Step E)

With reference toFIGS. 17 and 18, an exemplary method for extracting a target XML document from an encapsulating document is illustrated. This method may employ the system100illustrated inFIG. 7.

As a general overview,FIG. 17illustrates the extraction method in a graphical manner. The extraction operation requires only one operand: the encapsulating document20containing the target XML document2to be extracted. The method outputs an extracted target XML document2without any of the encapsulating information. This method is useful for updating or changing a target XML document2embedded within an encapsulating document20. The extraction operation has the following abstract signature:
extract(x-version(bodyvi[d],x-history[vi]))→d(31)

where “x-version(bodyvi[d], x-history[vi])” is the encapsulating document20, d is the target XML document, and viis the currently focused version62of the encapsulating document20.

With respect toFIG. 18, the method begins at step S90. At step S92, an encapsulating document20containing a target XML document2is received into memory104via input device102.

At step S94, the extraction module118isolates and extracts the target XML document2from the encapsulating document20. This can be performed by any XML parser capable of extracting nodes and/or subtrees from an XML document.

At step S96, the extraction module118outputs the extracted target XML document2to memory104, or to another output device such as client terminal140via the output device124(if not already stored in memory104,108).

The method ends at step S98.