JP2006155663A - 最大ビットスライスを用いてビットストリングにブール演算を施すための方法とシステム - Google Patents

Abstract

【課題】ビットストリングにブール演算を施して結果のビットストリングを形成するためのシステムと方法を提供する。
【解決手段】各ビットストリングは入力ビットスライスに分割される。結果のビットストリングは結果のビットスライスに分割される。作用は、第１のビットストリームからの第１の入力ビットスライスと第２のビットストリングからの第２の入力ビットスライスとに基づく。第１および第２の入力ビットスライスからより長いビット長の入力ビットスライスが選択される。より長い入力ビットスライスと、より短かいビット長の入力ビットスライスを有するビットストリングの複数の入力ビットスライスとがより長いビット長に等しい少なくとも一方のビットストリングのビット数まで作用に従って処理されて少なくとも１つの結果のビットスライスを形成する。
【選択図】図５

Description

本発明は、ビットストリングにブール演算を施すための方法とシステム、特に、最大ビットスライスを用いてビットストリングにブール演算を施すための方法と装置に関する。

ビットストリングは関係データベース管理システム(RDBMS) においてデータベースに格納されているレコード内で発生するデータ項目のインスタンスを表現するために用いることができる。データ格納に対する従来のアプローチでは、データの行と列に組織化されたテーブルを集めたものが利用されている。各列は情報の特定の形式を含み、各行はそれぞれの列で情報が異なる個別のレコードからなる。すべての行は同一の構造を有するレコードとして隣り合って格納される。このようなレコード指向のアプローチは多数の入出力を必要とし、複雑なインデックス機構を必要とし、データを周期的に戻し非正規化する必要がある。

これらの問題を実質的に軽減するRDBMS のデータ表現方法は10月７日に出願された国際出願 PCT／US88／03528 に記載されており、その開示全体は参照することによってここに組み込まれる。ビットストリングを用いたデータベーステーブルにおいてそれらの使用からデータ値を分離する列指向のアプローチを使用することによりデータベースが構造化される。情報を隣り合ったレコードとして格納するのでなく、データは列的に組織化された形で格納される。各テーブルをつくるデータ値はビットストリングを用いて分離され、ビットストリングの各々は各列からの１つの行のユニークな値を表わす。各ビットストリング内で、２進ビット値は与えられたレコード（または行）内の列値の発生率を示している。

RDBMS におけるように、クエリーを使ってデータベースに問い合わせを行なうことによって個々のデータレコードの位置を知ることができる。クエリー過程の共通の形式は、１対のビットストリングにブール演算を施してクエリーの条件を満足するデータベースレコードを表わす“結果のビットストリング”を形成することを含んでいる。

スペースを節約するため、ビットストリングはGlaser et al. の米国特許第 5,036,457に開示されたようなブール演算に従って圧縮、符号化および復号が可能であるが、この開示全体が参照によりここに組み入れられる。非圧縮の２進値ビットストリングはランまたはインパルスのいずれかからなる圧縮された２進ビット形式に変換される。反復的なループ構造を使って圧縮形の１対のインパルスにブール演算が施されて結果のビットストリングが形成される。この技術は通常行なわれているような１ビットずつの操作と比べて著しく高速である。

１対の圧縮されたインパルスが１対の符号化されたビットストリングから得られ、より短かい長さの（いわゆる最小の）インパルスが選択される。最小長インパルスの多数のビットに対してブール演算が施されこの最小長の結果のビットストリングが形成される。このサイクルが残りの最小長インパルスの各々に対して繰り返される。ブール演算を達成するに必要なサイクルの総数は２つの入力ビットストリングのインパルスの合計にほぼ等しい。多くの長いインパルスを有するビットストリングでは一般に問題にはならないが、多くの短かいインパルスを有するビットストリングを処理するための計算オーバーヘッドは過大である。それゆえ、不確定の長さの圧縮ビットストリングの対に対してブール演算を施す方法であって、各最小長インパルスに対する繰り返しを行なうことによる計算オーバーヘッドを回避できる方法へのニードがある。

本発明は最小長インパルスの代わりに最大長インパルスを使ってビットストリングにブール演算を施すための方法とシステムを提供することにより従来技術を改良する。

本発明の一具体例は、コンピュータを使ってビットストリングの連なりにブール演算を施して結果のビットストリングを形成するためのシステムと方法である。各ビットストリングは入力ビットスライスに分割される。結果のビットストリングは結果のビットスライスに分割される。第１のビットストリングからの第１の入力ビットスライスと第２のビットストリングからの第２の入力ビットスライスとに基づきブール演算による作用が決定される。第１の入力ビットスライスと第２のビットスライスとの中からより長いビット長の入力ビットスライスが選択される。より長いビット長に等しい少なくとも一方のビットストリングのビット数まで、より長い入力ビットスライスと、より短かいビット長の入力ビットスライスを有するビットストリングの複数の入力ビットスライスとが、決定された作用に従って処理されて少なくとも１つの結果のビットスライスを形成する。

本発明のさらに他の具体例が以下の詳細な記述から当業者に容易に明らかになるであろう。ここで、本発明を実施する上で企図された最良の形態の図解により本発明の具体例のみが示され記述される。理解されるように、本発明は他の異なる具体例が可能であり、そのいくつかの詳細は本発明の精神と範囲から逸脱することなく種々の自明な点で修正が可能である。したがって、図面と詳細な記述は例示にすぎず、限定的ではないと考えるべきである。

Ｉ．概説
図６，７および８を参照すると、本発明の一実施例はビットストリングＡ40及びＢ46の対にブール演算を施してビットストリングＣ52を生成する。ビットストリングＡおよびＢの双方は一連の入力ビットスライス41ａ，47ａ−ｊで表わされ、それらはこの例ではランとして処理される（ランおよびインパルスは後にさらに説明される）。ビットストリングＡ40とＢ46の対はブール演算に従って処理される。すなわち、ビットストリングＡ40とＢ46の対の各々からより長い長さ44を有するビットスライス41ａが選択され、この入力ビットスライス41ａはより長い長さ41ａに等しいビット数について他のビットストリング46の１つ以上のビットスライス47ａ−ｊに対して処理され、その結果として少なくとも１つのビットスライス53ａ−ｊの連なりが生成される。記述された具体例において、結果としてのビットスライス53ａが出力インパルスを生成するときはいつでも好ましくはそれはさらに処理されて符号化された格納効率の良い形式になる。
II．用語
“ビットストリング”とは２進ビットの列をいう。

“ラン”とは同じ２進値（またはジェンダ）のビットが１つ以上連続するビットストリングをいう。

“インパルス”とは同じ２進値（またはジェンダ）のビットの１つ以上の連続の後にその２進値と反対の２進値を持つ終了ビットが続くビットストリングをいう。

“特徴形式”とはビットストリングをランまたはインパルスのいずれかに分類するインジケータをいう。

“ジェンダ”とはランまたはインパルスの２進値を示すインジケータをいい、互換的に“極性”ともいわれる。

