EP2047386A1

EP2047386A1 - Update method for databases, particularly navigation databases

Info

Publication number: EP2047386A1
Application number: EP07787169A
Authority: EP
Inventors: Dirk Luedtke; Alexander Starke
Original assignee: Robert Bosch GmbH; Denso Corp
Current assignee: Robert Bosch GmbH; Denso Corp
Priority date: 2006-07-25
Filing date: 2007-07-06
Publication date: 2009-04-15
Also published as: DE102006034407A1; WO2008012190A1; US9378222B2; CN101558406B; US20100076928A1; JP2009545042A; JP5409357B2; CN101558406A

Abstract

A method for updating a local database (10; 11), particularly a navigation database, which is divided into segments (17; 24, 26; 28, 27; 30, 31), by transmitting an updated segment (17; 24, 26; 28, 27; 30, 31) from a central database divided into appropriate segments to the local database (10; 11) and storing the updated segment (17; 24, 26; 28, 27; 30, 31) in the local database (10; 11), avoids inconsistencies when updating is only in stages by mapping the segments (17; 24, 26; 28, 27; 30, 31) in the local database (10; 11) onto a hierarchic model and, when the segment (17; 24, 26; 28, 27; 30, 31) is updated, also updating those segments (17; 24, 26; 28, 27; 30, 31) on which the segment (17; 24, 26; 28, 27; 30, 31) is dependent.

Description

description

title

Update procedure for databases, in particular navigation databases

The present invention relates to a method for updating a decentralized

Database, in particular a navigation database, which is subdivided into segments, by transferring an updated segment from a segmented into central segments, in the central database in the decentralized database and storing the updated segment in the decentralized database.

Today's navigation systems have extensive databases in which, for example, data of a digitized map, data for entering the destination, route search and display, and route guidance are stored displaying the current position of a vehicle. Furthermore, the databases may contain additional data for driver assistance systems.

The user of a database has an interest in ensuring that the information contained in the database is as up-to-date as possible. For example, the value of a navigation database for the driver decreases if the road network underlying the database has changed or if a temporary traffic incident can not be taken into account because the navigation database contains no information on this. Another example is computer applications that rely on actual data.

Usually, a decentralized database is updated in such a way that in one

Data Center will check the availability of new data and, where appropriate, provide a new version of the database. If a new version of the database is available, it will be assembled and stored in an update database. The decentralized system, for example the navigation system in the vehicle, downloads suitable update data from this update database and integrates it into its decentralized database.

The updating of a database can be complete or partial.

A complete update has the advantage that the entire database is coordinated. The disadvantage, however, is that a complete update for the user is often associated with unnecessary cost and time. This is the case, for example, when data is transmitted that has either not changed or is not necessary for the user and the costs of

Depend on data volume.

Therefore, to reduce the amount of data required for an update step, the entire database can not be updated in a single step, but is only partially updated. For this purpose, the content of the database is divided into individual segments, for example, geographic and / or thematic aspects or a combination thereof.

However, the incremental update can cause problems because the database may lose consistency. That is, by updating a subarea, possible relationships with other segments can be resolved.

For example, it is conceivable that when updating in a segment

Road section is deleted, to which another, not updated segment with a road connection still points. Such inconsistencies must be avoided when updating in steps.

A common way to avoid inconsistencies when updating a database is to divide the database into non-overlapping segments, each of which has a version identifier assigned to it. Because of the dependencies between individual segments of the database is not every

Combining versions lead to a consistent state. Therefore, the data center and / or the distributed system must ensure that each update of the decentralized database results in a consistent combination of versions. The effort of this assurance increases with the number of dependencies between the individual segments. In order to reduce such dependencies, those segments of the database that need to be checked in an update are formed such that the number of relationships between the segments is minimized.

Another problem with updating the database in steps is the so-called avalanche effect. By this it is to be understood that although the user merely wishes to update one segment of the database, many versions of many segments of the database must also be updated to obtain a consistent combination of versions. This in turn leads to increased costs and an increased amount of time.

