System and method for serializing lazy updates in a distributed database without requiring timestamps

• US 6,381,609 B1
• Filed: 07/02/1999
• Issued: 04/30/2002
• Est. Priority Date: 07/02/1999
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Breitbart, Yuri J., Seshadri, Srinivasan, Silberschatz, Abraham, Komondoor, Raghavan V.
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/346,798
• Time in Patent Office: 1,033 Days
• Field of Search: 707/10, 707/102, 707/103, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• 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: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system for, and method of, ensuring serialization of lazy updates in a distributed database described by a directed acyclic copy graph. In one embodiment, the system includes: (1) a forest construction module that creates a forest having trees and edges from the directed acyclic copy graph and (2) a propagation module, associated with the forest construction module, that employs the edges of the forest to propagate the lazy updates among replicas in the distributed database and ensure the serialization.

Claims

1. A system for ensuring serialization of lazy updates in a distributed database described by a directed acyclic copy graph, comprising:

a forest construction module that creates a forest having trees and edges from said directed acyclic copy graph; and

a propagation module, associated with said forest construction module, that employs said edges of said forest to propagate said lazy updates among replicas in said distributed database and ensure said serialization.

2. The system as recited in claim 1 wherein each of said trees comprises a node with exactly one parent.

3. The system as recited in claim 1 wherein said propagation module propagates said lazy updates without employing timestamps.

4. The system as recited in claim 1 wherein said forest construction module arbitrarily selects a sink node of said forest.

5. The system as recited in claim 1 wherein said propagation module propagates transactions within a child tree of said forest only to selected children of said child tree.

6. The system as recited in claim 1 wherein said propagation module propagates transactions sequentially along edges of said forest.

7. The system as recited in claim 1 wherein a counterpart of said system is located at each replica of said distributed database.

8. A method of ensuring serialization of lazy updates in a distributed database described by a directed acyclic copy graph, comprising:

creating a forest having trees and edges from said directed acyclic copy graph; and

employing said edges of said forest to propagate said lazy updates among replicas in said distributed database and ensure said serialization.

9. The method as recited in claim 8 wherein each of said trees comprises a node with exactly one parent.

10. The method as recited in claim 8 wherein said employing comprises propagating said lazy updates without employing timestamps.

11. The method as recited in claim 8 wherein said creating comprises arbitrarily selecting a sink node of said forest.

12. The method as recited in claim 8 wherein said employing comprises propagating transactions within a child tree of said forest only to selected children of said child tree.

13. The method as recited in claim 8 wherein said employing comprises propagating transactions sequentially along edges of said forest.

14. The method as recited in claim 8 wherein said method is carried out at each replica of said distributed database.

15. A distributed database described by a directed acyclic copy graph, comprising:

at least two primary sites;

at least two secondary sites; and

a system for ensuring serialization of lazy updates among said at least two primary site and said at least two secondary sites, including;

a forest construction module that creates a forest having trees and edges from said directed acyclic copy graph, and

a propagation module, associated with said forest construction module, that employs said edges of said forest to propagate said lazy updates among replicas in said distributed database and ensure said serialization.

16. The distributed database as recited in claim 15 wherein each of said trees comprises a node with exactly one parent.

17. The distributed database as recited in claim 15 wherein said propagation module propagates said lazy updates without employing timestamps.

18. The distributed database as recited in claim 15 wherein said forest construction module arbitrarily selects a root of said forest.

19. The distributed database as recited in claim 15 wherein said propagation module propagates transactions within a child tree of said forest only to selected children of said child tree.

20. The distributed database as recited in claim 15 wherein said propagation module propagates transactions sequentially along edges of said forest.

21. The distributed database as recited in claim 15 wherein a counterpart of said system is located at said at least two primary site and said at least two secondary sites.

22. A system for ensuring serialization of lazy updates in a distributed database described by a directed acyclic copy graph, comprising:

a forest construction module that creates a forest including an undirected acyclic copy graph having edges from said directed acyclic copy graph; and

a propagation module, associated with said forest construction module, that employs said edges of said forest to propagate said lazy updates among replicas in said distributed database and ensure said serialization.

23. The system as recited in claim 22 wherein said propagation module propagates said lazy updates without employing timestamps.

24. The system as recited in claim 22 wherein said edges are undirected.

25. The system as recited in claim 22 wherein said propagation module propagates transactions sequentially along edges of said forest.

26. The system as recited in claim 22 wherein a counterpart of said system is located at each replica of said distributed database.