“非圧縮形”とはランまたはインパルスのいずれかである２進値の一次元アレイをいう。

“圧縮形”とはランまたはインパルスを（１）極性（２）特徴形式及び（３）長さで表わした表現形式をいう。

“符号化形式”とはパケット形式で格納される１つ以上連続するインパルスをいう。

Ａ．コンピュータシステムの説明
本発明に係り１対のビットストリングにブール演算を施すプログラム可能コンピュータとコンピュータプログラムを有するコンピュータシステムが図１に示される。このコンピュータシステムは、プログラム可能なマイクロプロセッサ２、ディスプレイ３、マイクロプロセッサ２のためのキーボード入力装置11およびビットストリングの格納またはバッファリングのための外部記憶装置12を含んでいる。変換のためのハードウェア、ソフトウェアまたはファームウェア及びブール演算のためのハードウェア、ソフトウェアまたはファームウェアはマイクロプロセッサ２に組み込まれたコンピュータプラットフォーム10（破線で示される）に収容されている。コンピュータプラットフォーム10はGlaser et al. の米国特許第 5,306,457号に示されたように、ビットストリングに対してブール演算を施すことに関連する種々の実体を調整する。

伝統的に、コンピュータプラットフォーム10は多くの標準的なコンピュータシステムで容易に採用することのできるプリント回路基板上に組み立てられた凡用プログラマブルコンピュータであり、それはその動作をここに開示されるように向けるためのコンピュータプログラムソフトウェアを備えた、パーソナル、ミニ、及びメインフレームコンピュータを含んでいる。コンピュータプラットフォーム10はまた集積回路チップ（またはチップの集合）上に形成された、または通常の手段でまたはマイクロコードとして読み出すことのできる実行可能な符号を焼き付けられた読み出し専用メモリ(ROM）チップを有する特殊目的のコンピュータでも良い。

Ｂ．コンピュータプログラムの説明
より特定的に、図２を参照すると、コンピュータプラットフォーム10はエンコーダ／デコーダ14、バス15と27でオプションとしてのバッファメモリ18に相互接続されたオプションとしての２次メモリ16（これはコンピュータプラットフォーム10の外に置くこともできる）、ブール論理ユニット(BLU）20、標準の処理ユニット25およびシステム調整器26を含んでいる。ビットストリングを符号化／復号化し、ブール演算を行ない、コンポーネント間のデータ転送を調整するソフトウェアプログラム（後にさらに説明する）がコンピュータプラットフォーム10にロードされると、コンピュータプラットフォーム10が形成され処理の準備が整う。

コンピュータプラットフォーム10の特殊なコンポーネントの詳細な議論をここに行なう。外部記憶装置12は符号化されたビットストリングを格納するための永続的またはバッファ的な記憶ユニットであり、典型的にはハードディスクである。ビットストリングは、関係データベース内の組織化されたデータ、外部通信手段が収集した組織化されていないデータ、または連続したビット列によって表わすことのできる任意の他の形式のデータを代表する。

外部装置12の内容はバス13によってコンピュータプラットフォーム10にロードされ、エンコーダ／デコーダ14にロードされ、エンコーダ／デコーダ14は符号化されたビットストリングを１つ以上の圧縮されたインパルスに分離する。この明細書を通してインパルスは１つの終了ビットを有するものとして記述されるが、１つの開始ビットを有するインパルスにも等しく適用される。また、“極性”および“ジェンダ”という用語は交換可能に使用され単に２進値をいう。ビットストリングを４つの異なる符号化されたインパルス形式の１つへ符号化またはそれから復号するためのエンコーダ／デコーダ14が実行するルーチンはGlaser et al, の米国特許第 5,036,457号に記述されている。

オプションとしての２次メモリ16は将来のブール演算のために圧縮されたビットストリングを格納するものであり、ホストコンピュータに含まれるメモリコンポーネントまたはコンピュータプラットフォーム10内に含まれるメモリコンポーネントであり得る。バッファメモリ18はBLU 20におけるビットストリングの処理の前または処理の後にビットストリングを２次メモリ16に格納する前に圧縮されたビットストリングを一時的に保持するための他のメモリ領域である。

BLU 20はインテル社製のペンティアム（登録商標）のようなマイクロプロセッサ（図示せず）上で実施されるBLU の具体例を利用して２つのビットストリングにブール演算を施す。ブール演算のいくつかまたはすべてはハードウェアでより効率的に実施することができる。しかしながら、ブール演算が主としてソフトウェアで実現されるとしても、BLU 20は圧縮されたビットストリングに対するブール演算を達成する現在公知の技術よりも格納、速度等の点でより効率的にブール演算を達成する。BLU 20は非常に速いクロック速度を持つ32ビットまたは64ビットのマイクロプロセッサのような最新のコンポーネントの利点をフルに取り入れることができる。

結果としてのビットスライス、すなわち、インパルスまたはランの対にブール演算が施された結果がBLU 20によって決定されると、結果のビットスライスはバス21によって標準処理ユニット25に送られる。標準処理ユニット25は結果の圧縮された（しかし符号化されていない）ビットスライスをそれらが圧縮されたインパルスに結合されるまで一時的に保持するための本質的に１対のバッファである。圧縮されたインパルスが標準処理ユニット25に形成されると、インパルスは符号化のためにバス23によってバッファメモリ18に出力される。

システム調整器26はコンピュータプラットフォーム10上でのデータの処理を制御する。バスシステムの動作およびコンピュータプラットフォーム10上のコンポーネントの動作はシステム調整器26のソフトウェアプログラムによって制御される。システム調整器26から出ている図２の点線は種々のコンポーネントに対する制御を示している。
IV．ビットストリングの形式
図３および図４を参照すると、圧縮されていないビットストリングと圧縮されたビットストリングとが２進ビット値33，36及び２値波形33′，36′として図解的に示されている。２進ビット値がこの明細書を通して言及されているが２値波形にも交換可能に適用できる。

Ａ．非圧縮形式
ビットスライスの２つのタイプは、ラン34とインパルス35である。これらは前述したようにいずれも生のビットストリングである。

Ｂ．圧縮形式
ラン34またはインパルス35のような各ビットスライスはスライスを圧縮形式で記述する属性５，６，７で表わすことができる。ビットスライスを伸長することなく属性５，６，７を使ってブール演算を達成することができる。記述された具体例において、入力属性は：特徴形式rS５；ジェンダgS６；及び長さlS７を含んでいる。特徴形式rS5 の“０”または“１”はスライスがそれぞれインパルス35またはラン34であることを示している。ジェンダgS６の“０”または“１”は終了ビットの前に続く１つ以上のビットのジェンダを示す。長さlS７はスライス内のビット数を示している。図３の例は、インパルスすなわちrS＝０で、ジェンダが“１”の連続ビットすなわちgS＝１で、長さが14ビットすなわちlS＝14であることを示している。

記述されている具体例はもっぱら圧縮形式に作用するが、本発明は生の非圧縮のビットストリングにもそれらを次のように圧縮することにより拡張可能である。各非圧縮ビットストリング33に対して、同じジェンダの１つ以上の連続ビットすなわちラン34をメモリ（図示せず）にシリアルに読み込み、ラン34とは反対のジェンダの単一ビットすなわち終了ビットが読まれるまで連続ビットを数えることによりストリングの各スライス34，35が形成される。ビットストリングの各インパルスが非圧縮形から圧縮形へ変換されるにつれ、属性５，６，７が生成される。特徴形式rS５にはビットストリングがインパルス35であることを示す“０”が格納され、ジェンダgS６にはラン34の適切なジェンダが格納され、長さlS７としてビットカウントが格納される。ブール演算が完了した後、結果のビットストリングをオプションとして非圧縮ビットストリング33に逆変換することができる。

１対の入力ビットストリング40，47がスライスＡおよびＢ（図示せず）を形成し、それぞれ特徴形式rA42とrB48、ジェンダgA43とgB49及び長さlA44とlB50を具備するものとする。そこで、長さはインパルスの長さであり、特徴形式rAとrBは次式から決定される。

rA＝（lA＜lB）｜rA （１）
rB＝（lA＞lB）｜rB （２）
ここでlAおよびlBは前に定義された長さである。式（１）及び（２）は“０”または“１”を返しそれらはスライスＡおよびＢがそれぞれインパルス35またはラン34として処理され戻り値を特徴形式rA42またはrB48として格納することを示す。等値性、すなわち、長さ44，50が等しいことは、ブール条件−rA ＆ −rBで表わされそれは双方のビットスライスが同じ長さのインパルスであることを示している。

Ｃ．ビットストリング形式間の関係
図５を参照すると、生のビットストリング、符号化ビットストリング及び圧縮インパルスの関係を示す流れ図が示されている。生のビットストリング（ブロック120)はビットストリング変換手段121好ましくはプロセッサ２によって圧縮インパルス（ブロック122)に変換される。符号化ビットストリング（ブロック123)は復号手段124 、好ましくはエンコーダ／デコーダ14によって圧縮インパルス（ブロック122)に復号される。

