(57)【特許請求の範囲】
【請求項１】
ユーザーインターフェース（３１）と；、
該ユーザーインターフェース（３１）と通信するプロセッサ（１２）と；
該プロセッサ（１２）と通信する地図データベース（４０）であって、
地図データ及び該地図データへの複数のインデックスを含む地図データベースと；
前記ユーザーインターフェースによって受信されるユーザ入力に基づいて前記地図データに対するリクエストを受け入れ、前記地図データが記憶される媒体（３２）から該地図データをアクセスしかつ地図表示のための地図データを提供することを含む、前記地図データに対する該リクエストに応答を供給する、前記プロセッサ（１２）によって使用されるデータ・アクセス・プログラミング（１８、１９）と；
前記地図データベースに関連付けられたロジック・ルール（３００）であって前記データ・アクセス・プログラミング（１８、１９）の部分ではない、ロジック・ルール（３００）と；
及び前記プロセッサによって実行される前記データ・アクセス・プログラミングの部分である演繹データベース・エンジン（２００）と、を備え、
前記演繹データベース・エンジンは、前記プロセッサによって実行され、前記ロジック・ルールにアクセスしかつ互いに組合せて、前記媒体からどの前記地図データにアクセスするかを決定するためにどの前記インデックスを用いるかを決定するためのルール・ベース（４０６）を形成することを特徴とするナビゲーション・システム。
【請求項２】
ユーザーインターフェース（３１）と；、
該ユーザーインターフェース（３１）と通信するプロセッサ（１２）と；
該プロセッサ（１２）と通信する地図データベース（４０）であって、第１のフォーマットで媒体（３２）に記憶される地図データを含む地図データベースとを備え、この場合前記第１のフォーマットが、前記地図データが前記媒体に記憶されるストレージ・フォーマットを含んでおり；さらに、
第２のフォーマットで供給されるべき前記ユーザーインタフェースによって受信されるユーザ入力に基づいて前記地図データに対するリクエストを受け入れ、前記媒体から前記地図データにアクセスし、該地図データを前記第１のフォーマットから前記第２のフォーマットに変換し、かつ地図表示のための地図データを提供することを含む、前記地図データに対する該リクエストに応答を供給する、前記プロセッサ（１２）によって使用されるデータ・アクセス・プログラミング（１８、１９）を備え、この場合、前記第２のフォーマットが、ナビゲーションアプリケーションが前記地図データを含むことができるデータフォーマットを含んでおり；さらに、
前記データ・アクセス・プログラミングの部分ではない、前記地図データベースと関連付けられたロジック・ルール（３００）と；及び
前記プロセッサによって実行される、前記データ・アクセス・プログラミングの部分である演繹データベース・エンジン（２００）とを備え、
前記演繹データベース・エンジンは、前記プロセッサによって使用されて、前記ロジック・ルールにアクセスしかつ互いに組合せて、前記地図データを前記第１のフォーマットから前記第２のフォーマットに変換する方法を決定するためのルール・ベース（４０６）を形成することを特徴とするナビゲーション・システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、地図データ用データベース・アーキテクチャに関し、特に本発明は、ナビゲーション・システムにおいて又はナビゲーション・アプリケーションによって用いる地図データ用演繹データベース・アーキテクチャに関する。
【０００２】
【従来の技術】
ナビゲーション・システムは、種々のコンピュータ・プラットフォームに供給される。あるナビゲーション・システムにおいて、ナビゲーション・アプリケーション及びハードウェアは、シングル・ユニットに組合させる。そのようなシングル・ユニット・システムは、車両に取付けられうるか又は人間によって運ばれうる。また、ナビゲーション・アプリケーションは、パーソナル・コンピュータ、パーソナル・ディジタル・アシスタント、パームパイロット(PalmPilot)型デバイス、等のような、汎用コンピュータ・プラットフォームに対して利用可能である。
【０００３】
ナビゲーション・システム及びナビゲーション・アプリケーションは、様々な有用なナビゲーション関連機能（機構・特徴）及びサービスを供給する。例えば、車両に取付けられたナビゲーション・システムは、所望の目的地までの運転に対する詳細な命令を供給することができそれにより走行時間及び費用を低減する。また、ナビゲーション・システム及びナビゲーション・アプリケーションは、所望の形式のビジネスを検索することができかつそのようなビジネスの場所へのルーティング・ガイダンスを供給する。また、ナビゲーション・システム及びナビゲーション・アプリケーションは、トラック運送会社、宅配便サービス、等のような車両部隊(vehicle fleets)のオペレータによって用いられうる。
【０００４】
種々の有用な機能を供給するために、ナビゲーション・システム及びナビゲーション・アプリケーションは、地図データを用いる。ナビゲーション・システム及びナビゲーション・アプリケーションに対して地図データを供給することに関連付けられた一つの考慮は、地図データが時代遅れに（古く）なるということである。例えば、新しい道路が造られ、ビジネスが場所を変え、道路建設が道路を閉鎖し、迂回路が設定され、博物館（美術館）及びレストランの時間が変わる、等。車両にナビゲーション・システムを有する車両の所有者のような、エンド・ユーザは、逐次更新されたナビゲーション・システムの地図データを持つことを欲するということが期待される。
【０００５】
【発明が解決しようとする課題】
ナビゲーション・システムに対する最新データを供給することに関する考慮は、異なる、非互換性のナビゲーション・システム・プラットフォームの急増である。ナビゲーション・システムの寿命の間にエンド・ユーザのナビゲーション・システムに対して最新地図データを供給するために、地図データのプロバイダは、最新地図データを有するだけでなく、エンド・ユーザの特定のナビゲーション・システム・プラットフォームと互換性があるプロダクトを供給ことが必要である。１０年以上でありうる、ナビゲーション・システムの期待される寿命の間に、これは、増大する数の古い、非互換性のナビゲーション・システム及びプラットフォームをサポートすることを必要とする。最新地図データ・プロダクトの特別バージョンが各別々の、異なるタイプ又はバージョンのナビゲーション・プラットフォームに対して製造されなければならないならば、異なるプロダクトの数は、長い年月の間、増大し続けてエンド・ユーザに対する最新地図データ・プロダクトの供給を困難かつ高価なものにする。
【０００６】
ナビゲーション・システム又はナビゲーション・アプリケーションにナビゲーション関連サービスを供給することに関連付けられた別の問題は、地図データと異なるタイプのデータを統合することである。例えば、ある人は、ディナーの予約をしかつ映画を見ることを欲しうる。ナビゲーション・システムは、所望のタイプのレストランにおける予約の可能性、種々の映画館における映画のショー・タイム（上映時間）、及びその人の場所と、所望のタイプのレストランの場所及び種々の映画館の場所との間の走行時間を考慮して、自動的に所望のタイプのレストランに予約をし、映画のチケットを取得し、かつレストランまで、そして映画館まで、それから家に戻るまでの走行のためのドライビング・インストラクション（命令）を供給する機能（特徴）を含みうるということが想像される。このような種類の機能（特徴）を供給するために、手段は、レストラン及び映画館の場所に関する地図データ、道路網での走行時間に関するデータ、レストラン予約に関するデータ、及び映画の上映時間及び予約に関するデータを組合せることを必要とする。
【０００７】
従って、ナビゲーション・システムで用いる地図データベースを更新することを供給する方法の必要性が存在する。
【０００８】
また、地図データベースに含まれる地図データと異なるタイプのデータを統合する方法の必要性が存在する。
【０００９】
【課題を解決するための手段】
これら及び他の目的に取り組むために、本発明は、ナビゲーション関連機能(navitation-related functions)を供給するために地図データを用いるデータベース・アーキテクチャを備えている。ナビゲーション関連機能は、ナビゲーション・プログラム・アプリケーションによって供給される。地図データベースは、媒体に記憶されかつ地理的特徴(geographic features)を表すデータを含みかつデータへの複数のインデックスを有する。データ・アクセス・レイヤーは、地理的参照データ(geographically-referenced data)に対してナビゲーション・プログラム・アプリケーションからのリクエストを受け入れ、地図データベースをアクセスしかつストリート・ネーム（通り名）、シティー・ネーム（都市名）、等のような地理的参照データ及び非空間的参照データを含むデータに対するナビゲーション・プログラム・アプリケーションからのリクエストに対する応答を供給する。論理規則（ロジック・ルール）は、地図データベースに関連付けられる。データ・アクセス・レイヤーは、媒体からデータをアクセスしかつそれらが媒体に記憶されるフォーマットからナビゲーション・プログラム・アプリケーションが使用できるフォーマットにデータを変換するためのインデックスの使用方法を決定するために論理規則をアクセスしかつ組合せる演繹データベース・エンジンを含む。データベース・アーキテクチャは、オフ・ボード・データ・サプライヤ(off-board data suppliers)から無線通信リンクを介して取得したデータを用いるナビゲーション・システムを含む車両ナビゲーション・システムで用いることができる。
【００１０】
【発明の実施の形態】
本発明のデータベース・アーキテクチャは、ナビゲーション・システム用データベース・アーキテクチャであって、地図データ及び該地データへの複数のインデックスを含む地図データベースと；地図的参照データに対するリクエストを受け入れ、前記地図データが記憶される媒体から該地図データをアクセスしかつ該地図的参照データに対する該リクエストに応答を供給するデータ・アクセス・プログラミングと；前記地図データベースに関連付けられたロジック・ルールと；及び前記データ・アクセス・プログラミングに関連付けられた演繹データベース・エンジンとを備え、前記演繹データベース・エンジンは、前記媒体からどの前記地図データをアクセスするかを決定するためにどの前記インデックスを用いるかを決定すべく前記ロジック・ルールをアクセスしかつ組合せることを特徴とする。
【００１１】
本発明のデータベース・アーキテクチャは、ナビゲーション・システム用データベース・アーキテクチャであって、第１のフォーマットで媒体に記憶される地図データを含む地図データベースと；第２のフォーマットで供給されるべき地図的参照データに対するリクエストを受け入れ、前記媒体から前記地図データをアクセス、該地図データを前記第１のフォーマットから前記第２のフォーマットに変換し、かつ該地図的参照データに対する該リクエストに応答を供給するデータ・アクセス・プログラミングと；前記地図データベースに関連付けられたロジック・ルールと；及び前記データ・アクセス・プログラミングに関連付けられた演繹データベース・エンジンとを備え、前記演繹データベース・エンジンは、前記地図データを前記第１のフォーマットから前記第２のフォーマットに変換する方法を決定すべく前記ロジック・ルールをアクセスしかつ組合せることを特徴とする。
【００１２】
本発明のデータベース・アーキテクチャでは、前記ロジック・ルールのそれぞれは、条件を特定する第１の部分とアクションを特定する第２の部分とを備えてもよい。
【００１３】
本発明のデータベース・アーキテクチャでは、前記演繹データベース・エンジンは、どの前記ロジック・ルールが満たされた第１の部分を有するかを決定し、満たされた前記第１の部分を有する前記ロジック・ルールのどの一つを最初に実行すべきかを決定し、かつ最初に実行すべく決定された前記ロジック・ルールの前記第２の部分で特定された前記アクションを実行するように構成してもよい。
【００１４】
本発明のデータベース・アーキテクチャでは、前記第２の部分は、プログラミング・ルーチン及び状態の変化の一つを示すようにしてもよい。
【００１５】
本発明のデータベース・アーキテクチャでは、前記条件は、前記地図データに関する本質的条件及び前記演繹データベース・エンジンによって先に決定された状態に関する付帯的条件の一つを備えてもよい。
【００１６】
本発明のデータベース・アーキテクチャでは、前記地図データは、第１のフォーマットで前記媒体に記憶されかつ前記地図的参照データに対するリクエストへの前記応答は、第２のフォーマットで供給され、かつ前記演繹データベース・エンジンは、前記地図データを前記第１のフィーマットから前記第２のフォーマットに変換する方法を決定するために前記ロジック・ルールをアクセスしかつ組合せるようにしてもよい。
【００１７】
本発明のデータベース・アーキテクチャでは、遠隔的に配置されたデータを更に備え、かつ前記ロジック・ルールは、利用可能な場合に前記遠隔的に配置されたデータへのアクセスを供給するロジック・ルールを含んでもよい。
【００１８】
本発明のデータベース・アーキテクチャでは、前記地図データベースは、更新されたデータを備え、かつ前記ロジック・ルールは、前記更新されたデータへのアクセスを供給するロジック・ルールを含んでもよい。
【００１９】
本発明のデータベース・アーキテクチャでは、前記データ・アクセス・プログラミングは、前記ロジック・ルールによって呼び出されるデータ検索ルーチンを含むインデックス・アクセス・システムを更に備え、前記データ検索ルーチンは、前記インデックスをアクセスするようにしてもよい。
【００２０】
本発明のデータベース・アーキテクチャでは、前記データ・アクセス・プログラミングは、地図データを前記第１のフォーマットから前記第２のフォーマットに変換するためにロジック・ルールによって呼び出されるデータ検索ルーチンを含む物理的から論理的への変換システムを更に備えてもよい。
【００２１】
本発明の方法は、地図データベースをアクセスするためのオペレーションの方法であって、ナビゲーション関連データに対するリスエストを受け入れる段階と；媒体に記憶された地図データベースをアクセスする段階と；前記地図データベースからデータを取得する段階と；前記リクエストに対して応答を供給するために前記地図データベースから取得した前記データを用いる段階とを具備し、前記アクセスする段階、前記取得する段階及び前記用いる段階は、前記応答を供給するために必要な全てのデータが前記地図データベースから取得されかつ応答が前記リクエストに供給されるまで、以下の段階を繰り返し実行することを含む：前記地図データベースに関連付けられたロジック・ルールをアクセスする段階；どの前記ロジック・ルールが満たされるかを決定する段階；満たされた前記ロジック・ルールのどれが最も高い優先度を有するかを結締する段階；及び前記最も高い優先度を有することが決定された前記ロジック・ルールによって特定されたアクションを実行する段階を具備する。
ことを特徴とする方法。
【００２２】
本発明のデータベース・アーキテクチャは、ナビゲーション・システム用の改良されたデータベース・アーキテクチャであって、前記データベース・アーキテクチャは、地図データ及び該地図データへの複数のインデックスを含む地図データベースを備え、更に前記データベース・アーキテクチャは、地図的参照データに対するリクエストを受け入れ、該地図データが記憶される媒体から該地図データをアクセスしかつ前記地図的参照データに対するリクエストに対して応答を供給するデータ・アクセス・プログラミングを含み、前記改良は、前記地図データベースに関連付けられたロジック・ルール；及び前記データ・アクセス・プログラミングに含まれる演繹データベース・エンジンを備え、前記演繹データベース・エンジンは、どの前記地図データを前記媒体からアクセスするかを決定するために用いる前記インデックスのどれかを決定するために前記ロジック・ルールをアクセスしかつ組合せる。
【００２３】
本発明のデータベース・アーキテクチャでは、前記ロジック・ルールのそれぞれは、条件を特性する第１の部分とアクションを特定する第２の部分とを備えもよい。
【００２４】
本発明のデータベース・アーキテクチャでは、前記演繹データベース・エンジンは、どの前記ロジック・ルールが満たされた第１の部分を有するかを決定し、満たされた前記第１の部分を有する前記ロジック・ルールのどの一つを最初に実行すべきかを決定し、かつ最初に実行すべく決定された前記ロジック・ルールの前記第２の部分で特定された前記アクションを実行するように構成してもよい。
【００２５】
本発明のデータベース・アーキテクチャでは、前記第２の部分は、プログラミング・ルーチン及び状態の変化の一つを示すように構成してもよい。
【００２６】
本発明のデータベース・アーキテクチャでは、前記条件は、前記地図データに関する本質的条件及び前記演繹データベース・エンジンによって先に決定された状態に関する付帯的条件の一つを備えてもよい。
【００２７】
本発明のデータベース・アーキテクチャは、ナビゲーション・システム用の改良されたデータベース・アーキテクチャであって、前記データベース・アーキテクチャは、第１のフォーマットで媒体に記憶される地図データを含む地図データベースを備え、更に、第２のフォーマットで供給されるべき地図的参照データに対するリクエストを受け入れ、前記媒体から前記地図データをアクセス、該地図データを前記第１のフォーマットから前記第２のフォーマットに変換し、かつ該地図的参照データに対する該リクエストに応答を供給するデータ・アクセス・プログラミングと；前記地図データベースに関連付けられたロジック・ルールと；及び前記データ・アクセス・プログラミングに含まれた演繹データベース・エンジンとを備え、前記演繹データベース・エンジンは、前記地図データを前記第１のフォーマットから前記第２のフォーマットに変換する方法を決定すべく前記ロジック・ルールをアクセスしかつ組合せる。
【００２８】
【実施例】
I.  ナビゲーション・システム − 概要
この開示の目的に対して、“ナビゲーション・システム”は、車両に取付けられたシステムを含むことが理解されている（即ち、車両搭載ナビゲーション・システム）。また、“ナビゲーション・システム”は、パーソナル・コンピュータ、ネットワーク、パーソナル・ディジタル・アシスタンス、携帯電子機器、等に取付けられたアプリケーションを含む、ナビゲーション関連機能（特徴）を供給しかつ地図データを用いるコンピュータ・プラットフォームに取付けられたソフトウェア・アプリケーションを含む。
【００２９】
本発明の実施例は、空間データベースのフィールドに意味データベース解析及び論理質問エンジン設計(logical query engine design)の原理を適用する。意味データベース（“演繹データベース”とも称する）は、ネットワーク構造において結びつくデータ及びロジック・ステートメント（論理文）のセットを規定する。質問を充たすために、演繹データベース・エンジンは、質問を充たすデータ要素を見付けるためにロジック・コネクション（論理結合）を介してネットワークを検索する。（データの）実際の読み出しは、真(true)または偽(false)のいずれかに対して評価する簡単な規則である低レベル述語(low level predicates)によって制御される。これらの低レベル述語は、次いでＣ機能(C functions)を呼び出す。偽に対して評価する述語は、データを戻さない（リターンしない）か又は不適用である。真に対して評価する述語は、一つの値又は行全体を戻す（リターンする）ことができる。
【００３０】
図１を参照すると、ナビゲーション・システム１０のブロック図が示されている。ナビゲーション・システムは、ハードウェア及びソフトウェア・コンポーネントを備えている。ハードウェア及びソフトウェア・コンポーネントは、ナビゲーション関連機能をエンド・ユーザ（例えば、ドライバ及び／又はパッセンジャ）に供給するために一緒に動作する。代替実施例において、以下に説明するように、ナビゲーション・システム１０は、車両の外部に設置されうるか又は種々の他のプラットフォーム又は環境で実施されうるけれども、図１において、ナビゲーション・システム１０は、自動車又はトラックのような、車両１１に取付けられる。ここの開示する実施例は、車両搭載システムに限定されない。
【００３１】
図１に示した実施例を参照すると、ナビゲーション・システム１０は、プロセッサ１２、プロセッサ１２に接続されたドライバ１４、メモリ２０及びナビゲーション・システムを動作するためのナビゲーション・システム・プログラミング（ソフトウェア、ファームウェア、データ、等）１８、並びに構成パラメータ１９のような、データを記憶するための不揮発性メモリ記憶装置１６を含む。また、ナビゲーション・システム１０は、測位システム・コンポーネント２４を含みうる。測位システム・コンポーネント２４は、その全てがこの分野において知られている、ＧＰＳ型技術、推測航法型システム、またはこれらの組合せ、或いは他のシステムを用いうる。測位システム・コンポーネント２４は、車両のスピード（速度）、方向、角加速度、等を測定する適当な感知（検知）装置２５を含みうる。また、測位システム・コンポーネント２４は、既知の方法で、ＧＰＳ信号を取得するための適当な技術を含みうる。測位システム・コンポーネント２４は、プロセッサ１２に信号２６を出力する。信号２６は、ナビゲーション・システム１０の場所（位置）、方向、走行距離、スピード、等を決定するためにプロセッサ１２上で実行されるプログラミング１８によって用いられる。
【００３２】
また、ナビゲーション・システム１０は、ユーザ・インタフェース３１を含む。ユーザ・インタフェース３１は、エンド・ユーザに情報をナビゲーション・システム１０に入力させる適当な装置を含む。この入力情報は、ナビゲーション・システムのナビゲーション機能を使用するためのリクエストを含みうる。例えば、入力情報は、所望の目的地へのルートに対するリクエストを含みうる。また、入力情報は、構成情報のような、他の種類の情報を含みうる。ナビゲーション・システムへ情報を入力するために用いられる装置は、キーパッド、キーボード、マイクロフォン、等、並びに、音声認識プログラムのような、適当なソフトウェアを含みうる。また、ユーザ・インタフェース３１は、エンド・ユーザに情報を戻して供給する適切な装置を含む。この装置は、ディスプレイ、スピーカ、又は他の手段を含みうる。
【００３３】
プロセッサ、ドライブ、メモリ、測位システム・コンポーネント、ユーザ・インタフェース、等を含む、これまで述べたナビゲーション・システムのコンポーネントは、ナビゲーション・システムにおいて用いられるあらゆるタイプのものでありうる。
【００３４】
ナビゲーション・システム１０は、地図データ４０を用いる。地図データ４０は、記憶媒体３２に記憶される。記憶媒体３２は、ナビゲーション・システムによって地図データベース４０を読み出しかつ用いることができるようにドライブ１４に取付けられる。記憶媒体３２は、車両が走行している地理領域に対する適当な地図データを有する記憶媒体を用いることができるように取付け自在かつ取替え自在でありうる。更に、記憶媒体３２は、その地図データ４０を容易に更新できるように取替え自在である。一実施例において、地図データ４０は、米国イリノイ州、ローズモント(Rosemont)のナビゲーション・テクノロジー・コーポレーション(Navigation Technologies Corporation)によって供給される。
【００３５】
一実施例において、記憶媒体３２は、ＣＤ−ＲＯＭディスクである。代替実施例において、記憶媒体３２は、ドライブ１４がＰＣＭＣＩＡスロットで置き換えられるような場合にはＰＣＭＣＩＡカードでありうる。固定又はハードディスク、ＤＶＤディスク又は他の現在利用可能な記憶媒体、並びに将来開発されるであろう記憶媒体を含む、種々の他の記憶媒体が用いられうる。記憶媒体３２及び地図データ４０は、代替実施例に関して以下により詳細に説明するように、ナビゲーション・システムの場所で物理的に供給されなくてもよい。代替実施例において、地図データ４０のあるもの又は全てがそれに記憶される、記憶媒体３２は、必要に応じて、通信リンクを介して供給される地図データの部分及びナビゲーション・システムの残りの部分から遠隔的に設置されうる。
【００３６】
図２を参照すると、ナビゲーション・システム１０のナビゲーション・システム・プログラミング１８に含まれるものは、ナビゲーション関連アプリケーション２８である。これらのナビゲーション関連アプリケーション２８は、種々のナビゲーション関連特徴（フューチャ）及び機能（ファンクション）を供給するために地図データ４０及び測位システム・コンポーネント２４からの出力（もし利用可能ならば）を用いる。これらのナビゲーション関連アプリケーション２８は、ルート計算アプリケーション３３、地図ディスプレイ・アプリケーション３４、ルート・ガイダンス・アプリケーション３５（詳細な方向が所望の目的地に到達するために供給される）、及び地理コーディング(geo-coding)（目的地の選択に用いられる）を含む。ナビゲーション・アプリケーション２８は、これらに追加して又は代替的に他の機能（ファンクション）又はサブプログラム３６を含みうる。例えば、ナビゲーション・アプリケーション２８は、地図マッチング機能（ファンクション）を供給する車両測位アプリケーションを含みうる。これらのナビゲーション関連アプリケーション２８は、個別のプログラムとして表されるけれども、それらは一つのアプリケーションに一緒に組合せられうる。
【００３７】
また、ナビゲーション・システム・プログラミング１８は、ユーザ・インタフェース・プログラミング３７を含む。ユーザ・インタフェース・プログラミング３７は、（図１の）ユーザ・インタフェース装置３１をサポートする。例えば、このユーザ・インタフェース・プログラミング３７は、ユーザ・インタフェース３１、メニューのディスプレイ、プロンプト、等を介してエンド・ユーザに情報のグラフィック・ディスプレイを供給する。また、ユーザ・インタフェース・プログラミングは、音声認識及び／又は記録音声セグメント又は音声合成を供給しうる。
【００３８】
また、ナビゲーション・システム・プログラミング１８は、オペレーティングシステム・プログラム３８を含みうる。オペレーティングシステム・プログラム３８は、ナビゲーション・システム１０のハードウェア・プラットフォームに適する。
【００３９】
また、ナビゲーション・システム・プログラミング１８は、データ・アクセス・レイヤー３９を含む。データ・アクセス・レイヤー３９は、媒体３２の地図データ４０をアクセスするためのプログラミングを含む。好ましい実施例において、データ・アクセス・レイヤー３９は、ナビゲーション・アプリケーション２８と地図データ４０との間、特にナビゲーション機能（ファンクション）２８とオペレーティングシステム３８との間に設置される。データ・アクセス・レイヤー３９は、以下に詳述する。
ＩＩ．  地図データベース
Ａ．  概要
図２を参照すると、地図データ４０は、一つ以上のコンピュータ読み取り可能データ・ファイル又はデータベース４２の形式で媒体３２に記憶される。地図データ４０は、特定の地図領域における又はそれに関する道路及び交差点の場所に関する情報を含みうるし、かつ、また、一方通行路及び方向転換制限、ストリート・アドレス、代替ルートに関するのような、道路及び交差点の属性に関する情報、並びにホテル、レストラン、博物館（美術館）、スタジアム、オフィス、自動車販売店、自動車修理工場、等に関する情報を含みうる。地図データベース４２の網羅領域(coverage region)は、シカゴ及びその郊外、ニューヨーク及びその郊外、ロサンジェルス及びその郊外のような、メトロポリタン・エリアを含みうるか、又は代替的に、領域エリアは、カリフォルニアのような、州全体、   アメリカ合衆国のような、国全体、又はドイツ、フランス、及びイタリアのような一つよりも多くの国、又はこれらの組合せを含みうる。一つの領域よりも多くの領域に関するデータが記憶媒体３２に記憶されうる。
【００４０】
網羅領域に対する適当な（相応な）レベルの機能性を供給するために、比較的大きなデータベースが供給される。ＣＤ−ＲＯＭディスク、ＤＶＤディスク、ハードディスク、又はＰＣＭＣＩＡカードのような、記憶媒体は、適当な機能性を供給するのに十分な大きさ及び複雑さのデータベースを取り扱うことが可能である。ナビゲーション・システムが既知の機能を実行するためにある一定の既知のかつ予想される方法で地図データを用いるので、地図データは、ナビゲーション・システムによってこれらの既知の方法でそれらの使用を容易にするような方法で編成し、構成し、及び／又は配置することができる。地図データベースにおいて地図データ４０を編成し、構成し、又は配置することができる方法のあるものは、その全体の開示がここで参考として採り入れられる米国特許第５，９６８，１０９号、第５，９７４，４１９号、及び第５，９５３，７２２号に記述される。
【００４１】
図３は、地図データベース４２の編成を示す。図３に示す編成は、データベースにおいて地図データ４０を編成することができる一つの方法を示す。種々の他の構成が可能でありかつそれらを用いることができる。図３において、地図データベース４２は、データの個別のサブセット４４を備えて示される。これらのサブセット４４は、ルーティング・データ５６、地図製作（カートグラフィック）・データ５７（地図ディスプレイ用）、操縦データ５８（ルート・ガイダンス用）、興味のある地点のデータ５９（ホテル、レストラン、博物館（美術館）、スタジアム、空港、等のような、特定の興味の地点を識別するため）、ネーム・データ６０（道路、場所及び他の特徴のネームを識別する）、場所６１（例えば、シティー（市）、ステート（州）、カウンティ（群））、郵便番号６２及び他の種類のデータ６３を含む。地図データベース４２は、異なるデータ・タイプで又はより少ない又はより多くのデータ・タイプで規定されうる。
【００４２】
地図データ４０の各サブセット４４は、特定のナビゲーション機能を実行するために必要なデータ及び関連属性を含むが機能を実行するために不要なデータ及び属性を排除する。ある情報が一つよりも多くのサブセットに含まれうるという結果を伴う、これらのサブセットのそれぞれの間でデータのオーバーラップが存在する。例えば、ルーティング・データ５６の道路区間を表しているデータ・エンティティ及び同じ地図製作データ５７の道路区間を表しているデータ・エンティティは、道路区間の終端に設置されたノード（節）を識別する属性を含みうる。この複製は、より大きな総合的データ記憶要求を結果としてもたらしうるけれども、ナビゲーション機能（即ち、図２のアプリケーション２８）のそれぞれは、より小さな量のデータを取り扱うことの合成効率によって利益を得る。
【００４３】
異なるタイプへの地図データ４０の編成は、異なるナビゲーション機能によってデータの効率的使用を供給するけれども、これらの異なるタイプを用いる異なる機能が一緒に動作することを供給する必要がある。これらのデータのタイプ４４を一緒の動作させるために、インデックス６６が地図データベース４２の一部として含まれる。インデックス６６は、相互参照、検索ツリー、及び／又は他のデータ見出し技術を供給する。インデックス６６は、データ・タイプ４４のいずれかの外部に設置することができるか又はインデックス６６は、データのタイプ４４のいずれかの内に設置されうる。地図データベース４４のこの実施例において、内部及び外部インデックスの両方を用いる。
【００４４】
Ｂ．  地図データのレイヤーリング（段彩式表現法）
それらの使用を向上させるために地図データ４０を編成することができる別の方法は、レイヤーのデータを供給することである。地図ディスプレイ・アプリケーション及びルート計算アプリケーションのような、ナビゲーション・アプリケーションのあるものは、異なるディテール（詳細・細部）のレベルのデータを用いうる。従って、データ・タイプのサブセットのあるものの内で、地図データ４０は、個別のレイヤーに供給される。
【００４５】
レイヤーリングを実施（実現）するための一つの方法は、各道路をランクに関連付けることである。道路のランクは、その機能クラス(functional class)に対応しうる。“４”のランクを有している道路は、高速道路及びフリーウェイのような、高いボリューム(high volume)の、制御アクセス道路(controlled access roads)を含みうる。“３”のランクを有している道路は、ほとんどスピード変化がない高いボリュームの道路でありうるが、制御アクセス道路である必要はない。より低くランク付けされた道路は、対応するより低いボリュームを扱い（処理し）かつ一般により多くのスピード変化又はより遅いスピードを有する。“０”のランクを有している道路は、最も低いボリュームを扱う（処理する）ことができる。例えば、これらの最も低くランク付けされた道路は、サイド・ストリート（脇道・横通り）、アリーウェイ（裏通り・路地）、等を含みうる。地図データベース４２では、道路の各部分は、個別の道路区間データ・エンティティによって表される。道路区間データ・エンティティは、のそれが表す道路区間のランクを識別する。
【００４６】
地図データベースにおいて、レイヤーは、物理的に又は論理的に実施（実現）されうる。物理的レイヤー（物理層）を供給するために、一つ以上のレイヤーに対応する個別のデータの集合又はグループが供給される。道路区間データ・エンティティのランクは、道路区間エンティティが含まれる最も高いデータ・レイヤーを決定するために用いられる。例えば、図４を参照すると、ルーティング・タイプ・データ５６は、データの５つの個別のレイヤー、Ｒ０，Ｒ１，Ｒ２，Ｒ３、及びＲ４を含みうる。これらのレイヤーのそれぞれは、ルート計算アプリケーション３３によって用いることができる、異なるディテールを有するルーティング・データの個別の集合を備えている。地図データベースのルーティング・データ５６において、レイヤー０（“Ｒ０”）は、“０”以上のランクを有している道路区間データ・エンティティ（及びそれらの対応ルーティング・データ属性のあるもの又は全て）を含む。そこで、レイヤー０は、地図領域における全ての道路の全ての部分に対応している道路区間データ・エンティティを含む。ルーティング・データ５６のレイヤー１は、ルーティング・データの個別のサブセット（又は集合）を備えかつ“１”以上のランクを有しているルーティング区間データ・エンティティ（及びそれらの対応ルーティング・データ属性のあるもの又は全て）だけを含む。ルーティング・データ５６のレイヤー２は、ルーティング・データの個別のサブセット（又は集合）を備えかつレベル“２”以上のランクを有しているルーティング区間データ・エンティティ（及びそれらの対応ナビゲーション・データ属性のあるもの又は全て）だけを含む、等。最も高いレイヤー（レイヤーｎ）は、ｎのランクを有している道路を表す記録だけを含む。他の実施例において、ｎは０よりも大きいあらゆる数でありうるけれども、本実施例において、ｎは４に等しい。各より高いレイヤーは、より少ない記録を含むが、これらの記録は、走行が一般により速い道路を表す。
【００４７】
データの他のタイプは、それぞれが異なるディテールのレベルを有する、データの個別の集合を含みうる。例えば、地図製作（カートグラフィック）・データ５７は、ルーティング・データ５６と同様なレイヤーを含む。地図製作データ５７の異なるレイヤーは、迅速なパニング及びズーミングを供給するために地図ディスプレイ・アプリケーション３４によって用いることができる。
【００４８】
レイヤーへのデータのあるももの編成は、データのある複製を結果としてもたらすけれども、レイヤーリングによって供給される増大した効率は、あらゆる欠点を一般にオフセットする。上記した個別のタイプのデータの使用によるように、これらのレイヤーを一緒の動作させることの必要性が生じる。インデックス６６は、この目的のために供給されうる。
【００４９】
上記したように、また、レイヤーリングは、論理的に実施することができる。レイヤーリングが論理的に実施される場合には、全てのランクのデータ・エンティティを含む（タイプの）データの一つの集合が供給される。しかしながら、（データ・アクセス・レイヤー３９における）フィルタリング・ルーティンは、より高いランクの道路だけが望ましい場合にはより低いランクの道路を表しているデータ・エンティティを抑制する。
【００５０】
Ｃ．  地図データのパーセライゼーション
ナビゲーション・システムによる地図データ４０の使用を容易にするために用いることができる別の方法は、データをパーセライズ(parcelize)することである。所与の地図領域全体に対するデータ記録の全てが同時にナビゲーション・システムのメモリにロードされないと想定すると、所望の機能を実行するために必要なそれらのデータだけをメモリにロードすることが望ましい。これを達成するために、地図データ４０は、ナビゲーション機能を実行するために媒体からデータをアクセスしかつ読み出すために必要な時間の量を最小化するように編成される。これを供給するために、データ４０は、パーセルに編成される。データがパーセライズされる場合には、地図データベース４２を一緒に構成する複数のデータ記録は、個別のグルーピング又はパーセルに一緒にグループにされる。図６は、パーセル９０に編成された地図データ４０を示す。データのパーセル９０は、パーセルの全てのデータが媒体３２から同時に一緒にアクセスされるように設定される。それが他の要因（ファクタ）に関連しうるけれども、これは、一つのディスク・アクセスでアクセスすることができるデータの量に関係しうる。ＣＤ−ＲＯＭディスクのようなあるタイプの媒体に対して、パーセルは、データの１６キロバイト量であるべく設定されうる。図６に示すように、地図データ４０及び地図データ４０に対するインデックス６６は、個別のパーセル９０に形成されうる。インデックス６６のパーセルは、グローバル部分９１のような、データベース４２の個別の部分に設置されうる。また、インデックスは、データ・タイプ４４のそれぞれの内に含まれうる。例えば、地図データ４０の各パーセル９０内に一つ以上のインデックスが存在しうる。
【００５１】
パーセライゼーションに関連して、それらの使用を容易にするために地図データのあるものを編成することができる別の方法は、データを空間的に編成することである。地図データが空間的に編成される場合には、地図領域において物理的に隣接する特徴は、データベースにおいて物理的（又は論理的）に隣接するデータ記録によって表される。地図データは、これらの技術の両方の利点を取るためにパーゼライズしかつ空間的に編成することの両方ができる。
【００５２】
パーセルにデータを形成する目的に対して、上述したように、データは、異なるタイプ４４にまず個別に編成されうる。これらのタイプのデータのあるものは、ナビゲーション・アプリケーション２８によるデータの使用を容易にするために空間的にパーセライズされうる。空間的にパーセライズされたデータは、地図的に近似な特徴を表すデータが   データベース４２及び／又は媒体３２で論理的及び／又は物理的に近似に設置されるように配置される。ナビゲーション・アプリケーションｐのあるものに対して、データの空間パーセラゼーションは、媒体からより迅速に必要な地図データを読み出しこと及びそれらを用いることができるメモリに関連データをロードすることを供給する。この種の編成は、記憶媒体３２でシークすること(seeking)を最小にしかつこれらのナビゲーション機能のオペレーション（動作・操作）をスピードアップしうる。ルーティング、カートグラフィック、及び興味がある地点のデータは、空間的に編成されうるデータの種類の中に含まれる。
【００５３】
空間的に編成された地図データをパーセライズするために用いることができる多数の異なる手順が存在する。例えば、簡単なパーセライゼーション方法は、各パーセルのデータが矩形、地図データに関する矩形グリッドを一緒に形成する複数のレギュラー・サイズの矩形の個別の一つの内に包含された特徴を表すように、地図データを複数のパーセル又はグルーピングに分けることを供給しうる。パーセライゼーションの別の方法は、最大スレショルド以下のパーセル・サイズが得られるまで、データを矩形のそれぞれが領域の部分を包含している矩形の二分によって形成される矩形地域内に包含されたパーセルに分けることである。更に、パーセライゼーション手順は、全体の開示がここに参考として採り入れられる１９９６年１０月２５日に出願した同時係属中の米国特許出願第０８／７４０，２９５号に開示され、そしてまたパーセライゼーション手順は、全体の開示がここに参考として採り入れられる米国特許第５，９５３，７２２号公報に開示されいる。開示されている対象を適用することができるパーセライゼーションの更に別の方法は、米国特許４，８８８，６９８号公報に開示されている。
【００５４】
図５及び６を参照して、空間的に編成されたデータのパーセライゼーションを説明する。図５は、地図領域１１２の地図１１１を示す。（ドットまたは点で表される）複数のポジション１１６が地図１１１に設置（配置）されるべく示されている。ポジション１１６のそれぞれは、図６の地図データベース４２に含まれる情報に関する特徴が設置（配置）される地図領域１１２の場所又は点を表す。例えば、ポジション１１４は、地図データベース４２におけるデータによって表される、道路区間の端点の物理的位置（ロケーション）、道路区間に沿った点、（ホテル、シビック・センター等のような）興味がある地点に対応しうる。これらのロケーション１１６のそれぞれは、固有の物理的ロケーション（緯度、経度、及びオプショナルな絶対的又は相対的標高）を有しかつロケーション１１６のそれぞれは、その二次元（又は三次元）地図座標（即ち、緯度、経度、及びオプショナルな標高）によって独自に識別されうる。
【００５５】
図５において、グリッド１１７は、地図１１１によって表される地図領域１１２の上に横たわる。グリッド１１７は、地図領域１１２を複数の矩形地域（エリア）１１９に分割する。これらの矩形地域１１９は、全て同じ大きさでありうるか又はパーセライゼーションに用いられる手順により異なる大きさを有しうる。グリッド１１７のグリッド線は、矩形地域１１９の境界を表す。境界のロケーション(位置)は、用いられるパーセライゼーション手順に依存しうる。一般に、空間パーセライゼーションに対する手順のいずれかを用いる場合には、各矩形地域１１９内に包含される特徴を表す特定のタイプのデータのデータ記録は、データの個別のパーセルに一緒にグループにされる。従って、（図６の）空間的に編成されたデータの各パーセル９０は、（図５に示すように）複数の矩形１１９の個別の一つの内に包含された地図特徴を表す一つ以上のデータ記録を含む。
【００５６】
図６に示すように、次いでパーセル９０は、各パーセル９０のデータが論理的及び／又は物理的に一緒にグループにされるようにデータベース４２を形成するために記憶される。パーセルは、ナビゲーション・システムによって媒体から同時にアクセスされるデータの量を表すので、データのパーセルがアクセスされる場合には、そのデータ記録の全てが同時にナビゲーション・システムのメモリに読み込まれる。図５の地図１１１を参照すると、これは、各矩形１１９内に包含された空間的に編成されたデータのタイプの全てのデータ記録がグループとして一緒にアクセスされるということを意味する。ある一定の種類のナビゲーション機能に対して、地図領域において物理的に隣接する特徴を表す全てのデータ記録を同時にメモリに有することが望ましいということを理解することができるであろう。
【００５７】
これらのタイプのデータに対してパーセル９０が形成されると、パーセルがオーダされる。種々のタイプのオーダリング(ordering)が用いられうる。一般に、データに対する検索を最小にするようにパーセルがオーダされることが好ましい。空間的に編成されたパーセルをオーダする一つの方法は、各データのタイプ内のｋＤ−ツリー・インデックスからの深さ優先オーダリングを用いることである。これは、ペアノ−キー(Peano-key)・オーダリングと同様なオーダリングを供給する。パーセルは、この近似ペアノ・キー・オーダにおいてディスク（即ち、図１及び２の媒体３２）に記憶されうる。空間的にパーセルをアクセスするためにｋＤ−ツリーのような、一つ以上のインデックスを用いることができる。このインデックスは、ナビゲーション・システムのプログラムが現在の車両のポジションに対応しているデータに最初設置される場合のような、任意のポジションの初期ロケーションに対して有用である。パーセルがオーダされると、それぞれは、また、固有のパーセル識別子（例えば、“パーセルＩＤ”が割り当てられる。パーセルＩＤは、パーセル及び／又は媒体上のパーセルのロケーションを識別するために用いられうる。
【００５８】
上記したように、ある種のデータは、空間的に編成されない（即ち、非空間的に編成されたデータの各パーセルは、図５の矩形地域１１９のいずれかに対応する必要はない）。例えば、ストリートのネーム（即ち、図３のネーム・データ６０）を表すデータは、空間的の代わりにアルファベット順に編成されうる。国、州、市、等のような行政的または政治的エンティティを表すデータは、空間的に編成されない他の種類のデータである。例えば、行政的または政治的エンティティを表すデータは、行政的権力層(administrative hierarchy)によって編成されうる。本実施例において、これらの非空間的に編成されるデータのタイプは、同様にパーセライズされる。
【００５９】
ＩＩＩ．  データ・アクセス・レイヤー
Ａ．概要
図２に関して上記したように、ナビゲーション・システム・プログラミング１８は、ナビゲーション・アプリケーション２８に対して地図データ４０をアクセスすることを供給するデータ・アクセス・レイヤー３９を含む。上述したように、地図データベース４２のデータ４０は、種々のナビゲーション・アプリケーション２８によるそれらの使用を容易にするために媒体３２上で圧縮され、配列（アレンジメント）され、編成され、パーセライズされ、かつインデックスされうる。データ・アクセス・レイヤー３９は、ナビゲーション・アプリケーション２８による使用のためのデータを戻すために記憶媒体３２の地図データベース４２の編成及び配列を取り扱う。
【００６０】
データ・アクセス・レイヤー３９は、ナビゲーション・アプリケーション２８と地図データベース４２との間に論理的に設置（位置決め）される。一実施例において、データ・アクセス・レイヤー３９及びナビゲーション・アプリケーション・プログラム２８は、他のタイプのコンパイレーション及び／又は配列を用いうるけれども、一つの実行可能なモジュールを形成するために一緒にコンパイルされる。
【００６１】
図７を参照すると、データ・アクセス・レイヤー３９は、幾つかのサブシステム・コンポーネントで構成されている。図７において、データ・アクセス・レイヤー３９は、演繹データベース・エンジン２００、アプリケーション・インタフェース２２０、問合せ検証(query validation)システム２４０、インデックス・アクセス・システム２６０、物理的から論理的への変換(physical-to-logical conversion)システム２８０、及びカーソル管理システム２９０を含む。これらのサブシステム・コンポーネントのそれぞれは、ある一定の機能を実施するプログラミングで構成されている。これらのサブシステム・コンポーネント間に内部インタフェースが存在する。これらのコンポーネントのそれぞれを以下に詳述する。
【００６２】
（本実施例のデータ・アクセス・レイヤー３９は、全体の開示がここに採り入れられる１８８６（１９８６）年１０月２５日に出願された米国特許出願第０８／７４０、２９８号に開示されたデータ・アクセス・レイヤーと同様である。本実施例のデータ・アクセス・レイヤー３９が米国特許出願第０８／７４０、２９８号に開示されたデータ・アクセス・レイヤーとは異なる方法がここに開示されている。これらの相違を除き、本実施例のデータ・アクセス・レイヤー３９は、米国特許出願第０８／７４０、２９８号に開示されたデータ・アクセス・レイヤーと同様でありうる。）
Ｂ．データベースに記憶されるロジック・ルール（論理規則）
図７は、ロジック・ルール（論理規則）３００を示す。ロジック・ルール３００は、地図データベース４２に関連付けられる。ロジック・ルール３００は、データ・アクセス・レイヤー３９に一部ではない。図７に示すように、ロジック・ルール３００は、媒体３２の地図データベース４２に記憶される。代替実施例では、ロジック・ルール３００は、以下に説明するように、それ以外に記憶されうる。
【００６３】
図８は、幾つかのロジック・ルール３００のコンポーネントを示す。各ロジック・ルール３００は、ヘッド３０６及びボディー３０８により構成されている。ロジック・ルール３００のヘッド３０６は、一つ以上のステートメント（文）を含む。各ステートメントは、一つ以上の変数を含みうる。定数は、変数に対して置換えることができる。変数は、あらゆる値を取ることができるということを意味する“自由変数”でありうる。
【００６４】
各ステートメントは、真であるか又は真でないかのいずれかを評価することができる。ルールのヘッド３０６内のステートメントは、論理関係オペレーション（例えば、“アンド(and)”、“オア(or)”、“ノット(not)”、等）と組合される。
【００６５】
各ステートメントは、地図データベースのデータ又はナビゲーション・システムの状態のいずれかに関する。データベース４２からのデータ４０に関するステートメントは本質的(intrinsic)であり、かつナビゲーション・システムに関するステートメントは付帯的(extrinsic)である。ナビゲーション・システムの“状態”は、他のロジック・ルールの先に実行及びデータベースのデータによって決定されるようなナビゲーション・システムの現在のしかし変更可能な状態を表す。
【００６６】
各ロジック・ルール３００のボディー３０８は、取るべき一つ以上のアクション（動作）を特定する。アクションは、（物理的から論理的へのシステム２８０、インデックス・アクセス・システム２６０、又は検証システム２４０における機能のような）機能への呼出し（コール）でありうる。また、ロジック・ルールのボディーにおいて特定されたアクションは、ナビゲーション・システムの状態を設定または変更することができる。
【００６７】
ロジック・ルール３００は、媒体３２で圧縮されうる。ロジック・ルール３００は、演繹データベース・エンジン２００によるルールの使用及びアクセスを容易にするように編成されうる。
【００６８】
Ｃ．  演繹データベース・エンジン
再び図７を参照すると、演繹データベース・エンジン２００は、地図データベース４２に含まれるデータ４０をアクセスし及び／又は用いる方法を決定するために地図データベース４２に関連付けられたロジック・ルール３００を用いる。
【００６９】
図９は、演繹データベース・エンジン２００の実行サイクル４００で実行される段階を示す。演繹データベース・エンジン２００の実行サイクル４００は、ナビゲーション・システムのオペレーションの間中、連続的にループする。
【００７０】
演繹データベース・エンジン２００内では、処理４０２は、ルール・ベース４０６を形成（及び更新）する。システムの動作（挙動）を支配している全てのルールは、ナビゲーション・システムのある状態に適するルールを迅速に見付けるためにメカニズムと一緒にグループにされ、ルールのグループは、“ルール・ベース”と呼ばれる。ルール・ベースは、動的一時構造である。ルール・ベース４０６を形成することにおいて、処理４０２は、必要な程度まで、媒体３２からロジック・ルール３００を読み出し、地図データベース４２からデータ４０を取得し、かつナビゲーション・システムの状態に関する他のデータ４０３を取得する段階を含む。これらのルール及びデータを用いて、処理４０３は、ルール・ベース４０６を構成するルールを形成する。媒体３２に記憶される全てのロジック・ルールは、演繹データベース・エンジン２００に対して利用可能である。しかしながら、処理４０２は、媒体３２からのロジック・ルール３００のどれをルール・ベース４０６に含むべきかを決定する。媒体３２からのロジック・ルール３００の全てをルール・ベース４０６に含むことを必要としない。
【００７１】
ルール・ベース４０６に含まれるルールのあるものは、個別のロジック・ルールからのステートメントを組合せることによって形成されうる。ステートメントを組合せる処理は、全ての述語がデータベースのエレメント（構成要素）を参照するまでルールのステートメントをより簡単なステートメントで置き換える。ステートメント組合せ処理は、ルール・ベース形成処理の内部部分（例えば、図９の４０２において示すような）によって実行されうる。代替的に、ステートメント組合せ処理は、演繹データベース・エンジン実行サイクルによって実行されうる（例えば、ステップ４０２−４２０）。
【００７２】
演繹データベース・エンジンの実行サイクル中に新しいルールをルール・ベースに追加することができる。また、演繹データベース・エンジンの実行サイクル中にルール・ベースからルールを削除することができる。
【００７３】
一度ルール・ベース４０６を形成する全てのルールが決定されたならば、演繹データベース・エンジン３００の処理４０８は、ルール・ベース４０６からのどのルールが満たされているか、即ち、ロジック・ルールのヘッド３０６において特定された事前条件（プレコンディション）が“真”であるかを決定する。一つのサイクルにおいて実行が可能な幾らかのルールが存在しうる。（ルール・ベース４０６からの）ルールのヘッドが論理的に真なステートメントである場合には、そのルールが実行されうるルールのリストに追加される。満たされた（ルール・ベース４−６からの）このルールのセットは、候補リスト４１２を形成する。（候補リストのこのルールのセットは、演繹データベース・エンジンの各実行サイクルに対して形成（又は更新）される。）
候補リスト４１２のロジック・ルールで、演繹データベース・エンジン３００の別の処理４１４は、候補リスト４１２からどの一つのロジック・ルールを実行すべきかを決定する。どのルールを“ファイヤー”（即ち、実行）すべきかの選択は、どのように特定的にルールが現在の状態に適用されるか、どのくらいルールが重要であるかが宣言され、どのくらい最近にルールが以前ファイヤーされたか、等のような、候補ルールに関する情報を考慮することによってなされる。これは、ルールのオーダリングによって又はあるタイプのルールを他のものよりも優先する演繹データベース・エンジンの構成（即ち、より多くのルール）によって決定することができる。
【００７４】
候補リスト４１２の中からどのルールをファイヤするかを決定した後、演繹データベース・エンジン２００は、ルールのボディー３０８で特定されたアクションを実行する処理４２０を含む。ボディー３０８で特定されたアクションは、物理的から論理的への変換システム２８０、インデックス・アクセス・システム２６０、又は検証システム２４０におけるルーチンを参照することができる。また、アクション３０８は、状態の変更を特定することもできる。ボディー３０８で特定されたアクションが物理的から論理的への変換システム２８０、インデックス・アクセス・システム２６０、又は検証システム２４０におけるルーチンを参照するならば、ルーチンが呼び出されかつ実行される。ルーチンが実行された後、ルーチンは、演繹データベース・エンジン２００へ戻りかつ演繹データベース・エンジン２００のオペレーションは、ステップ４０２へ折り返す（ループ・バック）ことによって継続する。ボディー３０８において特定されたアクションが状態の変更のためであるならば、状態が変更されかつ（状態変数４０６に）保管されそして演繹データベース・エンジン２００のオペレーションは、ステップ４０２へ折り返す（ループ・バック）ことによって継続する。
【００７５】
演繹データベース・エンジン２００のオペレーションは、このように継続する。
【００７６】
Ｄ．ルールとしてのデータの処理
演繹データ・モデルでは、データベース４２のデータの各行（ロー）（即ち、各“記録”）は、ナビゲーション・システムの状態の一部と考えられる。そこで、各行は、データ・テーブルにおける列（カラム）と同じ位多くの部分を含むロジック・ステートメントであると考えられる。例えば、レストラン及びそれらのロケーションの表は、“ネーム”、“料理”、“緯度”、“経度”、“番地”、及び“ブロック”の列（カラム）（即ち、“フィールド”）を有しうる。この例では、“ブロック”は、ストリート・ネーム及びシティーを含む記録の表への行番号である。ルートとして処理された、レストラン表の行は、“ネーム”が“New China Restaurant（ニュー・チャイナ・レストラン）”に等しくかつ“Cuisine（料理）”が“Chinese（中国料理）”に等しく“緯度”が“ｎｎｎ’ｍｍｍ”に等しくかつ“経度”が“ｑｑｑ’ｒｒｒ”に等しくかつ“番地”が“１１８５”に等しくかつ“ブロック”が“２３４５”に等しいようになる。データベースの演繹問合わせは、ルールのボディーがシステムの状態を変更することができるようにルールのヘッドに“真”であると考慮させるデータに対する検索として処理される。行がルールのヘッドを‘真’にさせるように検索される場合には、行の全ての列（カラム）値は、システム状態を変更するためにルールのボディーに利用可能である。
【００７７】
一度行が検索されたならば、それは、別の行がファイヤするまでそれを検索したルールをファイヤする権利がない。そこで、全ての中国料理レストランを検索する問合せは、“Restaurant.Cuisine = 'Chinese' and Block.BlockID = Restaurant.Block = > print(Restaurant.Name, Restaurant.AddressNumber, Block.StreetName, Block.City)”のようになる。選択されたデータを含むデータベースの行が再びファイヤすることを許されていないので、このルールは、レストラン表の中国料理レストラン毎に一度ファイヤされる。
【００７８】
データベースのインデックス（例えば、図３のインデックス６６）は、まったくデータのように処理されかつ同じルール及び問合わせエンジンで問合せされる。
【００７９】
リレーショナル・データベースに対する演繹データベースの利点は、列が簡単なタイプとしてではなくセットの構成要素（エレメント）として規定されるということである。レストラン表のブロック列(Restaurant table's Block column)は、を別の表のＩＤであるよりもブロック・データ(Block data)のセット全体を含みうる。
【００８０】
Ｅ.アプリケーション・インタフェース
図７を再び参照すると、アプリケーション・インタフェース２２０は、ナビゲーション・アプリケーション２８とインタフェースする。アプリケーション・インタフェース２２０は、ナビゲーション・アプリケーション２８からの地図的参照データ(geographically-referenced data)に対するリクエストを受け入れかつリクエストに対して応答を供給する。アプリケーション・インタフェース２２０は、ナビゲーション・アプリケーション２８に機能呼出しインタフェース(function call interface)を供給する。機能呼出しインタフェースは、ナビゲーション・アプリケーション・プログラム２８に対する記憶媒体３２の地図データのデータ構造ビュー（“ロジカル・データ・モデル”又は“ＬＤＭ”と称する）を規定する。ロジカル・データ・モデルは、相互参照することなく完全に圧縮解除された形式のデータ又はデータを用いることができる前に処理を必要とする他のタイプの情報を表す。一実施例において、アプリケーション・インタフェース２２０によって規定されるデータ構造ビューは、Ｃ言語である。
【００８１】
Ｆ．問合せ検証システム
上記したように、データ・アクセス・レイヤー・コンポーネント３９は、データ検証システム２４０を含む。データ検証システム２４０は、ナビゲーション・アプリケーション２８からアプリケーション・インタフェース２２０によって受取ったリクエストをチェックする。問合せ検証システム２４０は、ナビゲーション・アプリケーション２８からの地図的参照データ・リクエストが有効かどうかを決定することをチェックする。機能２４０は、それによってデータに対する有効リクエストを決定することができるデータを受取る。機能は、演繹データベース・エンジン２００からこれらのデータを受取る。演繹データベース・エンジンがオペレーションを開始する場合には、それは、その目的のために設計された一組のロジック・ルールを用いて初期化される。これらの初期化ロジック・ルールは、媒体に存在するデータ及びインデックスのタイプを識別しかつ結果としてどのようなタイプの問合せがサポートされるを識別する。これらの初期化ロジック・ルールを用いて、サポートされる問合せおよびデータ・タイプの表を準備することができる。この表は、地図的参照データに対するリクエストがナビゲーション・アプリケーション２８によってリクエストされる場合に問合せ検証システムによって用いられる。
【００８２】
Ｇ．インデックス・アクセス・システム
インデックス・アクセス・システム２６０は、データ・アクセス・レイヤー３９の一部である。インデックス・アクセス・システム２６０は、媒体３２の地図データベース４２のインデックス６６をアクセスしかつ用いるためのデータ検索ルーチン２６２を含む。インデックス６６は、アプリケーション・インタフェース２２０によって受取った地図的参照データに対するリクエストを満たすために媒体に記憶されたデータを探し出すために用いられる。インデックス６６は、媒体の一つ以上のどのパーセルが地図的参照データに対するリクエストに応答するために必要なデータを含むかを識別するために用いられうる。これは、所望のデータのパーセルが媒体に配置（設置）されるアドレス・ロケーション又はファイル・オフセットの識別を含みうる。また、インデックス６６は、各パーセル内の所望のデータのロケーションを決定するために用いられうる。
【００８３】
上記したように、インデックスは、ルール・ベース４０６の別のルールになりかつ更なるメカニズムなしでそれに対してマッチ（整合）される。問合せにおけるターム（用語）としてインデックスを用いる方法を示すルール・ベースにロジック・ステートメントを加えることによってインデックスをアコモデートすることができる。
【００８４】
データ検索ルーチン２６２は、低レベル・データ・アクセス・プリミティブとして作用（動作）する。インデックス・アクセス・レイヤー２６０のデータ検索ルーチン２６２は、一般的である、即ち、それらは、データベース４２又はインデックス６６に対して特定されない。その代わり、媒体のインデックス６６のロケーション、インデックスのタイプ、インデックスによって関連するデータのタイプ、インデックス・キー、等は、インデックス・アクセス・システム２６０のデータ検索ルーチン２６２が演繹データベース・エンジン２００によって呼び出される場合に含まれるパラメータによって特定される。演繹データベース・エンジン２００は、上述したように、ロジック・ルール３００を読み出しかつ組合せることによってインデックス・アクセス・システムのデータ検索ルーチン２６２を呼び出す場合に用いられるパラメータをフォーミュレート（公式化）する。
【００８５】
Ｈ．物理的から論理的への変換
物理的から論理的への変換システム２８０は、データ・アクセス・レイヤー３９の別の部分である。物理的から論理的への変換システム２８０は、それら（データ）が媒体に記憶されるフォーマットからナビゲーション・アプリケーションがそれら（データ）を用いることができるようなフォーマット（例えば、論理的データ・モデル・フォーマット）にデータを変換するためのデータ検索ルーチン２８２を含む。インデックス・アクセス・システム２６０のデータ検索ルーチン２６２のように、物理的から論理的への変換システム２８０のデータ検索ルーチン２８２は、低レベル・データ・アクセス・プリミティブとして動作（作用）する。物理的から論理的への変換システム２８０のデータ検索ルーチン２８２は、一般的である、即ち、それらは、データベース４２のデータのタイプに特定されない。その代わり、記録のサイズ、記録のロケーション、相互参照情報、必要な解凍及び／又はアンパッキング、等は、データ検索ルーチン２８２が演繹データベース・エンジン２００によって呼び出される場合に含まれるパラメータによって特定される。演繹データベース・エンジン２００は、ロジック・ルール３００を読み出しかつ組合せることによってデータ検索ルーチン２８２を呼び出す場合に用いられるパラメータをフォーミュレート（公式化）する。
【００８６】
Ｉ．カーソル
カーソル管理システム２９０は、データ・アクセス・レイヤー３９の一部である。ナビゲーション・アプリケーション２８からの地図的参照データに対するあるリクエストは、多重データ・エンティティを含む応答を結果としてもたらすことが期待される。例えば、特定の境界を示す矩形地域内の道路を表している全てのカートグラフィック・データ記録に対するリクエストは、数百の（多くの）データ記録を含みうる。カーソル管理システム２９０は、多重記録を含むナビゲーション・アプリケーション２８への応答を取り扱うことを供給する。
【００８７】
演繹データベース・エンジンの一実施例において、結果が得られかつ一度に一つの処理がなされる。地図データベースのデータの問合せは、演繹データベース・エンジン２００によるロジック・ルール３００の実行によって呼び出されるインデックス・アクセス管理システム２６０のルーチン２６２によって実行される。問合せは、問合せを規定するロジック・ルールによって命令（口述）されるように、地図データベースのデータの全て又は一部で実行されうる。データ記録のセット内には、問合せを満たすセットの第１の記録は、物理的から論理的への変換システム２８０の適当なルーチン２８２を用いて処理される。演繹データベース・エンジンによって実行される別のロジック・ルールは、第１の記録が問合せを満たすことが見出された後に、問合せは、問合せを満たすセットにおける次の記録を見出す、等、もはや問合せを満たすセットにおいて記録が見出されなくなるまでその地点からセットにおいてフォワードに継続するように、“GetNext”オペレーションを実行する。
【００８８】
カーソル管理システム２９０は、バッファリング及びゲートキーピング機能を実行する。カーソル管理システム２９０は、多重記録を含むナビゲーション・アプリケーション２８への応答を取り扱う。結果のセットが大きい場合には、カーソル管理システム２９０は、ナビゲーション・アプリケーションがキャッチ・アップできるまで演繹データベース・エンジンにより“GetNext”オペレーションを一時的に停止することができる。また、カーソル管理システム２９０は、メモリ・バッファに多重結果を一時的に記憶することができる。
ＩＶ．アプリケーション
Ａ．更新データを供給すること
図１０は、ナビゲーション・システムに新しいデータを供給できる方法を示す。図１０は、図１に関して説明された同じナビゲーション・システム１０を示す。ナビゲーション・システム１０は、図７〜図９に関して上述したように、演繹データベース・エンジン２００を有するデータ・アクセス・レイヤー３９を含んでいるナビゲーション・システム・プログラミング１８を含む。図１０において、先の地図データベース（例えば、図７の４２）は、新しい地図データベース５４２（例えば、バージョン２．０）で置き換えられている。新しい地図データベース５４２は、新しい媒体５３２に記憶されるか、または代替的に、新しい地図データベース５４２は、新しい地図データ５４０を含む。新しい地図データ５４０は、先の地図データ４０と同じ地図網羅地域に関する。代替的に、新しい地図データ５４０は、異なる地図網羅地域に関しうる。
【００８９】
新しい地図データベース５４２は、新しいタイプのデータを含みうる。例えば、地図データベース４２の先のバージョンは興味のある地点の電話番号を示すデータ含んでいたが、新しい地図データベース５４２は、また、興味のある地点のファックス番号、電子メール・アドレス及びウェブ・アドレスを示すデータを含む。更に、新しい地図データベース５４２は、また、古い及び新しいタイプのデータを相互参照するために用いることができる新しいインデックス５６６を含む（例えば、そこで興味のある地点を、そのファックス、電子メール、及びウェブ・アドレスによって見出すことができるし、その逆もできる）。
【００９０】
新しい地図データベース５４２の新しい地図データ５４０及びインデックス５６６に関連付けられるものは、新しいロジック・ルール５５０である。新しいロジック・ルール５５０は、新しい地図データベース５４２と同じ媒体５３２に配置（設置）されるかまたは代替的に、新しいロジック・ルール５５０は、異なる媒体に配置されうる。
【００９１】
新しいロジック・ルール５５０は、上述した先のロジック・ルール３００と同じ構造を有する。従って、各新しいロジック・ルール５５０は、先のロジック・ルール２００のように演繹データベース・エンジン２００によって同じように処理することができる。新しいロジック・ルール５５０は、新しいデータベース５４０のデータ５４０及びインデックス５６６に関する。従って、新しいロジック・ルール５５０は、新しい地図データベース５４２に含まれる新しいタイプのデータ、データ記憶される媒体５３２の新しいロケーション、先のタイプのデータ又は新しいタイプのデータのいずれかに関する新しいインデックス、等を説明する。例えば、媒体の興味がある地点のデータ記録のロケーションが変わったならば（例えば、興味がある地点のデータがより多く記憶されるので）、媒体上の新しいロケーションは、ロジック・ルール５５０によって特定される。そこで、演繹データベース・エンジン２００が興味がある地点に対する問合せに対して応答するためのデータを取得するために動作される場合には、それは、媒体上の興味がある地点のデータを探し出すために新しいロジック・ルールを用いる。
【００９２】
また、新しいロジック・ルール５５０は、新しい表を追加することを説明する。新しい表を追加することは、表に対するデータを追加すること及び表が既存のデータに接続する方法を示しているロジック・ルールのステートメントを追加することから構成される。既存の演繹データベース・エンジン２００は、データを検索する場合に新しいロジック・ルールのこれらの新しいステートメントをアクセスする。
【００９３】
データ・アクセス・レイヤー３９に含まれる演繹データベース・エンジン２００は、フォワード互換性を供給する。演繹データベース・エンジンを含むデータ・アクセス・レイヤーを有しているナビゲーション・システムは、ここの説明するように、更新された地図データ並びに新しいタイプのデータの両方を含む地図データベースの新しいリリースをアクセスしかつ用いることができる。これは、地図データベースの同じ新しい、更新されたバージョンを新しい及び古いナビゲーション・システムの両方で供給しかつ用いることができるという利点を供給する。
【００９４】
演繹データベース・エンジンを含むデータ・アクセス・レイヤーは、また、バックワード互換性を供給することができる。データ・アクセス・レイヤーの演繹データベース・エンジンにより、新しいナビゲーション・システムは、古いバージョンの地図データを用いることができる。これは、ナビゲーション・システム製造業者が、データが利用可能である前に新しいタイプのデータを用いるシステムを設計することができるという利点を供給する。これらのナビゲーション・システムは、新しいタイプのデータを含む新しいバージョンの地図データベースが利用可能になるまで現在利用可能なバージョンの地図データベースで実行することができる。新しいタイプのデータを有する新しいバージョンの地図データベースが利用可能になった場合には、新しいバージョンの地図データベースをナビゲーション・システムに取付けることができ、次いでそれ（ナビゲーション・システム）は、新しい種類のサービスを供給するために新しいタイプのデータを用いることができる。
【００９５】
Ｂ．オン・ボード及びオフ・ボード・データを組合せること
図１１は、車両ナビゲーション・システムに、オフ・ボード・データ・サプライヤから供給される更なるデータと組合せて車両にオン・ボード配置（搭載）された地図データベースを用いらせることができる手段を示す。オフ・ボード・データをアクセスしかつ用いることは、車両ナビゲーション・システムのデータ・アクセス・レイヤーに配置される演繹データベース・エンジンにより処理されるロジック・ルールによって可能になる。
【００９６】
図１１において、車両ナビゲーション・システム６００及び遠隔データ・サプライヤ６１０は、地図領域６１３に設置される。領域６１３は、メトロポリタン・エリア、州、プロビンス、国、又は一つ以上のメトロポリタン・エリア、州、国、等の組合せでありうる。図１１に示すシステムにおいて、多くの車両及び多くの遠隔データ・サプライヤが存在しうるということが理解されるけれども、一つの車両及び一つの遠隔データ・サプライヤだけが示されている。図１１のナビゲーション・システム６００は、図１に関して説明したナビゲーション・システム１０と同様であり、同じコンポーネントは、同じ参照番号によって識別される。図１１のナビゲーション・システム６００は、図７〜図９に関して上述したように演繹データベース・エンジン２００を有するデータ・アクセス・レイヤー３９を含んでいるナビゲーション・システム・プログラミング１８を含む。ナビゲーション・システム６００は、上述したように、データ４０、インデックス６６及びロジック・ルール３００を含む地図データベース４２を用いる。地図データベース４２は、ナビゲーション・システム６００に設置される、例えば、車両１０のナビゲーション・システム６００にローカル的に取付けられた、媒体３２に記憶される。
【００９７】
図１１において、ナビゲーション・システム６００は、それによってナビゲーション・システム６００が遠隔データ・サプライヤ６１０と無線で通信しかつデータを交換することができる、受信機、送信機、等のような、通信ハードウェア及びソフトウェア６１１を含む。セルラー、無線、衛星、ＰＣＳ／ＧＳＭ、等を含んでいる、あらゆるタイプの無線通信技術が適する。図１１の実施例において、データ・アクセス・レイヤー３９は、それによって演繹データベース・エンジン２００が補助データ・サプライヤ６１０にデータを送りかつそれからデータを受取るために通信ハードウェア及びソフトウェア６１１とインタフェースすることができる手段を供給する機能６４１を含む。
【００９８】
補助データ・サプライヤ６１０は、補助データ６４０を含む。補助データ６４０は、車両１０から遠隔のロケーションにある媒体６３２に記憶される。補助データ・サプライヤ６１０は、また、補助インデックス６６６及び補助ロジック・ルール６５０を含む。補助インデックス６６６及び補助ロジック・ルール６５０は、補助データ６４０と一緒に記憶されるうか又はそれ以外に記憶されうる。
【００９９】
補助データ・サプライヤ６１０は、また、それによって補助データ・サプライヤ６１０がナビゲーション・システム６００と通信しかつデータを交換する通信ハードウェア及びソフトウェア６５８を含む。補助データ・サプライヤ６１０は、また、データ・フルフィルメント・プログラム６７５を含む。
【０１００】
車両ナビゲーション・システムがオフ・ボード・データ・サプライヤによって供給されるデータをアクセスしかつ用いることができる方法は、以下の例において説明される。
【０１０１】
例１
図１１の実施例を用いて、ナビゲーション関連機能が供給されている場合に車両に供給されるナビゲーション機能が補助データを考慮することができるように車両にローカル的に存在しない補助データを車両のナビゲーション・システムに利用可能にすることができる。
【０１０２】
ナビゲーション・システム６００のオペレーション中、車両のロジック・ルール３００は、補助データ・リクエスト・プログラム６４１のルーチンを呼び出すように実行される。補助データ・リクエスト・プログラム６４１のこのルーチンは、補助データが利用可能であるかどうかを決定し、もしそれらが利用可能であれば、補助データを取得すべく車両の通信ハードウェア及びソフトウェア６１１を介してリクエストを送る。このロジック・ルールは、それがスタート・アップにより処理されかつ車両がオペレートされている間に潜在的に時間に応じて処理されるように書かれている。
【０１０３】
データ・リクエスト・プログラム６４１からのリクエストに応じて、遠隔データ・サプライヤ６１０は、応答を送る。遠隔データ・サプライヤ６１０から車両１０への応答は、ロジック・ルール６７０を含む。ダウンロードされたロジック・ルール６７０は、データのシームレス統合のために車両にオン・ボード配置されたロジック・ルール３００に結合される変数を含みうる。ダウンロードされたロジック・ルール６７０は、一時データ記憶装置６７７に車両にローカル的に記憶される。車両慮に設置された演繹データベース・エンジン２００は、ローカル的に既に記憶されたロジック・ルール３００を取り扱うのと同じ方法でダウンロードされたロジック・ルール６７０を取り扱う。ダウンロードされたロジック・ルール６７０は、演繹データベース・エンジン２００によって実行される全てのルールのセット（例えば、ルール・ベース）に追加される。ダウンロードされたロジック・ルール６７は、ある一定のタイプのリクエストの処理中にそれらがまず実行されるように書かれうる。
【０１０４】
例として、車両１０にローカル的に存在するデータ４０が所与の地図エリアにおける全てのレストランに対するリスティング（作表）を含むと想定する。この例によれば、遠隔データ・サプライヤ６１０は、ある一定のクレジット・カード保持者に対してディスカウントを供給するビジネス（レストランを含む）をリストする補助データベース６４２において利用可能なデータを有する。ナビゲーション・システム６００のユーザは、クレジット・カード保持者に対してディスカウントを供給する現在の車両ポジションの近くにあるレストランを検索することを欲する。ユーザは、（図１に示した）ユーザ・インタフェースを介してナビゲーション・システム６００に彼／彼女のリクエストを入力する。ナビゲーション・アプリケーション２８の機能は、データ・アクセス・レイヤー３９を呼び出す。演繹データベース・エンジン２００がレストランを見付けるためにロジック・ルールを処理する場合、ダウンロードされたロジック・ルールをまず処理してクレジット・カード保持者に対するディスカウントについてのデータが利用可能であるということを示す。ダウンロードされたロジック・ルールは、クレジット・カード保持者に対してディスカウントを供給するユーザの現在のロケーションに近いユーザによってリクエストされたタイプのビジネス（即ち、レストラン）にに関するデータを取得するためにデータ・リクエスト・アプリケーション６４１のルーチンを呼び出す。リクエストは、データ・フルフィルメント・プログラム６７５がクレジット・カード・ユーザに対してディスカウントを供給するユーザのロケーションに近いレストランに関するデータを取得するような遠隔データ・サプライヤ６１０に車両１０の通信装置６１１を介して送信される。これらのデータは、通信装置６５８及び６１１を介して遠隔データ・サプライヤ６１０からエンド・ユーザの車両１０に送信される。これらのデータは、車両１０において受信されかつ一時データ記憶装置６７７に記憶される。これらのダウンロードされたデータは、車両において既に利用可能なロジック・ルール３３並びにダウンロードされたロジック・ルール６７０を用いて演繹データベース・エンジン２００によってアクセスされかつ用いられる。
【０１０５】
例２
別の例によれば、図１１に示すシステム６００のような、車両搭載ナビゲーション・システムは、オフ・ボード・データ・サプライヤから供給される交通関連データを取得しかつ用いることができる。交通関連データは、先の例で説明したものと同様な方法で供給することができる。
【０１０６】
交通関連データの場合には、遠隔データ・サプライヤ６２０は、車両１０が配置されるような地域６１３における交通及び道路条件（状態）に関係するデータを取得しかつ供給する。遠隔データ・サプライヤ６１０（又は別のエンティティ）は、交通及び道路条件データを収集し、アセンブルし、編成し、分析しかつフォーマットするための装置及びプログラミングを有する。交通及び道路条件（状態）データは、一つ以上の適当な所定のフォーマットで準備される。一実施例において、代替システム及び／又はプロトコルを用いることができるけれども、交通関連データは、ＲＤＳ−ＴＭＣシステムにおいて設定されたＡＬＥＲＴ−Ｃメッセージに対する標準フォーマットに従う。
【０１０７】
交通関連データの場合には、車両のロジック・ルールは、交通関連データを取得すべきことをリクエストするとき及び取得すべき交通関連データの種類を決定する。例えば、車両のロジック・ルールは、交通によって影響を受けうるナビゲーション機能が実行されるようになっているときにだけ交通関連データに対するリクエストを開始しうる。例えば、ユーザが特定されたロケーションまでのルートを計算することをリクエストした場合、ロジック・ルールは、ルート計算機能（図２の３３）が交通条件（状態）に関する最新のデータを考慮して最も速いルートを決定するように交通関連データに対するリクエストを開始する。オペレーションの代替方法によれば、車両のロジック・ルールは、定期的に更新された交通関連データに対するリクエストを開始しかつ必要なときにデータが直ぐに利用可能なように一時データ記憶装置６７７に交通関連データを記憶しうる。
【０１０８】
車両のロジック・ルールは、ダウンロードされた交通データをナビゲーション・アプリケーション２８によって用いることができるようなフォーマットに変換するために適当なルーチンを呼び出す。ダウンロードされた交通データを変換するルーチンは、物理的から論理的へのシステム２８０又はこの機能を供給する別のシステムに含まれうる。ルーチンは、必要によりデータ・サプライヤ６１０からダウンロードされうる。
【０１０９】
また、ロジック・ルールは、あるタイプのナビゲーション関連機能のオペレーション中に最新交通データが定期的に取得されるように実行されうる。例えば、ユーザが所望の目的地に到達するためのルート・ガイダンス命令を供給されている間に、ロジック・ルールは、追従するルートに関する最新交通データをリクエストしかつ取得しうる。ルートが開始された後に交通渋滞が始まったならば、適当であるならば、代替ルートが決定されうる。
【０１１０】
ロジック・ステートメントが小さいので、このデータ・アクセス・ロジックをダウンロードすることは、容易である。そして、データ（例えば、ある一定の量よりも少ない交通遅延を有するシカゴの区間を選択する）を組合せることを必要とするリクエストは、適当なレポーティング・サービスを選択しかつ問合せに回答するために必要なデータだけをダウンロードする。
【０１１１】
例３
上述した例におけるように、オフ・ボード・データが車両ナビゲーション・システムに利用可能になった場合には、どのようにオン・ボード・データとオフ・ボード・データを一緒に用いるかを決定するためにロジック・ルールを用いることができる。例として、ロジック・ルールは、遠隔データ・ソースからダウンロードされなければならないデータの量を低減するためにローカル的に（即ち、車両において）利用可能なデータを用いて更なる処理が実行されるということを供給することができる。検索の順番を変えるロジック・ルールは、車両に既に存在しうる（例えば、図１１のロジック・ルール３００）か又は車両のユーザに遠隔データを利用可能にするために遠隔データ・プロバイダ６１０からダウンロードされるロジック・ルールの中にありうる。
【０１１２】
例４
別の例は、特定された矩形内の境界横断(border crossings)を決定することに関する。先の方法を用いて、矩形内の全てのＰＯＩを探して境界横断をフィルタすことができるか又は境界横断をフィルタしてそして矩形によりフィルタすることができる。別の先の方法によれば境界ポリラインを選択するために矩形をまず用いそして何も見つからなかったならば検索を中止する。演繹データベースの実施例により、これらのオプションは、ユーザのステートメントからデータ表をアクセスする実行可能なステップのセットに問合せを変形するリライティング・ルール（書換え規則）によって表現される。この例では、矩形インデックスがローカルでありかつＰＯＩタイプ・データがリモート（遠隔）であるならば、“表１をアクセスしかつ表２をアクセスするために結果を用いるならば、表１はリモートであり、表２をアクセスするために問合わせを書換えかつ表１をアクセスするために結果を用いる”という結果をもたらすルールが存在しうるしかつこのルールは、ＰＯＩを検索するものを含む全ての適用可能な問合せを変更しうる。
【０１１３】
上述した例により説明したように、演繹データベース・エンジンは、オン・ボード計算に基づくオフ・ボード・データ選択に対するサポートを供給する。
【０１１４】
Ｃ．他のデータ・プロバイダのデータを統合すること
図１１に関連して、車両のナビゲーション・システムがオフ・ボード・データ及びオン・ボード・データを組合せかつ用いる方法を説明した。また、ナビゲーション・システムは、地図データを車両に設置された更なるデータと組合せるために演繹データベース・アーキテクチャを用いることができる。これらの更なるデータは、車両において個別の媒体に設置されうるか又は代替的に、これらの更なるデータは、地図データとして同じ媒体に設置されうる。これらの更なるタイプのデータは、特別に向上された特徴に関係しうる。例えば、更なるタイプのデータは、レストラン・レーティング、ビデオ・クリップ、ツーリスト・アトラクション、等に関係しうる。
【０１１５】
図１２は、車両ナビゲーション・システム１０の図を示す。図１２のナビゲーション・システム６００は、図１に関して説明したナビゲーション・システム１０と同様である。ナビゲーション・システム１０は、地図データ４０、第１のタイプの補助データ７４０及び第２のタイプの補助データ８４０を用いる。第１のタイプの補助データ７４０は、地図データ４０と同じ媒体３２に設置される。第２のタイプの補助データ８４０は、第２の媒体８３２に配置される。第１のタイプの補助データ７４０に関連付けられるものは、インデックス７６６とロジック・ルール７５０である。第２のタイプの補助データ８４０に関連付けられるものは、インデックス８６６とロジック・ルール８５０である。
【０１１６】
車両の演繹データベース・エンジン２００は、地図データ４０及び更なるタイプのデータ７４０及び８４０をアクセスしかつ用いるためにロジック・ルール３００、７５０、及び８５０を読み出しかつ用いる。ロジック・ルールは、更なるデータ７５０及び８５０を地図データ４０に関連付ける方法を決定する。
【０１１７】
Ｄ．パーソナル・コンピュータ及びＰＤＡ’ｓのナビゲーション・アプリケーション
上に開示した実施例において、地図データベースに関連付けられたロジック・ルールを用いた演繹データベース・エンジンを含んでいるデータ・アクセス・レイヤーは、ナビゲーション・システムの一部として記述された。ロジック・ルールを用いる演繹データベース・エンジンを含んでいるデータ・アクセス・レイヤーは、ワークステーション、パーソナル・コンピュータ、パーソナル・ディジタル・アシスタント、ネットワーク、ページャ、テレビジョン、無線受信機、電話機、等を含んでいる、様々な異なる種類のプラットフォームに取付けられ及び／又は用いられうる。
【０１１８】
Ｅ．ナビゲーション・システム構成
異なるナビゲーション・システムは、異なるハードウェア資源、例えば、だいたいメモリ、速い又は遅いプロセッサ、等を有する。ナビゲーション・システムのハードウェア資源は、ナビゲーション・システムが地図データを用いる方法に影響を及ぼしうる。例えば、ナビゲーション・システムは、比較的大量のメモリを有するが、遅いプロセッサを有しうる。そのようなナビゲーション・システムでは、大量のデータをキャッシュすることを含むソフトウェア処理及びアルゴリズムは、多くの計算を含む処理及びアルゴリズムに対してより良い性能を供給しうる。ロジック・ルールは、ナビゲーション・システムのデータ・アクセス・レイヤーのソフトウェアがナビゲーション・システムのハードウェア資源を考慮するために地図を用いる方法を調整（チューン）しかつ構成するために用いることができる。例えば、ナビゲーション・システムがより多くのメモリ資源を含むならば、より多くのデータをキャッシュする処理が用いられる。
【０１１９】
ナビゲーション・システムのハードウェア資源を考慮するロジック・ルールは、ナビゲーション・システムの一部である個別のメモリ（例えば、ＲＯＭ）に含まれうる。個別のメモリのロジック・ルールは、個別のデータ・サプライヤ（例えば、図１１の遠隔データ・サプライヤ６１０）によって供給されるロジック・ルールと同様な方法で演繹データベースによって用いられる。演繹データベース・エンジンは、ある一定のデータ・アクセス機能が実行される方法に影響を及ぼすルーチンを呼び出すか又は情報を変えるために個別のメモリからロジック・ルールを読み出しかつ用いる。
【０１２０】
代替的実施例において、ナビゲーション・システムのハードウェア資源を考慮するロジック・ルールは、地図データベースに記憶されるロジック・ルールの中に含まれうる。ナビゲーション・システムのハードウェア資源を考慮するロジック・ルールが地図データベースに記憶されるロジック・ルールの中に含まれるならば、それらは、どの資源が利用可能であるかを決定するためにナビゲーション・システムのハードウェアを問合わせるデータ・アクセス・レイヤーのルーチンを呼び出す。これらの問合せに対する応答に基づき、データ・アクセス機能を実行する場合にナビゲーション・システムの利用可能なハードウェア資源を考慮する。ロジック・ルール及び演繹データベース・エンジンを用いて、それが設置されているナビゲーション・システムに対してデータ・アクセス・レイヤーを自動的に構成することができる（例えば、プラグ・アンド・プレイ構成）。更に、新しいハードウェア資源、例えば、より多くのメモリが追加される場合、ロジック・ルールによって呼び出されたルーチンは、新しいハードウェアを自動的に検出しかつ従ってデータ・アクセス機能を変更する。
【０１２１】
このコンセプトを更に拡張すると、演繹データベース・エンジンによって用いられるロジック・ルールは、また、データ・アクセス・レイヤーを異なるハードウェア・プラットフォームにポートするために用いることもできる。
【０１２２】
【発明の効果】
Ｖ．効果
上記したように、演繹データベース・エンジンを含むデータ・アクセス・レイヤーは、フォワード及びバックワード互換性を供給することができかつ同じ地図データベースをこれらの異なるプラットフォームで交換可能に用いらせるように異なるハードウェア・プラットフォームで用いることもできる。
【０１２３】
開示した実施例の効果は、ナビゲーション・システムがあらゆるタイプの地図データベースを用いることができるということである。データ・アクセス・レイヤーは、データベースでもちいるあらゆるインデックスを含んでいる、データベースに含まれたデータをアクセスし、読み出しかつ用いるための用いられる問合わせルーチンをフォーミュレートするためにデータベースに関連付けられたロジック・ルールを用いる。それによってデータベースがアクセスされる手段をフォーミュレートするためにデータ・アクセス・レイヤーがデータベースに関連付けられたロジック・ルールを用いるので、（ナビゲーション・システムの見地から）固定されたデータ・タイプを必ずしも必要としない。
【０１２４】
上述したことからの一つの効果は、パーセライゼーション技術を制限することなく地図データをパーセライズすることができるということである。適切なデータだけがアクセスされるようにどのパーセルを検索すべきかを示すためにロジック・ルールを用いることができる。別の効果は、新しいデータ・タイプ又は表を容易に追加できるということである。新しいデータ・タイプ又は表を追加するために、新しいデータ・タイプ又は表を参照する新しいロジック・ルールがデータベースに関連付けられる。
【０１２５】
別の効果は、演繹データベース・エンジンのオペレーションを並列処理に適応することができるということである。ロジック・ステートメントの処理は、必要に応じて組合される並列オペレーションの結果と並列で（特定の依存性が存在しない限り）行うことができる。例えば、データ検索処理は、問合わせに対して応答することが必要なデータを含んでいる全てのパーセルをまず検索しそして、  ならば、一つよりも多くのパーセルが検索されるならば、並列オペレーションが各パーセルで実行されるようにフォーミュレートすることができる。そして、全ての並列オペレーションが実行された後、結果が組合される。
【０１２６】
上述した実施例は、システムの組込まれた部分を形成するデータベースに対して特定の効果を供給する。ナビゲーション・システムで用いられる地図データベースは、そのようなシステムの一例である。それは低レベルのディテール(例えば、行アクセス、インデックス・ナビゲーション、等)を抽象して取り除かせるが、スキーマ・ジェネレーション、キャッシュ・マネージメント、トランザクション・サポート、記憶された手順、トリガ・サポート、保証、及び最適ＳＱＬ実行のようなエレメントに対する制御を許容するので、開示した実施例における演繹データベース・エンジンの使用は、効果的である。
【０１２７】
上述した実施例は、第３者のデータの統合を容易にする。
【０１２８】
また、上述した実施例は、容易なソフトウェア及びデータベース保守を供給しうる。
【０１２９】
上述した詳細の説明は、限定するためではなく説明のためであることを意図しており、全ての同等物を含んでいる特許請求の範囲が本発明の範疇を規定することを意図している、ということが理解されるべきである。
【図面の簡単な説明】
【図１】ナビゲーション・システムを示すブロック図である。
【図２】図１のナビゲーション・アプリケーション・ソフトウェアの部分を示すブロック図である。
【図３】図１及び図２の地図データベースに含まれる異なるタイプのデータを示す図である。
【図４】図３に示すルーティング・データの個別レイヤーを示す図である。
【図５】空間的に編成された地図データに対するパーセライゼーション方法(parcelization method)の応用を説明するために用いる地図領域のマップ（地図）を示す。
【図６】図５に示すパーセライゼーション方法による図１及び図２の地図データベースのデータのパーセル(parcels)の構成（配列）を示す図である。
【図７】図２のデータ・アクセス・レイヤーのブロック図である。
【図８】図７に示す規則の構成部分を示すブロック図である。
【図９】図７に示す演繹データベース・エンジンの動作のフローチャートである。
【図１０】更新地図データを有する図７のデータ・アクセス・レイヤーの使用を示すブロック図である。
【図１１】無線通信リンクで供給される追加データを有する図７のデータ・アクセス・レイヤーの使用を示すブロック図である。
【図１２】車両に搭載配置された(located on-board the vehicle)追加データを有する図７のデータ・アクセス・レイヤーの使用を示すブロック図である。
【符号の説明】
１０   ナビゲーション・システム
１１   車両
１２   プロセッサ
１４   ドライバ
１６   不揮発性メモリ
１８   ソフトウェア
１９   パラメータ
２０   ＲＡＭ
２４   測位システム
２５   センサ
２６   出力信号
３１   ユーザ・インタフェース
３２   記憶媒体
４０   地図データ
３００  ロジック・ステートメント
【図１】
0004817518.tif 000002
【図２】
0004817518.tif 000003
【図３】
0004817518.tif 000004
【図４】
0004817518.tif 000005
【図５】
0004817518.tif 000006
【図６】
0004817518.tif 000007
【図７】
0004817518.tif 000008
【図８】
0004817518.tif 000009
【図９】
0004817518.tif 000010
【図１０】
0004817518.tif 000011
【図１１】
0004817518.tif 000012
【図１２】
0004817518.tif 000013