Avalanche effects can be limited by dividing the database into smaller segments. However, smaller segments of the database whose versions need to be reviewed will result in a larger number of such segments. This also increases the maintenance effort and the storage space required for version control.

In addition, the likelihood of so-called structural changes increases, which means adding or removing segments of the database whose versions are being checked. Structure changes can only be managed with auxiliary structures.

Against this background, it is the object of the present invention to enable an improved consistent updating of any segments of a database.

This object is achieved by a method of the type described above in that the segments are mapped in the decentralized database on a hierarchical model and when updating the segment in the decentralized database and those segments are updated, on which the segment is dependent. Updating a segment does not cause an inconsistency of the database because the segments that it depends on are also updated.

The hierarchical data structure also allows the storage of relative paths, making saving and transferring the updated segments more efficient than before - A -

takes place and the maintenance of the database is reduced. The decentralized database is expediently displayed in a tree structure.

A division into segments can be effected by determining so-called versioned nodes in the decentralized database and forming the segments from in each case one versioned node as root and all subordinate nodes which are not versioned nodes and their successors. The terms node and root are not limited to tree structures, but are generally used herein for hierarchical data structures. Thereafter, a node represents a data element or a dataset of the database.

The root of the entire database is to be understood as that node which is arranged hierarchically at the highest level of the database; root of a segment is to be understood as that node which is arranged hierarchically at the highest level within the segment. The versioned nodes are a subset of all the nodes in the data tree whose elements include the root of the tree.

The number of versioned nodes and their distribution in the database can be made in individual cases according to expediency. Suitably, the number and designation of the versioned nodes is made such that data that is likely to be updated frequently is located in segments that have no or only a few child segments. In this way, the updating of a segment can be prevented from developing into an avalanche-like update. It is also not excluded parts of the database, for example, global

Indexes to exempt from the versioning described above. These parts then have to be ensured in another way that no inconsistencies occur when updating parts of this data.

So that the versions of a certain segment can be differentiated, each segment is assigned a version identifier. For example, the version identifier may consist of an integer. There are different ways to handle the version identifier of a child segment (B) when a parent segment (A) changes: 1) the version identifier of segment (B) remains unchanged if segment (B) has not changed; the version identifier of the segment (B) is increased if the segment (B) has changed. 2) The version identifier of the segment (B) is reset

(so-called reset, for example to zero), regardless of whether the segment (B) has changed or not. The reset also resets the version identifiers of all subordinate segments of segment (A). 3) The version identifier of the segment (B) is either left unchanged or reset. The choice can be arbitrary or situational.

However, the version identifier may also contain other information, such as information about the content and format of the data within a segment and / or about the structure of subordinate segments. The version identifier is within the associated segment or in a central list of decentralized

Database saved. As a result, the version identifier of a segment is also available at later times.

In a preferred embodiment, within the data center, for each new version identifier of a segment, it is checked which versions of other segments are consistent with the new version identifier. This task can be done by a

Update compiler done. On the one hand, this makes the consistency of the decentralized

Database ensured. On the other hand, changes to the database, in particular

Content, format, and / or structure changes are made without requiring additional consistency testing within the decentralized system.

Checking for consistency requires that the version of a versioned segment be uniquely addressed. This can be done through a version path. This is a vector whose components consist of versioned versions of the versioned segment and version identifiers of all minor versioned segments. This allows dependent child versions. However, it is also possible to address the version of a versioned segment by its version identifier, for example an integer. In order to enable a high mobility of a system, for example a navigation system, with the decentralized database, the transmission of the updated segments is preferably carried out wirelessly. This can be done for example by means of a radio or radio transmission or via a mobile telecommunications connection. Alternatively, a data transfer via exchangeable storage media is also conceivable. But it is also possible to carry out the transmission of the updated segments via the Internet.

The invention will be explained in more detail with reference to the accompanying figures. Show it:

FIG. 1 shows an overview of an updating system;

FIG. 2 shows an example of a hierarchically structured database;

FIG. 3 shows schematically the addition of a subordinate update segment,

Figure 4 - schematically changing a child update segment and

Figure 5 - schematically the removal of a subordinate update segment.

