Propogating updates efficiently in hierarchically structured data under a push model

• US 6,311,187 B1
• Filed: 12/29/1998
• Issued: 10/30/2001
• 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): Black, Thomas
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US09/222,121
• Time in Patent Office: 1,036 Days
• Field of Search: 707/3, 707/2, 707/8, 707/10, 707/103, 707/203, 707/204
• US Class Current: 707/770
• 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/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• 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 changes to the data located on the server, and applying the changes to the data on the server. These changes are propagated to remotely cached copies of the data on a client in response to an event on a server, and independently of events on the client, by (1) determining 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; (2) using the differences 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; and (3) sending the update to the client where the update is applied to the copy of the data to produce an 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, node split, node swap and node update operations.

Claims

1. A method for propagating changes in hierarchically organized data located on a server to a copy of the data located on a client, comprising:

receiving the changes to the data on the server;

applying the changes to the data on the server; and

responsively to an event on the server and independently of the client, propagating the changes to the copy of the data by,

determining differences between the data on the server and the copy of the data which the server has locally available,

using the differences to construct an update for the copy of the data which the server has locally available, 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.

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

3. The method of claim 1, wherein the event on the server includes a timer completing a preprogrammed time interval.

4. The method of claim 1, wherein the event on the server includes a change to the data located on the server.

5. The method of claim 1, wherein the act of propagating the changes to the copy of the data on the client takes place automatically at regular time intervals.

6. The method of claim 1, wherein the act of propagating the changes to the copy of the data on the client takes place automatically at irregular time intervals.

7. The method of claim 1, wherein the act of determining the differences involves aggregating the changes to the data.

8. The method of claim 1, wherein the act of determining the differences involves examining the data after the changes have been applied to the data.

9. 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.

10. 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.

11. The method of claim 1, 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 1, 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 1, wherein the update may include a node split operation that splits a node into a pair of nodes, and divides any children of the node that may exist between the pair of nodes.

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

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

16. The method of claim 1, 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 1, wherein the data that is hierarchically organized includes data that conforms to the HyperText Markup Language (HTML) standard.

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

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

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

21. The method of claim 1, wherein the copy of the data located on the client contains a subset of the data on the server.

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

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

24. A method for propagating changes in data located on a server to a copy of the data located on a client, comprising:

receiving the changes to the data on the server;

applying the changes to the data on the server; and

propagating the changes to the copy of a subset of the data on the client automatically at regular time intervals by,

determining differences between the data on the server and the copy of the data which the server has locally available,

using the differences to construct an update for the copy of the data which the server has locally available, wherein the update may include at least one from the group of, node insertion, node deletion, node copy, node move, node collapse, node split, node swap and node update operations for hierarchically organized nodes in the data,

validating the update at the server, and

sending the update from the server to the client.

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

receiving the changes to the data on the server;

applying the changes to the data on the server; and

responsively to an event on the server and independently of the client, propagating the changes to the copy of the data by,

determining differences between the data on the server and the copy of the data which the server has locally available,

using the differences to construct an update for the copy of the data which the server has locally available, 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.

26. An apparatus that propagates changes in data located on a server to a copy of the data located on a client, comprising:

a receiving mechanism that receives the changes to the data on the server;

a change application mechanism that applies the changes to the data on the server;

a difference determining mechanism that determines differences between the data on the server and the copy of the data which the server has locally available, wherein the difference determining mechanism operates responsively to an event on the server and independently of the client;

an update creation mechanism that constructs 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; and

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

27. The method of claim 26, wherein the difference determining mechanism and the update creation mechanism operate concurrently during a single pass through the data.

28. The apparatus of claim 26, further comprising an updating mechanism on the client that applies the update to the copy of the data to produce an updated copy of the data.

29. The apparatus of claim 26, 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 26, wherein the update includes a Multipurpose Internet Mail Extensions (MIME) content type specifying that the update contains updating operations for hierarchically organized data.

31. The method of claim 26, wherein the copy of the data located on the client contains a subset of the data on the server.

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

33. A method for propagating changes in data located on a server to a copy of the data located on a client, comprising:

receiving at the client 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;

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

responsively to an event on the server and independently of the client, propagating the changes to the copy of the data by;

determining differences between the data on the server and the copy of the data which the server has locally available,

using the differences to constuct an update for the copy of the data which the server has locally available, wherein the update may include node insertiom and node deletion operations for hierarchically organized nodes in the data, and

sending the update from the server to the client.

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

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

36. The method of claim 33, wherein the copy of the data located on the client contains a subset of the data on the server.

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

38. The method of claim 33, 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.