(57)【要約】【課題】  製品追跡システム、製品追跡方法、およびプログラムを提供すること。【解決手段】  製品追跡システム１０は、システム・マネージャ部１６と、照会マネージャ部２２とを含む情報処理装置を含んでいる。システム・マネージャ部は、供給連鎖の時間発展を含むベクトル・データと、製品の構成索引データとを生成する。照会マネージャ部２２は、製品の各パーツに対応する固有識別コードを戻させている。データベース２６は、システム・マネージャ部１６によって生成されたベクトル・データ３０と構成索引データ２８とを格納しており、システム・マネージャ部１６は、照会マネージャ部２２から照会を受け取り、データベース２６を、ベクトル・データおよびベクトル・データにより索引付けされた構成索引データを参照して検索を実行している。【選択図】図１２
2006244304.tif 000002
【特許請求の範囲】
【請求項１】
製品追跡システムであって、
システム・マネージャ部と照会マネージャ部とを備え、前記システム・マネージャ部がサプライチェーンの時間的な変化を記述するベクトル・データと製品の構成索引データとを生成し、前記ベクトル・データが前記構成索引データを索引付けしており、前記照会マネージャ部が前記製品の各パーツに対応する固有識別コードを戻させ、前記製品の識別値と少なくとも１つのパーツの識別値を含む照会を生成する、情報処理装置と、
前記システム・マネージャ部によって生成された前記ベクトル・データと前記構成索引データとを格納するデータベースとを含み、
前記システム・マネージャ部は、前記照会マネージャ部から照会を受け取り、前記データベースを、前記ベクトル・データおよび前記ベクトル・データにより索引付けされた前記構成索引データを参照して検索を実行する、製品追跡システム。
【請求項２】
前記ベクトル・データは前記データベースに格納され、前記サプライチェーンに対応して索引付けされる、請求項１に記載の製品追跡システム。
【請求項３】
前記固有識別コードは、９６ビットのバイナリ・コードである、請求項１に記載の製品追跡システム。
【請求項４】
前記製品追跡システムは、前記製品に含まれる前記パーツの階層分析に従った前記製品に含まれる特定パーツの検索システムである、請求項１に記載の製品追跡システム。
【請求項５】
情報処理装置を使用して製品追跡を行う方法であって、前記方法は、前記情報処理装置に対して、
供給連鎖の時間発展のベクトル・データおよび前記ベクトル・データにより索引づけられる製品の構成索引データを生成するステップと、
前記生成されたベクトル・データおよび前記構成索引データを格納するステップと、
照会マネージャ部が前記製品の各パーツに対応する固有識別コードを戻させ、前記製品の識別値と少なくとも１つのパーツの識別値を含む照会を生成するステップと、
照会を受け取り、データベースを前記ベクトル・データおよび前記ベクトル・データにより索引付けされた前記構成索引データを参照して検索するステップと
を実行させる、製品追跡方法。
【請求項６】
さらに、前記サプライチェーンに対応した前記ベクトル・データを作成するステップを含む請求項５に記載の製品追跡方法。
【請求項７】
前記固有識別コードは、９６ビットのバイナリ・コードである、請求項５に記載の製品追跡方法。
【請求項８】
情報処理装置を使用して製品追跡を行うプログラムであって、前記プログラムは、前記情報処理装置に対して、
サプライチェーンの時間的な変化を記述するベクトル・データおよび前記ベクトル・データにより索引づけられる製品の構成索引データを生成する手順と、
前記生成されたベクトル・データおよび前記構成索引データを格納する手順と、
照会マネージャ部が前記製品の各パーツに対応する固有識別コードを戻させ、前記製品の識別値と少なくとも１つのパーツの識別値を含む照会を生成する手順と、
照会を受け取り、データベースを前記ベクトル・データおよび前記ベクトル・データにより索引付けされた前記構成索引データを参照して検索する手順と
を実行させる、製品追跡のためのプログラム。
【請求項９】
さらに、前記供給連鎖に対応した前記ベクトル・データを作成する手順を実行させる、請求項８に記載のプログラム。
【請求項１０】
前記固有識別コードは、９６ビットのバイナリ・コードであり、前記プログラムは、前記製品に含まれるパーツの階層分析を実行する、請求項８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、製品管理に関し、より詳細には、本発明は、製品コードに対する新規なデータ構造を用いて効率的かつ迅速に構成部品の検索および追跡を可能とする、製品追跡システム、製品追跡を行うための方法、およびプログラムに関する。
【背景技術】
【０００２】
製造者にあっては、構成部品の追跡は、主要な課題となっている。車といった複雑な製品については、そのような追跡は、末端の製造者はますます責任を持たなくてはならないこととなっている。製造者は、その製品の副次的な構成部品についても責任を有しているが、部品管理のためのデータベースを管理することは、供給連鎖がより拡大し、またより流動的になっているので困難になっている。
【０００３】
他の問題点に加え、上述した環境下でソリューションを提供するために、近年では、エレクトロニック・プロダクト・コード(Electric Product Code: EPC)システムが提案されている。本発明は、EPCグローバル・ネットワーク・スタンダードに適合する企業について、無線周波数識別化(Radio Frequency Identification (RFID)でタグ付けされた部品および製品のために提案されるものである。EPCグローバルは、製品ラベリングのための規格であり、EANインターナショナルおよびユニフォーム・コード評議会(Uniform Code Council: UCC)が協働して管理している。EPCグローバル・ネットワークは、Auto-IDセンタにより開発されたシステムであり、エレクトロニック・プロダクト・コード(Electronic Product Code: EPC)およびRFID技術を普及化させるためのEPCグローバルにより維持されている。EPCグローバル・ネットワークは、下記の基本的なコンポーネントを含んでいる。
（ａ）エレクトロニック・プロダクト・コード（EPC）−ユニバーサル・プロダクト・コード(Universal Product Code: U.P.C)、すなわちバーコードのようにEPCは、製造者、製品、バージョンおよびシリアル番号を識別し、アイテムを固有に識別させる数値のセットを使用する。
（ｂ）IDシステム（EPCタグおよびリーダ）−EPCタグは、アンテナに取り付けられたマイクロチップからなる。EPCは、このタグに記録され、製造プロセス中に適用される。EPCタグは、それらのEPCを、無線周波数を使用する識別を使用してEPCリーダに対して通信する。EPCリーダは、無線周波数を使用してEPCタグと通信し、EPCミドルウェアを用いる局在化した商業情報システムへと情報を提供する。
（ｃ）EPCミドルウェア−サービスのためのこのソフトウェア規格は、EPCリーダまたはネットワーク・リーダまたはビジネス情報システムとの間でデータ交換を可能とする。
（ｄ）オブジェクト・ネーム・サービス（ONS）−ビジネス情報システムは、アイテムに関するEPCを情報に対してマッチングさせる必要がある。ONSは、コンピュータをワールド・ワイド・ウェブ(WWW)のサイトへと向かわせる、このサービスを提供する自動ネットワーク・サービスである。
（ｅ）EPC情報システム（EPCIS)−EPC情報サービスは、ユーザがEPCに基づいて取引を行っているパートナーとデータ交換を可能とする。
【０００４】
加えて、EPCグローバル・ネットワークは、フィジカル・マークアップ・ランゲージ（PML）規格を取り込むように設計されている。PMLは、XMLの拡張であり、物理世界におけるオブジェクトを識別させるためにAuto-IDセンタにより設計された。
【０００５】
EPCグローバルはまた、RosettaNetにより開発されたビジネス−ツウ−ビジネス(B2B)通信におけるebXML（電子ビジネスXML）標準を採用している。RosettaNetは、最近、ユニフォーム・コード評議会UCCに統合され、EPCで識別されるタグ−バーコードを管理する責任を有している。RosettaNetは、工業規格用途に対するebXMLへと拡張しており、B2B設定において通信される情報を詳細化することを可能としている。RosettaNetは、またebMS（ebXMLメッセージ・サービス）をその標準規格に取り込見つつあり、言語ばかりではなく、B2B通信の通信チャネルを提供する。EPCグローバルは、類似のメッセージング・サービスであるEPCメッセージングを提供しており、これもまたebXMLに適合する。
【０００６】
すなわち、供給者と製造者との間の簡単で、直接的な通信チャネルのための基盤は、敷かれているといえる。本発明の技術は、これらの条件を利用しようとするものであり、標準化された通信は、追跡技術を、より堅牢なアプリケーションとすることを可能とする。
EPCグローバル・ネットワークを用いる場合、この技術は、供給者のデータベースの横断的に閲覧することを維持する技術として捉えることができる。データベースのビュー管理として、この要求は特異的なものである。最適化された照会へのレスポンスを閲覧することについては、S. Chaudhuri, R. Krishnamurthy, S.  Potamianos, K. Shimらの”Optimizing Queries with Materialized Views.”, ICDE Proceedings 1995, P. 190-200（非特許文献１）に記載されている。その検討のほとんどは、データソースのアップデートの間にビューを管理することに費やされている。最近のいくつかのプロジェクトでは、Songting Chen, Jun Chen, Xin Zhang and Elke A. Rundensteiner, “Detection and Correction of Conflicting Source Updates for View Maintenance.”, ICDE’ 04, Boston, USA （非特許文献２）に開示されている。本発明者らの知り得る限りでは、いまだデータ供給源の関係が変化する間のビュー管理の問題に取り組んだ者はいないということができる。
【０００７】
ビュー管理に対してバージョンを付するという着想は新規でもなく、またバージョンとしてベクトルを使用するという着想も新規ではない。これらの技術は、Songting Chen, and  Bin Liu and Elke A. Rundensteiner, “Multiversion Based View Maintenance Over Distributed Data Sources”, ACM Transactions on Data source Systems (TODS),２００４年８月アクセプト、２００４年２１月に公開（非特許文献３）において、静的な関係およびメンバを含むデータソースのシステムを管理するための使用されてきている。これまでになされていない新規な技術は、複雑さが進行してゆく構成部品の階層についてデータソース管理に対して、ベクトル・バージョン付けを適用することである。
【非特許文献１】S. Chaudhuri, R. Krishnamurthy, S. Potamianos, K. Shimらの”Optimizing Queries with Materialized Views.”, ICDE Proceedings 1995, P. 190-200
【非特許文献２】Songting Chen, Jun Chen, Xin Zhang and Elke A. Runcensteiner, “Detection and Correction of Conflicting Source Updates for View Maintenance.”, ICDE’ 04, Boston, USA
【非特許文献３】Songting Chen, and  Bin Liu and Elke A. Rundensteiner, “Multiversion Based View Maintenance Over Distributed Data Sources”, ACM Transactions on Data source Systems (TODS),２００４年８月アクセプト
【発明の開示】
【発明が解決しようとする課題】
【０００８】
これまでに上述した技術が知られているが、これらの技術に対しては最終製品により完了される製品の構成部品の詳細なレコードを維持することが望まれていた。より具体的には、既存技術に対し、供給者またはアウトソーシングといった構成の変更に応答してより柔軟性を与え、自動化でき、かつ動的応答性を付与することで既存技術を改善したシステム、方法およびプログラムを提供する技術が必要とされていた。
【０００９】
本発明の対象は製造業であり、より具体的には本発明は、スキーマまたは相対関係がいつでも変化される多層の供給者のデータソースにわたり複雑な製品の部品追跡性を改善することを目的とする。本発明の別の目的は、製造者と供給者との間の変化する関係を管理する手段を提供することにある。さらに、本発明の目的は、供給者が変わる現実世界の設定において、いかなる製品の構成部品でも迅速に追跡することに対処することを目的とする。
【００１０】
本発明により解決される問題を考察するにあたり、製造者と供給者との構成を、下記のように仮定する。製品データベースおよび構成部品の供給者のデータベース{S}が存在するものとする。{S}は、その時点で参照しているデータと過去に参照したデータとの両方を含んでいる。すなわち、{S}を、古い供給者を含むすべての供給者の部品データに関するデータソースの集合とする。加えて、{S}内のデータソースSiに対して、Siで参照されるデータソースは、また{S}内に含まれているものとする。すなわち、{S}は、また、製品の製造者への供給者に対する構成部品の供給者をも再帰的に含んでいるものとする。
【００１１】
製造者は、変更される可能性のあるデータソースのスキーマおよびまた変更される可能性のあるデータソース間の関係の両方について{S}内のいかなるデータにわたって管理できないものとする。
【００１２】
このとき、いくつかの合理的な仮定を、製品追跡問題に適用できるものとする。
（ａ）製品データベースおよびすべての{S}内のデータソースは、追加されるだけであること。
（ｂ）{S}にわたり、製品からのすべての経路は、有限であり、エンドレス・ループが存在しないこと。
これらの仮定のうち（ａ）は、ほとんどの製造アプリケーションでは、製品が製造されてデータソースに追加され、けっして変更されないこと、（ｂ）は構成部品の階層の現実的なモードであり、製品が無限大の部品を有していないことから、上述した仮定は、ほとんどの製造企業で採用されるスキーマであることから妥当なものであると考えられる。
【課題を解決するための手段】
【００１３】
すなわち、本発明は、CIDテーブルとして参照される新規なデータ構造およびベクトル・バージョニング・システムを提供するものである。CIDテーブルは、バージョン化された分散されたテーブルで構成部品を識別するために用いられ、分散されたテーブルは、最終製品の構成部品階層をモデル化する。CIDテーブルは、ベクトル・バージョニング・システム（VVS）によりサポートされ、本発明の方法は、VVSを使用して、製造時点における構成部品の階層構造に沿ってCIDテーブルの構造を適正化する。
【発明の効果】
【００１４】
本発明のバージョニング・システムは、これまで未解決とされてきた、構成部品階層の変化を管理するという問題に対するソリューションを提供する。本発明のバージョニング・システムはまた、弱く関連づけられた参照データソースのシステムを管理するという問題に対する一般的なソリューションを提供することができる。
【００１５】
本発明のCIDテーブルは、データソースのＡと{S}の要素との間の関係が知られている場合に、Ａ内の所定のインデックスが付されたいかなる情報についても効率的に検索することができる。このため、ルックアップ時間がＯ（１）で部品をルックアップするためのソリューションとなる。この問題はまた、これまで未解決な問題であった。CIDテーブルの技術はまた、いかなる情報管理設定においても利用することができる。
【００１６】
本発明の技術の主要な構成は、処理が完全に“インハウス”であることにある。すなわち、すべての計算は局所的に実行され、すべての情報は局所的に格納され、供給者のデータベース内に「足跡」を残さず、むしろ、いかなる新規な通信システムを使用することがなく、また供給者に対して新規な要求を課すこともなく、この技術は既存の種々の規格を使用するのみである。RFIDタグについてのEPCグローバル規格内で機能するように特に設計されてはいるものの、本システムは、また、供給者との間での合意された別の既存の通信にも取り込ませることができる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を図面に示した特定の実施の形態をもって説明する。図１は、本発明の製品追跡システム１０を示しており、製品追跡システム１０は、概ね、オペレーティング・システム１２により与えられる指令に従ってシステムを制御するためのPENTIUM（登録商標）またはPowerPC（登録商標）またはRISCタイプCPU（図示せず）を含むマイクロコンピュータまたはワークステーションを含んでいる。オペレーティング・システムは、Windows（登録商標）XP、Windows（登録商標）200Xサーバ、Windows（登録商標）NT、MacOS（登録商標）、AIX（登録商標）、UNIX（登録商標）、LINUX（登録商標）などを含むいかなる適切なタイプのものから選択することができる。オペレーティング・システムの上部層には、Java（登録商標）アーキテクチャ１４が構築されており、Java（登録商標）は、後述する本発明により生成されるデータ構造の生成をサポートしている。本発明の製品追跡システム１０は、Java（登録商標）アーキテクチャ１４の上に、さらにシステム・マネージャ１６および照会マネージャ２２を備えている。システム・マネージャ１６は、さらにCIDテーブル・マネージャ１８とVVSマネージャ２０とを含んでおり、VVSマネージャ２０は、照会を受けた製品の構成部品の追跡のためのCIDテーブルおよびVVSデータを生成し、サポートしている。システム１０は、照会マネージャ２２を含んでおり、照会マネージャ２２は、特定の製品についての構成部品の追跡について照会要求を受け取って、システム・マネージャ１６と通信している。照会マネージャ２２の目的はシステム・マネージャ１６と製品追跡の照会にあたり通信することである。照会マネージャ２２は、製品のインデックスを使用して照会を処理しており、上述した定義に基づく１つまたはそれ以上のデータソースである{S}内に含まれる情報を要求する。
【００１８】
製品追跡システム１０はさらに、製品データベース２４を備えており、製品データベース２４は、製品識別子（プロダクトid）といった製品データおよび製品タイプ、製造日などの他のデータを格納している。製品データベース２４は、記録または読出し、または記録／読出しの両方のアクセス制御を行うため、本発明の製品追跡システム１０に直接接続されていてもよいし、製造者の工場といった遠隔サイトに配置されていてもよい。
【００１９】
システム・マネージャ１６により生成されたCIDテーブルとVVSとは、追跡データベース２６内に格納される。追跡データベース２６は、少なくとも２つのデータ領域を含んでいる。１つの領域は、CIDテーブル２８を格納していて、特定のVVSデータ３０を指定しており、他の領域は、照会を受けた製品の構成部品の追跡において本質的に使用されるVVSデータを格納している。CIDテーブル２８とVVSデータ３０とを構築するために必要なデータは、供給者のデータソースから定期的にまたはネットワーク３２を通したシステム・マネージャ１６からの要求に応答して取得される。システム・マネージャ１６は、照会マネージャ２２からの照会を受け取ると、システム１０は、例えばプロダクトidにより指定されるVVSデータを参照する。システム・マネージャ１６は、その後、VVSデータにより索引付けされたCIDテーブル２８を、プロダクトidを検索キーとして使用して検索する。目的とする部品が見出されると、システム・マネージャ１６は、照会マネージャに対して検索された結果を返してトランザクションを完了させる。
【００２０】
図２は、典型的な製品−構成部品の関係を指定した図である。製品Ｐは、多くの構成部品Ｗ、Ｆ、およびＥを含んでいる可能性があり、構成品は、図２に示されるように、それぞれさらにサブパーツＷ１、Ｗ２．．．を含んでいる可能性がある。最終製品Ｐは、図２（ａ）に示されるように、多くの構成部品およびサブパーツから構成されているので、製品Ｐは、構成部品およびサブパーツからなる木構造により特徴づけられる。本発明では、構成部品およびサブパーツは、部品に付されたRFIDタグに格納されたEPC規格に適合する９６ビットの固有識別子により表されている。最終製品はまた、最終製品を固有に識別させるための固有識別子または他のプロダクトidによりタグ付けされている。したがって、プロダクト−パーツ木のノードは、固有識別子により置き換えられることになる。
【００２１】
図３は、木構造を有するCIDテーブルの実施の形態のデータ構造を示す。図３に示されるように、車は、idＢ1、idＢ2、およびidＢ3の３つの構成部品を含んでいる。例えば、idＢ1で識別される部品は、ホイールであり、ホイールは、さらに２つの部品idC1、idC2から構成されていて、これらは具体的にはハブとタイヤである。タイヤは、さらにidD4などにより識別されたサブパーツを含んでいる。加えて、木のノードは、すべて固有のプロダクト識別値idAを含んでいるので、木のノードは、プロダクトidと特定の部品とを知るだけで照会することができる。図３に示したCIDテーブルは、小さなサイズのテーブルからなっているので、検索は効率的に行うことができる。
【００２２】
図３は、また、分散CIDテーブルの構造を示している。すべてのサブテーブルは、直接的に最終製品のID番号を参照しており、図３に示した実施の形態では、車が示されている。この特性は、製造者の製品データベースの閲覧によりすべてが検出されるという別の特徴を示すものである。
【００２３】
構成部品の供給ルートは、コスト、品質、供給量および部品のアウトソーシング化といった多くの理由により時々変更される。図４は、供給ルートが変更された構成部品またはサブパーツを示す。ハッチングされた部品は供給ルートが変更されている。図４に示した実施の形態では、ハブといったサブパーツは、新たな供給者から供給され、フレームおよび外装品は、構成部品４として新たな部品名である“ボディ”としてアウトソーシングされている。これらの変更の後、以前のCIDテーブルとは異なるエントリのCIDテーブルが生成される。従来では、CIDテーブルの変更は、システム・マネージャの大きな変更を伴いそしてユーザおよびソフトウェア・メーカに対して大きな資本投資を必要としていた。
【００２４】
CIDテーブルについてのスキーマは、いかなる時点におけるデータソースのシステムバージョンViに依存する。このため、新たなCIDは、すべての新たなバージョンについて生成される。CIDのサイズを小さく維持するために、どの時点でも新たなバージョンが発行できる。具体的には、新たなバージョンは、CIDのサイズが予め設定した限界値ｎに達した時点で発行することができる。
本発明にしたがい、上述した供給連鎖の変更は、新たなベクトル・バージョニング・システムのデータおよびVVSデータの生成を生じさせ、これらのデータは、典型的には、下記の情報を含んでいる。
（１）固有識別子Vi
（２）タイムスタンプtVi
（３）製品および備品のすべてのデータをリストした所与の時間における可変長ベクトルであって、各データが下記の情報を含むベクトル
（４）データソースの固有識別子si
（５）階層レベルにおける親データソースに対する参照；製品についてはこのフィールドは空とされる。
（６）タイムスタンプtsi
（７）このバージョンにおいてtsiが変更されたことを示すフラグ
（８）このデータソースに格納された製品のタイプPsi
【００２５】
データソース間の変更の追跡性を維持するため、本発明者らは、ベクトル・バージョニング・システムを実装させる。このバージョニング・システムは、システム内のすべてのデータソースの追跡性を維持させる、可変長ベクトルに依存する。本発明では、データに対するすべての変更が、製品の検索から検出される。このアプローチは、アップデート・タイムスタンプの意味づけに関連する不明確さを排除することができる。加えて、本発明によるバージョニングは、時間にわたる構成部品の改造における変化を可視化させることができる。ベクトル・バージョニングはまた、構成部品のルックアップの最適化のためのインフラ基盤を提供する。
【００２６】
システムのバージョニングを行うためにベクトルを使用することは、各データソースに関連して情報の独立性を維持する。この特性は、構成部品の階層が相互関連づけされたデータソースの木としてモデル化されるので都合がよく、このため、木のどの枝が変更されたか、およびどの枝が変更されずに同一に維持されているかを検索することを容易とする。ベクトル・バージョニング・システムについての要求される実装手法は、情報をＸＭＬドキュメントとして下記のように格納することである。
<version ID=uniqueID timestamp=time>
<data source ID=uniqueID parent=referenceID
time=timestamp changed=boolean type=referenceID />
…
</version>
製品タイプPsiは、製造者により決定される製品特異的なコードを使用するか、または物理マークアップ・ランゲージ（PML）規格を使用して実装することができる。バージョン・タイムスタンプは、構成部品の階層が変更された時点を参照させる。データソース・タイムは、データソースが変更された最新の時点である。製品の検索からのすべての変更は、製造者の製品データソースから得られる。
【００２７】
本発明のベクトル・バージョニング・システムは、製造時点での製品構造の断面を生成する。システムは、すべての構成部品の供給者の追跡性を維持するタイムスタンプを含む可変長ベクトルに依存している。製品の構造（新たな供給者、アウトソーシングなど）が変更されたどの時点であっても、新規なバージョンが生成される。それぞれのバージョンに対して各製品のすべての部品を索引付けする分散されたテーブルが存在し、テーブルのフォーマットは、ベクトル・バージョニング・システムの情報により決定され、最終製品を製造するために部品がどのようにして統合されたか、の木構造をモデル化している。図５（ａ）においては、VVSデータは、そのデータソースのスキーマを変更しており、この変更がタイムスタンプにより記録される。供給者のデータソースに対する変更は直接製品に影響を与え、これは逆に、ベクトル・バージョニング・システムのデータへと影響を与える。このことは、スキーマの変更通知を受け取ったシステム・マネージャが実行する。
【００２８】
図５（ｂ）は、新規な供給者が追加された場合の実施の形態を示す。製造ラインで実際に構成部品の階層における変更が通知された時点でだけ更新される。製品検査から変更を見出すことにより、バージョン変更における不明確さを無くすることができる。加えて、新規なデータソースに関連して製品データベースに通知または変更を行うことは必要とされない。
【００２９】
図５（ｃ）は、特定の供給者が以後供給しなくなった場合の実施の形態を示した図である。この状況は、Ｂからの最後の構成部品が使用された通知を受けたシステム・マネージャにより実行される。この通知は、Ｂがもはや供給者ではないこと製造サイトに配置された製造マネージャにより発行することができる。図５（ｂ）と図５（ｃ）との相違は重要である。本システムは、物理的に製造ライン上に存在しているので動的に新たな供給者を通知することができる。このため、特に通知は必要とされない。しかしながら、システム・マネージャは、供給者が停止されたたかどうかについて知ることができる類似の方法を有していない。すなわち、当該供給者からの部品の不存在は、発送の遅延である可能性もある。したがって、システム・マネージャは、システムから供給者を削除する特定の通知を受け取る必要がある。
【００３０】
構成部品の階層構造に対するすべての変更は、上述した３つの実施の形態では、排除することができる。例えば、供給者を新規な供給者に置換した時は、図５（ｂ）＋図５（ｃ）に対応し、２つの供給者の業務を単一の新たな供給者にアウトソーシングした場合には、図５（ａ）＋図５（ｂ）＋図５（ｃ）となる。
【００３１】
以下、CIDテーブルの生成および維持についていくつかの擬似コードを使用して説明する。システム・マネージャは、新規な製品が製造される時には常に、製品データベースをチェックしてCIDテーブルを更新する。加えて、システム・マネージャは供給者が停止された、または供給者がデータソースのスキーマを変更したかを通知するコマンドをモニタする。
【００３２】
図６は、新しいバージョンに対応するCIDテーブルを生成する場合の擬似コードを示す。新規なバージョンは、システム・マネージャが、供給連鎖が変更されたことを示すコマンドを受け取った時点で生成される。新規なバージョンは、以前のバージョンに対する追加的な変更を作成することにより生成される。図６に示した擬似コードにおいて、システム・マネージャは、新規なオブジェクトを生成するために古いバージョンをコピーし、その後新規なバージョンの特性を決定するため、受信したコマンドを解釈する。その後、新規なバージョンの新規なオブジェクトを用いて、新規なバージョンのための新規なCIDテーブルとして確立させる。
【００３３】
図７は、特定のバージョンのための新規なCIDテーブルを発行するための擬似コードの例を示す。まず、CIDテーブルを生成するバージョンが宣言され、その後プロダクトidがCIDテーブル内に設定される。その後、対応するバージョンが次のラインで参照されバージョンの対応するクラスが提供される。図８は、特定のバージョン（idVi）および特定のプロダクト（idBa）についての擬似コードの例を示した図である。擬似コードは、まずバージョンおよび製品の製造時をルックアップして、第１のループ内でのバージョンを認定し、第２のループでは、構成部品のid（idDBi）がコラム内に記入される。CIDテーブルは、バージョンに基づいているので、新規なCIDテーブルは、バージョンにおいて示されるデータソースにマッピングする必要がある。このマッピングは、２つのステップによって実行される。第１のステップは、トップ−ダウンでいくつのサブテーブルが分散したCIDテーブルに含まれているかを決定し、第２のステップは、各データソースの親を検索してどのテーブルが他のテーブルを参照しているかを決定する。
【００３４】
これらの２つのステップを、図９に示す、図９（ａ）には、トップ−ダウンステップが示されており、図９（ｂ）は、ボトム−アップステップを示している。各場合において、システム・マネージャが構成部品idおよびサブパーツidを検出した場合、システム・マネージャは、検出されたidを、適切な空フィールドに、所定の順番で記入してゆく。
【００３５】
すべての製品の構成部品の完全なリストを含ませるので、CIDは、新規な製品が製造された時にはいつも生成される。図１０は、新規な固有idの値を有する新規な製品が製造された場合にCIDテーブルをアップデートするための擬似コードを示す。擬似コードのアルゴリズムは、主としてすべての構成部品および製品の副次的な構成部品について、繰り返し検索を実行する。アップデートプロセスは、主にシステム・マネージャにより実行されるが、本発明ではルックアップ・サービス・マネージャといった他のエージェント・ソフトウェアを使用して構成部品idおよびサブパーツidなどの新規な製品のデータを集めることができる。エージェント・ソフトウェアは、SQL言語を使用した簡単な構成として実装でき、SQL言語で製品データベースから構成部品idおよびサブパーツidを、構成部品タイプおよびサブパーツのタイプと共に取得して、CIDテーブルをアップデートするために使用する取得したidと構成分のタイプとをリターンする。図１０に示されるように、CIDのアップデートはまず、CIDオブジェクトに索引iとタイムスタンプtimeを使用してアクセスする。ここで、索引iは、CIDテーブルに索引付けする新たなアイテムの索引である。図１０に示したアルゴリズムは、その後、CID（ｉ）がnullでないか否かをチェックすることにより、iについてCIDテーブル内にサブテーブルが存在するか否かを判断し、その後構成部品およびサブパーツのデータを取得し、CID（ｉ）がnullとなるまでパーツの階層レベルにおけるCIDテーブルにデータを追加する。この呼び出しは、CIDテーブルにリストされた最終製品におけるすべてのサブパーツについて繰り返し検索させるようにさせる。階層における変更は、データソース（idBi）が期待通りにｂｉに等しいか否かを判断することにより検出されると、システム・マネージャは、バージョンが変更されたか否かを決定し、その後関数new version()を呼び出し、その後、new version ()の下でupdateCID (idBi)を再度スタートさせる。関数new version（）を呼び出す前に、バージョン変更通知がシステム・マネージャにより受信される。
【００３６】
CIDテーブルを用いることで、製品−パーツ関係をルックアップすることが可能となる。このようなルックアップは、照会マネージャからのシステム・マネージャへと照会により実行される。図１１は、照会マネージャの擬似コードの例を示した図である。この擬似コードは、CIDテーブルを使用して最終製品についてのパーツのルックアップを完了させる。訂正されたCIDテーブルは、ベクトル・バージョニング・システムに従い、製造時刻を使用して識別される。照会は、ルックアップ・キーとして製品識別子idAiと部品識別子idBiとを含んでいる。その後、タイムスタンプtAi、バージョンViおよびパーツが照会内に設定される。検索後、決定された単一のパーツまたは複数のパーツのデータが、照会マネージャに対し、照会の戻り値として戻される。
【００３７】
図１２は、特定の製品のパーツについての製品追跡のための照会のための実施の形態を示す。照会マネージャ２２は、特定の製品idおよび構成部品またはサブパーツ・タイプまたはそれら双方を指定して照会をシステム・マネージャ１６へと発行する。システム・マネージャ１６は、照会内のパーツのパーツidを取得する。パーツidを決定した後、システム・マネージャ１６は、ケリーを受け取ってプロダクトid（pid）がリストされたベクトル・バージョニング・システムのデータを、バージョン・アナライザ１６ｂを使用して決定する。バージョン・アナライザ１６ｂは、照会を受けたプロダクトidを含むベクトル・バージョニング・システムのデータのバージョン番号またはバージョンidを決定する。ベクトル・バージョニング・システムのデータが決定されると、システム・マネージャ１６は、検索エンジン１６ａを使用して、決定されたpidをキーについてCIDテーブル（ラベルを必要とする）をベクトル・バージョニング・システムから検索する。検索エンジン１６ａは、SQLアーキテクチャまたはその他の検索アーキテクチャを実装するリレーショナル・データベースを含むいかなる従来のデータベース・ソフトウェアを用いても実装することができる。その後、システム・マネージャ１６は、さらに検索エンジンに対して、CIDテーブル内のパーツの特定パーツについて、パーツの固有識別コード(Uid)を指定して検索を実行させる。検索されたＵidは、システム・マネージャ１６に通知され、システム・マネージャ１６は、その後、Ｕid値を検索の結果として照会マネージャ２２へと戻す。
【００３８】
図１２に示した照会プロセスは、重要な部品の供給連鎖時として製造者とは独立して変更される場合における製品追跡に極めて有用である。本発明によれば、上述した供給連鎖における変更は、パーツ追跡分析に適正に考慮され、指定された製品には指定されたパーツが存在しないという照会結果を戻すような致命的な失敗を生じさせることがない。このような致命的な誤りは、供給連鎖が変更されてしまった場合に予測される。VVSデータおよびCIDテーブルは、また、検索空間を劇的に低下させるので、照会時間およびメモリおよびCPU占有時間などのハードウェア資源を劇的に削減する。
【００３９】
本発明のシステムは、パーツの製造者またはパーツのデータベースにおける索引を知ること無く全パーツのルックアップを行うように容易に拡張できる。この拡張は、典型的にはパーツのタイプについてPMLマークアップ規格を使用して実装することができる。しかしながら、製造者により広く用いられているいかなるマークアップ規格であっても本発明の構成は、可能である。パーツのタイプは、バージョン情報にリストされ、１つ以上の製造者を指定する。これらの製造者は、それぞれパーツタイプ・テーブルに登録されている。CIDテーブルが製品および製品タイプと共に照会された場合（製品および製品の製造者ではなく）、パーツのすべての製造者がチェックされる。後述する２つのアルゴリズムの擬似コードは、上述した拡張を与えることができる。
以下に示す第１の擬似コードは、ユーザ・オンデマンドにパーツ・テーブルを生成するために用いられ、僅かなメモリ領域を用いてシステム・マネージャのソフトウェア・モジュールとして容易に実装することができる。
【００４０】
SystemManager{
createPartTypesTable(idVi) { //version has id=idVi 
partTypesTable = new Mapping(); //from type to a set of database id’s
For each database with id=idDBi in the version with property id=idVi {
partTypesTable .add(type, idDBi);}}}
下記の第２の擬似コードは、パーツ・テーブルを当該バージョンについてパーツが由来するデータベースを識別して正確なCIDテーブル内のレコードに配置するために使用するアルゴリズムを示す。
LookupComponentPartFromProductAndType(index idAi, index type){
timestamp tAi = A.lookupTimestamp(idAi);
version Vi = versions.findVersion(tAi);
record Ai = CID(Vi).lookup(idAi);
index[ ] idDB[ ] = partTypesTable.lookup(type);
index part = null;
for (each idDBi in idDB[ ]){
if (Ai.idDBi != null) { part = Ai.idDBi; }
return part;}
これらのアルゴリズムは、本発明の適用例としてパーツタイプだけが知られている場合のパーツ追跡性を例示するものであって、製造業界にける本発明の別の応用例を例示する。
【００４１】
本発明の技術は、EPCglobal Network規格に適合する企業についてのRFIDによりタグ付けされた部品および製品について特に設計されている。これは、特に、EPCタグをRFIDタグの固有識別値として使用すること、およびEPC ISに通信可能なEPCミドルウェアを使用して、ONSに登録されることを必要とする。最終製造者は、固有識別子をブロードキャストする(EPC)、RFIDタグを含む部品を使用する。最終製品を製造するためにパーツを使用する場合には、RFIDタグが読み取られ、EPCが検出される。EPCは、ONSを使用して検索され、パーツに関連する情報は、EPC ISから呼び出される。EPCは、その後CIDテーブル内にパーツの固有識別子として格納される。パーツのEPCのCIDテーブル内での位置は、ONSを使用して検索され、製造者により決定される。
【００４２】
追加の副次的な部品は、パーツのEPC IS内にリストすることができるが、それら自体についてRFIDタグで個別的にラベルすることはない。この場合には、副次的な構成部品に関連する情報は、EPC ISを通してパーツ製造者から検索される。これとは別に、最終製造者がサブパーツ製造者からこの情報を直接的に検索させる場合（例えば、安全およびライアビリティ契約の一部として）、この情報は、システム・マネージャにより局所的に保存しておくことができる。
【００４３】
最終製品がその製造者がCIDテーブルにない構成部品を含む場合には、新規なバージョンが自動的に生成される。このため、本発明の製品追跡システムによれば、供給連鎖におけるいかなる変更での自動的に対処することができる。パーツのタイプは、PMLマークアップとしてEPC ISから検索され、新規なバージョンを生成するために使用される。バージョンから、問い合わせている最終製品から開始する新規なCIDテーブルが発行される。本発明の構成を使用するパーツのルックアップは容易である。CIDテーブルに格納されたEPCタグからパーツについてのすべての情報が、ONSおよびEPC ISを使用して検索することができる。
【産業上の利用可能性】
【００４４】
本発明のVVSおよびCIDシステムは、製造業界を超えて適用できる。VVSは、ルーズに連携した参照データベースの間において関連性を管理することができる。CIDは、データベース内での情報を索引付けする格納技術を提供する。同時に、これらの技術は、多数のデータベースからのレコードを含むいかなるデータセットについても索引付けおよび追跡性を提供することができる。この技術は、これまで汎用的なソリューションが無かった、ルーズに連携したデータベースの間における索引付けを提供する点で、特に新規なものである。
【００４５】
本発明の技術は、また、多数のパーツが本質的に同一な、例えばクレートまたはロットだけで識別されるような、単純な構成サブパーツのバッチであるような場合にでも適用することができる。この場合、クレートまたはロットIDが、CIDテーブルにおけるパーツの識別子として用いられる。この用途ではまた、リコールについての検索プロセスをスピードアップすることができる。損傷を受けたロットから各パーツを個別的に事後的に検索するのではなく、意図的に生成された固有識別子によることで、一度に単一のロットを参照するすべてのレコードについての検索が可能となる。
【００４６】
本発明の技術は、遠隔的なデータベースへのリクエストがバッチ処理されなければならない状況に対して用いるように容易に拡張することができる。CIDテーブルは、データベースの参照にしたがって分散され、このためのインフラ基盤はすでに確立されている。これは、CIDテーブルの所定の枝が、遠隔的なデータソースから照会のバッチが戻されるまでアップデートされないことを意味する。データソースが連続して使用できない場合や、接続時間が遅いまたは予測できない場合には、CIDテーブルは、特に効果的である。
【図面の簡単な説明】
【００４７】
【図１】本発明の製品追跡システム１０を示した図。
【図２】典型的な製品−構成パーツの関係を示した図。
【図３】木構造を有するCIDテーブルの実施の形態を示したデータ構造を示した図。
【図４】供給ルートが変更された構成部品およびサブパーツを示した図。ハッチングされたパーツがその供給ルートが変更されている。
【図５】ベクトル・バージョニング・システムのデータ構造の実施の形態を示した図。
【図６】新規なバージョンに対応するCIDを生成するための擬似コードを示した図。
【図７】特定のバージョンに新規なCIDテーブルを追加する場合の擬似コードを例示した図。
【図８】特定のバージョン（idVi）および特定の製品（idBa）についての擬似コードを例示した図。
【図９】（ａ）がトップ−ダウン検索を示し、（ｂ）がボトム−アップ検索を示した図。
【図１０】新規な固有のid値(Uid)を有する新規な製品について、CIDをアップデートした場合の擬似コードを例示した図。
【図１１】照会マネージャの擬似コードを例示した図であり、最終製品についての完全なルックアップのためにCIDテーブルを使用している。
【図１２】特定の製品についての照会の実施の形態を示した図。
【符号の説明】
【００４８】
１０−製品追跡システム
１２−オペレーティング・システム
１４−Java（登録商標）アーキテクチャ
１６−システム・マネージャ
１８−CIDテーブル・マネージャ
２０−VVSマネージャ
２２−照会マネージャ
２４−製品データベース
２６−追跡データベース
２８−CIDテーブル
３０−ベクトル・バージョニング・システムのデータ
３２−ネットワーク
【図１】
2006244304.tif 000003
【図２】
2006244304.tif 000004
【図３】
2006244304.tif 000005
【図４】
2006244304.tif 000006
【図５】
2006244304.tif 000007
【図６】
2006244304.tif 000008
【図７】
2006244304.tif 000009
【図８】
2006244304.tif 000010
【図９】
2006244304.tif 000011
【図１０】
2006244304.tif 000012
【図１１】
2006244304.tif 000013
【図１２】
2006244304.tif 000014
【外国語明細書】
【Title of Invention】 A product traceability system, a method for product tracing, and a program
【Technical Field】
【０００１】
The present invention relates to product management, and more practically, the present invention relates to a product traceability system, a method for product tracing, and a program which makes it possible to search and trace component parts effectively and quickly using novel data structures of product codes.
【Background Art】
【０００２】
Tracking of component parts is a major challenge for manufactures. For complex products, such as cars, such tracking is increasingly the responsibility of the end manufacturer. Manufacturers are held accountable for the subcomponent parts of their products, but managing databases of parts for complex products is a challenge as supply chains are getting larger and more dynamic.
【０００３】
In order to facilitate solutions in such circumstances, as well as solve other problems, recently an Electronic Product Code (EPC) system has been proposed. The technology of this patent is specifically designed to work with Radio Frequency Identification (RFID)-tagged parts and products, with companies conforming to the EPCglobal Network standards. EPC Global provides standards for product labeling and is managed jointly by EAN International and the Uniform Code Council (UCC). The EPCglobal Network is the system developed by the Auto ID Center and maintained by EPC Global for leveraging the Electronic Product Code (EPC) and RFID technologies. The EPCglobal Network is comprised of the following fundamental components:
(a) ELECTRONIC PRODUCT CODE (EPC) - Like the Universal Product Code (U.P.C.) or bar code, the EPC identifies the manufacturer, product, version and serial number, and uses an extra set of digits to identify unique items.
(b) ID System (EPC Tags and Readers) - EPC Tags consist of a microchip attached to an antenna. The EPC is stored on this tag, which is applied to an item during the manufacturing process. EPC Tags communicate their EPCs to EPC Readers using Radio Frequency Identification. EPC Readers communicate with EPC Tags via radio waves and deliver information to local business information systems using EPC Middleware.
(c) EPC MIDDLEWARE - This software specification for services enables data exchange between an EPC Reader, or network of readers, and business information systems.
(d) OBJECT NAME SERVICE (ONS) - Business information systems need a way of matching the EPC to information about the associated item. The ONS is an automated networking service that provides this service by pointing computers to sites on the World Wide Web.
(e) EPC Information Systems (EPCIS) - EPC Information Services enable users to exchange data with trading partners based on EPCs.
【０００４】
In addition, the EPC Global Network is designed to incorporate Physical Markup Language (PML) specifications. PML is an extension of XML, designed by the Auto-ID Center, for identifying objects in the physical world.
【０００５】
EPCglobal has also adopted the ebXML (Electronic Business XML) standard for Business to Business (B2B) communications, as developed by RosettaNet. RosettaNet, which has recently merged with the Uniform Code Council, UCC, is responsible for managing UPC identification tags- barcodes. RosettaNet is extending ebXML for industry-specific applications, enabling detailed information be communicated in B2B settings. RosettaNet is also incorporating the ebMS (ebXML Messaging Service) into its standards base, to provide not only a language, but also a communication channel for B2B communications. EPCGlobal provides a similar messaging service, EPC Messaging, which also conforms to ebXML.
【０００６】
In short, the groundwork has been laid for easy, direct, universal communication channels between suppliers and manufacturers, and universal product identification. The technology presented in this patent is designed to take advantage of this situation; standardized communication enables traceability technology with more robust applications. 
When utilizing the EPCglobal Network, this technology can be considered a caching technology, maintaining views across suppliers’ databases. With respect to database view management, this work is unique. The use of views for optimized query responses is well described by S. Chaudhuri, R. Krishnamurthy, S. Potamianos, K. Shim. “Optimizing Queries with Materialized Views.” ICDE Proceedings 1995. P 190〜200 (Non-patent literature 1). Most research has focused on optimizing view maintenance during data source updates. Some recent projects have involved maintaining views during schema changes as described by Songting Chen, Jun Chen, Xin Zhang and Elke A. Rundensteiner, Detection and Correction of Conflicting Source Updates for View Maintenance, ICDE'04, Boston, USA (Non-patent literature 2). To the best of our knowledge, no one has yet tackled the problem of maintaining views during changes to data source relationships.
【０００７】
The notion of using versioning to manage view maintenance is not new, nor is the notion of using vectors as versions; such technologies have been employed to manage systems of data sources with static relationships and members by Songting Chen and Bin Liu and Elke A. Rundensteiner, Multiversion Based View Maintenance Over Distributed Data Sources, ACM Transactions on Data source Systems (TODS), accepted Aug. 2004, to appear in Dec. 2004 (Non-patent literature 3). What is new is the application of vector versioning to the exceedingly complex situation of data source management for component parts hierarchies.
【Non-Patent literature 1】
S. Chaudhuri, R. Krishnamurthy, S. Potamianos, K. Shim. “Optimizing Queries with Materialized Views.” ICDE Proceedings 1995. P 190〜200.
【Non-Patent literature 2】
Songting Chen, Jun Chen, Xin Zhang and Elke A. Rundensteiner, Detection and Correction of Conflicting Source Updates for View Maintenance, ICDE'04, Boston, USA
【Non-Patent literature 3】
Songting Chen and Bin Liu and Elke A. Rundensteiner, Multiversion Based View Maintenance Over Distributed Data Sources, ACM Transactions on Data source Systems (TODS), accepted Aug. 2004, to appear in Dec. 2004
【Disclosure of Invention】
【Problem to be solved by Invention】
【０００８】
As the above technologies have been claimed so far, the technologies are expected to maintain records detailing the component parts of completed products by end manufacturers. More particularly, the technologies are expected to provide a system, a method and a program that improve upon existing technologies by providing more flexibility, automation, and dynamic response to changes to suppliers, or construction, such as outsourcing.
【０００９】
The target of the present invention is the manufacturing industry. In particular, the present invention concerns parts traceability of complex products over multiple-layers of supplier’s data sources which may change their schemas or relationships at any time. Another object of the present invention is to provide means for managing the changing relationships between the manufacturer and suppliers. Further, another object of the present invention is to addresses the problem of quickly tracing the component parts of any product in the real-world setting of changing suppliers.
【００１０】
In the consideration of the problem solved by this invention, manufacturer and supplier configurations are assumed as follows: a products database and a set of component parts suppliers’ data base, {S}. {S} includes both data that are currently referenced and data that has been referenced in the past. That is, {S} is a complete set of all suppliers’ parts data including old suppliers. In addition, for any data source, Si, in {S}, the data sources that Si references are also included in {S}. That is, {S} also recursively includes component-parts suppliers to the suppliers of the product manufacturer.
【００１１】
The manufacturer may not have control over any data source in {S}, including both the schemas of the data sources, which may change, and the relationships between the data sources, which may also change. 
【００１２】
Here, several reasonable assumptions are provided for the product tracing problems as follows:
(a) The product database and all data sources in {S} are append-only
(b) All paths from products through {S} are finite; no endless loops
These assumptions are justified because most manufacturing companies adopt the schemes: (a) in most manufacturing applications, once a product is produced and entered into the data source, it is never modified; and (b) is a realistic model of a component parts hierarchy; no products have an infinite number of parts.
【Means for Solving Problem】
【００１３】
The present invention, a novel data structure named a CID table, and a vector versioning system are proposed. The CID table is used to index component parts in a versioned, distributed table, and which models the component part hierarchy of the finished product. The CID table may be supported by the vector versioning system (VVS), and a method of dynamically adjusting the structure of the CID table using the VVS, in line with the component part hierarchy at the time of manufacturing.
【Advantage】
【００１４】
This versioning system is a solution to a heretofore unsolved problem: changing component parts hierarchy management. The versioning system also presents a general solution to the problem of managing a system of loosely-coupled reference data sources.
【００１５】
The CID tables make it possible to efficiently locate any information given an index in A, if the data source relationships between A and the elements of {S} is known. Thus, this is a solution to parts lookup in O(1) lookup time. This problem is also heretofore unsolved. The technology of the CID tables is also applicable in any information management setting.
【００１６】
A key aspect of this technology is that the operation is entirely “in-house.” That is to say, all computation is preformed locally, all information is stored locally, and there are no footprints in supplier’s databases. Rather then deploy any new communication systems or place new requirements on suppliers, this technology uses a variety of established standards. While specifically designed to work within the EPC Global standards for RFID tags, this system will also integrate with other existing communication agreements with suppliers. 
【Best Mode for Practicing Invention】
【００１７】
Hereinafter, the present invention will be detailed using particular embodiments depicted in drawings. Fig. 1 shows the product traceability system 10 of the present invention and the product traceability system 10 generally comprised of a microcomputer or a workstation including a CPU (not shown) such as PENTIUM (trademark) or PowerPC (trademark) or a RISC type processor for controlling the system along with instructions provided by an operating system 12. The operating system may be selected from any adequate type including Windows (trademark) XP, Windows (trademark) 200X Server, Windows (trademark) NT, MacOS (trademark), AIX, UNIX (trademark), LINUX etc. On the upper layer of the operating system, the Java (trademark) architecture 14 is constructed which supports generating data structures generated according to the present invention as explained hereinafter. The product traceability system 10 further comprises on the Java architecture 14, the system manager 16, and the query manager 22. The system manager 16 further comprises the CID table manager 18 and the VVS manager 20 for generating and supporting the CID tables and the VVS data for tracing of the component parts of the queried products. The system 10 comprises the query manager 22 which communicates to the system manager 16, upon receiving requests for querying traces of the component parts for a particular product. The purpose of the Query manager 22, is to communicate with the system manager upon querying the trace of the products. The query manager 22 is responsible for handling queries using an index in the products, which require information contained in one or more data sources in {S}, as described in the Problem to be solved by Invention.
【００１８】
The product traceability system 10 further comprises the product database 24 which stores product data such as product identifiers (product id) and other data such as product types, production dates, etc. The product database 24 may be directly connected to the product traceability system 10 to make storage and/or read-out access controls; however, it may be placed at a remote site such as a factory of the manufacturer.
【００１９】
The CID table and the VVS generated by the system manager 16 are stored in the traceability database 26. The traceability database 26 comprises at least two data areas. One area stores the CID tables 28 designated by particular VVS data 30 and the other area sores VVS data essentially used in tracing of component parts of the queried product. Necessary data for constructing CID table 28 and VVS data 30 may be obtained from a supplier’ data source periodically or upon requests from the system manager 16 through the network 32. When the system manager 16 receives queries from the query manager 22, the system 10 refers the VVS data designated by, for example, product ids. The system manager 16 then searches the CID table 28 indexed by the VVS data using the product ids as a search key. When the targeted parts are found, the system manager 16 returns to the query manager the searched data to complete transactions.
【００２０】
Fig. 2 shows the relation of typical products-components parts. The product P may comprise many component parts W, F, and E and each of the components further comprises sub-parts W1, W2,... as shown in Fig. 2. The final product P comprises many component parts and sub-parts as shown in Fig. 2 (a) and then the product P can be characterized by a tree structure of component parts and sub-parts. In the present invention, the component parts and sub-parts are represented with a unique identifier 96 bits, conforming to EPC specification, and stored in an RFID tag on the part; the final product may also be tagged by a unique identifier or other product ids in order to uniquely identify the final product. Then, the nodes of the product-parts tree may be represented by unique identifiers.
【００２１】
Fig. 3 shows the data structures of an embodiment of CID table with the tree structure. As shown in Fig. 3, the car comprises 3 (three) component parts with idB1, idB2, and idB3. For example, the part identified with idB1 is a wheel and further comprises two (2) sub parts idC1 and idC2 which are practically a hub and a tire. The tire further comprises a sub-parts identified by idD4 etc. In addition, the nodes of the tree all includes unique product id value idA and then the nodes of the tree may be queried only knowing the product id and particular parts. The CID table shown in Fig. 3 consists of small sized tables so that the search is efficiently made.
【００２２】
Fig. 3 also demonstrates the structure of the distributed CID table. Note that all sub tables reference directly to the ID number of the final product, in this case the car. This property is another manifestation of the fact that everything is observed from the perspective of the manufacturer’s products database.
【００２３】
Supply routes of the component parts and sub-parts are sometimes changed because of many reasons such as costs, qualities, supply amounts, and outsourcing of the parts etc. Fig. 4 shows such component parts and sub-parts to which their supply routes are changed; the parts with hatchings are the parts of which the supply routes are changed. In the embodiment shown in Fig. 4, the sub-part such as a hub is supplied from a new supplier and the frame and the exterior are brought to the outsourcing as a new part name as “Body,” which is referred by Component part 4. After these changes, CID tables with different entries from the former CID tables are created. Conventionally, such change in the CID tables require large changes in the system manager and require large capital investments both for users and software makers.
【００２４】
The schema for the CID is dependant on the version, Vi, of the data source system at any given time. Thus a new CID is generated for every new version. To keep the size of the CID down, a new version can be issued at any time. In particular, it is recommended that a new version be issued whenever the size of the CID table reaches a pre-set limit, n. 
According to the present invention, such change in the supply chains causes generation of new vector versioning system data and VVS data typically include the information described below:
(1) a unique identifier, vi
(2) a timestamp, tVi
(3) a flexible-length vector enumerating all data of products and parts, at that given time, with the following information about each data:
(4) a unique identifier, si, for that data source
(5) a reference to a parent data source in hierarchy levels; for products, this field is null
(6)a timestamp, tsi
(7) a flag, changed to indicate that tsi was changed in this version
(8) a type, Psi, of the product stored in this data source.
【００２５】
To keep track of the changing relationships between data sources, we implement a Vectored Versioning System. The versioning system relies on a flexible-length vector which keeps track of all the data sources in the system. Claim 10 All changes to data sources are measured from the perspective of products. This approach removes ambiguity concerning the meaning of update timestamps. In addition, versioning in this way makes it possible to visualize changes in the component parts hierarchy over time. Vector Versioning also provides an infrastructure for optimization of component part lookups.
【００２６】
The use of a vector to version the system allows information to be kept individually about each data source. This property is useful, since the component parts hierarchy is modeled as a tree of interconnected data sources. Thus, it is easy to see which branch of the tree has been changed, and which branches remain the same. This will prove essential to building the Component InDex tables (CID tables). The recommended implementation strategy for the Vector Versioning System is to store the information in an XML document, similar to the following:
<version ID=uniqueID timestamp=time>
<data source ID=uniqueID parent=referenceID
time=timestamp changed=boolean type=referenceID />
…
</version>
The product type, Psi, could be implemented either using product specific codes, as determined by the manufacturer, or by Physical Markup Language (PML) standards. The version timestamp reflects the time of a change in the component parts hierarchy. The data source time is the last time for a change to that data source. All changes are from the perspective of products, the manufacturer’s products data source.
【００２７】
The Vector Versioning System of the present invention creates a snapshot of the structure of the product at production time. The system relies on a flexible-length vector which keeps track of all the component part suppliers, and includes timestamps. Whenever there is a change to the structure of the product (new supplier, outsourcing, etc), a new version is issued. For each version, there is a distributed table indexing all component parts of each product. The table’s format is determined by the information in the vector versioning system, and models the tree structure of how the parts are put together to create the finished product. Fig. 5 shows the embodiments of data structure of the vector versioning system. In fig. 5 (a), the VVS data illustrates that the suppliers changes their data source schema and such change is recorded with the timestamp. Any changes to the schema of suppliers’ data sources immediately affect products, and in turn the vector versioning system data. Note that this relies on the system manager receiving notification of the schema change.
【００２８】
Fig. 5 (b) shows the embodiments when a new supplier is added. The version is only updated when the change in the component parts hierarchy is actually noticed on the production line. By looking at changes from the perspective of the products, there is no ambiguity in the time of a version change. In addition, there is no need to notify or change in the product database with respect to the new data source.
【００２９】
Fig. 5 (c) shows the embodiment when a particular supplier is discontinued. This situation relies on the system manager receiving notification that the last component part from B has been used. The above notification may be issued by a production manager located at the fabrication site where B is no longer a supplier. The distinction in notification between Figs. 5 (b) and (c) is important. This system dynamically notices new suppliers, because the parts are physically present on the production line. Thus, no notification is needed. However, the system manager has no similar way of knowing if a supplier has been terminated; an absence of parts from that supplier on the production line could merely mean a shipping delay. Thus, the system manager must be specifically notified to remove a supplier from the system.
【００３０】
All changes to component parts hierarchies can be reduced to the above three examples. For instance, replacing a supplier with a new supplier corresponds to Fig. 5 (b) + Fig. 5 (c); outsourcing the work of two suppliers to a single new supplier is Fig. 5 (a) + Fig. 5 (b) + Fig. 5 (c).
【００３１】
Hereinafter, creation and maintenance of the CID table will be explained using several pseudo codes. The system manager checks the products database and updates the CID table whenever a new product is produced. In addition, the system manager monitors commands for notifying that a supplier has been discontinued, or that a supplier has changed their data source schema.
【００３２】
Fig. 6 shows the pseudo code for creating a CID corresponding to a new version. The new version may be created when the system manager receives commands for notifying a change in the supply chain. New versions are created by making incremental changes to previous versions. In the pseudo code shown in Fig. 6, the system manager creates the new version by copying old version to create a new object and then interprets the received commands for determining characteristics of the new version. Then the new object of the new version is used to build a new CID table for the new version.
【００３３】
Fig. 7 shows a sample pseudo code for issuing a new CID table for a particular version. First, the version for which the CID table is created is declared and subsequently product id is set in the CID table. Then, the corresponding version is referred in the subsequent lines to provide the corresponding class of the versions. Fig. 8 shows a sample pseudo code for the particular version (id Vi) and the particular product (idBa). The pseudo code first looks up the version and time of product manufacturing in order to verify the version in the first loop and in the second loop, the component parts ids (idDBi) are filled in the column. The CID table is based on the version, and, as such, issuing a new CID table requires mapping the data sources outlined in the version. The mapping is executed in two steps; the first step is top down- to determine how many sub tables the distributed CID table should contain and the second step is bottom up, looking at the parents of each data source to determine which tables should reference which other tables.
【００３４】
These two steps are illustrated in Fig. 9. In Fig. 9 (a), the top-down step is shown and Fig. 9 (b) shows the bottom-up step. In each of the cases, when the system manager detects component part ids and the sub-part ids, the system manager fills the detected ids into adequate empty fields in the predetermined orders.
【００３５】
The CID is updated whenever a new product is produced, since it contains a complete list of the component parts of every product. Fig. 10 shows the sample pseudo code for updating the CID table when a new product with a new unique id value. The algorithm of the pseudo code mainly executes recursive search of all component parts and sub-component parts of the product. The update process is executed mainly by the system manager; however, in the present invention, other agent software such as a lookup service manager may be used to collect the new product data such as component part ids and sub-part ids. The agent software may be implemented as simple constructions using SQL language which obtain component parts ids and sub-part ids together with component part types or sub-part types from the product database and return the obtained ids and component types used to update the CID table. As shown in Fig. 10, the CID update first accesses a CID object by the index i and the timestamp  time. Here, the index i is the index of the new item to be indexed in the CID. The algorithm shown in Fig. 10 then determines whether or not a sub table in the CID exists for i, by checking that CID(i) is not null, and then acquires the data of component parts and sub-parts and add the data in the CID table in the hierarchy levels of the parts until CID (i) is null. This call creates a recursive search for all subcomponent parts in the final product which are listed in the CID table. When the change in the hierarchy is detected by determining whether or not data source (idBi) is equal to bi (as expected), the system manager determines that version has been changed and then invokes the function new version () and then restarts updateCID (idBi) under the new version. Prior to invoking the function new Version (), it is noted that the notification of the version change is  received by the system manager.
【００３６】
Using the CID table, is becomes possible to lookup the product-part relations. Such lookup is executed by a query issued from query manager to the system manager. Fig. 11 shows the sample pseudo code of the query manager; it makes use of the CID table to complete parts lookups on finished products. The correct CID table is identified using manufacturing time, according to the vector versioning system. The query includes, as the lookup keys, a product identifier idAi, and a part identifier idDBi. Then timestamp tAi, version Vi, and the part are set in the query. After the search, the determined part or parts data are returned to the query manager as the return values of the query.
【００３７】
Fig. 12 shows the embodiment of the query for product tracing of the parts of a particular product. The query manager 22 issues the query identifying the particular product id and component part and/or sub-parts types to the system manager 16. The system manager 16 obtains parts id of the parts designated in the query. After determining the parts id, the system manager 16 receives the query and determines the vector versioning system data in which the product id (pid) is listed using the version analyzer 16b which executes the analysis in which the version number or version id of the vector versioning system data including the queried product id is determined. Once the vector versioning system data is determined, the system manager 16 searches the CID table (label needed) for the determined key, pid, from the vector versioning system using the search engine 16a. The search engine 16a may be implemented using any conventional data base software including relational databases implemented therein the SQL architecture or other search architecture. Then the system manager 16 further causes the search engine to execute searches the designated unique identifier codes of the particular parts Uid or Uids of the parts in the CID table. The Uid or Uids searched are acknowledged to the system manager 16 and the system manager 16 then returns the value such as Uid value or values to the query manager 22 to the result of the query.
【００３８】
The query process shown in Fig. 12 is quite useful in the case of product tracing when the important parts supply chain is sometimes changed independently from the manufacturer. According to the present invention, such changes in the supply chain are readily taken into account in the part tracing analysis, without fatal failures, which return the query result that the designated part could not exist in the designated product. Such the fatal errors are expected in the event that supply chain has changed. The VVS data and CID table dramatically reduce search space such that the query time and hardware resources such as memory and CPU occupation time will be dramatically reduced.
【００３９】
The present system can be trivially extended to do a complete parts lookup, without knowing the manufacturer of the part, or the database index of the part. This extension would typically be implemented using PML markup specification for the type of part. However, any markup specification universally employed by the manufacturer would enable this feature. The type of part, as listed in the version information, may indicate more then one manufacturer. Each of these manufacturers is registered in a part-types table. When the CID table is searched with a product and part-type as query (as opposed to a product and part-manufacturer), every manufacturer of the part is checked. The following pseudo codes of two algorithms provide an example of this extension:
The following first pseudo code will be used to create part tables by user on-demand and may easily be implemented in the system manager as a software module with little memory space.
【００４０】
SystemManager{
createPartTypesTable(idVi) { //version has id=idVi 
partTypesTable = new Mapping(); //from type to a set of database id’s
For each database with id=idDBi in the version with property id=idVi {
partTypesTable .add(type, idDBi);}}}
The following second pseudo code represents the algorithm which uses the parts table to identify what database the part comes from for that version, and then locates the record in the correct CID table.
LookupComponentPartFromProductAndType(index idAi, index type){
timestamp tAi = A.lookupTimestamp(idAi);
version Vi = versions.findVersion(tAi);
record Ai = CID(Vi).lookup(idAi);
index[ ] idDB[ ] = partTypesTable.lookup(type);
index part = null;
for (each idDBi in idDB[ ]){
if (Ai.idDBi != null) { part = Ai.idDBi; }
return part;}
These algorithms demonstrate the application of this patent to parts traceability, knowing only part type. This is another application of this patent in the manufacturing community.
【Industrial Applicability】
【００４１】
This technology is specifically designed to work with RFID-tagged parts and products, with companies conforming to the EPCglobal Network standards. This specifically includes: using EPCs tags as unique identifiers on the RFID tags; and employing EPC middleware that enables communication to EPC IS and registration in the ONS. The end manufacturer uses parts equipped with RFID tags, broadcasting unique identifiers (EPC). Whenever a part is used to create a finished product, the RFID tag is read, and the EPC is found. The EPC is searched using the ONS, and the information concerning the part is retrieved from the EPC IS. The EPC is then stored in the CID table as a unique identifier for the part. The location of the part’s EPC in the CID table is determined by the manufacturer, as searched using the ONS.
【００４２】
Additional subcomponent parts may be listed in the EPC IS of a part, however, may not be individually labeled with RFID tags themselves. In this situation, information about the sub-component parts is retrieved from the parts manufacturer, through the EPC IS. Alternatively, if the end manufacturer has a contract for retrieving this information directly from the sub-part manufacturer (for example, as part of a safety and liability agreement), the information may be cached locally by the system manager.
【００４３】
If a finished product contains a component part whose manufacturer is not in the CID table, a new version is automatically triggered. Then any of change in the supply chain is automatically addressed by the present product traceability system. The type of the part is retrieved from the EPC IS as PML markup, and used to create the new version. From the version, a new CID table is issued, beginning with the finished product in question. Part lookups using this infrastructure are easy. From the EPC tag stored in the CID table, all information about a part can be retrieved using the ONS and EPC IS.
【００４４】
The VVS and CID systems claimed in this patent can be used for applications beyond that of the manufacturing community. The VVS provides a method for managing relationships between loosely-coupled reference databases. The CID provides a caching technology to index the information in said databases. Together, these technologies can provide indexing and traceability solutions for any dataset which includes records from multiple databases. This technology is particularly novel, in that it provides indexing solutions between loosely coupled databases, a problem heretofore without a general solution. 
【００４５】
The present technology is also applicable to situations where multiple parts are essentially identical, for example, batches of simple subcomponent parts, identified only by crate, or lot. In this situation the crate or lot ID is used as the identifier for the part, in the CID table. This application also speeds up the search process for recalls. Rather then individually searching each part from a damaged lot, by artificially created unique identifiers, it is possible to search for all records referencing a single lot ID at once.
【００４６】
This technology is trivially extensible for use in situations where remote database requests must be batched. Since the CID table is distributed according to database references, the infrastructure already exists. This would mean that certain branches of the CID table are not updated until the batch of queries has been returned from the remote data source. In situations where data sources are not continually available, or where connection time is slow and unpredictable, this ability provides a key advantage.
【Brief Explanation of Drawings】
Fig. 1 shows the product traceability system 10 of the present invention.
Fig. 2 shows the relation of typical products-components parts.
Fig. 3 shows the data structures of an embodiment of CID table with the tree structure.
Fig. 4 shows such component parts and sub-parts to which their supply routes are changed; the parts with hatchings are the parts of which the supply routes are changed.
Fig. 5 shows the embodiments of data structure of the vector versioning system.
Fig. 6 shows the pseudo code for creating a CID corresponding to a new version.
Fig. 7 shows a sample pseudo code for appending new CID table to a particular version.
Fig. 8 shows a sample pseudo code for the particular version (id Vi) and the particular product (idBa).
Fig. 9 shows the top-down approach in Fig. 9(a) and Fig. 9 (b) shows the bottom-up approach.
Fig. 10 shows the sample pseudo code for updating the CID table when a new product with a new unique id value.
Fig. 11 shows the sample pseudo code of the query manager and it makes use of the CID table to complete parts lookups on finished products.
Fig. 12 shows the embodiment of query to the parts of a particular product.
【Brief Explanation of Numerals】
10-product traceability system
12-operating system
14-Java architecture
16-system manager
18-CID table manager
20-VVS manager
22-Query manager
24-product database
26-traceability database
28-CID table
30-vector versioning system data
32-network
【Claim 1】    A product traceability system comprising:
an information processing apparatus including a system manager part and a query manager part, said system manager part generating vector data of time evolution of supply chains and component indexing data of products, said vector data indexing said component indexing data; and said query manager part generating queries for returning unique identification codes corresponding to each part of said products and including an identification value of said product and a identification value of at least one part; and
a database storing said vector data and said component indexing data generated by said system manager part;
wherein said system manager part receives queries from said query manager part and searches said database with referring said vector data and said component indexing data indexed by said vector data.
【Claim 2】    The product traceability system of claim 1, wherein said vector data are stored in said database and indexed in correspondence to said supply chains.
【Claim 3】    The product traceability system of claim 1, wherein said unique identification code is a 96 bits binary code.
【Claim 4】    The product traceability system of claim 1, wherein said product traceability system is a search system for specific parts included in said products, distributed according to a hierarchical analysis of the parts included in said products.
【Claim 5】    A method of product tracing using an information processing apparatus, said method causing said information processing apparatus to execute the steps of:
generating vector data of time evolution of supply chains and component indexing data of products, said vector data indexing said component indexing data;
storing said vector data and said component indexing data generated;
generating queries for returning unique identification codes corresponding to each part of said products and including an identification value of said product and a identification value of at least one part;
receiving said queries and searching said database, referring to said vector data and said component indexing data indexed by said vector data.
【Claim 6】    The method of claim 5, further comprising preparing said vector data corresponding to said supply chains.
【Claim 7】    The method of claim 5, wherein said unique identification code is a 96 bits binary code.
【Claim 8】    A program for product tracing using an information processing apparatus, said program causing said information processing apparatus to execute the steps of:
generating vector data of the time evolution of supply chains and component indexing data of products, said vector data indexing said component indexing data;
storing said vector data and said component indexing data;
generating queries for returning unique identification codes corresponding to each part of said products and including an identification value of said product and an identification value of at least one part;
receiving said queries and searching said database, referring to said vector data and said component indexing data indexed by said vector data.
【Claim 9】    The program of claim 8, further causing said information processing apparatus to execute the step of preparing said vector data corresponding to said supply chains.
【Claim 10】   The program of claim 8, wherein said unique identification code is a 96 bits binary code and said program is addressed to a hierarchical analysis of parts included in said products.
【要約】
【課題】  To provide a product traceability system, a method for product tracing, and a program
【解決手段】  A product traceability system 10 comprises an information processing apparatus including a system manager part 16 and a query manager part 22. The system manager part 16 generates vector data of time evolution of supply chains and component indexing data of products and component parts. The query manager part 22 generates queries for returning unique identification codes for each part of the products. A database 26 stores the vector data 30 and the component indexing data 28 generated by the system manager part 16 wherein the system manager part 10 receives queries from the query manager part 22 and searches the database 26 by referring the vector data and the component indexing data indexed by the vector data.
【選択図】  Fig. 12
2006244304.tif 000015
2006244304.tif 000016
2006244304.tif 000017
2006244304.tif 000018
2006244304.tif 000019
2006244304.tif 000020
2006244304.tif 000021
2006244304.tif 000022
2006244304.tif 000023
2006244304.tif 000024
2006244304.tif 000025
2006244304.tif 000026