ブール演算125 は本発明によれば１対の圧縮インパルス（ブロック122)に対して行なわれ、結果の圧縮インパルス（ブロック126)を形成する。オプションとして、結果の圧縮インパルス（ブロック126)は符号化手段127 好ましくはエンコーダ／デコーダ14によって符号化ビットストリング（ブロック128)に変換される。
Ｖ．ビットストリング処理
図６，７，８，９および10を参照すると、１対のビットストリングＡ40とＢ46が主プログラムループの各サイクルの中で最長（最大）カレントビットスライス41ａの長さを使って反復的に処理されて結果のビットストリング52，58，64を形成する。上記の様に、１対のビットストリングＡ40とＢ46と各結果のビットストリング52，58，64が２進ビット値40，46，52，58，64および２値波形40′，46′，52′，58′，64′として示されている。２進ビット値がこの明細書を通して言及されるが、同じ記述が互換的に２値波形にも適用される。

結果のビットストリングＣ52における各結果のビットスライス53ａ−ｊに対する結果の属性54，55，56は、以下にさらに詳細に記述される５つの出力関数によって決定される。各関数からの出力は各入力ビットスライス41ａ，47ａ−ｊに関する入力属性42，43，44，48，49，50から得られる入力パラメータに基づくものである。

主プログラムの各サイクルの中で処理されるビットの数は次式で表わされるような２つのスライスの長い方のビット数である。

lC＝MAX (lA, lB)−take （３）
ここでlAとlBは入力ビットストリングＡ40とＢ46の各々についての長さ41ａ，47ａのような入力ビットスライスの長さであり、lCは結果のビットストリング52，58，64についての結果のビットスライス47ａ，53ａ，65ａの長さであり、MAX( )は最大ビットスライス長を戻す関数であり、takeは入力スライス41ａ，47ａの長さが等しくないとき１値（“１”）であり、それ以外ではゼロ値（“０”）である。各サイクルの中で非常に多数のゼットを処理できるので、最小長インパルス技術よりも著しいスピードアップが達成される。

Ａ．入力パラメータ
入力パラメータを決定するためには次の３項目の情報を知り確認しなければならない：図11，12，13，14，15，16，17，18および19に表わされる所望のブール演算；ビットストリングＡ40における各入力ビットスライス41ａについての入力属性42，43，44；およびビットストリングＢ46における各入力ビットスライス47ａについての入力属性48，49，50。

３つの基本的なブール演算が実装される：図11，14，17および20に示されるAND ；図12，15，18および21に示されるOR；図13，16，19，22および23に示される XOR（排他的OR）、
特に記述されないが、さらなるブール演算または派生物が表１に示すように達成できる。さらに、３つ以上の入力に対するブール演算が想定できる。さらに、例えば、ブール演算子はNAND（AND の補数）、 NOR（ORの補数）、XNOR（XOR の補数）、XAND（排他的AND)および XNAND（排他的AND の補数）を含んでいる。派生物は加法性、可換性および分配性またはド・モルガンの定理のような通常のブール代数の性質や定理を適用することによって形成される等価的または組み合わせ的ブール演算子を含む。上記のリストは完全なものではなく本発明の範囲内でさらに他のブール演算が可能である。

Ｂ．出力関数
以下の記述において、それぞれの作用または出力関数はブール演算AND, OR およびXOR の各形式に１つのカルノー図で表わされる。各カルノー図は行と列からなる表である。例えば図11を参照すると、各行はビットストリングＡ40の各ビットスライス41ａの入力属性42，43からの特徴形式rA70およびgA71でインデックスされる。各列はビットストリングＢ46の各ビットスライス47ａ−ｊの入力属性48，49からの特徴形式rB73とジェンダgB74によってインデックスされる。ビットストリングＡ40からの特徴形式とジェンダのペアrA,gAとビットストリングＢ46についての特徴形式とジェンダのペアrB, gBが特定されることによってカルノー図の行72の１つと列75の１つが特定される。各関数の出力は特定された行および列の交点の２進値によって示される。

１．作用関数
ブール関数AND, OR およびXOR の演算について達成されるべき作用の形式を示すカルノー図はそれぞれ図11，12および13に示される。作用はコピー作用またはスキャン作用のいずれかである。各サイクルの間、入力ビットストリングＡ40とＢ46の各々に対するビットスライス41ａ，47ａのような２つの入力ビットスライスから最大すなわち最長の入力ビットスライスが選択される。

短かい方のビットスライスからの１つ以上の入力ビットスライスの個々のジェンダと長さを考慮する必要があるならばコピー作用が行なわれる。そうでなければ、スキャン作用が行なわれる。しかし、入力ビットスライスの長さが同じであれば、スキャンまたはコピー作用のいずれを行なっても良い。この場合、スキャン作用の方がコピー作用よりも速いのでスキャン作用が好ましい。

