(57)【要約】【課題】検索時間を短縮することのできる検索装置を提供する。【解決手段】オブジェクト指向データベースにおける問い合わせによって、母集合から特定の条件を満たす部分集合を取り出す場合、ナビゲーションによって与えられる問い合わせ式を、問い合わせ式の最後の条件式から、先頭に向かって順次ナビゲーションを解決することにより答えを得る。【選択図】　　　図２
2004078631.tif 000002
【特許請求の範囲】
【請求項１】
情報処理装置にオブジェクト指向データベースにおける検索方法を実現させるプログラムであって、
該オブジェクト指向データベースに対する問い合わせを入力する問い合わせ入力ステップと、
該問い合わせに記述されるナビゲーションを解析する問い合わせ解析ステップと、
該ナビゲーションの記述の最後の条件式を評価し、該ナビゲーションの記述を最後の条件式から、記述と逆方向に解決するナビゲーション逆順解決ステップと、
該ナビゲーションの記述を逆方向に解決した結果を収集する結果収集ステップと
を備えることを特徴とする検索方法を情報処理装置に実現させるプログラム。
【請求項２】
前記ナビゲーションの記述の最後の条件式は、クラスのインスタンスの値を具体的に指定する記述であることを特徴とする請求項１に記載のプログラム。
【請求項３】
前記検索方法は、ユーザが前記オブジェクト指向データベースにおいて、インスタンス間のリンクを定義した場合、該ユーザが指定したリンクと逆方向のリンクを自動的に生成することを特徴とする請求項１に記載のプログラム。
【請求項４】
インスタンス間のリンクを前記ナビゲーションの記述と逆方向に辿る場合、インスタンス間のリンクに該ナビゲーションに記載されていないリンクがあっても、当該記述されていないリンクを辿らないことを特徴とする請求項３に記載のプログラム。
【請求項５】
前記問い合わせは、前記ナビゲーションの先頭に記載されるクラスに属するインスタンスの母集合から、該ナビゲーションの最後の条件式を満たす部分集合を抽出する問い合わせであることを特徴とする請求項１に記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、オブジェクト指向データベース上において、所定のデータの集合を検索するための問い合わせを行う検索装置に関する。
【０００２】
【従来の技術】
オブジェクト指向データベースにおいては、各データは、各オブジェクトとして格納されている。各オブジェクトは、各クラスに所属し、各クラスで定義された属性を有する。例えば、「人間」というクラスに属性として「氏名」が設定された場合、「人間」というクラスには、様々な人の氏名が属性として格納される。また、オブジェクト指向データベースにおいては、各オブジェクト間の関係付けを行うことができ、「人間」というクラスを継承する「性別」というクラスでは、「人間」というクラスの属性値それぞれから「性別」というクラスの属性値である「男」あるいは「女」が関連付けられる。
【０００３】
このように、オブジェクト指向データベースでは、オブジェクトとして格納される各データを各クラス毎に分けて格納し、互いに継承と言う形で関連付けるようにする。ここで、例えば、オブジェクト指向データベースのユーザが、「人間」というクラスに登録されている各「氏名」の内、女性の人だけを取り出したいとする。オブジェクト指向データベースにおいては、特定の属性値を持つ集合を取り出す場合、オブジェクト名を連結して式として記述して、条件を設定し、システムにデータの取得を依頼する。この取り出したい集合を条件付ける、オブジェクト名を連結した形式を持つ条件式をナビゲーションと呼ぶ。
【０００４】
オブジェクト指向データベースに対する問い合わせの中でも、指定条件に該当するオブジェクトを母集合の中から検索する場合、母集合を検索の対象として、その要素一つ一つから順にナビゲーションをたどり、最終ナビゲート先オブジェクトが指定条件に一致するかどうかを確認して、問い合わせに対する結果集合を生成していた。
【０００５】
図１８は、オブジェクト指向データベースのクラスと属性とそれらの関係を説明する図である。
図１８に示されるように、ｃｌａｓｓＡがあり、ｃｌａｓｓＡには、オブジェクトａ１からａ５が設定されている。各属性にはオブジェクトが設定される。また、各オブジェクトａ１からａ５からは、ｃｌａｓｓＢへの接続関係であるｌｉｎｋＢが設けられている。図１８の場合にはもっとも単純な接続関係が記述されている。ｃｌａｓｓＡのオブジェクトａ１はｃｌａｓｓＢのオブジェクトｂ１にリンクが張られている。同様に、ｃｌａｓｓＡからｃｌａｓｓＥまで各リンクｌｉｎｋＢ〜ｌｉｎｋＥが張られている。
【０００６】
ｃｌａｓｓＥのオブジェクトｅ１からｅ５には、ｐｒｏｐｅｒｔｙという属性が設定されている。ここで、ｃｌａｓｓＥの属性ｐｒｏｐｅｒｔｙに“ｇｈｉ”と関連付けられているｃｌａｓｓＡのオブジェクトの集合をｃｌａｓｓＡのオブジェクトの全体集合から抜き出すような処理をする場合には、下記のような問い合わせ式、あるいは条件式を用いてデータベースを検索する。
ｃｌａｓｓＡ．ｌｉｎｋＢ．ｌｉｎｋＣ．ｌｉｎｋＤ．ｌｉｎｋＥ．ｐｒｏｐｅｒｔｙ＝＝”ｇｈｉ”　・・・・（１）
この式のように、クラス間のリンク関係を記述した式がナビゲーションと呼ばれる。このナビゲーションに従って、データベースを検索することにより、ｃｌａｓｓＡのオブジェクトの内、ｃｌａｓｓＥのｐｒｏｐｅｒｔｙとして”ｇｈｉ”をもつオブジェクトと関連付けられたｃｌａｓｓＡのオブジェクトの部分集合が得られる。
【０００７】
【発明が解決しようとする課題】
従来の技術において、上記のような問い合わせをする場合、ナビゲーションを順にたどっていかなければならないため、問い合わせの母集合の要素一つ一つに対してナビゲーションを順に辿り、最終ナビゲート先オブジェクトを見つけ、問い合わせ条件に一致しているかどうかを調べなければならない。問い合わせの対象となる母集合の要素が多く、かつ、問い合わせ条件に一致するオブジェクト数が母集合に対してはるかに少ない場合、最終ナビゲート先オブジェクトまでたどるナビゲーションの解決にかけた時間は無駄になり、問い合わせの対象となる母集合の要素が多い場合、ナビゲーションにかかる処理時間は無視できないものになる。
【０００８】
図１９は、従来のナビゲーションの解決方法を説明する図である。
まず、ｃｌａｓｓＡにおいて、ａ１からａ５までのオブジェクトが設定されているとする。すると、上記ナビゲーション（１）が問い合わせ式として与えられた場合、まず、ｃｌａｓｓＡとｃｌａｓｓＢが関連付けられているので、ｃｌａｓｓＡの各オブジェクトからｃｌａｓｓＢの各オブジェクトへとリンクを辿っていく。これにより、ａ１とｂ１、ａ２とｂ２、ａ３とｂ３、ａ４とｂ４、ａ５とｂ５の組が取り出される。次に、ｃｌａｓｓＢとｃｌａｓｓＣが関連付けられているので、ｌｉｎｋＢを辿った結果のそれぞれからｌｉｎｋＣを辿っていく。これにより、ａ１とｃ１、ａ２とｃ２、ａ３とｃ３、ａ４とｃ４、ａ５とｃ５の関係が見つけられる。同様にして、ｌｉｎｋＤ、ｌｉｎｋＥとたどり、ａ１とｅ１、ａ２とｅ２、ａ３とｅ３、ａ４とｅ４、ａ５とｅ５の組が取り出される。そこで、条件式は、ｃｌａｓｓＥのオブジェクトであるｐｒｏｐｅｒｔｙの属性が”ｇｈｉ”となっているｃｌａｓｓＡのオブジェクトを探すことであるので、図１８を参照すると、ｃｌａｓｓＥのｅ３が選択され、したがって、これと組をなすａ３が求める答えとして得られる。
【０００９】
図２０は、従来の技術におけるナビゲーションの解決の方向を示す図である。
図２０に示し、また、図１９において説明したように、式（１）で与えられたナビゲーションを解決するためにシステムが行うナビゲーションの解決の方向は、ｃｌａｓｓＡから、式（１）で与えられた順番にｃｌａｓｓのオブジェクトを辿り、最後のオブジェクトの属性が設定された条件に合致するか否かを判断することにより、対応するｃｌａｓｓＡのオブジェクトは条件を満たすものかどうかを判断する。すなわち、ｃｌａｓｓＡの全てのオブジェクトについて処理を行わなければならず、ｃｌａｓｓＡのすべてのオブジェクトに接続されているナビゲーションに記載されたｃｌａｓｓの接続関係を全て辿らなければならない。
【００１０】
図２１は、従来の技術を説明する別の例である。
この場合、ナビゲーションが以下の式で与えられるとする。
ｃｌａｓｓＡ．ｌｉｎｋＢ．ｌｉｎｋＣ．ｐｒｏｐｅｒｔｙ＝＝”ｇｈｉ”　　　（２）
この場合、ｃｌａｓｓＡには、ａ１〜ａ８までのオブジェクトが定義されており、ｌｉｎｋＢを辿ると、ｃｌａｓｓＡの２つのオブジェクトとｃｌａｓｓＢの１つのオブジェクトが関連付けられている。すなわち、ａ１、ａ２とｂ２、ａ３、ａ４とｂ４、ａ５、ａ６とｂ６、ａ７、ａ８とｂ８が関連付けられている。同様に、ｌｉｎｋＣを辿ると、ｂ１、ｂ３とｃ３、ｂ２、ｂ４とｃ４、ｂ５、ｂ７とｃ７、ｂ６、ｂ８とｃ８が関連付けられている。
【００１１】
図２２は、図２１の場合のナビゲーションの従来の解決方法の例である。
図２２に示されるように、ｌｉｎｋＢとｌｉｎｋＣを辿って、ｃｌａｓｓＡのオブジェクトとｃｌａｓｓＣのオブジェクトとの関係を得ると、ｃｌａｓｓＣのオブジェクトの属性が”ｇｈｉ”となっているオブジェクトｃ４を取り出す（図２１参照）。そして、ｃ４と関連しているａ１〜ａ４が求めるべき集合となる。
【００１２】
図２３は、図２１の例の場合のリンクを辿る回数を示す図である。
ｌｉｎｋＢにおいては、ｃｌａｓｓＡの各オブジェクトからｃｌａｓｓＢの各オブジェクトに対し、各オブジェクトに１個のリンクが張られているため、リンクを辿る動作は各オブジェクトについて１回でよい。しかし、ｃｌａｓｓＢからｃｌａｓｓＣのｌｉｎｋＣにおいては、ｂ２には、ａ１とａ２からの２つのリンクが張られているので、ｂ２からリンクを辿る動作は２回しなければならない。同様に、ｂ４、ｂ６、ｂ８についても２回ずつリンクを辿る動作をしなければならない。従って、たとえリンクがクラスを辿って行くにつれ、集約されていっても、ナビゲーションを解決するために必要なリンクを辿る動作は減少しないという傾向がある。
【００１３】
従って、ｃｌａｓｓＡのオブジェクト数（母集合の要素数）が多い場合、全てのオブジェクトについてリンクを辿る動作をしなければならないので、求めようとする結果を得るまでに時間がかかってしまう。
【００１４】
本発明の課題は、検索時間を短縮することのできる検索装置を提供することである。
【００１５】
【課題を解決するための手段】
本発明の検索装置は、オブジェクト指向データベースにおける検索装置であって、該オブジェクト指向データベースに対する問い合わせを入力する問い合わせ入力手段と、該問い合わせに記述されるナビゲーションを解析する問い合わせ解析手段と、該ナビゲーションの記述の最後の条件式を評価し、該ナビゲーションの記述を最後の条件式から、記述と逆方向に解決するナビゲーション逆順解決手段と、該ナビゲーションの記述を逆方向に解決した結果を収集する結果収集手段とを備えることを特徴とする。
【００１６】
検索方法は、オブジェクト指向データベースにおける検索方法であって、該オブジェクト指向データベースに対する問い合わせを入力する問い合わせ入力ステップと、該問い合わせに記述されるナビゲーションを解析する問い合わせ解析ステップと、該ナビゲーションの記述の最後の条件式を評価し、該ナビゲーションの記述を最後の条件式から、記述と逆方向に解決するナビゲーション逆順解決ステップと、該ナビゲーションの記述を逆方向に解決した結果を収集する結果収集ステップとを備えることを特徴とする。
【００１７】
本発明によれば、要素数の大きな母集合から所定の条件を満たす部分集合を抽出する問い合わせを、オブジェクト指向データベースにおいて行う場合、問い合わせの記述に用いられるナビゲーションを、その最終の記述から逆順に解決するので、所定の結果を得るまでに辿るリンクの数を少なくすることができる。従って、データベースシステムの動作を高速化することができる。
【００１８】
【発明の実施の形態】
本発明においては、ナビゲーションに対して各々逆リンクを設定しておく。最終ナビゲート先のオブジェクトが所属するクラスを対象として、問い合わせ条件に一致するかどうかを調べて、最初に、問い合わせ条件に一致する最終ナビゲート先オブジェクトの集合を求める。求めた集合の要素から逆リンクをたどってナビゲーションを逆順に解決することにより、問い合わせの母集合から結果集合を取り出すことができる。
【００１９】
しかし、問い合わせの母集合に対して、問い合わせ条件に一致する最終ナビゲート先オブジェクトがほぼ母集合の要素数と同数である場合、ナビゲーションを逆にたどることによるメリットがなくなる。
【００２０】
このため、ナビゲーションを逆順にたどって問い合わせを実行する本発明を適用するかどうかを、問い合わせ毎に利用者に指定させることとする。
式（３）が、与えられた問い合わせ条件式とする。
ｓｅｌｅｃｔ　ｃｌａｓｓＡ　ｆｒｏｍ　ｃｌａｓｓＡ
ｗｈｅｒｅ　ｃｌａｓｓＡ．ｌｉｎｋＢ．ｌｉｎｋＣ．ｌｉｎｋＤ．ｌｉｎｋＥ．ｐｒｏｐｅｒｔｙ＝＝”ｇｈｉ”　　　　（３）
ここで、ｃｌａｓｓＡは問い合わせの対象となるクラスで、このクラスに属するインスタンス（属性）が、この問い合わせ式の母集合となる。ｌｉｎｋＢ，ｌｉｎｋＣ，　ｌｉｎｋＤ，　ｌｉｎｋＥはナビゲーションの一つ一つを表しており、ｐｒｏｐｅｒｔｙが最終ナビゲート先となる。このとき、ｃｌａｓｓＡ、ｃｌａｓｓＢ、ｃｌａｓｓＣ、ｃｌａｓｓＤ、ｃｌａｓｓＥの関係は、前述の図１８に示す通りである。
【００２１】
楕円はクラスを表し、長方形がインスタンスを表し、矢印がナビゲーションを表している。
各クラスの関係が図１８である場合、ｃｌａｓｓＡに属するインスタンスの一つ一つを対象として、ｌｉｎｋＢ、ｌｉｎｋＣ、ｌｉｎｋＤ、ｌｉｎｋＥのナビゲーションを逆順に解決していく概念図を図１に示す。
【００２２】
図１は、本発明の実施形態に従った検索方法の原理説明図である。
この場合、まず、ｃｌａｓｓＥのインスタンス（属性）が”ｇｈｉ”となっているオブジェクトｅ３を取り出す。そして、式（３）に左から記載されているナビゲーションを同式の右から順に辿っていく。すると、ｃｌａｓｓＥからｃｌａｓｓＤに辿ることにより、ｄ３が選択される。ｃｌａｓｓＤからｃｌａｓｓＣを辿ることにより、ｃ３が選択される。同様に、ｃｌａｓｓＣからｃｌａｓｓＢを辿ることにより、ｂ３が選択され、ｃｌａｓｓＢからｃｌａｓｓＡに辿ることにより、求める答えであるａ３が得られる。
【００２３】
図２は、本発明の実施形態に従ったナビゲーション逆順に辿る方法の概念図である。
同図に示されるように、ユーザがｃｌａｓｓＡからｃｌａｓｓＢ、ｃｌａｓｓＢからｃｌａｓｓＣ、ｃｌａｓｓＣからｃｌａｓｓＤ、ｃｌａｓｓＤからｃｌａｓｓＥにリンクを張った場合、システムは、自動的に逆方向のリンクを張り、ｃｌａｓｓＥからｃｌａｓｓＡに向かってリンクを辿ることができるようにする。
【００２４】
また、ｃｌａｓｓＡ、ｃｌａｓｓＢ、ｃｌａｓｓＣ、ｃｌａｓｓＤ、ｃｌａｓｓＥの関係として図２１に示す関係を考える。
各クラスの関係が図２１である場合、本発明の実施形態により、逆リンクを使ってナビゲーションを逆順に解決していく概念図を図３に示す。
【００２５】
図３は、本発明の実施形態に従った検索方法の別の例を示す図である。
ナビゲーションを順にたどるよりも、逆リンクを使って逆順にたどる方が問い合わせを最適に行える理由について説明する。従来の方法でナビゲーションを順にたどる場合、クラス関係が図１８で式（３）が与えられるとすると、図１９に示したような概念図で表されるが、ｃｌａｓｓＡからｃｌａｓｓＢへたどるのに５つ（ｃｌａｓｓＡのインスタンス数）のナビゲーションを解決する必要がある。ｃｌａｓｓＢからｃｌａｓｓＣへ辿るにも同様に５つのナビゲーションを解決する必要があり、最後のｃｌａｓｓＤからｃｌａｓｓＥへのナビゲーションもすべて辿ってみなければｐｒｏｐｅｒｔｙの値が分からないために同様に５つのナビゲーションを解決する必要があり、最終的な集合を得るまでに、以下の時間がかかることが分かる。
ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＋ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＋ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＋ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）
＝ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＊４
ここで、ｌｉｎｋ（）は一つのナビゲーション解決するのにかかる時間を表し、ｎｕｍ（）は、集合の要素数を表す関数とする。
【００２６】
これに対して、逆リンクを使ってナビゲーションを逆順に解決する場合、最終的な集合を得るまでに、以下の時間がかかることが分かる。
ｌｉｎｋ（）＋ｌｉｎｋ（）＋ｌｉｎｋ（）＋ｌｉｎｋ（）＝ｌｉｎｋ（）＊４
となり、ナビゲーションを逆順にたどる方が最適に処理できることは明らかである。
【００２７】
同様に、クラス関係が図２１であった場合、式（３）があたえられたとすると、従来の場合は、図２２で示したような概念図で表されるが、このとき、従来の方法でナビゲーションを順に解決すると、最終的な集合を得るまでに以下の時間がかかることが分かる。
ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＋ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＝ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＊２
これに対して、逆リンクを使ってナビゲーションを逆順にたどって解決する場合、最終的な集合をえるまでに、以下の時間がかかることが分かる。
ｌｉｎｋ（）＊２＋ｌｉｎｋ（）＊４＝ｌｉｎｋ（）＊６　＜ｌｉｎｋ（）＊ｎｕｍ（ｃｌａｓｓＡ）＊２
となり、この場合もナビゲーションを逆順にたどる方が最適に処理できることは明らかである。この概念図を図４に示す。
【００２８】
図４は、本発明の実施形態の処理概念を示す別の例の図である。
同図においては、太い矢印が解決するナビゲーションであり、ナビゲーションが式（２）で与えられた場合である。まず、本発明の実施形態においては、ナビゲーションを逆順に辿るので、ｃｌａｓｓＣのｐｒｏｐｅｒｔｙの値が”ｇｈｉ”であるオブジェクトｃ４を取り出す。そして、ｃ４からナビゲーションを逆順に辿ると、次に、ｃｌａｓｓＢのｂ２とｂ４に至る。更に、ナビゲーションを逆順に辿ると、ｃｌａｓｓＢのｂ２とｂ４から、ｃｌａｓｓＡのａ１、ａ２、ａ３、ａ４に至る。従って、求める答えは、ａ１〜ａ４ということになる。
【００２９】
従って、問い合わせ母集合に対して、指定条件に一致する最終ナビゲート先のオブジェクト数がはるかに少ない場合、逆リンクを使ってナビゲーションを逆順に解決した方が問い合わせの最適化が実現できる。
【００３０】
図５は、本発明の実施形態に従った、ナビゲーションの解決を行う処理のフローチャートである。
まず、ステップＳ１において、ユーザが条件式を入力する。本発明の実施形態に従った装置あるいはシステムは、ステップＳ２において、条件式の解析をし、ステップＳ３において、ナビゲーションを解析する。そして、ステップＳ４において、ユーザがナビゲーションの逆順解決の指定を行ったか否かを判断する。ユーザがナビゲーションの逆順解決を指定していない場合には、ステップＳ５に進んで、従来のナビゲーションの解決方法と同じ方法によって、ユーザの問い合わせに対する応答を作成する。このステップＳ５の処理は、従来の処理であるので、説明を省略する。
【００３１】
ステップＳ４において、ユーザがナビゲーションの逆順解決を指定していた場合には、ステップＳ６において、ナビゲーションの最後に記述されている最終条件と一致するオブジェクトを、ナビゲーションの最後に記載されているクラスから選択する。そして、ステップＳ７において、ナビゲーションの記述の最後の方から純に前に向かって、逆順のリンクを解決する処理を行う。ここで、逆順のリンクを解決する場合、逆順のリンクが、あるオブジェクトから２つ以上のオブジェクトに張られている場合があるが、ユーザが入力したナビゲーションに記述されているリンク以外のリンクは辿らないようにする。そして、ステップＳ９において、最終的な結果集合を作成し、処理を終了する。
【００３２】
図６は、本発明の実施形態に従ったシステムが、ユーザの設定したリンクとは逆方向のリンクを自動的に作成する処理のフローチャートである。
ステップＳ１５において、ユーザがリンク属性を宣言する。ステップＳ１６において、逆順リンク用の属性をリンク先のクラスに作成する。ステップＳ１７において、ユーザがリンク属性のオブジェクトを指定し、ステップＳ１８において、逆リンクを生成する。
【００３３】
ここで、ユーザがリンク属性を宣言する場合のユーザの定義画面の例を図７に示す。また、ステップＳ１６のユーザの定義に従って、システムが自動的に逆順リンク用の属性をクラス情報に生成した状態の例を図８に示す。更に、ユーザがリンク属性にオブジェクトを指定する例及びシステムが格納しているデータに逆リンクを設定する例を図９に示す。
【００３４】
図７は、本発明の実施形態に従った、クラス定義画面の例を示す図である。
図７においては、ユーザが入力する値として、クラス名、属性の型、属性の名前が設定されている。図７（ａ）では、クラス名として”ｃｌａｓｓＡ”、属性の型として、”ｃｌａｓｓＢ”、属性の名前として”ｌｉｎｋＢ”が設定されている。これにより、ｃｌａｓｓＡからｃｌａｓｓＢへのｌｉｎｋＢが設定される。
【００３５】
また、図７（ｂ）のように、クラス名として”ｃｌａｓｓＢ”、属性の型として”ｃｌａｓｓＣ”、属性の名前として”ｌｉｎｋＣ”が設定されている。これにより、ｃｌａｓｓＢからｃｌａｓｓＣに対してｌｉｎｋＣが設定される。
【００３６】
図７（ｃ）では、クラス名として”ｃｌａｓｓＣ”、属性の型として”Ｓｔｒｉｎｇ”、属性の名前としてｐｒｏｐｅｒｔｙが設定されている。従って、ｃｌａｓｓＣのｐｒｏｐｅｒｔｙには、”Ｓｔｒｉｎｇ”すなわち、文字列が設定されることが定義されている。
【００３７】
図８は、クラス定義によるクラステーブルの作成例を示した図である。
図８（ａ）は、図７（ａ）のユーザ定義に従って生成されるクラステーブルである。図８（ａ）においては、クラス名”ｃｌａｓｓＡ”の属性定義として、型が”ＯＩＤ”、名前が”ｏｉｄ”の属性が設定されている。これは、ｃｌａｓｓＡに属するオブジェクトのＩＤである。次の属性として、型が”ｃｌａｓｓＢ”、名前が”ｌｉｎｋＢ”の属性が設定されている。これによりｃｌａｓｓＡからｃｌａｓｓＢへのｌｉｎｋＢが設定されている。
【００３８】
図８（ｂ）は、図７（ｂ）のユーザ定義に従って生成されるクラステーブルである。図８（ｂ）においては、クラス名”ｃｌａｓｓＢ”の属性定義として、ｃｌａｓｓＢのオブジェクトＩＤとｃｌａｓｓＢからｃｌａｓｓＣへのｌｉｎｋＣが設定される。更に、当該システムは、ｃｌａｓｓＡからｃｌａｓｓＢへのｌｉｎｋＢが張られたことに伴い、ｌｉｎｋＢの逆リンク”ｒｅｖｅｒｓｅ
ｔｏ　ｌｉｎｋＡが属性の型を”ｃｌａｓｓＡ”として自動的に設定する。
【００３９】
また、図８（ｃ）は、図７（ｃ）のユーザ定義に従って生成されるクラステーブルである。図８（ｃ）においては、クラス名”ｃｌａｓｓＣ”の属性定義として、ｃｌａｓｓＣのオブジェクトＩＤがシステムにより設定されると共に、ユーザが設定した、属性の型”Ｓｔｒｉｎｇ”、属性の名前”ｐｒｏｐｅｒｔｙ”という属性が設定される。更に、当該システムは、属性の型”ｃｌａｓｓＢ”、属性の名前”ｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＢ”というｌｉｎｋＣの逆リンクを自動生成する。
【００４０】
図９は、リンク属性のオブジェクト設定と格納されたデータ構造の例である。
図９において、左側に図示された２つの画面例は、ユーザのオブジェクトへのリンクの設定画面例であり、右側に図示された２つの図は、ユーザの設定によりメモリに格納されたデータ構造の例を示す図である。
【００４１】
ユーザがオブジェクトへリンクを設定する場合には、まず、図９左上の画面が表示される。この画面には、ユーザがリンク属性を設定するオブジェクトのＩＤであるａ１が示され、リンクの属性名として”ｌｉｎｋＢ”が示されている。ここで、ユーザがリンク属性を設定する前は、”ｌｉｎｋＢ”の属性値は指定されていない。この時点でのデータ構造は、右上の図に記載されているとおりである。つまり、ｃｌａｓｓＡのデータには、オブジェクトＩＤ（前述の属性であって型がＯＩＤ、名前がｏｉｄの属性値）として”ａ１”が設定され、”ｌｉｎｋＢ”には、何も設定されていない。また、ｃｌａｓｓＢのデータには、オブジェクトＩＤ（型がＯＩＤ、名前がｏｉｄの属性値）として、”ｂ１”が設定され、”ｌｉｎｋＣ”と”ｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＡ”には何も設定されていない。
【００４２】
次に、ユーザがリンク属性をオブジェクトに設定した後は、図９の左下の画面のように、ユーザの指定により、”ｌｉｎｋＢ”の属性値として”ｂ１”が設定されている。この場合のデータは、図９の右下の図のように、ｃｌａｓｓＡのオブジェクトＩＤが”ａ１”の属性”ｌｉｎｋＢ”の属性値として”ｂ１”が設定される。また、このとき、ｃｌａｓｓＡのオブジェクト”ａ１”からｃｌａｓｓＢのオブジェクト”ｂ１”にリンクが張られる。このリンクが”ｌｉｎｋＢ”である。また、ｌｉｎｋＢはユーザによって張られるが、システムは、ｌｉｎｋＢが張られてことに対応して、ｃｌａｓｓＢのオブジェクト”ｂ１”からｃｌａｓｓＡのオブジェクト”ａ１”に対し、逆リンク”ｒｅｖｅｒｓｅｔｏ　ｌｉｎｋＡ”を生成する。このデータフィールドには、ｃｌａｓｓＡのオブジェクト”ａ１”のオブジェクトＩＤが設定される。これにより、オブジェクト”ａ１”からオブジェクト”ｂ１”へのリンクがユーザに張られると共に、システムによって、オブジェクト”ｂ１”からオブジェクト”ａ１”へのリンクが張られる。
【００４３】
図１０は、図７から図９の図に基づいてシステムが逆リンクを生成する場合に行う処理の流れを説明するフローチャートである。
まず、ステップＳ２０において、図７のように、ユーザがクラスの定義を宣言し、クラス名及び属性の型と名前を指定する。ステップＳ２１において、ユーザの入力した定義に従い、クラスの情報を格納するテーブルを作成する。図８がその作成例である。クラス情報は、クラス名と属性情報からなる。ユーザが定義した属性に加え、オブジェクトを一意に識別するためのオブジェクトＩＤ（ＯＩＤ）と、逆順リンク用の属性をシステムで定義する。
【００４４】
ステップＳ２２において、ユーザがリンク属性のオブジェクトを指定する例が図９に示されている。図９の図の見方は前述したとおりである。図９においては、ａ１、ｂ１というオブジェクトが既に存在しているものとしている。ａ１はｃｌａｓｓＡのオブジェクトであり、ｂ１はｃｌａｓｓＢのオブジェクトである。それぞれ、クラス定義にしたがって、ａ１は、ｏｉｄとして”ａ１”を有し、更に、属性としてｌｉｎｋＢを有している。また、ｂ１は、ｏｉｄとして”ｂ１”を有し、更に、属性としてｌｉｎｋＣとｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＡという属性を持つ。ステップＳ２４において、ａ１の属性ｌｉｎｋＢに”ｂ１”を設定すると、システムは、図８のテーブルから、ｃｌａｓｓＢにはｃｌａｓｓＡへの逆順リンク属性を持っていることが分かるため、ａ１の属性ｌｉｎｋＢに”ｂ１”を設定するのと同時に、ｂ１の逆順リンク属性ｒｅｖｅｒｓｅ　ｔｏ　ｃｌａｓｓＡに”ａ１”を設定して、逆リンクを生成する。
【００４５】
図１１は、ユーザが検索条件式を入力する入力指定画面の一例を示す図である。
図１１においては、検索対象として「ｃｌａｓｓＡ」が指定され、検索条件としては、「ｃｌａｓｓＡ．ｌｉｎｋＢ．ｌｉｎｋＣ．ｐｒｏｐｅｒｔｙ＝＝”富士通”」が入力されている。これがナビゲーションである。また、２つめの検索条件も入力可能になっているが、ここの例では何も入れられていない。検索条件１と検索条件２とを両方用いて検索を行う場合には、両検索条件のａｎｄをとるかｏｒをとるかのいずれかが選択可能となっている。また、検索に際し、本発明の実施形態に従った逆順検索を行うか行わないかを指定できるようになっている。そして、ユーザが検索条件の入力を終了した後、検索開始ボタンを押すと、システムが検索を始める。
【００４６】
図１２〜図１４は、本発明の実施形態に従ったナビゲーションの逆順解決処理を具体例を挙げて説明する図である。
図１２は、クラス情報のテーブルのデータ例を示した図である。図１２〜図１４の例では、図１２のクラスが既に定義されているものとする。ｃｌａｓｓＡは、属性の型がＯＩＤ（オブジェクトのＩＤの型）であり、属性の名前がｏｉｄの属性と、属性の型がｃｌａｓｓＢ（ｃｌａｓｓＢのインスタンスのオブジェクトＩＤの型を設定している）で、名前がｌｉｎｋＢの属性が１つのインスタンスを構成することが定義されている。同様に、ｃｌａｓｓＢには、型がＯＩＤ、名前がｏｉｄの属性と、型がｃｌａｓｓＣで、名前がｌｉｎｋＣの属性と、型がｃｌａｓｓＡで、名前がｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＡの属性が１つのインスタンスを構成することが設定されている。ｃｌａｓｓＣには、型がＯＩＤ、名前がｏｉｄの属性と、型がＳｔｒｉｎｇで、名前がｐｒｏｐｅｒｔｙの属性と、型がｃｌａｓｓＢで、名前がｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＢの属性がインスタンスを構成することが設定されている。
【００４７】
図１３においては、具体的に、ｏｉｄが”ａ１”、”ａ２”、”ａ３”のｃｌａｓｓＡのインスタンスが示されており、これらのインスタンスの属性ｌｉｎｋＢには、それぞれ、ｃｌａｓｓＢのリンク先のオブジェクトのＩＤである、”ｂ１”、”ｂ２”、”ｂ３”が設定されている。
【００４８】
ｃｌａｓｓＢのインスタンスでは、ｏｉｄが”ｂ１”、”ｂ２”、”ｂ３”のオブジェクトに、ｃｌａｓｓＡの各インスタンスからのリンクが張られており、ｃｌａｓｓＣのインスタンスへのリンクを張るために、ｌｉｎｋＣにｃｌａｓｓＣのインスタンスのオブジェクトＩＤが設定され、ｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＡには、ｃｌａｓｓＢのインスタンスからｃｌａｓｓＡのインスタンスへの、逆リンクが設定されている。
【００４９】
ｃｌａｓｓＣのインスタンスには、ｃｌａｓｓＢのインスタンスからのリンクが張られており、ｏｉｄが”ｃ１”、”ｃ２”、”ｃ３”のオブジェクトＩＤのオブジェクトに、属性の名前がｐｒｏｐｅｒｔｙという、型がＳｔｒｉｎｇで示される実際の文字列と、ｃｌａｓｓＣのインスタンスからｃｌａｓｓＢのインスタンスへの逆リンクを張るためのｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＢという名前の属性に、ｃｌａｓｓＢのインスタンスのオブジェクトＩＤが設定されている。
【００５０】
図１４は、図１１から図１３の例に基づいてナビゲーションを逆順に解決する処理を説明する図である。
図１４（ａ）のフローチャートにそって説明する。
【００５１】
まず、ステップＳ３０において、図１１に示したような検索条件をユーザが与えたとすると、システムには、
ｓｅｌｅｃｔ　ｃｌａｓｓＡ　ｆｒｏｍ　ｃｌａｓｓＡ　ｗｈｅｒｅｃｌａｓｓＡ．ｌｉｎｋＢ．ｌｉｎｋＣ．ｐｒｏｐｅｒｔｙ＝＝”富士通”
という問い合わせ式が渡される。
【００５２】
次に、ステップＳ３１において、問い合わせ式を解析し、問い合わせ対象のクラスと条件式とに分解し、条件式にナビゲーションがるかどうかを判断する。その結果、
問い合わせ対象：ｃｌａｓｓＡ
条件式：ｃｌａｓｓＡ．ｌｉｎｋＢ．ｌｉｎｋＣ．ｐｒｏｐｅｒｔｙ＝＝”富士通
ナビゲーション：有り
となる。
【００５３】
次に、ステップＳ３２において、ナビゲーションの解析を行い、条件式と図８に示したようなクラス情報テーブルから図１４（ｂ）のようなナビゲーションのテーブルを作成する。
【００５４】
ステップＳ３３では、ユーザが逆順検索を指定したか否かを判断する。ステップＳ３３において、ユーザが逆順検索を指定していないと判断した場合には、ステップＳ３４において、従来通りの検索を行う。
【００５５】
ステップＳ３３において、逆順検索の指定があると判断された場合には、ステップＳ３５において、図１４（ｂ）のナビゲーションからナビゲーションの最後のクラスがｃｌａｓｓＣであることを判断する。そして、ｃｌａｓｓＣのオブジェクトを対象に、属性ｐｒｏｐｅｒｔｙが”富士通”という値を持つものを選択する。図１３では、オブジェクトｃ１を選択する。
【００５６】
ステップＳ３６において、オブジェクトｃ１から、ナビゲーションテーブルを見て、逆順リンク属性ｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＢを参照することで、オブジェクトｂ１を獲得する。オブジェクトｂ１から、同じくナビゲーションテーブルを見て、逆順リンク属性ｒｅｖｅｒｓｅ　ｔｏ　ｌｉｎｋＡを参照することで、オブジェクトａ１を獲得する。
【００５７】
そして、ステップＳ３７において、逆順リンクで求めた、問い合わせ対象の部分集合を作成する。図１３の例では、｛ａ１｝という集合を作成する。
図１５及び図１６は、本発明の実施形態に従った処理のアルゴリズムを疑似コードとして示す図である。
【００５８】
図１５は、図１６のアルゴリズムが動作する場合に入力として与えるべきデータを示している。図１５は、与えられた条件式のナビゲーション解析の結果である。そのほかに、図１６のアルゴリズムの入力として、指定された条件式も入力されるものとする。図１６のアルゴリズムの出力は、検索の結果集合である。
【００５９】
図１５においては、ナビゲーション解析の結果として、次のナビゲーションへのリンク、クラス名、リンクの属性が少なくとも抽出され、更に、実装条件により、必要に応じてその他の情報も得るようにする。
【００６０】
図１６は、ユーザがナビゲーションの逆順解決を指定した部分の疑似コードである。
最初のｉｆ文によって、ユーザから逆順解決が指定されたか否かを判断する。逆順解決が指定されていない場合には、ｅｌｓｅ文の「これまでと同じ処理」すなわち、従来技術と同じ処理を用いて、問い合わせに対する応答を生成する。
【００６１】
最初のｉｆ文において、逆順指定があると判断された場合には、次に、最終条件の一致するオブジェクトを選択する一連の処理を行う。すなわち、ナビゲーションリンクから最終ナビゲートのクラス名を獲得する。これは、ｏｄｂ　ＧｅｔＬａｓｔＮａｖｉｇａｔｉｏｎＣｌａｓｓというサブルーチンにナビゲーションの解析結果を投入し、得られたクラス名をｃｌａｓｓＩｎｆｏという変数に代入することによって行われる。
【００６２】
次に、指定された条件式から最終ナビゲーションクラスに対して行う条件式を抽出する。これは、ｏｄｂ　ＧｅｔＣｏｎｄｉｔｉｏｎＦｏｒＬａｓｔＮａｖｉＣｌａｓｓというサブルーチンに、指定された条件式を代入し、ｃｏｎｄｉｔｉｏｎという変数に、条件式を代入することによって行われる。
【００６３】
更に、最終条件に一致するオブジェクトを選択する。これは、
ｏｄｂ　ＧｅｔＯｂｊｅｃｔｓＦｏｒＬａｓｔＮａｖｉＣｌａｓｓというサブルーチンに、ｃｌａｓｓＩｎｆｏとｃｏｎｄｉｔｉｏｎを投入し、得られたオブジェクトをｂａｇＬａｓｔＮａｖｉという変数に代入することによって行われる。
【００６４】
次に、逆順リンクを辿って、最終的な結果集合を得る一連の処理を行う。
まず、逆順リンクの開始として、ｂａｇＴｍｐＮａｖｉにｂａｇＬａｓｔＮａｖｉを代入する。そして、ナビゲーション解析結果を逆順にループする処理ループを実行する。まず、ｂａｇＴｍｐＮａｖｉのオブジェクトを一つずつスキャンする。つまり、逆順リンクの属性を参照するため、オブジェクトの逆リンク先が設定されているｒｅｖｅｒｓｅ　ｐｒｏｐｅｒｔｙの属性値を参照する。ここで、ナビゲーションと一致しない逆順リンクを辿らないために、ｒｅｖｅｒｓｅ　ｐｒｏｐｅｒｔｙの属性値のクラスがナビゲーションのクラス名と一致するか否かを判断する。一致する場合にのみ、ｂａｇＴｍｐＮａｖｉから現在スキャン中のオブジェクトを削除して、ｒｅｖｅｒｓｅ　ｐｒｏｐｅｒｔｙの属性値を挿入する。以上のナビゲーション解析結果の逆順にループする処理をナビゲーションの先頭のまで行うと、ｂａｇＴｍｐＮａｖｉが最終的なオブジェクトの結果集合となる。
【００６５】
図１７は、本発明の実施形態の処理をプログラムで実現する場合に、プログラムの実行に必要とされる情報処理装置のハードウェア環境を示した図である。
本発明の実施形態を実現するプログラムは、ＲＯＭ１２あるいは、ＲＡＭ１３に格納され、ＣＰＵ１０によって実行される。ＲＯＭ１２あるいはＲＡＭ１３からのプログラムコードは、バス１１を介してＣＰＵ１０に送られ、また、ＣＰＵ１０の演算結果は、ＲＡＭ１３に送られる。ＲＡＭ１３に送られた演算結果は、ディスプレイなどを含む入出力装置２０によって、ユーザに提示される。
【００６６】
入出力装置２０は、ディスプレイの他に、ユーザの指示を入力するキーボードや、マウス、テンプレートなどを含む。本発明の実施形態を実現するプログラムは、ＲＡＭ１３に展開される前には、ハードディスクなどの記憶装置１７に格納されていたり、可搬記録媒体１９に格納されている。記憶装置１７からは、プログラムが直接ＲＡＭ１３に、バス１１を介して展開されて、ＣＰＵ１０によって実行される。
【００６７】
可搬記録媒体１９に格納されたプログラムは、読み取り装置１８によって読み取られ、バス１１を介してＲＡＭ１３に展開され、ＣＰＵ１０によって実行される。
【００６８】
また、通信インターフェース１４は、ネットワーク１５を介して情報提供者１６のデータベースなどにアクセスすることができ、当該プログラムをダウンロードすることができる。ダウンロードされた当該プログラムは、記憶装置１７あるいは、可搬記録媒体１９に格納される。
【００６９】
記憶装置１７あるいは可搬記録媒体１９に格納された、ダウンロードされたプログラムは、上記したように、ＲＡＭ１３に展開されて、ＣＰＵ１０によって実行される。
【００７０】
あるいは、通信インターフェース１４、ネットワーク１５を使って、情報提供者１６にアクセスし、ネットワーク環境の下で、当該プログラムを実行することも可能である。
【００７１】
（付記１）情報処理装置にオブジェクト指向データベースにおける検索方法を実現させるプログラムであって、
該オブジェクト指向データベースに対する問い合わせを入力する問い合わせ入力ステップと、
該問い合わせに記述されるナビゲーションを解析する問い合わせ解析ステップと、
該ナビゲーションの記述の最後の条件式を評価し、該ナビゲーションの記述を最後の条件式から、記述と逆方向に解決するナビゲーション逆順解決ステップと、
該ナビゲーションの記述を逆方向に解決した結果を収集する結果収集ステップと
を備えることを特徴とする検索方法を情報処理装置に実現させるプログラム。
【００７２】
（付記２）前記ナビゲーションの記述の最後の条件式は、クラスのインスタンスの値を具体的に指定する記述であることを特徴とする付記１に記載のプログラム。
【００７３】
（付記３）前記検索方法は、ユーザが前記オブジェクト指向データベースにおいて、インスタンス間のリンクを定義した場合、該ユーザが指定したリンクと逆方向のリンクを自動的に生成することを特徴とする付記１に記載のプログラム。
【００７４】
（付記４）インスタンス間のリンクを前記ナビゲーションの記述と逆方向に辿る場合、インスタンス間のリンクに該ナビゲーションに記載されていないリンクがあっても、当該記述されていないリンクを辿らないことを特徴とする付記３に記載のプログラム。
【００７５】
（付記５）前記問い合わせは、前記ナビゲーションの先頭に記載されるクラスに属するインスタンスの母集合から、該ナビゲーションの最後の条件式を満たす部分集合を抽出する問い合わせであることを特徴とする付記１に記載のプログラム。
【００７６】
（付記６）オブジェクト指向データベースにおける検索装置であって、
該オブジェクト指向データベースに対する問い合わせを入力する問い合わせ入力手段と、
該問い合わせに記述されるナビゲーションを解析する問い合わせ解析手段と、
該ナビゲーションの記述の最後の条件式を評価し、該ナビゲーションの記述を最後の条件式から、記述と逆方向に解決するナビゲーション逆順解決手段と、
該ナビゲーションの記述を逆方向に解決した結果を収集する結果収集手段と
を備えることを特徴とする検索装置。
【００７７】
（付記７）オブジェクト指向データベースにおける検索方法であって、
該オブジェクト指向データベースに対する問い合わせを入力する問い合わせ入力ステップと、
該問い合わせに記述されるナビゲーションを解析する問い合わせ解析ステップと、
該ナビゲーションの記述の最後の条件式を評価し、該ナビゲーションの記述を最後の条件式から、記述と逆方向に解決するナビゲーション逆順解決ステップと、
該ナビゲーションの記述を逆方向に解決した結果を収集する結果収集ステップと
を備えることを特徴とする検索方法。
【００７８】
【００７９】
【発明の効果】
本発明によれば、要素数の多い母集合から特定の条件を満たす部分集合を取り出す処理を、オブジェクト指向データベースにおいて、問い合わせ式を用いて、データベースシステムに行わせる場合、より効率的にかつ高速に問い合わせに対する結果を得ることができる。
【図面の簡単な説明】
【図１】本発明の実施形態に従った検索方法の原理説明図である。
【図２】本発明の実施形態に従ったナビゲーション逆順に辿る方法の概念図である。
【図３】本発明の実施形態に従った検索方法の別の例を示す図である。
【図４】本発明の実施形態の処理概念を示す別の例の図である。
【図５】本発明の実施形態に従った、ナビゲーションの解決を行う処理のフローチャートである。
【図６】本発明の実施形態に従ったシステムが、ユーザの設定したリンクとは逆方向のリンクを自動的に作成する処理のフローチャートである。
【図７】本発明の実施形態に従った、クラス定義画面の例を示す図である。
【図８】クラス定義によるクラステーブルの作成例を示した図である。
【図９】リンク属性のオブジェクト設定と格納されたデータ構造の例である。
【図１０】図７から図９の図に基づいてシステムが逆リンクを生成する場合に行う処理の流れを説明するフローチャートである。
【図１１】ユーザが検索条件式を入力する入力指定画面の一例を示す図である。
【図１２】本発明の実施形態に従ったナビゲーションの逆順解決処理を具体例を挙げて説明する図（その１）である。
【図１３】本発明の実施形態に従ったナビゲーションの逆順解決処理を具体例を挙げて説明する図（その２）である。
【図１４】本発明の実施形態に従ったナビゲーションの逆順解決処理を具体例を挙げて説明する図（その３）である。
【図１５】本発明の実施形態に従った処理のアルゴリズムを疑似コードとして示す図（その１）である。
【図１６】本発明の実施形態に従った処理のアルゴリズムを疑似コードとして示す図（その２）である。
【図１７】本発明の実施形態の処理をプログラムで実現する場合に、プログラムの実行に必要とされる情報処理装置のハードウェア環境を示した図である。
【図１８】オブジェクト指向データベースのクラスと属性とそれらの関係を説明する図である。
【図１９】従来のナビゲーションの解決方法を説明する図である。
【図２０】従来の技術におけるナビゲーションの解決の方向を示す図である。
【図２１】従来の技術を説明する別の例である。
【図２２】図２１の場合のナビゲーションの従来の解決方法の例である。
【図２３】図２１の例の場合のリンクを辿る回数を示す図である。
【符号の説明】
１０　　　ＣＰＵ
１１　　　バス
１２　　　ＲＯＭ
１３　　　ＲＡＭ
１４　　　通信インターフェース
１５　　　ネットワーク
１６　　　情報提供者
１７　　　記憶装置
１８　　　読み取り装置
１９　　　可搬記録媒体
２０　　　入出力装置
【図１】
2004078631.tif 000003
【図２】
2004078631.tif 000004
【図３】
2004078631.tif 000005
【図４】
2004078631.tif 000006
【図５】
2004078631.tif 000007
【図６】
2004078631.tif 000008
【図７】
2004078631.tif 000009
【図８】
2004078631.tif 000010
【図９】
2004078631.tif 000011
【図１０】
2004078631.tif 000012
【図１１】
2004078631.tif 000013
【図１２】
2004078631.tif 000014
【図１３】
2004078631.tif 000015
【図１４】
2004078631.tif 000016
【図１５】
2004078631.tif 000017
【図１６】
2004078631.tif 000018
【図１７】
2004078631.tif 000019
【図１８】
2004078631.tif 000020
【図１９】
2004078631.tif 000021
【図２０】
2004078631.tif 000022
【図２１】
2004078631.tif 000023
【図２２】
2004078631.tif 000024
【図２３】
2004078631.tif 000025