(57)【要約】  ハードウェアデータベース管理システム用アーキテクチャが開示される。データフローエンジンが、１つまたは複数のデータベースを構成している情報を格納するメモリに接続されている。データフローエンジンは、パーサ、実行ツリーエンジン、及びグラフエンジンによって形成されている。パーサは、標準化データベースステートメントを取込み、これらのステートメントを１組の実行可能な命令、及び関連付けられたデータオブジェクトに変換する。次いで、実行可能な命令及びデータオブジェクトは実行ツリーエンジンへ送られる。実行ツリーエンジンは、実行可能な命令を、実行する順序を表す実行ツリーを作成する。グラフエンジンは、メモリ内のデータベースへのアクセスを必要とする実行可能な命令を実行ツリーエンジンから受け、標準化データベースステートメントを実施するために実行可能な命令が要求するデータベース内の情報を操作する。【選択図】図２
2008500604.tif 000002
【特許請求の範囲】
【請求項１】
データベース内に格納されている情報を、標準化データベースステートメントを使用して管理し、且つ操作するハードウェアデータベース管理システムであって、
上記標準化データベースステートメントを受け、上記標準化データベースステートメントを実行可能な命令及びデータオブジェクトに変換するパーサと、
上記パーサに接続され、上記パーサから上記実行可能な命令を受けて上記実行可能な命令から実行ツリーを作成し、実行のために上記実行ツリーをスケジュールする実行ツリープロセッサと、
上記実行ツリープロセッサに接続され、上記実行可能な命令によって要求されると上記データベースを操作するように動作可能なグラフエンジンと、
を含むことを特徴とするハードウェアデータベース管理システム。
【請求項２】
上記データベース内の情報は、グラフの形状でメモリ内に表されていることを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項３】
上記実行ツリープロセッサは更に、上記パーサから受けた上記実行可能な命令の妥当性を検査するように動作可能であることを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項４】
上記実行ツリープロセッサは更に、上記データベース内のデータの完全性を保証し、上記データベース内の制限された情報へのアクセスを制御するように動作可能であることを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項５】
上記実行ツリープロセッサは更に、上記実行可能な命令に従って機能を遂行するように動作可能な少なくとも１つの機能エンジンを含むことを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項６】
上記標準化データベースステートメントは、構造化照会言語ステートメントであることを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項７】
上記実行ツリープロセッサは更に、上記実行ツリーを連続的に最適化するように動作可能であることを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項８】
上記グラフエンジンによる上記データベースの操作は、上記データベースからの情報の読出し、上記データベース内への情報の書込み、及び上記データベース内の情報の変更を含むことを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項９】
上記実行ツリープロセッサは、外部マイクロプロセッサからルーチンを呼出すことができることを特徴とする請求項１に記載のハードウェアデータベース管理システム。
【請求項１０】
データベース管理システムをハードウェアで実現するためのデータフローエンジンであって、上記データベース管理システムは情報のデータベースに対して標準化データベースステートメントを処理するように動作可能であり、上記データフローエンジンが、
上記標準化データベースステートメントを実行可能な命令に変換するように動作可能なパージングエンジンと、
上記パージングエンジンから上記実行可能な命令を受けて上記実行可能な命令の妥当性を検査し、実行ツリーを構築して上記実行可能な命令をスケジュールするようになっており、更に、上記データベース内の情報の完全性を保証し且つ上記データベース内の制限された情報へのアクセスを制御するように動作可能な実行エンジンと、
上記データベース内の情報の操作を必要とする上記実行可能な命令を実行するように動作可能なグラフエンジンと、
を含むことを特徴とするデータフローエンジン。
【請求項１１】
上記データベース内の情報は、上記グラフエンジンにアクセス可能なランダムアクセスメモリ内に格納されていることを特徴とする請求項１０に記載のデータフローエンジン。
【請求項１２】
上記データベースは複数のデータフローエンジンに接続されているメモリ内に表されており、上記データフローエンジンは第２のデータフローエンジンに要求を送ることによって情報にアクセスできることを特徴とする請求項１０に記載のデータフローエンジン。
【請求項１３】
上記実行ツリープロセッサは更に、上記実行可能な命令に従って機能を遂行するように動作可能な少なくとも１つの機能エンジンを含むことを特徴とする請求項１０に記載のデータフローエンジン。
【請求項１４】
上記標準化データベースステートメントは、構造化照会言語ステートメントであることを特徴とする請求項１０に記載のデータフローエンジン。
【請求項１５】
上記標準化データベースステートメントは、拡張可能マークアップ言語であることを特徴とする請求項１０に記載のデータフローエンジン。
【請求項１６】
上記実行ツリープロセッサは更に、上記実行ツリーを連続的に最適化するように動作可能であることを特徴とする請求項１０に記載のデータフローエンジン。
【請求項１７】
上記グラフエンジンによる上記データベースの操作は、上記データベースからの情報の読出し、上記データベース内への情報の書込み、及び上記データベース内の情報の変更を含むことを特徴とする請求項１０に記載のデータフローエンジン。
【請求項１８】
上記実行ツリープロセッサは、外部マイクロプロセッサからルーチンを呼出すことができることを特徴とする請求項１０に記載のデータフローエンジン。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータベース構造、及びデータベース管理システムに関する。より特定的には本発明はハードウェアデータベース管理システム用アーキテクチャに関する。
【背景技術】
【０００２】
データベースという用語は、殆ど無限数の事項に使用されてきている。しかしながら、この用語の最も一般的な意味は、編成された態様で格納されているデータの集まりのことである。データベースは、それらがビジネスツールとして導入されて以来、コンピュータの基本的アプリケーションの１つになった。データベースは、階層型、関係型、及びオブジェクト指向型を含む種々のフォーマットで存在している。これらの中で最も広く知られているものは、明らかに、オラクル、ＩＢＭ、及びマイクロソフトから販売されているような関係型データベースである。関係型データベースは、1970年に最初に導入され、それ以降発展し続けている。関係型モデルは、二次元テーブルの形状のデータを表し、各テーブルは格納されている情報のある特定の片を表している。関係型データベースは、論理的に見れば、二次元テーブルの集まり、またはアレイである。
【０００３】
関係型データベースは今日使用されている典型的なデータベースであるが、オブジェクト指向型データベースフォーマットＸＭＬはネットワークまたはウェブへのその適用性、サービス、及び情報の故に支持を得ている。オブジェクト指向データベースは、関係型データベース構造に使用されているフラットアレイの代わりに、ツリー構造に編成されている。データベース自体は、単に関係型またはオブジェクト指向型のような特定のフォーマットに編成され、格納されている情報の集まりに過ぎない。データベース内の情報を検索して使用するためには、データベースを操作するデータベース管理システム（“ＤＢＭＳ”）が必要である。
【０００４】
従来のデータベースは、幾つかの固有の欠点を有している。サーバハードウェア及びプロセッサパワーに対する不断の改良がデータベースの性能の改善に資してはいるが、一般的に言ってデータベースは未だに低速である。データベースの速度は、大きく且つ複雑なプログラムを走らせる汎用プロセッサと、ディスクアレイへのアクセス時間とによって制限される。近年におけるマイクロプロセッサの性能の改良のほぼ全ては、それが基本的なコード及びデータにアクセスするのに要する時間を短縮することを試みるものであった。不幸にも、データベースの性能に関して、もし主たる応用が、データベース管理システムの場合のようにメモリ内の多数の、及び変化する数の位置を読むか、または変更することであれば、プロセッサが如何に速く内部サイクルを実行できるかは重要ではない。
【０００５】
また、如何に多くの、または如何に速いプロセッサをデータベースのために使用するとしても、プロセッサは汎用であり、ソフトウェアアプリケーション並びにオペレーティングシステムを使用しなければならない。このアーキテクチャは、ソフトウェアコード並びにオペレーティングシステム機能への複数回のアクセスを必要とし、従ってメモリアクセス、データベース管理システムの主機能には充てられない莫大な量のプロセッサ時間を要することになる。
【０００６】
サーバ及びプロセッサ技術以外にも、大きいデータベースは、実際のデータが格納されている回転ディスクアレイによって制限される。ダイナミックランダムアクセスメモリ（ＤＲＡＭ）のようなソリッドステートメモリ内にデータをキャッシュすることによってデータベースの動作を加速しようとする多くの試みが高費用をかけてなされてきたが、ＤＲＡＭ内にデータベース全体を格納しない限り、データベース管理システムにおけるデータアクセスのランダム性は、キャッシュ内に格納されているデータのミスが莫大な量の資源を浪費し、性能に大きい影響を与えることを意味する。更に、回転ディスクアレイはかなりな時間を要し、データが断片化されるにつれてディスクアレイの性能が劣化しないように保つべくそれらを絶えず最適化するための金銭が費やされる。
【０００７】
データベース管理システムにおけるこれらの結果を全て取得し、維持することは極めて高価である。データベース管理システムに関連する主要コストは、データベース管理プログラム及びアプリケーションのための初期及び継続（反復）ライセンシングコストである。データベースソフトウェアの使用を許可する会社は、そのソフトウェアを走らせる全アプリケーション及びＤＢＭＳサーバ内の各プロセッサ毎に毎年ライセンスフィーを課すコスト構造を構築してきた。このように、ＤＢＭＳは極めて拡張性に富む（スケーラブルである）が、データベースを維持するコストも比例して増加する。また、現データベース管理システムの本質から、一旦顧客があるデータベースベンダーを選択してしまうと、その顧客は全ての実際的な目的に関してそのベンダーに拘束されるようになる。時間、経費、及びデータに対するリスクのコストが極めて高いのでデータベースプログラムを変えることは極めて困難であり、これが、現在では業界で標準的に実施されているように、データベースベンダーが極めて高いライセンシングフィーを毎年課すことを可能にしているのである。
【０００８】
データベースを変える理由は、標準化されたデータベース言語の所有権を主張できる実施に伴うこのような経費問題である。今日市販されている全ての主要データベースプログラムは標準照会言語、即ちＳＱＬと呼ばれる標準に基づく関係型データベースプロダクトであり、各データベースベンダーは僅かに異なる標準を実現して、全ての実際的な目的のために互換性のないプロダクトをもたらしている。また、関係型ではない拡張可能マークアップ言語（“ＸＭＬ”）のような新しい標準及び技術を受入れるためにデータは関係型テーブル内に格納されるので、ＸＭＬを関係型プロダクトが理解可能な形状に変換するために大きく且つ低速のソフトウェアプログラムを使用しなければならないか、または新しいＸＭＬデータベースのために完全に分離したデータベース管理システムを構築し、展開し、維持しなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従って、要望されているのは、従来のデータベースに比して改良された性能を有し、プロトコルに寛容なデータベース管理システムである。
【課題を解決するための手段】
【００１０】
本発明は、完全にハードウェアで実現されたデータベース管理エンジンを提供する。データベース自体はランダムアクセスメモリ（“ＲＡＭ”）内に格納され、データフローエンジンと称する専用プロセッサを使用してアクセスされる。データフローエンジンは、標準ＳＱＬ及びＸＭＬデータベースコマンド及び演算を、データフローエンジンが実行可能なマシン命令にパーズする。これらの命令は、データフローエンジンがデータをデータベース内に格納し、データベース内のデータを検索し、変化させ、そして削除することを可能にする。データフローエンジンはエンジンカードの一部であり、エンジンカードは、データフローエンジンのための処理機能を遂行して入データをデータフローエンジンのためにフォーマットされたステートメントに変換するマイクロプロセッサを更に含む。エンジンカードはホストプロセッサに接続されており、ホストプロセッサはデータベース管理エンジンへのユーザインタフェースを管理する。
【００１１】
データフローエンジンによって実現されているデータベース管理システムは、ＲＡＭ内に格納されているデータベースに接続されたパーサ、実行ツリーエンジン、及びグラフエンジンによって形成されている。パーサ即ちパージングエンジンは、ＳＱＬまたはＸＭＬ標準のような標準化されたデータベースステートメントを取込み、このステートメント及び関連付けられたデータオブジェクトから実行可能な命令を作成する。実行可能な命令及びそれらに関連付けられたデータオブジェクトは、実行エンジン（実行ツリープロセッサともいう）へ送られ、実行エンジンはステートメントを形成している実行可能な命令を使用して実行ツリーを作成する。この実行ツリーは、実行可能な命令の相互依存性に基づく実行可能な命令の実行順序を表す。次いで実行可能な命令は、実行ツリーによって規定されたように実行される。データベースへのアクセスを必要とする命令は、グラフエンジンへ送られる。グラフエンジンは、データベース内の情報を操作（読出し、書込み、及び変更のような）するように動作可能である。グラフエンジンは、データベース内に含まれる情報を格納するために使用されるデータ構造を作成し、維持するようにも動作可能である。
【００１２】
実行ツリーの作成に加えて、実行エンジンはデータベース内にデータの完全性を維持し、データベース内の制限された情報へのアクセスを制御する。実行エンジンは、データベース内の情報へのアクセスを必要としない諸機能をも遂行することができ、またネットワークに接続されている外部マイクロプロセッサまたは他のデバイス内のルーチンのような、データフローエンジンの外部の機能またはルーチンを呼出すこともできる。
【００１３】
以上に本発明の好ましい、そして代替特色の概要をかなり広く説明したので、当業者ならば以下の本発明の詳細な説明がより深く理解されよう。本発明の特許請求の範囲を形成する本発明の付加的な特色を以下に説明する。当業者ならば、本発明と同一の目的を遂行するために、他の構造を設計し、変更するための基準として以下に開示する概念及び特定の実施の形態を容易に使用することができよう。当業者ならば、本発明の思想及び範囲から逸脱することなく同等構造を実現することも可能であろう。
【発明を実施するための最良の形態】
【００１４】
図１は、従来技術のネットワーク化されたデータベース管理システム１０を示す図である。従来技術のデータベース管理システム（“ＤＢＭＳ”）は、オラクル、ＤＢ２、及びＳＱＬサーバのようなデータベースプログラムを走らせているサン、ＩＢＭ、及びデル製のサーバのような汎用ＤＢＭＳサーバ１２及び１４を使用して実現されている。これらのプログラムは、ＤＢＭＳサーバ１２及び１４内の１つまたはそれ以上の汎用マイクロプロセッサ１８上で走る。データベース内のデータは、ディスクドライブ３６及び３８のアレイを使用して格納される。ディスクアレイ３６及び３８から読出し、それらへ書込むためのアクセス時間が動作を大幅に遅くし得るから、データベース管理システム１０の動作を援助するために、総合データベースの極く一部をサーバ１２及び１４内にキャッシュすることができる。
【００１５】
データベース管理システム１０は、ＤＢＭＳサーバ１２及び１４の他に、ＤＢＭＳサーバ１２及び１４と共に走るアプリケーションサーバ２２及び２４を含むことができる。ＤＢＭＳサーバはディスクアレイ３６及び３８内に含まれるデータの格納、検索、変化、及び削除のような基本的なデータベース機能を管理し、一方アプリケーションサーバはＤＢＭＳと共に作業してデータマインニング、パターン認識、傾向分析等のようなタスクを遂行するプログラムを走らせる。アプリケーションサーバ２２及び２４も、アプリケーションプログラムを走らせている汎用マイクロプロセッサ２８を有する汎用サーバである。
【００１６】
データベース管理システム１０は、ネットワーク３４を通してワークステーション３２（データベースのユーザを表す）によってアクセスされる。ユーザはアプリケーションサーバへ命令を送り、アプリケーションサーバはＤＢＭＳサーバにアクセスしてユーザに対する適切な応答を入手する。データベース管理システム１０はネットワークを介してユーザ及びデータベースにアクセスするので、データベースの個々の要素でさえも同一位置を占める必要はない。
【００１７】
データベース管理システム１０の長所の１つは、その拡張可能性である。データベース、データベース管理システム、及びアプリケーションサーバは、ユーザ数の増加、データベース自体内のデータの増加、またはシステム上で走るより集中的なアプリケーションに応答して容易に拡張することができる。システムは、プロセッサ１０及び３０のようなプロセッサ、及びＤＢＭＳを、既存アプリケーションサーバに付加することによって拡張することも、または付加的なアプリケーションサーバ２６及びＤＢＭＳ１６を付加して何らかの増加したロードを処理することもできる。更に、新しいディスクアレイを付加して格納される実際のデータベース（１つまたは複数の）のサイズを増加させることが可能である。
【００１８】
データベース管理システム１０は極めて大きいデータベースと共に動作させることも、異なるユーザの要求に合致するように容易に拡張することもできるが、多くの公知の問題に悩まされている。サーバハードウェア及びプロセッサパワーの不断の改良がデータベースの性能を改善してはきたが、一般的に言って、データベース管理システム１０に関連して上述したように構築されたデータベースは、未だに低速である。データベースの速度は、大きく且つ複雑なプログラムを走らせる汎用プロセッサと、ディスクアレイ３６及び３８のようなディスクアレイへのアクセス時間とによって制限される。更に、データが断片化されるにつれてディスクアレイの性能が劣化しないように絶えず最適化するために、かなりの時間と金銭とを費やさなければならない。
【００１９】
更に、データベース管理システム１０を取得し、維持することは極めて高価である。データベース管理システム１０に関連する主要コストは、データベース管理プログラム及びアプリケーションのための初期及び継続ライセンシングコストである。データベースソフトウェアの使用を許可する会社は、そのソフトウェアを走らせる全アプリケーション及びＤＢＭＳサーバ内の各プロセッサ毎に毎年ライセンスフィーを課すコスト構造を構築してきた。このように、ＤＢＭＳは極めて拡張可能性に富むが、データベースを維持するコストも比例して増加する。また、現データベース管理システムの本質から、一旦顧客があるデータベースベンダーを選択してしまうと、その顧客は全ての実際的な目的に関してそのベンダーに拘束されるようになる。時間、経費、及びデータに対するリスクのコストが極めて高いので、データベースプログラムを変えることは極めて困難であり、これが、データベースベンダーが極めて高い年毎にライセンシングフィーを課すことを可能にしているのである。
【００２０】
今日市販されている全ての主要データベースプログラムは、標準照会言語、即ちＳＱＬと呼ばれる標準に基づく関係型データベースプロダクトであり、各データベースベンダーは僅かに異なる標準を実現して、全ての実際的な目的のために互換性のないプロダクトをもたらしている。大きいＤＢＭＳのそれぞれが所有権を主張できるものであるために、顧客は新しいベンダーに容易に切り替えることを阻害されている。また、関係型ではない拡張可能マークアップ言語（“ＸＭＬ”）のような新しい標準及び技術を受け入れるためにデータは関係型テーブル内に格納されるので、ＸＭＬを関係型プロダクトが理解可能な形状に変換するために大きく且つ低速のソフトウェアプログラムを使用しなければならないか、または新しいＸＭＬデータベースのために完全に分離したデータベース管理システムを作成し、展開し、維持しなければならない。
【００２１】
図２は、図１のデータベース管理システムの欠陥を解消するデータベース管理システムを示している。図１のデータベース管理システム１０は、データベース管理（“ＤＢＭ”）エンジン４０に置換されている。ＤＢＭエンジン４０は、専用のハードウェアで実現されている完全データベース管理システムである。データベース管理システムを完全にハードウェアで実現することによって、ＤＢＭエンジン４０は、従来データベース管理システムに伴っていた多くの問題を解消する。ハードウェアで実現されたデータベース管理の面だけではなく、図２にデータベース５２で示されているデータベース自体もランダムアクセスメモリ（“ＲＡＭ”）内に格納されているので、データ自体の極めて高速な格納、検索、変更、及び削除が可能である。更に、ＤＢＭエンジン４０は、プロトコルに対して寛容な独特なデータ構造で情報をデータベース５２内に格納する。これは、ＤＢＭエンジン４０が、同一の独特なデータ構造を使用して、ハードウェアでＳＱＬ及びＸＭＬの両データベースをデータベース５２内に実現できることを意味している。
【００２２】
ＤＢＭエンジン４０は、ネットワーク５４を通してワークステーション５６と通信できるように構成することができる。ＤＢＭエンジン４０との通信を管理するために、及び多分ワークステーション５６とＤＢＭエンジン４０との間で交換される情報の若干の処理を遂行するために、ワークステーション６０にはソフトウェアプログラム及び／またはドライバ６０がインストールされている。ＤＢＭエンジン４０は、ワークステーション５６を使用するユーザに透明であるように設計されている。換言すれば、ユーザは、オラクル、ＩＢＭ、ＤＢ２、マイクロソフトＳＱＬサーバ、その他のデータベースの訓練を受けていても、いなくても、習熟しているＳＱＬまたはＸＭＬと実質的に同一のフォームを使用してＤＢＭエンジン４０及びデータベース５２にアクセスすることができる。これは、現在のユーザに最小の訓練を行うだけで、既存のデータベースからＤＢＭエンジン４０への移行を可能にする。
【００２３】
ＤＢＭエンジン４０は、エンジンカード６４、ホストマイクロプロセッサ４４、及びデータベース５２を含む。ＤＢＭエンジン４０との接続は、ホストマイクロプロセッサ４４によって検査される。ホストマイクロプロセッサ４４は、ＯＤＢＣ、またはＪＤＢＣのような標準ネットワークデータベースプロトコルを使用して、ワークステーション５６との接続を確立する。ホストマイクロプロセッサ４４は、ＤＢＭエンジン４０へのアクセス、要求、及び応答の他に、アプリケーションを走らせ、データベースへの問合せに対するある初期処理を遂行し、また他のエンジンカード６４によって遂行させる必要がないオーバヘッドを処理するために使用することもできる。
【００２４】
エンジンカード６４は、オラクル、ＩＢＭ、及びマイクロソフトがソフトウェアプログラムで実現しているデータベース管理システムを、ハードウェアで実現したものである。エンジンカード６４は、ホストマイクロプロセッサ４４と通信するために、及び情報をマイクロプロセッサ４８とデータフローエンジン５０との間で交換するために使用されるＰＣＩブリッジ４６を含む。マイクロプロセッサ４８は、ホストマイクロプロセッサ４４からの要求をデータフローエンジン５０のための適切なフォーマットに配置し、データフローエンジンに対する要求をキューに入れ、データフローエンジン５０が遂行することができない処理タスクを処理する。マイクロプロセッサ４８はＰＣＩブリッジ４６を通してデータフローエンジン５０と通信し、データフローエンジン５０に出入する全ての情報はマイクロプロセッサ４８を通過する。
【００２５】
図５を参照して詳細を後述するデータフローエンジンは、データベース機能を処理するように最適化された専用プロセッサである。データフローエンジンは、フィールドプログラマブルゲートアレイ（“ＦＰＧＡ”）、または特定用途向け集積回路（“ＡＳＩＣ”）の何れかで実現することができる。データフローエンジン５０は、データベース５２とのインタフェースである。データフローエンジンは、データベース５２内の情報の格納、検索、変化、及び削除に対する責を負う。データベース機能の全てが、データフローエンジン５０内にハードウェアで直接実現されているので、ソフトウェアデータベース管理プログラムは必要ではない。これは、現在データベース管理システムに関連付けられている初期及び継続ライセンスフィーを排除する。
【００２６】
またデータベース管理システムが全てハードウェアで構成され、データベース５２が全てＲＡＭ内に格納されているので、データベース内の要求を処理するのに要する時間は現在のデータベース管理システムよりもかなり短縮される。現在のデータベース管理システムを用いると、要求を、プログラム自体及びオペレーティングシステムのような種々のレベルのソフトウェアの間で、並びにプロセッサのローカルＲＡＭ、入力／出力プロセッサ、外部ディスクアレイ等を含む幾つかのレベルのハードウェアの間で往来させなければならない。要求を種々のソフトウェアレベル及びハードウェアデバイスの間で往来させなければならないので、データベース管理システムから要求への応答は極めて時間がかかり、資源に負担をかける。一方、ＤＢＭエンジン４０は要求を直接的にデータフローエンジン５０に渡し、データフローエンジン５０はメモリに直接アクセスし、応答を処理し、そして応答を戻す。これらは全てマシンレベルで行われ、オペレーティングシステム及びソフトウェアプログラムを通過させる必要も、ディスクアレイにアクセスして待機する必要もない。本発明のアプローチは、現在実現されているデータベース管理システムよりも数桁も高速である。
【００２７】
ＤＢＭエンジン４０も、現在のデータベース管理システムと同様に容易に拡張可能である。より多くのユーザ、またはより大きいデータベースを受入れるために、データベース５２に関連するＲＡＭを増加させることも、及び／またはＤＢＭエンジン４２のような付加的なＤＢＭエンジンをネットワークに付加することもできる。本発明のデータベース管理システムが拡張可能であるので、ユーザは、メモリまたはＤＢＭエンジンを試しに付加した後に現在の要望に対して必要なシステムだけを購入することができる。要望が変化した場合も、成長要求に合わせて付加的な機器を購入することができる。図１に関連して説明したようなデータベース管理プログラム及び付加的なプロセッサを必要としないので、本発明によるデータベース管理システムを拡張する場合、付加的なソフトウェアライセンスは必要ではない。
【００２８】
図３に示す本発明によるデータベース管理システムは、データマインニング、パターン識別、及び傾向分析のようなより複雑なアプリケーションを遂行するために、プロセッサ６２を有する既存アプリケーションサーバ６０を組入れている。ＤＢＭエンジン４０は、この場合もデータベース及びデータベース管理機能を提供するが、ＤＢＭエンジン４０及び４２の資源を消費することなく複雑なアプリケーションを走らせることができるようにアプリケーションサーバ６０が付加されている。更に、既存データベースハードウェアを本発明のデータベース管理システム内のアプリケーションサーバとして使用することができるので、既存データベースを本発明のデータベース管理システムに転用する場合、既存資源が浪費されることはない。図１に示すデータベース管理システムと同様に、ワークステーション５６によって表されているユーザは、ネットワーク５４を通してアプリケーションサーバ６０と通信する。次いでアプリケーションサーバ６０は、ＤＢＭエンジン４０及び４２の資源にアクセスし、応答をワークステーション５６に戻して渡す。
【００２９】
図４に、ＤＢＭエンジン４０をより詳細に示す。ＤＢＭエンジン４０は、ネットワークインタフェースカード（“ＮＩＣ”）６８を通してネットワーク５４と通信する。次いでＮＩＣ６８はＰＣＩバス７０に接続される。ＤＢＭエンジン４０への要求、及びそれからの応答は、ＮＩＣ６８からホストＰＣＩブリッジ６６を通してホストマイクロプロセッサ４４へ渡される。図２に関して説明したように、ホストマイクロプロセッサ４４は、ユーザの追跡及び認証、標準データベース通信ドライバを使用しての要求及び応答の引渡し、要求及び応答の多重化及びデマルチプレックス、及びデータフローエンジン５０による処理のために要求及び応答をフォーマットすることを援助するために使用される。ホストマイクロプロセッサは、多重化データをブロックでマイクロプロセッサ４８へ送る。この実施の形態におけるブロックは、64キロバイト長である。
【００３０】
マイクロプロセッサ４８はホストマイクロプロセッサ４４から要求を受信し、それらの要求をステートメントの形状で（本発明の現在の実施の形態においては32文字長）データフローエンジンへ渡す。データフローエンジン５０はマイクロプロセッサ４８からステートメントを取込み、データベースに要求された機能を遂行する。データフローエンジン５０の動作の詳細に関しては、図５を参照して後述する。データフローエンジン５０は、バス７４を使用してデータベース５２にアクセスする。
【００３１】
前述したように、データベース５２は、従来のデータベースにおけるディスクアレイに代わってＲＡＭ内に格納されている。これにより、従来のデータベースよりも遥かに短いアクセス時間を可能にしている。これもまた前述したように、データベース５２内のデータはプロトコルから独立している。これは、ＤＢＭエンジン４０が、同一データベース内のオブジェクト向けの、または階層型の情報を関係型データとして格納することを可能にする。関係型データベースによって使用されているテーブルフォーマットでデータを格納するのではなく、データフローエンジン５０はデータをグラフ構造でデータベース内に格納する。この構造においては、グラフ内の各エントリは、情報を、及び／またはその後のエントリに関する情報を記憶する。データベースのグラフ構造がデータを効率的に格納する手段を提供するので、関係型モデルを使用する同等のディスクアレイに収納されるよりも遥かに多くの情報を格納することができる。他の、より広いグラフ構造と共に本発明に使用することができるデータベースのためのこのような構造の１つが、Bennettの米国特許第6,185,554号に開示されているので参照されたい。データベース５２は、ＲＡＭの複数のバンクを含むことができ、これらのＲＡＭはデータフローエンジン５０と同一場所に配置することも、または図６に関して後述するように、外部バス上に分布させることもできる。
【００３２】
データフローエンジンは、データベース５２の他にワーキングメモリ７２にも接続されている。ワーキングメモリ７２もＲＡＭメモリであり、ポインタ、ステータス、及びデータベースをトラバースする時にデータフローエンジン５０が使用する他の情報を格納するために使用される。
【００３３】
以下に図５を参照してデータフローエンジン５０を詳細に説明する。データフローエンジン５０は、パーサ１５２、実行ツリーエンジン１５４、及びグラフエンジン１５６によって形成されている。パーサ１５２は、ＳＱＬステートメントまたはＸＭＬステートメントのようなステートメントを、実行可能な命令及びこれらのユニットに関連付けられたデータオブジェクトに解体するように動作する。パーサは、各新ステートメントを取込み、演算子及びそれらに関連付けられたデータオブジェクトを識別する。例えば、ＳＱＬステートメントSELECT DATA FROM TABLE WHERE DATA2＝VALUEにおいて、演算子SELECT、FROM、WHERE、及び＝を演算子として識別し、一方DATA、TABLE 、 DATA2、及びVALUEをデータオブジェクトとして識別する。次いで演算子は実行可能な命令に変換され、一方それらのデータオブジェクトはそれらの対応する演算子に関連付けられてメモリ内に格納される。パーサが特定のステートメントを終了させると、さらなる処理のために、一連の実行可能な命令及びそれらの関連付けられたデータへのリンクが実行ツリーエンジン１５４へ送られる。
【００３４】
パーサ１５２は、入力ステートメントバッファ１６０、ハードウェアトークンエンジン１６２、ハードウェア優先順位エンジン１６４、及びハードウェアリンカー及びパーズツリーエンジン１６６によって形成されている。ステートメントは、ＰＣＩバス７６を通して送受される。新しいステートメントはパーサ１５２へ送られ、パーサ１５２においてバッファされ、入力ステートメントバッファ１６０において待機させられる。ステートメントは、入力ステートメントバッファ１６０からハードウェアトークンエンジン１６２へ送られ、ハードウェアトークンエンジン１６２においてステートメントの各要素が演算子のテーブルと比較される。もしステートメント内の要素がテーブル内のエントリと一致すればそれは演算子として識別され、演算子は２進コードの形状であることができる実行可能な命令に置換される。テーブル内のどのエントリとも一致しない要素はデータオブジェクトとして識別され、適切な演算子に関係付けられ、外部メモリ７２内に格納される。
【００３５】
ハードウェアトークンエンジン１６２によって生成された実行可能な命令は、ハードウェア優先順位エンジン１６４へ送られる。ハードウェア優先順位エンジン１６４は各実行可能な命令を調べ、それらを実行しなければならない順序に従ってそれらをリンクする。例えば、式Ａ＋Ｂ*（Ｃ＋Ｄ）において、ハードウェア優先順位エンジンは、括弧内のステートメント（Ｃ＋Ｄ）を最初に実行し、その結果をＡに加算する前に、その結果にＢを乗算しなければならないことを認識する。一旦正確な手順が確立されれば実行可能な命令がハードウェアリンカー及びパーズツリーエンジン１６６へ送られる。このハードウェアリンカー及びパーズツリーエンジン１６６は、外部ワーキングメモリ７２を管理する。ハードウェアリンカー及びパーズツリーエンジン１６６は全ての実行可能な命令及びデータオブジェクトの処理の準備が整った時に、実行可能な命令を外部ワーキングメモリ７２内に格納する。
【００３６】
実行可能な命令及びデータオブジェクトの処理の準備が整うと実行ツリービルダー１７０は、先ず、実行可能な命令が適切且つ有効であることを検査する。次いで実行ツリーエンジン１７０は、ステートメントを形成している実行可能な命令を取込み、実行ツリーを構築する。実行ツリーは、実行可能な命令によって表される全ステートメントを処理するために個々の実行可能な命令が処理される手法を表している。ＳＱＬステートメントSELECT DATA FROM TABLE WHERE DATA2＝VALUEのための実行ツリーの例は、次のように表すことができる。
SELECT
／  ＼
DATA   WHERE
／          ＼
FROM              ＝
／              ／  ＼
TABLE         DATA2    VALUE
／
FROM
／
TABLE
【００３７】
アセンブルされた実行ツリーは、従属を有していない要素から、最多の従属を有している要素に向かって、即ち図示の例では底から頂に向かって実行される。ステートメントの処理をより効率的に行うために、他の枝に従属を有していない枝を並列に実行することができる。例えば、図示の例の左枝及び右枝は如何なる相互依存性も有しておらず、並列に実行することができる。ハードウェアエイリアスエンジン１７２は、データベース内に存在し得る何等かのテーブルエイリアスを追跡し、それらのマッピングを供給する。
【００３８】
実行ツリー記憶装置１７４及び実行ツリーキャッシュ１７６は、実行ツリー及び実行ツリーが必要とし得る何等かの関連情報をバッファし、格納する。実行ツリープロセッサ１７８は実行ツリーを取込み、ツリー内の如何なる相互依存性をも有していない要素を識別し、実行ツリーのこれらの要素を処理のためにスケジュールする。各要素はその中に、その機能の結果を格納すべきメモリ内の位置を指し示すポインタを含む。各要素の処理が終了し、その結果が適切なメモリ位置内に格納されるとその要素はツリーから除去され、次の要素が相互依存性を有していないものとしてタグ付けされ、実行ツリーエンジン１７８による処理のためにスケジュールされる。実行ツリーエンジンは次の要素を処理のために取込み、機能コントローラ１８０内のスレッドが開くのを待機する。更に、実行ツリー全体に共通の要素を、割当てられたタグとすることができる。これらのタグは、実行ツリーの命令全体の共通要素の結果を共用するために使用することができる。例えば、もし同一ステートメント全体の複数の場所にVALUE＋VALUE2が繰り返されていれば、VALUE＋VALUE2が現れる度毎にそれを再実行または再計算する代わりに、VALUE＋VALUE2の結果が１つのタグに割当てられ、このタグがVALUE＋VALUE2の各場合毎に実行ツリー内に挿入される。このタグはVALUE＋VALUE2の第１の計算からのその結果を指し示し、それをその後の要素の場合に使用してその後の命令の実行に要する処理時間を節約する。
【００３９】
機能コントローラ１８０は、ステートメント記憶装置１８２、ステートメントコントローラ１８４、及びシーケンサ１８６と共に、個々の実行可能な命令、及びそれらの関連付けられたデータオブジェクトを処理するように動作する。オプティマイザ及びシーケンサ１８６は各ステートメントの処理を連続的に監視し、最も効率的に処理できるように実行ツリーを最適化する。またオプティマイザ及びシーケンサ１８６は、特定の実行命令及び何等かの関連付けられたデータオブジェクトが要素をグラフエンジン１５６、ストリングプロセッサ１９２、または浮動小数点プロセッサ１９４の何れかへ送る時点を、機能コントローラ１８０に告げるようにも動作する。
【００４０】
データの完全性エンジン１９６はデータベース制約を強化するように動作する。即ち、データベース内にナル値を存在させず、重複を存在させず、そして対応値を一致させるように強化する。特権エンジン１９０は、アクセスが制限されているデータベース内の情報へのアクセスを制御し、またユーザのサブセットだけが見ることができる。トランザクションの完全性コントローラ１８８はデータベースのためのコミット及びロールバック機能を提供し、データベース内の情報の読出しの一貫性を保証する。コミット及びロールバック機能は、データベース内の情報が変更される時に出現する。変化される情報は、変化が完遂されるまで元の情報と並列に保持され、他の情報ユーザは古いデータを見るので読出しの一貫性が得られる。完遂されていない変化はロールバックされるか、またはデータベースから除去される。
【００４１】
実行エンジン１５４は、分離したデータフローエンジンに関連付けられたデータにアクセスするために、またはデータフローエンジンの外部の機能または図４のマイクロプロセッサ４８内で走るルーチンのようなルーチンにアクセスするために、データフローエンジン５０の外部へ進むこともできる。この場合、データ要求、または機能またはルーチン呼出しは、実行ツリーエンジン１５４によって入力／出力プロセッサ２０２へ送られる。入力／出力プロセッサ２０２は、この情報をＰＣＩバス７６を通して図４のマイクロプロセッサ４８へ送ってデータ要求に対する応答を処理または経路指定するか、または機能またはルーチン呼出しをＰＣＩバス７６から受信して入力機能バッファ２０４へ送り、入力／出力プロセッサ２０２へ戻させる。入力／出力プロセッサ２０２は、この応答を実行ツリーエンジン１５４へ戻してさらなる処理を遂行させる。
【００４２】
データベース内のエントリへのアクセスを必要とする実行可能な命令、または機能呼出しは、グラフエンジン１５６へ送られる。グラフエンジン１５６は、データベースへの書込み、データベースからの読出し、及びデータベースの変更を行うメカニズムになっている。データベース自体は、データベースメモリ１５８内に格納されている。メモリ１５８は好ましくはランダムアクセスメモリであるが、フラッシュメモリまたは回転メモリを含む如何なる型のメモリであることもできる。性能並びにメモリ利用率を改善するために、データベース内に含まれる情報は従来のデータベースとは異なるメモリ内に格納される。ＳＱＬ標準に準拠するデータベースのような従来のデータベースは本質的には関係型であり、関係付けられた二次元テーブルの形状で情報をデータベース内に格納する。各テーブルは一連の列及び行で形成されている。関係型モデルは数十年にわたって存在してきており、それはほぼ全ての大きいデータベースの基準である。他のモデルが特定のアプリケーションのために人気を得始めており、その最も注目すべきものはウェブサービス及び不統一データのために使用されるＸＭＬである。ＸＭＬでのデータは、これもツリー構造と呼ぶことができる階層型フォーマットで格納される。
【００４３】
本発明のデータベースは、他の何れのデータベースとも異なるデータ構造で情報を格納する。本発明は、情報を格納するためにグラフ構造を使用する。公知の階層型ツリー構造においては根が存在し、根からの枝に沿って種々のノードが存在する。ツリー内の何れか特定のノードを見出すためには、根から始めて正しい枝を辿り、最終的に所望のノードに到達する。一方、グラフは、円弧またはエッジによって接続されている一連のノード、または頂点である。ツリーとは異なり、グラフは特定の根及び独特な枝を有する必要がない。またツリーとは異なり、グラフ内の頂点は他のツリー内に合流している円弧、または同一ツリー内へループバックする円弧を有することができる。
【００４４】
本発明のデータベースの場合、頂点は、データベース内に表されている情報、並びに該情報及びその頂点を他の頂点へ接続する円弧に関する若干の特性である。グラフエンジン１５６は、データベース内に含まれる情報を格納するグラフを構築し、変更し、そしてトラバースするために使用される。グラフエンジン１５６は、データベースからの、またはデータベースに変化を要求する実行可能な命令を取込み、新しい頂点及び円弧を作成し、既存の頂点または円弧を変更または削除し、そして処理中のステートメントによって要求された頂点から情報を読出すためのメカニズムを提供する。
【００４５】
データベース１５８を含むグラフは、メモリ２００及び２０１内に格納される。メモリ２０１はグラフエンジン１５８にローカルであり、直接アクセスすることができる。データベース１５８を格納するのに利用可能なメモリを増加させるために、グラフエンジン１５６はメモリコントローラ１９８を１つのリングに接続することができる。任意数のメモリモジュール２００内にデータベース１５８を格納することができるように、メモリコントローラ１９８はリングバス８６を形成している。データは、メモリコントローラがそのアドレス空間をそのメモリコントローラが制御しているメモリに属するものと認識するまで、メモリコントローラ１９８のリングバス８６を次々に渡されて行く。次いでメモリがアクセスされ、結果は、それがグラフエンジン１５６に戻されるまでリングバスを次々に渡されて行く。
【００４６】
図６を参照して、コンパクトＰＣＩアーキテクチャにより実現された本発明の実施の形態を説明する。データベース管理システムは、図２乃至５を参照して説明したものと正確に同じように動作する。コンパクトＰＣＩフォームファクタを使用することにより、付加的なメモリカードを外部セルバス８６に接続することが可能になる。コンパクトＰＣＩシャーシ内に利用可能なだけ多くのメモリカード９２を、外部セルバス８６に接続することができる。メモリカード９２の他に、データベースの不揮発性バージョンをＲＡＭ内に格納されているデータベースと並列に維持することができるように、持続性記憶媒体を外部セルバス８６に接続することができる。この持続性記憶媒体は、ディスクドライブであることも、またはフラッシュメモリのような静的デバイスであることもできる。
【００４７】
図２乃至４を参照して説明したマイクロプロセッサは、モトローラ社製のパワーＰＣラインのマイクロプロセッサ、またはインテル社製のＸ86またはペンティアム（登録商標）ラインのマイクロプロセッサを含む如何なる適当なマイクロプロセッサであることもできる。更に、ＰＣＩブリッジ及びネットワークインタフェースカードは、容易に入手可能な公知の部品である。特定のプロトコル、実施、及び資材に関して特定の例を示したが、当業者ならばネットワーク処理システム、ポリシーゲートウェイはプロトコルから独立しており、且つ本発明の範囲から逸脱することなく種々の異なる態様で機能できることが理解されよう。
【図面の簡単な説明】
【００４８】
【図１】従来技術のデータベーストポロジ図である。
【図２】本発明の原理に従って構築されたデータベーストポロジ図であって、本発明の原理によるデータベース管理エンジンのブロック図を含む。
【図３】本発明の原理に従って構築された代替データベーストポロジ図である。
【図４】図３のデータベース管理エンジンの実施の形態のブロック図である。
【図５】図４のデータフローエンジンの実施の形態のブロック図である。
【図６】コンパクトＰＣＩ形状ファクタと同等な、本発明によるデータベース管理エンジンの実施の形態のブロック図である。
【図１】
2008500604.tif 000003
【図２】
2008500604.tif 000004
【図３】
2008500604.tif 000005
【図４】
2008500604.tif 000006
【図５】
2008500604.tif 000007
【図６】
2008500604.tif 000008