従って、コピーまたはスキャン作用のいずれかが要求される状況はカルノー図80，81，82中でそれぞれ１値（“１”）及びゼロ値（“０”）としてテーブル化されている。１値（“１”）は、より長いビット長に等しい数のビット数まで入力ビットストリングがスライスごとにコピーされることを示している。結果のビットスライスは１以上のより短かい入力ビットスライスの各々に対する属性に基づくものであるから、より長いビット長の入力ビットスライスは無視される。ゼロ値（“０”）は長さlCに等しいビット数までより短かい入力ビットストリングがスキャンされなければならないことを示している。結果のビットスライスは長さlCの属性に基づくものであるから、１つ以上のより短かい入力ビットスライスのジェンダが出力では無視される。

２．特徴形式関数
ブール関数AND, OR およびXOR の演算に対する結果のビットスライス53ａ−ｊ，59ａ−ｊ，65ａ−ｊの特徴形式rC54，60，66を示すカルノー図が図14，図15および図16にそれぞれ示されている。特徴形式はランまたはインパルスのいずれかである。したがって、結果のビットスライスにランまたはインパルスのいずれが出力されるかの状況がカルノー図85，86，87にランに対する１値（“１”）およびインパルスに対するゼロ値（“０”）としてテーブル化されている。

３．ジェンダ関数
ブール関数AND, OR およびXOR の演算に対する結果のビットスライス53ａ−ｊ，59ａ−ｊ，65ａ−ｊのジェンダgC55，61，67を示すカルノー図がそれぞれ図17，18および19に示されている。従って、適切なジェンダはカルノー図90，91，92に１値（“１”）およびゼロ値（“０”）としてそれぞれテーブル化されている。

４．take関数
ブール関数AND, OR およびXOR の演算に対して“take”ビットが必要かどうか示すカルノー図がそれぞれ図20，21および22に示されている。takeビットは以前に記述した式（３）に従いより長いビット長44から差し引かれる単一ビット値である。takeビットはビットストリングＡ40とＢ46の対の各々からの入力ビットスライス41ａ，47ａの長さlA44とlB50の関数である。長さが等しくなければtakeビットは１に設定され、それ以外では“０”に設定される。したがってtakeビットが必要であるか（否か）の状況はカルノー図95，96，97に１値（“１”）およびゼロ値（“０”）としてそれぞれテーブル化されている。

５．フリップ関数
ブール関数XOR の演算について“フリップ”作用が行なわれなければならないかを示すカルノー図が図23に示されている。フリップビットとして表わされるフリップ作用とはカレントビットスライス47ａ−ｊから出力されるかまたは決定される各ビットのジェンダを“フリッピング”することにより結果のビットスライス65ａ−ｉのジェンダが反転されなければならないかを意味する。したがって、フリップ作用が行なわれるか（否か）の状況はカルノー図102 に１値（“１”）およびゼロ値（“０”）としてそれぞれ（フリップビットとして）テーブル化されている。ブール関数AND とORの演算に対するカルノー図はない。というのは、それらのブール演算に対して結果のビットスライス53ａ−ｉ，59ａ−ｉは決して反転されないからカルノー図はすべてゼロ値であるからである。

Ｃ．出力関数ルックアップテーブル
図11，12，13，14，15，16，17，18，19，20，21，22および23の５つの関数に対するカルノー図が組み合わせられて図24に出力関数のルックアップテーブルとして示されている。入力ビットスライスの特徴形式とジェンダおよびブール関数AND, OR およびXOR の演算の各々に対応する関数からの出力にそれぞれ相当する４組の列がある。特に、第１列はビットストリングＡ40の各ビットスライス41ａについての入力属性42，43からの特徴形式rA70とジェンダgA、およびビットストリングＢ46の各ビットスライス47ａ−ｊについての入力属性48，49に対する特徴形式rB70とジェンダgB74によってインデックスされる。ブール関数AND, OR およびXOR の演算に対する列は作用ａ80，81，82、特徴形式rC85，86，87、ジェンダgC90，91，92、takeビットｔ95，96，97およびフリップビットｆ100, 101, 102 に相当する出力を含んでいる。ビットストリングＡ40からの特徴形式rAとジェンダgAのペア及びビットストリングＢ46についての特徴形式rBとジェンダgBのペアが特定されてルックアップテーブルの行106 が選択される。各関数105 の出力は行106 と選択されたブール演算に対する出力関数に相当する列との交点にある。
VI．実施例
図26および27を参照すると、理解を容易にするため、図24の出力関数ルックアップテーブルを図解的に表わすテーブルが示されている。それは、ビットストリングＡ40からの特徴形式rAとジェンダgAのペアおよびビットストリングＢ46についての特徴形式rBとジェンダgBのペアを使ってルックアップテーブルと同じ形でインデックスされている。作用、結果のビットスライスの特徴形式rCとジェンダgC、takeビットおよびフリップビットはブール関数AND, OR およびXOR でそれぞれまとめられた列110, 111および112 にテキスト形式115 で記述されている。さらに、入力ビットスライス41ａ，47ａの各々に対するそれぞれの入力属性42，43，44，48，49，50、そして特に、特徴形式rA42とrB48、ジェンダgA43とgB49及び長さlA44とlB50が列113 に図解的に描かれている。図24のルックアップテーブルと同様に、出力関数の各々の出力115 が、入力属性に相当する行と選択されたブール演算に相当する列110, 111, 112 の交点に記述されている。

ビットスライスの対に対する２値波形を図解的に示しそれ故に理解が容易な図26および27を参照して各ブール演算の例を記述する。

Ａ．ブール関数AND の演算
所望のブール演算がAND110であるとする。入力ビットストリングＡ40とＢ46の対は図６および７に示されている。結果のビットストリングＣ52は図８に示されている。第１のビットスライス41ａがビットストリングＡ40から選択され第２のビットスライス47ａがビットストリングＢ46から選択される。第１のビットスライス41ａは式（１）から計算された“１”に等しい特徴形式rA42（第１のビットスライス41ａはより短かいビットスライスの長さまでは“ラン”であることを示す）、“１”のジェンダgA43（第１のビットスライス41ａは極性が“１”のランを含んでいることを示す）および34ビットの長さlA44を含む入力属性を有している。より短かいビットスライス47ａの長さまでの第２のビットスライスは“０”の特徴形式rB48（第２のビットスライス47ａはより短かいビットスライスの長さまではインパルスであることを示す）、“０”のジェンダgB（第２のビットスライス47ａは極性が“０”のランを含んでいることを示す）および６ビットの長さlB50を含む入力属性を有している。

図26および27の“1100”に等しい行114 (rA, gA, rB およびgBを組み合わせてビットストリング“1100”が形成された）が選択されAND 演算（列110)に対する出力関数から出力が決定される。第１のビットスライス41ａは第２のビットスライス47ａよりも長いビット長lA44を有しているから、ビットストリングＢ46のより短かいビットスライス47ａ−ｊの各々が第１のビットスライス41ａの長さlA44からtakeビットを引いたものに等しいビット数、すなわち33ビットまで結果のビットスライスＣ52へとコピーされる。コピーが完了したら、第１のビットスライス41ａには１ビットが残り、第２のビットスライスはビットスライス47ｊとなりその中の１ビットが（暗黙の後縁のゼロビットとともに）残る。