The following presentation is based on a navigation system. However, the invention is not limited to navigation systems, but can be used anywhere where updated data needed and must be incorporated into a database. As an example, downloading updated versions of games or application programs from the Internet may be mentioned.

FIG. 1 shows a data center 1. The data center is used to create navigation databases. The navigation databases include, for example, information about the road network or so-called points of interest, such as locations of gas stations, hotels or attractions. The data center 1 comprises a data compiler 2, which collects data and sets. The data compiler 2 is also called a data compiler. The data compiler 2 gathers data that is necessary or useful for a navigation database, such as the aforementioned road network data. From this data, the data compiler 2 sets updates 3, 4, 5 of the raw data of the navigation

Database together. In Figure 1, the three cylinders represent three updates 3, 4, 5 of the navigation database for three consecutive years. Each update 3, 4, 5 comprises the entire database of raw data of the underlying navigation database. Changes to the data compared to an update 3, 4 of a previous year do not have to concern the entire dataset. So it is conceivable that the data of the road network changed only in a regional area, although the raw data contains the road network for a whole country.

An update compiler 6, also called update compiler, checks an update compiled by the data compiler 2 3, 4, 5, where the

Data stock has changed since the previous update 3, 4. When the update compiler 6 detects a change, it provides the update 3, 4, 5 in an update database 7. From the update database 7, this data can be transmitted to a decentralized system 8 or retrieved from the decentralized system 8.

The decentralized system 8 in the exemplary embodiment shown here is a navigation system that is installed in a vehicle. The decentralized system 8 comprises an update integrator 9, which retrieves the data from the update database and transfers it to the decentralized system 8. The update integrator 9 then updates a decentralized database 10 within the decentralized system 8, in the present case, therefore, the navigation database in the vehicle.

FIG. 2 shows a database 11 with the structure of a data tree, or more precisely a binary tree, in which at most two subordinate nodes 13 branch off from a node 12.

However, it is not a prerequisite for the present invention that the database 11 is mapped to a tree structure. All that is required is that it is a hierarchical data structure or at least a hierarchical data structure can be überfuhrt. An easy way to project a non-hierarchical data structure into a hierarchical structure is to consider the entire database as the root of a tree, with each segment of the database being treated as one directly subordinate to the root node. However, a deeper data structure may also be desired. This can be done, for example, by means of XML (Extensible

Markup Language). In this case, each XML element can be regarded as a node in the hierarchical data model.

The database 11 has two different classes at nodes 14, 15: one class forms the set of versioned nodes 14, the other class the set of the unversioned nodes 15. The number and distribution of the versioned nodes 14 within the database 11 determines the mutual Dependency of the data that must be taken into account when updating the database 11. The division into the two classes is arbitrary, with the one exception that the root 16 must represent a versioned node 13.

The versioned nodes 14 and unversioned nodes 15 are grouped into versioned segments 17. The versioned segments 17 are shown in dotted lines in FIG. Each versioned segment 17 consists of a versioned node 12, 14, 16 and possibly all of this versioned node 12, 14, 16 dependent, that is, subordinate unversioned node 15 and their non-versioned successors. Each versioned segment 17 thus contains exactly one versioned node 12, 14, 16. The significance of the versioned segment 17 is that it can only be updated as a whole, even if only some parts of its data have changed.

The database 11 will be explained in more detail below using data for a navigation database.

The root 16 of the data tree forms a highest level 18, the so-called

Database level. The root 16 represents the road map of a whole country. In a second level 19, the directory level, the node 14 represents a limited geographic area within the country. In a next level 20, the so-called file level, there is a versioned node 20 that is the node 14 is subordinate and contains information about points of interest of the geographic area represented by the node 14. The versioned node 14 has another child node 21, which contains information about road maps of the geographic area. The node 21 has a child node 22 located in a fourth level 23, the so-called element level. The node 22 contains a 3D representation of houses in the streets represented by the node 21. The data tree could also contain other levels, such as additional directory levels or attribute levels.

The following section explains in more detail how the division of the database 11 into the individual versioned segments 17 has an effect.

