(57)【要約】【課題】  データベース・システム、データベース・システムのためのコンピュータ実行可能な方法、プログラムおよびデータベース・システムにおける索引テーブルをアップデートする方法を提供すること。【解決手段】  データベース・システムは、タイムスタンプが付されたアイテムのアイテム・テーブルを格納している。アイテムは、さらにそれぞれタイムスタンプによりテーブル内において分類され、かつアイテム・テーブルが索引データにより索引づけられている。データベース・システムは、さらに、索引データと共にアイテム・テーブルの最も早いタイムスタンプをリストし、索引データのための索引テーブルと、この索引テーブルを使用してアイテム・テーブルを検索するシステム・マネージャとを含んでいる。【選択図】図２
2006178848.tif 000002
【特許請求の範囲】
【請求項１】
データベースに格納されたアイテムを検索するデータベース・システムであって、前記データベース・システムは、
タイムスタンプが付されたアイテムのアイテム・テーブルを格納し、前記アイテムは、それぞれ前記タイムスタンプによりアイテム・テーブル内において分類され、かつ前記アイテム・テーブルが索引データにより索引づけられるデータベースと、
前記索引データと共に前記アイテム・テーブルの最も早いタイムスタンプをリストした、前記索引データのための索引テーブルと、
前記索引テーブルを使用して前記アイテム・テーブルを検索するシステム・マネージャと、
前記アイテム・テーブルをモニタして前記索引テーブルをアップデートし、前記アイテム・テーブルと前記索引テーブルとの間の関連を保持させるためのモニタ・ツールを含む前記索引テーブルのメンテナンス・モジュールと
を含み、
前記モニタ・ツールは、前記索引データを含む前記アイテム・テーブルから最新のタイムスタンプを有する前記アイテムを前記索引データと共に呼び出して、前記呼び出されたタイムスタンプと前記索引データとを検査キーとして使用して前記索引テーブルの前記関連を検査する、データベース・システム。
【請求項２】
前記データベース・システムは、さらに、前記索引テーブルの更新ツールを含み、前記更新ツールは、前記モニタ・ツールによる前記タイムスタンプと前記索引データとにしたがった前記検査の結果に応答して、前記索引テーブルへとレコードを追加する、請求項１に記載のデータベース・システム。
【請求項３】
前記データベース・システムは、さらに、前記更新ツールにより使用される二分木検索ツールを含む、請求項２に記載のデータベース・システム。
【請求項４】
データベース・システムにおけるデータベースの検索方法であって、前記データベース・システムは、ＣＰＵと、メモリと、記憶デバイスとを含むコンピュータを含み、前記データベースは、前記記憶デバイスに格納されており、前記データベース検索方法は、前記コンピュータに対し、
タイムスタンプが付されたアイテムのアイテム・テーブルをデータベースに格納するステップであって、前記アイテムは、それぞれ前記タイムスタンプによりアイテム・テーブル内において分類され、かつ前記アイテム・テーブルが索引データにより索引づけられるステップと、
前記索引データと共に前記アイテム・テーブルの最も早いタイムスタンプをリストした、前記索引データのための索引テーブルを格納するステップと、
前記索引テーブルを参照して前記アイテム・テーブルを検索するステップであって、前記索引テーブルを、メンテナンス・モジュールにより時間経過に関連して修正するステップとを含み、
前記メンテナンス・モジュールは、さらに、
前記アイテム・テーブルと前記索引テーブルとの間の関連をモニタするステップと、
前記アイテム・テーブルから最新のタイムスタンプを有する前記アイテムを前記索引データと共に呼び出すステップと、
前記呼び出されたタイムスタンプと前記索引データとを検査キーとして使用して前記索引テーブルの前記関連を検査するステップとを実行させる、方法。
【請求項５】
前記方法はさらに、前記コンピュータに対して、前記タイムスタンプと前記索引データとにしたがった前記検査ステップの結果に応答して、前記索引テーブルへとレコードを追加するステップを実行させる、請求項４に記載のデータベース検索方法。
【請求項６】
前記方法はさらに、前記コンピュータに対して、前記修正するステップで二分木検索を実行させる、請求項４に記載のデータベース検索方法。
【請求項７】
データベース・システムにおけるデータベースの検索方法を実行させるコンピュータ実行可能なプログラムであって、前記データベース・システムは、ＣＰＵと、メモリと、記憶デバイスとを含み、前記データベースは、前記記憶デバイスに格納されており、前記プログラムは、前記コンピュータに対し、
タイムスタンプが付されたアイテムのアイテム・テーブルをデータベースに格納するステップであって、前記アイテムは、それぞれ前記タイムスタンプによりアイテム・テーブル内において分類され、かつ前記アイテム・テーブルが索引データにより索引づけられるステップと、
前記索引データと共に前記アイテム・テーブルの最も早いタイムスタンプをリストした、前記索引データのための索引テーブルを格納するステップと、
前記索引テーブルを参照して前記アイテム・テーブルを検索するステップであって、前記索引テーブルを、メンテナンス・モジュールにより時間経過に関連して修正するステップとを含み、
前記メンテナンス・モジュールは、さらに、
前記アイテム・テーブルと前記索引テーブルとの間の関連をモニタするステップと、
前記アイテム・テーブルから最新のタイムスタンプを有する前記アイテムを前記索引データと共に呼び出すステップと、
前記呼び出されたタイムスタンプと前記索引データとを検査キーとして使用して前記索引テーブルの前記関連を検査するステップとを実行させる、プログラム。
【請求項８】
前記プログラムはさらに、前記コンピュータに対して、前記タイムスタンプと前記索引データとにしたがった前記検査ステップの結果に応答して、前記索引テーブルへとレコードを追加するステップを実行させる、請求項７に記載のプログラム。
【請求項９】
前記プログラムはさらに、前記コンピュータに対して、前記修正するステップで二分木検索を実行させる、請求項７に記載のプログラム。
【請求項１０】
データベース・システムにおける索引テーブルをアップデートする方法であって、前記データベース・システムは、ＣＰＵと、メモリと、記憶デバイスとを含むコンピュータを含み、前記データベースは、前記記憶デバイスに格納されており、前記方法は、前記コンピュータに対し、
タイムスタンプが付されたアイテムのアイテム・テーブルをデータベースに格納するステップであって、前記アイテムは、それぞれ前記タイムスタンプによりアイテム・テーブル内において分類され、かつ前記アイテム・テーブルが索引データにより索引づけられるステップと、
前記索引データと共に前記アイテム・テーブルの最も早いタイムスタンプをリストした、前記索引データのための索引テーブルを格納するステップと、
前記アイテム・テーブルと前記索引テーブルとの間の関連をモニタするステップと、
前記アイテム・テーブルから最新のタイムスタンプを有する前記アイテムを前記索引データと共に呼び出すステップと、
前記呼び出されたタイムスタンプと前記索引データとを検査キーとして使用して前記索引テーブルの前記関連を検査するステップと、
前記タイムスタンプと前記索引データとにしたがった前記検査の結果に応答して、前記索引テーブルへとレコードを追加するステップとを実行させる、方法。
【請求項１１】
さらに、
前記索引テーブルを参照して前記データベースの二分木検索を実行させるステップと、
検索キーに応答して前記索引テーブルに対してレコードを追加することが必要か否かを判断するステップと、
前記判断ステップに応答して、前記追加が要求される場合には、前記二分木検索を実行させながら前記レコードを追加するために修正関数を呼び出すステップと、
を実行させる請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースのエントリの更新技術に関し、より詳細には、データベース・システム、データベースのエントリの検索を効率的に高速化させる時間依存の逆参照テーブルを生成する方法およびプログラムに関する。
【背景技術】
【０００２】
データベース検索の最適化は、多くの研究・開発の対象とされてきている。それにもかかわらず、すべての主要データベース・メーカは、多くの時間を上述した最適化のために投入してきた。個別的なデータベースの検索は、特有化して実装されており、この理由は、最適化が、特定のデータベース構造に高度に適合化されるためである。
【０００３】
データベースおよびデータベースに格納されるデータは、ますます膨大になってきており、かつデータベース・システムは、分散コンピューティング環境によりますます利用されるようになってきている。このような状況下では、データベース・システムのユーザは、データベースの時間に依存する関連性に注意を払わなければならず、このため、時間経過と共にエントリが追加、または更新されるデータベースの効率的な検索性を向上させることが必要とされている。
【０００４】
本発明と同一の譲受人に譲渡された小林らによる特開２００１−３１２５０５Ａ号公報（特許文献１）は、アイテムが時間と共に更新されるデータベース内のアイテムの検索／抽出システムを開示している。開示されたシステムにおいては、アイテムは、タイムスタンプを含むバイナリ・データとして格納されており、このため、検索クエリーにタイム・ウィンドウを追加して時刻に関連して重み付けされたアイテムを抽出している。しかしながら、開示された方法は、検索されるべきアイテムとは別に用意されるいかなる索引データ構造の使用を開示するものではない。
【特許文献１】特開２００１−３１２５０５Ａ
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明者らの意図する対象は、製造業界であり、具体的には、本発明は、より複雑なデータ構造に取り込まれてしまう生産物の追跡を取り扱うものである。本発明者らは、これをデータベースのいかなる時点においてもその概要または関連性を変化させてしまう可能性のある多重のレイヤにわたって逆追跡を行う、という問題として捉えるものである。本発明は、更新周期にぶれがある場合であっても特定の構成部品を使用して製造される最終製品を迅速に同定する手段を提供する。
【０００６】
したがって、本発明は、大規模で分散環境に設置された情報を検索するものである。上述したように、本技術は、捕捉されたデータを使用して効率的な索引生成を行うように構成される。本発明の手法は、対応付けに際して時間窓を使用する手法を使用する点で、これまでの手法とは異なるものである。本発明は、供給における連鎖が変化する、すなわち、データの更新周期の変化する構成部品を追跡するための手段を提供するものである。本発明では、製造時点での供給における連鎖の詳細を知ることなく、製品と構成部品とを迅速にマッチングさせることが可能となる。本発明により与えられるソリューションは、供給における連鎖、すなわちデータベースのデータの更新周期が変化することによる構成部品の追跡性の問題に適合させた、効率的な逆索引テーブルを利用する。
【課題を解決するための手段】
【０００７】
本明細書において後述するように、部品が多くの場合に順次的に供給され使用される場合には、上述したテーブルのメンテナンス・コストは小さく、頻繁に出荷または製造遅延および誤発注された部品があるような場合には、実行時間は、対数オーダーとなる。この実行時間は、本明細書で説明されるように時間で重み付けをした二分木検索アルゴリズムを使用することにより達成される。
【０００８】
本発明者らは、供給のための連鎖が変化する場合における構成部品を追跡するための手段を提供する。この手段は、製造時点でも供給の連鎖についての詳細を知ることなく製品および構成部品を迅速に対応付けすることができる。本発明のソリューションは、供給のための連鎖が変化する場合における構成部品を追跡するために適合化された効率的な逆索引テーブルを提供するものである。
【発明の効果】
【０００９】
本発明によれば、部品が多くの場合に順次的に供給され使用される場合には、上述したテーブルのメンテナンス・コストは小さく、頻繁に出荷または製造遅延および誤発注された部品があるような場合にでも、実行時間を対数オーダー程度に納めることができる、時間で重み付けをした二分木検索アルゴリズムを提供することができる。
【発明を実施するための最良の形態】
【００１０】
以下本発明をメーカ−供給者による部品供給のデータベースに対して、不特定の経路にしたがって本発明の逆探索で、データベースの参照が行われるという、特定の実施の形態を用いて説明する。特に、本発明者は、その構成部品のうちの１つを知ることにより、供給における連鎖が変化した製品を同定することに基づいて本発明を説明する。
【００１１】
Ａ．システム構成
図１は、本発明で使用するシステム・アーキテクチャを示した概略図である。データベース・システム１０は、概ね、逆索引テーブルを生成する方法を実行するＣＰＵ１２と、ＣＰＵ１２による処理を可能とし、実行プログラムおよびデータを格納するメモリ１４とを含んでいる。データベース・システム１０は、さらにネットワーク・デバイス１６と、ＡＴＡ、ＩＤＥ、ＲＳ−２３２Ｃなどの適切なインタフェース１８−２２を含んで構成されおり、それぞれキーボードなどの入力デバイス２４、ディスプレイ・デバイス２６、および記憶デバイス２８へと相互接続されている。記憶デバイス２８には、データベース３０が格納されており、周期的またはユーザ・ニーズに応答してデータベースのエントリがアップデートされている。
【００１２】
データベース・システム１０は、ウィンドウズ（登録商標）またはＭａｃＯＳ（登録商標）などのオペレーティング・システムにより、ＰＥＮＴＩＵＭ（登録商標）タイプのプロセッサのもとで動作されるマイクロコンピュータまたはワークステーションとすることができる。これとは別に、データベース・システム１０は、ＡＩＸ（登録商標）の下で、ＲＩＳＣアーキテクチャのマイクロプロセッサにより処理されるＵＮＩＸ（登録商標）またはＬＩＮＵＸアーキテクチャを有することもできる。図１に示したデータベース３０は、ＳＱＬ言語によりアクセス可能な、いかなるリレーショナル・データベースを含む、いかなるデータベースからでも選択することができる。
【００１３】
図２は、データベース３０のデータ構成を示した図である。データベース３０は、概ね、部品テーブル３２およびＳ１といった特定のアイテムについてのＲＣＩＤテーブルとして参照される２つのデータセットを保有している。部品テーブルは、ｔ１、ｔ２、ｔ３、．．．というように、時刻にしたがって生成され、部品テーブルの生成は、周期的、またはユーザがデータベースのエントリをアップデートする必要がある場合に実行される。加えて、データベース３０は、ＲＣＩＤテーブル３４として参照される別のテーブルを含んでおり、ＲＣＩＤテーブル３４は、アップデート時刻ｔｎと部品テーブル識別値（ｉｄ：｛Ｐ｝ｉｄ）とが対とされている。部品テーブルのアップデート時刻は、予測できないので、部品テーブルのユーザは、部品テーブルに付加されたタイムスタンプを問い合わせることにより所望する部品テーブルを検索する。しかしながら、ユーザは、ユーザが正確なタイムスタンプを知らない場合には、時間的に更新される多数の部品テーブルの中から直接的に当該部品テーブルを見出すことはできない。したがって、図２に示すようなリバース部品インデックス(Reverse Component InDex)テーブルを生成することが有効である。本発明の別の実施の形態では、部品テーブル３２とＲＣＩＤテーブル３４とは、倉庫部門および生産部門といった遠隔したサイトに設置された異なるハードディスク・ドライブに格納され、部品テーブルとＲＣＩＤテーブルとの間の一致性は、ネットワークを介して達成されても良い。
【００１４】
図３は、本発明のデータベース・システム１０のソフトウェア構成を示した図である。データベース・システム１０は、概ね３層ソフトウェア・アーキテクチャとされている。オペレーティング・システム３６のレイヤは、最も下層、すなわち基本ソフトウェア層となっている。システム・マネージャ３８のレイヤは、オペレーティング・システム３６上に構成され、アプリケーション４０からの要求に応答してＲＣＩＤテーブルの管理を実行する。アプリケーション４０は、データベース３０とユーザとの間のインタフェースを与えており、入出力操作または検索操作を通してデータベース３０のエントリにアクセス可能とされている。
【００１５】
システム・マネージャ３８には、モニタ機能が実装されており、このモニタ機能は、最も新しく特定の部品リストに付加されたタイムスタンプのクエリーを発行し、その戻り値として対応するタイムスタンプを受け取る。なお、このモニタ機能を、以後、manufacturingTimeFast(idSi)命令として参照する。システム・マネージャ３８は、また、Compare(), Find (), およびInsert()として参照される関数を実装している。関数Compare()は、ＲＣＩＤテーブルに格納された同一の｛Ｐ｝ｉｄのタイムスタンプと戻り値とを比較して、ＲＣＩＤテーブルの順序を変更する、すなわちＲＣＩＤテーブルのメンテナンスを行う。関数Find ()は、戻り値を部品テーブルが間に挿入されたタイムスタンプのシーケンスと比較する。関数Insert ()は、Find()により見出されたタイムスタンプを有するレコードの間に部品テーブル｛Ｐ｝ｉｄを挿入する。
【００１６】
本発明をさらに説明するために、ここで下記の通りに仮定を行うものとする。
（１）製品のデータベースＭと、供給者のデータベースをＳとする。製品Ｍのシステム・マネージャは、Ｇであり、Ｓに対するいかなる制御もできないか、またはＳからＭへの供給連鎖の制御をできないものとする。システム・マネージャは、Ｍ内にリストされているすべての製品についての部品リストを、製品テーブルに保持しているものとする。多くの製品があるので、本発明者らは、製品リストは、製造時刻に応答していくつかのより小さなテーブルへと分割されるものと仮定する。例えば、新たな製品テーブルは、毎月作成される。これらのより小さなテーブルは、所定の仕方において索引付けされ、製品テーブル｛Ｐ｝のセットを構成する。
（２）さらに、このシステムでは、Ｍに含まれる情報を要求するＧへのクエリーを仮定する。本発明の課題は、｛Ｐ｝したがって、Ｍ内のＳのどの要素であっても効率的に見出すことにある。供給鎖についての知見に直接的に基づいて本発明では、以下の特徴を想定する。
（ａ）Ｍ、｛Ｐ｝、およびＳは、追加されるだけである。
（ｂ）Ｓの所与のインデックスで、Ｓを同定する。すなわち、本発明ではいかなる部品の製造者を部品ＩＤから指定することができる。
（ｃ）ＭおよびＳのすべてのエントリは、タイムスタンプが付されている。
（ｄ）同時に製造された構成部品は、概ね、同時に構築するために使用される。ここで、この特徴を次のように一般化する。データベースＳｉ中のあるタイムスタンプｔＳｉｊを持つエントリｉｄＳｉｊが、データベースＭ中のタイムスタンプｔＭｊを持つエントリｉｄＭｊにより参照されているとする。別のエントリｉｄＳｉｋがタイムスタンプｔＳｉｋをもつとすると、ｔＳｉｊ−ｔＳｉｋが小さいとき、エントリｉｄＳｉｊとエントリｉｄＳｉｋは時間的に近傍にあると呼ぶ。ここで前述の特徴を一般化すると、「ｉｄＳｉｋが、タイムスタンプｔＭｋを持つエントリｉｄＭｋにより参照されているとすると、エントリｉｄＳｉｊとエントリｉｄＳｉｋが時間的に近傍にあるならば、エントリｉｄＭｊとエントリｉｄＭｋも近傍にある（即ち、ｔＭｊ−ｔＭｋは小さい）」と表現できる。
（ｅ）構成部品は、概ねそれらが到着した順に使用され、出荷は、まれにしか長期間遅延しない。このため、より古い構成部品は、より新しい構成部品が使用され始めると、それよりも新しい製品を製造するために使用されることはほとんどない。
【００１７】
この特徴は、一般化することができＳｉ内のそれぞれ、ｉｄＳｉｊおよびｉｄＳｉｋ、それぞれタイムスタンプｔＳｉｊおよびｔＳｉｋでインデックス化された２つの要素では、ｔＳｉｊ＞＞ｔＳｉｋである。これらの要素がｉｄＭｊ、タイムスタンプｔＭｊおよびｉｄＭｋ、タイムスタンプｔＭｋでそれぞれ参照される場合には、ｔＭｊ＜＜ｔＭｋである場合はほとんどない。
【００１８】
基本的な方法は、部品逆索引テーブル(Reverse Component InDex (RCID) table)において部品製造の時間窓を索引付けすることである。このテーブルは、構成部品の製造時刻をその部品を含む可能性に最も高い｛Ｐ｝のテーブルにマッチングさせる。また、（ｄ）で仮定したように、本発明の目的は、完全な逆索引テーブルを実装することなく、逆ルックアップについての検索空間を狭めることにある。ＲＣＩＤテーブルは、システム・マネージャＧにより保守され、データベースを検索することなく、または中間データベースにアクセスすることなく、構成部品のデータベースからの情報の抽出を迅速な方法を提供する。
【００１９】
ＳについてのＲＣＩＤテーブルは、開始時刻ｔにより参照される時間窓を、｛Ｐ｝内のｐｉといった識別値により索引付けされた特定のテーブルへとマッピングする。Ｓからの開始時刻ｔＳｊは、タイムスタンプであり、インデックスｉｄＳｊを有するエントリに対応する。この場合、ｉｄＳｊは、参照の連続バッチにおけるインデックスｐｉを有する部品テーブルにリストされた、Ｍの要素により参照されるＳ内の最初のインデックスである。すなわち、ｔは、テーブルＰｉが開始されて以来、製品Ｍを製造するために使用された第１の構成部品の製造時刻を表す。
【００２０】
Ｂ．ＲＣＩＤ保守
以下に説明するアルゴリズムは、最適化された手法を使用する。本発明において、ほとんどの構成部品は、順に供給され、すべてが順調に進行している場合には、ＲＣＩＤテーブルは、編集されないとする。このアルゴリズムでは、ＲＣＩＤは、新規な部品テーブルが生成される場合、または大きな出荷遅延があって新たな部品テーブルが間において生成される場合にアップデートされるだけである。ここで、説明している実施の形態では、下記の仮定を行う。
（ｆ）工場フロアにあるすべての構成部品の製造時刻をルックアップする効率的な手段が存在する。すなわち、製造センタにおけるすべての構成部品について、アクセスしやすい方法でその製造時刻のある種の記録が存在することである。ここで、上述した問題は、manufacturingTimeFast(idSi)で表される関数として定式化することができ、この関数は、ＩＤ番号がｉｄＳｉの部品の製造時刻を返す。
上記（ｆ）の仮定には、下記の理由により妥当性を与えることができる。
・供給者にあっては、その製品に製造情報を与えることが必要であることが現実的であり、
・構成部品が使用されるまでの短時間に対してそのような情報を保持することはコスト的に高くはないこと、
・｛Ｐ｝を構成するにあたり製造者により関連するクエリーはすでに実行されていること、である。
【００２１】
図４〜図６は、関数Compare()、Find()、Insert()による基本的なモニタ手順を示した図である。図４では、部品テーブル｛Ｐ｝は、manufacturingTimeFast(idSi)により問い合わせを受け、manufacturingTimeFast(idSi)は、その返り値ｔをシステム・マネージャへと返す。その後、変数を（ｔ、ｔｎ）としてCompare()の関数呼び出しが行われる。ここで、ｔは、部品テーブル｛Ｐ｝ｉｄの最新のタイムスタンプであり、ｔｎは、ＲＣＩＤテーブルにおける同一の｛Ｐ｝ｉｄのタイムスタンプである。図４に示した実施の形態では、ｔ＞ｔｎなので関数Compareは、正の戻り値を返し、ＲＣＩＤテーブルには不正規な順番が存在しない。
【００２２】
図５は、タイムスタンプｔｎ−２を有するｉｄが付された｛Ｐ｝ｉｄで示される部品テーブルにおけるモニタ手順の別の実施の形態を示した図である。manufacturingTimeFast(idSi)の戻り値は、ｔｋであり、戻り値ｔｋは、ｔｎ−２とｔｎ−１の間にある。したがって、ＲＣＩＤテーブルのタイムスタンプシーケンスは、正確であり、いかなるメンテナンス手順も必要ではない。
【００２３】
図６は、ＲＣＩＤテーブルが修正されるべき場合のモニタ手順の実施の形態を示した図である。図６では、戻り値ｔｋは、ｔｎ−２およびｔｎ−２との間に存在するが、付加されている｛Ｐ｝ｉｄは、異なっている。このため、ＲＣＩＤテーブルは、正確なシーケンスを含ませるために修正されなければならない。この修正手順は、図７で説明するInsert []の関数呼び出しにより実行される。
【００２４】
図７は、ＲＣＩＤテーブルの修正プロセスの機能を示した図である。関数Insert []を呼び出す前に、システム・マネージャは、関数Compare ()を呼び出して、部品テーブルまたは複数の部品テーブルが挿入されるレコードを決定する。その後、システム・マネージャは、関数Predict trを呼び出して、対応する部品テーブルｉｄを有する備品テーブル｛Ｐ｝ｉｄの挿入シーケンスを決定し、その後システム・マネージャは、関数Insert []を変数（ｔ；Ｐｉ）と共に呼び出してＲＣＩＤテーブルに正確なレコードを挿入する。
【００２５】
このアルゴリズムは、図８に示す手順により正確に示される。図８においては、未定義関数predictRangeが現れており、この関数predictRangeは、Ｐｊにリストされるべき最後の部品の製造時間を同定する目的を有している。要素は、部品の製造時刻によっては順序づけられないので、完成した製品の製造順で重み付けした二分木検索が行われる。図９には、predictRangeの擬似コードをまとめる。
【００２６】
Ｃ．時間重み付け二分木検索
システム・マネージャＧは、関数manufacturingTimeSlow(idSi)を呼び出すことができる。この関数は、manufacturingTimeFast(idSi)と同一の機能を有しており、ｉｄＳｉで索引付けされる構成部品Ｓｉの製造時刻を戻す。しかしながら、Ｓｉは、最近に使用されたものである必要はなく、この関数は、ＲＣＩＤ内において不正確にマッピングされた部品の古いバッチを見出すために使用される。典型的には、この関数は、データベース内のルックアップとして実装されることになる。この関数は、Ｓが遠隔しており、問い合わせが高いコストを要するという意味で「遅い」と言える。
【００２７】
本質的な方法は、以前の時刻後の次の参照時刻を見出すために二分木検索を行うことである。この二分木検索をできるだけ少ないmanufacturingTimeSlow()呼び出しを可能とさせるために、本発明では、表の順番ではなく、製造時刻により検索すべき要素を選択する。これは、Ｓ中でルックアップを行ってｉｄＳｉを見出すためにｉｄＭｉを使用したＰｉ中のすべてのｉｄＭｉにわたって二分木検索を行う量となる。本発明における特徴的な構成は、ｉｄＭｉを、レコードの数ではなく、実時刻の差を含むタイムスタンプに基づいて選択することである。
【００２８】
図１０には、二分木検索アルゴリズムの擬似コードを示す。これらの関数は、predictRangeに対して次のインデックスを返すことを可能とする。この計算のオーバーヘッドは、manufacturingTimeSlow ()への呼び出しにかかるO(log(n))だけでマッピングすることができ、したがって、時間重み付け二分木検索は、システム・マネージャに対して重大なオーバーヘッドを与えることがない。
【００２９】
Ｄ．本発明の更新アルゴリズムの概略的な解析
新たに製造された製品それぞれに対して（すなわち、｛Ｐ｝の各アップデートに対して）：構成部品がほとんどの場合にその製造の順に使用される場合は、Ｓに対する読み出しコストはゼロであり、ＲＣＩＤに対する書き込みコストはゼロであり、計算コストは、O(1)であり、メモリ使用量はゼロである。構成部品が遅延するが、その遅延が予測できる場合には、Ｓの読み出しコストゼロであり、ＲＣＩＤの読み出しコストは、O(|RCID|)、すなわち、近似的にO(|{P}|+|失われた出荷の数|）であり、ＲＣＩＤへの書き込みコストは、O(1)であり、計算コストは、O(|RCID|)であり、メモリ使用量はゼロである。部品は遅延するが、その遅延が予測できない場合は、Ｓの読み出しコスト（すなわち、manufacturingTimeSlowの呼び出し数)は、O（log(｜Pi|））であり、｛Ｐ｝の読み出しコストは、O（log(｜Pi|２)であり、ＲＣＩＤへの書き込みコストは、O(｜RCID|）であり、｛Ｓ｝における各Ｓｉへの通信コストは、O(log(n))であり、計算コストは、O(|RCID|+log(|Pi|2)であり、メモリ使用量は、O(1)となる。
したがって、この更新アルゴリズムは、大きな出荷遅延が存在しない場合には高速かつ安価に処理できる。加えて、そのような出荷遅延が存在したとしても、供給者のデータベースに対する高コストの呼び出しは、１度だけ実行されるだけで良く、またこの呼び出しは、対数関数的な頻度に制限される。
【００３０】
Ｅ．ＲＣＩＤを使用した製品のルックアップ
本発明においては、部品テーブルは、ＲＣＩＤを使用してルックアップされることで部品テーブルの検索を向上させる。図１１に示した擬似コードは、ＲＣＩＤテーブルを使用したルックアップを実行するためのアルゴリズムを示す。図１１に示すように、ルックアップ手順は、簡単なコードにより実行され、したがってルックアップ手順、すなわち部品テーブルの検索は高速にかつ部品テーブルに格納されたデータにほとんど完全に依存する。
【００３１】
ＲＣＩＤテーブルにおける誤差は、時間重み付け二分木検索が、部品が多くの場合に製造される順に使用される場合に効果的なことから、僅かである。したがって、データベースＳへの全通信（すなわち、manufacturingTimeSlowの呼び出し）は、O(1)ですませることができる。全計算時間は、O(|Pj|+|RCID|)である。ＲＣＩＤテーブルを除く処理時間は、｛Ｐ｝内のすべてのテーブルについて、O(|P1|*|P2|*・・・*｜Pj|*・・・)である。したがって、このアルゴリズムは、計算時間に関連して大きな改善をもたらす。
【００３２】
加えて、本発明では、システム・マネージャは、ＲＣＩＤのランタイム修正をＲＣＩＤテーブルを使用したルックアップの間に行うことができる。間違いが見出される場合のランタイム修正の実施の形態を図１２に示す。図１２に示すように、システム・マネージャは、ＲＣＩＤを、保守手順において使用すると共用される関数predictRange, Insertを使用して訂正し、このため、全体のソフトウェア・コードは、極めてコンパクトにすることができる。特にこのコードは、製造時刻が不正順となった部品について使用されるコードと極めて似ている。特に、このコードは、同一のpredictRange関数に依存するものである。したがって、この修正アルゴリズムは、ＲＣＩＤアップデート・アルゴリズムのコストおよびランタイムと等価的となる。
【００３３】
本発明のプログラムは、例えばＣ、Ｃ＋＋、Ｊａｖａ（登録商標）などいかなる知られたプログラム言語によっても記述することができ、フレキシブル・ディスク、ＣＤ−ＲＯＭ、ＤＶＤ、光磁気ディスクといったいかなるコンピュータ可読な媒体に記録して頒布することができ、またネットワークを通して伝送することができる。
【００３４】
Ｆ．適用分野
本発明は、リバース・アイテム・ルックアップの問題に対する効果的なソリューションを提供するため広い適用性を有している。本発明は、いかなる部品供給者においても僅かな要求のもとで実装でき、かつ完全に自動的に動作させることができる。したがって、この技術は、製造の完全な履歴にわたり製造者により使用されるすべての構成部品に対する完全な構成部品追跡システムを可能とする。加えて、ＲＣＩＤと共に検索空間を狭めるタイム・ウィンドウの使用は、この技術を、データベースがタイムスタンプを含むいかなる状況についても適用することを可能とし、この結果、本システムは、履歴記録、セキュリティ・ログ、図書館における貸出しなどを含む技術分野における検索のために使用することができる。
【産業上の利用可能性】
【００３５】
ＲＣＩＤは、製品のアイテムの所与の１つについていかなる情報でも効率的に配置することを可能とする。したがって、本技術は、部品リコールの間に製造者に対し、大きな補助を与えることができる。典型的には、構成部品の完全なバッチを追跡することは、煩雑であり、また時間を浪費するものである。しかしながら、この新規に改善された検索方法を使用することで、欠陥部品を含むすべての出荷済み製品に迅速に対応することが可能となる。このことは、製造者の出費を削減し、劣悪な部品を使用することから危険にさらされている消費者への通知プロセスを早めることを可能とする。
【図面の簡単な説明】
【００３６】
【図１】本発明において使用するシステム・アーキテクチャの概略図。
【図２】データベース３０のデータ構成を示した図。
【図３】本発明のデータベース・システム１０のソフトウェア構成を示した図。
【図４】本発明における基本的なモニタ手法を示した図。
【図５】本発明における基本的なモニタ手法を示した図。
【図６】本発明における基本的なモニタ手法を示した図。
【図７】ＲＣＩＤテーブルの修理プロセスの機能を示した図。
【図８】本発明において用いられるアルゴリズムの擬似コードを示した図。
【図９】predictRangeの擬似コードを示した図。
【図１０】二分木検索アルゴリズムのための擬似コードを示した図。
【図１１】ＲＣＩＤテーブルを使用した参照アルゴリズムの擬似コードを示した図。
【図１２】ランタイム修正を行うための実施の形態の擬似コードを示した図。
【符号の説明】
【００３７】
１０−データベース・システム
１２−ＣＰＵ
１４−メモリ
１６−ネットワーク・デバイス
１８、２０、２２−インタフェース
２４−入力デバイス
２６−ディスプレイ・デバイス
２８−記憶デバイス
３０−データベース
３２−部品テーブル（アイテム・テーブル）
３４−ＲＣＩＤテーブル（索引テーブル）
３６−オペレーティング・システム
３８−システム・マネージャ
４０−アプリケーション
【図１】
2006178848.tif 000003
【図２】
2006178848.tif 000004
【図３】
2006178848.tif 000005
【図４】
2006178848.tif 000006
【図５】
2006178848.tif 000007
【図６】
2006178848.tif 000008
【図７】
2006178848.tif 000009
【図８】
2006178848.tif 000010
【図９】
2006178848.tif 000011
【図１０】
2006178848.tif 000012
【図１１】
2006178848.tif 000013
【図１２】
2006178848.tif 000014
【外国語明細書】
【Title of Invention】 A database system, a computer executable method, a computer executable program for the database system, and a method for updating an indexing tables in a database system
【Technical Field】
【０００１】
The present invention relates to a technique for updating entries of database, and particularly relates to the database system, a method and a program for creating a time-based reverse look-up table which effectively accelerates retrievals of entries of the database.
【Background Art】
【０００２】
Optimizing database searches has been the subject of much research. Indeed, every major database maker has devoted much time and energy to such optimizations. Searching individual databases has become a specific of implementation, since optimizations are so highly keyed to specific database structures.
【０００３】
The database and data stored in the database become more and more huge and the database systems are more and more utilized by a distributed computing environment. In such a circumstance, users of the database system have to pay attention to the time dependent correlation of the databases and then it is requested to enhance the search efficiency of database in which entries are updated or evolved with respect to time elapse.
【０００４】
Japanese Patent Laid-Open No. 2001-312505A (Patent Literature 1) by, Kobayashi et. al. and assigned to the same assignee of the present invention discloses the search/retrieval system of items in the database in which the items are evolved with respect to time. In the disclosed system, the items are stored as a binary data including timestamps and then a time window is added in the search query to retrieve the time weighted items. However, the disclosed method does not use any indexing data structure prepared separately with the items searched.
【Patent Literature 1】Japanese Patent Laid-Open No. 2001-312505A
【Disclosure of Invention】
【Problem to be Solved by Invention】
【０００５】
The target of the inventors is the manufacturing industry and particularly, the invention concerns tracing products as they are incorporated in more complex data structure. The inventors address the problem of reverse traceability over multiple-layers of databases which may change their schemas or relationships at any time. The present invention provides a means for quickly identifying the final product built using a specific component part, even when data-update cycle is uncertain. 
【０００６】
This patent hence concerns searching for information in a large, distributed database setting. As such, this technology is designed for efficient indexing, using cached data. The approach of the present invention differs from previous approaches in that we make use of time windows for mapping. The present invention provides a means for component-parts traceability in a changing supply chain, i.e., data-update cycle. It is possible to quickly match products and component parts, without knowing the details of the supply chain at the manufacturing time. The present solution incorporates an efficient reverse lookup table tailored to the problem of component-parts traceability in a changing supply chain, i.e., up-date cycles of the database.
【Advantage of Invention】
【０００７】
As shown hereinafter in this disclosure, the maintenance cost of these tables is tiny if parts are mostly delivered and used in order, and approaches a logarithmic execution time for error correction when there are frequent shipping or production delays and badly-ordered parts. This execution time is achieved using a Time-Weighted Binary Search Algorithm, as described in this patent.
【Means for Solving Problem】
【０００８】
We provide a means for component-parts traceability in a changing supply chain. It is possible to quickly match products and component parts, without knowing the details of the supply chain at the manufacturing time. Our solution incorporates an efficient reverse lookup table tailored to the problem of component-parts traceability in a changing supply chain.
【０００９】
According to the present invention, the maintenance cost of these tables is tiny if parts are mostly delivered and used in order, and approaches a logarithmic execution time for error correction when there are frequent shipping or production delays and badly-ordered parts. This execution time is achieved using a Time-Weighted Binary Search Algorithm, as described in the present invention.
【Best Mode for Practicing Invention】
【００１０】
Hereinafter, the present invention will be disclosed by using a specific embodiment in which the maker-supplier parts distribution database is subjected to the present reverse-tracing database references along an uncertain path. Specifically, we attempt to identify a product, by knowing one of its component parts, in a changing supply chain.
【００１１】
A. SYSTEM CONSTRUCTION
Fig. 1 shows a general system architecture used in the present invention. The system 10 comprises generally a CPU 12 for executing the method for creating reverse look-up table and a memory 14 which makes possible the processing of CPU 12 and stores execution programs and data. The system 10 further comprises a network device 16 and appropriate interfaces 18-22 such as ATA, IDE, or RS-232C etc. and each of which is interconnected to an input device 24 such as keyboard, to a display device 26, and to a storage device 28. In the storage device 28, the database 30, are stored and periodically or upon user-needs, entries of the database are updated.
【００１２】
The system 10 may be a microcomputer or a workstation operated by an operating system such as Windows (trademark), or MacOS (trademark) under PENTIUM (trademark) type processor. Alternatively, the system 10 may have the architecture of UNIX or LINUX which are processed by a RISC architecture microprocessor under the AIX (trademark) architecture. The database 30 shown in Fig. 1 may be adopted from any databases including any relational database which may be accessed by SQL language.
【００１３】
Fig. 2 shows a data construction of the database 30. The database 30 generally contains two sets of data which are referred as parts-table 32 and RCID-tables for a specific item such as S1. The parts-tables are created along with time such as t1, t2, t3,... and the creation of the parts-table may be executed periodically or every time when users need such update of the database entries. In addition, the database 30 contains other table referred by RCID-table 34 in which the update-time tn and parts-table id ({P}id) are paired therein. Because the update-time of the parts-table is unpredictable, the users of the parts-table searches his or hers desired parts-table by querying the timestamp appended thereto; however, the user can not find the parts-table directly among many time-evolved parts-table when the user does not know the exact timestamp. Therefore, it is quite useful to create the Reverse Component InDex (RCID) table as shown in Fig. 2. The another embodiment of the present invention, the parts-table 32 and the RCID-table 34 are stored in different hard-disk drive placed remote sites such as a warehouse section and a factory section and the coincidence of the parts-list and the RCID table may be attained through network.
【００１４】
Fig．3 shows a software construction of the present system 10, and the system 10 is generally constructed as 3 (three) layered software architecture. The operating system 36 layer is the lowest, i.e., basic software. The system manager 38 layer stands on the operating system 36 and executes the management of the RCID table upon request from the application 40. The application 40 provides interfaces between the database 30 and the user and makes it possible to access to the entries of the database 30 through an input-output operation or a search operation.
【００１５】
The system manager 38 is implemented with a monitor function which issues query of the most recent timestamp appended to the particular parts-table and receives the corresponding timestamp as the return value, which referred by the instruction hereafter as manufacturingTimeFast(idSi). The system manager 38 is also implemented with functions referred as Compare (), Find (), and Insert (). The function Compare () compares the returned value with the timestamp of the same {P}id stored in the RCID table to re-order or to provide maintenance of the RCID table. The function Find () compares the returned value with the sequence of the timestamps between which the parts-table is inserted. The function Insert () inserts the parts-table {P}id between the records having the timestamps which are found by the Find ().
【００１６】
In order to further explain the present invention, here some additional assumptions are provided as follows:
(1) Consider a database of products, M, and a supplier database, S. The System Manager, G, of M, may not have any control over S, or the supply chain from S to M. The system manager maintains a parts list for every product listed in M, in a product table. Because there are many products, we assume the product table is broken down into several smaller tables, based on manufacturing time. For example, a new product table might be started every month. These smaller tables are indexed in some fashion, and constitute a set of product tables, {P}.
(2) It is further assumed, in this system, queries to G which require information contained in M. The subject of the invention is efficiently finding any element of S in {P}, and therefore in M. The following features are herein assumed based directly on observations of supply chains:
(a) M, {P} and S are append-only
(b) Given an index in S, we identify S. That is, we can tell the manufacturer of any part, from the part ID.
(c) every entry in M, and S is timestamped
(d) Component parts which are manufactured at the same time are generally used for construction at the same time. We generalize this property as: Consider an element in Si with index idSij and timestamp tSij, which is referenced by idMj, at timestamp tMj. It is likely that a nearby element of Si, idSik, with timestamp tSik, such that tSij- tSik is small, will be referenced by a nearby element of A, idMk, with timestamp tMk, such that tMj-tMk is small. 
(e) Component parts are generally used in the order they arrive, and shipments are rarely delayed for a long time. Thus, it is unlikely that an older component part is used to build a newer product, once newer component parts have begun to be used.
【００１７】
This property may be generalized as: two elements in Si, with indices idSij and idSik, and timestamps tSij and tSik, respectively, such that tSij >> tSik. If these elements are referenced by idMj, at timestamp tMj and idMk at timestamp tMk, respectively, It is unlikely that tMj << tMk.
【００１８】
The basic method is to index time windows of parts manufacture in a Reverse Component InDex table, RCID. This table will match manufacturing times of component parts, to tables in {P} which likely contain that part. As per assumption (d), our goal here is to avoid implementing a complete reverse-lookup table, but to narrow the search space for reverse lookups. The RCID table is maintained by the System Manager, G, and provides a fast way to retrieve information from the component part’s databases without searching them, or accessing intermediate databases.
【００１９】
The RCID table for S maps time windows, represented by start times, t, to a specific table in {P}, indexed by some identification number, pi. The start time is a timestamp, tSj, from S, corresponding to an entry with index idSj. idSj in this case is the first index in S referenced by an element of M listed in the parts table with index pi, in a continuous batch of references. That is, it represents the manufacturing time of the first component part that was used to make a product M since table Pi was started.
【００２０】
B. RCID MAINTENANCE
The following algorithm employs an optimistic strategy. Here the assumption is provided that most component parts are delivered in order, and do not edit the RCID table if everything goes smoothly. This algorithm only updates the RCID when a new parts table has been issued, or if there is a major shipping delay, and a new parts table has been issued in the interim. Here, in the explained embodiment, the following assumptions are made:
(f) There exists an efficient means of looking up the manufacturing time of component parts which are still on the factory floor. That is, for every component part in the manufacturing center, there exists some record of its manufacturing time in an easy to access manner. Here, the above matter may be formalized with a function of manufacturingTimeFast(idSi), which returns the manufacturing time of the part Si with ID number idSi.
The above assumption (f) may be justified on the following grounds:
・It is realistic to require suppliers to provide manufacturing information on their products
・It is inexpensive to maintain such information for the short period of time that the component part is waiting to be used
・A related query may already be preformed by the manufacturer in building {P}
【００２１】
Figs. 4-6 shows the basic monitor procedure by the functions Compare (), Find (), Insert (). In Fig. 4, the parts-table {P} is queried by manufacturingTimeFast(idSi) and the manufacturingTimeFast(idSi) returns its return value t to the system manager. Then the function call Compare () is made with its variables (t, tn). Here, t is the newest timestamp of parts-table {P}id and tn is the timestamp of the same {P}id in the RCID table. In the case shown in Fig. 4, the function Compare returns positive return value, because the result is t>tn and there is no irregular order in the RCID table.
【００２２】
Fig. 5 shows another embodiment of the monitor procedure in which the parts-table appended with the id of {P}id with the timestamp tn-2. The return value of manufacturingTimeFast(idSi)=tk, and the returned value tk lies between tn-2 and tn-1. Thus the timestamp sequence of the RCID is correct so that any maintenance procedure is not required.
【００２３】
Fig. 6 shows the embodiment of the monitor procedure in which the RCID table has to be repaired. In Fig. 6, the return value tk lies between tn-2 and tn-1; however, the appended {P}id is different. Then, the RCID table has to be repaired to include the correct sequence. This repair procedure is executed by the function call of Insert [] as explained in Fig. 7.
【００２４】
Fig. 7 shows the function of repair process of the RCID table. Prior to calling the function Insert [], the system manager calls the function Compare () to determine the records between which the parts-table or parts-tables are inserted are determined. Then the system manager calls the function Predict tr to determine the insert sequence of the corresponding parts-table id {P}id and then the system manager calls the function Insert [] with the variables (t; Pi) to insert the correct records to the RCID table.
【００２５】
The algorithm is explicitly laid out in the pseudocode shown in Fig. 8. In Fig. 8, the undefined function predictRange appears, and the function predictRange is for the purpose to identify the manufacturing time of the last component part should be listed in Pj. Since elements are not ordered by component manufacturing time, the binary search, weighted by order of the manufacture of the finished product is allowed. In Fig. 9, the pseudocode of the predictRange is summarized.
【００２６】
C. TIME WEIGHTED BINARY SEARCH
The system manager, G, can call on the function manufacturingTimeSlow(idSi). This function operates the same as manufacturingTimeFast(idSi), returning the manufacturing time of a component part, Si, with index idSi. However, Si need not have been recently used; this function is used to find old batches of parts which were incorrectly mapped in the RCID. Typically this function would be implemented as a lookup in database. This function is slow in the sense that S is likely remote, and queries are expensive.
【００２７】
The essential method is to do a binary search to find the time of the next reference after time previous. In order to let this binary search do as few calls to manufacturingTimeSlow () as possible, here, elements are selected to search by manufacturing time, not by order in the table. This amounts to a binary search, over all idMi in Pi, using those idMi to find the idSi to lookup in S. The unique aspect here is that we choose the idMi based on timestamps, with differences in real time, not on record numbers.
【００２８】
The pseudocode for the binary search algorithm is shown in Fig. 10.
These functions allow predictRange to return the next index. The overhead for the computation is correctly mapped with only O(log(n)) calls to manufacturingTimeSlow () and hence the time weighted binary search does not exert heavy overhead to the system manager.
【００２９】
D. Brief Analysis of Update Algorithms of the present invention
For each new product manufactured (ie each update to {P}):
If the component part was used mostly in the order of it’s manufacturing: 
Read cost to S is zero: Write cost to RCID is zero: Computation cost is O(1): Memory used is zero: If the component part was delayed, but it’s delay has been predicted: Read cost to S is zero: Read cost to RCID is O(|RCID|) approx O(|{P}|+|number of lost shipments|): Write cost to the RCID is O(1): Computation cost is O(|RCID|): Memory used is zero: If the component part was delayed, but it’s delay has been predicted: Read cost to S (ie number of calls to manufacturingTimeSlow) is O(log(|Pi|)): Read cost to {P} is O(log(|Pi|)2): Write cost to RCID is O(|RCID|): Communication cost to each Si in {S} is O(log(n)): Computation cost is O(|RCID|+ log(|Pi|)2): Memory used is O(1)
Thus, this update algorithm operates quickly and economically unless there is a major shipping delay. In addition, if there is such a delay, expensive calls to the supplier’s database are only preformed once, and these calls are limited logarithmically.
【００３０】
E. PRODUCT LOOKUPS USING THE RCID
In the present invention, the part-table is looked-up using the RCID to enhance the search of the parts-table. The pseudocode shown in Fig. 11 demonstrates the algorithm for performing lookups using the RCID table. As shown in Fig. 11, the lookup procedure is executed by simple codes and then it is understood that the lookup procedure, i.e., the search of the parts-table is completed fast and depends almost entirely on the data stored in the parts-table.
【００３１】
Errors in the RCID table should be few, since the Time Weighted Binary Search is efficient when parts are used mostly in the order they are made. Thus, total communication to database S (i.e., calls to manufacturingTimeSlow) is O(1). Total computation time is O(|Pj|+|RCID|). The processing time without the RCID tables would be O(|P1|*|P2|*…*|Pj|* …), for every table in {P}. Thus this algorithm is a drastic improvement in computation cost.
【００３２】
In addition, the present invention, the system manager may perform runtime correction of the RCID during lookup of parts using the RCID table. If a mistake is discovered, the embodiment for such runtime correction is shown in Fig. 12. As shown in Fig. 12, the system manager may correct the RCID using shared functions used in the maintenance procedure and then the entire software code may be quite compact. Particularly, the code is very similar to the code used for badly out of order parts at production time. In particular, this code relies on the same predictRange function. Thus, the correction algorithm has equivalent costs and runtimes to those of the RCID update algorithm.
【００３３】
The program of the present invention is described by any of well known programming languages such as, for example, C, C++, and Java (trademark) and distributed by recording any computer readable media such as a flexible disk, a CD-ROM, a DVD, Magneto-Optical disk or by transmitting through a network.
【００３４】
F.  APPLICATION FIELDS
The present invention has wide application range in order to provide an efficient solution to the problem of reverse item lookups. It can be implemented for any parts supplier, with few requirements, and operates entirely autonomously. Thus, this technology enables a complete component part tracking system for all component parts used by the manufacturer, over the entire history of production. In addition, the use of time windows to narrow search spaces together with the RCID makes this technology applicable for any situation where databases are timestamped. Thus, this system could be used for searching in the technology area including; Historical Records, Security Logs, Lending Libraries and the like.
【Industrial Applicability】
【００３５】
The RCID makes it possible to efficiently locate any information about a product, given one of its items. Thus this technology can provide vast assistance to manufacturers during parts recalls. Typically, tracing an entire batch of component parts is cumbersome and time consuming. However, with this newly improved search method, it is possible to quickly locate all shipped products containing the defective parts. This will reduce expense for manufacturers, and hasten the notification process to customers who may be in danger from the use of faulty parts.
【Brief Explanation of Drawings】
【００３６】
Fig. 1 shows general system architecture used in the present invention.
Fig. 2 shows a data construction of the database 30.
Fig. 3 shows a software construction of the present system 10.
Fig. 4 shows the basic monitor procedure in the present invention.
Fig. 5 shows the basic monitor procedure in the present invention.
Fig. 6 shows the basic monitor procedure in the present invention.
Fig. 7 shows the function of repair process of the RCID table.
Fig. 8 shows the pseudocode of the algorithm explicitly laid out in the present invention.
Fig. 9 shows the pseudocode of the predictRange.
Fig. 10 shows the pseudocode for the binary search algorithm.
Fig. 11 shows the pseudocode which demonstrates the algorithm for performing lookups using the RCID table.
Fig. 12 shows the pseudocode for the embodiment of runtime correction.
【Description of Numerals】
【００３７】
10-database system
12-CPU
14-memory
16-network device
18, 20, 22-interface
24-input device
26-display device
28-storage device
30-database
32-parts tables (item tables)
34-RCID table (indexing table)
36-operating system 
38-system manager
40-application
【Claim 1】   A database system for searching items stored in a database, said database system comprising;
a database storing item tables of items appended by timestamps, said items each being categorized by timestamp into said tables, and said item tables being indexed by indexing data;
an indexing table for said indexing data, listing the earliest timestamp of said item table together with said indexing data;
a system manager for searching said item tables using said indexing table; and
a maintenance module for said indexing table, said maintenance module comprising a monitor tool for monitoring said item tables and updating said indexing tables to maintain a correlation between said item tables and said indexing table, wherein said monitor tool invokes from said item table with said indexing data the item with the newest timestamp together with said indexing data and examines said correlation of said indexing table using said invoked timestamp and said indexing data as examination keys.
【Claim 2】   The database system of claim 1, wherein said database system further includes a repair tool of said indexing table and said repair tool appends records to said indexing table in response to results of said examination of said monitor tool according to said timestamp and said indexing data.
【Claim 3】   The database system of claim 2, wherein said database system further includes a binary search tool which is employed by said repair tool.
【Claim 4】   The database search method in a database system, said database system comprising a computer including a CPU, a memory, and a storage device, said database being stored in said storage device, said database search method making said computer execute the steps of:
storing item tables of items appended by timestamps in a database, said items each being categorized by timestamp into said tables, and said item tables being indexed by indexing data;
storing an indexing table for said indexing data, listing the earliest timestamp of said item table together with said indexing data;
searching said item tables referring said indexing table, said indexing table being repaired with respect to time evolution by a maintenance module, said maintenance module executing further steps of;
monitoring the correlation between said item tables and said indexing table,
invoking from said item table said newest timestamp together with said indexing data, and
examining said correlation of said indexing table using said invoked timestamp and said indexing data as examination keys.
【Claim 5】   The database search method of claim 4, said method further making said computer execute the step of appending records to said indexing table in response to results of said examination of said monitor tool according to said timestamp and said indexing data.
【Claim 6】   The database search method of claim 3, said method further including the step of executing a binary search as part of said repairing step.
【Claim 7】   A computer executable program for a database search method in a database system, said database system comprising a computer including a CPU, a memory, and a storage device, said database being stored in said storage device, said program making said computer execute the steps of:
storing item tables of items appended by timestamps in a database, said items each being categorized by timestamp into said tables, and said item tables being indexed by indexing data;
storing an indexing table for said indexing data, listing the earliest timestamp of said item table together with said indexing data;
searching said item tables referring said indexing tables, said indexing table being repaired with respect to time evolution by a maintenance module, said maintenance module executing further steps of;
monitoring a correlation between said item tables and said indexing table,
invoking from said item table said newest timestamp together with said indexing data, and
examining said correlation of said indexing table using said invoked timestamp and said indexing data as examination keys.
【Claim 8】   The program of claim 7, said program further making said computer execute the step of appending records to said indexing table in response to results of said examination of said monitor tool according to said timestamp and said indexing data.
【Claim 9】   The program of claim 7, said program further including the step of executing a binary search using modules shared with said repairing step.
【Claim 10】  A method for updating an indexing tables in a database system, said database system comprising a computer including a CPU, a memory, and a storage device, said database being stored in said storage device, said method making said computer execute the steps of:
storing item tables of items appended by timestamps in a database, said items each being categorized by timestamp into said tables, and said item tables being indexed by indexing data;
storing an indexing table for said indexing data, listing the earliest timestamp of said item table together with said indexing data;
monitoring a correlation between said item tables and said indexing table,
invoking from said item table said newest timestamp together with said indexing data,
examining said correlation of said indexing table using said invoked timestamp and said indexing data as examination keys, and
appending records to said indexing table in response to results of said examination of said monitor tool according to said timestamp and said indexing data.
【Claim 11】  The method of claim 10, further including the step of;
executing a binary search of said database with referring said indexing table,
determining whether or not an appending of records of said indexing table is required depending on search keys, and
depending on said determination step, if said appending is required, calling a repairing function so as to append said records while executing said binary search.
【要約】
【課題】  To provide a database system, a computer executable method, a computer executable program for the database system, and a method for updating an indexing tables in a database system.
【解決手段】  A database system comprises a database storing item tables of items appended by timestamps. Each of items is further categorized by timestamp into said tables, and said item tables being indexed by indexing data. The database system further comprises an indexing table for said indexing data, listing the earliest timestamp of said item table together with said indexing data and a system manager for searching said item tables using said indexing table and a maintenance module for said indexing table.
【選択図】  Fig. 2
2006178848.tif 000015
2006178848.tif 000016
2006178848.tif 000017
2006178848.tif 000018
2006178848.tif 000019
2006178848.tif 000020
2006178848.tif 000021
2006178848.tif 000022
2006178848.tif 000023
2006178848.tif 000024
2006178848.tif 000025
2006178848.tif 000026