次に、図26および27の“1010”に等しい行116 が選択される（列110)。ビットスライス41ａの残りの部分はより短かいビットスライス47ｊよりも長いビット長lA44（暗黙の後縁ビットのゼロを含む）を有するので、ビットストリングＢ46のより短かいビットスライス47ｊがスキャンされその後入力終了状態が検知されて演算が完了する。

Ｂ．ブール関数ORの演算
所望のブール演算がOR 111であるとする。入力ビットストリングＡ40とＢ46の対は図６および７に示されている。結果のビットストリングＣ58は図９に示されている。第１のビットスライス41ａがビットストリングＡ40から選択され第２のビットスライス47ａがビットストリングＢ46から選択される。第１のビットスライス41ａは式（１）から計算された“１”に等しい特徴形式rA42（第１のビットスライス41ａはより短かいビットスライスの長さまでは“ラン”であることを示す）、“１”のジェンダgA43（第１のビットスライス41ａは極性が“１”のランを含んでいることを示す）および34ビットの長さlA44を含む入力属性を有している。より短かいビットスライス47ａの長さまでの第２のビットスライスは“０”の特徴形式rB48（第２のビットスライス47ａはより短かいビットスライスの長さまではインパルスであることを示す）、“０”のジェンダgB（第２のビットスライス47ａは極性が“０”のランを含んでいることを示す）および６ビットの長さlB50を含む入力属性を有している。

図26および27の“1100”に等しい行114 が選択されOR演算（列111)に対する出力関数から出力が決定される。第１のビットスライス41ａは第２のビットスライス47ａよりも長いビット長lA44を有しているから、ビットストリングＢ46のより短かいビットスライス47ａ−ｊの各々が第１のビットスライス41ａの長さlA44からtakeビットを引いたものに等しいビット数、すなわち33ビットまで結果のビットスライスＣ58へとスキャンされる。スキャンが完了したら、第１のビットスライス41ａには１ビットが残り、第２のビットスライスはビットスライス47ｊとなりその中の１ビットが残る。

次に、図26および27の“1010”に等しい行116 が選択される（列110)。ビットスライス41ａの残りの部分はより短かいビットスライス47ｊよりも長いビット長lA44（暗黙の後縁ビットのゼロを含む）を有するので、ビットストリングＢ46のより短かいビットスライス47ｊがコピーされその後入力終了状態が検知されて演算が完了する。

Ｃ．ブール関数XOR の演算
所望のブール演算がXOR 112 であるとする。入力ビットストリングＡ40とＢ46の対は図６および７に示されている。結果のビットストリングＣ64は図10に示されている。第１のビットスライス41ａがビットストリングＡ40から選択され第２のビットスライス47ａがビットストリングＢ46から選択される。第１のビットスライス41ａは式（１）から計算された“１”に等しい特徴形式rA42（第１のビットスライス41ａはより短かいビットスライスの長さまでは“ラン”であることを示す）、“１”のジェンダgA43（第１のビットスライス41ａは極性が“１”のランを含んでいることを示す）および34ビットの長さlA44を含む入力属性を有している。より短かいビットスライス47ａの長さまでの第２のビットスライスは“０”の特徴形式rB48（第２のビットスライス47ａはより短かいビットスライスの長さまではインパルスであることを示す）、“０”のジェンダgB（第２のビットスライス47ａは極性が“０”のランを含んでいることを示す）および６ビットの長さlB50を含む入力属性を有している。

図26および27の“1100”に等しい行114 が選択されXOR 演算（列112)に対する出力関数から出力が決定される。第１のビットスライス41ａは第２のビットスライス47ａよりも長いビット長lA44を有しているから、ビットストリングＢ46のより短かいビットスライス47ａ−ｊの各々が第１のビットスライス41ａの長さlA44からtakeビットを引いたものに等しいビット数、すなわち33ビットまで結果のビットスライスＣ64へとコピーされる。コピーが完了したら、第１のビットスライス41ａには１ビットが残り、第２のビットスライスはビットスライス47ｊとなりその中の１ビットが残る。

次に、図26および27の“1010”に等しい行116 が選択される（列110)。ビットスライス41ａの残りの部分はより短かいビットスライス47ｊよりも長いビット長lA44（暗黙の後縁ビットのゼロを含む）を有するので、ビットストリングＢ46のより短かいビットスライス47ｊがコピーされその後入力終了状態が検知されて演算が完了する。
VII ．コンピュータプログラム構造
図１のシステムにおいて使用するためのコンピュータプログラムの構造と、本発明に係りブール演算を達成するためのコンピュータプログラムによって創出されるプロセスが図28−30の流れ図に図解的に示される。

Ａ．最大ループ
結果のビットストリングＣを形成するために、ビットストリングＡおよびＢの対についてブール演算110, 111, 112 を施すためのプロセスが図28に示される。その目的は、各サイクルの中で長さlCの最大ビットスライスに等しいビット数までビットストリングＡおよびＢの対からのビットスライスをブール演算に従って反復的に処理することにある。

それらの入力属性42，43，44，48，49，50を含むビットストリングＡ40およびＢ46は２次メモリ16に格納され、処理のためにBLU 20へロードされるに先立ってバッファメモリ18に格納される。ビットストリングＡ40とＢ46のそれぞれを反転させることを表わす１対の反転インジケータフラグcAおよびcBが設定される（ブロック149)。次に主プログラムループ（ブロック 150−166)に入る。ビットスライス41ａ，47ａがビットストリングＡ40とＢ46のそれぞれから選択され、それぞれの長さlA44とlB50、ジェンダgA43とgB49、および特徴形式rA42とrB48を含む入力属性が決定される（ブロック 150）。ジェンダgA43とgB49はそれぞれの反転インジケータフラグcAとcBにより、後者のフラグがセットされていたら反転される（ブロック151)。これらの入力属性に基づき、達成されるべき作用（スキャンまたはコピー）80，81，82、結果のビットスライス53ａ−ｊ，59ａ−ｂ，65ａ−ｊの特徴形式rC85，86，87とジェンダgC90，91，92、およびtakeビット95，96，97またはフリップビット100, 101, 102 が必要であるかが決定される（ブロック152)。

