Update transactions and method and programming for use thereof for incrementally updating a geographic database

• US 5,893,113 A
• Filed: 04/25/1996
• Issued: 04/06/1999
• Est. Priority Date: 04/25/1996
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Jasper, John, Herbst, James, McGrath, Timothy
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/634,892
• Time in Patent Office: 1,076 Days
• Field of Search: 395/616, 395/614, 395/617, 395/615, 395/611, 707/201, 707/200, 707/104, 707/203, 701/208, 701/201, 701/23
• US Class Current: 1/1
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/92 Navigation
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system and method of providing incremental updates for a geographical data set for use in navigation systems. The system and method include organizing updates of geographical data set into a series of transactions. Each of the transactions includes a transaction identifier that uniquely identifies the transaction, and n steps to be applied to the geographical data set to complete the transaction. All the steps of the transaction are required to be successfully applied in order for the transaction to be completed, otherwise, the entire transaction is not applied.

Claims

1. A method of updating a geographical data set for use in navigation systems, comprising:

providing a series of transactions;

wherein each transaction of said series is comprised of;

a transaction identifier that uniquely identifies said transaction; and

n steps to be applied to a plurality of objects in said geographical data set to complete said transaction; and

applying said series of transactions to said plurality of objects in said geographical data set.

2. The method of claim 1 further comprising:

executing said n steps for each of said series of transactions.

3. The method of claim 1 further comprising:

not applying said transaction if any of said n steps is not successfully applied.

4. The method of claim 1 further comprising:

attempting to apply a first of said n steps; and

if said first of said n steps is successfully applied, attempting to apply and applying each subsequent step, if any, of said n steps until all of said n steps are applied.

5. The method of claim 4 further comprising:

if any of said steps cannot be successfully applied, reestablishing the data set as it was prior to attempting to apply any of said n steps of said transaction.

6. The method of claim 1 comprising the steps of:

attempting to apply each of said n steps, and

if a step of said transaction cannot be successfully applied, restoring the data set to its condition prior to application of said transaction.

7. The method of claim 1 wherein one of said n steps alters an object, and wherein said one step further comprises:

providing a reference to said object.

8. The method of claim 7 wherein said reference is an explicit reference.

9. The method of claim 7 wherein said reference is a descriptive reference.

10. The method of claim 7 wherein said reference uniquely identifies said object to be altered.

11. The method of claim 7 wherein said one of said n steps provides a description of an existing state of said object.

12. The method of claim 7 wherein said one of said n steps further comprises:

providing a description of a state to which said object is to be altered.

13. The method of claim 1 wherein each of said n steps includes a reference that uniquely identifies an object.

14. The method of claim 13 wherein said references include explicit references.

15. The method of claim 13 wherein said references include descriptive references.

16. The method of claim 13 wherein said references include both explicit references and descriptive references.

17. The method of claim 1 wherein each of said n steps comprises:

providing a description of an existing state of an object to be altered.

18. The method of claim 1 wherein each of said n steps comprises:

providing a description of a state to which an object is to be altered.

19. The method of claim 1 wherein one of said n steps alters a characteristic of an object, and wherein the method further comprises:

providing a reference to the object to which said characteristic being altered is associated.

20. The method of claim 19 wherein said reference is an explicit reference.

21. The method of claim 19 wherein said reference is a descriptive reference.

22. The method of claim 19 wherein said reference uniquely identifies said characteristic to be altered.

23. The method of claim 19 wherein said one of n steps comprises:

providing a description of an existing state of the characteristic to be altered.

24. The method of claim 19 wherein said one of said n steps comprises:

providing a description of a state to which said characteristic is to be altered.

25. The method of claim 1 wherein one of said n steps alters a characteristic of a particular type associated with an object, wherein only one instance of said type of characteristic is associated with said object, and wherein the method further comprises:

providing a reference to the object to which said characteristic being altered is associated; and

identifying the characteristic type to be altered.

26. The method of claim 1 wherein multiple instances of a single type of characteristic are associated with an object and further wherein one of said n steps alters one instance of said characteristics of said single type associated with the object, wherein said one instance has a value, and wherein the method further comprises:

providing a reference to the object to which said characteristic being altered is associated;

identifying the characteristic type to be altered; and

identifying the value of said characteristic to be altered.

27. The method of claim 1 wherein said transaction further comprises:

an indication when the transaction was originally published.

28. The method of claim 1 wherein said transaction further comprises:

an indication when the transaction is to take effect.

29. The method of claim 1 wherein said transaction further comprises:

an identification of a data set to which said transaction is to be applied.

30. The method of claim 1 wherein said transaction further comprises an identification of n.

31. The method of claim 1 wherein one of said n steps comprises adding new data to the data set.

32. The method of claim 1 wherein one of said n steps comprises removing existing data from the data set.

33. The method of claim 1 wherein one of said n steps comprises changing an existing state of data values to different data values.

34. The method of claim 1 wherein one of said n steps comprises adding a new object to the data set.

35. The method of claim 1 wherein one of said n steps comprises deleting an object from the data set.

36. The method of claim 1 wherein an object comprises one of:

a geographical node, a geographical edge, a geographical face, a geographical point feature, a geographical line feature, a geographical area feature, a geographical relationship, a source document, and a geographical name.

37. The method of claim 1 wherein one of said n steps comprises adding a new characteristic to the data set.

38. The method of claim 1 wherein one of said n steps comprises deleting an existing characteristic from the data set.

