(57)【要約】【課題】大規模データベースを、低コストで使用環境の制約なく管理し、使い勝手のよい環境を提供する技術を提供する。【解決手段】それぞれ一意のレコード番号を有する複数のレコードが格納されるデータベースから所望のレコードの位置情報を特定するためのインデックスであって、指定された値のレコード番号を返すとともに、所定の項目でソート後の順位に応じたレコード番号を返すインデックスを用いたレコードの位置情報を特定する位置情報特定部を備える情報処理装置を提供する。また、このインデックスのサイズは、元のデータベースサイズに比例的とする。【選択図】図７
2015207026.tif 000002
【特許請求の範囲】
【請求項１】
予め定めたデータ項目毎の項目値を格納するレコードからなるデータベースを管理する情報処理装置であって、
検索対象となり得る前記データ項目毎のインデックスファイルと、
前記インデックスファイルを用いて、所望の前記レコードの位置情報を特定する位置情報特定部と、を備え、
前記各レコードには、予め一意にレコード番号が付与され、
前記位置情報特定部は、前記位置情報として前記レコード番号を特定し、
前記データ項目毎のインデックスファイルは、当該データ項目の前記項目値から前記レコード番号を取得でき、かつ、当該データ項目をキー項目として前記データベースをソートしたソートデータベースの順位から前記レコード番号を取得できるものであること
を特徴とする情報処理装置。
【請求項２】
請求項１記載の情報処理装置であって、
管理対象の前記データベースは複数であり、
前記各データベースには、予め一意にデータベースＩＤが付与され、
前記インデックスファイルは、前記データベース毎に生成され、
前記ソートデータベースは、前記複数のデータベースを仮想的に統合した仮想統合データベースを、当該データ項目をキー項目としてソートしたものであり、
前記位置情報特定部は、前記位置情報として、所望の前記レコードが属する前記データベースの前記データベースＩＤをさらに特定すること、
を特徴とする情報処理装置。
【請求項３】
請求項１または２記載の情報処理装置であって、
前記データ項目毎のインデックスファイルは、
当該データ項目に属する一意の項目値を所定順に格納する値リストと、
前記値リストの格納順に、前記項目値毎に当該データベース中の累積レコード数を格納する累積数リストと、
前記データベースを、当該データ項目をキー項目として前記所定順にソート後の前記レコード番号の並び順を格納するソートリストと、を備えること
を特徴とする情報処理装置。
【請求項４】
請求項１または２記載の情報処理装置であって、
前記データ項目毎のインデックスファイルは、
当該データベースを、当該データ項目をキー項目として所定順にソート後の前記レコード番号の並び順を格納するソートリストと、
前記データベースの、当該データ項目が備える前記項目値を、当初の並び順で格納する元データリストと、を備えること
を特徴とする情報処理装置。
【請求項５】
請求項１から４いずれか１項記載の情報処理装置であって、
前記位置情報特定部は、前記データ項目毎のインデックスファイルを用い、当該データ項目の指定された項目値の位置情報を特定する第一探索部を備えること
を特徴とする情報処理装置。
【請求項６】
請求項１から４いずれか１項記載の情報処理装置であって、
前記位置情報特定部は、前記データ項目毎のインデックスファイルを用い、前記ソートデータベースの、指定された位置の、前記位置情報を特定する第二探索部を備えること
を特徴とする情報処理装置。
【請求項７】
請求項６記載の情報処理装置であって、
前記位置情報特定部は、前記データ項目毎の各項目値について、当該項目値より小さいレコード数および当該項目値に等しいレコード数を、前記データベース毎に算出するレコード数計算部をさらに備えること
を特徴とする情報処理装置。
【請求項８】
請求項１から７いずれか１項記載の情報処理装置であって、
前記位置情報特定部が特定した位置情報に従って、前記データベースから前記所望のレコードを抽出するレコード抽出部をさらに備えること
を特徴とする情報処理装置。
【請求項９】
所望のレコードの位置情報を特定する位置情報特定部を備える情報処理装置において、記憶装置に格納された、予め定めたデータ項目毎の項目値を格納するレコードからなり、前記各レコードには予め一意にレコード番号が付与されているデータベースにおける、予め定めたデータ項目であるターゲット項目の所定の項目値であるターゲット値を有するレコードの位置情報を特定するレコード位置情報特定方法であって、
前記記憶装置には、検索対象となり得る前記データ項目毎のインデックスファイルがさらに格納され、
前記インデックスファイルは、
当該データ項目に属する一意の項目値を所定順に格納する値リストと、
前記値リストの格納順に、前記項目値毎に当該データベース中の累積レコード数を格納する累積数リストと、
前記データベースを、当該データ項目をキー項目として前記所定順でソート後の前記レコード番号の並び順を格納するソートリストと、を備え、
前記ターゲット項目の前記値リストにアクセスし、当該データベースの当該ターゲット項目が、前記ターゲット値を有しているか否かを判別する有無判別ステップと、
前記有無判別ステップで有りと判別された場合、前記累積数リストと前記ソートリストとを用い、当該ターゲット値の前記レコード番号を特定し、前記位置情報とするレコード番号特定ステップと、を含むこと
を特徴とするレコード位置情報特定方法。
【請求項１０】
所望のレコードの位置情報を特定する位置情報特定部を備える情報処理装置において、記憶装置に格納された、予め定めたデータ項目毎の項目値を格納するレコードからなり、前記各レコードには予め一意にレコード番号が付与されているデータベースにおける、予め定めたデータ項目であるターゲット項目の所定の項目値であるターゲット値を有するレコードの位置情報を特定するレコード位置情報特定方法であって、
前記記憶装置には、検索対象となり得る前記データ項目毎のインデックスファイルがさらに格納され、
前記インデックスファイルは、
当該データベースを、当該データ項目をキー項目として所定順にソート後の前記レコード番号の並び順を格納するソートリストと、
前記データベースの、当該データ項目の前記値を、当初の並び順で格納する元データリストと、を備え、
前記ターゲット項目の前記元データリストにアクセスし、当該データベースの当該ターゲット項目が、前記ターゲット値を有しているか否かおよび有している場合、その順位を判別する有無順位判別ステップと、
前記有無順位判別ステップで有りと判別された場合、当該元データリストの前記順位を、当該ターゲット値の前記レコード番号として特定し、前記位置情報とするレコード番号特定ステップと、を含むこと
を特徴とするレコード位置情報特定方法。
【請求項１１】
所望のレコードの位置情報を特定する位置情報特定部を備える情報処理装置において、記憶装置に格納された、予め定めたデータ項目毎の項目値を格納するレコードからなり、前記各レコードには予め一意にレコード番号が付与されている複数のデータベースにおける、前記複数のデータベースを仮想的に統合して予め定めたデータ項目をキー項目としてソートした仮想統合ソートデータベース内の仮想的な位置であるターゲット位置のレコードの位置情報を特定するレコード位置情報特定方法であって、
前記記憶装置には、前記データベース毎の、検索対象となり得る前記データ項目毎のインデックスファイルがさらに格納され、
前記インデックスファイルは、
当該データ項目に属する一意の項目値を所定順に格納する値リストと、
前記値リストの格納順に、前記項目値毎に当該データベース中の累積レコード数を格納する累積数リストと、
前記データベースを、当該データ項目をキー項目として前記所定順でソート後の前記レコード番号の並び順を格納するソートリストと、を備え、
前記キー項目の前記値リストと前記累積数リストと前記ソートリストとを用い、前記仮想統合ソートデータベースにおける格納範囲に、前記ターゲット位置を含む探索値を決定する探索値決定ステップと、
前記キー項目の前記値リストと前記累積数リストと前記ソートリストとを用い、前記決定した探索値内で前記ターゲット位置に相当する探索値が属するテーブルと、当該テーブル内での順位とを前記位置情報として特定する位置情報特定ステップと、を含むこと
を特徴とするレコード位置情報特定方法。
【請求項１２】
所望のレコードの位置情報を特定する位置情報特定部を備える情報処理装置において、記憶装置に格納された、予め定めたデータ項目毎の項目値を格納するレコードからなり、前記各レコードには予め一意にレコード番号が付与されている複数のデータベースにおける、前記複数のデータベースを仮想的に統合して予め定めたデータ項目をキー項目としてソートした仮想統合ソートデータベース内の仮想的な位置であるターゲット位置のレコードの位置情報を特定するレコード位置情報特定方法であって、
前記記憶装置には、前記データベース毎の、検索対象となり得る前記データ項目毎のインデックスファイルがさらに格納され、
前記インデックスファイルは、
当該データベースを、当該データ項目をキー項目として所定順にソート後の前記レコード番号の並び順を格納するソートリストと、
前記データベースの、当該データ項目の前記値を、当初の並び順で格納する元データリストと、を備え、
前記キー項目の前記ソートリストと前記元データリストとを用い、前記仮想統合ソートデータベースにおける格納範囲に、前記ターゲット位置を含む探索値を決定する探索値決定ステップと、
前記キー項目の前記ソートリストと前記元データリストを用い、前記決定した探索値内で前記ターゲット位置に相当する探索値が属するテーブルと、当該テーブル内での順位とを前記位置情報として特定する位置情報特定ステップと、を含むこと
を特徴とするレコード位置情報特定方法。
【請求項１３】
コンピュータを、
それぞれ、予め定めたデータ項目毎の値を格納するレコードからなり、前記各データベースの各レコードには予め一意にレコード番号が付与されている複数のデータベースから、前記各データベースが備えるインデックスファイルを用いて、所望のレコードの位置情報を特定する位置情報特定手段として機能させる情報処理プログラムであって、
前記インデックスファイルは、前記データベースそれぞれから生成され、前記データ項目毎に、当該データ項目の前記項目値から前記レコード番号を取得し、かつ、ソートデータベースの順位から前記レコード番号を取得するものであり、
前記ソートデータベースは、前記複数のデータベースを仮想的に統合した仮想統合データベースを、当該データ項目をキー項目としてソートしたものであること
を特徴とする情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース管理技術に係り、特に、分散記憶される大規模データの管理技術に関する。
【背景技術】
【０００２】
データを蓄積し、必要なデータをそこから取り出して提示する「検索」はデータベース管理装置の基本的な役割である。この検索を高速化するためにはインデックスが必須である。既存のインデックスには、例えば、Ｂ−Ｔｒｅｅ、ハッシュなどがある（例えば、非特許文献１参照）。
【０００３】
近年、データ量が急激に増加し、必然的にデータベースは大規模化している。また、大規模なデータベースは、データが各地で分散収集されることが多い。例えば、各店舗で発生するＰＯＳデータ、各地の天文台や気象台などで取得される観測データなどである。
【先行技術文献】
【非特許文献】
【０００４】
非特許文献１：  Ｄｏｕｇｌａｓ  Ｃｏｍｅｒ  ”Ｔｈｅ  Ｕｂｉｑｕｉｔｏｕｓ  Ｂ−Ｔｒｅｅ”，  Ｃｏｍｐｕｔｉｎｇ  Ｓｕｒｖｅｙｓ，  Ｊｕｎｅ  １９７９，  Ｖｏｌ  １１，  Ｎｏ．２，  ｐ１２１−ｐ１３７
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来のインデックスでは、大規模なデータ、分散して取得されるデータには対応しきれていない。
【０００６】
まず、大規模化に伴って切実に要求されるようになる処理速度が十分ではない。例えば、従来のインデックスを用いると、１００万行分のデータの検索に約１秒かかるシステムがあるとしよう。１秒なら満足できる。ところが、データが１億行になると、同じ処理速度を維持したとしても１００秒かかり、使用に耐えない。また、従来最も頻繁に使用されてきたインデックスであるＢ−Ｔｒｅｅは、動作機構が複雑で、キャッシュにヒットしにくく、大規模データでの速度が出にくい。このため、データ規模が大きくなると、専用のシステムなどを構築し、対応せざるを得ない。
【０００７】
また、既存技術ではサーバレス化、データベースの分散化ができない。大規模なデータベースは、上述のように、データが各地で分散収集されることが多いが、従来の検索システムでは、データをサーバに集め、その後、検索等の処理を行う。このような手順となるのは、従来のインデックスが、データベース内のデータに、一意のレコード番号を付与することができないためである。一意のレコード番号はスキーマが異なるデータベース間でも通用する指標であるが、従来のインデックスはこの性質を有しないためにデータを分散管理することが困難となる。従って、検索時は、データを集積したサーバ側で、サーバのＣＰＵばかりを使いながら検索処理を行うこととなり、同時アクセス数の増加につれ、早い段階で検索遅延が発生する。
【０００８】
このサーバ側での処理は、高コスト化と使用環境の制約とをもたらす。通常、１台のサーバでは、せいぜい１００万行分のデータしか管理できない。このため、取扱いデータが１億行になると１００台のサーバが必要となり、導入費用、管理費用が膨大なものとなるとともに、これらのサーバを設置管理する施設が必要となる。上述のように、専用システムを構築する場合は、尚更である。また、このとき、インデックスそのものの容量も問題となる。例えば、Ｂ−Ｔｒｅｅは、データベースの格納データ数をｎとすると、Ｏ（ｎ＊ｌｏｇ（ｎ））の格納領域を必要とする。インデックスの容量の肥大化は、パフォーマンスの低下にもつながる。
【０００９】
従って、大規模データベースでのインデックスは、データベースが大規模になっても、必要な記憶容量が急激に増大しない性質を有することが望ましい。例えば、データベースの格納データ数をｎとすると、そのサイズはＯ（ｎ）が望ましい。また、サーバレス化し、各地で取得されたデータを、そのまま各地で分散管理し、ネットワークを介して、自在にアクセスできることが望ましい。これらは現状のインデックスでは実現できない。
【００１０】
本発明は、上記事情に鑑みてなされたもので、大規模データベースを、低コストで使用環境の制約なく管理でき、使い勝手のよい環境を提供する技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、それぞれ一意のレコード番号を有する複数のレコードが格納されるデータベースから所望のレコードの位置情報を特定するためのインデックスであって、指定された値のレコード番号を返すとともに、所定の項目でソート後の順位に応じたレコード番号を返すインデックスを用いたレコードの位置情報を特定する位置情報特定部を備える情報処理装置を提供する。また、このインデックスのサイズは、元のデータベースサイズに比例的とする。
【００１２】
具体的には、予め定めたデータ項目毎の項目値を格納するレコードからなるデータベースを管理する情報処理装置であって、検索対象となり得る前記データ項目毎のインデックスファイルと、前記インデックスファイルを用いて、所望のレコードの位置情報を特定する位置情報特定部と、を備え、前記各レコードには、予め一意にレコード番号が付与され、前記位置情報特定部は、前記位置情報として前記レコード番号を特定し、前記データ項目毎のインデックスファイルは、当該データ項目の前記項目値から前記レコード番号を取得でき、かつ、当該データ項目をキー項目としてソートしたソートデータベースの順位から前記レコード番号を取得できるものであることを特徴とする情報処理装置を提供する。
【００１３】
また、所望のレコードの位置情報を特定する位置情報特定部を備える情報処理装置において、記憶装置に格納された、予め定めたデータ項目毎の項目値を格納するレコードからなるデータベースであって、各レコードには予め一意にレコード番号が付与されているデータベースにおける、予め定めたデータ項目であるターゲット項目の所定の項目値であるターゲット値を有するレコードの位置情報を特定するレコード位置情報特定方法であって、前記記憶装置には、検索対象となり得る前記データ項目毎のインデックスファイルがさらに格納され、前記インデックスファイルは、当該データ項目に属する一意の項目値を所定順に格納する値リストと、前記値リストの格納順に、前記項目値毎に当該データベース中の累積レコード数を格納する累積数リストと、前記データベースを、当該データ項目をキー項目として前記所定順でソート後の前記レコード番号の並び順を格納するソートリストと、を備え、前記ターゲット項目の前記値リストにアクセスし、当該データベースの当該ターゲット項目が、前記ターゲット値を有しているか否かを判別する有無判別ステップと、前記有無判別ステップで有りと判別された場合、前記累積数リストと前記ソートリストとを用い、当該ターゲット値の前記レコード番号を特定し、前記位置情報とするレコード番号特定ステップと、を備えることを特徴とするレコード位置情報特定方法を提供する。
【００１４】
さらに、所望のレコードの位置情報を特定する位置情報特定部を備える情報処理装置において、記憶装置に格納された、予め定めたデータ項目毎の項目値を格納するレコードからなる複数のデータベースであって、各レコードには予め一意にレコード番号が付与されている複数のデータベースにおける、前記複数のデータベースを仮想的に統合して予め定めたデータ項目をキー項目としてソートした仮想統合ソートデータベース内の仮想的な位置であるターゲット位置のレコードの位置情報を特定するレコード位置情報特定方法であって、前記記憶装置には、前記データベース毎の、検索対象となり得る前記データ項目毎のインデックスファイルがさらに格納され、前記インデックスファイルは、当該データ項目に属する一意の項目値を所定順に格納する値リストと、前記値リストの格納順に、前記項目値毎に当該データベース中の累積レコード数を格納する累積数リストと、前記データベースを、当該データ項目をキー項目として前記所定順でソート後の前記レコード番号の並び順を格納するソートリストと、を備え、前記キー項目の前記値リストと前記累積数リストと前記ソートリストとを用い、前記仮想統合ソートデータベースにおける格納範囲に、前記ターゲット位置を含む探索値を決定する探索値決定ステップと、前記キー項目の前記値リストと前記累積数リストと前記ソートリストとを用い、前記決定した探索値内で前記ターゲット位置に相当する探索値が属するテーブルと、当該テーブル内での順位とを前記位置情報として特定する位置情報特定ステップと、を備えることを特徴とするレコード位置情報特定方法を提供する。
【００１５】
また、コンピュータを、それぞれ、予め定めたデータ項目毎の値を格納するレコードからなる複数のデータベースであって、各データベースの各レコードには予め一意にレコード番号が付与されているデータベースから、各データベースが備えるインデックスファイルを用いて、所望のレコードの位置情報を特定する位置情報特定手段として機能させる情報処理プログラムであって、前記インデックスファイルは、前記データベースそれぞれから生成され、前記データ項目毎に、当該データ項目の前記項目値から前記レコード番号を取得し、かつ、当該データ項目をキー項目としてソートしたソートデータベースの順位から前記レコード番号を取得するものであることを特徴とする情報処理プログラムを提供する。
【００１６】
また、ネットワークで接続された、予め定めたデータ項目毎の項目値を格納するレコードからなるデータベースを管理する第一の情報処理装置と、所望の前記レコードの位置情報を特定する第二の情報処理装置と、を備えるデータベースシステムであって、前記第一の情報処理装置は、検索対象となり得る前記データ項目毎のインデックスファイルを備え、前記各レコードには、予め一意にレコード番号が付与され、前記データ項目毎のインデックスファイルは、当該データ項目の前記項目値から前記レコード番号を取得でき、かつ、当該データ項目をキー項目としてソートしたソートデータベースの順位から前記レコード番号を取得できるものであり、前記第二の情報処理装置は、前記位置情報として前記レコード番号を特定することを特徴とするデータベースシステムを提供する。
【００１７】
このデータベースシステムにおいて、管理対象の前記データベースは複数であり、前記各データベースには、予め一意にデータベースＩＤが付与され、前記インデックスファイルは、前記データベース毎に生成され、前記ソートデータベースは、前記複数のデータベースを仮想的に統合した仮想統合データベースを、当該データ項目をキー項目としてソートしたデータベースであり、前記第二の情報処理装置は、前記位置情報として、所望のレコードが属するデータベースの前記データベースＩＤをさらに特定するよう構成してもよい。このとき、前記管理対象の複数のデータベースのうち、少なくとも１以上のデータベースが、それぞれ前記ネットワークに接続された異なる第一の情報処理装置上に格納されていてもよい。
【発明の効果】
【００１８】
大規模データベースを、低コストで使用環境の制約なく管理でき、使い勝手のよいデータベース管理環境を提供できる。
【図面の簡単な説明】
【００１９】
【図１】第一の実施形態のデータベースシステムのブロック図である。
【図２】（ａ）〜（ｄ）は、第一の実施形態のデータベースを説明するための説明図である。
【図３】（ａ）〜（ｄ）は、第一の実施形態のデータベースを説明するための説明図である。
【図４】第一の実施形態の仮想統合データおよび仮想統合ソートデータを説明するための説明図である。
【図５】第一の実施形態の情報処理装置の機能ブロック図である。
【図６】（ａ）〜（ｃ）は、第一の実施形態のデータ項目毎のインデックスファイルを説明するための説明図である。
【図７】（ａ）および（ｂ）は、第一の実施形態のテーブル毎のインデックスファイルを説明するための説明図である。
【図８】第一の実施形態の第一探索処理のフローチャートである。
【図９】第一の実施形態の第二探索処理のフローチャートである。
【図１０】第一の実施形態の位置情報特定処理のフローチャートである。
【図１１】第一の実施形態の閲覧処理を説明するための説明図である。
【図１２】（ａ）〜（ｃ）は、第二の実施形態のデータ項目毎のインデックスファイルを説明するための説明図である。
【図１３】（ａ）および（ｂ）は、第二の実施形態のテーブル毎のインデックスファイルを説明するための説明図である。
【発明を実施するための形態】
【００２０】
＜＜第一の実施形態＞＞
以下、本発明を適用する実施形態を、図面を用いて説明する。まず、本実施形態のシステム構成を説明する。
【００２１】
図１は、本発明の実施形態のデータベースシステム１００の概略およびデータベースシステム１００が備える情報処理装置の機能ブロックを説明するための図である。本図に示すように、本実施形態では、複数の情報処理装置１１０−０、１１０−１、１１０−２がネットワーク１２０を介して接続される。以下、各情報処理装置を区別する必要が無い場合は、情報処理装置１１０で代表する。なお、ここでは、一例として、ネットワーク１２０に接続される情報処理装置１１０が３台の場合を示すが、接続される情報処理装置１１０の数はこれに限られない。
【００２２】
各情報処理装置１１０は、後述するデータベースを保持するとともに、各情報処理装置１１０が保持するデータベースを管理するデータ管理装置として機能する。データ管理装置として、例えば、データベースの閲覧機能、検索機能なども提供する。各情報処理装置１１０は、ＣＰＵ１１１とメモリ１１２と記憶装置１１３とを備える。また、ネットワーク１２０を介して、各情報処理装置１１０間でデータの送受信を可能とするネットワークインタフェース（ＮＷＩＦ）１１４を備える。また、各情報処理装置１１０には、情報処理装置１１０のユーザインタフェースである入力装置１１５および表示装置１１６が接続される。さらに、外部記憶装置１１７が接続されていてもよい。
【００２３】
本実施形態では、各情報処理装置１１０−０、１１０−１、１１０−２が、それぞれ、データベース２００−０、２００−１、２００−２を蓄積する。データベースについても、特に区別する必要が無い場合は、表形式データ２０１で代表する。データベース２００は、各情報処理装置１１０の記憶装置１１３または外部記憶装置１１７に蓄積される。
【００２４】
さらに、本実施形態では、各情報処理装置１１０−０、１１０−１、１１０−２は、それぞれ、データベース２００−０、２００−１、２００−２のインデックスファイル３００−０、３００−１、３００−２を備える。インデックスファイルについても、特に区別する必要が無い場合は、インデックスファイル３００で代表する。インデックスファイル３００は、各情報処理装置１１０の記憶装置１１３またはメモリ１１２に蓄積される。また、インデックスファイル３００は、任意の時間間隔で作成される。例えば、所定量のデータが収集される毎に作成される。
【００２５】
次に、各情報処理装置１１０が蓄積するデータベース２００について説明する。本実施形態のデータベースは、構造化された表形式データ、半構造化データ、非構造化データ、いずれであってもよい。
【００２６】
構造化された表形式データ２０１の例を図２（ａ）に示す。構造化された表形式データ２０１は、本図に示すように、１つ以上のデータ項目（列）２１１に対応した項目値２１２を含む１つ以上のレコード（行）２１３の配列である。
【００２７】
各レコード２１３には、レコード番号（ＲｅｃＮｏ．）２１４が付与される。このレコード番号は、表形式データ２０１の中の、レコードが収容されている位置を表す情報である。このレコード番号は、表形式データ２０１に、所定のタイミングで付与される。所定のタイミングは、例えば、表形式データ２０１が作成された時点などとする。本実施形態のデータベース２００では、レコード番号を指定することにより、各レコードにアクセスできる。
【００２８】
一般に、表形式データ２０１は、レコードが常にレコード番号（ＲｅｃＮｏ．）２１４の順番に配列されているとは限らない。たとえば、作成時の表形式データ２０１（元の表形式データ２０１と呼ぶ。）を、所定のデータ項目２１１をキー項目として、その項目値２１２が昇順に並ぶようにソートすると、ソート後の表形式データ２０１ｓのレコードの並び順は、元の表形式データ２０１のレコードの並び順とは異なる。このような例を図２（ｂ）に示す。図２（ｂ）は、データ項目２１１「Ｎａｍｅ」をキー項目として、表形式データ２０１を昇順にソートした場合のソート結果である。本明細書では、各態様のデータベース２００のレコードの並び順を表す情報を、レコード順序番号（順位）２１５と呼ぶ。元の表形式データ２０１では、レコード順序番号２１５は、レコード番号（ＲｅｃＮｏ．）２１４に一致する。
【００２９】
なお、図２（ａ）では、データ項目２１１として、＜Ｇｅｎｄｅｒ＞、＜Ｎａｍｅ＞、＜Ａｇｅ＞の３つを備える５つのレコード２１３を例示する。ここでは、例えば、レコード番号２１４が０のレコード２１３の、データ項目２１１が＜Ｇｅｎｄｅｒ＞の項目値２１２は「ｆｅｍａｌｅ」、データ項目２１１が＜Ｎａｍｅ＞の項目値２１２は「Ｊｅｍｉ」、データ項目２１１が＜Ａｇｅ＞の項目値２１２は、「２」である。ただし、本実施形態では、データ項目２１１の数、レコード２１３の数はこれに限られない。
【００３０】
なお、項目値２１２は、数値データ、テキストデータのいずれであってもよいが一意に順序を付与できるものとする。例えば、データ項目２１１が＜Ａｇｅ＞の項目値２１２として２、１・・といった数値データが格納され、データ項目２１１が＜Ｎａｍｅ＞の項目値２１２としてＪｅｍｉ、Ｇｒｉｚａ、・・・・といったテキストデータが格納される。
【００３１】
なお、図２（ｃ）および図２（ｄ）に示すように、本実施形態の表形式データ２０１のデータ項目２１１は、各レコード２１３に複数の項目値２１２を格納可能な繰り返し項目であってもよい。ここでは、＜Ｎａｍｅ＞のデータ項目２１１が、繰り返し項目である場合を例示する。なお、繰り返し項目の中に格納される複数の項目値２１２は、通常順序を問わない。すなわち、図２（ｃ）の表形式データ２０１と図２（ｄ）に示す表形式データ２０１とは、論理的に同じとみなされる。
【００３２】
半構造化データ２０２の例を、図３（ａ）に示す。半構造化データ２０２は、基本的に表形式データ２０１と同様の構成を有する。すなわち、１つ以上のデータ項目２１１に対応した項目値２１２を含む１つ以上のレコードの配列である。ただし、半構造化データ２０２では、データ項目２１１には、必ず値があることが保証されるデータ項目２１１と、保証されていないデータ項目２１１とがある。
【００３３】
図３（ａ）の例では、＜ＩＤ＞が、必ず値があることが保証されるデータ項目２１１であり、その他の＜ｎａｍｅ＞、＜ａｄｄｒｅｓｓ＞、＜ｇｅｎｄｅｒ＞、＜ａｇｅ＞、＜ｆｏｏｄ＞は、保証されていないデータ項目２１１である。
【００３４】
非構造化データ２０３の例を図３（ｂ）に示す。非構造化データ２０３も、基本的に表形式データ２０１と同様の構成を有する。すなわち、１つ以上のデータ項目２１１に対応した項目値２１２を含む１つ以上のレコード２１３の配列である。ただし、非構造化データ２０３では、データが存在することを保証されるデータ項目はない。
【００３５】
なお、本実施形態では、半構造化データ２０３および非構造化データ２０４は、それぞれ図３（ｃ）および図３（ｄ）に示すように、表形式データ２０１と同様の構造にマッピングし、処理を行う。なお、値のない項目値２１２（ＮＵＬＬ項目）の取り扱いは、予め定めておく。以下、本実施形態では、ＮＵＬＬ項目は、各データ項目２１１の最小値として取り扱うものとして説明する。
【００３６】
以下、本実施形態では、データベース２００として、ＮＵＬＬ項目を有する場合も含め、構造化された表形式データ２０１が登録されている場合を例にあげて説明する。他の形式のデータであっても、処理は同様である。
【００３７】
また、本実施形態では、表形式データ２０１は、分散管理されているものとする。以下、本明細書では、各情報処理装置１１０が備える表形式データ２０１を、それぞれテーブル（Ｔａｂｌｅ）と呼ぶ。各テーブルは、予め一意に識別番号ｉが付与されるものとする。本実施形態では、表形式データ２０１−０、２０１−１、２０１−２を、それぞれ、識別番号０、１、２が付与された、Ｔａｂｌｅ０，Ｔａｂｌｅ１，Ｔａｂｌｅ２と呼ぶ。なお、本実施形態では、テーブルは、１の情報処理装置１１０が複数備えていてもよい。また、各テーブルの識別番号ｉを、テーブルＩＤと呼ぶ。
【００３８】
本実施形態の情報処理装置１１０は、分散管理されているテーブル群から、所望のレコードの位置情報を特定する。分散管理されているテーブル群を、テーブルＩＤ順に仮想的に統合したデータベースを、仮想統合データベース（仮想統合ＤＢ）と呼ぶ。また、仮想統合ＤＢを、所定のデータ項目をキー項目としてソートしたデータベースを、仮想統合ソートデータベース（仮想統合ソートＤＢ）と呼ぶ。仮想統合ソートＤＢのレコード順序番号を、仮想行（Ｖｒｅｃ）と呼ぶ。
【００３９】
図４は、仮想統合ＤＢと仮想統合ソートＤＢを説明するための図である。ここでは、検索対象テーブル群を、テーブル０（Ｔａｂｌｅ０）とテーブル１（Ｔａｂｌｅ１）とする場合を例示する。本図に示すように、仮想統合ＤＢ５００は、テーブル０と、テーブル１とをテーブルＩＤ順に仮想的に統合したものである。また、仮想統合ソートＤＢ５１０は、仮想統合ＤＢ５００を、所定のデータ項目（ここでは、＜Ｎａｍｅ＞）をキーとしてソートしたものである。ここで、項目５０１は、テーブルＩＤとレコード番号とを示すものである。
【００４０】
本例では、テーブル０は、図２（ａ）に示す表形式データ２０１であり、レコード数５つの構造化された表形式データである。一方、テーブル１は、レコード数６つで、ＮＵＬＬ項目を有する非構造化データである。
【００４１】
本実施形態の情報処理装置１１０は、ユーザからデータ項目２１１と所定の項目値２１２とを指定されると、テーブル群を探索し、当該データ項目２１１で指定された項目値２１２を有するレコード２１３を特定し、位置情報を返す。位置情報は、当該項目値２１２に等しいレコード２１３が所属するテーブル（所属テーブル）のテーブルＩＤと、レコード番号とする。また、ユーザから、仮想統合ソートＤＢ５１０を生成する際のキー項目とするデータ項目２１１と、仮想行（Ｖｒｅｃ）とを指定されると、当該仮想行（Ｖｒｅｃ）のレコード２１３の位置情報を返す。
【００４２】
これを実現する情報処理装置１１０の機能を以下に説明する。図５に、上記機能を実現する情報処理装置１１０の機能ブロック図を示す。本図に示すように、本実施形態の情報処理装置１１０は、インデックス作成部４１０と、位置情報特定部４２０とを備える。これらの各機能は、情報処理装置１１０が備えるＣＰＵ１１１が、予め記憶装置１１３に保持するプログラムを、メモリ１１２にロードして実行することにより実現される。以下、各部の詳細について説明する。
【００４３】
インデックス作成部４１０は、任意の時間間隔で、表形式データ２０１からインデックスファイル３００を作成する。
【００４４】
ここで、本実施形態のインデックス作成部４１０が作成するインデックスファイル３００について説明する。本実施形態のインデックスファイル３００は、各情報処理装置１１０上で管理される表形式データ２０１から、所望のレコード２１３の位置を特定する処理を高速化するために設けられる、１以上の要素を備える配列形式の１以上のリストである。
【００４５】
図６は、本実施形態のインデックスファイル３００を説明するための図である。本実施形態のインデックス作成部４１０は、分散管理される全てのテーブルについて、それぞれ以下のインデックスファイル３００を作成する。ここでは、図２（ａ）に示す表形式データ２０１から作成されるインデックスファイル３００を例にあげて説明する。
【００４６】
インデックスファイル３００は、表形式データ２０１のデータ項目２１１毎に生成される。インデックスファイル３００を作成するデータ項目２１１を着目項目と呼ぶ。図６（ａ）は、着目項目が＜Ｇｅｎｄｅｒ＞の、図６（ｂ）は、着目項目が＜Ｎａｍｅ＞の、図６（ｃ）は、着目項目が＜Ａｇｅ＞の例である。これらの図に示すように、本実施形態のインデックスファイル３００は、値リスト（ＶＬ）３１０と、蓄積数リスト（ＣＡＧＲ）３２０と、ソートリスト（ＳＯＳ）３３０と、を備える。各リストは、要素とその位置であるレコード順序番号を示す順位（Ｏｒｄ）とから構成される。各リストは、順位（Ｏｒｄ）を指定することにより、各要素を抽出することができる。また、リストＡＢＣの、０から始まる順位ｊの要素をＡＢＣ［ｊ］と示す。
【００４７】
ＶＬ３１０は、着目項目に表れる一意の項目値２１２を、予め定めた順（例えば、昇順または降順）にソートし、要素として格納したリストである。具体的には、ＶＬ３１０は、表形式データ２０１を、着目項目をキーとして、予め定めた順にソートし、その結果（ソート後の表形式データ２０１ｓ）の同一値をサプレスすることにより生成する。
【００４８】
ＳＯＳ３３０は、表形式データ２０１を、着目項目をキーとしてソートした際のレコード番号２１４の並び順を要素として格納したものである。ソートは、ＶＬ３１０と同じ同順とする。ＳＯＳ３３０を備えることにより、ソート後の項目値２１２に対応するレコード番号２１４を自由に取り出すことができる。
【００４９】
ＣＡＧＲ３２０は、各項目値２１２のレコード数の累積値を要素として格納したものである。レコード数の累積は、ＶＬ３１０の順になされる。これは、ＶＬ３１０とＳＯＳ３３０とを関連付けるリストでもある。ＣＡＧＲ３２０により、ＶＬ３１０の各要素の、ＳＯＳ３３０の格納範囲を知ることができる。すなわち、ｉが０より大きい場合、ＶＬ３１０の要素ＶＬ［ｊ］は、ＳＯＳ３３０の、［ＣＡＧＲ［ｊ−１］，ＣＡＧＲ［ｊ］）の区間、すなわち、ＣＡＧＲ［ｊ−１］からＣＡＧＲ［ｊ］−１の順位に格納される。なお、ＶＬ３１０の要素ＶＬ［０］は、ＳＯＳ３３０の、［０，ＣＡＧＲ［０］）の区間の順位に格納される。以下、本明細書では、区間、範囲を説明する際、閉区間を［］で示し、開区間を（）で示す。
【００５０】
例えば、図６（ｂ）の例では、ＶＬの順位１の要素「Ｇｒｉｚｚａ」について説明する。ＣＡＧＲ３２０の順位０の要素は「１」であり、ＣＡＧＲ３２０の順位１の要素は「３」である。従って、「Ｇｒｉｚｚａ」は、ＳＯＳ３３０の順位［１、３）の範囲、すなわち、順位［１，２］の範囲に格納される。
【００５１】
また、インデックスファイル３００の各リストは、テーブル毎に作成される。図７（ａ）および図７（ｂ）に、着目項目が＜Ｎａｍｅ＞の場合のインデックスファイル３００例を示す。図７（ａ）がテーブル０のインデックスファイル３００であり、図７（ｂ）がテーブル１のインデックスファイル３００である。
【００５２】
次に、位置情報特定部４２０について説明する。位置情報特定部４２０は、ユーザからの指示に従って、インデックスファイル３００を用い、テーブル群を探索し、所定のレコードの位置情報を特定する。これを実現するため、本実施形態の位置情報特定部４２０は、データ項目２１１と所定の項目値２１２とが指定されたことを受け、当該データ項目２１１の項目値２１２を有するレコードを探索し、位置情報を特定する第一探索部４２１と、ソートキー項目とするデータ項目２１１と仮想行（Ｖｒｅｃ）とが指定されたことを受け、当該仮想行（Ｖｒｅｃ）のレコードを探索し、位置情報を特定する第二探索部４２２と、指定されたレコード数を計算するレコード数計算部４２３と、を備える。
【００５３】
本実施形態のレコード数計算部４２３は、以下の式（１）および式（２）で示す２つの関数を用意し、第一探索部４２１および第二探索部４２２が位置情報を探索する際、以下の式（３）および式（６）で示すレコード数を計算する。算出は、指定されたデータ項目２１１の、ＶＬ３１０、ＣＡＧＲ３２０、ＳＯＳ３３０を用いて行う。以下、テーブル（ｉ）の各リストを、それぞれ、ＶＬ（ｉ）、ＣＡＧＲ（ｉ）、ＳＯＳ（ｉ）と呼ぶ。
【００５４】
【数１】
2015207026.tif 000003
式（１）で得られるＣＬＴＰ（ｉ）［ｊ］は、ＶＬ（ｉ）の順位ｊの項目値より小さい値に属するレコード数である。
【数２】
2015207026.tif 000004
式（２）で得られるＣＥＱＰ（ｉ）［ｊ］は、ＶＬ（ｉ）の順位ｊの項目値と等しい値に属するレコード数である。
【００５５】
【数３】
2015207026.tif 000005
式（３）で得られるＣＬＴＶ（ｉ）＜ｘ＞は、テーブルｉの、予め定めた項目値ｘより小さい値に属するレコード数である。なお、式（３）において、ｃａｓｅ１は、項目値ｘがＶＬ（ｉ）に存在する場合であり、ｊは、項目値ｘのＶＬ（ｉ）内の順位である。また、ｃａｓｅ２は、項目値ｘがＶＬ（ｉ）に存在しない場合であって、ｊは、ＶＬ（ｉ）の項目値の中に、ｘより小さい値が存在する場合の、その最大の項目値の順位とする。また、ｃａｓｅ３は、項目値ｘがＶＬ（ｉ）に存在しない場合であって、かつ、ＶＬ（ｉ）の項目値の中に、ｘより小さい値が存在しない場合である。
【００５６】
【数４】
2015207026.tif 000006
式（４）で得られるＣＥＱＶ（ｉ）＜ｘ＞は、テーブルｉの、予め定めた項目値ｘと等しい値に属するレコード数である。なお、（４）において、ｃａｓｅ１は、項目値ｘがＶＬ（ｉ）に存在する場合でり、ｊは、項目値ｘのＶＬ（ｉ）内の順位とする。また、ｃａｓｅ２は、項目値ｘがＶＬ（ｉ）に存在しない場合である。
【００５７】
【数５】
2015207026.tif 000007
式（５）で得られるＣＡＬＴＶ＜ｘ＞は、仮想統合ＤＢ５００および仮想統合ソートＤＢ５１０における、予め定めた項目値ｘより小さい値に属するレコード数である。
【００５８】
【数６】
2015207026.tif 000008
式（６）で得られるＣＡＥＱＶ＜ｘ＞は、仮想統合ＤＢ５００および仮想統合ソートＤＢ５１０における、予め定めた項目値ｘと等しい値に属するレコード数である。
【００５９】
次に、本実施形態の第一探索部４２１の処理を説明する。上述のように、第一探索部４２１は、ユーザからデータ項目２１１と項目値とが与えられると、分散管理対象のテーブル内の位置情報を返す。すなわち、値から、当該値を有するレコードの、テーブルＩＤとレコード番号とを特定する。
【００６０】
具体的には、各テーブルｉについて、テーブルＩＤ順に、当該データ項目２１１を着目項目とするインデックスファイル３００の中のＶＬ（ｉ）を探索し、指定された項目値の有無、および、有りの場合はその位置を特定する。ＶＬ（ｉ）の探索は、２分割法などを用いて行う。そして、ＶＬ（ｉ）内で指定された項目値が有る場合は、ＣＡＧＲ（ｉ）、ＳＯＳ（ｉ）を用い、上記手法で、そのレコード番号を特定する。
【００６１】
図８は、本実施形態の第一探索部４２１による第一探索処理の処理フロー例である。なお、ここでは、探索対象とするテーブル数をＭ（Ｍは１以上の整数）とする。探索対象とするテーブル群は、予め定められているものとする。また、このとき、探索結果は、記憶装置１１３内の第一探索結果格納領域に格納されるものとする。
【００６２】
本図に示すように、ユーザから、探索対象のデータ項目２１１（Ｔａｒｇｅｔ  Ｉｔｅｍ：ＴＩ）と項目値２１２（Ｔａｒｇｅｔ  Ｖａｌｕｅ：ＴＶ）とが与えられると、まず、探索するテーブルＩＤを初期化する（ｉ＝０）とともに、第一探索結果格納領域を初期化する（ステップＳ１１０１）。そして、テーブルｉのデータ項目ＴＩのインデックスファイル３００にアクセスする。
【００６３】
まず、ＶＬ（ｉ）にアクセスし、項目値ＴＶを探索する（ステップＳ１１０２）。ここでは、２分割法などを用い、探索する。ＶＬ（ｉ）に項目値ＴＶが存在する場合、その順位を抽出し、ＣＡＧＲ（ｉ）にアクセスし、上述の手法で、項目値ＴＶのＳＯＳ（ｉ）での格納範囲を特定する（ステップＳ１１０３）。得られた格納範囲に従ってＳＯＳ（ｉ）にアクセスし、項目値ＴＶのレコード番号２１４を得る（ステップＳ１１０４）。得られたレコード番号２１４を、探索中のテーブルのテーブルＩＤに対応づけて、第一探索結果格納領域に追加保存する（ステップＳ１１０５）。
【００６４】
その後、全てのテーブルの処理を終えるまで、次のテーブルのインデックスファイル（ｉ）にアクセスし、ステップＳ１１０２からの処理を繰り返す（ステップＳ１１０６、１１０７）。
【００６５】
一方、ステップＳ１１０２において、ＶＬ（ｉ）に項目値ＴＶが存在しない場合、そのままステップＳ１１０６に移行し、処理を繰り返す。
【００６６】
全てのテーブルの処理を終えると、第一探索結果格納領域に保存されるテーブルＩＤとレコード番号との組を、位置情報として出力する（ステップＳ１１０８）。
【００６７】
以上の第一探索部４２１による第一探索処理を、図７を用い、具体例で説明する。例えば、データ項目２１１として＜Ｎａｍｅ＞が、項目値として「Ｓｉｌｌａｂｕｂ」が指定されたものとする。まず、テーブル０のＶＬ（０）にアクセスし、「Ｓｉｌｌａｂｕｂ」の有無を判別する。テーブル０には、この項目値はないため、次にテーブル１に移る。そして、テーブル１で、同様にＶＬ（１）にアクセスし、順位として４を得る。ＣＡＧＲ（０）にアクセスし、その格納範囲として［４，５］を得る。そして、ＳＯＳ（０）にアクセスし、レコード番号１、２を得る。最終的に探索結果として、テーブル１のレコード番号１、２を出力する。
【００６８】
次に、本実施形態の第二探索部４２２の処理を説明する。上述のように、第二探索部４２２は、ユーザからキー項目と仮想統合ソートＤＢ５１０の仮想行（Ｖｒｅｃ）とを指定されると、該当レコードの位置情報を返す。すなわち、仮想統合ソートＤＢ５１０の指定仮想行ＴＰのレコードの、テーブルＩＤとレコード番号２１４とを特定する。
【００６９】
具体的には、テーブルＩＤ順に、ＶＬ３１０にアクセスし、所定の位置（例えば、中央付近）の値を抽出し、仮の探索値（仮探索値）とし、仮探索値の、仮想統合ソートＤＢ５１０における仮想行（仮仮想行）を得る。得られた仮仮想行と指定仮想行とを比較し、両者が一致するまで、探索を繰り返す。そして、一致した仮探索値の位置情報を算出する。
【００７０】
なお、仮探索値の仮仮想行は、上記レコード数計算部４２３による式（５）および式（６）で算出する。すなわち、仮仮想行（順位）の範囲は、［ＣＡＬＴＶ＜仮探索値＞、ＣＡＬＴＶ＜仮探索値＞＋ＣＡＥＱＶ＜仮探索値＞）である。すなわち、ＣＡＬＴＶ＜仮探索値＞からＣＡＬＴＶ＜仮探索値＞＋ＣＡＥＱＶ＜仮探索値＞−１である。
【００７１】
図９は、本実施形態の第二探索部４２２による第二探索処理の処理フロー例である。なお、ここでは、探索対象とするテーブル数をＭ（Ｍは１以上の整数）とする。また、このとき、記憶装置１１３内の、探索結果を格納する領域を第二探索結果格納領域とする。また、仮探索値として抽出した値を保持する領域を、仮探索値格納領域とする。
【００７２】
ユーザから指定仮想行としてＴＰが与えられると、まず、探索するテーブル番号および第二探索結果格納領域を初期化する（ステップＳ１２０１）。そして、テーブルｉの、仮想統合ソートＤＢ５１０作成時のキー項目ＴＩの、インデックスファイル３００にアクセスする。
【００７３】
まず、ＶＬ（ｉ）にアクセスし、予め定めた規則に従って仮探索値ｖｐを決定する（ステップＳ１２０２）。ここでは、上述のように、例えば、中央値を抽出する。このとき、仮探索値ｖｐの、当該ＶＬ（ｉ）における順位をｊとする。また、決定した仮探索値ｖｐおよび順位ｊを、仮探索値格納領域に追加登録する（ステップＳ１２０３）。そして、レコード数計算部４２３に、仮探索値ｖｐの仮想行（仮仮想行）の範囲を算出させる（ステップＳ１２０４）。
【００７４】
指定仮想行ＴＰと仮仮想行の範囲とを比較する（ステップＳ１２０５）。指定仮想行ＴＰが、仮仮想行の範囲内であれば、仮探索値ｖｐが、仮想行の値ＶＴＰであると決定する（ステップＳ１２０９）。そして、値ＶＴＰの中の、仮想行ＴＰのテーブルＩＤとレコード番号とを特定する位置情報特定処理を行い（ステップＳ１２１０）、処理を終了する。
【００７５】
一方、指定仮想行ＴＰが仮仮想行の範囲外である場合、予め定めた規則に従って、テーブルｉ内で新たな仮探索値を決定可能か判断する（ステップＳ１２０６）。ここでは、例えば、指定仮想行ＴＰが、仮仮想行の最小値より小さい場合、ＶＬ（ｉ）内の仮探索値ｖｐと、仮探索値格納領域に既に格納されている仮探索値で、仮探索値ｖｐより小さい値の中の最大値と、の間で決定する。一方、指定仮想行ＴＰが仮仮想行の最大値より大きい場合、ＶＬ（ｉ）内の仮探索値ｖｐと、仮探索値格納領域に格納されている仮探索値で、仮探索値ｖｐより大きい値の中の最小値との間で決定する。
【００７６】
決定可能な場合、新たな仮探索値ｖｐを決定し（ステップＳ１２０７）、ステップＳ１２０３へ移行し、処理を繰り返す。
【００７７】
一方、新たな仮探索値ｖｐを、上記範囲で決定できない場合、次のテーブルに移行し（ステップＳ１２０８）、ステップＳ１２０２から処理を繰り返す。
【００７８】
次に、本実施形態の第二探索部４２２による、上記位置情報特定処理の流れを説明する。ここでは、テーブルＩＤ順に、仮想行ＴＰに相当するレコードが、当該テーブルに属するか否かを判別し、属する場合、その中のレコード番号を決定する。これらの判別および決定には、レコード数計算部４２３による計算結果を用いる。図１０は、第二探索部４２２による本実施形態の位置情報特定処理の処理フロー例である。
【００７９】
まず、所属するテーブルのテーブルＩＤを決定する所属テーブル決定処理を行う。ここでは、テーブルＩＤ順に（ステップＳ１３０１）、ｉ以下のテーブルが有する、値ＶＴＰに等しい値のレコードの総数ＡＣ（ｉ）＜ＶＴＰ＞を算出する（ステップＳ１３０２）。ＡＣ（ｉ）は、以下の式（７）で算出する。
【数７】
2015207026.tif 000009
【００８０】
そして、当該テーブルｉの項目値ＶＴＰに等しい値を有するレコードの中の順位が最大のレコードの、仮想統合ソートＤＢ５１０内の順位ＰＯＳ（ｉ）＜ＶＴＰ＞（算出仮想行）を決定する。このＰＯＳ（ｉ）＜ＶＴＰ＞は、項目値ＶＴＰより小さい値のレコード総数ＣＡＬＴＶ＜ＶＴＰ＞に、ＡＣ（ｉ）＜ＶＴＰ＞を加算する、以下の式（８）により得られる（ステップＳ１３０３）。
【数８】
2015207026.tif 000010
【００８１】
その後、算出された仮想行ＰＯＳ（ｉ）＜ＶＴＰ＞と指定された仮想行ＴＰとの大小を比較する（ステップＳ１３０４）。その結果、ＰＯＳ（ｉ）＜ＶＴＰ＞が仮想行ＴＰ以上の場合、仮想行ＴＰに対応するレコードの所属テーブルは、テーブルｉと決定する（ステップＳ１３０５）。
【００８２】
ステップＳ１３０４で、算出された仮想行が指定された仮想行ＴＰより小さい場合、次のテーブルに移り（ステップＳ１３１０）、ステップＳ１３０２に戻り、処理を繰り返す。
【００８３】
一方、所属テーブルｉが決定すると、以下の式を用い、仮想行ＴＰに相当するレコードの、テーブルｉ内のレコード番号（ＲｅｃＮｏ．）を算出するレコード番号算出処理を行う。
【００８４】
レコード番号算出処理では、まず、仮想統合ソートＤＢ５１０の、テーブルｉの項目値ＶＴＰに等しい値に属するレコードの、直前のレコードの位置を算出する（ステップＳ１３０６）。これは、ＰＯＳ（ｉ−１）＜ＶＴＰ＞である。なお、ｉ＝０のときは、ＣＡＬＴＶ＜ＶＴＰ＞とする。
【００８５】
そして、テーブルｉ内の項目値ＶＴＰに等しい値に属するレコードの中で、仮想行ＴＰに相当するレコードのレコード順位ＡＡを算出する（ステップＳ１３０７）。これは、仮想行ＴＰから、ＰＯＳ（ｉ−１）＜ＶＴＰ＞（または、ＣＡＬＴＶ＜ＶＴＰ＞）を減算した値から、さらに１を減算したものとして得られる。
【００８６】
そして、ＳＯＳ（ｉ）内での順位Ｏｒｄを算出する（ステップＳ１３０８）。テーブルｉ内の項目値ＶＴＰより小さい値に属するレコード数ＣＬＴＶ（ｉ）＜ＶＴＰ＞に、レコード順ＡＡを加算した値が、ＳＯＳ（ｉ）の位置（順位Ｏｒｄ）を示す。すなわち、ＢＢ＝ＣＬＴＶ（ｉ）＜ＶＴＰ＞＋ＡＡとすると、仮想行ＴＰに相当するレコードの、ＳＯＳ（ｉ）内の位置（順位Ｏｒｄ）は、ＢＢで表される。
【００８７】
そして、ＳＯＳ（ｉ）［ＢＢ］の要素を、レコード番号（ＲｅｃＮｏ．）として決定し（ステップＳ１３０９）、処理を終了する。
【００８８】
以下、本実施形態の第二探索処理を、図４および図７を用い、具体例で説明する。キー項目として＜Ｎａｍｅ＞、仮想行（Ｖｒｅｃ）ＴＰとして、５が指定されたものとする。
【００８９】
第二探索部４２２は、図７に示す着目項目がＮａｍｅのインデックスファイル３００にアクセスする。まず、テーブル０のＶＬ（０）にアクセスし、例えば、順位が２の「Ｊｅｍｉ」を仮探索値ｖｐに抽出する。そして、レコード数計算部４２３により、仮想統合ソートＤＢ５１０での「Ｊｅｍｉ」の順位の範囲を得る。ここでは、［６，７］と得る。
【００９０】
指定された仮想行ＴＰはこの範囲外で、より小さい値であるため、ＶＬ（０）において、仮探索値ｖｐとして、より小さい値を抽出し直す。例えば、「Ｇｒｉｚｚａ」をｖｐとする。「Ｇｒｉｚｚａ」の仮想統合ソートＤＢ５１０での順位の範囲として、同様に、［３、５］を得る。仮想行ＴＰが範囲内であるため、仮仮想値ｖｐ「Ｇｒｉｚｚａ」を、仮想行の値ＶＴＰとする。
【００９１】
次に、テーブルを決定する。ここでは、まず、テーブル０までの、「Ｇｒｉｚｚａ」の数を算出し、２を得る。また、仮想統合ソートＤＢ５１０の「Ｇｒｉｚｚａ」より小さい値の総数（ＣＡＬＴＶ＜Ｇｒｉｚｚａ＞）は３である。よって、テーブル０の「Ｇｒｉｚｚａ」の最大順位のものの、仮想統合ソートＤＢ５１０における仮想行は、４となる。
【００９２】
仮想行ＴＰと比較すると、算出された仮想行の方が小さいため、次のテーブル１に移行し、同様の処理を行う。テーブル１の「Ｇｒｉｚｚａ」の最大順位のものの、仮想統合ソートＤＢ５１０における仮想行として、５を得る。これは、仮想行ＴＰ以下の値であるため、仮想行ＴＰのレコードの所属テーブルは１と決定する。
【００９３】
最後に、レコード番号を決定する。仮想統合ソートＤＢ５１０において、テーブル１の「Ｇｒｉｚｚａ」の直前のレコードの順位として、４を得る。テーブル１内の、指定仮想行ＴＰに相当する「Ｇｒｉｚｚａ」の順位ＡＡは０となる。テーブル１内で、「Ｇｒｉｚｚａ」より小さい値のレコード数（ＣＬＴＶ＜Ｇｒｉｚｚａ＞）は２であるため、ＳＯＳ（１）の順位２の要素が、指定仮想行ＴＰの「Ｇｒｉｚｚａ」のレコード番号となる。
【００９４】
なお、本実施形態では、位置情報として、所属するテーブルのテーブルＩＤと、レコード番号とを出力するよう構成しているが、これに限られない。例えば、各テーブルのレコード数を用い、テーブルＩＤ順に全テーブルの全レコードに、連番のレコード番号（統合レコード番号）を付与し、統合レコード番号を返すよう構成してもよい。統合レコード番号は、自身のテーブルよりテーブルＩＤの小さいテーブルの総レコード数を、自身のテーブルのレコード番号に加算したものとなる。
【００９５】
なお、上記実施形態では、複数のデータベースを探索対象とする場合を例にあげて説明したが、探索対象とするデータベース数は１つであってもよい。ただし、データベース数が１つの場合、第一探索部４２１および第二探索部４２２は、当該データベースのインデックスファイル３００内のみを検索し、位置情報としてレコード番号のみを返す。
【００９６】
すなわち、単一データベースに対し、本実施形態のインデックスファイル３００を用い、所定のデータ項目と項目値とを指定することにより当該項目値を有するレコードのレコード番号を得ることができる。また、所定のデータ項目をキー項目としてソート後のデータベースの所定の行を指定することにより、当該レコードのレコード番号を得ることができる。
【００９７】
また、上記実施形態では、各情報処理装置１１０が、インデックス作成部１１０および位置情報特定部４２０を備える場合を例にあげて説明したが、これに限られない。位置情報特定部４２０は、データベースを保持する情報処理装置１１０とは独立した情報処理装置であって、データベースを保持する各情報処理装置１１０とデータの送受信が可能な情報処理装置が備えていてもよい。インデックス作成部１１０についても同様である。この場合、位置情報特定部４２０を備える情報処理装置１１０から、所望のデータベース２００およびそのインデックスファイル３００を備える情報処理装置１１０にアクセスし、上記位置情報特定部４２０による処理を実行する。
【００９８】
また、統合し、データを探索する対象のデータベースを、ユーザが選択するよう構成してもよい。ユーザが選択する場合、ユーザに選択可能なデータベースの一覧を表示し、その中から受け付けるよう構成してもよい。
【００９９】
また、本実施形態において、第一探索処理を行う対象のデータ項目２１１および項目値２１２の指定は、ユーザが行うよう構成してもよい。この場合、ユーザからデータ項目２１１および項目値２１２の指定を受け付けるユーザインタフェース画面を提供するよう構成してもよい。第二探索処理も同様に、第二探索処理を行う指定仮想行ＴＰの指示をユーザが行うよう構成してもよい。この場合、ユーザから仮想行ＴＰの指示を受け付けるユーザインタフェース画面を提供するよう構成してもよい。
【０１００】
また、本実施形態の情報処理装置１１０は、さらに、表示制御部を備えていてもよい。表示制御部は、第一探索部４２１または第二探索部４２２が特定した位置情報に従って、当該テーブルにアクセスしてレコードを抽出し、表示装置１１６の表示領域に表示する。すなわち、表示制御部は、レコード抽出機能と表示機能とを実現する。
【０１０１】
これにより、例えば、特定の項目値を指定した検索処理を実現できる。検索処理は、以下のように実現される。ユーザが指定したデータ項目２１１において、ユーザが指定した項目値２１２を有するレコードの位置情報を第一探索部４２１が特定する。第一探索部４２１が特定した位置情報に従って、表示制御部が、当該レコードを各テーブルから抽出し、表示装置１１６の表示領域に表示する。
【０１０２】
また、仮想統合ソートＤＢ５１０の閲覧処理を実現できる。閲覧処理は、以下のように実現される。ユーザが指定した仮想行ＴＰを含む所定数の仮想行それぞれのレコードの位置情報を第二探索部４２２が特定する。ここでは、図１１に示すように、表示装置１１６の表示領域に表示可能な行数（ここでは、Ｌ行）の仮想行の位置情報を特定する。第二探索部４２２が特定した位置情報に従って、表示制御部がこれらのレコードを各テーブルｉから抽出し、仮想行順に表示装置１１６の表示領域に表示させる。例えば、スクロール操作などにより、ユーザが指定する仮想行ＴＰが変更される毎にこの一連の処理を行い、表示を更新する。
【０１０３】
以上説明したように、本実施形態のデータベース２００は、特定のデータ項目２１１において項目値２１２が指定されると当該項目値２１２に属するレコードの位置情報を返し、また、仮想統合ソートＤＢ５１０の仮想行ＴＰが指定されると、当該仮想行ＴＰの位置情報を返すインデックスファイル３００を備える。そして、位置情報特定部４２０は、このインデックスファイル３００を用いてユーザが指定するレコードを探索し、その位置情報を特定する。特に、データベース２００が分散管理されていたとしても、仮想的に統合し、ソートした状態の、指定された順位のレコードの、位置情報を返すことができる。
【０１０４】
従って、本実施形態によれば、ユーザは、データベースが単一であっても、複数のデータベースに分散管理されていても、本実施形態のインデックスファイル３００により、容易に、所望のレコードを探索し、その位置情報を特定することができる。
【０１０５】
これにより、上述のように、分散管理されているデータベースであっても、容易に、全データベースの中から、所望の値を抽出する検索処理を実現できる。さらに、容易に、全データベースを仮想的に統合し、ソートした状態での閲覧処理を実現できる。また、検索処理、閲覧処理時に仮想的な統合で済み、実際に統合する必要がないため、実際に全てのデータベースをコピーし、一元管理する必要がない。このため、コピーのための時間も不要となり、かつ、一元管理のための巨大なメモリ領域を用意する必要もない。
【０１０６】
また、従来、大量データベースの検索に用いられていたＢ木等のインデックスの使用領域は、元となるデータベースのデータ量が大きくなるに従って、加速度的に増加（Ｏ（ｎｌｏｇ（ｎ））する。これに比べ、本実施形態のインデックスファイル３００のサイズは、元のデータベースのサイズに比例的（Ｏ（ｎ））である。このため、元のデータベースのサイズが膨大であっても、記憶領域を大幅に圧迫することがない。
【０１０７】
また、本実施形態のインデックスファイル３００を構成する各リスト内の要素には、いずれも順位（Ｏｒｄ）でアクセスできる。また、上記探索をインデックスファイル３００の検索のみにより実現している。このため、探索のために事前分散管理されているサイト間の通信量も抑えられる。従って、レコードの探索、抽出時に通信量が増大することがない。
【０１０８】
従って、大規模データベースであっても、また、そのデータベースが分散管理されていたとしても、大容量のデータの送受信がないため、専用の通信網を用意しなくてもよい。このため、本実施形態によれば、インターネットなどの既存のネットワークを用いて、データベースシステムを構築可能である。
【０１０９】
また、本実施形態のインデックスファイル３００は、上述のような簡易な構成であるため、データベース種を問わず、作成が可能である。このため、管理対象のデータベース種を問わず、容易に所望のデータの位置の特定および抽出が可能となる。また、検索のための事前設計も不要である。
【０１１０】
従って、本実施形態によれば、大規模なデータベースであっても、分散管理されていても、容易に、高速に、使用環境の制約もなく、汎用のハードウェア、汎用の通信網上で、小規模サイズ、ミドルサイズのデータベースと同様に取り扱うことができる。
【０１１１】
すなわち、本実施形態のインデックスファイル３００は、非常に高速な検索を実現でき、１兆レコードに及ぶデータベースを現実的に構築できる、といった大規模性を有する。さらに、本実施形態のインデックスファイル３００は、スキーマが異なるデータベース間でも通用する指標である一意のレコード番号を有するため、広域分散性を有し、互いに地球の裏側にあるようなデータベース間の連携も可能である。また、本実施形態によれば、サーバを必要としない。すなわち、クライアントのＣＰＵを用いて検索が行われる。このため、クライアント数の増加に連れて投入されるＣＰＵ数が増え、多数のクライアントを無理なく接続することができる。また、サーバレスであるため、サーバ装置及びサーバソフトが不要で低コストでデータベースシステムを構築できる。
【０１１２】
＜＜第二の実施形態＞＞
次に、本発明を適用する第二の実施形態を説明する。第一の実施形態とは、同機能ではあるが、異なるインデックスを用いる。
【０１１３】
本実施形態のデータベースシステムは、基本的に図１に示す、第一の実施形態のデータベースシステム１００と同様である。また、データベースシステム１００の各装置も同様である。ただし、上述のように、インデックスファイル３００が異なる。従って、情報処理装置１１０内の、インデックスファイル３００の構成が異なるとともに、インデックス作成部４１０および位置情報特定部４２０の処理が異なる。また、適用可能なデータベース種も異なる。以下、本実施形態について、第一の実施形態と異なる構成に主眼をおいて説明する。
【０１１４】
本実施形態の情報処理装置１１０の機能構成は、基本的に図５に示す第一の実施形態と同様に、インデックス作成部４１０と、位置情報特定部４２０とを備える。そして、位置情報特定部４２０は、第一の実施形態同様、第一探索部４２１と、第二探索部４２２と、レコード数計算部４２３とを備える。
【０１１５】
本実施形態のインデックス作成部４１０は、第一の実施形態同様、任意の時間間隔で、表形式データ２０１からインデックスファイル３００を作成する。例えば、所定量のデータが収集される毎に作成する。ただし、作成するインデックスファイル３００が異なる。
【０１１６】
本実施形態のインデックス作成部４１０が作成するインデックスファイル３００について説明する。図１２は、本実施形態のインデックスファイル３００を説明するための図である。本実施形態のインデックス作成部４１０は、分散管理される全てのテーブルについて、それぞれ、以下のインデックスファイル３００を作成する。また、本実施形態のインデックスファイル３００も、第一の実施形態同様、表形式データ２０１の各データ項目２１１に対して作成される、１以上の要素を備える配列形式の１以上のリストである。第一の実施形態同様、インデックスファイル３００を作成するデータ項目２１１を、着目項目と呼ぶ。
【０１１７】
ここでは、第一の実施形態の図２（ａ）に示す表形式データ２０１から作成されるインデックスファイル３００を例にあげて説明する。図１２（ａ）は、着目項目が＜Ｇｅｎｄｅｒ＞の、図１２（ｂ）は、着目項目が＜Ｎａｍｅ＞の、図１２（ｃ）は、着目項目が＜Ａｇｅ＞の例である。これらの図に示すように、インデックスファイル３００は、ソートリスト（ＳＯＳ）３３０と、元となるテーブルの着目項目のデータにより構成されるリスト（元データリスト：ＯＲＧ）３４０と、を備える。各リストは、要素とその位置を示す順位（Ｏｒｄ）とから構成される。各リストは、順位（Ｏｒｄ）を指定することにより、各要素を抽出することができる。また、また、リストＡＢＣの、０から始まる順位ｊの要素をＡＢＣ［ｊ］と示す。なお、ＳＯＳ３３０の構成および作成手法は第一の実施形態と同様である。
【０１１８】
また、本実施形態においても、インデックスファイル３００の各リストは、テーブル毎に作成される。図１３（ａ）および図１３（ｂ）に、着目項目が＜Ｎａｍｅ＞の場合の、インデックスファイル３００例を示す。図１３（ａ）がテーブル０のインデックスファイル３００であり、図１３（ｂ）がテーブル１のインデックスファイル３００である。
【０１１９】
次に、本実施形態で適用可能なデータベースについて説明する。本実施形態では、インデックスファイル３００として、ＳＯＳ３３０と、ＯＲＧ３４０とを用いる。このため、本実施形態では、第一の実施形態同様、構造化データ、半構造化データおよび非構造化データのいずれであってもよい。ただし、いずれの形式のデータベースであっても、各データ項目に格納する項目値は１つとする。
【０１２０】
次に、本実施形態の位置情報特定部４２０について説明する。本実施形態の位置情報特定部４２０も、第一の実施形態同様、ユーザからの指示に従って、位置情報を特定する。第一探索部４２１は、データ項目２１１と所定の項目値２１２とが指定されたことを受け、当該データ項目２１１の項目値２１２を有するレコードを探索し、位置情報を特定する。また、第二探索部４２２は、ソートキー項目とするデータ項目２１１と仮想行（Ｖｒｅｃ）とが指定されたことを受け、仮想統合ソートＤＢ５１０の、当該仮想行（Ｖｒｅｃ）のレコードを探索し、位置情報を返す。
【０１２１】
まず、第一探索部４２１による第一探索処理を説明する。本実施形態の第一探索処理も、第一の実施形態同様、指定された値を有するレコードの位置情報を探索し、特定する。本実施形態の第一探索部４２１は、探索対象のデータ項目２１１（Ｔａｒｇｅｔ  Ｉｔｅｍ：ＴＩ）と項目値２１２（Ｔａｒｇｅｔ  Ｖａｌｕｅ：ＴＶ）とを指定されると、テーブルＩＤ順にＯＲＧ３４０を探索する。探索は、２分割法等の従来の探索法を用いる。
【０１２２】
本実施形態の第一探索部４２１は、ヒットする毎に、第一探索結果格納領域に、当該レコードの順位（Ｏｒｄ）をレコード番号として、レコード番号とテーブルＩＤとを追加保存する。
【０１２３】
以下、本実施形態の第一探索処理を、図１３を用い、具体例で説明する。例えば、データ項目２１１として＜Ｎａｍｅ＞が、項目値２１２として「Ｓｉｌｌａｂｕｂ」が指定されたものとする。まず、テーブル０のＯＲＧ３４０にアクセスし、２分割法で「Ｓｉｌｌａｂｕｂ」の有無を判別する。テーブル０には、この値はないため、次にテーブル１に移る。そして、テーブル１で、同様にＯＲＧ３４０にアクセスし、順位として、１と２とを得る。これをレコード番号として、テーブルＩＤに対応づけて第一探索結果格納領域に格納し、最終的に出力する。
【０１２４】
次に、本実施形態の第二探索部４２２の第二探索処理を説明する。本実施形態の第二探索処理も、第一の実施形態同様、ユーザからキー項目とユーザからキー項目と仮想統合ソートＤＢ５１０の仮想行（Ｖｒｅｃ）とを指定されると、該当レコードの位置情報を返す。すなわち、仮想統合ソートＤＢ５１０の指定仮想行ＴＰのレコードの、テーブルＩＤとレコード番号２１４とを特定する。
【０１２５】
このとき、本実施形態では、テーブルＩＤ順に、ＯＲＧ３４０にアクセスし、所定の位置（例えば、中央付近）の値を抽出し、仮の探索値（仮探索値）とし、仮探索値の、仮想統合ソートＤＢ５１０における仮想行（仮仮想行）を得る。得られた仮仮想行と指定仮想行とを比較し、両者が一致するまで、探索を繰り返す。そして、一致した仮探索値の位置情報を算出する。
【０１２６】
従って、本実施形態の第二探索処理の流れは、基本的に第一の実施形態の図９および図１０に示す第二探索処理と同様である。ただし、ステップＳ１２０２における最初の仮探索値ｖｐの決定手法、ステップＳ１２０３で仮探索値格納領域に格納する情報、および、ステップＳ１２０６における新たな仮探索値ｖｐの決定手法が異なる。
【０１２７】
また、本実施形態では、レコード数計算部４２３による、上記第二探索処理において用いる、テーブル（ｉ）内の値ｘより小さい値に属するレコード数を示すＣＬＴＶ（ｉ）＜ｘ＞と、同ｘに等しい値に属するレコード数を示すＣＥＱＶ（ｉ）＜ｘ＞との算出法が第一の実施形態と異なる。本実施形態の第二探索処理の説明に先立ち、本実施形態のレコード数計算部４２３による上記各レコード数算出処理について説明する。
【０１２８】
本実施形態のレコード数計算部４２３は、値ｘが指定されると、ＯＲＧ（ｉ）を探索し、テーブル（ｉ）内の順位（Ｏｒｄ）を取得する。ここでは、２分割法などを用いて算出し、１つの順位（Ｏｒｄ）が指定されるまで、探索を行う。
【０１２９】
ここで、値ｘがＯＲＧ（ｉ）内で検出されない場合、当該テーブルｉのＣＬＴＶ（ｉ）＜ｘ＞およびＣＥＱＶ（ｉ）＜ｘ＞を、ともに０とする。
【０１３０】
一方、１つの順位（Ｏｒｄ）が検出されると、ＳＯＳ（ｉ）を探索し、値ｘのＳＯＳ（ｉ）内での格納範囲［ｅ１、ｅ２］を特定する。ここでは、検出された順位Ｏｒｄｘを要素に持つレコードの前後のレコードのＯＲＧ（ｉ）の要素を判別することにより決定する。
【０１３１】
このとき、ＣＬＴＶ（ｉ）＜ｘ＞は、格納範囲の最小順位の値ｅ１で得られ、ＣＥＱＶ（ｉ）＜ｘ＞は、格納範囲内の個数、すなわち、最大順位ｅ２から最小順位ｅ１を減算した値に１を足した値として得られる。
【０１３２】
なお、第二探索処理において用いる、仮想統合ＤＢ５００における、値ｘより小さい値に属するレコード数ＣＡＬＴＶ＜ｘ＞、および、値ｘに等しい値に属するレコード数ＣＡＥＱＶ＜ｘ＞の算出法は、第一の実施形態と同様である。
【０１３３】
次に、本実施形態の第二探索処理の詳細を説明する。ここでは、図９に示す、第一の実施形態の第二探索処理の処理フロー例に従って、第一の実施形態と異なる処理に主眼をおいて説明する。
【０１３４】
ステップＳ１２０２において、本実施形態では、各テーブルｉにおいて、最初の仮探索値ｖｐを以下の手順で決定する。すなわち、まず、ＳＯＳ（ｉ）にアクセスし、所定の位置（例えば、中央付近）の要素（ＥｌｅｍｅｎｔＡ）を抽出する。そして、ＯＲＧ３４０にアクセスし、要素（ＥｌｅｍｅｎｔＡ）を順位（Ｏｒｄ）に持つレコードの要素（ＶａｌｕｅＢ）を抽出し、仮探索値ｖｐとする。
【０１３５】
また、ステップＳ１２０３において、本実施形態では、仮探索値ｖｐと、ＯＲＧ（ｉ）における順位（Ｏｒｄ）と、当該仮探索値ｖｐのＳＯＳ（ｉ）での順位（Ｏｒｄ）も併せて保存する。
【０１３６】
さらに、ステップＳ１２０６において、新たな仮探索値ｖｐは、ＳＯＳ（ｉ）内で２分割法を行い、順次決定する。このとき、指定仮想行ＴＰが、仮仮想行の最小値より小さい場合、現在の仮探索値ｖｐのＳＯＳ（ｉ）での順位と、仮探索値格納領域に既に格納されている仮探索値で、現在の仮探索値ｖｐより小さい値の中の最大値のＳＯＳ（ｉ）での順位と、の間で決定する。一方、指定仮想行ＴＰが、仮仮想行の最大値より大きい場合、現在の仮探索値ｖｐのＳＯＳ（ｉ）での順位と、仮探索値格納領域に既に格納されている仮探索値で、現在の仮探索値ｖｐより大きい値の中の最小値のＳＯＳ（ｉ）での順位と、の間で決定する。
【０１３７】
以下、本実施形態の第二探索処理の具体例を、図４および図１３（ａ）、（ｂ）を用いて説明する。ここでは、キー項目として＜Ｎａｍｅ＞、仮想行（Ｖｒｅｃ）ＴＰとして、５が指定されたものとする。
【０１３８】
第二探索部４２２は、まず、図１３（ａ）に示す、テーブル０の、着目項目がＮａｍｅのインデックスファイル３００にアクセスする。そして、ＳＯＳ（０）にアクセスし、例えば、順位が３の要素０を抽出する。そして、ＯＲＧ（０）にアクセスし、順位が０の要素「Ｊｅｍｉ」を仮探索値ｖｐとして抽出する。
【０１３９】
そして、仮想統合ソートＤＢ５１０での「Ｊｅｍｉ」の順位の範囲を得る。ここでは、［６，７］と得る。仮想行ＴＰはこの範囲外で、より小さい値であるため、ＳＯＳ（０）において、仮探索値ｖｐとして、より小さい順位の値を抽出し直す。例えば、順位が１の要素１を抽出し、ＯＲＧ（０）にアクセスし、順位が１の要素「Ｇｒｉｚｚａ」を新たな仮探索値ｖｐとする。
【０１４０】
同様に、仮想統合ソートＤＢ５１０での「Ｇｒｉｚｚａ」の順位の範囲として、［３、５］を得る。仮想行ＴＰが範囲内であるため、「Ｇｒｉｚｚａ」を、仮想行の値ＶＴＰとする。
【０１４１】
次に、テーブルを決定する。ここでは、まず、テーブル０までの、「Ｇｒｉｚｚａ」の数を算出し（ＣＡＬＴＶ＜Ｇｒｉｚｚａ＞）、２を得る。また、仮想統合ソートＤＢ５１０の「Ｇｒｉｚｚａ」より小さい値の総数（ＣＡＬＴＶ＜Ｇｒｉｚｚａ＞）は３である。よって、テーブル０の「Ｇｒｉｚｚａ」の最大順位のものの、仮想統合ソートＤＢ５１０における仮想行は、４となる。
【０１４２】
仮想行ＴＰと比較すると、算出された仮想行の方が小さいため、次のテーブル１に移行し、同様の処理を行う。テーブル１の「Ｇｒｉｚｚａ」の最大順位のものの、仮想統合ソートＤＢ５１０における仮想行として、５を得る。これは、仮想行ＴＰ以下の値であるため、仮想行ＴＰのレコードの所属テーブルは１と決定する。
【０１４３】
最後に、レコード番号を決定する。仮想統合ソートＤＢ５１０において、テーブル１の「Ｇｒｉｚｚａ」の直前のレコードの順位として、４を得る。テーブル１内の、指定仮想行ＴＰに相当する「Ｇｒｉｚｚａ」の順位ＡＡとして、０を得る。テーブル１内で、「Ｇｒｉｚｚａ」より小さい値のレコード数（ＣＬＴＶ＜Ｇｒｉｚｚａ＞）は２であるため、ＳＯＳ（１）の順位２の要素が、指定仮想行ＴＰの「Ｇｒｉｚｚａ」のレコード番号となる。
【０１４４】
なお、本実施形態においても、上記実施形態では、複数のデータベースを探索対象とする場合を例にあげて説明したが、探索対象とするデータベース数は１つであってもよい。また、位置情報特定部４２０が、データベースを保持する情報処理装置１１０とは独立した情報処理装置に構築されていてもよい。さらに、第一の実施形態と同様の表示制御部を備え、検索処理、閲覧処理等を実現可能なよう構成してもよい。また、ユーザが特定対象、抽出対象とする項目値、仮想行を指定可能なインタフェース、ユーザが検索対象とするデータベースを選択可能なインタフェースを備えていてもよい。
【０１４５】
以上説明したように、本実施形態においても、第一の実施形態と同様の効果を得ることができる。
【０１４６】
なお、上記インデックスファイル３００の構成は、上記各実施形態の構成に限られない。すなわち、元のデータベースから作成され、元のデータベースのサイズとサイズが比例的であり、かつ、所定のデータ項目と値とが与えられると、それを満たすレコードの位置情報を返すことができ、かつ、仮想的に統合し、所定のデータ項目でソートされた状態の指定された順位のレコードの、位置情報を返すことができるインデックスファイルであれば、その構成は問わない。例えば、所定の項目値の個数（０も含む）を判別可能な第一のリストと、所定のデータ項目でソート後の各レコードの順位を把握可能な第二のリストの組合せであってもよい。
【符号の説明】
【０１４７】
１００：データベースシステム、１１０：インデックス作成部、１１０：情報処理装置、１１１：ＣＰＵ、１１２：メモリ、１１３：記憶装置、１１４：ＮＷＩＦ、１１５：入力装置、１１６：表示装置、１１７：外部記憶装置、１２０：ネットワーク、２００：データベース、２０１：表形式データ、２０１ｓ：ソート後の表形式データ、２０２：半構造化データ、２０３：半構造化データ、２０３：非構造化データ、２０４：非構造化データ、２１１：データ項目、２１２：項目値、２１３：レコード、２１４：レコード番号、２１５：レコード順序番号、３００：インデックスファイル、３１０：ＶＬ、３２０：ＣＡＧＲ、３３０：ＳＯＳ、３４０：ＯＲＧ、４１０：インデックス作成部、４２０：位置情報特定部、４２１：第一探索部、４２２：第二探索部、４２３：レコード数計算部、５００：仮想統合ＤＢ、５０１：テーブルＩＤとレコード番号、５１０：仮想統合ソートＤＢ
【図１】
2015207026.tif 000011
【図２】
2015207026.tif 000012
【図３】
2015207026.tif 000013
【図４】
2015207026.tif 000014
【図５】
2015207026.tif 000015
【図６】
2015207026.tif 000016
【図７】
2015207026.tif 000017
【図８】
2015207026.tif 000018
【図９】
2015207026.tif 000019
【図１０】
2015207026.tif 000020
【図１１】
2015207026.tif 000021
【図１２】
2015207026.tif 000022
【図１３】
2015207026.tif 000023