図25を参照すると、図24に示されるルックアップテーブルに示される作用ａ、特徴形式rC、ジェンダgC、takeビットｔおよびフリップビットｆを格納するための２次元アレイfunctions 〔３〕〔16〕（３列16行）を記述するデータ構造が示されている。３つの列は所望のブール演算（AND, OR またはXOR)を示すためであり、16の行は所望のブール演算に対応する作用ａ、特徴形式rC、ジェンダgC、takeビットｔおよびフリップビットｆを格納するためである。アレイfunction〔３〕〔16〕は所望のブール演算によってインデックスされて列が選択され、ストリングＡ40の特徴形式rAとジェンダgAとストリングＢ46の特徴形式rBとジェンダgBでインデックスされて行が選択される。アレイfunction〔３〕〔16〕は外部記憶装置12に格納され、コンピュータプログラムのソフトウェアがプログラムのスタートアップ時にロードされるとき２次メモリ16へ読み込まれる。作用、特徴形式およびジェンダが決定され格納されると、ストリングＡ40とストリングＢ46の対について入力ビットスライス41ａ，47ａの中からそれらのビット長lA44とlB50を比較することによってより長いビット長を持つ入力ビットスライスが選択される（ブロック153)。ビットストリングＡ40からの入力ビットスライス41ａがより長いビット長lA44を持つならば、結果のビットスライス53ａ，59ａ，65ａのビット長lC56，62，68はビットスライス長lA44に等しく設定される（ブロック154)。ビットストリングＢ46からのビットスライス47ａがより長いビット長lB50を持つならば、ビットストリングＡ40とＢ46及びそれらの反転インジケータフラグcAとcBがスワップされる（ブロック155)。その理由は、取り扱いを簡単にするためより長いビット長を持つビットスライスを有するビットストリングが常にビットストリングＡになるようにするためである。次に、結果のビットスライス53ａ，59ａ，65ａのビット長lC56，62，68がビット長lB50に等しく設定される（ブロック156)。

入力ビットスライス41ａ，47ａの対に対する入力属性42，43，48，49に基づきtakeビット95，96，97が決定され、takeビットがゼロでなければ（ブロック157)、結果のビットスライス53ａ，59ａ，65ａの長さlC56，62，68がデクリメントされ、より長いビットスライス41ａの長さlA44が結果のビットスライス47ａ，53ａ，65ａの長さlC56，62，68だけ減らされる（ブロック159)。そうでなくてtakeビットがゼロであれば（ブロック157)、もしあればビットストリングＡ40すなわちより長いビットスライスを持つビットストリングの中のビットスライス41ａに続く次の入力ビットスライス（図６に示されるビットストリング40では次の入力ビットスライスはない）が２次メモリ16から獲得される（ブロック160)。

（ブロック152 で決定されたような）コピー作用が必要であれば（ブロック161)、33に等しい数のビット（結果のビットスライス53ａ−ｉ，65ａ−ｉの長さlC56，62，68）がビットストリングＢ46からコピーされる（ブロック162)。これはさらに図29との関係において以下に記述される。（ブロック152 で決定されたような）スキャン作用が必要であれば（ブロック161)、33に等しい数のビット（結果のビットスライス59ａの長さlC56，62，68）がビットストリングＢ46からスキャンされる（ブロック163)。これもさらに図30との関係において以下に記述される。

入力終了変数eoiBで示されるように、ビットストリングＢ46の終わりが検出されたら（ブロック164)、ビットストリングＡ40内の残りのビットはビットストリングＡ40の残りのビットを標準プロセッサ25に出力することによって処理され（ブロック165)それによってプログラムが終了する。そうでなくてビットストリングＢ46の終わりが検出されず（ブロック164)、入力終了変数eoiAで示されるように、ビットストリングＡ40の終わりが検出されたら（ブロック166)、ビットストリングＢ46の残りのビットはビットストリングＢ46の残りのビットを標準プロセッサ25へコピーすることによって処理され（ブロック167)それによってプログラムが終了する。そうでなくてビットストリングＡ40の終わりが検出されなかったら（ブロック166)、制御はもしあれば次の入力ビットスライス41ａ，47ｊの組のために主プログラムループ（ブロック 151−166)の先頭に戻る。

Ｂ．コピー手続
上記のプロセスに基づくコピー作用（ブロック162)を達成する手続が図29に示されている。その目的は結果のビットストリングＣ52，58，64に対する結果のビットスライス53ａ，59ａ，65ａの長さlC56，62，68に等しい数のビットをビットストリングＢ46からスライスごとにコピーすることである。初めに、結果のビットスライス53ａ，59ａ，65ａのジェンダgC55，61，67、特徴形式rC54，60，66および長さlC56，62，68がそれぞれプログラム変数ｇ，ｒおよびlenに格納される（ブロック180)。

ビットストリングＢ46の１つ以上の入力ビットスライス47ａ−ｊの各々を処理するためのループ（ブロック 181−190)が開始する。最初に、現在の入力ビットスライス47ａに対する特徴形式rB48と長さlB50が現在の結果のビットスライス53ａ，65ａの特徴形式rC54，66および長さlC56，58にコピーされる（それぞれブロック181 および182)。プログラム変数len の値が現在のビットスライス47ａ−ｉの長さlB50だけ減じられる（ブロック183)。結果のビットスライス53ａ，65ａのジェンダgC55，67が現在の入力ビットスライス47ａ−ｉのジェンダgB49と同じ値に設定される。ただし、フリップビット100, 101, 102 または反転インジケータフラグcBがオンであれば、結果のビットスライス53ａ，65ａのジェンダgC55，67は反転される（ブロック184)。特徴形式rC54，66、ジェンダgC55，67および長さlC56，68を含む現在の結果のビットスライス53ａ，65ａが標準プロセッサ25へ出力され（ブロック185)、ビットストリングＢ46の次の入力ビットスライス47ｂが獲得される（ブロック186)。入力終了変数eoiBで示されるように、ビットストリングＢ46の終わりが検出されたら（ブロック187)、処理ループ（ブロック 181−190)からブロック188 へ抜ける。処理を完了するため、結果のビットスライス53ａ，65ａの特徴形式rC54，66とジェンダgC55，67はプログラム変数ｒとｇに格納されていた（ブロック180)特徴形式とシェンダに設定される（それぞれブロック188 と189)。上記のように、フリップビットまたは反転インジケータフラグcBがセットされていれば結果のビットスライス53ａ，65ａのジェンダgC55，67が反転される（ブロック189)。ビットストリングＢ46の終わりが検出されなければ（ブロック187)、プログラム変数len における長さが現在の入力ビットスライス47ｂ−ｉと比較される。格納されている長さlen が現在の入力ビットスライス長lB50よりも短かければ、処理ループ（ブロック 181−190)から抜ける。そうでなければ、処理は処理ループ（ブロック 181−190)の先頭に続く。

処理ループ（ブロック 181−190)から抜けたら（ブロック190)、結果のビットスライス53ａ，65ａの特徴形式rC54，66とジェンダgC55，67は値１（“１”）と現在の入力ビットスライス47ｂ−ｉのジェンダgB49に設定される（それぞれブロック 191と192)。上記したように、フリップビットまたは反転インジケータフラグcBがセットされていれば、結果のビットスライス53ａ，65ａのジェンダgC55，67は反転される（ブロック192)。さらに、現在の入力ビットスライス47ｂ−ｉはプログラム変数len の値だけ減じられる（ブロック193)。最後に、結果のビットスライス53ａ，65ａの長さlC56，68がプログラム変数len の長さに設定され（ブロック194)、特徴形式rC54，66、ジェンダgC55，67および長さlC56，58を含む現在の結果のビットスライス53ａ，65ａが標準プロセッサ25へ出力される（ブロック195)。ビットストリングＢ46に対する長さlB50、特徴形式rB48、ジェンダgB49および入力終了変数eoiBが戻される（ブロック196)。

