Directed graph for distribution of time-constrained data

• US 7,353,223 B2
• Filed: 08/28/2003
• Issued: 04/01/2008
• Est. Priority Date: 08/28/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Klein, Udo
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Mahmood; Rezwanul
• Application Number:
  US10/650,079
• Publication Number:
  US 20050050012A1
• Time in Patent Office: 1,678 Days
• Field of Search: 700/100, 707/100, 707/101, 707/201, 707/203, 707/4, 707/2, 707/3, 707/5, 707/6, 705/3
• US Class Current: 707/610
• 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/275 Synchronous replication
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

In synchronizing data across a database, time-dependent and time-constrained data may be synchronized, using grouping value(s) that may themselves be time-dependent. When a time constraint prohibits data timelines from exhibiting time gaps, data included in the timeline may be mapped to a directed graph. In this way, any time gaps may be filled by extending data records that precede the gap(s), and this operation may be reflected in a coloring of the directed graph. Then, recursive processing may be performed using the directed graph, so as to account for any unanticipated effects of the extended data records.

Claims

1. A computer-implemented method comprising:

translating grouping values into nodes of a directed graph, wherein the grouping values are associated with periods of timelines, the timelines comprising data records, and wherein a grouping value associated with a period of a first one of the timelines being the same as a grouping value associated with a concurrently occurring period of a second one of the timelines indicates that specified data of a data record for the period of the first one of the timelines is to be synchronized with the specified data of a data record for the period of the second one of the timelines;

distributing data through the nodes to obtain a modified subset of the data records;

re-distributing the data recursively along the nodes to obtain a modified directed graph;

translating the modified directed graph into a modified plurality of timelines that include the modified subset of data records; and

storing the modified plurality of timelines in a storage medium.

2. The method of claim 1, wherein the data records are subject to a time constraint such that temporal gaps between the data records are not allowed, and further wherein the modified subset of data records are in compliance with the time constraint.

3. The method of claim 1 comprising extending a data record preceding a temporary gap between data records caused by a modification of the data records through the temporary gap to a next-occurring data record.

4. The method of claim 1 wherein translating sequences of grouping values comprises:

assigning identical grouping values to a single node; and

inserting edges of the directed graph between pairs of nodes that correspond to consecutively-occurring ones of the periods.

5. The method of claim 4 comprising representing a node of the directed graph based on a grouping value and beginning point of an associated one of the periods.

6. The method of claim 1 wherein distributing data through the nodes comprises:

assigning each grouping value and its associated period an assigned color; and

coloring each node its assigned color to represent data, so that nodes having identical color share identical data.

7. The method of claim 1 wherein re-distributing the data comprises:

associating data records of a first timeline and a second timeline from the plurality of timelines with a first grouping value; and

synchronizing the data records.

8. The method of claim 1 wherein distributing data comprises removing a node from the directed graph that corresponds to a timeline period that is associated with a data record having data at its beginning.

9. The method of claim 1 wherein distributing data comprises:

traversing the directed graph and designating consecutive nodes identically so as to represent identical data stored in association with the grouping values represented by the consecutive nodes; and

stopping the traversing upon reaching a differently-designated node.

10. An apparatus comprising a storage medium having machine-executable instructions stored thereon, the instructions including:

a first code segment, stored on the storage medium, for selecting a first grouping value sequence associated with a first timeline, the first timeline including first data records;

a second code segment, stored on the storage medium, for selecting a second grouping value sequence associated with a second timeline, the second timeline including second data records, wherein the first data records and second data records are subject to a time constraint such that no gap is allowed between any two of the first data records and between any two of the second data records, and further wherein a grouping value associated with a period of the first timeline being the same as a grouping value associated with a concurrently occurring period of the second timeline indicates that specified data of a data record for the period of the first timeline is to be synchronized with the specified data of a data record for the period of the second timeline;

a third code segment, stored on the storage medium, for mapping the first grouping value sequence and the second grouping value sequence into nodes of a directed graph;

a fourth code segment, stored on the storage medium, for representing data associated with a first grouping value in the directed graph by providing a first designation to a first node associated with the first grouping value; and

a fifth code segment, stored on the storage medium, for recursively distributing data through the directed graph in response to a modification of one of the first data records, beginning with a high date of the first timeline and the second timeline, to ensure that all of the first and second data records are in accordance with the time constraint.

11. The apparatus of claim 10 comprising a fifth code segment for extending a data record that precedes a gap in its associated timeline, in violation of the time constraint, until the data record meets a succeeding data record.

12. The apparatus of claim 10 comprising a sixth code segment for mapping the directed graph into a modified first timeline and a modified second timeline.

13. The apparatus of claim 10 wherein each grouping value is associated with a time period, and wherein identical data appears in the first timeline and the second timeline whenever a grouping value and period overlap.

14. The apparatus of claim 10 comprising:

a sixth code segment, stored on the storage medium, for assigning identical grouping values to a single node of the directed graph; and

a seventh code segment, stored on the storage medium, for inserting edges of the directed graph between pairs of nodes that correspond to consecutively-occurring ones of grouping values from the first grouping value sequence and the second grouping value sequence.

15. The apparatus of claim 10 comprising a sixth code segment, stored on the storage medium, for removing a node from the directed graph that corresponds to a timeline period that is associated with a data record having data at its beginning.

16. The apparatus of claim 10 comprising:

a sixth code segment, stored on the storage medium, for traversing the directed graph and designating consecutive nodes identically so as to represent identical data stored in association with the grouping values represented by the consecutive nodes; and

a seventh code segment, stored on the storage medium, for stopping the traversing upon reaching a differently-designated node.

17. A system comprising:

means for associating, in an electronic database, nodes of a directed graph with grouping periods and grouping values associated with timelines, wherein a grouping value associated with a period of a first one of the timelines being the same as a grouping value associated with a concurrently occurring period of a second one of the timelines indicates that specified data of a data record for the period of the first one of the timelines is to be synchronized with the specified data of a data record for the period of the second one of the timelines;

means for associating, in an electronic database, an edge of the directed graph between succeeding grouping periods;

means for distributing data through the nodes to obtain a modified subset of the data records, re-distributing the data recursively along the nodes to obtain a modified directed graph, and translating the modified directed graph into a modified plurality of timelines that include the modified subset of data records; and

means for storing the modified plurality of timelines in a storage medium.

18. The system of claim 17 wherein the timelines each comprises data records that are subject to a time constraint such that no temporal gap is allowed to exist between any two of the data records included in the respective timeline.

19. The system of claim 17 comprising means for designating nodes of the directed graph as corresponding to grouping periods containing data.

20. The system of claim 17 wherein a grouping period and a grouping value are associated with identical data of the timelines.