A method of updating a database of a navigation device, said database storing at least a base version of a digital map for a geographical area, said method comprising: identifying versions (6-8, 16-18) of said digital map for said geographical area which are available locally in said database or remotely from said navigation device; executing a navigation task by the navigation device, including: - selecting, based on said identified versions (6-8, 16-18), a version (7, 8, 17, 18) of said digital map for execution of said navigation task, said selected version (7, 8, 17, 18) including data stored in a plurality of storage blocks, wherein data from a sub-set (23, 25) of said plurality of storage blocks is required to execute said navigation task; wherein said executing the navigation task further includes: - selectively downloading over a wireless interface, depending on whether all storage blocks of said sub-set (23, 25) are already stored locally in said database, data stored in storage blocks of said sub-set (23, 25) which are not yet stored locally in said database, and storing said downloaded data in said database without modifying said base version of said digital map, wherein the data is downloaded when required upon execution of the navigation task; and - using said data of said sub-set (23, 25) to execute said navigation task, without prior combination with the base version of the digital map, wherein the downloaded data is limited to those storage blocks of the selected version which contain data required for execution of the navigation task and which are not yet stored locally, the method being characterised in that the navigation task includes a route search and the execution of the route search is started before the downloading is completed. identifying versions (6-8, 16-18) of said digital map for said geographical area which are available locally in said database or remotely from said navigation device; executing a navigation task by the navigation device, including: - selecting, based on said identified versions (6-8, 16-18), a version (7, 8, 17, 18) of said digital map for execution of said navigation task, said selected version (7, 8, 17, 18) including data stored in a plurality of storage blocks, wherein data from a sub-set (23, 25) of said plurality of storage blocks is required to execute said navigation task; wherein said executing the navigation task further includes: - selectively downloading over a wireless interface, depending on whether all storage blocks of said sub-set (23, 25) are already stored locally in said database, data stored in storage blocks of said sub-set (23, 25) which are not yet stored locally in said database, and storing said downloaded data in said database without modifying said base version of said digital map, wherein the data is downloaded when required upon execution of the navigation task; and - using said data of said sub-set (23, 25) to execute said navigation task, without prior combination with the base version of the digital map, wherein the downloaded data is limited to those storage blocks of the selected version which contain data required for execution of the navigation task and which are not yet stored locally, the method being characterised in that the navigation task includes a route search and the execution of the route search is started before the downloading is completed. - selecting, based on said identified versions (6-8, 16-18), a version (7, 8, 17, 18) of said digital map for execution of said navigation task, said selected version (7, 8, 17, 18) including data stored in a plurality of storage blocks, wherein data from a sub-set (23, 25) of said plurality of storage blocks is required to execute said navigation task; - selectively downloading over a wireless interface, depending on whether all storage blocks of said sub-set (23, 25) are already stored locally in said database, data stored in storage blocks of said sub-set (23, 25) which are not yet stored locally in said database, and storing said downloaded data in said database without modifying said base version of said digital map, wherein the data is downloaded when required upon execution of the navigation task; and - using said data of said sub-set (23, 25) to execute said navigation task, without prior combination with the base version of the digital map, wherein the downloaded data is limited to those storage blocks of the selected version which contain data required for execution of the navigation task and which are not yet stored locally,