Ｃ．スキャン手続
上記のプロセスに基づくスキャン（ブロック163)を達成する手続が図30に示される。その目的は、長さlCに等しいビット数までビットストリングＢの１つ以上の入力ビットスライス47ａ−ｊをスキャンすることにある。特徴形式rC60、ジェンダgC61および長さlC62を含む現在の結果のビットスライス59ａが標準プロセッサ25へ出力される。

ビットストリングＢ46の１つ以上のより短かい入力ビットスライス47ａ−ｉを処理するためのループ（ブロック 201−204)が始まる。最初に、結果のビットスライス59ａの長さlC62がビットストリングＢ46の長さlB50に等しいビット数だけ減じられる（ブロック201)。入力ビットストリングＢ46の次の入力ビットスライス47ｂが獲得される（ブロック202)。入力終了変数eoiBによって示されるビットストリングＢの終わりが検出されたら、処理ループ（ブロック 201−204)から抜ける。そうでなければ、結果のビットスライス59ａの長さlC62が現在の入力ビットスライス47ｂの長さlBよりも小さければ（ブロック204)、処理は処理ループ（ブロック 201−204)の先頭に続く。そうでなければ、処理ループ（ブロック 201−204)から抜けて現在の入力ビットスライス47ｂ−ｉの長さlB50が結果のビットスライス59ａの長さlC62に等しいビット数だけ減じられる（ブロック205)。長さlB50、特徴形式rB48、ジェンダgB49および入力終了変数eoiB Ｂ46が戻される（ブロック206)。

本発明が好適な実施例を参照して特定的に示され記述されたが、当業者であれば本発明の範囲および精神から逸脱することなく形式および詳細において前記およびそれ以外の変更を加え得ることがわかるであろう。

本発明に係りブール演算を達成するためのコンピュータプラットフォームを備えたコンピュータシステムの機能ブロック図である。 図１のコンピュータプラットフォームの機能ブロック図である。 例として非圧縮ビットストリングを示す図である。 例として圧縮ビットストリングを示す図である。 生のビットストリング、符号化ビットストリング、および圧縮ビットストリングの関係を示すフローチャートである。 非圧縮ビットストリングを表わす図である。 非圧縮ビットストリングを表わす図である。 図６および７の非圧縮ビットストリングにブール関数ANDの演算を施して形成される非圧縮の結果のビットストリングを表わす図である。 図６および７の非圧縮ビットストリングにブール関数ORの演算を施して形成される非圧縮の結果のビットストリングを表わす図である。 図６および７の非圧縮ビットストリングにブール関数XORの演算を施して形成される非圧縮の結果のビットストリングを表わす図である。 ブール関数ANDの演算に対応する作用関数のカルノー図である。 ブール関数ORの演算に対応する作用関数のカルノー図である。 ブール関数XORの演算に対応する作用関数のカルノー図である。 ブール関数ANDの演算に対応する特徴形式関数のカルノー図である。 ブール関数ORの演算に対応する特徴形式関数のカルノー図である。 ブール関数XORの演算に対応する特徴形式関数のカルノー図である。 ブール関数ANDの演算に対応するジェンダ関数のカルノー図である。 ブール関数ORの演算に対応するジェンダ関数のカルノー図である。 ブール関数XORの演算に対応するジェンダ関数のカルノー図である。 ブール関数ANDに対応するtakeビット関数のカルノー図である。 ブール関数ORに対応するtakeビット関数のカルノー図である。 ブール関数XORに対応するtakeビット関数のカルノー図である。 ブール関数XORに対応するフリップビット関数のカルノー図である。 図11，12，13，14，15，16，17，18，19，20，21，22および23の作用、特徴形式、ジェンダ、takeビットおよびフリップ関数を融合させた出力関数ルックアップテーブルである。 図24の出力関数ルックアップテーブルを格納するデータ構造を示す図である。 図24のルックアップテーブルを図解的に表わすテーブルの一部である。 図24のルックアップテーブルを図解的に表わすテーブルの残りの一部である。 本発明に係るブール演算を達成する方法の流れ図である。 図28の方法で使用されるコピー関数の流れ図である。 図28の方法で使用されるスキャン関数の流れ図である。

Claims (25)

1. 関係データベース管理システムを動かすためのコンピュータを使用してビットストリングにブール演算を施して結果のビットストリングを形成するためのステップを具備する方法であって、ビットストリングは関係データベース管理システムにおける組織化されたデータを表わし、結果のビットストリングはユーザによるクエリーの条件を満足する関係データベース管理システムにおけるレコードを表わし、各ビットストリングは入力ビットスライスに分割され、結果のビットストリングは結果のビットスライスに分割され、コンピュータを使用するステップはさらに、関係データベース管理システムにおける組織化されたデータを表わす第１のビットストリングからの第１の入力ビットスライスと関係データベース管理システムにおける組織化されたデータを表わす第２のビットストリングからの第２の入力ビットスライスとに基づきブール演算による作用を決定し、
   第１の入力ビットスライスと第２の入力ビットスライスとの中からより長いビット長の入力ビットスライスを選択し、
   より長いビット長を有するビットストリングのビット数まで、より長い入力ビットスライスと、より短かいビット長の入力ビットスライスを有するビットストリングの複数の入力ビットスライスとを、決定された作用に従って処理してユーザのクエリーの条件を満足する結果のビットストリングについて少なくとも１つの結果のビットスライスを形成する各ステップを具備する方法。