39. The method of claim 1 wherein one of said n steps comprises changing an existing characteristic to a different characteristic.

40. The method of claim 1 wherein a characteristic comprises one of:

an X, Y, and Z value, a set of nodes that make up an edge, a set of edges that make up a face, a geometric composition, an attribute, text of a name, and descriptive information for source material.

41. The method of claim 1 wherein one of said n steps comprises splitting a line feature.

42. The method of claim 1 wherein one of said n steps comprises merging a line feature.

43. The method of claim 1 wherein one of said n steps comprises splitting an edge.

44. The method of claim 1 wherein one of said n steps comprises merging an edge.

45. The method of claim 1 wherein said geographical data set is in an interchange format.

46. The method of claim 45 wherein said interchange format is GDF.

47. The method of claim 1 wherein said geographical data set is in an application format.

48. The method of claim 1 wherein each of said transactions further comprises a dependency indication identifying required prior transactions, if any, and further comprising the step of:

refraining from applying the transaction if any prior transaction in said dependency indication is missing.

49. The method of claim 1 wherein said navigation systems are installed in vehicles and wherein the method further comprises:

providing copies of said series of transactions for said vehicles.

50. A method of organizing geographical data for navigation application programs, said method comprising:

associating geographical data representing geographical objects with geographical data representing characteristics that describe the geographical objects;

identifying a first plurality of said geographical objects with explicit object references; and

identifying a second plurality of geographical objects with descriptive object references, wherein each of said descriptive object references includes the geographical data in at least one characteristic associated with said geographical object.

51. The method of claim 50 wherein said explicit references and descriptive references uniquely identify all of said geographical objects.

52. A method for updating a geographical data set, wherein said geographical date set includes data elements corresponding to geographical locations, comprising:

storing values corresponding to geographic data in a first type of database element;

using said values in said first type of database element to identify a second type of database element wherein said second type of database element is associated with said first type of database element; and

updating the values in the second type of database element.

53. An update transaction for an existing geographical data set used in computer-based navigation systems, said update transaction and said existing geographical data set embodied in computer-readable media, wherein said existing geographical data set comprises geographical objects and characteristics that describe said geographical objects, said update transaction comprising:

transaction control data to correctly alter the existing geographic data set from one valid state to another; and

n steps to be executed to complete said transaction, wherein said n steps identify a plurality of geographical objects and attributes to be updated.

54. A method of updating an existing geographical data set comprised of:

providing a geographical data set comprised of geographical objects and characteristics that describe said geographical objects; and

providing a series of update transactions, each of said update transactions defined as in claim 53.

55. The invention of claim 53 wherein said transaction control data further comprises:

a dependency indication identifying required prior transactions, if any.

56. The invention of claim 53 wherein said update transaction further comprises:

a transaction identifier that uniquely identifies said transaction.

57. The invention of claim 53 wherein said transaction control data identifies a set of transactions which must have been successfully applied prior to said update transaction.

58. The invention of claim 53 wherein said transaction control data identifies the existing geographic data set to be updated.

59. The invention of claim 53 wherein said transaction control data identifies when said update transaction was originally published.

60. The invention of claim 53 wherein said transaction control data identifies when said ordered set of alterations are to be effective.

61. A method for processing an update of an existing navigation dataset that has become outdated comprising:

acquiring an update transaction, wherein said update transaction comprises an ordered set of alterations to be made to the navigation dataset and control data to correctly alter the dataset from one valid state to another valid state, wherein said control data includes dependency data indicating prior update transactions, if any, which are required to have been applied to the existing navigation dataset, wherein said prior update transactions do not necessarily include all prior update transactions; and

executing an update program that uses the update transaction and said control data and applies the update transaction to the existing navigation dataset.

62. A computer program for updating an existing navigation dataset from a first valid state to a second valid state using an update transaction, said computer program comprising:

programming code that confirms that the update transaction corresponds to the existing navigation dataset;

programming code that checks that the required prior transactions have been applied to the existing navigation dataset; and

programming code that applies a set of alterations included in the update transaction to the existing navigation dataset to update said existing navigation dataset from said first valid state to said second valid state.

63. The computer program of claim 62 further comprising:

programming code that restores the existing navigation dataset to said first valid state if any one alteration of said set of alterations state cannot be successfully applied thereto.

64. A system for updating a plurality of existing navigation datasets comprising:

developing an update transaction for an existing navigation dataset, wherein the update transaction comprises an ordered set of alterations to be made to a plurality of objects in the dataset and control data to correctly alter the existing dataset from one valid state to another valid state; and

publishing the update transaction to a navigation data set to a plurality of entities wherein each of said plurality of entities has a copy of the existing navigation data set.

65. The system of claim 64 wherein the alterations comprise a set of steps.

66. The system of claim 64 wherein the set of steps includes adding new data to the dataset.

67. The system of claim 64 wherein the set of steps includes removing existing data from the dataset.

68. The system of claim 64 wherein the set of steps includes changing the state of known data values in the existing dataset to have different data values.

69. The system of claim 64 wherein the update transaction further comprises a transaction identification.

70. The system of claim 69 wherein the transaction identification uniquely identifies the transaction.

71. The system of claim 64 wherein the control data identifies a set of transactions which must have been successfully applied prior to said update transaction.

72. The system of claim 64 wherein the control data identities the dataset to be updated.

73. The system of claim 64 wherein the control data includes a time stamp identifying when said update transaction was originally published.

74. The system of claim 64 wherein the control data includes an effective data identifying when said ordered set of alterations are to be effective.