If the database 11 is changed so that the user is no longer interested in the points of interest of the geographic area represented by the node 14, then the versioned segment identified by the versioned node 20 as

Root is deleted, without an update of the versioned segment 17 is required. This follows from the fact that the deleted points of interest belong to a versioned segment that is subordinate to the versioned segment 17. If, on the other hand, the data for the road maps in node 21 are to be changed, the entire versioned segment 17 must be updated.

In FIG. 3, a versioned segment 24 at a specific point in time is shown in the left-hand box. The database is now updated once, which is indicated by an arrow 25. The update consists of adding a versioned segment 26 to the database. The versioned segment 26 is immediately subordinate to the versioned segment 24, that is, there are no levels between them. Each versioned segment 24, 26 carries its own version, stored either in the respective versioned segment 24, 26 or in a central list outside the versioned segments 24, 26. Before the update, the versioned segment 24 had a version identifier n, where n represents an integer. After the addition of the subordinate versioned segment 26, the version identifier of the versioned segment 24 increases by 1, that is, the versioned segment 24 now has the version identifier n + 1. The added versioned segment 26 gets the version identifier 1 because it was not previously available. Storing the versions of the individual versioned segments 24, 26 is important because the versioned segments 24, 26 can only be updated properly in stages with increasing versions. This also ensures that, knowing a version number of a versioned segment, the temporal state of that versioned segment can be reconstructed.

FIG. 4 shows a versioned segment 27 at a particular point in time, to which a versioned segment 28 is subordinate. The versioned segment 27 has the version identifier n, the versioned segment 28 the version identifier m, where m and n are integers. During an update, indicated by an arrow 29, the versioned segment 28 is changed. For this reason, the version ID of the versioned segment 28 increases by 1, so it is now m + 1. The version identifier of the versioned segment 27 remains unchanged.

FIG. 5 shows a versioned segment 30 with a versioned segment 31 at a specific point in time. The versioned segment 30 has the version identifier n, the versioned segment 31 the version identifier m, where m and n are integers. After an update, indicated by an arrow 32, the versioned segment 31 has been removed. The version ID of the versioned version

Segment 30 increases by 1 and is now n + 1.

Claims

claims

Method for updating a decentralized database (10, 11), in particular a navigation database, which is subdivided into segments (17, 24, 26, 28, 27, 30, 31) by transmitting an updated segment (17, 24, 26 28, 27, 30, 31) from a central database subdivided into corresponding segments (17, 24, 26, 28, 27, 30, 31) into the decentralized database (10, 11) and storing the updated segment (17; 24, 26, 28, 27, 30, 31) in the decentralized database (10, 11), characterized in that the segments (17, 24, 26, 28, 27, 30, 31) in the decentralized database (10; 11) are modeled on a hierarchical model and when updating the segment (17; 24, 26; 28, 27; 30, 31) also those segments (17; 24, 26; 28, 27; 30, 31) are updated, of which the segment (17; 24, 26; 28, 27; 30, 31) is dependent.

2. The method according to claim 1, characterized in that the hierarchical model has a tree structure.

Method according to claim 1 or 2, characterized in that in the decentralized database (10; 11) versioned nodes (12, 14, 16, 20, 22) are determined and the segments (17; 24, 26; 28, 27 30, 31) each comprise a versioned node (12, 14, 16, 20, 22) as root and all subordinate nodes (15, 21) which are not versioned nodes (12, 14, 16, 20, 22), and their successors are formed.

4. The method according to any one of claims 1 to 3, characterized in that each segment (17; 24, 26; 28, 27; 30, 31) is assigned a version.

5. The method according to claim 4, characterized in that the version is represented by an integer.

6. Method according to one of claims 3 to 5, characterized in that the version is stored within the associated segment (17; 24, 26; 28, 27; 30, 31) or in a central data structure of the decentralized database (10; 11) becomes.

7. Method according to one of claims 3 to 6, characterized in that within a data center (1) for each new version of a segment (17; 24, 26; 28, 27; 30, 31) it is checked which versions of other segments have the new version are consistent.