2. 各入力ビットスライスは属性で表わされ、前記決定するステップは、第１の入力ビットスライスを表わす属性と第２の入力ビットスライスとに基づいて作用を特定し、前記処理するステップは、決定された作用に従って属性を処理する請求項１記載の方法。
3. 第１の圧縮ビットスライスから第１の入力ビットスライスの入力属性を決定し第２の圧縮ビットスライスから第２の入力ビットスライスの入力属性を決定するステップをさらに具備し、前記決定するステップは第１の入力ビットスライスの入力属性を第２の入力ビットスライスの入力属性と比較するステップを具備する請求項２記載の方法。
4. 各圧縮ビットスライスは、圧縮ビットスライスが表わす各入力ビットスライスの特徴形式を示すための特徴形式インジケータを具備し、第１の圧縮入力ビットスライスの特徴形式インジケータを第１の入力ビットスライスの入力属性に結合し、第２の圧縮入力ビットスライスの特徴インジケータを第２の入力ビットスライスの入力属性に結合する段階をさらに具備する請求項２記載の方法。
5. 各圧縮ビットスライスは圧縮ビットスライスが表わす各入力ビットスライスの２進値を示すジェンダインジケータを具備し、第１の圧縮入力ビットスライスのジェンダインジケータを第１の入力ビットスライスの入力属性に結合し、第２の圧縮入力ビットスライスのジェンダインジケータを第２の入力ビットスライスの入力属性に結合するステップをさらに具備する請求項２記載の方法。
6. 各圧縮ビットスライスは圧縮ビットスライスが表わす各入力ビットスライスの長さを示す長さインジケータを具備し、第１の圧縮入力ビットスライスの長さインジケータを第１の入力ビットスライスの入力属性に結合し、第２の圧縮入力ビットスライスの長さインジケータを第２の入力ビットスライスの入力属性に結合するステップをさらに具備する請求項２記載の方法。
7. 第１の入力ビットスライスと第２の入力ビットスライスの双方の入力属性はそれぞれが特徴形式を具備し、作用を決定するために第１の入力ビットスライスの特徴形式を第２の入力ビットスライスの特徴形式と比較するステップをさらに具備する請求項２記載の方法。
8. 各入力ビットスライスの入力属性はそれぞれの入力ビットスライスのビットの２進値を示すジェンダを具備し、作用の決定のために第１の入力ビットスライスのジェンダを第２の入力ビットスライスのジェンダと比較するステップをさらに具備する請求項２記載の方法。
9. 各入力ビットスライスの入力属性はビット長を具備し、作用の決定のために第１の入力ビットスライスビット長を第２の入力ビットスライスのビット長と比較するステップをさらに具備する請求項２記載の方法。
10. 入力ビットスライスの少なくとも一方はインパルスを具備し、インパルスは同じ２進値の少なくとも１つの連続する２進ビットとそれに続き少なくとも１つの連続２進ビットの一方の終わりに反対の２進値の２進ビットを具備し、前記処理するステップはインパルスを処理するステップを具備する請求項１記載の方法。
11. 前記決定するステップは結果のビットストリングを表わす各結果のビットスライスの少なくとも１つの結果の属性を特定する請求項１記載の方法。
12. 各結果のビットスライスの結果の属性は結果のビットスライスの複数の特徴形式の１つを示す特徴形式を具備し、前記処理するステップは特徴形式を決定するステップを具備する請求項11記載の方法。
13. 各結果のビットスライスの結果の属性は結果のビットスライスの複数のジェンダの１つを示すジェンダを具備し、前記処理するステップはジェンダを決定するステップを具備する請求項11記載の方法。
14. 各結果のビットスライスの結果の属性は結果のビットスライスのビット数を示すビット長を具備し、前記処理するステップはビット長を決定するステップを具備する請求項11記載の方法。
15. 前記処理するステップは、より短かいビット長の入力ビットスライスを有するビットストリングの複数の入力ビットスライスへのコピー作用を達成するステップを具備する請求項１記載の方法。
16. 前記処理するステップはより長い入力ビットスライスへのスキャン作用を達成するステップを具備する請求項１記載の方法。
17. 第１のビットストリングからの第１の入力ビットスライスと第２のビットストリングからの第２の入力ビットスライスとに基づきフリップ関数が必要であるかを決定し、
    フリップ関数が必要とされるとき、処理するステップの中で第１の入力ビットスライスまたは第２の入力ビットスライスへフリップ関数を施すステップをさらに具備する請求項１記載の方法。
18. 第１のビットストリングからの第１の入力ビットスライスと第２のビットストリングからの第２の入力ビットスライスとに基づいてtake関数が必要であるかを決定し、
    take関数が必要であるとき、処理するステップの中で結果のビットスライスと第１の入力ビットスライスまたは第２の入力ビットスライスとにtake関数を施すステップをさらに具備する請求項１記載の方法。
19. 複数のビットストリングを格納するメモリであってその各々は関係データベース管理システムにおける組織化されたデータを表わし各々が入力ビットスライスに分割されるものを具備する関係データベース管理システムと、
    ビットストリングの１つにブール演算を施して結果のビットストリングを形成する手段であって、該結果のビットストリングはユーザのクエリーの条件を満足する関係データベース管理システムにおけるレコードを表わし、結果のビットストリングは結果のビットスライスに分割されるものと、
    関係データベース管理システムにおける組織化されたデータを表わす第１のビットストリングからの第１の入力ビットスライスと関係データベース管理システムにおける組織化されたデータを表わす第２のビットストリングからの第２の入力ビットスライスとに基づきブール演算による作用を決定する手段と、
    第１の入力ビットスライスと第２の入力ビットスライスとの中からより長いビット長の入力ビットスライスを選択する手段と、
    より長いビット長を有するビットストリングのビット数まで、より長い入力ビットスライスと、より短かいビット長の入力ビットスライスを有するビットストリングの複数の入力ビットスライスとを、決定された作用に従って処理してユーザのクエリーの条件を満足する結果のビットストリングについて少なくとも１つの結果のビットスライスを形成する手段とを具備するシステム。
20. 関係データベース管理システムを動かすためのコンピュータを使用して各々が２進ビットスライスの連なりで表わされる１対の２進ビットストリングへブール演算を効率的に施すための方法であって、２進ビットストリングは関係データベース管理システムにおける組織化されたデータを表わしブール演算はユーザのクエリーに基づく関数を表わし、
    ブール演算に従って１対の２進ビットストリングを処理して、結果のビットスライスの連なりによって表わされ、ユーザのクエリーの条件を満足する関係データベース管理システムにおけるレコードを表わす結果の２進ビットストリングを形成するステップを具備し、該ステップは、
    ビットスライスの連なりの各々からの１対の２進ビットスライスの中からより長いビット長の２進ビットスライスを選択し、
    より長いビット長を有する２進ビットストリングのビット数まで、ブール演算を施してユーザのクエリーの条件を満足する結果のビットストリングについて少なくとも１つの結果のビットスライスを形成するステップを具備する方法。
21. 結果のビットスライスの連なりの各々はさらに特徴形式を具備し、前記施すステップは、
    １対の２進ビットスライスを比較して結果のビットスライスの連なりの各々によって表わされるビットスライスの形式を決定し、
    ビットスライスの形式を結果のビットスライスの連なりの各々の特徴形式に割り当てることをさらに具備する請求項20記載の方法。
22. ビットスライスの形式はランまたはインパルスのいずれかを表わし、前記割り当てるステップはランインジケータまたはインパルスインジケータを特徴形式にそれぞれ割り当てることをさらに具備する請求項21記載の方法。
23. 結果のビットスライスの連なりの各々はジェンダをさらに具備し、前記施すステップは
    １対の２進ビットスライスを調べて結果のビットスライスの連なりの各々によって表わされる２進値を決定し、
    結果のビットスライスの連なりの各々のジェンダに前記２進値を割り当てることをさらに具備する請求項20記載の方法。
24. １対の２進ビットスライスの各々はさらに反転インジケータを具備し、前記調べるステップは反転インジケータを調べることをさらに具備し、前記割り当てるステップは反転またはフリップが必要であるとき結果のビットスライスの連なりの各々のジェンダを反転させることをさらに具備する請求項23記載の方法。
25. 結果のビットスライスの連なりの各々は長さをさらに具備し、前記施すステップは、
    １対の２進ビットスライスを調べて結果のビットスライスの連なりの各々の長さを決定し、
    長さを結果のビットスライスの連なりの各々に割り当てることをさらに具備する請求項20記載の方法。

Images