MAINTAINING A RELATIONSHIP BETWEEN TWO DIFFERENT ITEMS OF DATA

• US 20100153397A1
• Filed: 08/05/2009
• Published: 06/17/2010
• Est. Priority Date: 10/13/2000
• Status: Active Grant

• Current Assignee: MIOsoft Corporation
• Original Assignee: MIOsoft Corporation
• Inventors: Siepmann, Ernst M., van Gulik, Mark D.A., Barabas, Albert B.
• Granted Patent: US 9,189,536 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Data is stored persistently. At least two different items of the data are stored in two different non-conflicting regions or two different physical clusters. A relationship is maintained between the two different items of data. The relationship enables a process to reach any one of the data items from the other data item. Consistency of the relationship is maintained notwithstanding updates of either or both of the items.

Claims

1-23. -23. (canceled)

24. A method comprising

maintaining a database that stores data persistently,

accepting jobs for concurrent execution by processors, the jobs requiring access to data in the database, at least some of the jobs requiring execution as a group, each of the jobs of a group having associated information that defines its participation in the group, and

a processor refraining from executing any of the jobs of a group until it determines from the associated information that processing can proceed for all of the jobs of the group.

25. The method of claim 24, in which the jobs that are accepted for execution as a group are created by branching of other jobs.

26. The method of claim 24 in which the information associated with the jobs of a group is generated at the time of creation of the jobs.

27. The method of claim 24 in which the information includes a tag that identifies a job as participating in the group.

28. The method of claim 24 in which the information includes a quorum fraction that represents the job'"'"'s proportion of participation in the group.

29. A method comprising

maintaining a database that stores data persistently,

accepting jobs for concurrent execution by processors, the jobs requiring access to data in the database, and

causing each of the processors to execute at least some of the jobs other than in the order in which the jobs are received for execution.

30. The method of claim 29 in which the at least some of the jobs to be executed by one of the processors are replaced by a single aggregated job.

31. The method of claim 29 in which each of the processors determines an order in which to process at least some of the jobs based on the physical locations on disk of the data that must be accessed by the jobs.

32. The method of claim 29 in which at least some of the jobs to be executed by a processor are redundant, and the processor does not execute the redundant jobs.

33. A method comprising

maintaining a database that stores data persistently,

accepting tasks from task sources, the tasks being associated with priority information that identifies each of them as having one of at least two different levels of priority for execution,

defining, for each of the tasks, jobs to be executed to complete the task,

distributing the jobs for concurrent execution by processors, and

selecting jobs for execution in an order that is based on the priorities of the tasks with which they are associated.

34. The method of claim 33 in which at least some of the tasks have competing requirements for use of regions of the database, each of the regions including data that is all either locked or not locked for writing at a given time, and each of the regions is associated with one of the processors.

35. The method of claim 33 in which the jobs are executed in an order that assures no more than a predetermined average short delay between the creation of a task and the execution of the jobs defined for the task.

36. The method of claim 33 in which jobs of one priority are guaranteed to be executed in a manner that does not delay jobs of a second priority by more than a predetermined average delay time.

37. The method of claim 33 in which the tasks include higher priority tasks generated by users for execution in real-time and lower priority tasks generated by software processes.

38. The method of claim 33 in which jobs are selected into an execution set of a predetermined size by each of the processors from a staged set of jobs that has been distributed to that processor and is awaiting execution.

39. The method of claim 33 in which only jobs of higher priority are selected from the staged set until the execution set is filled, and, if the execution set cannot be filled by higher priority jobs, then lower priority jobs are selected from the staged set for inclusion in the execution set.

40. A method comprising

storing data persistently in a database, and

creating at least two physical clusters of data items in a storage medium, at least one of the clusters containing at least one data item that is a replica of one of the data items in the other cluster, the clusters being organized by two different criteria.

41. The method of claim 40 in which consistency is maintained between the data and the replica by concurrent processing on at least two different processors

42. The method of claim 40 in which the two different processors do not use shared memory for the concurrent processing.

43. The method of claim 40 in which, while the replica is being updated, the related portions of the data may be concurrently updated.

44. The method of claim 40 in which the portion of the data included in each of the replicas are specified by a user.

45. The method of claim 40 in which the portions of the data included in each of the replica are selected.

46. The method of claim 40 in which the replica is associated with an index.

47. The method of claim 40 in which the data and replica are operated on by algorithms and the replica and data are partitioned to enable the algorithms to be decomposed into sub-algorithms that are executed on the respective partitions of the replica and data concurrently.

48. The method of claim 40 in which the concurrent processing is done in a predetermined relative order with respect to the stored data and the replica.

49. A method comprising

storing data persistently,

storing persistent replicas of portions of the data, and

partitioning the stored replicas into partitions that enable an algorithm that uses the data to be decomposed into sub-algorithms that can be processed concurrently.

50. The method of claim 49 in which consistency among the replicas is maintained by concurrent processing on at least two different processors

51. The method of claim 49 in which the two different processors do not use shared memory for the concurrent processing.

52. The method of claim 49 in which, while one of the replicas is being updated, the related portions of the data may be concurrently updated.

53. The method of claim 49 in which the replicas can be concurrently updated by at least two different processors.

54. The method of claim 49 in which the portions of the data included in each of the replicas are specified by a user.

55. The method of claim 49 in which the portions of the data included in each of the replicas are selected.

56. The method of claim 49 in which the replicas are physically clustered in storage.

57. The method of claim 49 in which each replica contains only data that is required by one of the sub-algorithms.

58. The method of claim 49 in which the concurrent processing is done in a predetermined relative order with respect to the stored data and the replicas.