(57)【要約】  データ照会方法および装置ならびにデータベースシステムが提供される。本方法は、データ照会要求を受信するステップ（S1110）と、データ照会要求に従って元の照会プランを生成するステップ（S1120）と、元の照会プランに従って候補照会プランセットを取得するステップ（S1130）と、元の照会プランの結合述語を再構成するステップ（S1140）と、元の照会プランの再構成された結合述語の基本情報を決定するステップ（S1150）と、元の照会プランの再構成された結合述語の制約条件を決定するステップ（S1160）と、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定するステップ（S1170）と、元の照会プランの等コスト照会プランに従って照会を実行するステップ（S1180）とを含む。データ照会方法および装置ならびにデータベースシステムによれば、データ照会性能を向上させることができる。
2019504390.tif 000002
【特許請求の範囲】
【請求項１】
データ照会方法であって、前記方法がデータベースシステムによって実行され、前記データベースシステムがコンピュータデバイス上で動作し、前記方法が、
データ照会要求を受信するステップと、
前記データ照会要求に従って元の照会プランを生成するステップと、
前記元の照会プランの結合述語を再構成するステップと、
前記元の照会プランの再構成された結合述語の基本情報を決定するステップと、
結合演算規則に基づいて、前記元の照会プランの前記再構成された結合述語の制約条件を決定するステップと、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定するステップと、
前記元の照会プランの前記等コスト照会プランに従って照会を実行するステップと
を含む、データ照会方法。
【請求項２】
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定する前記ステップが、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランセットを決定するステップ
を含み、
前記元の照会プランの前記等コスト照会プランに従って照会を実行する前記ステップが、
照会を実行するために前記等コスト照会プランセットから照会プランを選択するステップ
を含む、請求項1に記載の方法。
【請求項３】
前記方法が、
前記元の照会プランに従って候補照会プランセットを取得するステップ
をさらに含み、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランセットを決定する前記ステップが、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記候補照会プランセットから前記等コスト照会プランセットを決定するステップ
を含む、請求項2に記載の方法。
【請求項４】
前記元の照会プランの結合述語を再構成する前記ステップが、
前記元の照会プランの内部結合演算のすべての結合述語を連言標準形に変換し、同じ入力テーブルを有する結合述語を組み合わせるステップと、
前記元の照会プランの非内部結合演算のすべての結合述語を1つの結合述語に組み合わせるステップと
を含む、請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記結合述語の前記基本情報が、前記結合述語の入力テーブルと、前記結合述語が位置する結合演算の左サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の右サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の結合タイプとを含む、請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記結合演算規則が、演算レベル規則および述語レベル規則を含み、前記演算レベル規則が、演算レベル交換規則：e1 oap12 e2＝e2 oap12 e1、演算レベル組み合わせ規則：（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）、演算レベル左置換規則：（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2、および演算レベル右置換規則：e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）を含み、前記述語レベル規則が、述語レベル組み合わせ規則：（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）、述語レベル左置換規則：（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2、および述語レベル右置換規則：e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）を含み、eiは照会式であり、oaおよびobは結合演算であり、pijはeiとejとの結合述語である、請求項1から5のいずれか一項に記載の方法。
【請求項７】
結合演算規則に基づいて、前記元の照会プランの前記再構成された結合述語の制約条件を決定する前記ステップが、
前記元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAをトラバースするステップ、および
oAが、oBを前記ルートノードとして使用する前記サブツリーの左サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル左置換規則および前記述語レベル左置換規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加するステップ、または
oAが、oBを前記ルートノードとして使用する前記サブツリーの右サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル右置換規則および前記述語レベル右置換規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加するステップ
を含み、
前記第1の制約条件が、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、前記第2の制約条件が、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAを前記ルートノードとして使用する前記サブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、前記第1のサブツリーがT2のすべての入力テーブルを含むことを示す、
請求項6に記載の方法。
【請求項８】
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定する前記ステップが、
第1の候補照会プランP’が以下の条件を満たす場合に、P’は前記元の照会プランPの等コスト照会プランであると決定するステップであって、以下の条件が、
P’の各第1の結合演算の結合タイプが内部結合であり、前記第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、前記少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件、
P’の各結合演算ob’の各結合述語pに関して、
ob’が前記演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する前記結合演算の右サブツリーに含まれるpの入力テーブルを示し、または
ob’が前記演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件である、ステップ
を含む、請求項1から7のいずれか一項に記載の方法。
【請求項９】
照会を実行するために前記等コスト照会プランセットから照会プランを選択する前記ステップが、
照会を実行するために前記等コスト照会プランセットから最小コストの照会プランを選択するステップ
を含む、請求項2に記載の方法。
【請求項１０】
データ照会装置であって、
データ照会要求を受信するように構成される受信モジュールと、
前記データ照会要求に従って元の照会プランを生成するように構成される生成モジュールと、
前記元の照会プランの結合述語を再構成するように構成される再構成モジュールと、
前記元の照会プランの再構成された結合述語の基本情報を決定し、結合演算規則に基づいて、前記元の照会プランの前記再構成された結合述語の制約条件を決定し、前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定するように構成される決定モジュールと、
前記元の照会プランの前記等コスト照会プランに従って照会を実行するように構成される照会モジュールと
を備える、データ照会装置。
【請求項１１】
前記決定モジュールが、前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランセットを決定するように特に構成され、
前記照会モジュールが、照会を実行するために前記等コスト照会プランセットから照会プランを選択するように特に構成される、
請求項10に記載の装置。
【請求項１２】
前記装置が、
前記元の照会プランに従って候補照会プランセットを取得するように構成される取得モジュール
をさらに備え、
前記決定モジュールが、前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記候補照会プランセットから前記等コスト照会プランセットを決定するように特に構成される、
請求項11に記載の装置。
【請求項１３】
前記再構成モジュールが、
前記元の照会プランの内部結合演算のすべての結合述語を連言標準形に変換し、同じ入力テーブルを有する結合述語を組み合わせ、
前記元の照会プランの非内部結合演算のすべての結合述語を1つの結合述語に組み合わせる
ように特に構成される、請求項10から12のいずれか一項に記載の装置。
【請求項１４】
前記結合述語の前記基本情報が、前記結合述語の入力テーブルと、前記結合述語が位置する結合演算の左サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の右サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の結合タイプとを含む、請求項10から13のいずれか一項に記載の装置。
【請求項１５】
前記結合演算規則が、演算レベル規則および述語レベル規則を含み、前記演算レベル規則が、演算レベル交換規則：e1 oap12 e2＝e2 oap12 e1、演算レベル組み合わせ規則：（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）、演算レベル左置換規則：（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2、および演算レベル右置換規則：e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）を含み、前記述語レベル規則が、述語レベル組み合わせ規則：（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）、述語レベル左置換規則：（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2、および述語レベル右置換規則：e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）を含み、eiは照会式であり、oaおよびobは結合演算であり、pijはeiとejとの結合述語である、請求項10から14のいずれか一項に記載の装置。
【請求項１６】
前記決定モジュールが、
前記元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAをトラバースし、
oAが、oBを前記ルートノードとして使用する前記サブツリーの左サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル左置換規則および前記述語レベル左置換規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加するか、または
oAが、oBを前記ルートノードとして使用する前記サブツリーの右サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル右置換規則および前記述語レベル右置換規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加する
ように特に構成され、
前記第1の制約条件が、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、前記第2の制約条件が、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAを前記ルートノードとして使用する前記サブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、前記第1のサブツリーがT2のすべての入力テーブルを含むことを示す、
請求項15に記載の装置。
【請求項１７】
前記決定モジュールが、
第1の候補照会プランP’が以下の条件を満たす場合に、P’は前記元の照会プランPの等コスト照会プランであると決定するように特に構成され、以下の条件が、
P’の各第1の結合演算の結合タイプが内部結合であり、前記第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、前記少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件、
P’の各結合演算ob’の各結合述語pに関して、
ob’が前記演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する前記結合演算の右サブツリーに含まれるpの入力テーブルを示し、または
ob’が前記演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件である、
請求項10から16のいずれか一項に記載の装置。
【請求項１８】
前記照会モジュールが、
照会を実行するために前記等コスト照会プランセットから最小コストの照会プランを選択する
ように特に構成される、請求項11に記載の装置。
【請求項１９】
データ照会装置であって、装置が、プロセッサおよびメモリを備え、前記メモリが、命令を格納するように構成され、前記プロセッサが、前記命令を実行するように構成され、前記プロセッサが、前記プロセッサが前記命令を実行したときに、請求項1から9のいずれか一項に記載の方法を実行する、データ照会装置。
【請求項２０】
請求項10から18のいずれか一項に記載のデータ照会装置とデータベースとを備えるデータベースシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報技術の分野に関し、より具体的には、データ照会方法および装置ならびにデータベースシステムに関する。
【背景技術】
【０００２】
構造化照会言語（Structured Query Language、SQL）は、リレーショナルデータベース管理システムの標準言語である。構造化照会言語は、高度な非手続き型の記述言語である。すなわち、構造化照会言語は、ユーザが上位層のデータ構造上で必要なデータを取得することを可能にするが、構造化照会言語は、ユーザがデータを取得するための方法、すなわち一般的には照会プランを指定することを必要としない。照会プランはツリーで表され得る。ツリーのリーフノードは入力テーブルを示し、中間ノードは演算を示す。SQL照会は、通常、多くの等コスト照会プランを有し、異なる照会プランの実行時間は異なる。したがって、データベースシステムには、最適な（すなわち、実行時間が最短である）照会プランを選択するための照会オプティマイザコンポーネントが存在する。
【０００３】
照会オプティマイザの主な機能は、元の照会プランの等コスト照会プランを決定し、最適な照会プランを選択することである。しかしながら、従来技術では、いくらかの等コスト照会プランが省略され、その結果、照会性能が影響を受けている。
【発明の概要】
【課題を解決するための手段】
【０００４】
本発明の実施形態は、データ照会性能を向上させるために、データ照会方法および装置ならびにデータベースシステムを提供する。
【０００５】
第1の態様によれば、本発明の一実施形態は、データ照会方法であって、方法がデータベースシステムによって実行され、データベースシステムがコンピュータデバイス上で動作し、本方法が、
データ照会要求を受信するステップと、
データ照会要求に従って元の照会プランを生成するステップと、
元の照会プランの結合述語を再構成するステップと、
元の照会プランの再構成された結合述語の基本情報を決定するステップと、
結合演算規則に基づいて、元の照会プランの再構成された結合述語の制約条件を決定するステップと、
元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定するステップと、
元の照会プランの等コスト照会プランに従って照会を実行するステップと
を含む、データ照会方法を提供する。
【０００６】
本発明の実施形態では、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、元の照会プランの等コスト照会プランが決定され、元の照会プランの相対的に多量の等コスト照会プランが取得され得るため、データ照会のパフォーマンスを向上させることができる。
【０００７】
一部の実施態様では、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定するステップが、
元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランセットを決定するステップ
を含み、
元の照会プランの等コスト照会プランに従って照会を実行するステップが、
照会を実行するために等コスト照会プランセットから照会プランを選択するステップ
を含む。
【０００８】
一部の実施態様では、本方法は、
元の照会プランに従って候補照会プランセットを取得するステップ
をさらに含み、
元の照会プランの候補照会プランは、ここで可能な限り多く取得されるべきであり、好ましくは、照会プラン列挙アルゴリズムを、元の照会プランのすべての候補照会プランを列挙するために使用することができ、典型的な列挙アルゴリズム、例えば、IBM System Rで使用される動的プログラミングアルゴリズムが使用されてもよく、
元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランセットを決定するステップが、
元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って候補照会プランセットから等コスト照会プランセットを決定するステップ
を含む。
【０００９】
本発明の実施形態では、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、候補照会プランセットから元の照会プランの等コスト照会プランが決定され、元の照会プランのすべての等コスト照会プランが取得され得るため、データ照会のパフォーマンスをさらに向上させることができる。
【００１０】
一部の実施態様では、元の照会プランの結合述語を再構成するステップが、
元の照会プランの内部結合演算のすべての結合述語を連言標準形に変換し、同じ入力テーブルを有する結合述語を組み合わせるステップと、
元の照会プランの非内部結合演算のすべての結合述語を1つの結合述語に組み合わせるステップと
を含む。
【００１１】
一部の実施態様では、結合述語の基本情報は、結合述語の入力テーブルと、結合述語が位置する結合演算の左サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の右サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の結合タイプとを含む。
【００１２】
一部の実施態様では、結合演算規則は、演算レベル規則および述語レベル規則を含み、演算レベル規則は、演算レベル交換規則：e1 oap12 e2＝e2 oap12 e1、演算レベル組み合わせ規則：（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）、演算レベル左置換規則：（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2、および演算レベル右置換規則：e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）を含み、述語レベル規則は、述語レベル組み合わせ規則：（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）、述語レベル左置換規則：（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2、および述語レベル右置換規則：e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）を含み、eiは照会式であり、oaおよびobは結合演算であり、pijはeiとejとの結合述語である。
【００１３】
一部の実施態様では、結合演算規則に基づいて、元の照会プランの再構成された結合述語の制約条件を決定するステップが、
元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAをトラバースするステップ、および
oAが、oBをルートノードとして使用するサブツリーの左サブツリー内にあるときに、oAおよびoBが演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが演算レベル左置換規則および述語レベル左置換規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加するステップ、または
oAが、oBをルートノードとして使用するサブツリーの右サブツリー内にあるときに、oAおよびoBが演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが演算レベル右置換規則および述語レベル右置換規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加するステップ
を含み、
第1の制約条件が、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、第2の制約条件が、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAをルートノードとして使用するサブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、第1のサブツリーがT2のすべての入力テーブルを含むことを示す。
【００１４】
一部の実施態様では、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定するステップが、
第1の候補照会プランP’が以下の条件を満たす場合に、P’は元の照会プランPの等コスト照会プランであると決定するステップであって、この以下の条件が、
P’の各第1の結合演算の結合タイプが内部結合であり、第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件、
P’の各結合演算ob’の各結合述語pに関して、
ob’が演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する結合演算の右サブツリーに含まれるpの入力テーブルを示し、または
ob’が演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件である、ステップ
を含む。
【００１５】
一部の実施態様では、照会を実行するために等コスト照会プランセットから照会プランを選択するステップが、
照会を実行するために等コスト照会プランセットから最小コストの照会プランを選択するステップ
を含む。
【００１６】
第2の態様によれば、本発明の一実施形態は、データ照会装置を提供する。本装置は、第1の態様による方法を実行するためのモジュールを含む。
【００１７】
第3の態様によれば、本発明の一実施形態は、データ照会装置を提供する。本装置は、プロセッサと、メモリと、通信インタフェースとを含む。プロセッサは、メモリおよび通信インタフェースに結合される。メモリは、命令を格納するように構成され、プロセッサは、命令を実行するように構成され、通信インタフェースは、プロセッサの制御下で別のネットワーク要素と通信するように構成される。プロセッサは、プロセッサが命令を実行したときに、第1の態様による方法を実行する。
【００１８】
第4の態様によれば、本発明の一実施形態は、データベースシステムを提供する。データベースシステムは、第2の態様または第3の態様によるデータ照会装置とデータベースとを含む。
【００１９】
一部の実施態様では、元の照会プランの等コスト照会プランは、4つの演算レベル規則および3つの述語レベル規則の少なくとも1つを使用して変換することによって元の照会プランから取得される照会プランである。
【００２０】
一部の実施態様では、等コスト照会プラン空間は、4つの演算レベル規則および3つの述語レベル規則の少なくとも1つを使用して変換することによって元の照会プランから取得される複数の照会プランを含む。
【００２１】
本発明の実施形態の技術的解決策をより明確に説明するために、以下では、本発明の実施形態を説明するために必要な添付図面について簡単に説明する。明らかに、以下の説明における添付図面は、本発明の一部の実施形態しか示しておらず、当業者は、創造的な努力なしにこれらの添付図面から他の図面をさらに得ることができる。
【図面の簡単な説明】
【００２２】
【図１ａ】本発明の一実施形態による適用シナリオの概略図である。
【図１ｂ】本発明の一実施形態による別の適用シナリオの概略図である。
【図１ｃ】本発明の一実施形態による結合演算の一例である。
【図２】本発明の一実施形態による、等コスト照会プランの一例である。
【図３】本発明の一実施形態による演算レベル交換規則の一例である。
【図４】本発明の一実施形態による演算レベル組み合わせ規則の一例である。
【図５】本発明の一実施形態による演算レベル左置換規則の一例である。
【図６】本発明の一実施形態による演算レベル右置換規則の一例である。
【図７】本発明の一実施形態による述語レベル組み合わせ規則の一例である。
【図８】本発明の一実施形態による述語レベル左置換規則の一例である。
【図９】本発明の一実施形態による述語レベル右置換規則の一例である。
【図１０】本発明の一実施形態による、等コスト照会プランの一例である。
【図１１】本発明の一実施形態によるデータ照会方法の概略フローチャートである。
【図１２】本発明の一実施形態による照会プランの一例である。
【図１３Ａ】本発明の一実施形態による元の照会プランの述語の制約条件を決定するフローチャートの前半である。
【図１３Ｂ】本発明の一実施形態による元の照会プランの述語の制約条件を決定するフローチャートの後半である。
【図１４】本発明の一実施形態による制約条件の追加の概略図である。
【図１５】本発明の一実施形態による制約条件の追加の別の概略図である。
【図１６】本発明の一実施形態による等コスト照会プランを決定する例である。
【図１７】本発明の一実施形態によるデータ照会装置の概略ブロック図である。
【図１８】本発明の一実施形態によるデータベースシステムの概略ブロック図である。
【図１９】本発明の一実施形態によるデータ照会装置の概略構成図である。
【発明を実施するための形態】
【００２３】
以下では、本発明の実施形態の添付図面を参照しながら、本発明の実施形態の技術的解決策を明確かつ完全に説明する。明らかに、説明されている実施形態は、本発明の実施形態のすべてではなく、その一部である。創造的な努力なしに本発明の実施形態に基づいて当業者によって得られる他のすべての実施形態は、本発明の保護範囲内に含まれるものとする。
【００２４】
本発明の実施形態における技術的解決策は、データベースシステムに適用することができる。図1aおよび図1bは、本発明の一実施形態による適用シナリオの概略図である。図1aは、単一のサーバを有するデータベースシステムであり、図1bは、分散データベースシステムである。
【００２５】
図1aに示すように、単一のサーバを有するデータベースシステム（すなわち、サーバ）は、データベース管理システムおよびデータベースを含み、クライアントの照会要求を処理し、照会結果をクライアントに返すように構成される。データベース管理システムは、照会オプティマイザなどの管理コンポーネントを含み、データベースシステムを管理するように構成される。このシナリオでは、本発明の実施形態における方法は、サーバ、またはサーバのデータベース管理システム、またはデータベース管理システムの照会オプティマイザによって実行され得る。
【００２６】
図1bに示すように、分散データベースシステムは、複数のサーバおよび分散管理システムを含み、クライアントの照会要求を処理し、照会結果をクライアントに返すように構成される。各サーバは、データベース管理システムおよびデータベースを含み、分散管理システムは、照会オプティマイザなどの管理コンポーネントを含み、分散データベースシステムを管理するように構成される。このシナリオでは、本発明の実施形態における方法は、分散データベースシステム、または分散データベースシステムの分散管理システム、または分散管理システムの照会オプティマイザによって実行され得る。
【００２７】
本発明の実施形態の理解を容易にするために、以下ではまずデータベースシステムに関する用語を説明する。
【００２８】
本発明の様々な実施形態において、結合演算は、演算または結合と呼ばれる場合もあり、また、結合演算は、データベース内の2つ以上のテーブルを1つの結果テーブルに組み合わせる。結合述語は述語と呼ばれる場合もあり、また、結合述語は、2つ以上のテーブルの列の関係を記述するために使用される。結合演算は、結合述語を使用してデータベース内のテーブルを組み合わせる。
【００２９】
結合演算は、内部結合（inner join）、左／右外部結合（left／right outer join）、完全外部結合（full outer join）、左／右半結合（left／right semi−join）、および左／右反結合（left／right anti−join）に分類される。
【００３０】
内部結合（inner join）は、データベースにおける最も一般的な結合演算である。内部結合は、結合述語に基づいて2つのテーブル（例えば、RおよびS）の列を互いに組み合わせて、新しい結果テーブルを生成する。この演算は、テーブルRの各行とテーブルSの各行を比較し、結合述語を満たす組み合わせを発見する。結合述語が満たされているとき、RおよびSの合致した行は、結果テーブルの1つの行として、列を単位に（並べて）組み合わされる。
【００３１】
左外部結合（left outer join）は、内部結合の拡張である。左外部結合と内部結合の違いは、2つのテーブルRおよびSに対して左外部結合が実行された場合に、結合述語を満たすように左テーブル（すなわち、テーブルR）の行に合致する右テーブルSの行がなかった場合、内部結合で左テーブルの行の値を直接破棄する代わりに、左外部結合は、それでもレコードを返し、その場合、レコードは、左テーブルのすべての列の値を保持するが、右テーブルの行に対応する各列の値が空（NULL）であることである。右外部結合（right outer join）は左外部結合と同様であるが、唯一の違いは、右テーブルの行に合致する左テーブルの行がなかった場合、演算によって返されるレコードにおける、左テーブルの各列の値が空であることである。完全外部結合（full outer join）は、左／右外部結合と同様であるが、唯一の違いは、左テーブルまたは右テーブルに関係なく、テーブルの行に合致する行がなかった場合に、演算がレコードを返し、レコードの合致しなかった行の、テーブルの列の値が空であることである。
【００３２】
左半結合（left semi−join）は、右テーブルに合致する行がある（すなわち、結合述語を満たす）左テーブルの行のみを返す。右半結合（right semi−join）は、左テーブルに合致する行がある（すなわち、結合述語を満たす）右テーブルの行のみを返す。
【００３３】
左反結合（left anti−join）は、右テーブルに合致する行がない（すなわち、結合述語を満たさない）左テーブルの行のみを返す。右反結合（right anti−join）は、左テーブルに合致する行がない（すなわち、結合述語を満たさない）右テーブルの行のみを返す。半結合および反結合の定義から、半結合と反結合が互いに相補的なセットであることが分かる。
【００３４】
図1cは、上記の様々な結合演算の例を示す。図1cでは、テーブルRおよびテーブルSに対して結合演算が実行されることが一例として使用されている。結合述語はR．b＝S．cであり、様々な結合演算の結果が図1cに示されている。
【００３５】
図2は、等コスト照会プランの一例を示す。図2に示すように、SQL照会R1∞p12R2∞p23R3の場合、R1、R2、およびR3は入力テーブルを表し、∞は内部結合演算を表し、p12およびp23は、それぞれR1とR2との結合述語およびR2とR3との結合述語を表す。図2の2つの照会プランの両方は、照会に関して等コスト照会プランである。
【００３６】
本発明の様々な実施形態では、結合演算規則は、演算レベル規則および述語レベル規則を含む。演算レベル規則は、演算レベル交換規則、演算レベル組み合わせ規則、演算レベル左置換規則、および演算レベル右置換規則を含む。述語レベル規則は、述語レベル組み合わせ規則、述語レベル左置換規則、および述語レベル右置換規則を含む。以下の説明において、各記号の意味を表1に示す。
【００３７】
【表１】
2019504390.tif 000003
【００３８】
演算レベル交換規則は、e1 oap12 e2＝e2 oap12 e1である。図3は、演算レベル交換規則の一例である。表2は、演算レベル交換規則の結合演算テーブルであり、各結合演算が演算レベル交換規則を満たすかどうかを示す。＋は、結合演算が演算レベル交換規則を満たすことを示し、−は、結合演算が演算レベル交換規則を満たさないことを示す。右外部結合、右半結合、および右反結合は、対応する左結合演算に変換することができ、したがって、本明細書では左結合演算のみが考慮されることを理解されたい。
【００３９】
【表２】
2019504390.tif 000004
【００４０】
演算レベル組み合わせ規則は、（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）である。図4は、演算レベル組み合わせ規則の一例である。表3は、演算レベル組み合わせ規則の結合演算テーブルであり、任意の2つの結合演算が演算レベル組み合わせ規則を満たすかどうかを示す。＋は、2つの結合演算が演算レベル組み合わせ規則を満たすことを示し、−は、2つの結合演算が演算レベル組み合わせ規則を満たさないことを示す。上付き文字を伴う＋は、ある条件下で組み合わせ規則が満たされることを示す。すなわち、上付き文字の条件が満たされている場合にのみ、2つの対応する結合演算は、組み合わせ規則を満たすことができる。
【００４１】
【表３】
2019504390.tif 000005
【００４２】
演算レベル左置換規則は、（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2である。図5は、演算レベル左置換規則の一例である。表4は、演算レベル左置換規則の結合演算テーブルであり、任意の2つの結合演算が演算レベル左置換規則を満たすかどうかを示す。＋は、2つの結合演算が演算レベル左置換規則を満たすことを示し、−は、2つの結合演算が演算レベル左置換規則を満たさないことを示す。上付き文字を伴う＋は、ある条件下で左置換規則が満たされることを示す。すなわち、上付き文字の条件が満たされている場合にのみ、2つの対応する結合演算は、左置換規則を満たすことができる。
【００４３】
【表４】
2019504390.tif 000006
【００４４】
演算レベル右置換規則は、e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）である。図6は、演算レベル右置換規則の一例である。表5は、演算レベル右置換規則の結合演算テーブルであり、任意の2つの結合演算が演算レベル右置換規則を満たすかどうかを示す。＋は、2つの結合演算が演算レベル右置換規則を満たすことを示し、−は、2つの結合演算が演算レベル右置換規則を満たさないことを示す。上付き文字を伴う＋は、ある条件下で右置換規則が満たされることを示す。すなわち、上付き文字の条件が満たされている場合にのみ、2つの対応する結合演算は、右置換規則を満たすことができる。
【００４５】
【表５】
2019504390.tif 000007
【００４６】
上記の演算レベル規則では、演算の結合述語とその演算は結び付けられている、すなわち、結合述語は演算間を移動できない。演算レベル規則とは異なり、述語レベル規則では、述語は演算間を移動できる。
【００４７】
述語レベル組み合わせ規則は、（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）である。∧はAND論理演算を示し、pはp23以外の結合述語を示し、pは空ではない。図7は、述語レベル組み合わせ規則の一例である。
【００４８】
述語レベル左置換規則は、（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2である。∧はAND論理演算を示し、pはp13以外の結合述語を示し、pは空ではない。図8は、述語レベル左置換規則の一例である。
【００４９】
述語レベル右置換規則は、e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）である。∧はAND論理演算を示し、pはp13以外の結合述語を示し、pは空ではない。図9は、述語レベル右置換規則の一例である。
【００５０】
表6は、述語レベル規則の結合演算テーブルであり、任意の2つの結合演算が述語レベル規則を満たすかどうかを示す。＋は、2つの結合演算が述語レベル規則を満たすことを示し、−は、2つの結合演算が述語レベル規則を満たさないことを示す。上記の3つの述語レベル規則の結合演算テーブルは同じである、すなわち、表6は、3つの述語レベル規則のすべての結合演算テーブルを表す。
【００５１】
【表６】
2019504390.tif 000008
【００５２】
本発明の実施形態では、上記の演算レベル規則または述語レベル規則を使用して変換することにより取得され得るすべての照会プランは、等コスト照会プランである。すなわち、本発明の実施形態における等コスト照会プラン空間は、4つの演算レベル規則および3つの述語レベル規則の少なくとも1つを使用して変換することにより取得され得るすべての照会プランである。規則が演算間で満たされるかどうかは、規則の結合演算テーブルに問い合わせることによって判定され得る。
【００５３】
演算レベル規則のみを使用して変換することにより得られる等コスト照会プラン空間と比較して、本発明の実施形態の等コスト照会プラン空間はより完全である。すなわち、演算レベル規則のみを使用して変換を行う場合、すべての等コスト照会プランを取得することができない。例えば、図10に示すように、左の元の照会プランに対して、右の2つの候補照会プランでは、演算間で結合述語を移動させているため、上記の4つの演算レベル規則を使用して左の元の照会プランを変換することによっては、これらの2つの候補照会プランは取得することができない。なお、2つの右の候補照会プランは、実際には左の元の照会プランと等価である。
【００５４】
本発明の実施形態では、元の照会プランの等コスト照会プランは、演算レベル規則および述語レベル規則に基づいて決定され、元の照会プランのすべての等コスト照会プランを取得することができる。
【００５５】
図11は、本発明の一実施形態によるデータ照会方法1100の概略フローチャートである。方法1100は、データベースシステムによって実行され、データベースシステムは、コンピュータデバイス上で動作する。具体的には、本方法は、コンピュータ上で動作するデータ照会装置によって実行される。データ照会装置は、照会オプティマイザなどの、データベースシステム内の装置であってもよいし、データベースシステムであってもよい。
【００５６】
S1110．データ照会要求を受信する。
【００５７】
例えば、データ照会要求は、SQL言語を使用してユーザによって入力されたデータ照会要求であってもよい。
【００５８】
S1120．データ照会要求に従って元の照会プランを生成する。
【００５９】
データ照会要求が受信された後、データ照会要求は、元の照会プランを取得するために構文解析される。
【００６０】
任意選択的に、S1130．元の照会プランに従って候補照会プランセットを取得する。
【００６１】
候補照会プランセットは、元の照会プランのすべての候補照会プランを含む。このステップでは、照会プラン列挙アルゴリズムが、元の照会プランのすべての候補照会プランを列挙するために使用されてもよい。例えば、典型的な列挙アルゴリズムは、IBM System Rで使用される動的プログラミングアルゴリズムを含む。
【００６２】
元の照会プランのすべての候補照会プランが列挙された後、元の照会プランの等コスト照会プランが、すべての候補照会プランから決定されてもよい。
【００６３】
このステップは任意選択のステップである。すなわち、本発明のこの実施形態では、以下のステップを使用して、等コスト照会プランまたは等コスト照会プランセットを元の照会プランから直接取得してもよいし、以下のステップを使用して、等コスト照会プランセットを候補照会プランセットから取得してもよい。
【００６４】
S1140．元の照会プランの結合述語を再構成する。
【００６５】
具体的には、元の照会プランの内部結合演算のすべての結合述語が、連言標準形に変換され、同じ入力テーブルを有する結合述語が組み合わされ、元の照会プランの非内部結合演算のすべての結合述語が、1つの結合述語に組み合わされる。
【００６６】
すなわち、再構成方法は、元の照会プランの各結合演算ノードをトラバースし、以下の2つの場合に結合演算ノードの結合タイプに従って処理を行うことである。
【００６７】
結合演算が内部結合の場合、結合演算のすべての述語は、連言標準形（conjunctive normal form、CNF）、すなわちp1∧p2∧．．．∧pnの形に変換され、同じ入力テーブルを有する述語は組み合わされる。
【００６８】
結合演算が内部結合でない場合、結合演算のすべての述語は1つの述語に組み合わされる。
【００６９】
S1150．元の照会プランの再構成された結合述語の基本情報を決定する。
【００７０】
本発明の様々な実施形態において、結合述語の基本情報は、結合述語の入力テーブルと、結合述語が位置する結合演算の左サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の右サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の結合タイプとを含む。
【００７１】
具体的には、述語pに関して、述語pの基本情報は、
T（p）：pに含まれる入力テーブルと、
Tl（p）：pが位置する演算の左サブツリーに含まれるpの入力テーブルと、
Tr（p）：pが位置する演算の右サブツリーに含まれるpの入力テーブルと、
O（p）：pが位置する演算の結合タイプと
を含む。
【００７２】
例えば、図12に示すルートノードの結合述語p＝｛R1．a＋R2．b＝R3．c｝に関して、pの基本情報は、
T（p）：｛R1，R2，R3｝、
Tl（p）：｛R1，R2｝、
Tr（p）：｛R3｝、および
O（p）：内部結合
である。
【００７３】
S1160．結合演算規則に基づいて、元の照会プランの再構成された結合述語の制約条件を決定する。
【００７４】
具体的には、元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAがトラバースされ、
oAが、oBをルートノードとして使用するサブツリーの左サブツリー内にあるときに、oAおよびoBが、演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第1の制約条件が、oBの再構成された各結合述語に追加され、oAおよびoBが、演算レベル左置換規則および述語レベル左置換規則を満たさない場合、第2の制約条件が、oBの再構成された各結合述語に追加され、
oAが、oBをルートノードとして使用するサブツリーの右サブツリー内にあるときに、oAおよびoBが、演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第2の制約条件が、oBの再構成された各結合述語に追加され、oAおよびoBが、演算レベル右置換規則および述語レベル右置換規則を満たさない場合、第1の制約条件が、oBの再構成された各結合述語に追加され、その場合、
第1の制約条件は、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、第2の制約条件は、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAをルートノードとして使用するサブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、第1のサブツリーがT2のすべての入力テーブルを含むことを示し、∩は積集合記号である。
【００７５】
例えば、図13Aおよび図13Bは、元の照会プランの述語の制約条件を決定するフローチャートを示す。図13Aおよび図13Bに示す手順は、2層トラバーサルを含む。外層に関しては、元の照会プランの各演算ノードoB（oBの再構成された述語はpb1∧pb2∧．．．∧pbnである）がトラバースされ、内層に関しては、oBをルートノードとして使用する照会サブツリー内の各演算ノードoA（oAの再構成された述語はpa1∧pa2∧．．．∧panである）がトラバースされる。次に、以下の2つの場合に、oAとoBとの関係に従って、oBの各述語に制約条件が追加される。
【００７６】
oAがoBの左サブツリー内にある場合、図14に示す方法に従って、oBの各述語pbiに制約条件が追加される。
【００７７】
oAがoBの右サブツリー内にある場合、図15に示す方法に従って、oBの各述語pbiに制約条件が追加される。
【００７８】
S1170．元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定する。
【００７９】
任意選択的に、元の照会プランの等コスト照会プランセットが、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って決定されてもよい。等コスト照会プランセットの照会プランは、元の照会プランの等コスト照会プランである。
【００８０】
このステップでは、任意選択的に、元の照会プランの候補照会プランセットが列挙されて取得される場合、候補照会プランセットから等コスト照会プランセットを決定してもよい、すなわち、各候補照会プランが元の照会プランの等コスト照会プランであるかどうかが判定される。候補照会プランセットが存在しない場合は、元の照会プランから候補照会プランを取得するたびに、候補照会プランが元の照会プランの等コスト照会プランであるかどうかを判定してもよい。
【００８１】
具体的には、第1の候補照会プランP’が以下の条件を満たす場合に、P’は元の照会プランPの等コスト照会プランであると決定され、この以下の条件とは、
P’の各第1の結合演算の結合タイプが内部結合であり、第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件（この条件は結合タイプの一貫性と呼ばれ得る）、
P’の各結合演算ob’の各結合述語pに関して、
ob’が演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する結合演算の右サブツリーに含まれるpの入力テーブルを示し、
ob’が演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件（この条件は入力テーブル情報の一貫性と呼ばれ得る）、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件（この条件は制約条件の一貫性と呼ばれ得る）であり、元の照会プランの候補照会プランセットが前に取得されている場合、ここでの第1の候補照会プランP’は、候補照会プランセット内の候補照会プランであってもよい。
【００８２】
元の照会プランのすべての等コスト照会プランは、上記の方法で取得することができる。すなわち、本発明のこの実施形態で取得される等コスト照会プランセットは最も完全である。
【００８３】
S1180．元の照会プランの等コスト照会プランに従って照会を実行する。
【００８４】
任意選択的に、照会プランは、照会を実行するために等コスト照会プランセットから選択されてもよい。すなわち、照会プランは、照会を実行するために上記の取得された等コスト照会プランセットから選択される。具体的には、最小コストの照会プランが、照会を実行するために等コスト照会プランセットから選択され、照会結果が返されてもよい。
【００８５】
本発明のこの実施形態における等コスト照会プランセットは、元の照会プランのすべての等コスト照会プランを含むため、本発明のこの実施形態では、最適な照会プランを選択することができる。異なる照会プランの性能が数十倍、さらには数百倍異なることを考えると、本発明のこの実施形態の方法を使用することにより、データ照会性能を大幅に向上させることができる。
【００８６】
したがって、本発明のこの実施形態のデータ照会方法によれば、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、元の照会プランの等コスト照会プランが決定され、元の照会プランのすべての等コスト照会プランが取得され得るため、データ照会のパフォーマンスを向上させることができる。
【００８７】
本発明のこの実施形態における等コスト照会プランセットは、4つの演算レベル規則および3つの述語レベル規則の少なくとも1つを使用して変換することにより元の照会プランから取得され得るすべての照会プランを含む。元の照会プランの等コスト照会プランを決定するための方法は、上記のステップS1140〜S1170で与えられる。以下では、具体例を参照して、元の照会プランの等コスト照会プランを決定するための方法を詳細に説明する。これは、当業者が本発明のこの実施形態をよりよく理解するのを助けることを意図しているに過ぎず、本発明のこの実施形態の範囲を限定することを意図していないことに留意されたい。
【００８８】
図16は、3つの照会プランP、P’、およびP”を示す。∞は内部結合演算を表し、
【００８９】
【数１】
2019504390.tif 000009
【００９０】
は左反結合を表し、Pは元の照会プランであり、P’およびP”は候補照会プランである。候補照会プランP’およびP”が元の照会プランPと等価であるかどうかは、以下の方法で判定され得る。
【００９１】
1．元の照会プランPの結合述語が再構成され、再構成された結合述語の基本情報が決定され、Pは、3つの結合演算（すなわち、∞p14∧p34、
【００９２】
【数２】
2019504390.tif 000010
【００９３】
、および∞p12）を含む。結合演算∞p14∧p34に関して、結合演算は内部結合であるため、結合演算の述語は連言標準形に変換する必要がある（p14∧p34の連言標準形はp14∧p34である）。p14およびp34の入力テーブルは異なるため、p14およびp34は、1つの述語に組み合わせることができない。結合演算
【００９４】
【数３】
2019504390.tif 000011
【００９５】
に関して、結合演算は内部結合ではないため、結合演算の述語（すなわち、p23）は1つの述語とみなされる。同様に、結合演算∞p12の述語は、再構成された後でも依然としてp12である。述語が再構成された後、再構成された述語の基本情報が決定される。表7に、Pの再構成された述語の基本情報を示す。
【００９６】
【表７】
2019504390.tif 000012
【００９７】
2．再構成された結合述語の制約条件が決定される。すなわち、演算∞p14∧p34は2つの下位演算（すなわち、∞p12および
【００９８】
【数４】
2019504390.tif 000013
【００９９】
）を有するので、述語p14およびp34の制約条件を取得するために、2つの下位演算および演算が対応する規則を満たすかどうかを判定する必要がある。下位演算∞p12および演算∞p14∧p34は、演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たし、演算レベル左置換規則および述語レベル左置換規則をさらに満たすため、制約規則を追加する必要はない。下位演算
【０１００】
【数５】
2019504390.tif 000014
【０１０１】
および演算∞p14∧p34は、演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさないため、p14およびp34に規則R3−＞R2を追加する必要がある。さらに、
【０１０２】
【数６】
2019504390.tif 000015
【０１０３】
および演算∞p14∧p34は、述語レベル左置換規則を満たさないが、演算レベル左置換規則を満たすため、制約規則をさらに追加する必要はない。同様に、演算∞p12および
【０１０４】
【数７】
2019504390.tif 000016
【０１０５】
ならびに演算∞p12および
【０１０６】
【数８】
2019504390.tif 000017
【０１０７】
の下位演算の述語の制約条件は、演算∞p12および
【０１０８】
【数９】
2019504390.tif 000018
【０１０９】
ならびに演算∞p12および
【０１１０】
【数１０】
2019504390.tif 000019
【０１１１】
の下位演算が対応する規則を満たすかどうかを判定することによって取得され得る。表8に、元の照会プランPの再構成された述語の制約条件を示す。
【０１１２】
【表８】
2019504390.tif 000020
【０１１３】
3．等コスト照会プランが、基本情報および述語の制約条件に従って決定される。すなわち、候補照会プランP’は結合タイプの一貫性に違反するため、P’は元の照会プランPと等価ではない（P’のルートノードの演算は2つの述語を含むが、ノードの演算タイプは内部結合ではなく、p23に対応する、Pの演算の結合タイプも内部結合ではない）。候補照会プランP”は、結合タイプの一貫性（P”の演算∞p12∧p34は内部結合であり、p12およびp34に対応する、元の照会Pの演算も内部結合である）と、入力テーブル情報の一貫性（P”の述語の入力テーブル情報およびテーブルの述語の入力テーブル情報が一貫する）と、制約条件の一貫性（P”の述語がテーブルに示された制約条件を満たす）とを満たすため、P”は、元の照会プランPと等価である。
【０１１４】
本発明のこの実施形態における、等コスト照会プランを決定するための方法によれば、元の照会プランのすべての等コスト照会プランを取得することができ、データ照会性能を向上させることができる。
【０１１５】
上記のプロセスのシーケンス番号は、本発明の様々な実施形態において実行順序を意味するものではないことを理解されたい。プロセスの実行順序は、プロセスの機能および内部論理に従って決定されるべきであり、本発明の実施形態の実施プロセスへの制限として解釈されるべきではない。
【０１１６】
以上、本発明の一実施形態によるデータ照会方法について詳細に説明した。以下では、本発明の一実施形態によるデータ照会装置およびデータベースシステムについて説明する。データ照会装置およびデータベースシステムは、本発明の上記の実施形態におけるデータ照会方法を実行することができる。
【０１１７】
図17は、本発明の一実施形態によるデータ照会装置1700の概略ブロック図を示す。装置1700は、データベースシステム内の装置、例えば照会オプティマイザであってもよい。図17に示すように、装置1700は、
データ照会要求を受信するように構成される受信モジュール1710と、
データ照会要求に従って元の照会プランを生成するように構成される生成モジュール1720と、
元の照会プランの結合述語を再構成するように構成される再構成モジュール1740と、
決定モジュール1750であって、元の照会プランの再構成された結合述語の基本情報を決定し、結合演算規則に基づいて、元の照会プランの再構成された結合述語の制約条件を決定し、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定するように構成される決定モジュール1750と、
元の照会プランの等コスト照会プランに従って照会を実行するように構成される照会モジュール1780と
を含む。
【０１１８】
本発明のこの実施形態のデータ照会装置によれば、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、元の照会プランの等コスト照会プランが決定され、元の照会プランのすべての等コスト照会プランが取得され得るため、データ照会のパフォーマンスを向上させることができる。
【０１１９】
任意選択的に、本発明の一実施形態では、決定モジュール1750は、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランセットを決定するように特に構成され、
照会モジュール1780は、照会を実行するために等コスト照会プランセットから照会プランを選択するように特に構成される。
【０１２０】
任意選択的に、本発明の一実施形態では、装置1700は、
元の照会プランに従って候補照会プランセットを取得するように構成される取得モジュール1730
をさらに含んでもよく、
決定モジュール1750は、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って候補照会プランセットから等コスト照会プランセットを決定するように特に構成される。
【０１２１】
任意選択的に、本発明の一実施形態では、再構成モジュール1740は、
元の照会プランの内部結合演算のすべての結合述語を連言標準形に変換し、同じ入力テーブルを有する結合述語を組み合わせ、
元の照会プランの非内部結合演算のすべての結合述語を1つの結合述語に組み合わせるように特に構成される。
【０１２２】
任意選択的に、本発明の一実施形態では、結合述語の基本情報は、結合述語の入力テーブルと、結合述語が位置する結合演算の左サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の右サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の結合タイプとを含む。
【０１２３】
任意選択的に、本発明の一実施形態では、結合演算規則は、演算レベル規則および述語レベル規則を含み、演算レベル規則は、演算レベル交換規則：e1 oap12 e2＝e2 oap12 e1、演算レベル組み合わせ規則：（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）、演算レベル左置換規則：（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2、および演算レベル右置換規則：e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）を含み、述語レベル規則は、述語レベル組み合わせ規則：（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）、述語レベル左置換規則：（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2、および述語レベル右置換規則：e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）を含み、eiは照会式であり、oaおよびobは結合演算であり、pijはeiとejとの結合述語である。
【０１２４】
任意選択的に、本発明の一実施形態では、決定モジュール1750は、
元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAをトラバースし、
oAが、oBをルートノードとして使用するサブツリーの左サブツリー内にあるときに、oAおよびoBが演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが演算レベル左置換規則および述語レベル左置換規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、
oAが、oBをルートノードとして使用するサブツリーの右サブツリー内にあるときに、oAおよびoBが演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが演算レベル右置換規則および述語レベル右置換規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加する
ように特に構成され、
第1の制約条件は、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、第2の制約条件は、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAをルートノードとして使用するサブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、第1のサブツリーがT2のすべての入力テーブルを含むことを示す。
【０１２５】
任意選択的に、本発明の一実施形態では、決定モジュール1750は、
第1の候補照会プランP’が以下の条件を満たす場合に、P’は元の照会プランPの等コスト照会プランであると決定する
ように特に構成され、この以下の条件は、
P’の各第1の結合演算の結合タイプが内部結合であり、第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件、
P’の各結合演算ob’の各結合述語pに関して、
ob’が演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する結合演算の右サブツリーに含まれるpの入力テーブルを示し、
ob’が演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件である。
【０１２６】
任意選択的に、本発明の一実施形態では、照会モジュール1780は、
照会を実行するために等コスト照会プランセットから最小コストの照会プランを選択する
ように特に構成される。
【０１２７】
本発明のこの実施形態によるデータ照会装置1700は、本発明の実施形態によるデータ照会方法の実行主体に対応してもよく、装置1700のモジュールの上記の他の演算および／または機能は、それぞれ上記の方法の対応する手順を実施するために使用される。簡潔にするために、ここでは詳細は再度説明しない。
【０１２８】
図18は、本発明の一実施形態によるデータベースシステム1800の概略ブロック図を示す。図18に示すように、データベースシステム1800は、本発明の実施形態による上記のデータ照会装置1700と、データベース1810とを含む。データベースシステム1800は、本発明の実施形態によるデータ照会方法を実行し、データベース1810において照会を実行することができる。
【０１２９】
図19は、本発明の別の実施形態によるデータ照会装置の構成を示す。装置は、少なくとも1つのプロセッサ1902（例えばCPU）と、少なくとも1つのネットワークインタフェース1905または別の通信インタフェースと、メモリ1906と、これらの装置間の接続および通信を実施するように構成される少なくとも1つの通信バス1903とを含む。プロセッサ1902は、メモリ1906に格納された実行可能モジュール（コンピュータプログラムなど）を実行するように構成される。メモリ1906は、高速ランダム・アクセス・メモリ（RAM、Random Access Memory）を含んでもよく、また、少なくとも1つの磁気ディスクメモリなどの不揮発性メモリ（non−volatile memory）をさらに含んでもよい。少なくとも1つの他のネットワーク要素との通信接続は、少なくとも1つのネットワークインタフェース1905（有線であっても無線であってもよい）を使用して実施される。
【０１３０】
一部の実施態様では、メモリ1906は、プログラム19061を格納し、プロセッサ1902は、本発明の上記の実施形態によるデータ照会方法を実行するためにプログラム19061を実行する。
【０１３１】
本発明のこの実施形態における「および／または」という用語は、関連する対象を説明するための関連の関係のみを説明しており、3つの関係が存在し得ることを表すことを理解されたい。例えば、Aおよび／またはBは、以下の3つのケース、すなわち、Aのみが存在するケース、AおよびBの両方が存在するケース、Bのみが存在するケースを表すことができる。さらに、本明細書中の記号「／」は、一般に、互いに関連付けられる対象間の「または」関係を示す。
【０１３２】
当業者であれば、本明細書に開示されている実施形態に記載された例との組み合わせにおいて、ユニットおよびアルゴリズムステップが、電子ハードウェア、コンピュータソフトウェア、またはこれらの組み合わせによって実施され得ることに気づくことができる。ハードウェアとソフトウェアとの互換性を明確に説明するために、上では、機能に応じて各例の構成およびステップを一般的に説明した。機能がハードウェアとソフトウェアのどちらによって実行されるかは、技術的解決策の特定の用途および設計制約条件に依存する。当業者であれば、特定の用途ごとに、説明された機能を実施する異なる方法を使用し得るが、その実施は本発明の範囲を超えると考えられるべきではない。
【０１３３】
簡便かつ簡単な説明のために、上記のシステム、装置、およびユニットの詳細な動作プロセスについては、上記の方法の実施形態における対応するプロセスを参照することができ、ここでは詳細を再度説明していないことが、当業者によって明確に理解され得る。
【０１３４】
本出願で提供されるいくつかの実施形態において、開示されたシステム、装置、および方法が他の方法で実施され得ることを理解されたい。例えば、説明した装置の実施形態は単なる例である。例えば、ユニットの分割は、論理的な機能の分割に過ぎず、実際の実施では他の分割であってもよい。例えば、複数のユニットまたはコンポーネントが、別のシステムとして組み合わされるか、もしくは統合されてもよいし、一部の特徴が、無視されるか、もしくは実行されなくてもよい。さらに、提示または叙述された相互結合または直接結合または通信接続は、装置またはユニット間のいくつかのインタフェース、間接結合、もしくは通信接続または電気的接続、機械的接続、もしくは他の形態の接続によって実施されてもよい。
【０１３５】
別々の部分として説明されているユニットは、物理的に別々であってもなくてもよく、ユニットとして提示されている部分は、物理的なユニットであってもなくてもよく、1つの位置に配置されても、複数のネットワークユニットに分散されてもよい。ユニットの一部または全部は、本発明の実施形態の解決策の目的を達成するために実際の必要に応じて選択されてもよい。
【０１３６】
さらに、本発明の実施形態における機能ユニットは、1つの処理ユニットに統合されてもよいし、これらのユニットの各々は、物理的に単独で存在してもよいし、2つ以上のユニットが、1つのユニットに統合される。統合ユニットは、ハードウェアの形態で実施されてもよいし、ソフトウェア機能ユニットの形態で実施されてもよい。
【０１３７】
統合ユニットが、ソフトウェア機能ユニットの形態で実施され、独立した製品として販売または使用される場合、統合ユニットは、コンピュータ可読記憶媒体に格納されてもよい。そのような理解に基づいて、本質的に、本発明の技術的解決策、または従来技術に寄与する部分、または技術的解決策の全部もしくは一部は、ソフトウェア製品の形態で実施されてもよい。ソフトウェア製品は、記憶媒体に格納され、コンピュータデバイス（パーソナルコンピュータ、サーバ、またはネットワークデバイスであってもよい）に、本発明の実施形態で説明した方法のステップの全部または一部を実行するように命令するためのいくつかの命令を含む。上記の記憶媒体は、プログラムコードを格納することができる任意の媒体（USBフラッシュドライブ、リムーバブル・ハード・ディスク、読み出し専用メモリ（ROM、Read−Only Memory）、ランダム・アクセス・メモリ（RAM、Random Access Memory）、磁気ディスク、または光ディスクなど）を含む。
【０１３８】
上記の説明は、本発明の特定の実施形態に過ぎず、本発明の保護範囲を限定するものではない。本発明で開示された技術的範囲内で当業者により容易に想到される修正例または置換例は、本発明の保護範囲内に含まれるものとする。したがって、本発明の保護範囲は、特許請求の範囲の保護範囲に従うものとする。
【符号の説明】
【０１３９】
1100  データ照会方法
1700  データ照会装置
1710  受信モジュール
1720  生成モジュール
1730  取得モジュール
1740  再構成モジュール
1750  決定モジュール
1780  照会モジュール
1800  データベースシステム
1810  データベース
1902  プロセッサ
1903  通信バス
1905  ネットワークインタフェース
1906  メモリ
19061  プログラム
【図１ａ】
2019504390.tif 000021
【図１ｂ】
2019504390.tif 000022
【図１ｃ】
2019504390.tif 000023
【図２】
2019504390.tif 000024
【図３】
2019504390.tif 000025
【図４】
2019504390.tif 000026
【図５】
2019504390.tif 000027
【図６】
2019504390.tif 000028
【図７】
2019504390.tif 000029
【図８】
2019504390.tif 000030
【図９】
2019504390.tif 000031
【図１０】
2019504390.tif 000032
【図１１】
2019504390.tif 000033
【図１２】
2019504390.tif 000034
【図１３Ａ】
2019504390.tif 000035
【図１３Ｂ】
2019504390.tif 000036
【図１４】
2019504390.tif 000037
【図１５】
2019504390.tif 000038
【図１６】
2019504390.tif 000039
【図１７】
2019504390.tif 000040
【図１８】
2019504390.tif 000041
【図１９】
2019504390.tif 000042
【手続補正書】
【提出日】平成30年7月9日(2018.7.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ照会方法であって、前記方法がデータベースシステムによって実行され、前記データベースシステムがコンピュータデバイス上で動作し、前記方法が、
データ照会要求を受信するステップと、
前記データ照会要求に従って元の照会プランを生成するステップと、
前記元の照会プランの結合述語を再構成するステップと、
前記元の照会プランの再構成された結合述語の基本情報を決定するステップと、
結合演算規則に基づいて、前記元の照会プランの前記再構成された結合述語の制約条件を決定するステップと、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定するステップと、
前記元の照会プランの前記等コスト照会プランに従って照会を実行するステップと
を含む、データ照会方法。
【請求項２】
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定する前記ステップが、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランセットを決定するステップ
を含み、
前記元の照会プランの前記等コスト照会プランに従って照会を実行する前記ステップが、
照会を実行するために前記等コスト照会プランセットから照会プランを選択するステップ
を含む、請求項1に記載の方法。
【請求項３】
前記方法が、
前記元の照会プランに従って候補照会プランセットを取得するステップ
をさらに含み、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランセットを決定する前記ステップが、
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記候補照会プランセットから前記等コスト照会プランセットを決定するステップ
を含む、請求項2に記載の方法。
【請求項４】
前記元の照会プランの結合述語を再構成する前記ステップが、
前記元の照会プランの内部結合演算のすべての結合述語を連言標準形に変換し、同じ入力テーブルを有する結合述語を組み合わせるステップと、
前記元の照会プランの非内部結合演算のすべての結合述語を1つの結合述語に組み合わせるステップと
を含む、請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記結合述語の前記基本情報が、前記結合述語の入力テーブルと、前記結合述語が位置する結合演算の左サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の右サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の結合タイプとを含む、請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記結合演算規則が、演算レベル規則および述語レベル規則を含み、前記演算レベル規則が、演算レベル交換規則：e1 oap12 e2＝e2 oap12 e1、演算レベル組み合わせ規則：（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）、演算レベル左置換規則：（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2、および演算レベル右置換規則：e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）を含み、前記述語レベル規則が、述語レベル組み合わせ規則：（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）、述語レベル左置換規則：（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2、および述語レベル右置換規則：e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）を含み、eiは照会式であり、oaおよびobは結合演算であり、pijはeiとejとの結合述語である、請求項1から5のいずれか一項に記載の方法。
【請求項７】
結合演算規則に基づいて、前記元の照会プランの前記再構成された結合述語の制約条件を決定する前記ステップが、
前記元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAをトラバースするステップ、および
oAが、oBを前記ルートノードとして使用する前記サブツリーの左サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル左置換規則および前記述語レベル左置換規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加するステップ、または
oAが、oBを前記ルートノードとして使用する前記サブツリーの右サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル右置換規則および前記述語レベル右置換規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加するステップ
を含み、
前記第1の制約条件が、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、前記第2の制約条件が、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAを前記ルートノードとして使用する前記サブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、前記第1のサブツリーがT2のすべての入力テーブルを含むことを示す、
請求項6に記載の方法。
【請求項８】
前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定する前記ステップが、
第1の候補照会プランP’が以下の条件を満たす場合に、P’は前記元の照会プランPの等コスト照会プランであると決定するステップであって、以下の条件が、
P’の各第1の結合演算の結合タイプが内部結合であり、前記第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、前記少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件、
P’の各結合演算ob’の各結合述語pに関して、
ob’が前記演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する前記結合演算の右サブツリーに含まれるpの入力テーブルを示し、または
ob’が前記演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件である、ステップ
を含む、請求項1から7のいずれか一項に記載の方法。
【請求項９】
照会を実行するために前記等コスト照会プランセットから照会プランを選択する前記ステップが、
照会を実行するために前記等コスト照会プランセットから最小コストの照会プランを選択するステップ
を含む、請求項2に記載の方法。
【請求項１０】
データ照会装置であって、
データ照会要求を受信するように構成される受信モジュールと、
前記データ照会要求に従って元の照会プランを生成するように構成される生成モジュールと、
前記元の照会プランの結合述語を再構成するように構成される再構成モジュールと、
前記元の照会プランの再構成された結合述語の基本情報を決定し、結合演算規則に基づいて、前記元の照会プランの前記再構成された結合述語の制約条件を決定し、前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランを決定するように構成される決定モジュールと、
前記元の照会プランの前記等コスト照会プランに従って照会を実行するように構成される照会モジュールと
を備える、データ照会装置。
【請求項１１】
前記決定モジュールが、前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記元の照会プランの等コスト照会プランセットを決定するように特に構成され、
前記照会モジュールが、照会を実行するために前記等コスト照会プランセットから照会プランを選択するように特に構成される、
請求項10に記載の装置。
【請求項１２】
前記装置が、
前記元の照会プランに従って候補照会プランセットを取得するように構成される取得モジュール
をさらに備え、
前記決定モジュールが、前記元の照会プランの前記再構成された結合述語の前記基本情報および前記元の照会プランの前記再構成された結合述語の前記制約条件に従って前記候補照会プランセットから前記等コスト照会プランセットを決定するように特に構成される、
請求項11に記載の装置。
【請求項１３】
前記再構成モジュールが、
前記元の照会プランの内部結合演算のすべての結合述語を連言標準形に変換し、同じ入力テーブルを有する結合述語を組み合わせ、
前記元の照会プランの非内部結合演算のすべての結合述語を1つの結合述語に組み合わせる
ように特に構成される、請求項10から12のいずれか一項に記載の装置。
【請求項１４】
前記結合述語の前記基本情報が、前記結合述語の入力テーブルと、前記結合述語が位置する結合演算の左サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の右サブツリーに含まれる前記結合述語の入力テーブルと、前記結合述語が位置する前記結合演算の結合タイプとを含む、請求項10から13のいずれか一項に記載の装置。
【請求項１５】
前記結合演算規則が、演算レベル規則および述語レベル規則を含み、前記演算レベル規則が、演算レベル交換規則：e1 oap12 e2＝e2 oap12 e1、演算レベル組み合わせ規則：（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）、演算レベル左置換規則：（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2、および演算レベル右置換規則：e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）を含み、前記述語レベル規則が、述語レベル組み合わせ規則：（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）、述語レベル左置換規則：（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2、および述語レベル右置換規則：e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）を含み、eiは照会式であり、oaおよびobは結合演算であり、pijはeiとejとの結合述語である、請求項10から14のいずれか一項に記載の装置。
【請求項１６】
前記決定モジュールが、
前記元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAをトラバースし、
oAが、oBを前記ルートノードとして使用する前記サブツリーの左サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル左置換規則および前記述語レベル左置換規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加するか、または
oAが、oBを前記ルートノードとして使用する前記サブツリーの右サブツリー内にあるときに、oAおよびoBが前記演算レベル組み合わせ規則および前記述語レベル組み合わせ規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが前記演算レベル右置換規則および前記述語レベル右置換規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加する
ように特に構成され、
前記第1の制約条件が、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、前記第2の制約条件が、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAを前記ルートノードとして使用する前記サブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、前記第1のサブツリーがT2のすべての入力テーブルを含むことを示す、
請求項15に記載の装置。
【請求項１７】
前記決定モジュールが、
第1の候補照会プランP’が以下の条件を満たす場合に、P’は前記元の照会プランPの等コスト照会プランであると決定するように特に構成され、以下の条件が、
P’の各第1の結合演算の結合タイプが内部結合であり、前記第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、前記少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件、
P’の各結合演算ob’の各結合述語pに関して、
ob’が前記演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する前記結合演算の右サブツリーに含まれるpの入力テーブルを示し、または
ob’が前記演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件である、
請求項10から16のいずれか一項に記載の装置。
【請求項１８】
前記照会モジュールが、
照会を実行するために前記等コスト照会プランセットから最小コストの照会プランを選択する
ように特に構成される、請求項11に記載の装置。
【請求項１９】
請求項10から18のいずれか一項に記載のデータ照会装置とデータベースとを備えるデータベースシステム。
【請求項２０】
コンピュータに請求項1から9のいずれか一項に記載のデータ照会方法を実行させるように構成されたコンピュータプログラム。
【請求項２１】
請求項２０に記載のコンピュータプログラムを記憶するコンピュータ読み取り可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本開示は、情報技術の分野に関し、より具体的には、データ照会方法および装置ならびにデータベースシステムに関する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
本開示は、データ照会性能を向上させるために、データ照会方法および装置ならびにデータベースシステムを提供する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
本開示は、データ照会性能を向上させるために、データ照会方法および装置ならびにデータベースシステムを提供する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
第1の態様によれば、本開示の一実施形態は、データ照会方法であって、方法がデータベースシステムによって実行され、データベースシステムがコンピュータデバイス上で動作し、本方法が、
データ照会要求を受信するステップと、
データ照会要求に従って元の照会プランを生成するステップと、
元の照会プランの結合述語を再構成するステップと、
元の照会プランの再構成された結合述語の基本情報を決定するステップと、
結合演算規則に基づいて、元の照会プランの再構成された結合述語の制約条件を決定するステップと、
元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定するステップと、
元の照会プランの等コスト照会プランに従って照会を実行するステップと
を含む、データ照会方法を提供する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
本開示の実施形態では、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、元の照会プランの等コスト照会プランが決定され、元の照会プランの相対的に多量の等コスト照会プランが取得され得るため、データ照会のパフォーマンスを向上させることができる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
本開示の実施形態では、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、候補照会プランセットから元の照会プランの等コスト照会プランが決定され、元の照会プランのすべての等コスト照会プランが取得され得るため、データ照会のパフォーマンスをさらに向上させることができる。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
第2の態様によれば、本開示の一実施形態は、データ照会装置を提供する。本装置は、第1の態様による方法を実行するためのモジュールを含む。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
第3の態様によれば、本開示の一実施形態は、データ照会装置を提供する。本装置は、プロセッサと、メモリと、通信インタフェースとを含む。プロセッサは、メモリおよび通信インタフェースに結合される。メモリは、命令を格納するように構成され、プロセッサは、命令を実行するように構成され、通信インタフェースは、プロセッサの制御下で別のネットワーク要素と通信するように構成される。プロセッサは、プロセッサが命令を実行したときに、第1の態様による方法を実行する。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
第4の態様によれば、本開示の一実施形態は、データベースシステムを提供する。データベースシステムは、第2の態様または第3の態様によるデータ照会装置とデータベースとを含む。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
本開示の実施形態の技術的解決策をより明確に説明するために、以下では、本開示の実施形態を説明するために必要な添付図面について簡単に説明する。明らかに、以下の説明における添付図面は、本開示の一部の実施形態しか示しておらず、当業者は、創造的な努力なしにこれらの添付図面から他の図面をさらに得ることができる。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
【図１ａ】本開示の一実施形態による適用シナリオの概略図である。
【図１ｂ】本開示の一実施形態による別の適用シナリオの概略図である。
【図１ｃ】本開示の一実施形態による結合演算の一例である。
【図２】本開示の一実施形態による、等コスト照会プランの一例である。
【図３】本開示の一実施形態による演算レベル交換規則の一例である。
【図４】本開示の一実施形態による演算レベル組み合わせ規則の一例である。
【図５】本開示の一実施形態による演算レベル左置換規則の一例である。
【図６】本開示の一実施形態による演算レベル右置換規則の一例である。
【図７】本開示の一実施形態による述語レベル組み合わせ規則の一例である。
【図８】本開示の一実施形態による述語レベル左置換規則の一例である。
【図９】本開示の一実施形態による述語レベル右置換規則の一例である。
【図１０】本開示の一実施形態による、等コスト照会プランの一例である。
【図１１】本開示の一実施形態によるデータ照会方法の概略フローチャートである。
【図１２】本開示の一実施形態による照会プランの一例である。
【図１３Ａ】本開示の一実施形態による元の照会プランの述語の制約条件を決定するフローチャートの前半である。
【図１３Ｂ】本開示の一実施形態による元の照会プランの述語の制約条件を決定するフローチャートの後半である。
【図１４】本開示の一実施形態による制約条件の追加の概略図である。
【図１５】本開示の一実施形態による制約条件の追加の別の概略図である。
【図１６】本開示の一実施形態による等コスト照会プランを決定する例である。
【図１７】本開示の一実施形態によるデータ照会装置の概略ブロック図である。
【図１８】本開示の一実施形態によるデータベースシステムの概略ブロック図である。
【図１９】本開示の一実施形態によるデータ照会装置の概略構成図である。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
以下では、本開示の実施形態の添付図面を参照しながら、本開示の実施形態の技術的解決策を明確かつ完全に説明する。明らかに、説明されている実施形態は、本開示の実施形態のすべてではなく、その一部である。創造的な努力なしに本開示の実施形態に基づいて当業者によって得られる他のすべての実施形態は、本開示の保護範囲内に含まれるものとする。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
本開示の実施形態における技術的解決策は、データベースシステムに適用することができる。図1aおよび図1bは、本開示の一実施形態による適用シナリオの概略図である。図1aは、単一のサーバを有するデータベースシステムであり、図1bは、分散データベースシステムである。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
図1aに示すように、単一のサーバを有するデータベースシステム（すなわち、サーバ）は、データベース管理システムおよびデータベースを含み、クライアントの照会要求を処理し、照会結果をクライアントに返すように構成される。データベース管理システムは、照会オプティマイザなどの管理コンポーネントを含み、データベースシステムを管理するように構成される。このシナリオでは、本開示の実施形態における方法は、サーバ、またはサーバのデータベース管理システム、またはデータベース管理システムの照会オプティマイザによって実行され得る。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
図1bに示すように、分散データベースシステムは、複数のサーバおよび分散管理システムを含み、クライアントの照会要求を処理し、照会結果をクライアントに返すように構成される。各サーバは、データベース管理システムおよびデータベースを含み、分散管理システムは、照会オプティマイザなどの管理コンポーネントを含み、分散データベースシステムを管理するように構成される。このシナリオでは、本開示の実施形態における方法は、分散データベースシステム、または分散データベースシステムの分散管理システム、または分散管理システムの照会オプティマイザによって実行され得る。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
本開示の実施形態の理解を容易にするために、以下ではまずデータベースシステムに関する用語を説明する。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
本開示の様々な実施形態において、結合演算は、演算または結合と呼ばれる場合もあり、また、結合演算は、データベース内の2つ以上のテーブルを1つの結果テーブルに組み合わせる。結合述語は述語と呼ばれる場合もあり、また、結合述語は、2つ以上のテーブルの列の関係を記述するために使用される。結合演算は、結合述語を使用してデータベース内のテーブルを組み合わせる。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
本開示の様々な実施形態では、結合演算規則は、演算レベル規則および述語レベル規則を含む。演算レベル規則は、演算レベル交換規則、演算レベル組み合わせ規則、演算レベル左置換規則、および演算レベル右置換規則を含む。述語レベル規則は、述語レベル組み合わせ規則、述語レベル左置換規則、および述語レベル右置換規則を含む。以下の説明において、各記号の意味を表1に示す。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
本開示の実施形態では、上記の演算レベル規則または述語レベル規則を使用して変換することにより取得され得るすべての照会プランは、等コスト照会プランである。すなわち、本開示の実施形態における等コスト照会プラン空間は、4つの演算レベル規則および3つの述語レベル規則の少なくとも1つを使用して変換することにより取得され得るすべての照会プランである。規則が演算間で満たされるかどうかは、規則の結合演算テーブルに問い合わせることによって判定され得る。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
演算レベル規則のみを使用して変換することにより得られる等コスト照会プラン空間と比較して、本開示の実施形態の等コスト照会プラン空間はより完全である。すなわち、演算レベル規則のみを使用して変換を行う場合、すべての等コスト照会プランを取得することができない。例えば、図10に示すように、左の元の照会プランに対して、右の2つの候補照会プランでは、演算間で結合述語を移動させているため、上記の4つの演算レベル規則を使用して左の元の照会プランを変換することによっては、これらの2つの候補照会プランは取得することができない。なお、2つの右の候補照会プランは、実際には左の元の照会プランと等価である。
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００５４
【補正方法】変更
【補正の内容】
【００５４】
本開示の実施形態では、元の照会プランの等コスト照会プランは、演算レベル規則および述語レベル規則に基づいて決定され、元の照会プランのすべての等コスト照会プランを取得することができる。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】変更
【補正の内容】
【００５５】
図11は、本開示の一実施形態によるデータ照会方法1100の概略フローチャートである。方法1100は、データベースシステムによって実行され、データベースシステムは、コンピュータデバイス上で動作する。具体的には、本方法は、コンピュータ上で動作するデータ照会装置によって実行される。データ照会装置は、照会オプティマイザなどの、データベースシステム内の装置であってもよいし、データベースシステムであってもよい。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
このステップは任意選択のステップである。すなわち、本開示のこの実施形態では、以下のステップを使用して、等コスト照会プランまたは等コスト照会プランセットを元の照会プランから直接取得してもよいし、以下のステップを使用して、等コスト照会プランセットを候補照会プランセットから取得してもよい。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
本開示の様々な実施形態において、結合述語の基本情報は、結合述語の入力テーブルと、結合述語が位置する結合演算の左サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の右サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の結合タイプとを含む。
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
元の照会プランのすべての等コスト照会プランは、上記の方法で取得することができる。すなわち、本開示のこの実施形態で取得される等コスト照会プランセットは最も完全である。
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】００８５
【補正方法】変更
【補正の内容】
【００８５】
本開示のこの実施形態における等コスト照会プランセットは、元の照会プランのすべての等コスト照会プランを含むため、本開示のこの実施形態では、最適な照会プランを選択することができる。異なる照会プランの性能が数十倍、さらには数百倍異なることを考えると、本開示のこの実施形態の方法を使用することにより、データ照会性能を大幅に向上させることができる。
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】変更
【補正の内容】
【００８６】
したがって、本開示のこの実施形態のデータ照会方法によれば、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、元の照会プランの等コスト照会プランが決定され、元の照会プランのすべての等コスト照会プランが取得され得るため、データ照会のパフォーマンスを向上させることができる。
【手続補正２９】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】変更
【補正の内容】
【００８７】
本開示のこの実施形態における等コスト照会プランセットは、4つの演算レベル規則および3つの述語レベル規則の少なくとも1つを使用して変換することにより元の照会プランから取得され得るすべての照会プランを含む。元の照会プランの等コスト照会プランを決定するための方法は、上記のステップS1140〜S1170で与えられる。以下では、具体例を参照して、元の照会プランの等コスト照会プランを決定するための方法を詳細に説明する。これは、当業者が本開示のこの実施形態をよりよく理解するのを助けることを意図しているに過ぎず、本開示のこの実施形態の範囲を限定することを意図していないことに留意されたい。
【手続補正３０】
【補正対象書類名】明細書
【補正対象項目名】０１１４
【補正方法】変更
【補正の内容】
【０１１４】
本開示のこの実施形態における、等コスト照会プランを決定するための方法によれば、元の照会プランのすべての等コスト照会プランを取得することができ、データ照会性能を向上させることができる。
【手続補正３１】
【補正対象書類名】明細書
【補正対象項目名】０１１５
【補正方法】変更
【補正の内容】
【０１１５】
上記のプロセスのシーケンス番号は、本開示の様々な実施形態において実行順序を意味するものではないことを理解されたい。プロセスの実行順序は、プロセスの機能および内部論理に従って決定されるべきであり、本開示の実施形態の実施プロセスへの制限として解釈されるべきではない。
【手続補正３２】
【補正対象書類名】明細書
【補正対象項目名】０１１６
【補正方法】変更
【補正の内容】
【０１１６】
以上、本開示の一実施形態によるデータ照会方法について詳細に説明した。以下では、本開示の一実施形態によるデータ照会装置およびデータベースシステムについて説明する。データ照会装置およびデータベースシステムは、本開示の上記の実施形態におけるデータ照会方法を実行することができる。
【手続補正３３】
【補正対象書類名】明細書
【補正対象項目名】０１１７
【補正方法】変更
【補正の内容】
【０１１７】
図17は、本開示の一実施形態によるデータ照会装置1700の概略ブロック図を示す。装置1700は、データベースシステム内の装置、例えば照会オプティマイザであってもよい。図17に示すように、装置1700は、
データ照会要求を受信するように構成される受信モジュール1710と、
データ照会要求に従って元の照会プランを生成するように構成される生成モジュール1720と、
元の照会プランの結合述語を再構成するように構成される再構成モジュール1740と、
決定モジュール1750であって、元の照会プランの再構成された結合述語の基本情報を決定し、結合演算規則に基づいて、元の照会プランの再構成された結合述語の制約条件を決定し、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランを決定するように構成される決定モジュール1750と、
元の照会プランの等コスト照会プランに従って照会を実行するように構成される照会モジュール1780と
を含む。
【手続補正３４】
【補正対象書類名】明細書
【補正対象項目名】０１１８
【補正方法】変更
【補正の内容】
【０１１８】
本開示のこの実施形態のデータ照会装置によれば、述語の基本情報と結合演算規則に基づいて取得される制約条件とに従って、元の照会プランの等コスト照会プランが決定され、元の照会プランのすべての等コスト照会プランが取得され得るため、データ照会のパフォーマンスを向上させることができる。
【手続補正３５】
【補正対象書類名】明細書
【補正対象項目名】０１１９
【補正方法】変更
【補正の内容】
【０１１９】
任意選択的に、本開示の一実施形態では、決定モジュール1750は、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って元の照会プランの等コスト照会プランセットを決定するように特に構成され、
照会モジュール1780は、照会を実行するために等コスト照会プランセットから照会プランを選択するように特に構成される。
【手続補正３６】
【補正対象書類名】明細書
【補正対象項目名】０１２０
【補正方法】変更
【補正の内容】
【０１２０】
任意選択的に、本開示の一実施形態では、装置1700は、
元の照会プランに従って候補照会プランセットを取得するように構成される取得モジュール1730
をさらに含んでもよく、
決定モジュール1750は、元の照会プランの再構成された結合述語の基本情報および元の照会プランの再構成された結合述語の制約条件に従って候補照会プランセットから等コスト照会プランセットを決定するように特に構成される。
【手続補正３７】
【補正対象書類名】明細書
【補正対象項目名】０１２１
【補正方法】変更
【補正の内容】
【０１２１】
任意選択的に、本開示の一実施形態では、再構成モジュール1740は、
元の照会プランの内部結合演算のすべての結合述語を連言標準形に変換し、同じ入力テーブルを有する結合述語を組み合わせ、
元の照会プランの非内部結合演算のすべての結合述語を1つの結合述語に組み合わせるように特に構成される。
【手続補正３８】
【補正対象書類名】明細書
【補正対象項目名】０１２２
【補正方法】変更
【補正の内容】
【０１２２】
任意選択的に、本開示の一実施形態では、結合述語の基本情報は、結合述語の入力テーブルと、結合述語が位置する結合演算の左サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の右サブツリーに含まれる結合述語の入力テーブルと、結合述語が位置する結合演算の結合タイプとを含む。
【手続補正３９】
【補正対象書類名】明細書
【補正対象項目名】０１２３
【補正方法】変更
【補正の内容】
【０１２３】
任意選択的に、本開示の一実施形態では、結合演算規則は、演算レベル規則および述語レベル規則を含み、演算レベル規則は、演算レベル交換規則：e1 oap12 e2＝e2 oap12 e1、演算レベル組み合わせ規則：（e1 oap12 e2）obp23 e3＝e1 oap12（e2 obp23 e3）、演算レベル左置換規則：（e1 oap12 e2）obp13 e3＝（e1 obp13 e3）oap12 e2、および演算レベル右置換規則：e1 oap13（e2 obp23 e3）＝e2 obp23（e1 oap13 e3）を含み、述語レベル規則は、述語レベル組み合わせ規則：（e1 oap12 e2）obp∧p23 e3＝e1 oap12∧p（e2 obp23 e3）、述語レベル左置換規則：（e1 oap12 e2）obp13∧p e3＝（e1 obp13 e3）oap12∧p e2、および述語レベル右置換規則：e1 oap∧p13（e2 obp23 e3）＝e2 obp∧p23（e1 oap13 e3）を含み、eiは照会式であり、oaおよびobは結合演算であり、pijはeiとejとの結合述語である。
【手続補正４０】
【補正対象書類名】明細書
【補正対象項目名】０１２４
【補正方法】変更
【補正の内容】
【０１２４】
任意選択的に、本開示の一実施形態では、決定モジュール1750は、
元の照会プランの結合演算ノードoBごとに、oBをルートノードとして使用するサブツリー内の各結合演算ノードoAをトラバースし、
oAが、oBをルートノードとして使用するサブツリーの左サブツリー内にあるときに、oAおよびoBが演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが演算レベル左置換規則および述語レベル左置換規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、
oAが、oBをルートノードとして使用するサブツリーの右サブツリー内にあるときに、oAおよびoBが演算レベル組み合わせ規則および述語レベル組み合わせ規則を満たさない場合、第2の制約条件をoBの再構成された各結合述語に追加し、oAおよびoBが演算レベル右置換規則および述語レベル右置換規則を満たさない場合、第1の制約条件をoBの再構成された各結合述語に追加する
ように特に構成され、
第1の制約条件は、T（e2）−＞T（e1）∩T（pa1∧pa2∧．．．∧pan）であり、第2の制約条件は、T（e1）−＞T（e2）∩T（pa1∧pa2∧．．．∧pan）であり、T（e1）は、oAをルートノードとして使用するサブツリーの左サブツリーe1に含まれる元の入力テーブルを示し、T（e2）は、oAをルートノードとして使用するサブツリーの右サブツリーe2に含まれる元の入力テーブルを示し、T（pa1∧pa2∧．．．∧pan）は、oAの再構成された結合述語pa1∧pa2∧．．．∧panに含まれる元の入力テーブルを示し、T1−＞T2は、T1−＞T2によって制約される結合述語がルートノードとして位置する結合演算を使用する第1のサブツリーがT1の入力テーブルを含む場合に、第1のサブツリーがT2のすべての入力テーブルを含むことを示す。
【手続補正４１】
【補正対象書類名】明細書
【補正対象項目名】０１２５
【補正方法】変更
【補正の内容】
【０１２５】
任意選択的に、本開示の一実施形態では、決定モジュール1750は、
第1の候補照会プランP’が以下の条件を満たす場合に、P’は元の照会プランPの等コスト照会プランであると決定する
ように特に構成され、この以下の条件は、
P’の各第1の結合演算の結合タイプが内部結合であり、第1の結合演算が、少なくとも2つの再構成された結合述語を有する結合演算であり、少なくとも2つの再構成された結合述語の各結合述語に対応する、Pの結合演算の結合タイプが内部結合であるという条件、
P’の各結合演算ob’の各結合述語pに関して、
ob’が演算レベル交換規則を満たさないとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しく、Tl（p）が、pが位置する結合演算の左サブツリーに含まれるpの入力テーブルを示し、Tr（p）が、pが位置する結合演算の右サブツリーに含まれるpの入力テーブルを示し、
ob’が演算レベル交換規則を満たすとき、P’のTl（p）とPのTl（p）が等しく、P’のTr（p）とPのTr（p）が等しいか、またはP’のTl（p）とPのTr（p）が等しく、P’のTr（p）とPのTl（p）が等しいという条件、および
P’の各結合演算ob’の各結合述語pに関して、pが、Pのpに関する制約条件を満たすという条件である。
【手続補正４２】
【補正対象書類名】明細書
【補正対象項目名】０１２６
【補正方法】変更
【補正の内容】
【０１２６】
任意選択的に、本開示の一実施形態では、照会モジュール1780は、
照会を実行するために等コスト照会プランセットから最小コストの照会プランを選択する
ように特に構成される。
【手続補正４３】
【補正対象書類名】明細書
【補正対象項目名】０１２７
【補正方法】変更
【補正の内容】
【０１２７】
本開示のこの実施形態によるデータ照会装置1700は、本開示の実施形態によるデータ照会方法の実行主体に対応してもよく、装置1700のモジュールの上記の他の演算および／または機能は、それぞれ上記の方法の対応する手順を実施するために使用される。簡潔にするために、ここでは詳細は再度説明しない。
【手続補正４４】
【補正対象書類名】明細書
【補正対象項目名】０１２８
【補正方法】変更
【補正の内容】
【０１２８】
図18は、本開示の一実施形態によるデータベースシステム1800の概略ブロック図を示す。図18に示すように、データベースシステム1800は、本開示の実施形態による上記のデータ照会装置1700と、データベース1810とを含む。データベースシステム1800は、本開示の実施形態によるデータ照会方法を実行し、データベース1810において照会を実行することができる。
【手続補正４５】
【補正対象書類名】明細書
【補正対象項目名】０１２９
【補正方法】変更
【補正の内容】
【０１２９】
図19は、本開示の別の実施形態によるデータ照会装置の構成を示す。装置は、少なくとも1つのプロセッサ1902（例えばCPU）と、少なくとも1つのネットワークインタフェース1905または別の通信インタフェースと、メモリ1906と、これらの装置間の接続および通信を実施するように構成される少なくとも1つの通信バス1903とを含む。プロセッサ1902は、メモリ1906に格納された実行可能モジュール（コンピュータプログラムなど）を実行するように構成される。メモリ1906は、高速ランダム・アクセス・メモリ（RAM、Random Access Memory）を含んでもよく、また、少なくとも1つの磁気ディスクメモリなどの不揮発性メモリ（non−volatile memory）をさらに含んでもよい。少なくとも1つの他のネットワーク要素との通信接続は、少なくとも1つのネットワークインタフェース1905（有線であっても無線であってもよい）を使用して実施される。
【手続補正４６】
【補正対象書類名】明細書
【補正対象項目名】０１３０
【補正方法】変更
【補正の内容】
【０１３０】
一部の実施態様では、メモリ1906は、プログラム19061を格納し、プロセッサ1902は、本開示の上記の実施形態によるデータ照会方法を実行するためにプログラム19061を実行する。
【手続補正４７】
【補正対象書類名】明細書
【補正対象項目名】０１３１
【補正方法】変更
【補正の内容】
【０１３１】
本開示のこの実施形態における「および／または」という用語は、関連する対象を説明するための関連の関係のみを説明しており、3つの関係が存在し得ることを表すことを理解されたい。例えば、Aおよび／またはBは、以下の3つのケース、すなわち、Aのみが存在するケース、AおよびBの両方が存在するケース、Bのみが存在するケースを表すことができる。さらに、本明細書中の記号「／」は、一般に、互いに関連付けられる対象間の「または」関係を示す。
【手続補正４８】
【補正対象書類名】明細書
【補正対象項目名】０１３２
【補正方法】変更
【補正の内容】
【０１３２】
当業者であれば、本明細書に開示されている実施形態に記載された例との組み合わせにおいて、ユニットおよびアルゴリズムステップが、電子ハードウェア、コンピュータソフトウェア、またはこれらの組み合わせによって実施され得ることに気づくことができる。ハードウェアとソフトウェアとの互換性を明確に説明するために、上では、機能に応じて各例の構成およびステップを一般的に説明した。機能がハードウェアとソフトウェアのどちらによって実行されるかは、技術的解決策の特定の用途および設計制約条件に依存する。当業者であれば、特定の用途ごとに、説明された機能を実施する異なる方法を使用し得るが、その実施は本開示の範囲を超えると考えられるべきではない。
【手続補正４９】
【補正対象書類名】明細書
【補正対象項目名】０１３５
【補正方法】変更
【補正の内容】
【０１３５】
別々の部分として説明されているユニットは、物理的に別々であってもなくてもよく、ユニットとして提示されている部分は、物理的なユニットであってもなくてもよく、1つの位置に配置されても、複数のネットワークユニットに分散されてもよい。ユニットの一部または全部は、本開示の実施形態の解決策の目的を達成するために実際の必要に応じて選択されてもよい。
【手続補正５０】
【補正対象書類名】明細書
【補正対象項目名】０１３６
【補正方法】変更
【補正の内容】
【０１３６】
さらに、本開示の実施形態における機能ユニットは、1つの処理ユニットに統合されてもよいし、これらのユニットの各々は、物理的に単独で存在してもよいし、2つ以上のユニットが、1つのユニットに統合される。統合ユニットは、ハードウェアの形態で実施されてもよいし、ソフトウェア機能ユニットの形態で実施されてもよい。
【手続補正５１】
【補正対象書類名】明細書
【補正対象項目名】０１３７
【補正方法】変更
【補正の内容】
【０１３７】
統合ユニットが、ソフトウェア機能ユニットの形態で実施され、独立した製品として販売または使用される場合、統合ユニットは、コンピュータ可読記憶媒体に格納されてもよい。そのような理解に基づいて、本質的に、本開示の技術的解決策、または従来技術に寄与する部分、または技術的解決策の全部もしくは一部は、ソフトウェア製品の形態で実施されてもよい。ソフトウェア製品は、記憶媒体に格納され、コンピュータデバイス（パーソナルコンピュータ、サーバ、またはネットワークデバイスであってもよい）に、本開示の実施形態で説明した方法のステップの全部または一部を実行するように命令するためのいくつかの命令を含む。上記の記憶媒体は、プログラムコードを格納することができる任意の媒体（USBフラッシュドライブ、リムーバブル・ハード・ディスク、読み出し専用メモリ（ROM、Read−Only Memory）、ランダム・アクセス・メモリ（RAM、Random Access Memory）、磁気ディスク、または光ディスクなど）を含む。
【手続補正５２】
【補正対象書類名】明細書
【補正対象項目名】０１３８
【補正方法】変更
【補正の内容】
【０１３８】
上記の説明は、本開示の特定の実施形態に過ぎず、本開示の保護範囲を限定するものではない。本開示で開示された技術的範囲内で当業者により容易に想到される修正例または置換例は、本開示の保護範囲内に含まれるものとする。したがって、本開示の保護範囲は、特許請求の範囲の保護範囲に従うものとする。
【国際調査報告】
2019504390.tif 000043
2019504390.tif 000044
2019504390.tif 000045
2019504390.tif 000046