Update transactions and method and programming for use thereof for incrementally updating a geographic database5893113Abstract 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 We claim: Description BACKGROUND OF THE INVENTION
TABLE 1
______________________________________
Examples of Characteristics
Characteristic
Characteristic
Object Type Value
______________________________________
Road Element Road Width 6 Metres
Node X-Coordinate 12.34567.degree. North
______________________________________
III. Unambiguous Identification for Objects and Characteristics Once the relationship between the objects and their characteristics has been established for a particular data model, the methods for unambiguously identifying the individual components can be described. Unambiguous identification of objects and characteristics are called references. A. Object References An "object reference" is a property of an object that distinguishes it from all other objects. This property is a distinguishing set of data, in the known dataset, which unambiguously identifies the object. There are two types of object references: explicit and descriptive. (1) Explicit Object Reference The first type of "object reference" is the "explicit reference". The "explicit reference" is an identifier which is provided by the supplier solely for the purpose of future reference to the object. Table 2, below, is an example showing "explicit object references" for the listed objects.
TABLE 2
______________________________________
Descriptive of Explicit Object References
Object Components of Explicit Reference
______________________________________
node Record Type and Record ID of Node Record
edge Record Type and Record ID of Edge Record
face Record Type and Record ID of Face Record
point feature
Record Type and Record ID of Point Feature
Record
line feature
Record Type and Record ID of Line Feature Record
area feature
Record Type and Record ID of Area Feature Record
relationship
Record Type and Record ID of Relationship Record
source document
Record Type and Record ID of Document Record
name Record Type and Record ID of Name Record
______________________________________
In some cases, other identifiers which were provided in the original dataset may be required to make these explicit references unique. An example of a generic explicit reference for all objects is:
______________________________________
Record Identifier
+Record Type
›+Dataset ID ›+SectionID!!
______________________________________
where square brackets › ! indicate optional components which are only required to provide uniqueness. It is possible to use the existing CEN GDF attribute called External Identifier to publish the explicit object reference. This attribute allows the publisher to assign a unique reference to an object independently of the record types and record identifiers which are internal to a particular GDF dataset. (2) Descriptive Object Reference Sometimes, it is not desirable to use an explicit reference for every object in a database. This may be because either the publisher's or user's data structures do not permit an external reference due to size or processing considerations. In these situations, it is favorable to use some set of the existing data associated to the object to unambiguously distinguish it. This has the benefit of using data that already exists in the database. These references are called "descriptive object references." A descriptive object reference identifies an object by using a (sub)set of the characteristic data that defines the object. For example, a "Prohibited Turn" Relationship may be identified by stating the set of Road Elements which composed it in the original dataset. As with the explicit references, descriptive references must be unique. A "Validity Period", "Vehicle Type" or other type of subattribute may be used to describe a limitation in the existence of a particular object. These subattributes can be called "definitive attributes". A "definitive attribute" may be needed to uniquely identify an object. In the example of a "Prohibited Turn" relationship, if the restriction is in effect only between 7:00 am and 9:00 am and between 4:00 pm and 6:00 pm, it might not be valid to describe the object only as a set of Road Elements. Instead it might be necessary also to state the particular "Validity Period" in order to distinguish whether we are updating the "Prohibited Turn" between 7:00 am and 9:00 am or the "Prohibited Turn" between 4:00 pm and 6:00 pm. Definitive attributes may be optional parts of a descriptive reference. Therefore, it is possible that the format of descriptive object references may vary for objects of the same type. An example of a generic descriptive object reference for all relationship objects is:
______________________________________
Relationship.sub.-- type.sub.-- code
+Num.sub.-- Features
+(feature class code+feature ID).sup.occurs Num-.sbsp.--.sup.features
times
›{+subattribute type
+subattribute value}.sup.occurs 0 or more times !
______________________________________
Square brackets › ! indicate optional components that are only required to provide uniqueness. Braces { } indicate a set of components that can occur zero or more times. The superscript for the braces describes how often it repeats. (3) Syntax for declaring object references To make certain that both the geographic data set developer/publisher and the geographical data set customer/user of the data understand exactly what is being used as an object reference, the developer/publisher should have a way of clearly stating the methods used for referencing objects. Specifically, the developer/publisher should have a method for identifying: (1) the type of reference (explicit or descriptive) that is valid for each object type; (2) the format and construction of the references; and (3) the fields which comprise the mandatory and optional components of a descriptive object reference. B. Characteristic References In order to process update actions of characteristic data, there is provided a means to unambiguously identify a particular instance of an object's characteristic. The characteristic reference can be made by first referencing a particular object (by using the explicit or descriptive reference), and then identifying the instance of the characteristic. If there is only one instance of characteristic data of a particular type, then it is enough to simply state the characteristic type. For example, if a Road Element has only one value for the Form of Way attribute, then it is sufficient to identify the Road Element object, and then indicate the Form of Way attribute. Sometimes there are several instances of characteristic data for a single characteristic type. For example, a Road Element may have one Name Attribute with the value "Main Street" and another Name Attribute with the value "First Avenue". In these cases, the publisher identifies both the characteristic type and the characteristic value in order to uniquely reference a particular instance of the characteristic. EXAMPLES A Road Element (with explicit Object ID 1001) has only one instance of the Route Identifier characteristic (characteristic type RT) and it has the value "US-101". If the Route Identifier characteristic changes from "US-101" to "US-101 North", then the publisher/developer can simply publish the following:
______________________________________
object 1001,
characteristic RT, now has the value "US-101
North"
______________________________________
However, suppose there is a road element object with explicit ID 2002, and it has two instances of the Route Identifier characteristic; one instance has the value "US-101" and the other instance has the value "I-95". If the Route Identifier changes from "US-101" to "US-101 North", then the publisher/developer must state:
______________________________________
object 2002,
characteristic RT, the instance with the value
"US-101" now has the value "US-101 North".
______________________________________
This is in order not to confuse the change of Route Identifier instance "US-101" with the Route Identifier instance "I-95". In the cases where there is only one instance of a particular characteristic type, it may be allowed (but not required) for the publisher/developer to include the characteristic value. That means, in the first example, it would have been equally valid to say:
______________________________________
object 1001, characteristic RT, the instance with
the value "US-101" now has the value "US-101
North".
______________________________________
IV. Format for Publishing an Update As stated above, an incremental update is a description of an alteration to a known set of data. The update should contain a reference to the database element being updated, and a description of the alteration to the content of the known dataset. The update preferably contains controls to provide that the dataset maintains integrity. This integrity facilitates the dataset's ability to be later updated by another update. To satisfy these requirements, control data is provided that enables the ability to determine the state of the data before it is altered. This ensures that all of the dependencies which are required before processing and update have been satisfied. In addition, the control data provides the ability to perform multiple alterations as a single action. This avoids the possibility that any single alteration might leave the dataset in a condition which does not satisfy all of the quality and integrity requirements. Therefore, it is preferable to have the ability to identify multiple alterations that are treated as a single action. Accordingly, an update consists of an ordered set of database alterations and the necessary control information to correctly alter a known dataset from one valid state to another valid state. The database alterations are known as steps. The set of steps and control data are known as a "transaction". A "transaction" is comprised of the following:
______________________________________
TRANSACTION =
Transaction Identification
Transaction Control Data
Number.sub.-- of.sub.-- Steps
{
Step Action
Step Details
}.sup.occurs Number.sbsp.--.sup.of.sbsp.--.sup.Steps
______________________________________
times
The components inside the braces { } may occur zero or more times. The superscript for the braces describes how often it repeats. FIG. 2 illustrates the components that make up a transaction 20. Specifically, the transaction 20 includes a transaction identification 24, a dependency identification 28, an original publication date 32, an effective date 36, an indication of the number of steps 40, and one or more steps 44 (44.sub.1 through 44.sub.n). Each of these components is described in detail below. A. Transaction identification The "transaction identification" is a preferably sequential number that uniquely identifies (in combination with the "database identification") the complete transaction. In combination with the database identification, the sequence number acts as a release/database version number. It can be used to indicate which transactions have been processed. Transactions do not have to be processed in order of sequence number, only in order of dependencies. Transaction identifiers may be used to determine the completeness of the updates to a particular database, for example by keeping them strictly sequential. B. Transaction Control Data The "transaction control data" consists of the following fields: "dependency", "database identification", "time stamp of publish", and "time stamp of effective date". Each of these are described as follows: (1) "dependency" The "dependency" is a set of transaction identifications which must have been successfully applied prior to the current transaction being applied. It is valid for the "dependency" field to be blank, indicating there are no dependencies. (2) "database identification" The "database identification" is a publisher/specified identification of the database to be updated. (3) "time stamp of publish" The "time stamp of publish" is the time and date when the transaction was originally published. (4) "time stamp of effective date" The "time stamp of effective date" is the time and date when the alterations described in the transaction will take effect. If it is left blank, it indicates is that the alterations are effective immediately. C. Number.sub.-- of.sub.-- Steps The "Number.sub.-- of.sub.-- Steps" is an integer number, n, that indicates how many separate "Steps" are included in the particular transaction. n may be 1, 2, or even thousands. D. Step Actions "Step actions" describe the basic action to be performed to alter an existing dataset. The basic actions are: (1) add new, previously not known data to the dataset (called an "add") (2) remove existing known data from the dataset (called a "delete") (3) changing the state of the known data values to have new, different data values (called a "change"). (The above list of actions is exemplary and is not intended to be an exhaustive listing of all possible "step actions".) Because "objects" are independent of other "objects", for purposes of this embodiment, an "object" does not "change" to another object; only the "characteristics" of an "object" can change. For example, one "Road Element" does not change into another "Road Element". However, the name or geometric description of a "Road Element" may change. Likewise, one "source document" does not change into another "source document"; however, its "title" or "year of publication" may be updated. Therefore, "objects" are only added or deleted from a dataset. Because "characteristics" are descriptive in nature, they can change their value, or be added or removed from a dataset. Also, typically, when an "object" is added, several "characteristics" of that "object" may also be added. This leads us to the following set of valid "step actions". This list is exemplary and is not intended to be exhaustive. Object Add, Object Delete, Characteristic Add, Characteristic Delete, Characteristic Change, and Object and Characteristic Add. In addition, due to the need to regularly perform specific types of changes, the following "step actions" are also permitted: a line feature split, a line feature merge, an edge split, and an edge merge. E. Step Details The components of the "step details" are as follows: (1) Object Reference The explicit or descriptive reference for the object which will be altered or have one of its characteristics altered. (2) Old Data State A description of either the object or the characteristic as it exists in the currently known dataset prior to this step action. (3) New Data State A description of either the object or the characteristic as it will exist in the new dataset upon completion of the step action. The values required for Old Data State and New Data State vary depending on the Step Action. These requirements are described in Table 3. Again, this listing is exemplary and is not intended to be an exhaustive listing of all possible combinations.
TABLE 3
__________________________________________________________________________
Example - Table of Transaction Data Required by Step Action
Step Action
Reference
Old Data State
New Data State
__________________________________________________________________________
Object Add
Explicit or
None Definition of Object
descriptive
reference of
object to be
added
Object Delete
Explicit or
None None
descriptive
reference of
object to be
deleted
Characteristic
Explicit or
None Characteristic
Characteristic
Add descriptive Type to be
Value
reference of added
object for which
a characteristic
is to be added
Characteristic
Explicit or
Characteristic
Characteristic
None
Delete descriptive
Type to be
Value*
reference of
deleted
*This is only
object for which
required if
a characteristic
there is more
is to be deleted
than one
instance of
this
Characteristic
Type for this
object
Characteristic
Explicit or
Characteristic
Characteristic
New Characteristic Value
Change descriptive
Type to be
Value of
reference of
changed
instance to be
object for which
changed*
a characteristic
*This is only
is to be changed
required if
there is more
than one
instance of
this
Characteristic
Type for this
object
Object and
Explicit or
None Definition of Object
Characteristic
descriptive List of Characteristic Types
Add reference of and Values to be added
object to be
added
__________________________________________________________________________
The "Old Data State" is used to state the previous value of a characteristic type and value as it existed in the known dataset prior to the start of this step action. If a characteristic type had more than one instance for the given object, then the characteristic type and characteristic value which is being changed or deleted must be stated. If the characteristic type had only one occurrence for the given object then only the characteristic type is required. As an example, for Level 0 or Level 1 GDF Features, if a set of geometry is listed in "Old Data State", then only that subset is deleted or replaced by the set of geometry listed in the "New Data State" section. For a Characteristic Change, the geometry listed in the "New Data State" section must be connected geometric primitives. V. Procedures for Processing an Update A transaction contains an ordered set of steps, grouped together to form a single act of adding, changing and/or deleting objects and/or characteristics to the known dataset. All steps in the transaction must be completed successfully, or the entire transaction (i.e., all the steps that make up the transaction) is not applied. The steps are to be performed in the order in which they are stated in the transaction. A flow chart showing the process for applying the steps of a transaction is included at FIG. 3. In FIG. 3, the transaction process first attempts to apply the first step (Step 50). If the step is successfully applied (Step 52), the transaction process checks to determine whether there are more steps to the transaction (Step 54), and if there are, the process loops (Step 56). If any of the steps cannot successfully be applied, the transaction process does not apply the previous steps, if any (Step 58), restores the geographical data set to the state that it was in prior to any changes attempted by the transaction, and the transaction is not applied. However, if each of the steps can be successfully applied, then all the steps are applied (Step 59), and the transaction is complete. For example, if a new street were added, multiple alterations may be required to effectuate several geometry changes, an "object add", and, the assigning of attributes of the street. If only some (but not all) of these actions are applied in the database, the incomplete transaction may break the road connectivity, rendering the database unusable or erroneous at the affected elements. Therefore, all of the alterations should be grouped into a single transaction. If any of them cannot be performed, then the entire transaction is abandoned. The following rules govern the processing of an update: (1) All of a transaction's dependencies must be successfully applied before a transaction can be applied. (2) All of a transaction's steps must be successfully applied for a transaction to be successful. (3) If a complete transaction is unsuccessful, none of that transaction's steps are applied. Any data affected by steps applied prior to the failure of a transaction is restored. (4) The data processor should track all necessary information needed to restore data affected by any action if the entire transaction cannot be completed. (5) It is not a requirement for every change to actually alter the known dataset. For example, a data publisher may publish a "characteristic change" transaction and provide a characteristic value which is the same as the value in the known dataset. Referring to FIG. 4, in updating the geographical data set 10, the alterations to the geographical data set can be grouped into one or more transactions 20, 70, 72, 74 and so on. The transactions are then applied to the data set 10. Each transaction is independent of the others in the sense that any of the transactions can be applied in any order so long as the required dependencies for that transaction have been applied. It is expected that many of the transactions will have dependencies that require previous transactions to have been applied. Each transaction can make zero, one, a few, or many alterations to the data set. For example, some transactions may involve making only a single alteration to a single data element of the geographical data set, whereas other transactions may include hundreds or thousands of alterations to many of the elements of the data set. Thus, the embodiment of the transaction format, as described above, is very versatile for enabling the updating of a geographical data set. Further, the geographical data set and the updating transactions do not necessarily have to be in the same format. It is understood that the transaction updates and/or the geographical data set may be converted from one format to another in connection with the application of the updates. For example, the transactions may be published in a non-proprietary format, translated into a customer's proprietary format, and applied to the customer's geographical data set which also may be in a proprietary format. Alternatively, the customer may convert its existing geographical data set into a non-proprietary format, apply transactions in the non-proprietary format, and convert the updated geographical data set back into a proprietary format. Similarly, a geographical data set publisher can publish transactions in its own format, provide the transactions to a customer who converts the transactions into its own proprietary format and applies the translated transactions to its geographical data set in its own format without ever converting either the transactions or the geographical data set into the non-proprietary format. The embodiment is applicable to both interchange formats and application formats. FIG. 5 illustrates diagrammatically the use of descriptive object references to uniquely identify a transaction. Geographic data has the property of being unique. That is, geographic data, such as latitude and longitude, defines a unique location on the earth. Because the geographical data itself can be unique, the value of the data itself can be used to uniquely identify the data elements that are used to contain the values. This provides a database developer or customer with an ability to uniquely identify the data in the database for any purpose, such as updating, without necessarily providing explicit, extraneous identification data. This has the potential advantage of reducing the amount of data that is necessary to store. In FIG. 5, a transaction includes a step 80. The step 80 includes an alteration E.sub.xu to an element E.sub.x in the existing data set 10 having data elements E.sub.1 to E.sub.n that include the element E.sub.x. The step 80 includes the descriptive reference 88 which includes fields of geographical information that have values that relate to geographical data (represented by the drawing of the earth 92). The geographical information in the descriptive reference is sufficient such that the values of the information in these fields of geographical data provide a means for an update processor program P to uniquely identify the element E.sub.x. Example 1 This example demonstrates a process for providing an incremental update of a geographical data set. In this example, the geographical data set conforms to the GDF standard. Further, in this example, the geographical data set is assumed to relate to the City of Chicago. According to this example, it is also assumed that in the original release of the geographical data set, it was represented that at the intersection of Illinois Avenue and McClurg Ct. there were no turn restrictions. However, subsequent to the original release of the navigation data set, the City of Chicago installed signs in all directions prohibiting left turns. Thus, the navigation data set developer that produced the original geographical data set wishes to provide an update of the original geographical data set to take into account this new geographical information without having to replace the entire data set or complete files of the data set. Accordingly, the navigation data set developer may prepare a transaction as follows:
______________________________________
Transaction ID = 0000027
Transaction Control Data:
(1) dependency =
0000026; 0000025;
0000024; 0000021.
(2) database ID = NT001USCHIC0047
(3) time date = 960131, 063500
(4) effective = 960131, 063500
Number.sub.-- of.sub.-- Steps = 4
First Step Action = Characteristic Change
Step Details:
(1) Object Reference =
Explicit Reference: 1056290
(2) Old Data State =
Turn Restriction Attribute =
"none"
(3) New Data State =
Turn Restriction Attribute =
"left turn prohibited"
Second Step Action = Characteristic Change
Step Details =
(1) Object Reference =
Explicit Reference: 1056229
(2) Old Data State =
Turn Restriction Attribute =
"none"
(3) New Data State =
Turn Restriction Attribute =
"left turn prohibited"
Third Step Action = Characteristic Change
Step Details =
(1) Object Reference =
Explicit Reference: 2847200
(2) Old Data State =
Turn Restriction Attribute =
"none"
(3) New Data State =
Turn Restriction Attribute =
"left turn prohibited"
Fourth Step Action = Characteristic Change
Step Details =
(1) Object Reference =
Explicit Reference: 2847289
(2) Old Data State =
Turn Restriction Attribute =
"none"
(3) New Data State =
Turn Restriction Attribute =
"left turn prohibited"
}
______________________________________
After this transaction has been prepared, it is made available as an incremental update to entities or persons who have the original navigation data set. These entities and persons may include companies that use the navigation data set in navigation systems, fleet operators, traffic management organizations, end-users and others. This transaction may be provided by itself, or may be bundled with other transactions. In this example, the transaction being processed has a "transaction ID" of "0000027". To use this transaction to incrementally update an existing navigation data set, the entity that has an existing navigation data set will run an incremental update program. The incremental update program processes the transaction to update the existing data set by performing the following steps. In this example, the incremental update program that applies the transaction "0000027" to the original data set first checks to confirm that the database ID "NT001USCHIC0047" listed in the transaction 0000027 corresponds to the ID of the navigation data set being updated. The navigation data set ID may be stored in a computer-readable format in or with the navigation data set in a header or initialization file, for example. If the ID's do not match, the transaction 0000027 does not relate to the navigation data set and the update program will not permit the process to proceed. Next, the incremental update program checks the dependencies. The transaction listed above has the following four dependencies: "0000026", "0000025", "0000024", and "0000021". This means that the incremental update processing program will permit the transaction 0000027 to proceed only if these other transactions with these transaction ID's have already been applied to the navigation data set. If any of these dependencies has not been applied, the incremental update program will not proceed with this transaction. (For this purpose, the original navigation data set maintains a listing of the transactions that have been successfully applied to it in a header or initialization file, for example.) The transaction 0000027 listed above has a "time date" stamp of "960131,063500" which means that it was released at 6:35 A.M. on Jan. 31, 1996. The transaction 0000027 is effective as of that same date and time. The transaction 000027 has four steps. These steps provide for changing the characteristic attributes associated with the four Road Element segments that meet at the intersection of Illinois Street and McClurg Ct. In this example, each of the street segments that meet at the intersection of Illinois Street and McClurg Ct. is represented by a separate explicit object reference. For example, the segment of Illinois Street east of the intersection with McClurg Ct. has the explicit reference of "1056290"; the segment of Illinois Street west of the intersection with McClurg Ct. has the explicit reference of "1056229"; the segment of McClurg Ct. north of the intersection with Illinois Street has the explicit reference of "2847200"; and the segment of McClurg Ct. south of the intersection with Illinois Street has the explicit reference of "2847289". For each of these Road Elements, a separate step is set forth in the transaction to change the value of the Turn Restriction Attribute from "none" to "left turn prohibited". The incremental update program attempts to apply each of the four steps to the navigation data set. These steps are applied in order. First, the incremental update program finds the Turn Restriction attribute characteristic associated with the Road Element object having the Explicit Reference "1056290". This Road Element object represents the road segment of Illinois Street east of the intersection (node) with McClurg Ct. The First Step of the transaction identifies the old value of the Characteristic Attribute Turn Restriction that is to be changed ("none") and also identifies the value to which this Characteristic Attribute is to be changed ("left turn prohibited"). The incremental update program attempts to apply the First Step. If the First Step can be successfully applied, the update program proceeds to attempt to apply the Second Step, and so on, until all the Steps of the transactions are applied. In the Second Step, for example, another Road Element object is identified by means of the Explicit Reference "1056229". This Road Element object represents the road segment of Illinois Street west of the intersection with McClurg Ct. Just as in the First Step, the value "none" of the characteristic attribute Turn Restriction is changed to have the value "left turn prohibited". If any of the four Steps cannot be applied, the transaction is aborted. For example, the incremental update program may not be able to find the object with the Explicit Reference. This may occur if the data set has been corrupted or damaged. Likewise, a step cannot be applied if the Old Data State does not match the data that exists in the original data set. For example, in the First Step, the incremental update program will check the existing value of the characteristic Turn Restriction attribute associated with the Road Element that has the explicit reference "1056290". If the navigation data set being updated does not have the value "none" in the characteristic attribute Turn Restriction associated with this object, the First Step will not be applied. As mentioned above, if any of the four Steps cannot be applied, the entire transaction is not applied. Thus, if the Fourth Step cannot be applied, the First, Second, and Third Steps are not applied, and the values of the Old Data State are restored. In the example, this would mean that "none" would be restored in the characteristic attribute Turn Restriction associated with each of the three Road Element objects explicitly identified in these four steps. When completed, transaction 0000027 is added to the list of successfully applied transactions. It is intended that the foregoing detailed description be regarded as illustrative rather than limiting and that it is understood that the following claims including all equivalents are intended to define the scope of the invention.
|
Same subclass Same class Consider this |
||||||||||