Propogating updates efficiently in hierarchically structured date

• US 6,377,957 B1
• Filed: 12/29/1998
• Issued: 04/23/2002
• Est. Priority Date: 12/29/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Jeyaraman, Thulasiraman
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/222,088
• Time in Patent Office: 1,211 Days
• Field of Search: 707/200, 707/202, 707/103, 707/500, 707/203, 707/204
• US Class Current: 707/625
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

One embodiment of the present invention provides a system that efficiently propagates changes in hierarchically organized data to remotely cached copies of the data. The system operates by receiving an access to the data at a client. In response to this access, the system determines if the client contains a copy of the data. If so, the system sends a request to a server for an update to the copy. The server receives the request and determines differences between the current version of the data at the server and an older copy of the data at the client, which the server has stored locally. These differences are used to construct an update for the copy of the data, which may include node insertion and node deletion operations for hierarchically organized nodes in the data. Next, the update is sent to the client where it is applied to the copy of the data to produce an updated copy of the data. Finally, the original access is allowed to proceed on the updated copy of the data. According to one aspect of the present invention, the act of determining differences, and the act of using the differences to construct the update both take place during a single pass through the data. According to another aspect of the present invention, the update for the copy of the data may include node copy, node move, node collapse and node splitting operations.

Claims

1. A method for propagating changes in data that is hierarchically organized to a copy of the data, comprising:

receiving, at a client, a request to access to the data;

determining if the client contains the copy of the data;

if the client contains the copy, sending a request to a server for an update to the copy of the data;

after the request is sent to the server, receiving from the server an update for the copy of the data, wherein the update may include node insertion and node deletion operations for hierarchically organized nodes in the data;

applying the update to the copy of the data to produce an updated copy of the data; and

allowing the requested access to the data to proceed.

2. The method of claim 1, wherein the update additionally includes at least one from the group of, node move, node collapse, node split and node update operations.

3. The method of claim 1, wherein the act of sending the request to the server includes sending an indicator of when the copy of the data was last updated.

4. The method of claim 1, wherein the update includes a Multipurpose Internet Mail Extensions (MIME) content type specifying that the update contains updating operations for hierarchically organized data.

5. The method of claim 1, wherein the act of applying the update to the copy of the data takes place in semiconductor memory, whereby the update is able to proceed rapidly in the absence of time-consuming I/O operations.

6. A method for propagating changes in data that is hierarchically organized to a copy of the data, comprising:

receiving, at a server, a request for an update for the copy of the data located on a client;

in response to the request, determining differences between the data and the copy of the data;

using the differences to construct the update for the copy of the data, wherein the update may include node insertion and node deletion operations for hierarchically organized nodes; and

sending the update from the server to the client.

7. The method of claim 6, wherein the acts of determining the differences and constructing the update take place during a single pass through the data.

8. The method of claim 6, wherein the update additionally includes at least one from the group of, node move, node collapse, node split and node update operations.

9. The method of claim 6, wherein:

the act of sending the request to the server includes sending an indicator of when the copy of the data was last updated; and

the act of determining differences includes examining the indicator to determine how the data on the server has changed since the copy of the data was last updated.

10. The method of claim 6, wherein the update includes a Multipurpose Internet Mail Extensions (MIME) content type specifying that the update contains updating operations for hierarchically organized data.

11. The method of claim 6, wherein the update may include a node copy operation that makes an identical copy of a node as well as any subtree of the node that may exist.

12. The method of claim 6, wherein the update may include a node move operation that moves a node to another location in a tree of hierarchically organized nodes.

13. The method of claim 6, wherein the update may include a node split operation that splits a node into two separate nodes, and divides any children of the node that may exist between the two separate nodes.

14. The method of claim 6, wherein the update may include a node collapse operation that collapses two nodes into a single node, which inherits any children of the two nodes that may exist.

15. The method of claim 6, wherein a node deletion operation includes deleting any nodes that are subordinate to the node.

16. The method of claim 6, wherein the update may include a node swap operation that swaps two nodes as well as any subtrees of the nodes that may exist.

17. The method of claim 6, wherein the data that is hierarchically organized includes data that conforms to the HyperText Markup Language (HTML) standard.

18. The method of claim 6, wherein the data that is hierarchically organized includes data that conforms to the Extensible Markup Language (XML) standard.

19. The method of claim 6, wherein the data that is hierarchically organized includes a hierarchical database.

20. The method of claim 6, wherein the data that is hierarchically organized includes a directory service that supports a hierarchical name space.

21. The method of claim 6, further comprising receiving changes to the data on the server from an external source.

22. The method of claim 6, wherein the copy of the data located on the client includes a copy of a subset of the data.

23. The method of claim 6, wherein the server includes a proxy server for caching data in transit between a server and a client.

24. The method of claim 6, wherein the copy of the data located on the client includes a subset of the data on the server, wherein the subset is adaptively changed as required by the client.

25. The method of claim 6, wherein the update includes data that is validated at the server.

26. A computer readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for propagating changes in data that is hierarchically organized to a copy of the data, comprising:

receiving, at a server, a request for an update for the copy of the data located on a client;

in response to the request, determining differences between the data and the copy of the data;

using the differences to construct the update for the copy of the data, wherein the update may include node insertion and node deletion operations for hierarchically organized nodes in the data; and

sending the update from the server to the client.

27. An apparatus that propagates changes in data that is hierarchically organized to a copy of the data, comprising:

a receiving mechanism, on a server, that receives a request for an update for the copy of the data located on a client;

an update creation mechanism, on the server, that determines differences between the data and the copy of the data and uses the differences to create the update for the copy of the data, wherein the update may include node insertion and node deletion operations for hierarchically organized nodes in the data; and

a sending mechanism, on the server, that sends the update from the server to the client.

28. The apparatus of claim 27, wherein the update creation mechanism is configured to determine differences and create the update during a single pass through the data.

29. The apparatus of claim 27, wherein the update additionally includes at least one from the group of, node move, node collapse, node split and node update operations.

30. The apparatus of claim 27, wherein the update creation mechanism is configured to determine when the copy of the data on the client was last updated, and to determine how the data on the server has changed since the copy of the data was last updated.

31. The apparatus of claim 27, wherein the update includes a Multipurpose Internet Mail Extensions (MIME) content type specifying that the update contains updating operations for hierarchically organized data.

32. An apparatus that propagates changes in data that is hierarchically organized to a copy of the data, comprising:

a request generation mechanism, on a client, that receives an access to the data, determines if the client contains the copy of the data, and if so, sends a request for an update to a server;

an update receiving mechanism, on the client, that receives an update for the copy of the data from the server, wherein the update may include node insertion and node deletion operations for hierarchically organized nodes in the data; and

an updating mechanism, on the client, that applies the update to the copy of the data on the client to produce an updated copy of the data.

33. A method for propagating changes in data, the data being organized isomorphically to a hierarchy having a plurality of nodes, the method comprising:

receiving at a server a request for an update to a copy of the data;

responsively to the request, determining at the server a set of one or more differences between the copy and a preferred version of the data, the server having access to the copy and the preferred version at least for purposes of determining the set of differences;

using the set of differences to construct an update for the copy, the update being suitable to conform the copy to the preferred version of the data, the update including at least one operation selected from the group of, inserting a node in the data hierarchy or deleting a node from the data hierarchy; and

making the update thus constructed available for further use.

34. The method of claim 33, wherein the acts of determining the differences and constructing the update take place during a single pass through the data.