Directed graph for distribution of time-constrained data

• US 20050050012A1
• Filed: 08/28/2003
• Published: 03/03/2005
• Est. Priority Date: 08/28/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Klein, Udo
• Granted Patent: US 7,353,223 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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;

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.

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 instructions stored thereon, the instructions including:

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

a second code segment for selecting a second grouping value sequence associated with a second timeline, the second timeline including second data records;

a third code segment for mapping the first grouping value sequence and the second grouping value sequence into nodes of a directed graph; and

a fourth code segment 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.

11. The apparatus of claim 10 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 second data records.

12. The apparatus of claim 11 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.

13. The apparatus of claim 11 comprising a fifth code segment 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.

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

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

16. The apparatus of claim 10 comprising:

a fifth code segment for assigning identical grouping values to a single node of the directed graph; and

a sixth code segment 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.

17. The apparatus of claim 10 comprising a fifth code segment 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.

18. The apparatus of claim 10 comprising:

a fifth code segment 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 sixth code segment for stopping the traversing upon reaching a differently-designated node.

19. A system comprising:

means for associating nodes of a directed graph with grouping periods and grouping values associated with timelines;

means for associating an edge of the directed graph between succeeding grouping periods; and

means for distributing data associated with the timelines by operating on the directed graph, and thereafter translating the directed graph back into the timelines.

20. The system of claim 19 wherein the timelines comprise 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.

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

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