(57)【特許請求の範囲】
【請求項１】
変数を表す部分文字列各々を用いて表現される文字列の表現パターンと、該文字列の表現において必須となる前記部分文字列各々の必須部分文字列の桁数を求める式パターンと、前記部分文字列各々が関連していることを示す関連パターンと、が関連付けて記憶された関連パターン情報テーブルを参照し、テスト対象のプログラムの入力データの制約条件を示す元制約情報から、前記文字列の表現パターンと一致する文字列を抽出し、
前記関連パターン情報テーブルを参照して、抽出した前記文字列の前記表現パターンに対応する前記式パターン及び関連パターンを取得し、
取得した前記式パターン及び前記関連パターンに、抽出した前記文字列に含まれる部分文字列を代入して、必須部分文字列と部分文字列各々が関連していることを示す関連情報を求め、
前記元制約情報に含まれる変数を表す前記部分文字列と、該部分文字列の桁数と、が関連付けられている項目定義情報を参照して、前記部分文字列に対応する前記必須部分文字列の桁数を取得し、
前記必須部分文字列に取得した前記桁数を代入し、
前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々の前記桁数を取得し、取得した前記桁数各々を前記必須部分文字列各々に対応する前記部分文字列の分割位置を求め、
前記分割位置に従い、抽出した前記文字列に含まれる前記部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振り、
前記元制約情報の抽出した前記文字列に含まれる前記部分文字列のうち分割された前記部分文字列を、分割した前記部分文字列の名称を用いた表現に変換して変換後制約情報を生成する、
処理をコンピュータに実行させるテストデータ生成プログラム。
【請求項２】
前記変換後制約情報を入力として、ＳＭＴソルバを用いて前記変換後制約情報が有する条件各々の充足値を求め、
前記充足値各々を用いて変換後制約の充足値から元制約情報の有する条件を充足するテストデータを生成する、
処理を前記コンピュータに実行させること特徴とする請求項１に記載のテストデータ生成プログラム。
【請求項３】
前記桁数を代入したすべての前記必須部分文字列に対して、複数回、前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々に前記桁数各々を、反映させて分割位置を求め、
前記桁数を代入したすべての前記必須部分文字列に対応する前回の分割位置と今回の分割位置を同じにする、
処理を前記コンピュータに実行させること特徴とする請求項１または２に記載のテストデータ生成プログラム。
【請求項４】
変数を表す部分文字列各々を用いて表現される文字列の表現パターンと、該文字列の表現において必須となる前記部分文字列各々の必須部分文字列の桁数を求める式パターンと、前記部分文字列各々が関連していることを示す関連パターンと、が関連付けて記憶された関連パターン情報テーブルを参照し、テスト対象のプログラムの入力データの制約条件を示す元制約情報から、前記文字列の表現パターンと一致する文字列を抽出し、
前記関連パターン情報テーブルを参照して、抽出した前記文字列の前記表現パターンに対応する前記式パターン及び関連パターンを取得し、
取得した前記式パターン及び前記関連パターンに、抽出した前記文字列に含まれる部分文字列を代入して、必須部分文字列と部分文字列各々が関連していることを示す関連情報を求め、
前記元制約情報に含まれる変数を表す前記部分文字列と、該部分文字列の桁数と、が関連付けられている項目定義情報を参照して、前記部分文字列に対応する前記必須部分文字列の桁数を取得し、
前記必須部分文字列に取得した前記桁数を代入し、
前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々の前記桁数を取得し、取得した前記桁数各々を前記必須部分文字列各々に対応する前記部分文字列の分割位置を求め、
前記分割位置に従い、抽出した前記文字列に含まれる前記部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振り、
前記元制約情報の抽出した前記文字列に含まれる前記部分文字列のうち分割された前記部分文字列を、分割した前記部分文字列の名称を用いた表現に変換して変換後制約情報を生成する、
こと特徴とするテストデータ生成方法。
【請求項５】
変数を表す部分文字列各々を用いて表現される文字列の表現パターンと、該文字列の表現において必須となる前記部分文字列各々の必須部分文字列の桁数を求める式パターンと、前記部分文字列各々が関連していることを示す関連パターンと、が関連付けて記憶された関連パターン情報テーブルを参照し、テスト対象のプログラムの入力データの制約条件を示す元制約情報から、前記文字列の表現パターンと一致する文字列を抽出し、
前記関連パターン情報テーブルを参照して、抽出した前記文字列の前記表現パターンに対応する前記式パターン及び関連パターンを取得し、
取得した前記式パターン及び前記関連パターンに、抽出した前記文字列に含まれる部分文字列を代入して、必須部分文字列と部分文字列各々が関連していることを示す関連情報を求め、
前記元制約情報に含まれる変数を表す前記部分文字列と、該部分文字列の桁数と、が関連付けられている項目定義情報を参照して、前記部分文字列に対応する前記必須部分文字列の桁数を取得し、
前記必須部分文字列に取得した前記桁数を代入する、生成部と、
前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々の前記桁数を取得し、取得した前記桁数各々を前記必須部分文字列各々に対応する前記部分文字列の分割位置を求める、分割部と、
前記分割位置に従い、抽出した前記文字列に含まれる前記部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振る、定義部と、
前記元制約情報の抽出した前記文字列に含まれる前記部分文字列のうち分割された前記部分文字列を、分割した前記部分文字列の名称を用いた表現に変換して変換後制約情報を生成する、制約変換部と、
を備えること特徴とするテストデータ生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムのテストに用いるテストデータを生成するテストデータ生成プログラム、テストデータ生成方法、テストデータ生成装置に関する。
【背景技術】
【０００２】
近年、充足可能性問題を解くSatisfiability Modulo Theories(ＳＭＴ)ソルバなどを用い、データが満たすべき条件の解（充足値）を求めることによって、テストデータを生成する技術が提案されている。
【０００３】
ＳＭＴソルバの時間計算量の削減は、ＳＭＴソルバの入力となる制約（ＳＭＴインスタンス）を如何に単純にできるかによって決まる。制約とは、プログラムの仕様に基づいて生成される条件やプログラムで用いるデータの取り得る範囲などである。
制約（条件）の例
文字列Ａ＝文字列Ｂかつ
文字列Ｂ＞文字列Ｃ
【０００４】
すなわち、ＳＭＴソルバの時間計算量の削減は、充足値を求める対象であるデータ（例えば、上記文字列Ａ、文字列Ｂ、文字列Ｃなど）の表現と、そのデータ表現に従った制約（例えば、制約（条件）の例）の表現により決まる。特に、業務アプリケーションにおいては、文字列項目（例えば、上記文字列Ａ、文字列Ｂ、文字列Ｃ）および文字列項目に関するＳＭＴインスタンスにおける文字列の制約の表現は、ＳＭＴソルバの実用性に大きく関わる。
【０００５】
文字列の制約の種類としては、例えば、大小関係を示す表現「Ｘ＝Ｙ」、「Ｘ＞Ｙ」、「Ｙ＞Ｘ」（辞書順の比較）、部分文字列に関する関係を示す表現、文字列長に関する関係を示す表現がある。部分文字列に関する関係を示す表現には、「subString(X, 0, 4) = Y 」（Ｘの０文字目から３文字目がＹと同じ）、「charAt(X, 0) = 'a'」（Ｘの０文字目が'a'）、「prefix(X, Y)」 （Ｘの先頭部分がＹと同じ）などがある。また、文字列長に関する関係を示す表現には、「strLength(X) = 10」（Ｘの文字数が１０）などがある。なお、文字列長に関する関係は文字の終端を示す文字に関する制約と考えると、部分文字列に関する関係ともいえる。
【０００６】
ところで、制約に用いられる文字列には前方一致や部分一致をはじめとする部分文字列に関する制約が出現することがある。
文字列制約の例
文字列１＝subString(文字列３, 0, 4)（４文字）
文字列２＝subString(文字列３, 4, 7)（３文字）
文字列４＝文字列３（１２文字）
文字列制約を充足する文字列の例
文字列１＝ＡＢＣＤ
文字列２＝ＥＦＧ
文字列３＝ＡＢＣＤＥＦＧ００００１
文字列４＝文字列３
【０００７】
文字列制約の例は、文字列３には文字列１と文字列２が含まれ、文字列３と文字列４は一致する場合を示している。上記文字列制約の例のような場合、従来、文字列１〜４各々に含まれる各文字を要素とする配列により表現して、要素ごとに充足値を求めている。
従来の文字列制約表現例
文字列１[０]＝文字列３[０]
文字列１[１]＝文字列３[１]
文字列１[２]＝文字列３[２]
文字列１[３]＝文字列３[３]
文字列２[０]＝文字列３[４]
文字列２[１]＝文字列３[５]
文字列２[２]＝文字列３[６]
文字列４[０]＝文字列３[０]
文字列４[１]＝文字列３[１]
文字列４[２]＝文字列３[２]
：
：
文字列４[１０]＝文字列３[１０]
文字列４[１１]＝文字列３[１１]
【０００８】
そのため、ＳＭＴソルバが扱う文字列が多くなるとともに、文字列１〜４の関係をも考慮しなければならないため、制約が複雑になりＳＭＴソルバの時間計算量が増加してしまう。すると、前方一致や部分一致をはじめとする部分文字列に関する制約を多く含むような、業務アプリケーションにおいて実用的な時間計算量でテストデータを生成することができない。
【０００９】
なお、関連する技術として、テスト項目作成者の誤解や読解漏れによる過ったテスト項目を作成する恐れのないテスト項目設計支援システムが開示されている。このテスト項目設計支援システムによれば、機能仕様書を入力する仕様書入力部を備えている。また、機能記述ルールを記憶する機能記述ルールファイル、項目分析ルールを記憶する項目分析ルールファイル、機能記述ルールにしたがって記述された機能を原因項目と結果項目に分類し項目分析ルールに従って各項目の間の関係を分析する項目分析部を備えている。また、項目分析の結果から原因−結果グラフを自動生成する原因−結果グラフ作成部、原因−結果グラフを表示するディスプレイ装置、原因−結果グラフから原因−結果テーブルを自動作成する原因−結果テーブル変換部を備えている。また、変換された原因−結果テーブルを表示するディスプレイ装置、原因−結果テーブルからテスト項目を作成するテスト項目作成部を備えている。
【００１０】
また、関連する技術として、制約プログラミングを用いたアプリケーションプログラムにおいて、アプリケーションプログラム自体の改造を必要とすることなく、制約条件の変更を可能とする技術が開示されている。その技術によれば、アプリケーションの実行時に、制約変数管理手段により、制約定義記憶部から制約定義を読み込み、制約変数を抽出し、その制約変数名をキーとして当該制約変数のデータドメインをデータドメイン記憶部から取得する。そして、制約充足ソルバ固有の内部表現に変換して制約変数名とともに記憶する。また、制約条件構築手段により、制約定義から関係式を抽出し、記憶された制約充足ソルバ固有の内部表現に変換された制約変数を利用して、抽出した関係式を制約充足ソルバ固有の内部表現として構築する。その結果、アプリケーションとは独立に定義された制約条件から動的に制約定義を構築可能としている。
【００１１】
例えば、関連する技術として、文字列を、該文字列に含まれる文字数分の、各文字を要素（変数）とする配列で表現し、要素毎に充足値を得るという技術が知られている。
また、関連する技術として、文字列の制約条件として、大小関係のみが制約式に含まれる場合には、この文字列部分全体を変数に置き換え、大小関係を満たす充足値（数値）を得る。次に、この数値を文字列に変換することで文字列のテストデータを生成するという技術が知られている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平８−０４４５８９号公報
【特許文献２】特開２００７−３２８５８０号公報
【非特許文献】
【００１３】
【非特許文献１】「Path Feasibility Analysis for String-Manipulating Programs」、Nikolaj Bjorner, Nikolai Tillmann, and Andrei Voronkov、 http://research.microsoft.com/pubs/81181/fulltext.pdf
【非特許文献２】「SMT Solverを利用したWebアプリケーション用テストデータの生成」、藤原他、情報処理学会第72回全国大会 平成22年
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明は、制約に含まれる文字列毎に、他の文字列と関連する部分文字列を求め、該部分文字列を１つの要素に変換し、ＳＭＴソルバの時間計算量を削減するテストデータ生成プログラム、テストデータ生成方法、テストデータ生成装置を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本実施の態様のひとつであるテストデータ生成は、関連パターン情報を参照し、上記文字列のパターンと一致するプログラムの仕様に基づいて生成されるテストの条件を有する元制約情報に含まれる文字列を抽出する。関連パターン情報は、変数を表す部分文字列各々を用いて表現される文字列の表現パターン、該文字列の表現において必須となる上記部分文字列各々の桁数を求める式パターン、上記部分文字列各々の関連していることを示す関連パターン、が関連付けられている。
【００１６】
続いて、上記関連パターン情報を参照し、抽出した文字列に対応する上記式パターンを取得し、取得した上記式パターンと上記関連パターンに、抽出した上記文字列に含まれる部分文字列を代入し、必須部分文字列と関連情報を求める。
【００１７】
続いて、上記元制約情報に含まれる変数を表す上記部分文字列と、該部分文字列の桁数と、が関連付けられている項目定義情報を参照し、上記部分文字列に対応する上記必須部分文字列の桁数を取得し、上記必須部分文字列に取得した上記桁数を代入する。
【００１８】
続いて、上記桁数を代入した上記必須部分文字列と上記関連情報とを用いて、関連する該必須部分文字列各々の上記桁数を取得し、取得した上記桁数各々を上記必須部分文字列各々に対応する上記部分文字列の分割位置を示す数値とする。
【００１９】
続いて、上記分割位置に従い、抽出した上記文字列に含まれる上記部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振りる。
続いて、上記元制約情報の抽出した上記文字列に含まれる上記部分文字列のうち分割された上記部分文字列を、分割した上記部分文字列の名称を用いた表現に変換して変換後制約情報を生成する。
【００２０】
続いて、上記変換後制約情報を入力として、ＳＭＴソルバを用いて上記変換後制約情報が有する条件各々の充足値を求める。
上記充足値各々を用いて変換後制約の充足値から元制約情報の有する条件を充足するテストデータを生成する。
【発明の効果】
【００２１】
実施の形態によれば、ＳＭＴソルバの時間計算量を削減することができるという効果を奏する。 
【図面の簡単な説明】
【００２２】
【図１】テストデータ生成装置のハードウェアの一実施例を示す図である。
【図２】テストデータ生成装置の制御部と記憶部の一実施例を示す図である。
【図３】商品検索用アプリケーションの画面の一実施例を示す図である。
【図４】商品検索用アプリケーションのＤＢの一実施例を示す図である。
【図５】項目定義情報のデータ構造の一実施例を示す図である。
【図６】元制約情報の一実施例を示す図である。
【図７】テストデータ生成装置の動作の一実施例を示すフロー図である。
【図８】関連パターン情報のデータ構造の一実施例を示す図である。
【図９】生成部の動作の一実施例を示すフロー図である。
【図１０】部分文字列関連情報のデータ構造の一実施例を示す図である。
【図１１】分割部の動作の一実施例を示すフロー図である。
【図１２】項目分割情報のデータ構造の一実施例を示す図である。
【図１３】定義部の動作の一実施例を示すフロー図である。
【図１４】データ表現情報のデータ構造の一実施例を示す図である。
【図１５】制約変換部の動作の一実施例を示すフロー図である。
【図１６】変換後元制約情報の一実施例を示す図である。
【図１７】ＳＭＴソルバにより求められた充足値のデータ構造の一実施例を示す図である。
【図１８】制約変換部の動作の一実施例を示すフロー図である。
【図１９】元制約充足情報のデータ構造の一実施例を示す図である。
【発明を実施するための形態】
【００２３】
本実施の態様では、制約に含まれる文字列ごとに、複数の文字列間の関連を記憶した情報を参照して他文字列と一致する部分文字列を求め、該部分文字列を１つの要素とする配列に変換し、制約を変換する。
元の文字列制約の例
文字列１＝subString(文字列３, 0, 4)（４文字）
文字列２＝subString(文字列３, 4, 7)（３文字）
文字列４＝文字列３（１２文字）
変換後の文字列制約における文字列表現の例
文字列１＝要素１（１要素）
文字列２＝要素２（１要素）
文字列３＝要素３ 要素４ 要素５（３要素）
文字列４＝要素６ 要素７ 要素８（３要素）
変換後の文字列制約の例
要素１＝要素３
要素２＝要素４
要素６＝要素３
要素７＝要素４
要素８＝要素５
【００２４】
要素１は文字列１、要素２は文字列２、要素３、要素４、要素５は文字列３、要素６、要素７、要素８は文字列４にそれぞれ対応する。
その後、変換した制約をＳＭＴソルバの入力として充足値求め、求めた充足値を用いてテストデータを生成する。その結果、ＳＭＴソルバの時間計算量を削減することができる。
【００２５】
以下図面に基づいて、本発明の実施形態について詳細を説明する。
テストデータ生成装置１について説明する。
図１は、テストデータ生成装置のハードウェアの一実施例を示す図である。テストデータ生成装置１は、制御部２、記憶部３、記録媒体読取装置４、入出力インタフェース５（入出力Ｉ／Ｆ）、通信インタフェース６（通信Ｉ／Ｆ）などを備えている。また、上記各構成部はバス７によってそれぞれ接続されている。
【００２６】
制御部２は、後述する生成部２０１、分割部２０２、定義部２０３、制約変換部２０４、充足値生成部２０５、充足値変換部２０６などを有している。また、制御部２はCentral Processing Unit（ＣＰＵ）、マルチコアＣＰＵ、プログラマブルなデバイス（Field Programmable Gate Array（ＦＰＧＡ）、Programmable Logic Device（ＰＬＤ）など）を用いることが考えられる。
【００２７】
記憶部３は、制御部２が実行するプログラムや後述する関連パターン情報２０７、元制約情報２０８、項目定義情報２０９、元制約充足情報２１０を記憶している。また、部分文字列関連情報２１１、項目分割情報２１２、データ表現情報２１３、変換後制約情報２１４、変換後制約充足値情報２１５などを記憶している。記憶部３は、例えばRead Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）などのメモリやハードディスクなどが考えられる。なお、記憶部３にはパラメータ値、変数値などのデータを記録してもよいし、実行時のワークエリアとして用いてもよい。上記関連パターン情報２０７、元制約情報２０８、項目定義情報２０９、元制約充足情報２１０を記憶している。また、部分文字列関連情報２１１、項目分割情報２１２、データ表現情報２１３、変換後制約情報２１４、変換後制約充足値情報２１５などは、データベースに記録されていてもよい。
【００２８】
記録媒体読取装置４は、制御部２の制御に従って記録媒体８に対するデータのリード／ライトを制御する。そして、記録媒体８に記録媒体読取装置４の制御で書き込まれたデータを記録させたり、記録媒体８に記録されたデータを読み取らせたりする。また、着脱可能な記録媒体８は、コンピュータで読み取り可能なnon-transitory（非一時的）な記録媒体として、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、ハードディスク装置（ＨＤＤ）などがある。光ディスクには、Digital Versatile Disc（ＤＶＤ）、ＤＶＤ−ＲＡＭ、Compact Disc Read Only Memory（ＣＤ−ＲＯＭ）、ＣＤ−Ｒ(Recordable)／ＲＷ（ReWritable）などがある。光磁気記録媒体には、Magneto-Optical disk（ＭＯ）などがある。なお、記憶部３もnon-transitory（非一時的）な記録媒体に含まれる。
【００２９】
入出力インタフェース５には、入出力部９が接続され、利用者が入力した情報（例えば、プログラムや仕様などのデータ）を受信し、バス７を介して制御部２または記憶部３などに送信する。また、制御部２からの命令に従ってディスプレイの画面上に出力情報（プログラムのテスト結果やテストデータなど）や操作情報などを表示する。入出力部９の入力装置は、例えば、キーボード、ポインティングデバイス（マウスなど）、タッチパネルなどが考えられる。なお、入出力部９の出力部であるディスプレイは、例えば、液晶ディスプレイなどが考えられる。また、出力部はCathode Ray Tube（ＣＲＴ）ディスプレイ、プリンタなどの出力装置であってもよい。
【００３０】
通信インタフェース６は、Local Area Network（ＬＡＮ）接続やインターネット接続や無線接続を行うためのインタフェースである。また、通信インタフェース６は必要に応じ、他のコンピュータとの間のＬＡＮ接続やインターネット接続や無線接続を行うためのインタフェースである。また、他の装置に接続され、外部装置からのデータの入出力を制御する。
【００３１】
このようなハードウェア構成を有するコンピュータを用いることによって、後述する各種処理機能（例えば、図７、図９、図１１、図１３、図１５、図１８に示すフロー）が実現される。その場合システムが有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体８に記録しておくことができる。
【００３２】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの記録媒体８が販売される。また、プログラムをサーバコンピュータの記憶装置に記録しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【００３３】
プログラムを実行するコンピュータは、例えば、記録媒体８に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶部３に記録する。そして、コンピュータは、自己の記憶部３からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、記録媒体８から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【００３４】
図２は、テストデータ生成装置の制御部と記憶部の一実施例を示す図である。
生成部２０１は、後述する関連パターン情報を参照し、文字列のパターンと一致するプログラムの仕様に基づいて生成されるテストの条件を有する元制約情報に含まれる文字列を抽出する。関連パターン情報は、変数を表す部分文字列各々を用いて表現される文字列の表現パターン、該文字列の表現において必須となる前記部分文字列各々の桁数を求める式パターン、前記部分文字列各々の関連していることを示す関連パターン、が関連付けられている。また、生成部２０１は、関連パターン情報を参照し、抽出した文字列に対応する式パターンを取得し、取得した式パターンと関連パターンに、抽出した文字列に含まれる部分文字列を代入し、必須部分文字列と関連情報を求める。生成部２０１は、後述する項目定義情報を参照し、部分文字列に対応する必須部分文字列の桁数を取得し、必須部分文字列に取得した桁数を代入する。項目定義情報は、元制約情報に含まれる変数を表す部分文字列と、該部分文字列の桁数と、が関連付けられている。
【００３５】
分割部２０２は、桁数を代入した必須部分文字列と関連情報とを用いて、関連する該必須部分文字列各々の桁数を取得し、取得した桁数各々を必須部分文字列各々に対応する部分文字列の分割位置を示す数値を求める。
【００３６】
定義部２０３は、分割位置に従い、抽出した文字列に含まれる部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振る。
制約変換部２０４は、元制約情報から抽出した文字列に含まれる部分文字列のうち分割された部分文字列を、分割した部分文字列の名称を用いた表現に変換して後述する変換後制約情報を生成する。
【００３７】
充足値生成部２０５は、変換後制約情報を入力として、ＳＭＴソルバを用いて変換後制約情報が有する条件各々の充足値を求める。
充足値変換部２０６は、充足値各々を用いて変換後制約の充足値から元制約情報の有する条件を充足するテストデータを生成する。
【００３８】
テストデータ生成装置の動作について説明する。
例えば、商品検索用アプリケーションを用いて説明をする。なお、本例では商品検索用アプリケーションを用いて説明するが、商品検索用アプリケーションに限定されるものではない。図３は、商品検索用アプリケーションの画面の一実施例を示す図である。図３に示す商品検索アプリケーションは、入出力部９の出力装置に表示される商品検索画面３０１を用いて商品を検索し、検索結果をする商品検索結果画面３０５または商品検索結果画面３０７に表示する。商品検索画面３０１には、メーカ名を入力するためのテキスト入力部３０２、カテゴリ名を入力するためのテキスト入力部３０３、検索を開始するための実行ボタン３０４（「検索結果」）が配置されている。本例では、テキスト入力部３０２に「Maker1」が入力され、テキスト入力部３０３に「Category1」が入力された場合が示されている。商品検索結果画面３０５は、入力されたメーカ名またはカテゴリ名に基いて検索した結果、一致する商品がない場合に表示される画面で、「マッチする商品はありません」などのメッセージを表示する。商品検索結果画面３０７は、入力されたメーカ名またはカテゴリ名に基いて検索した結果、一致する商品がある場合に表示される画面である。商品検索結果画面３０７のテーブル３０８は、行が選択されたことを示す「選択」と、商品名を表示する「商品名」と、商品名に関連する商品コードを表示する「商品コード」とを表示する情報を有する。「選択」は、本例では選択されると「●」が表示され、選択されていない状態では「○」が表示される。「商品名」には、本例では「Product1」「Product2」・・・・が示されている。「商品コード」には、本例では空であるが実際には商品名に関連する商品コードを表示される。商品検索結果画面３０７の実行ボタン３０９（「詳細」）は、選択されると「商品名」に関連付けられている「単価」「在庫数」が表示される。商品検索結果画面３０５と商品検索結果画面３０７の実行ボタン３０６と３１０（「戻る」）は、商品検索画面３０１の画面に戻る場合に選択するボタンである。
【００３９】
商品検索用アプリケーションは、商品検索画面３０１のテキスト入力部３０２、３０３から入力されたメーカ名とカテゴリ名を用いて、記憶部３または外部のデータベースシステムなどに記憶されているデータベース（ＤＢ）を検索して商品検索結果を求める。ＤＢの例を図４に示す。図４は、商品検索用アプリケーションのＤＢの一実施例を示す図である。ＤＢ４０１は、メーカＤＢ４０２（またはメーカテーブル）、カテゴリＤＢ４０３（またはカテゴリテーブル）、商品ＤＢ４０４（または商品テーブル）、在庫状況ＤＢ４０５（または在庫状況テーブル）を有している。メーカＤＢ４０２は、メーカ名を記憶する「名前」と、「名前」に記憶されているメーカ名各々に関連付けられているコードが記憶されている「コード」とを有している。カテゴリＤＢ４０３は、カテゴリ名を記憶する「名前」と、「名前」に記憶されているカテゴリ名各々に関連付けられているコードが記憶されている「コード」とを有している。商品ＤＢ４０４は、商品名を記憶する「商品名」と、「商品名」に記憶されている商品名各々に関連付けられている商品コードが記憶されている「商品コード」と、商品名各々に関連付けられている単価が記憶されている「単価」とを有している。在庫状況ＤＢ４０５には、商品ＤＢ４０４の「商品名」に記憶されている商品名各々関連付けられている商品コードが記憶されている「商品コード」と、商品コード各々に関連付けられている商品の在庫数が記憶されている「在庫数」とを有している。
【００４０】
商品検索用アプリケーションでは、商品検索画面３０１のテキスト入力部３０２、３０３にメーカ名とカテゴリ名が入力されて実行ボタン３０４（検索結果）が選択されると、ＤＢ４０１のメーカＤＢ４０２とカテゴリＤＢ４０３各々の「名前」を参照する。そして、入力されたメーカ名とカテゴリ名とに一致する名前を検索する。検索された場合には、メーカＤＢ４０２とカテゴリＤＢ４０３各々の名前に関連付けられているメーカＤＢ４０２とカテゴリＤＢ４０３各々のコードを用いて、該コード各々を含む商品コードが商品ＤＢ４０４の「商品コード」に存在するかを検索する。一致する商品コードが存在した場合には、商品検索結果画面３０５を表示する。また、実行ボタン３０９（詳細）が選択されると、商品ＤＢ４０４と在庫状況ＤＢ４０５を参照して、現在選択されている商品の単価と在庫数が表示される。
【００４１】
次に、商品検索用アプリケーションにおけるデータの定義について説明する。
図５は、項目定義情報のデータ構造の一実施例を示す図である。図２の項目定義情報２０９は、例えば、図５に示す画面に関する項目定義情報５０１やＤＢに関する項目定義情報５０２などがある。項目定義情報５０１は、「画面」「項目」「型」「桁」などの情報を記憶する。「画面」には、画面を識別するための識別情報が記憶されている。本例では、商品検索画面３０１を示す「検索画面」・・・・が記憶されている。「項目」には、「検索画面」に記憶されている画面に設けられている項目などを識別する情報が記憶されている。例えば、プログラムで扱う変数に対応する名称などが記憶されている。本例では、商品検索画面３０１のテキスト入力部３０２、３０３を用いて入力されるデータが代入される変数に対応する情報「メーカ」「カテゴリ」・・・・が記憶されている。「型」には、「項目」に対応する変数などのデータの型が記憶されている。データの型は、例えば、プログラムで扱うことができる変数などの型などである。本例では、「項目」の情報各々に対応する「文字列」などが記憶されている。「桁」には、「項目」に対応する変数などのデータの桁（桁数）が記憶されている。本例では、「項目」の「メーカ」「カテゴリ」・・・・に対応する「文字列」の桁「１０」が記憶されている。
【００４２】
項目定義情報５０２は、「ＤＢ」「項目」「型」「桁」などの情報を記憶する。本例では、図４のＤＢ４０１に関する項目定義情報が示されている。「ＤＢ」には、ＤＢなどに含まれるデータベース情報（またはテーブル）を識別する情報が記憶される。本例では、データベース情報としてメーカＤＢを示す「メーカ」、カテゴリＤＢを示す「カテゴリ」、商品ＤＢを示す「商品」、在庫状況ＤＢを示す「在庫状況」が記憶されている。「項目」には、「ＤＢ」に記憶さえているデータベース情報各々に対応するカラムが記憶されている。本例では、「メーカ」に関連する「項目」として「名前」「コード」と、「カテゴリ」に関連する「項目」として「名前」「コード」とが記憶されている。また、「商品」に関連する「項目」として「商品名」「商品コード」「単価」と、「在庫状況」に関連する「項目」として「商品コード」「在庫数」とが記憶されている。「型」には、「項目」に対応する変数などのデータの型が記憶されている。データの型は、例えば、プログラムで扱うことができる変数の型である。本例では、「項目」に記憶されている情報各々に対応する型として「文字列」「文字列」・・・「非負整数」「文字列」「非負整数」が記憶されている。「桁」には、「項目」に対応する変数などのデータの桁（桁数）が記憶されている。本例では、「項目」に記憶されている情報各々に対応する桁として「１０」「４」・・・「１０」「１３」「１０」が記憶されている。
【００４３】
元制約情報について説明をする。
元制約情報２０８は、仕様に基づいて生成したテスト項目と、アプリケーションで使用する各種スタブ（例えば、データベーススタブやネットワークスタブなど）の制約項目と、を用いて生成される情報である。例えば、上記商品検索用アプリケーションをテストするために用いる元制約情報を図６に示す。図６は、元制約情報の一実施例を示す図である。図６の元制約情報６０３は、テスト項目６０１（１）〜（３）と、制約項目６０２（４）〜（７）とを用いて生成される。元制約情報６０３は、例えば、テスト項目６０１（１）〜（３）と制約項目６０２（４）〜（７）に示されている条件を、形式的に記述したものである。
記述例
numOfRecord(r in T, condition)          （記述１）
subStr(X, i, j)                          （記述２）
【００４４】
上記記述１は「conditionを満たすテーブルTのレコードrの数」という意味を表し、上記記述２は「項目Xのi番目からj-1番目の文字列」という意味を表している。
【００４５】
図７は、テストデータ生成装置の動作の一実施例を示すフロー図である。
ステップＳ１０１で生成部２０１は後述する関連パターン情報２０７を用いて元制約情報２０８を解析して、後述する部分文字列関連情報２１１を生成する。
【００４６】
関連パターン情報２０７は、例えば、図８に示すようなパターンが考えられる。図８は、関連パターン情報のデータ構造の一実施例を示す図である。図８の関連パターン情報８０１は、「Ｎｏ」「表現パターン」「式パターン」「関連パターン」などの情報を有している。「Ｎｏ」には、「表現パターン」に記憶されている文字列を識別する情報が記憶されている。本例では、「Ｐ１」「Ｐ２」「Ｐ３」・・・「Ｐ１２」が記憶されている。「表現パターン」には、変数を表す部分文字列各々を用いて表現される文字列のパターンが記憶されている。本例では、表現パターンとして大小関係を示す「str1 # S」「str1 # str2」が「Ｐ１」「Ｐ２」に関連付けられて記憶されている。また、部分文字列に関する関係を示す「charAt(str1, N1) # C」「charAt(str1, N1) # charAt(str2, N2)」「subString(str1, N1, N2) # S」「subString(str1, N1, N2) # str2」「subString(str1, N1, N2) # subString(str2, N3, N4)」「prefix(str1, S)」「prefix(str1, str2)」が「Ｐ３」〜「Ｐ９」に関連付けられて記憶されている。また、文字列長に関する関係を示す「strLength(str1) = N」「strLength(str1) > N」「strLength(str1) # strLength(str2)」が「Ｐ１０」〜「Ｐ１２」に関連付けられて記憶されている。
【００４７】
上記表現パターンの記述について説明する。str[a]は、strのa番目の文字単独で構成される部分文字列を示している。str[a, b]は、a番目からb-1番目までの文字からなるstrの部分文字列を示している。chars(str, i, j)は、{str[i], str[i+1], ..., str[j-1]}を示している。d(X)は、Xの桁数（最大文字列長、Xが文字列リテラルの場合はその長さ）を示している。str連番（N）は 文字列変数を示している。連番(N)は数値を示している。Sは文字列リテラルを示している。Cは文字リテラルを示している。#は「=」「>」「<」のいずれかを示している。
【００４８】
「式パターン」には、「表現パターン」に記憶されている部分文字列の表現において必須となる部分文字列各々の変換する場合に用いる式が記憶されている。本例の式パターンについて説明する。表現パターン「str1 # S」の場合は、例えば、「str1 = "ABC"」といった制約の表現については、str1がどのような形にも分割可能であるので変換しないでよいため、本例では空を示す「−」が記憶されている。
【００４９】
表現パターン「str1 # str2」の場合は、例えば、str1の式を「{str1[0, min(d(str1), d(str2))]}」とし、str2の式を「{str2[0, min(d(str1), d(str2))]}」とする。例えば、str1が５桁、str2が６桁の文字列とする。このとき、「str1 > str2」という表現を考える。「str1 > str2」は「(str1 > str2の先頭５文字) or (str1 = str2の先頭５文字) and (str2の６文字目以降が空でない)」と捉えるため、str1[0,5]、str2[0,5]が必須部分文字列となる。なお、str2[0,5]を切り出せば、str2の６文字目以降を切り出すことができる。「min(d(str1), d(str2))」はd(str1)とd(str2)のうち小さい方の値が代入される。
【００５０】
表現パターン「charAt(str1, N1) # C」の場合は、例えば、str1の式を「{str1[N1]}」にする。なお、「charAt(str1, 4) = 'A'」といった制約の表現では、str1の４文字目（０発進)を特別扱いする。
【００５１】
表現パターン「charAt(str1, N1) # charAt(str2, N2)」の場合は、例えば、str1の式を「{str1[N1]}」にし、str2を「{str2[N2]}」にする。
表現パターン「subString(str1, N1, N2) # S」の場合は、例えば、str1の式を「{str1[N1, N2]}」にする。
【００５２】
表現パターン「subString(str1, N1, N2) # str2」の場合は、例えば、str1の式を「{str1[N1, N2]}」にし、str2の式を「{str2[0, N2-N1]}」にする。Ｎｏ「Ｐ２」の表現と同様、お互いに対応する文字が存在する部分とそうでない部分とを区別した表現を行うため、str1の「N1」から「N2-1」文字目とstr2の先頭「N2-N1」文字を切り出す。
【００５３】
表現パターン「subString(str1, N1, N2) # subString(str1, N3, N4)」の場合は、例えば、str1の式を「{str1[N1, N2]}」にし、str2の式を「{str2[N3, N4]}」にする。
表現パターン「prefix(str1, S)」の場合は、例えば、str1の式を「{srt1[0, d(S)]}」にする。「prefix(str1, "ABC")」という表現は、「str1[0,3]="ABC"」と等価である。「d("ABC")=3」に注意。
【００５４】
表現パターン「prefix(str1, str2)」の場合は、例えば、str1の式を「chars(srt1, 0, d(str2))」にし、str2の式を「chars(str2, 0, d(str2))」にする。str2の長さが可変であるので、「str1, str2」について、str2の桁数−1番目までの全ての文字を分けて考える。
【００５５】
表現パターン「strLength(str1) = N」の場合は、例えば、str1の式を「{str1[N-1], str1[N]}」にする。「strLength(str1) = 4」は「str1[3] != '\0' and str1[4] = '\0'」と捉えるため、str1の３文字目と４文字目を切り出す。
【００５６】
表現パターン「strLength(str1) > N」の場合は、例えば、str1の式を「{str1[N]}」にする。
表現パターン「strLength(str1) # strLength(str2)」の場合は、例えば、str1の式を「chars(srt1, 0, min(d(str1), d(str2)))」にし、str2の式を「chars(str2, 0, min(d(str1), d(str2)))」にする。str1、str2の長さが可変であるので、お互いに対応する文字が存在する全ての文字は切り出す。
【００５７】
「関連パターン」には、部分文字列各々が関係していることを示す情報が記憶されている。例えば、「{str1 <-> str2}」は、str1とstr2の部分文字列が関係していることを示している。
【００５８】
ステップＳ１０１の動作について図９を用いて説明する。
図９は、生成部の動作の一実施例を示すフロー図である。ステップＳ２０１では、生成部２０１が元制約情報２０８の未選択の文字列を抽出する。例えば、図６の（１）〜（７）から文字列を抽出する。
抽出した文字列の例
r.名前 = 検索画面.メーカ
【００５９】
上記抽出した文字列の例は、図６の元制約情報６０３の（１）の行から抽出した文字列である。文字列の抽出は、予め記憶部３に記憶されている文字列に示されている表現各々と、元制約情報２０８に記憶されている文字列の表現とを、例えば、パターンマッチングなどの技術を用いて比較し、パターンが一致する文字列を抽出する。なお、パターンマッチング以外でも、文字列の表現が一致することが判定できれば限定されるものではない。
【００６０】
ステップＳ２０２では、生成部２０１がステップＳ２０１でパターンが一致する文字列が抽出されたか否かを判定し、文字列が抽出されない場合には生成部２０１の処理を終了（Ｙｅｓ）し、抽出された場合はステップＳ２０３（Ｎｏ）に移行する。文字列が抽出されない場合とは、元制約情報２０８にパターンが一致する文字列がないか、または元制約情報２０８に含まれている文字列についてすべてを抽出してしまい、これ以上抽出すべき文字列がないことを示している。
【００６１】
ステップＳ２０３では、生成部２０１がステップＳ２０１で抽出した文字列に対して、関連パターン情報２０７のうち未選択の表現パターンを取得する。例えば、図８のＰ１から順番に行を選択し「表現パターン」に記憶されている文字列を取得することが考えられる。
【００６２】
ステップＳ２０４では、生成部２０１が抽出した文字列と取得した表現パターンを比較し、パターンが一致する場合にはステップＳ２０５（Ｙｅｓ）に移行し、一致しない場合にはステップＳ２０６（Ｎｏ）に移行する。例えば、上記抽出した文字列の例の場合、図８の関連パターン情報８０１の「Ｎｏ」「Ｐ２」と一致する。
【００６３】
ステップＳ２０５では、生成部２０１が一致した表現パターンを記憶部３に記憶する。
ステップＳ２０６では、生成部２０１が現在選択されている文字列に対して関連パターン情報２０７の表現パターンを全て選択したか否かを判定し、全ての表現パターンが選択されていればステップＳ２０６（Ｙｅｓ）に移行する。未選択の表現パターンがなければステップＳ２０３（Ｎｏ）に移行する。関連パターン情報８０１の例であれば、「Ｎｏ」「Ｐ１」から「Ｐ１２」までの表現をすべて選択した場合にステップＳ２０７（Ｙｅｓ）に移行する。
【００６４】
ステップＳ２０７では、生成部２０１が一致した文字列に含まれる変数となる部分文字列を、関連パターン情報２０７の「式パターン」に記憶されている式に当てはめて、部分文字列関連情報２１１に記憶する。
【００６５】
例えば、上記抽出した文字列の例について説明する。抽出した文字列が「r.名前 = 検索画面.メーカ」とすると、一致する表現パターンは関連パターン情報８０１の「Ｎｏ」「Ｐ２」の表現パターンになる。そうすると抽出した文字列「r.名前 = 検索画面.メーカ」を参照し、「Ｎｏ」「Ｐ２」の「表現パターン」に対応する「式パターン」の「{str1[0, min(d(str1), d(str2))]}」「{str2[0, min(d(str1), d(str2))]}」を選択することになる。
【００６６】
「str1」「str2」各々に対応する部分文字列（変数）は、それぞれ「str1」がメーカＤＢ４０２の有する部分文字列（変数）「メーカ.名前」となり、「str2」が商品検索画面３０１の有する部分文字列（変数）「検索画面.メーカ」となる。なお、抽出した文字列「r.名前 = 検索画面.メーカ」内の「r」はメーカＤＢ４０２を示す「メーカ」に変換されている。
【００６７】
次に、パターン「{str1[0, min(d(str1), d(str2))]}」「{str2[0, min(d(str1), d(str2))]}」」の「str1」「str2」各々に、「メーカ.名前」と「検索画面.メーカ」を代入する。その結果、代入した式を得る。
代入した式の例
{メーカ.名前[0, min(d(メーカ.名前), d(検索画面.メーカ))]}
{検索画面.メーカ[0, min(d(メーカ.名前), d(検索画面.メーカ))]}
【００６８】
ステップＳ２０８では、生成部２０１が項目定義情報２０９から関連するデータを取得し、ステップＳ２０７で生成した式に代入する。関連するデータは、例えば、桁などが考えられる。上記説明した生成した式の例の場合、「d(メーカ.名前)」と「d(検索画面.メーカ)」は、「メーカ.名前」と「検索画面.メーカ」各々の文字列の桁を代入する。「検索画面.メーカ」に対応する関連するデータとして図５の項目定義情報５０１の「桁」に記憶されている「１０」を取得する。また、「メーカ.名前」に対応する関連するデータとして図５の項目定義情報５０２の「桁」に記憶されている「１０」を取得する。その後、生成した式の例に示した対応箇所に、取得した関連データである桁を代入する。
生成した式にデータを代入した例
{メーカ.名前[0, min(10, 10)]}      →  {メーカ.名前[0, 10]}
{検索画面.メーカ[0, min(10, 10)]}  →  {検索画面.メーカ[0, 10]}
【００６９】
ステップＳ２０９では、生成部２０１が部分文字列関連情報２１１の「必須部分文字列」にステップＳ２０８で代入した式を記憶する。例えば、図１０に示す部分文字列関連情報１０１に示すように記憶する。
【００７０】
図１０は、部分文字列関連情報のデータ構造の一実施例を示す図である。図１０の部分文字列関連情報１０１は、「Ｎｏ」「関連」「文字列項目」「必須部分文字列」に記憶する情報を有する。「Ｎｏ」には、部分文字列関連情報１０１の行ごとに割り振られる情報で、本例では、「Ｒ１」「Ｒ２」「Ｒ３」・・・「Ｒ１０」が記憶されている。「関連」は、必須部分文字列が関係していることを示している。例えば、関連パターン情報８０１に必須部分文字列が関係していることを示す情報が記憶されている。本例では、「{メーカ.名前 <-> 検索画面.メーカ}」「{カテコ゛リ.名前 <-> 検索画面.カテコ゛リ}」「{メーカ.名前 <-> 検索画面.メーカ}」・・・「{在庫状況.商品コート゛<-> 商品.商品コート゛}」が記憶されている。例えば、関連パターン情報８０１の「関連」に「{str1 <->  str2}」が記憶されていて、str1が「メーカ.名前」でstr2が「検索画面.メーカ」である場合は、「{メーカ.名前 <-> 検索画面.メーカ}」が記憶される。
【００７１】
「文字列項目」には項目を示す情報が記憶される。本例では、「Ｎｏ」各々に関連付けられて文字列項目「メーカ.名前」「検索画面.メーカ」「カテコ゛リ.名前」「検索画面.カテコ゛リ」「メーカ.名前」「検索画面.メーカ」・・・「在庫状況.商品コート゛」「商品.商品コート゛」が記憶されている。例えば、「Ｒ１」には文字列項目「メーカ.名前」「検索画面.メーカ」が記憶されている。
【００７２】
「必須部分文字列」には、必須部分文字列を示す情報が記憶される。本例では、「文字列項目」各々に関連付けられて必須部分文字列「str[0, 10］」「str[0, 10］」「str[0, 10］」・・・「str[0, 13］」が記憶されている。なお、本例では必須部分文字列の文字列項目は「str」で表しているが、文字列項目を用いて表してもよい。
【００７３】
図７のステップＳ１０２の説明をする。
ステップＳ１０２では、分割部２０２が部分文字列関連情報２１１を用いて項目分割情報を抽出する。ステップＳ１０２の動作について図１１を用いて説明する。
【００７４】
図１１は、分割部の動作の一実施例を示すフロー図である。ステップＳ３０１では、分割部２０２が項目分割情報２１２を初期化する。
図１２は、項目分割情報のデータ構造の一実施例を示す図である。図１２の項目分割情報１２１は画面情報に関する項目分割情報で、図２の項目分割情報２１２は、例えば、図５に示す画面に関する項目定義情報５０１やＤＢに関する項目定義情報５０２などがある。
【００７５】
項目定義情報１２１は、「画面」「項目」「分割位置」などの情報を記憶する。「画面」には、画面を識別するための識別情報が記憶されている。本例では、商品検索画面３０１を示す「検索画面」・・・・が記憶されている。「項目」には、「画面」に記憶されている画面に設けられている項目などを識別する情報が記憶されている。例えば、プログラムで扱う変数に対応する名称などが記憶されている。本例では、商品検索画面３０１のテキスト入力部３０２、３０３を用いて入力されるデータが代入される変数に対応する情報「メーカ」「カテゴリ」・・・・が記憶されている。「分割位置」には、「項目」に対応する文字列（変数）などのデータを分割する位置が記憶されている。本例では、「項目」各々に対応する文字列（変数）の分割位置として「{0, 10}」「{0, 10}」・・・・が記憶されている。
【００７６】
項目定義情報１２２は、「ＤＢ」「項目」「分割位置」などの情報を記憶する。本例では、図４のＤＢ４０１に関する項目定義情報が示されている。「ＤＢ」には、ＤＢなどに含まれるデータベース情報（またはテーブル）を識別する情報が記憶される。本例では、データベース情報としてメーカＤＢを示す「メーカ」、カテゴリＤＢを示す「カテゴリ」、商品ＤＢを示す「商品」、在庫状況ＤＢを示す「在庫状況」が記憶されている。「項目」には、「ＤＢ」に記憶されているデータベース情報各々に対応するカラムが記憶されている。本例では、「メーカ」に関連する「項目」として「名前」「コード」と、「カテゴリ」に関連する「項目」として「名前」「コード」とが記憶されている。また、「商品」に関連する「項目」として「商品名」「商品コード」「単価」と、「在庫状況」に関連する「項目」として「商品コード」「在庫数」とが記憶されている。「分割位置」には、「項目」各々に対応する文字列（変数）などのデータを分割する位置が記憶されている。本例では、「項目」各々に対応する文字列（変数）の分割位置として「{0, 10}」「{0, 4}」「{0, 10}」・・・「{0, 4, 7, 13}」「{}」が記憶されている。
【００７７】
なお、ステップＳ３０１において、分割部２０２が項目分割情報１２１と１２２とを初期化するとは、「分割位置」の内容をすべて「{}」にすることである。
ステップＳ３０２では、分割部２０２が部分文字列関連情報２１１の未選択の行を選択する。ステップＳ３０３では、分割部２０２が部分文字列関連情報２１１の必須部分文字列を項目分割情報２１２の分割位置に反映させる。ステップＳ３０４では、分割部２０２が二項間の分割位置を反映させる。ステップＳ３０５では、部分文字列関連情報の全ての行を選択したか否かを判定し、全てを選択した場合にはステップＳ３０６（Ｙｅｓ）に移行し、未選択の行がある場合にはステップＳ３０２（Ｎｏ）に移行する。
【００７８】
ステップＳ３０２〜Ｓ３０５の動作について説明する。
例えば、図１０の部分文字列関連情報１０１の「Ｒ１」に対応する行から順番に選択する場合について説明する。
【００７９】
ステップＳ３０２でＲ１に対応する行が選択された場合、ステップＳ３０３では部分文字列関連情報１０１の文字列項目「メーカ.名前」「検索画面.メーカ」を参照して項目分割情報１２１、１２２の必須部分文字列を反映させる分割位置を特定する。Ｒ１の場合、文字列項目がメーカＤＢ４０２の名前を示しているので、項目分割情報１２２の１行目の分割位置が特定される。また、文字列項目が商品検索画面３０１の入力部３０２のメーカを示しているので、項目分割情報１２１の１行目の分割位置が特定される。その後、特定され項目分割情報１２２の１行目の分割位置に必須部分文字列の開始位置と終了位置示す情報（例えば、{0, 10}）などを記憶させる。また、特定され項目分割情報１２１の１行目の分割位置に必須部分文字列の開始位置と終了位置示す情報（例えば、{0, 10}）などを記憶させる。
【００８０】
次に、Ｒ１〜Ｒ３の処理が完了してステップＳ３０２でＲ４に対応する行が選択された場合について説明する。ステップＳ３０３では部分文字列関連情報１０１の文字列項目「商品.商品コート゛」「メーカ.コート゛」を参照して項目分割情報１２１、１２２の必須部分文字列を反映させる分割位置を特定する。Ｒ４の場合、文字列項目が商品ＤＢ４０４の商品コードを示しているので、項目分割情報１２２の６行目の分割位置が特定される。また、文字列項目がメーカＤＢ４０２のコードを示しているので、項目分割情報１２２の２行目の分割位置が特定される。その後、特定され項目分割情報１２２の６行目の分割位置に必須部分文字列の開始位置と終了位置示す情報（例えば、{0, 4}）などを記憶させる。また、特定された項目分割情報１２２の２行目の分割位置に必須部分文字列の開始位置と終了位置示す情報（例えば、{0, 4}）などを記憶させる。
【００８１】
次に、Ｒ１〜Ｒ８の処理が完了してステップＳ３０２でＲ９に対応する行が選択された場合について説明する。ステップＳ３０３では部分文字列関連情報１０１の文字列項目「商品.商品コート゛」「在庫状況.商品コート゛」を参照して項目分割情報１２１、１２２の必須部分文字列を反映させる分割位置を特定する。Ｒ９の場合、文字列項目が商品ＤＢ４０４の商品コードを示しているので、項目分割情報１２２の６行目の分割位置が特定される。また、文字列項目が在庫状況ＤＢ４０５のコードを示しているので、項目分割情報１２２の８行目の分割位置が特定される。その後、特定され項目分割情報１２２の６行目の分割位置に必須部分文字列の開始位置と終了位置示す情報（例えば、{0, 13}）などを反映させる。このとき、既に分割位置にデータがある場合は、今回取得した情報を追加する。本例であれば、既にある情報{0, 4}に今回取得した情報{0, 13}を追加して{0, 4, 13}を生成する。また、特定され項目分割情報１２２の８行目の分割位置に必須部分文字列の開始位置と終了位置示す情報（例えば、{0, 13}）などを反映させる。このとき、既に分割位置にデータがある場合は、今回取得した情報を追加する。本例であれば、Ｒ８の行さ選択されたときに既にある情報が{0, 4, 7}であるので、今回取得した情報{0, 13}を追加して{0, 4, 7, 13}を生成する。
【００８２】
ステップＳ３０４では、分割部２０２が二項間の分割位置を反映させる。例えば、部分文字列関連情報１０１のＲ１の場合は、部分文字列関連情報１０１の「関連」の「{メーカ.名前 <-> 検索画面.メーカ}」を参照して、メーカＤＢ４０２の名前と検索画面ＤＢ４０５のメーカの二項を選択する。しかし、選択した二項に対応する項目分割情報１２２の「分割位置」各々には同じ「{0, 10}」が記憶されているので、「分割位置」の情報はともに「{0, 10}」のまま変更されない。
【００８３】
部分文字列関連情報１０１のＲ４の場合は、部分文字列関連情報１０１の「関連」の「{商品.商品コート゛ <-> メーカ.コート゛}」を参照して、商品ＤＢ４０４のコードとメーカＤＢ４０２のコードの二項を選択する。しかし、選択した二項に対応する項目分割情報１２２の「分割位置」各々には同じ「{0, 4}」が記憶されているので、「分割位置」の情報はともに「{0, 4}」のまま変更されない。
【００８４】
部分文字列関連情報１０１のＲ９の場合であれば、部分文字列関連情報１０１の「関連」の「{商品.商品コート゛ <-> 在庫状況.商品コート゛}」を参照して、商品ＤＢ４０４の商品コードと在庫状況ＤＢ４０５の商品コードの二項を選択する。選択した二項に対応する項目分割情報１２２の「分割位置」の商品ＤＢ４０４の商品コードには「{0, 4, 7, 13}」が記憶されている。また、選択した二項の項目分割情報１２２の「分割位置」の在庫状況ＤＢ４０５の商品コードには「{0, 13}」が記憶されている。そこで、選択した二項に対応する項目分割情報１２２の「分割位置」各々の情報を同じにするため、在庫状況ＤＢ４０５の商品コードの「{0, 13}」に商品ＤＢ４０４の商品コードの「{0, 4, 7, 13}」を反映させる。
【００８５】
ステップＳ３０５では、分割部２０２が部分文字列関連情報２１１のすべての行を選択したか否かを判定し、すべての行を選択した場合にはステップＳ３０６（Ｙｅｓ）に移行し、未選択の行がある場合にはステップＳ３０２（Ｎｏ）に移行する。部分文字列関連情報１０１の例であれば、Ｒ１〜Ｒ１０に対応する行をすべて選択されていれば、ステップＳ３０６（Ｙｅｓ）に移行する。
【００８６】
ステップＳ３０６では、分割部２０２が反映（ステップＳ３０２〜Ｓ３０５の処理）の前（初期化または前回のステップＳ３０２〜Ｓ３０５の処理）と後（今回のステップＳ３０２〜Ｓ３０５の処理）で、部分文字列関連情報２１１のすべての分割位置を比較する。そして、反映の前後で部分文字列関連情報２１１のすべての分割位置が変化していればステップＳ３０７（Ｙｅｓ）に移行し、変化していない場合にはこの処理を終了する。
【００８７】
ステップＳ３０１で分割部２０２が初期化または前回の項目分割情報２１２と、ステップＳ３０５までの処理により生成された項目分割情報２１２とを比較する。例えば、初期化した直後は項目分割情報１２１、１２２の「分割位置」の情報はすべて「｛｝」で、その後のステップＳ３０２〜Ｓ３０５により生成される項目分割情報１２１、１２２の「分割位置」の情報は図１２に示した状態になる。その結果、項目分割情報１２１、１２２は反映の前後で変化しているので、ステップＳ３０７（Ｙｅｓ）に移行する。
【００８８】
また、初期化後の１回目のステップＳ３０２〜Ｓ３０５の処理である図１２に示した状態の項目分割情報１２１、１２２の「分割位置」のすべての情報と、次のステップＳ３０２〜Ｓ３０５の処理の結果が図１２に示した項目分割情報１２１、１２２の「分割位置」のすべての情報と、が同じであるならこの処理を終了する。
【００８９】
ステップＳ３０６の処理は、項目分割情報２１２を生成する際に、部分文字列関連情報２１１の行の選択する順番により、ステップＳ３０４の二項間の分割位置が反映されないことを避けるための処理である。この処理を実行することにより、項目分割情報２１２に二項間の分割位置の反映がされる。
【００９０】
図７のステップＳ１０３の説明をする。
ステップＳ１０３では、定義部２０３が項目分割情報２１２と項目定義情報２０９とを用いてデータ表現情報を抽出する。ステップＳ１０３の動作について図１３を用いて説明する。
【００９１】
図１３は、定義部の動作の一実施例を示すフロー図である。ステップＳ４０１では、定義部２０３が項目分割情報２１２の未選択の行を選択する。例えば、図１２に示した項目分割情報１２１、１２２を選択し、項目分割情報１２１の最初の行から順番に選択をし、項目分割情報１２１の行をすべて選択し終えたら、項目分割情報１２２の最初の行を選択し、順番に行を選択することが考えられる。
【００９２】
ステップＳ４０２では、定義部２０３がステップＳ４０１で選択した行に対応する項目定義情報２０９を取得する。例えば、図１２の項目分割情報１２２の６行目が選択された場合、商品ＤＢ４０４の商品コードに対応する図５の項目定義情報５０２の６行目が選択され、「商品」「商品コード」「文字列」「１３」を取得する。
【００９３】
ステップＳ４０３では、定義部２０３が選択した項目分割情報２１２の「分割位置」が空「｛｝」であるか否かを判定し、空「｛｝」である場合にはステップＳ４０４（Ｙｅｓ）に移行し、空「｛｝」でない場合にはステップＳ４０５（Ｎｏ）に移行する。
【００９４】
ステップＳ４０４では、定義部２０３が項目分割情報２１２の「分割位置」の空「｛｝」に関連付けられている「項目」と一致する、項目定義情報２０９の「項目」に関連付けられている「桁」各々を取得する。次に、データ表現情報２１３の上記項目定義情報２０９の「項目」と一致する「項目」に対応する「桁範囲」に、「０」から「桁−１」を入力する。
【００９５】
データ表現情報２１３は、例えば、図１４に示すデータ表現情報１４１、１４２などが考えられる。図１４は、データ表現情報のデータ構造の一実施例を示す図である。
データ表現情報１４１は、例えば、「画面」「項目」「データ表現」などの情報を記憶する。「画面」には、画面を識別するための識別情報が記憶されている。本例では、図３に商品検索画面３０１に関連することを示す「検索画面」が記憶されている。「項目」には、「画面」に記憶されている検索画面に設けられている項目などを識別する情報が記憶されている。例えば、プログラムで扱う変数に対応する名称などが記憶されている。本例では、商品検索画面３０１のテキスト入力部３０２、３０３を用いて入力されるデータが代入される変数に対応する情報「メーカ」「カテゴリ」が記憶されている。「データ表現」は、「桁範囲」「対応データ項目」を有している。「桁範囲」には、「項目」各々に対応する桁数から１を引いた値が記憶される。本例では、「桁範囲」に「０−９」「０−９」が記憶されている。「対応データ項目」には、「項目」各々に対応する項目名が記憶される。本例では、「項目」に「メーカ」「カテゴリ」が記憶されている。
【００９６】
データ表現情報１４２は、「ＤＢ」「項目」「データ表現」などの情報を記憶する。本例では、図４のＤＢ４０１に関するデータ表現情報が示されている。「ＤＢ」には、ＤＢなどに含まれるデータベース情報（またはテーブル）を識別する情報が記憶される。本例では、データベース情報としてメーカＤＢを示す「メーカ」、カテゴリＤＢを示す「カテゴリ」、商品ＤＢを示す「商品」、在庫状況ＤＢを示す「在庫状況」が記憶されている。「項目」には、「ＤＢ」にあるデータベース情報各々に対応するカラムが記憶されている。本例では、「メーカ」に関連する「項目」として「名前」「コード」と、「カテゴリ」に関連する「項目」として「名前」「コード」とが記憶されている。また、「商品」に関連する「項目」として「商品名」「商品コード」「単価」と、「在庫状況」に関連する「項目」として「商品コード」「在庫数」とが記憶されている。
【００９７】
「データ表現」は、「桁範囲」「対応データ項目」を有している。「桁範囲」には、「項目」各々に対応する桁数から１を引いた値が記憶される。本例では、「桁範囲」に「０−９」「０−４」「０−９」・・・「０−９」が記憶されている。「対応データ項目」には、「項目」各々に対応する項目名が記憶される。本例では、「項目」に「名前」「コード」「名前」・・・「在庫数」が記憶されている。
【００９８】
ステップＳ４０４で定義部２０３は、例えば、項目分割情報１２２の「分割位置」の５、７、９行目の空「｛｝」に関連付けられている「項目」と一致する、項目定義情報５０２の「項目」に関連付けられている「桁」各々を取得する。本例では、項目定義情報５０２の「桁」からそれぞれ「１０」「１０」「１０」を取得する。次に、データ表現情報１４１の上記項目定義情報５０２の「項目」と一致する「項目」に対応する「桁範囲」に、０−９を入力する。本例では、データ表現情報１４１の「桁範囲」の５、９、１３に「０−９」が記憶される。「９」は、桁「１０」から１を引いて数値であり、「−」は、例えば範囲を示す記号で、０−９であれば０から９範囲を示す。
【００９９】
ステップＳ４０５では、定義部２０３が項目分割情報２１２の「分割位置」の先頭の分割位置を示す数値を選択する。例えば、項目分割情報１２２の「分割位置」の６行目の「{0, 4, 7, 13}」が選択されているとすると、「０」が選択される。
【０１００】
ステップＳ４０６では、定義部２０３が現在選択されている「分割位置」の数値の次に、分割位置を示す数値が存在するか否かを判定し、存在する場合にはステップＳ４０７（Ｙｅｓ）に移行し、存在しない場合にはステップＳ４１０（Ｎｏ）に移行する。例えば、項目分割情報１２２の「分割位置」の６行目の「{0, 4, 7, 13}」が選択されているとすると、「０」の次に「４」が存在するのでステップＳ４０７（Ｙｅｓ）に移行する。
【０１０１】
ステップＳ４０７では、定義部２０３が現在選択されている「項目」に対応する「分割位置」の数値の次の数値と、現在選択されている「項目」に一致する項目定義情報２０９に対応する「桁」とを比較する。次の数値＜桁であるときステップＳ４０８（Ｙｅｓ）に移行し、次の数値＜桁でない場合ステップＳ４１０（Ｎｏ）に移行する。例えば、項目分割情報１２２の「分割位置」の６行目の「{0, 4, 7, 13}」が選択されているとすると、「０」の次に「４」が存在し、現在選択されている「項目」に一致する項目定義情報５０２の６行目に対応する「桁」が「１３」である。よって、次の数値「４」＜桁「１３」なのでステップＳ４０８（Ｙｅｓ）に移行する。
【０１０２】
ステップＳ４０８で定義部２０３は、現在選択されている「桁範囲」に「選択している分割位置の数値」から「次の分割位置の数値−１」を生成するとともに、対応する行を生成してデータ表現情報２１３に追加する。例えば、項目分割情報１２２の「分割位置」の６行目の「{0, 4, 7, 13}」のうち、現在選択されている「分割位置」の数値が「０」で、次の分割位置を示す数値が「４」である場合、図１４のデータ表現情報１４２の「桁範囲」の６行目に対応する行が生成される。すなわち、「商品」「商品コード」「０−３」「商品コード１」が生成され、データ表現情報１４２に追加される。データ表現情報１４２の「商品」「商品コード」は、データ表現情報１４２の「項目」と一致する項目分割情報１２２の「商品」「商品コード」を記憶する。「０−３」は、選択している分割位置の数値「０」から次の分割位置の数値−１「４−１」を求めて記憶する。「商品コード１」は、生成した新しい項目名である。本例では、「項目」の「商品コード」に連番「１」を付している。
【０１０３】
また、項目分割情報１２２の「分割位置」の６行目の「{0, 4, 7, 13}」のうち、現在選択されている「分割位置」の数値が「４」で、次の分割位置を示す数値が「７」である場合、図１４のデータ表現情報１４２の「桁範囲」の７行目に対応する行が生成される。すなわち、「商品」「商品コード」「４−６」「商品コード２」が生成され、データ表現情報１４２に追加される。データ表現情報１４２の「商品」「商品コード」は、データ表現情報１４２の「項目」と一致する項目分割情報１２２の「商品」「商品コード」を記憶する。「４−６」は、選択している分割位置の数値「４」から次の分割位置の数値−１「７−１」を求めて記憶する。「商品コード２」は、生成した新しい項目名である。本例では、「項目」の「商品コード」に連番「２」を付している。
【０１０４】
ステップＳ４０９では、定義部２０３が次の分割位置の数値を選択し、ステップＳ４０６に移行する。例えば、項目分割情報１２２の「分割位置」の６行目の「{0, 4, 7, 13}」のうち、現在選択されている「分割位置」の数値が「０」で、次の分割位置を示す数値が「４」である場合には、「４」が選択される。
【０１０５】
ステップＳ４１０では、定義部２０３が現在選択されている「桁範囲」に現在選択されている「分割位置」の数値と、項目定義情報２０９の対応する「桁」から１を引いた値とを用いて桁範囲を生成し、桁範囲に対応する行をデータ表現情報２１３に追加する。例えば、項目分割情報１２２の「分割位置」の６行目の「{0, 4, 7, 13}」のうち、現在選択されている「分割位置」の数値が「７」で、次の分割位置を示す数値が「１３」である場合、ステップＳ４０７からステップＳ４１０に移行する。そして、図１４のデータ表現情報１４２の「桁範囲」の８行目に対応する行が生成される。すなわち、「商品」「商品コード」「４−６」「商品コード３」が生成され、データ表現情報１４２に追加される。データ表現情報１４２の「商品」「商品コード」は、データ表現情報１４２の「項目」と一致する項目分割情報１２２の「商品」「商品コード」を記憶する。「７−１２」は、選択している分割位置の数値「７」から次の分割位置の数値−１「１３−１」を求めて記憶する。「商品コード３」は、生成した新しい項目名である。本例では、「項目」の「商品コード」に連番「３」を付している。
【０１０６】
ステップＳ４１１では、定義部２０３が項目分割情報２１２に未選択の「項目」が存在するか否かを判定し、存在する場合にはステップＳ４０１（Ｙｅｓ）に移行し、存在しない場合にはこの処理を終了（Ｎｏ）する。
【０１０７】
図７のステップＳ１０４の説明をする。
ステップＳ１０４では、制約変換部２０４が元制約情報２０８とデータ表現情報２１３とを用いて変換後制約情報２１４を抽出する。ステップＳ１０４の動作について図１５を用いて説明する。
【０１０８】
図１５は、制約変換部の動作の一実施例を示すフロー図である。
図１５のステップＳ２０１〜Ｓ２０８では、制約変換部２０４が図９に示したステップＳ２０１〜Ｓ２０８と同じ処理を行う。例えば、図６の元制約情報６０３の（３）の「(subString(r1.商品コート゛, 0, 4) = r2.コート゛)」が選択されたとすれば、「文字列項目」として「商品.商品コート゛」「カテコ゛リ.コート゛」が生成される。そして、「必須部分文字列」として「商品.商品コート゛」に対応する「{str[4, 7]}」と「カテコ゛リ.コート゛」に対応する「{str[0, 3]}」が生成される。
【０１０９】
ステップＳ５０１では、制約変換部２０４が生成した必須部分文字列の範囲に対応するデータ表現情報２１３の対応データ項目名を特定する。例えば、図６の元制約情報６０３の（３）の「(subString(r1.商品コート゛, 0, 4) = r2.コート゛)」が選択され、「必須部分文字列」として「商品.商品コート゛」に対応する「{str[4, 7]}」と「カテコ゛リ.コート゛」に対応する「{str[0, 3]}」が生成されている場合を考える。その場合、制約変換部２０４はデータ表現情報１４１、１４２から、「商品」「商品コード」「４−６」「商品コード２」を有する行が選択される。すなわち、対応データ項目名として「商品コード２」が特定される。
【０１１０】
ステップＳ５０２では、制約変換部２０４がステップＳ５０１で特定した対応データ項目名を用いて、元制約情報２０８の対応する箇所を変換する。例えば、図６の元制約情報６０３の（３）において、「商品コード２」が特定された場合、上記「(subString(r1.商品コート゛, 0, 4) = r2.コート゛)」は、「r1.商品コード２ = r2.コード」のように表現される。
【０１１１】
図１６に、図６の元制約情報６０３を、対応データ項目名を用いて変換した例を示す。図１６は、変換後元制約情報の一実施例を示す図である。図１６の下線部が変換された箇所を示している。
【０１１２】
図７のステップＳ１０５では、充足値生成部２０５が変換後制約情報２１４を入力として、Satisfiability Modulo Theories(ＳＭＴソルバ)を用いて変換後制約情報２１４を充足する解（充足値）を求め、変換後制約充足値情報２１５に記憶する。
【０１１３】
ＳＭＴソルバに関しては、例えば、次の非特許文献を参照されたい。
・足立正和，他、「充足可能性判定に基づくリアルタイムシステムのスケジューリング解析」、組込みシステムシンポジウム２００８、平成２０年１０月
・Armin Biere, Marijn Heule, Hans Van Maaren, Toby Walsh, "Handbook of Satisfiability(Frontiers in Artificial Intelligence and Applications)",IOS Press, ２００９年２月
・R.E. Bryant, Daniel Kroening, Ofer Strichman, "Decision Procedures: An Algorithmic Point of View (Texts in Theoretical Computer Science. An EATCS Series)", Springer, ２００８年７月７日
【０１１４】
図１７は、ＳＭＴソルバにより求められた充足値の一実施例を示す図である。変換後制約情報１６１の充足値は変換後制約充足値情報２１５に記憶される。
検索画面１７１の場合、商品検索画面３０１のテキスト入力部３０２、３０３に入力される「メーカ」に対応する「１０１」、「カテゴリ」に対応する「２０２」となる。
【０１１５】
また、メーカ１７２の場合、メーカＤＢ４０２に記憶される「名前」「１０１」に対応付けられるコード「１０００１」と、「名前」「２０２」に対応付けられるコード「１０００２」が充足値となる。
【０１１６】
カテゴリ１７３の場合、カテゴリＤＢ４０３に記憶される「名前」「２０１」に対応付けられるコード「２０００１」と、「名前」「２０２」に対応付けられるコード「２０００２」が充足値となる。
【０１１７】
商品１７４の場合、商品ＤＢ４０４に記憶される「商品名」「商品コード１」「商品コード２」「商品コード３」「単価」各々に対応付けられるデータが充足値となる。「商品名」の充足値は「３０１」「３０２」「３０３」である。「商品コード１」の充足値は商品名「３０１」「３０２」「３０３」各々に関連付けられる「１０００１」「１０００１」「１０００２」である。「商品コード２」の充足値は商品名「３０１」「３０２」「３０３」各々に関連付けられる「２０００１」「２０００１」「２０００２」である。「商品コード３」の充足値は商品名「３０１」「３０２」「３０３」各々に関連付けられる「３０００１」「３０００２」「３０００１」である。「単価」の充足値は商品名「３０１」「３０２」「３０３」各々に関連付けられる「１０００」「２０００」「３０００」である。
【０１１８】
在庫状況１７５の場合、在庫状況ＤＢ４０５に記憶される「商品コード１」「商品コード２」「商品コード３」「在庫数」各々に対応付けられるデータが充足値となる。「商品コード１」の充足値は「１０００１」「１０００２」である。「商品コード２」の充足値は「２０００１」「２０００２」である。「商品コード３」の充足値は「３０００１」「３０００１」である。「在庫数」の充足値は「商品コード１」「商品コード２」「商品コード３」各々に関連付けられる「１０００」「２０００」「３０００」である。
【０１１９】
ステップＳ１０６では、充足値生成部２０５が変換後制約情報を充足する解があるか否かを判定し、解がある場合にはステップＳ１０７（Ｙｅｓ）に移行し、解がない場合にはステップＳ１０８（Ｎｏ）に移行する。
ステップＳ１０７では、充足値変換部２０６が元制約充足データを生成する。
【０１２０】
図７のステップＳ１０７の説明をする。
ステップＳ１０７の動作について図１８を用いて説明する。図１８は、制約変換部の動作の一実施例を示すフロー図である。
【０１２１】
ステップＳ６０１では、充足値変換部２０６が変換後制約情報の充足値（変換後制約充足値情報２１５）を文字列に変換する。ステップＳ６０２では、充足値変換部２０６が文字列に変換した各データをデータ表現情報２１３に従って結合し、元制約充足情報２１０を生成する。
【０１２２】
例えば、「商品コード１」「商品コード２」「商品コード３」に「１０００１」「２００１」「３０００１」が記憶されている場合、まず、ステップＳ６０１で文字列「Ａ００１」「Ｃ０１」「００００１」に変換される。次に、ステップＳ６０２で、データ表現情報１４２の６〜８行目を参照して「Ａ００１」「Ｃ０１」「００００１」を結合して、「Ａ００１Ｃ０１００００１」とする。
【０１２３】
図１９は、元制約充足情報のデータ構造の一実施例を示す図である。
検索画面１９１の場合、商品検索画面３０１のテキスト入力部３０２、３０３に入力される「メーカ」に対応する「１０１」、「カテゴリ」に対応する「２０２」を、ステップＳ６０１では、「Ｍａｋｅｒ０」「Ｃａｔｅｇｏｒｙ１」に変換する。
【０１２４】
また、メーカ１９２の場合、メーカＤＢ４０２に記憶される「名前」の「１０１」を、ステップＳ６０１で「Ｍａｋｅｒ０」にし、対応付けられるコード「１０００１」を「Ａ００１」に変換する。また、「名前」の「２０２」を、ステップＳ６０１で「Ｍａｋｅｒ１」にし、対応付けられるコード「１０００２」を「Ａ００２」に変換する。
【０１２５】
また、カテゴリ１９３の場合、カテゴリＤＢ４０３に記憶される「名前」の「２０１」を、ステップＳ６０１で「Ｃａｔｅｇｏｒｙ０」にし、対応付けられるコード「２０００１」を「Ｃ００１」に変換する。また、「名前」の「２０２」を、ステップＳ６０１で「Ｃａｔｅｇｏｒｙ１」にし、対応付けられるコード「２０００２」を「Ｃ００２」に変換する。
【０１２６】
また、商品１９４の場合、商品ＤＢ４０４に記憶される「商品」の「３０１」「３０２」「３０３」は、ステップＳ６０１で「Pｒｏｄｕｃｔ０」「Pｒｏｄｕｃｔ１」「Pｒｏｄｕｃｔ２」に変換される。「商品コード」には、「Pｒｏｄｕｃｔ０」「Pｒｏｄｕｃｔ１」「Pｒｏｄｕｃｔ２」各々に関連付けられている。ステップＳ６０１、Ｓ６０２により変換された「Ａ００１Ｃ０１００００１」「Ａ００１Ｃ０１００００２」「Ａ００２Ｃ０２００００１」が記憶されている。「単価」には「Pｒｏｄｕｃｔ０」「Pｒｏｄｕｃｔ１」「Pｒｏｄｕｃｔ２」各々に関連付けられ、「１０００」「２０００」「３０００」が記憶されている。
【０１２７】
また、在庫状況１９５の場合、在庫状況ＤＢ４０４に記憶される「商品コード」は、ステップＳ６０１、Ｓ６０２により変換された「Ａ００１Ｃ０１００００１」「Ａ００１Ｃ０１００００２」「Ａ００２Ｃ０２００００１」が記憶されている。「在庫数」には「Ａ００１Ｃ０１００００１」「Ａ００２Ｃ０２００００１」各々に関連付けられ、「１００」「２００」が記憶されている。
【０１２８】
効果について説明する。
本実施の態様では、制約に含まれる文字列ごとに、複数の文字列間の関連を記憶した情報を参照して他文字列と一致する部分文字列を求め、該部分文字列を１つの要素とする配列に変換し、制約を変換する。その後、変換した制約をＳＭＴソルバの入力として充足値求め、求めた充足値を用いてテストデータを生成する。その結果、ＳＭＴソルバの時間計算量を削減することができるという効果を奏する。すなわち、項目分割情報に従って変換後制約情報を生成することで、文字配列に対する制約として表現していた文字列の制約は、部分文字列に対応する単独の値（数値等）に対する制約として表現され、変換後制約の複雑さが抑えられる。そのため、充足可能性判定がより効率化し、多くの文字列制約を含むデータをより高速に生成することが可能になる
例えば、「商品.商品コード」によって表現される文字列が１３文字からなる場合、文字列に関する制約を３つの部分文字列に対する制約として表現できる場合、従来と比べて制約の複雑さ（変数の数）は３／１３となり、制約に対する充足可能性判定もより効率化される。
【０１２９】
また、文字列の制約のうち、「０文字目から３文字目」といった、部分文字列の切り出し位置が一通りに定まっているものに対し効果的に作用する。こういった性質は業務アプリケーションの仕様に頻出するので、業務システムのテストデータ生成に寄与するところ大である
【０１３０】
また、本発明は、上記実施の形態に限定されるものでなく、本発明の要旨を逸脱しない範囲内で種々の改良、変更が可能である。
【０１３１】
実施形態に関し、更に以下の付記を開示する。
（付記１）
変数を表す部分文字列各々を用いて表現される文字列の表現パターンと、該文字列の表現において必須となる前記部分文字列各々の必須部分文字列の桁数を求める式パターンと、前記部分文字列各々が関連していることを示す関連パターンと、が関連付けて記憶された関連パターン情報テーブルを参照し、テスト対象のプログラムの入力データの制約条件を示す元制約情報から、前記文字列の表現パターンと一致する文字列を抽出し、
前記関連パターン情報テーブルを参照して、抽出した前記文字列の前記表現パターンに対応する前記式パターン及び関連パターンを取得し、
取得した前記式パターン及び前記関連パターンに、抽出した前記文字列に含まれる部分文字列を代入して、必須部分文字列と部分文字列各々が関連していることを示す関連情報を求め、
前記元制約情報に含まれる変数を表す前記部分文字列と、該部分文字列の桁数と、が関連付けられている項目定義情報を参照して、前記部分文字列に対応する前記必須部分文字列の桁数を取得し、
前記必須部分文字列に取得した前記桁数を代入し、
前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々の前記桁数を取得し、取得した前記桁数各々を前記必須部分文字列各々に対応する前記部分文字列の分割位置を求め、
前記分割位置に従い、抽出した前記文字列に含まれる前記部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振り、
前記元制約情報の抽出した前記文字列に含まれる前記部分文字列のうち分割された前記部分文字列を、分割した前記部分文字列の名称を用いた表現に変換して変換後制約情報を生成する、
処理をコンピュータに実行させるテストデータ生成プログラム。
（付記２）
前記変換後制約情報を入力として、ＳＭＴソルバを用いて前記変換後制約情報が有する条件各々の充足値を求め、
前記充足値各々を用いて変換後制約の充足値から元制約情報の有する条件を充足するテストデータを生成する、
処理を前記コンピュータに実行させること特徴とする付記１に記載のテストデータ生成プログラム。
（付記３）
前記桁数を代入したすべての前記必須部分文字列に対して、複数回、前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々に前記桁数各々を、反映させて分割位置を求め、
前記桁数を代入したすべての前記必須部分文字列に対応する前回の分割位置と今回の分割位置を同じにする、
処理を前記コンピュータに実行させること特徴とする付記１または２に記載のテストデータ生成プログラム。
（付記４）
変数を表す部分文字列各々を用いて表現される文字列の表現パターンと、該文字列の表現において必須となる前記部分文字列各々の必須部分文字列の桁数を求める式パターンと、前記部分文字列各々が関連していることを示す関連パターンと、が関連付けて記憶された関連パターン情報テーブルを参照し、テスト対象のプログラムの入力データの制約条件を示す元制約情報から、前記文字列の表現パターンと一致する文字列を抽出し、
前記関連パターン情報テーブルを参照して、抽出した前記文字列の前記表現パターンに対応する前記式パターン及び関連パターンを取得し、
取得した前記式パターン及び前記関連パターンに、抽出した前記文字列に含まれる部分文字列を代入して、必須部分文字列と部分文字列各々が関連していることを示す関連情報を求め、
前記元制約情報に含まれる変数を表す前記部分文字列と、該部分文字列の桁数と、が関連付けられている項目定義情報を参照して、前記部分文字列に対応する前記必須部分文字列の桁数を取得し、
前記必須部分文字列に取得した前記桁数を代入し、
前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々の前記桁数を取得し、取得した前記桁数各々を前記必須部分文字列各々に対応する前記部分文字列の分割位置を求め、
前記分割位置に従い、抽出した前記文字列に含まれる前記部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振り、
前記元制約情報の抽出した前記文字列に含まれる前記部分文字列のうち分割された前記部分文字列を、分割した前記部分文字列の名称を用いた表現に変換して変換後制約情報を生成する、
こと特徴とするテストデータ生成方法。
（付記５）
前記コンピュータは、
前記変換後制約情報を入力として、ＳＭＴソルバを用いて前記変換後制約情報が有する条件各々の充足値を求め、
前記充足値各々を用いて変換後制約の充足値から元制約情報の有する条件を充足するテストデータを生成する、
こと特徴とする付記４に記載のテストデータ生成方法。
（付記６）
前記コンピュータは、
前記桁数を代入したすべての前記必須部分文字列に対して、複数回、前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々に前記桁数各々を、反映させて分割位置を求め、
前記桁数を代入したすべての前記必須部分文字列に対応する前回の分割位置と今回の分割位置を同じにする、
こと特徴とする付記４または５に記載のテストデータ生成方法。
（付記７）
変数を表す部分文字列各々を用いて表現される文字列の表現パターンと、該文字列の表現において必須となる前記部分文字列各々の必須部分文字列の桁数を求める式パターンと、前記部分文字列各々が関連していることを示す関連パターンと、が関連付けて記憶された関連パターン情報テーブルを参照し、テスト対象のプログラムの入力データの制約条件を示す元制約情報から、前記文字列の表現パターンと一致する文字列を抽出し、
前記関連パターン情報テーブルを参照して、抽出した前記文字列の前記表現パターンに対応する前記式パターン及び関連パターンを取得し、
取得した前記式パターン及び前記関連パターンに、抽出した前記文字列に含まれる部分文字列を代入して、必須部分文字列と部分文字列各々が関連していることを示す関連情報を求め、
前記元制約情報に含まれる変数を表す前記部分文字列と、該部分文字列の桁数と、が関連付けられている項目定義情報を参照して、前記部分文字列に対応する前記必須部分文字列の桁数を取得し、
前記必須部分文字列に取得した前記桁数を代入する、生成部と、
前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々の前記桁数を取得し、取得した前記桁数各々を前記必須部分文字列各々に対応する前記部分文字列の分割位置を求め、分割部と、
前記分割位置に従い、抽出した前記文字列に含まれる前記部分文字列を分割し、分割した部分文字列各々の桁範囲と、該分割した部分文字列各々に名称を割り振る、定義部と、
前記元制約情報の抽出した前記文字列に含まれる前記部分文字列のうち分割された前記部分文字列を、分割した前記部分文字列の名称を用いた表現に変換して変換後制約情報を生成する、制約変換部と、
を備えること特徴とするテストデータ生成装置。
（付記８）
前記変換後制約情報を入力として、ＳＭＴソルバを用いて前記変換後制約情報が有する条件各々の充足値を求める充足値生成部と、
前記充足値各々を用いて変換後制約の充足値から元制約情報の有する条件を充足するテストデータを生成する充足値変換部と、
を備えること特徴とする付記７に記載のテストデータ生成装置。
（付記９）
前記分割部は、
前記桁数を代入したすべての前記必須部分文字列に対して、複数回、前記桁数を代入した前記必須部分文字列と前記関連情報とを用いて、関連する該必須部分文字列各々に前記桁数各々を、反映させて分割位置を求め、
前記桁数を代入したすべての前記必須部分文字列に対応する前回の分割位置と今回の分割位置を同じにする、
を備えること特徴とする付記７または８に記載のテストデータ生成装置。
【符号の説明】
【０１３２】
１  テストデータ生成装置
２  制御部
３  記憶部
４  記録媒体読取装置
５  入出力インタフェース
６  通信インタフェース
７  バス
８  記録媒体
９  入出力部
２０１  生成部
２０２  分割部
２０３  定義部
２０４  制約変換部
２０５  充足値生成部
２０６  充足値変換部
２０７  関連パターン情報
２０８  元制約情報
２０９  項目定義情報
２１０  元制約充足情報
２１１  部分文字列関連情報
２１２  項目分割情報
２１３  データ表現情報
２１４  変換後制約情報
２１５  変換後制約充足値情報
【図１】
0005673395.tif 000002
【図２】
0005673395.tif 000003
【図３】
0005673395.tif 000004
【図４】
0005673395.tif 000005
【図５】
0005673395.tif 000006
【図６】
0005673395.tif 000007
【図７】
0005673395.tif 000008
【図８】
0005673395.tif 000009
【図９】
0005673395.tif 000010
【図１０】
0005673395.tif 000011
【図１１】
0005673395.tif 000012
【図１２】
0005673395.tif 000013
【図１３】
0005673395.tif 000014
【図１４】
0005673395.tif 000015
【図１５】
0005673395.tif 000016
【図１６】
0005673395.tif 000017
【図１７】
0005673395.tif 000018
【図１８】
0005673395.tif 000019
【図１９】
0005673395.tif 000020