(57)【要約】      （修正有）【課題】データベースのための２つのスキーマを照合する。【解決手段】データベースのための第１のスキーマ及び第２のスキーマ内の全ての要素対について類似度値を求めるステップと、決定関数を最適化して、大域合致決定変数の集合を生成して最適化するステップを含む方法を提供するものであって、決定関数は類似度測定値及び大域合致決定変数に関するものであり、前記決定関数は等式制約及び不等式制約を受ける。【選択図】図１
2014010829.tif 000002
【特許請求の範囲】
【請求項１】
第１のスキーマ及び第２のスキーマの要素を照合する方法であって、
前記第１のスキーマ及び前記第２のスキーマ内の全ての要素対の類似度値を求めるステップと、
決定関数を最適化して、大域合致決定変数の集合を生成する、最適化するステップであって、前記決定関数は、類似度測定値及び前記大域合致決定変数に関するものであり、前記決定関数は、等式制約及び不等式制約を受ける、最適化するステップと、
を含む、第１のスキーマ及び第２のスキーマの要素を照合する方法。
【請求項２】
各前記等式制約及び各前記不等式制約は複数の前記大域合致決定変数を含む、請求項１に記載の方法。
【請求項３】
決定関数及び前記制約は線形である、請求項２に記載の方法。
【請求項４】
前記第１のスキーマは、Ｎ１個の第１の要素Ｅ１を有するＳ１であり、前記第２のスキーマは、Ｎ２個の第２の要素Ｅ２を有するＳ２である、請求項１に記載の方法。
【請求項５】
各前記スキーマは、最上レベルのルートノードと、中間ノードと、最低レベルのリーフノードとを有する階層構造を有する、請求項１に記載の方法。
【請求項６】
類似度値は第１の要素Ｅｉｊの全ての対についてｗ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）であり、前記類似度値は行列Ｗ内に記憶される、請求項４に記載の方法。
【請求項７】
大域合致決定変数は離散変数Ｄｉｊであり、｛０，１｝内の値をとり、ここで、Ｄｉｊ＝１は、要素Ｓ１．ＥｉとＳ２．Ｅｊとの間の合致を表し、Ｄｉｊ＝０は合致なしを表す、請求項４に記載の方法。
【請求項８】
決定関数はＦ（Ｗ，Ｄ）であり、最適化は前記決定関数の最大化又は最小化である、請求項６に記載の方法。
【請求項９】
前記決定関数は以下である、
【数１】
2014010829.tif 000011
請求項８に記載の方法。
【請求項１０】
不等式制約は、
全てのｉ＝１，．．．，Ｎ１について
【数２】
2014010829.tif 000012
及び
全てのｊ＝１，．．．，Ｎ２について
【数３】
2014010829.tif 000013
であり、ここで、ｂ１（ｉ）及びｂ２（ｊ）は要素Ｓ１．Ｅｉ及びＳ２．Ｅｊの最大合致数を表す、請求項８に記載の方法。
【請求項１１】
複数の大域合致決定変数Ｄは各不等式に含まれる、請求項１０に記載の方法。
【請求項１２】
前記決定関数は線形計画法を用いて解かれる、請求項３に記載の方法。
【請求項１３】
前記決定関数又は前記制約は非線形であり、前記決定関数は分岐限定プロセス、勾配降下法、又は逐次二次計画法によって解かれる、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、複数のスキーマ内の要素を照合することに関し、より詳細には、同一の概念又はエンティティを指す要素を照合することに関する。
【背景技術】
【０００２】
データベースを管理する際の１つの問題は、複数のデータベースを統合することである。データベースの構造は通常、スキーマによって定義される。各データベースが独自のデータスキーマを有しているが、複数のスキーマ内の要素が同じ概念又は物理エンティティに対応している場合、多くの場合に、要素間の明示的なマッピングを発見し確立することが必要である。
【０００３】
実際の用途は、データ移行、仮想データベース、及びデータ解析を含む。データ移行は、１つのデータベースが別のデータベースに組み込まれなくてはならないときに行われる。仮想データベースでは、複数のデータベースにアクセスするのに単一のインターフェースが用いられる。データ解析は、複数のデータベースが単一のスキーマによって定義されるときに行われる。
【０００４】
自動スキーマ照合（ＡＳＭ：Ａｕｔｏｍａｔｉｃ  Ｓｃｈｅｍａ  Ｍａｔｃｈｉｎｇ）の目的は、２つのスキーマからの要素のいずれの対が類似しているかを示すことである。スキーマが生成されるとき、通常、表される要素についての完全で明確な情報は提供されない。これによってＡＳＭは非常に困難となる。任意のそのような情報が存在する場合、その情報は通常、コンピューター処理を意図したものではない。むしろ、データベース設計者は通常、スキーマのメンテナンスを容易にするように、要素名のための適切な語又は略語を選択する。
【０００５】
ＡＳＭ問題を解決するために、要素対のための意味のある類似度値を導出することが必要である。類似度値を求めるための複数の照合方法が知られている。
【０００６】
要素名の語彙的解析は、そのような照合方法の１つの例である。有用とすることができる異なるタイプの情報は、スキーマの構造である。
【０００７】
多くの例において、スキーマは要素名の「平坦な（ｆｌａｔ）」リストによって表されるのではなく、要素は階層に編成される。例えば、要素「顧客名（ＣｕｓｔｏｍｅｒＮａｍｅ）」は、３つの下位要素「ファーストネーム（Ｆｉｒｓｔ−Ｎａｍｅ）」、「ミドルイニシャル（ＭｉｄｄｌｅＩｎｉｔｉａｌ）」、及び「ファミリーネーム（ＦａｍｉｌｙＮａｍｅ）」を有する場合がある。構造情報は、類似度値を導出するための技術に対して用いることができる。
【０００８】
ＡＳＭ技術の別の例は、２つのデータベース要素の実際の値が、例えば名称、数等にわたる同じ統計分布に由来するか否かを立証することを検討し、これを、対応するスキーマ要素が合致する証拠として用いる。辞書、辞典、及び他の補助的なデータ源がＡＳＭの目的で用いられてきた。
【０００９】
ＡＳＭ方法の目的は、照合技法のうちの１つ若しくは複数、又はそれらの組合せからの類似度値に基づいてスキーマ要素間の正しい合致を正確に判断することである。
【００１０】
ＡＳＭ方法の一例は、或る特定のしきい値を超える類似度値を有する全ての要素対が合致を宣言されるしきい値を設定することである。例えば、２つのスキーマＳ１及びＳ２、しきい値パラメーターδｔｈ、及び全ての要素対Ｓ１．Ｅｉ及びＳ２．Ｅｊ間の類似度値ｗ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）を所与とすると、合致決定変数Ｄｔｈｒｅｓｈ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）は、ｗ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）≧δｔｈの場合に１に設定され、そうでない場合、０に設定される。Ｄｔｈｒｅｓｈ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）＝１である要素対は、しきい値設定法によって合致であると宣言される。
【００１１】
この方法は、合致決定を選ぶ際にあまり選択的でなく、結果的に大きな誤差が生じる可能性がある。この方法を上回る改善形態は、ＭＡＸ１／ＤＥＬＴＡである。この方法は、Ｓ２内の全ての要素間で、Ｓ１．Ｅｉ要素が最大類似度値ｗ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）を有するか、又はこの最大値の許容範囲内にある場合、合致Ｄｍａｘ１ｄｅｌｔａ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）＝１であると判断する。同様に、他方の方向に進むとき、Ｓ１内の全ての要素間で、Ｓ２．Ｅｉ要素が最大類似度値ｗ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）を有するか、又はこの最大値の許容範囲内にある場合、要素Ｄｍａｘ１ｄｅｌｔａ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）＝１である。
【００１２】
この方法の変形形態が存在する。実際、ＭＡＸ１／ＤＥＬＴＡは、類似度値の最大性に基づいて合致決定を行うという点で、より選択的である。これは、しきい値設定と比較して、合致の尤度を良好に示す役割を果たす。
【００１３】
ＡＳＭのための最も知られた方法は、異なる照合器からの類似度値を組み合わせて単一の値にし、その組み合わされた値を用いて合致の集合を求めることによって機能する。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
第１のスキーマ及び第２のスキーマの要素を照合する方法を提供することが求められている。
【課題を解決するための手段】
【００１５】
前記第１のスキーマ及び前記第２のスキーマ内の全ての要素対の類似度値が求められる。
【００１６】
次に、決定関数が最適化され、大域合致決定変数の集合が生成される。ここで、前記決定関数は、類似度測定値及び前記大域合致決定変数に関するものであり、この決定関数は、等式制約及び不等式制約を受ける。
【発明の効果】
【００１７】
これにより、第１のスキーマ及び第２のスキーマの要素を照合する方法を提供することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の１つの実施の形態のための、スキーマ要素を照合する方法の流れ図である。
【図２】本発明の別の実施の形態のための、スキーマ要素を照合する方法の流れ図である。
【発明を実施するための形態】
【００１９】
図１及び図２は、本発明の実施の形態によるスキーマを照合する代替的な方法を示している。各方法への入力は、Ｎ１個の第１の要素を有する第１のスキーマＳ１１００、及びＮ２個の第２の要素を有する第２のスキーマＳ２１０２である。スキーマはメモリ内に記憶することができる（１１０）。
【００２０】
スキーマは階層構造を有することができ、最上レベルのルートノードと、中間ノードと、最低レベルのリーフノードとを有する。
【００２１】
いずれの方法のステップも、当該技術分野において既知のメモリ及び入出力インターフェースに接続されたプロセッサにおいて実行することができる。
【００２２】
第１の要素Ｓ１．Ｅｉ及び第２の要素Ｓ２．Ｅｊの全ての対について類似度ｗ（Ｓ１．Ｅｉ，Ｓ２．Ｅｊ）が求められ（１２０）、行列Ｗに記憶される。ここで、Ｗｉｊは要素Ｓ１．ＥｉとＳ２．Ｅｊとの間の類似度値である。
【００２３】
類似度値は、語彙情報、又は要素間の類似度を推定する他の情報を用いる照合プロセスによって求めることができる。
【００２４】
出力は大域合致決定変数Ｄｉｊ１０９であり、｛０，１｝内の値をとる離散変数である。ここで、Ｄｉｊ＝１は要素Ｓ１．ＥｉとＳ２．Ｅｊとの間の合致を表し、Ｄｉｊ＝０は合致なしを表す。
【００２５】
類似度値Ｗ及び大域合致決定変数Ｄに依拠する決定関数Ｆ（Ｗ，Ｄ）を用いる。決定関数の最適化（最大化又は最小化）によって合致決定を判断する。
【００２６】
実施の形態は以下の線形関数を用いる。
【００２７】
【数１】
2014010829.tif 000003
【００２８】
要素間の潜在的な合致の集合に対する等式制約及び不等式制約を定義する（１２１及び１２２）。等式及び不等式も線形である。関数の集合｛Ｆｅｑ１（Ｄ），Ｆｅｑ２（Ｄ），．．．，ＦｅｑＮｅ（Ｄ）｝によって表されるＮｅ個の等式が存在する。スカラーの集合｛ｂｅｑ１，．．．，ｂｅｑＮｅ｝は、等式制約の右辺を表す。
【００２９】
関数の集合｛Ｆｅｑ１（Ｄ），ｘＦｅｑ２（Ｄ），ｘ，．．．，ｘＦｅｑＮｉ（Ｄ）｝、及び不等式制約の右辺を表すスカラーの集合｛ｂｉｎｅｑ１，ｘｂｉｎｅｑ２，ｘ．．．，ｘｂｉｎｅｑＮｉ｝によって表されるＮｉ個の不等式制約が存在する。
【００３０】
本発明の好ましい実施の形態では、制約は不等式制約
全てのｉ＝１，．．．，Ｎ１について
【数２】
2014010829.tif 000004
及び
全てのｊ＝１，．．．，Ｎ２について
【数３】
2014010829.tif 000005
を含む。ここで、ｂ１（ｉ）は要素Ｓ１．Ｅｉの最大合致数を表し、ｂ２（ｊ）は要素Ｓ２．Ｅｊの最大合致数を表す。各式に複数の大域合致決定変数Ｄが含まれることに留意されたい。
【００３１】
合致決定Ｄを求めるために、制約の条件下で決定関数を最適化する（１２３）。
【００３２】
１つの実施の形態では、解かれる（１３０）最適化問題は以下である。
【００３３】
【数４】
2014010829.tif 000006
【００３４】
（式１）における最適化問題は、決定関数Ｆ（Ｗ，Ｄ）及び制約関数の線形性又は非線形性に依拠して混合整数線形計画法（ＭＩＬＰ）又は混合整数非線形計画法（ＭＩＮＬＰ）のカテゴリーに分かれる。上記の問題の解は合致決定１０９を提供し、幾つかの方法、例えば分岐限定プロセスによって解くことができる。
【００３５】
以下のように上記の問題の連続緩和も与える。
【００３６】
【数５】
2014010829.tif 000007
【００３７】
（式２）において、決定変数Ｃは、要素Ｃｉｊが０と１との間の実数に制限された行列である。上記の緩和問題の解２３０は、幾つかの方法によって効率的に見つけることができる。例えば、それらの方法は、シンプレックス法又は様々な内点法である。二値合致決定変数Ｄは、連続変数Ｃから復元することができる。
【００３８】
そのような復元手順の１つの実施の形態は、しきい値設定に基づく手順である。この手順では、Ｃｉｊが或る特定のしきい値δ１よりも大きく、かつＷｉｊが別のしきい値δ２よりも大きい場合にＤｉｊ＝１である。
【００３９】
復元手順の別の実施の形態は、下限制約Ｃｉｊ≧０に対応する双対変数λｉｊに基づいて合致決定を推測することである。現在ゼロ値のＣｉｊに非ゼロ値をとらせることに起因して生じる目的関数において、最適化問題が最大化されるので、双対変数λｉｊは減少を表す。
【００４０】
双対変数に基づく復元手順は、λｉｊ≦δ３である場合、Ｄｉｊ＝１の形態をとる。ここで、δ３はしきい値である。この手法は、感度解析に基づき、決定関数及び制約関数の線形性又は非線形性から生じる場合がある線形問題及び非線形問題の双方について成り立つ。
【００４１】
本発明の他の実施の形態は、決定関数Ｆ（Ｗ，Ｄ）又は制約が非線形である計算手順を含む。
【００４２】
１つのそのような実施の形態では、制約は以下の形態となる。
全てのｉ＝１，．．．，Ｎ１について
【数６】
2014010829.tif 000008
及び
全てのｊ＝１，．．．，Ｎ２について
【数７】
2014010829.tif 000009
また、決定関数は以下となる。
【００４３】
【数８】
2014010829.tif 000010
【００４４】
ここで、ＵｉｊｋはＤｉｊ及びＤｉｋを同時に選択することに関する対エネルギー項であり、ＶｉｋｊはＤｉｊ及びＤｋｊを同時に選ぶことに関する対エネルギー項である。
【００４５】
この問題は、勾配上昇／下降又は逐次二次計画問題等の非線形計画最適化法、それに続く上述したような復元手順を用いて、上記の（式２）で規定したような非線形計画緩和によって解かれる。
【図１】
2014010829.tif 000014
【図２】
2014010829.tif 000015
【外国語明細書】
2014010829.tif 000016
2014010829.tif 000017
2014010829.tif 000018
2014010829.tif 000019
2014010829.tif 000020
2014010829.tif 000021
2014010829.tif 000022
2014010829.tif 000023
2014010829.tif 000024
2014010829.tif 000025
2014010829.tif 000026
2014010829.tif 000027
2014010829.tif 000028
2014010829.tif 000029
2014010829.tif 000030
2014010829.tif 000031