(57)【要約】式の管理は、条件式を含む第１の照会を受取るステップを含む。式は次いで表の列におけるデータとして表わされる。基準の第１の集合を指定する第２の照会が受取られ、第２の照会が実行されることによって、列における式が基準の第１の集合を満たすかどうかに少なくとも基づいてデータが選択される。実施例において、第２の照会は基準の第２の集合をさらに指定し、第２の照会を実行するステップは、式列以外の列におけるデータが第２の基準を満たすかどうかに基づいてデータを選択するステップを含む。式を保存する列において作成され得る特殊な索引が定められることにより、式の大きな集合が効率的にフィルタリングされる。表にデータとして保存される式集合を評価する方法は、各式からの各述語を分類し、その述語分類に基づいて式集合をフィルタリングする。
2005525657.tif 000002
【特許請求の範囲】
【請求項１】
データベースにおける式を管理するための方法であって、前記方法は
第１の条件式を含む第１の照会を受取るステップと、
第１の条件式を表の列におけるデータとして表わすステップと、
１つまたはそれ以上の基準の第１の集合を指定する第２の照会を受取るステップと、
第２の照会を実行して、列における条件式が基準の第１の集合を満たすかどうかに少なくとも基づいてデータを選択するステップとを含む、方法。
【請求項２】
第２の照会は、１つまたはそれ以上の基準の第２の集合をさらに指定し、第２の照会を実行するステップは、前記列以外の１つまたはそれ以上の列におけるデータが基準の第２の集合を満たすかどうかに基づいてデータを選択するステップを含む、請求項１に記載の方法。
【請求項３】
第１の照会を受取るステップは、データベースアプリケーションの第１のユーザから第１の照会を受取るステップを含み、第１の条件式は、ユーザが関心を持つデータに対してデータが満たす必要のある１つまたはそれ以上の基準を指定する、請求項１に記載の方法。
【請求項４】
第２の照会を受取るステップは、データベースアプリケーションの第２のユーザから第２の照会を受取るステップを含み、第２の照会は、第１のユーザに対して利用可能にされるデータに対してデータが満たす必要のある１つまたはそれ以上の基準の第２の集合を指定することにより、第１のユーザと第２のユーザとの相互フィルタリングを可能にする、請求項３に記載の方法。
【請求項５】
第１の照会を受取るステップは、情報購読システムに対する利用者から第１の照会を受取るステップを含み、第１の条件式は、利用者が関心を持つデータに対してデータが満たす必要のある１つまたはそれ以上の基準を指定する、請求項１に記載の方法。
【請求項６】
第２の照会を受取るステップは、購読システムにおける発行者から第２の照会を受取るステップを含み、第２の照会は、利用者に発行されるデータに対してデータが満たす必要のある１つまたはそれ以上の基準の第２の集合を指定する、請求項５に記載の方法。
【請求項７】
第２の照会を受取るステップは、情報購読システムにおける発行者から第２の照会を受取るステップを含み、第２の照会は、購読システムに対する利用者に発行されるデータに対してデータが満たす必要のある１つまたはそれ以上の基準の第２の集合を指定する、請求項１に記載の方法。
【請求項８】
第１の条件式を列におけるデータとして表わすステップは、複数の第１の照会からの第１の条件式の集合を列におけるデータとして表わすステップを含み、前記方法はさらに、
基準の第１の集合のそれぞれの基準に関連する述語識別子に基づいて第１の条件式の集合からの述語をグループ化するステップと、
それぞれの述語識別子に関連する述語演算子および定数の集合を述語表に保存するステップと、
特定の述語識別子に関連付けられた述語演算子および定数の集合に基づいて連結ビットマップ索引を作成するステップとによって、
表の列に索引を作成するステップを含む、請求項１に記載の方法。
【請求項９】
１つまたはそれ以上のプロセッサによって実行されるときに、１つまたはそれ以上のプロセッサに請求項１−８に記載される方法のいずれか１つを行なわせる命令の１つまたは
それ以上の連続を運ぶ、コンピュータ読取可能媒体。
【請求項１０】
表の列におけるデータとして保存される式集合を評価するための方法であって、前記方法は
式集合の各式からの各述語を、
索引付けされる属性述語、ここではそれぞれの述語識別子に関連して述語表のそれぞれの列に保存される演算子および定数属性の集合に基づいてビットマップ索引が作成される、
保存される属性述語、ここでは演算子および定数属性の集合はそれぞれの述語識別子に関連して述語表のそれぞれの列に保存され、演算子および定数属性の集合に対して索引は作成されない、
疎述語、ここでは疎述語に関連する述語識別子は式集合において共通でなく、疎述語は述語表にデータとして保存される、のうちのいずれか１つとして分類するステップと、
式集合からの述語の分類に基づいて式集合をフィルタリングするステップとを含む、方法。
【請求項１１】
式集合をフィルタリングするステップは
第１に、索引付けされる属性述語をフィルタリングすることによって、その索引付けされる属性述語のすべてが所与のデータ項目に対して真である１つまたはそれ以上の式を含む式の第１の集合を得るステップと、
第２に、式の第１の集合の保存される属性述語をフィルタリングすることによって、その保存される属性のすべてが所与のデータ項目に対して真である１つまたはそれ以上の式を含む式の第２の集合を得るステップと、
第３に、式の第２の集合の疎述語があればそれをフィルタリングすることによって、その述語のすべてが所与のデータ項目に対して真である１つまたはそれ以上の式を含む式の第３の集合を得るステップとを含む、請求項１０に記載の方法。
【請求項１２】
式の第３の集合からの式によって表わされる基準を満たすデータに対する関心を表わした、情報購読システムに対する利用者に、所与のデータ項目を発行するステップをさらに含む、請求項１１に記載の方法。
【請求項１３】
１つまたはそれ以上のプロセッサによって実行されるときに、１つまたはそれ以上のプロセッサに請求項１０−１２に記載される方法のいずれか１つを行なわせる命令の１つまたはそれ以上の連続を運ぶ、コンピュータ読取可能媒体。
【請求項１４】
複数の行を有する表において構築される索引を保存するコンピュータ読取可能媒体であって、前記索引は
連結ビットベクトルを含み、各ビットベクトルは表のそれぞれの列に各々保存される演算子および定数の１つに関連付けられ、演算子および定数は、購読システムに対する利用者が関心を持つデータに対してデータが満たす必要のある１つまたはそれ以上の基準を指定する条件式からの１つまたはそれ以上の述語のうちの１つの述語に関連付けられる、コンピュータ読取可能媒体。
【請求項１５】
データベースにおける式を管理するための装置であって、
第１の条件式を含む第１の照会を受取る手段と、
第１の条件式を表の列におけるデータとして表わす手段と、
１つまたはそれ以上の基準の第１の集合を指定する第２の照会を受取る手段と、
第２の照会を実行して、列における条件式が基準の第１の集合を満たすかどうかに少なくとも基づいてデータを選択する手段とを含む、装置。
【請求項１６】
表の列におけるデータとして保存される式集合を評価するための装置であって、
式集合の各式からの各述語を、
索引付けされる属性述語、ここではそれぞれの述語識別子に関連して述語表のそれぞれの列に保存される演算子および定数属性の集合に基づいてビットマップ索引が作成される、
保存される属性述語、ここでは演算子および定数属性の集合はそれぞれの述語識別子に関連して述語表のそれぞれの列に保存され、演算子および定数属性の集合に対して索引は作成されない、
疎述語、ここでは疎述語に関連する述語識別子は式集合において共通でなく、疎述語は述語表にデータとして保存される、のうちのいずれか１つとして分類する手段と、
式集合からの述語の分類に基づいて式集合をフィルタリングする手段とを含む、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
この出願は、２００２年５月１０日に提出された「データベースシステムにおける式の管理」と題する米国仮特許出願番号第６０／３７８，０１８号に関連しており、その優先権の利益を主張するものであり、それはここに完全に示されたのと同様に、すべての目的に対して全体に亘って引用により援用される。
【０００２】
発明の分野
この発明は一般的にデータベース管理システムに関し、より特定的には、データベースシステムにおける条件式を管理する技術に関する。
【背景技術】
【０００３】
発明の背景
事象および内容に基づく購読システムの状況においては、それが満たされた場合に動作を引起す事象が定められる。たとえば、利用者は、内容の状態を定める事象を含む規則を定め、それが満たされた場合にその内容を利用者に送信させることができる。データベース管理システムを事象に基づく購読システムに対する基礎エンジンとして用いることによって、利用者は事象の内容の条件式を表わす照会をシステムに登録できる。こうした購読または同様に機能するシステムにおいては、所望の内容データの発行を管理するために、照会すなわち内容に対する式集合の非常に大きな集合が登録され得る。所与のデータ項目が利用可能になるとき、これらの条件式がフィルタリングされて、この所与のデータ項目に一致する式が見出される。
【０００４】
式集合をフィルタリングするタスクに対する簡単だが非効率的なアプローチは、データ項目の各々に対して所与の集合におけるすべての式をテストすることである。しかし、このアプローチは式の大きな集合に対しても、高速の事象に対してもスケーラブルでない。したがって、殆どの商業システムは式集合を前処理して、式集合における整合する述語をグループ化して複数の式に亘る処理コストを分担するインメモリ整合ネットワーク（すなわち特殊化したデータ構造）を作成する。
【０００５】
整合ネットワークは決定樹であり、その各ノードが所与の式集合における述語グループを表わす。データが親ノードを表わす述語に対して真と評価するときにのみ、そのデータは親ノードからその子へと流れる。決定樹の根から葉ノードへの経路は、式におけるすべての論理積を表わす。木の中の葉ノードは式識別子によってラベル付けされ、データ項目が葉ノードにおける述語テストを通ると、対応する式はそのデータ項目に対して真とみなされる。既存のシステムに対して、整合ネットワークの多くの変形（ＲＥＴＥ、ＴＲＥＡＴおよびゲータ（Gator）ネットワークなど）が用いられている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
既存のシステムにおいて、式および関連情報のフィルタリングを必要とするあらゆる演算は、有意カスタム符合化を必要とし、性能特性を減少させる。さらに、対応する整合ネットワークが主メモリに適合しなければならないため、式の数の大きさには制限があり、式の変更はコストがかかり、またユーザは構造に対するフィルタリング戦略ならびに式および関連データの使用を調整できない。
【０００７】
前述に基づき、購読システムに関連する式などの式を管理する改善された機構を提供す
ることが明らかに望ましい。また、他の関連情報に対するフィルタに関連して式をフィルタリング可能にする機構がより特定的に要求されている。
【０００８】
この発明は、制限のためではなく例として、添付の図面に例示されており、ここで類似の参照番号は類似の構成要素を示す。
【課題を解決するための手段】
【０００９】
詳細な説明
データベースシステムにおいて式を管理するための方法およびシステムを説明する。また、より特定的には、事象および内容に基づく情報購読システムに関連する条件式を管理するための方法およびシステムを説明する。
【００１０】
以下の説明においては、説明の目的のために、この発明の完全な理解を与えるために多数の特定的な詳細が示される。しかし、この発明はこれらの特定の詳細なしに実行されてもよいことが明らかである。他の場合においては、この発明を不必要に不明確にすることを避けるために、周知の構造および装置はブロック図の形で示す。
【００１１】
概要
しばしば標準データベース照会の形をとる条件式は、表の列におけるデータとして表わされる。これらの式はたとえば、情報購読システムにおけるデータをフィルタリングするためのデータフィルタを表わしてもよい。次いで、基準を指定する別の標準データベース照会が列に対して実行されて、その列中の式が指定される基準を満たすかどうかを判断できる。その基準はたとえば、購読システムに入来するデータを表わしてもよい。
【００１２】
よって、ここに記載される式処理機構は、式を他の関連するユーザ指定のデータに沿って照会可能なデータとして扱うことにより、データベース技術と一体化される。たとえば、発行者がその利用者に関する他のフィルタリング基準を照会に含ませてもよい。
【００１３】
実施例においては、第１の条件式を含む第１の照会が受取られる。たとえば、第１の照会は、挿入（ＩＮＳＥＲＴ）またはデータベースロード演算を介して受取られてもよい。次いで第１の式は表の列におけるデータとして表わされる。基準の第１の集合を指定する第２の照会が受取られ、第２の照会が実行されることにより、列中の式が基準の第１の集合を満たすかどうかに少なくとも基づいてデータが選択される。たとえば、第２の照会はデータベースアプリケーションのユーザから受取られてもよい。
【００１４】
実施例において、第２の照会はさらに基準の第２の集合を指定し、ここで第２の照会を実行するステップは、その列以外の列におけるデータが第２の基準を満たすかどうかに基づいてデータを選択するステップを含む。
【００１５】
別の実施例は、利用者から購読サービスまたはシステムに第１の照会を受取るステップを含み、ここで第１の式は利用者が関心を持つデータに対してデータが満たす必要のある基準を指定し、さらに、購読システムに関連する発行者からの第２の照会を受取るステップを含み、ここで第２の照会は利用者に発行されるデータに対して、利用者に関して、データが満たす必要のある基準を指定する。よって、利用者および発行者の両方によってデータに相互フィルタリングを行なうことができる。
【００１６】
局面の１つに従うと、式をデータとして保存する列において特殊な索引を定めることにより、式の大きな集合を効率的にフィルタリングする。
【００１７】
実施例において、式の述語は、それらの左辺の共通性、すなわち第１の式の基準に関連
する共通の識別子に基づいてグループ化される。これらのグループはデータベースに永続的に保存される。さらに、述語に関連する演算子および定数がそれぞれの述語グループに関連して述語表に保存され、その演算子および定数に基づいて、連結ビットマップ索引などの索引が作成される。
【発明を実施するための最良の形態】
【００１８】
データベースシステムにおける式の管理
事象および内容に基づく購読システムにおいて、典型的には、事象構造または状況に対する式または規則（たとえば事象−条件−動作（ＥＣＡ）ルール）の集合が定められ、事象の構造は式において用い得る基本属性を判断する。この状況において用いられる「事象」という用語は、それに対して式または「条件」が評価されるデータ項目を示す。たとえば、株取引の状況における事象は、公的に取引される株が特定の価格に達することであってもよく、それがデータ項目として表わされる。すなわち、このような事象に関連する式の基本属性は、たとえばＳＹＭＢＯＬ（記号）、ＰＲＩＣＥ（価格）およびＣＨＡＮＧＥ（変化）を含み得る。ＥＣＡルールは、事象が起こることによってトリガされるまで休止している。
【００１９】
事象構造または状況に対して定められる一組の式は式集合と呼ばれる。たとえば、利用者Ａは、ＳＹＭＢＯＬ＝ＯＲＣＬ，ＰＲＩＣＥ＞３０，ａｎｄ  ＣＨＡＮＧＥ＞５で表わされる事象に関心を持っているかもしれない。利用者Ｂは、ＳＹＭＢＯＬ＝ＣＳＣＯ，ａｎｄ  ＰＲＩＣＥ＞２５で表わされる事象に関心を持っているかもしれない。また利用者Ｃは、ＳＹＭＢＯＬ＝ＩＮＴＣ，ａｎｄ  ＣＨＡＮＧＥ／ＰＲＩＣＥ＞０．１で表わされる事象に関心を持っているかもしれない。
【００２０】
規則に基づく典型的なシステム、たとえば内容に基づく購読システムにおいては、条件式の大きな集合の効率的なフィルタリングがシステムのスケーラビリティにとって決定的である。表中の行の大きな集合に対していくつかの照会が実行される典型的なデータベース設計とは異なり、規則に基づくシステムでは、単一のデータ項目に対して（照会のＷＨＥＲＥ（どこ）文節に類似する）多数の式を演算する。
【００２１】
アプリケーションに対して定められる式は比較的静的であり、これらの式に対して新たなデータを高速で処理すべきである。したがって局面の１つに従うと、式の前処理が行なわれて、特殊化されたデータ構造および索引などのデータアクセス機構を構築することにより、新たなデータ項目による高速フィルタリングが可能となる。
【００２２】
式の集合の前処理
システムにおいて多数の条件式が与えられるとき、それらの式は基本述語レベルにおいて類似性を有する傾向がある。すなわち、論理積によって繋がれた１つまたはそれ以上の基本述語を各々有する２つの式は、共通の述語を有し得る。よって、式評価コストを複数の式で分担することによって、前述の類似性を活用する。実施例においては、関数のライブラリ、すなわち式型ライブラリ（Expression Type Library）が式の集合の前処理を支持する。
【００２３】
式型ライブラリは、式に対する整合ネットワークを構築するために必要とされる基本的な相関性を提供する。このライブラリは、式ストリングを論理積および論理和で繋がれた基本述語を含む式木（expression tree）に変換できるＪａｖａ（登録商標）クラスの集合として提供される。このライブラリは、式集合における式を前処理するために、またこれらの式に対する増分変更の際に、あらゆる索引付け方式によって使用可能である。
【００２４】
このライブラリは、式を解析してそれらを次のように処理する。
【００２５】
（１）  たとえば、式中の述語を再配置することによってそれを論理和正規形（ＤＮＦ）、すなわちＡＮＤ従属節のＯＲリストに書替えることによって、式を正規化する。たとえば、
ＳＹＭＢＯＬ＝“ＧＥ”ａｎｄ（ＰＲＩＣＥ＜２５  ｏｒ  ＰＲＩＣＥ＞３５）
の形の式は、ＤＮＦ変換後には次のように書替えられる。
【００２６】
（ＳＹＭＢＯＬ＝“ＧＥ”ａｎｄ  ＰＲＩＣＥ＜２５）ｏｒ（ＳＹＭＢＯＬ＝“ＧＥ”ａｎｄ  ＰＲＩＣＥ＞３５）
（２）  式中の各述語を書替えて、右辺に純定数があるようにすることによって、述語を正規化する。たとえば、
ＰＲＩＣＥ＞２７＋ＣＨＡＮＧＥ
の形の述語は、次のように書替えられる。
【００２７】
ＰＲＩＣＥ−ＣＨＡＮＧＥ＞２７
（３）  述語を次のように解くことによってデコードする。
【００２８】
左辺（ＬＨＳ）：１つまたはそれ以上の属性の式または関数（例、述語ＰＲＩＣＥ−ＣＨＡＮＧＥ＞２７のＰＲＩＣＥ−ＣＨＡＮＧＥ）
右辺（ＲＨＳ）：定数（例、述語ＰＲＩＣＥ−ＣＨＡＮＧＥ＞２７の“２７”）
関係演算子：ＬＨＳとＲＨＳとを繋ぐ関係演算子（例、述語ＰＲＩＣＥ−ＣＨＡＮＧＥ＞２７の“＞”）
述語の左辺、たとえば属性ＳＹＭＢＯＬは、複合属性とも呼ばれる。それは１つまたはそれ以上の基本属性またはＣＨＡＮＧＥ／ＰＲＩＣＥなどのユーザが定める関数を含む部分式であってもよい。
【００２９】
述語の演算子は予め定められた整数値に対応付けられるが、実施例はこのような対応付けに制限されない。対応付けされた演算子および関連の述語定数（ＲＨＳ）は述語表に保存され、述語表については以下により詳細に説明する。実施において、ＩＮリスト、副照会などの構成を含む述語は、他の述語とグループ化されない。
【００３０】
属性集合
この発明の或る局面に従うと、事象構造または状況を捕捉する属性集合が作成される。属性集合は式集合において用いられる基本属性のリストと、それらのデータ型とを有する。最も簡単な形のとき、属性集合はデータベース中の抽象型定義に似ている。たとえば、式集合において用いられる基本属性の集合がその属性集合を構成する。
【００３１】
属性集合を作成するための制限的でない技術の１つは、以下のコマンドで表わされる。
【００３２】
【数１】
2005525657.tif 000003
【００３３】
これによって、基本属性“ＳＹＭＢＯＬ”、“ＰＲＩＣＥ”および“ＣＨＡＮＧＥ”を有する属性集合“ＴＩＣＫ”が作成される。
【００３４】
重要なことに、式集合は表の列に保存される。たとえば、式はデータベース表中のＶＡＲＣＨＡＲ２またはＣＬＯＢ列に保存され得る。このような列は、たとえばいくつかの式集合メタデータを列に関連付けることによって、ＥＸＰＲＥＳＳＩＯＮ（式）データ型の列として認識できる。さらに、式集合を保存する列は、式集合に対して作成された属性集合に関連付けられる。属性集合を式集合に関連付けるための制限的でない技術の１つは、以下のコマンドで表わされる。
【００３５】
【数２】
2005525657.tif 000004
【００３６】
これによって、属性集合“ＴＩＣＫ”は、表“ＴＲＡＤＥＲ”（取引者）の“ＩＮＴＥＲＥＳＴ”（関心）列に保存される式集合に関連付けられる。
【００３７】
属性集合に関連付けられたＶＡＲＣＨＡＲ２またはＣＬＯＢ列は、ＥＸＰＲＥＳＳＩＯＮ列を構成する。ＥＸＰＲＥＳＳＩＯＮ列に保存される値は式として扱われ、それらは最初に、ＸＰＡＴＨ式を含み得るＳＱＬ−ＷＨＥＲＥ文節形式に準拠することが期待される。これらの式は、あらゆるシステム変数および、たとえば次のものなどのユーザ環境において有効なユーザが定める関数とともに、属性集合において定められるすべての属性を用いることができる。
【００３８】
【数３】
2005525657.tif 000005
【００３９】
式フィルタ
実施例に従うと、式フィルタとはＰＬ／ＳＱＬパッケージおよびＡＰＩの集合であって、ユーザ表中の式を管理し、また所与のデータ項目に対する式をフィルタリングする。すなわち、標準ＳＱＬまたはその他の照会言語照会を用いて、式において表わされる基準を所与のデータ項目と突き合わせる。発行システムにおいて、式は、利用者が関心を持つデータに対してデータが満たす必要のある基準を指定する。式フィルタは２つの構成要素を含む。すなわち、ＥＶＡＬＵＡＴＥ（評価）演算子（すぐ下に説明する）と、式フィルタ索引型（Indextype）（「式集合に対する索引の作成」という見出しの下に説明する）とである。
【００４０】
ＥＶＡＬＵＡＴＥ演算子
ＥＸＰＲＥＳＳＩＯＮ列に保存される式集合を処理する新たな演算子が導入される。この演算子は、標準ＳＱＬまたはＤＭＬステートメントのＷＨＥＲＥ文節において、データ項目に対する式をフィルタリングするために用いることができる。新たな演算子ＥＶＡＬＵＡＴＥを用いた式集合の述語は、表中のあらゆる他の述語と組合せることができる。ＥＶＡＬＵＡＴＥ演算子は、たとえばＩＮＴＥＲＥＳＴなどの、式を保存する列の名前および所与のデータ項目を引数として受入れる。ＥＶＡＬＵＡＴＥ演算子は内部で式集合メタデータを用いて、提出されるデータ項目に対して式を評価する。
【００４１】
ＥＶＡＬＵＡＴＥ演算子を用いる照会の一例は次のとおりである。
【００４２】
【数４】
2005525657.tif 000006
【００４３】
この照会が所与のデータ項目値に対して真と評価すれば、その式は真とみなされる。
【００４４】
式が保存される表における照会を広げて、マルチテーブル結合、およびＧＲＯＵＰ  ＢＹ（のグループ）文節、ＯＲＤＥＲ  ＢＹ（のオーダ）文節、ＨＡＶＩＮＧ（有する）文節などを用いるあらゆるその他のデータベース照会演算を含ませることもできる。また、式が保存される表とデータ項目を保存する表とを繋ぐことによって、データ項目のバッチに対して式の集合をフィルタリングすることも予期される。このような照会の一例は次のとおりである。
【００４５】
【数５】
2005525657.tif 000007
【００４６】
ここでＴＩＣＫは式集合に対して定められた属性集合の名前であり、ＴＲＡＤＥＲＳは式集合を保存する表（例として図１を参照）であり、ＤＡＴＡＩＴＥＭＳは処理される、すなわち式集合と比較されるデータ項目を保存する表である。
【００４７】
式集合に対する索引の作成
データ項目に対してそれぞれの式をテストすることは線形の時間解である。式の大きな集合が定められるとき、このアプローチは大量のデータ項目に対してスケーラブルでない。したがって、実施例においては、新たな索引付け機構を用いて式の大きな集合を効率的に評価し、それによって所与のデータ項目またはデータストリングに対する式集合の評価を速める。この索引はＥＸＰＲＥＳＳＩＯＮ列に定めることができ、よって照会オプティマイザは索引使用コストに基づいて式集合の評価に対する索引の使用を判断できる。実施においては、式集合に対する索引を維持するために永続的なデータベースオブジェクトが作成され、ここで索引作成時に式集合を前処理することがこれらのデータベースオブジェクトを占める。加えて、これらのオブジェクトに保存される情報は、式を保存する表におけるＤＭＬ演算を用いる式集合に対するあらゆる変更を反映するように維持される。
【００４８】
式フィルタ索引型
実施例において、索引付け方式は、拡張可能な索引付けフレームワークを用いる新たな索引型すなわち式フィルタとして実施される。実施において、索引付け方式は、オラクル拡張可能索引付けフレームワーク（Oracle Extensible Indexing framework）を用いる新たな索引型すなわち式フィルタとして実施される。式フィルタ索引型は、ＶＡＲＣＨＡＲ２、ＣＬＯＢまたはＢＦＩＬＥ型のデータベース列に保存される式のあらゆる集合における索引を作成するために用い得る。しかし、データ型として保存される式に対して用いられ得る前述以外の別の索引型の使用も予期され、したがってそれもこの発明の実施例の範囲内である。
【００４９】
式フィルタ索引型実施は、式の集合を解析し、式中の述語を、整合左辺を有する互いに素の集合にグループ化する。式集合中の述語をグループ化するために用いられるデータ構造は本質的にリレーショナルである。永続的なデータベースオブジェクトが式フィルタ索引データ構造に用いられる実施において、このようなデータベースオブジェクトの一例は次のとおりである。
【００５０】
述語表：式中に示される述語を保存する関係表
ビットマップ索引：述語表における１つまたはそれ以上のビットマップ索引
アクセス関数：述語表を照会してデータ項目に対して式をフィルタリングする関数
これらのオブジェクトは集合的に、同等および範囲述語の両方に基づく式の効率的なフィルタリングを提供する。さらに、索引構造オブジェクトはデータベースに永続的に保存
されるため、典型的に主メモリを広範囲に亘って用いる、先行アプローチにおける式集合の大きさに関連するメモリの制約が、この実施例には当てはまらない。対照的に、この実施例を用いる演算は、必要なデータベースブロックを必要に応じてデータベースバッファキャッシュに保存できる。
【００５１】
前述のとおり、式の所与の集合の式は、固定されたデータ型を有する基本属性の集合を示す。さらに、これらの属性に対する有効値の集合がデータ項目を構成し、それがこれらの式に対して評価される。したがって、式集合を式フィルタ索引型によって索引付けするためには、式集合に用いられているすべての基本属性を、式を保存するデータベース列に関連付ける必要がある。これらの基本属性は、いくつかの任意の複合属性とともに、式集合に対する属性集合を構成し、これは１つまたはそれ以上のデータディクショナリ表に保存される。前述のような式フィルタ索引を作成するための制限的でない技術の１つは以下のコマンドによって表わされ、これは式が保存される表ＴＲＡＤＥＲのＩＮＴＥＲＥＳＴ列における索引ＴＲＡＤＥＲＦＩＬＴＥＲ（取引者フィルタ）を作成する。加えてこの索引は、こうした属性にビットマップ索引を定めることによって、ＳＹＭＢＯＬおよびＰＲＩＣＥ属性を含む述語を効率的にフィルタリングするよう構成される。
【００５２】
【数６】
2005525657.tif 000008
【００５３】
ＣＲＥＡＴＥ  ＩＮＤＥＸ（索引作成）ステートメントに渡されるパラメータは、式フィルタ索引に用いられるオブジェクト（述語表、ビットマップ索引およびアクセス関数）の構造を判断するため、フィルタの性能に影響する。ＣＲＥＡＴＥ  ＩＮＤＥＸステートメントにおけるＰＡＲＡＭＥＴＥＲＳ（パラメータ）文節は任意であり、この文節がないときには、属性集合のすべての（本来の型の）基本属性が保存され索引付けされる。
【００５４】
実施例において、述語表の演算子およびよくあるＬＨＳに対するＲＨＳ定数列に対して連結ビットマップ索引が作成される。たとえば、ＬＨＳ属性ＳＹＭＢＯＬは株照会に関する式によく用いられるため、演算子およびＳＹＭＢＯＬ属性を含む述語に関する定数列に対してビットマップ索引が作成されて、連結ビットマップ索引に組合されてもよい。これらのビットマップ索引は、式集合評価の際の多次元索引として機能する。
【００５５】
一般的に、新たな索引型（すなわち式フィルタ索引型）として実施されて、式をデータとして保存する列に適用される、ここに記載される索引付け方式の利用は、新たなＥＶＡＬＵＡＴＥ演算子が式フィルタ索引を使用できるようにすることによって、式の大きな集合を効率的に評価する方法を提供する。
【００５６】
述語評価
実施例においては、述語の分析において、式集合中の述語は３つの集合に分類される。
【００５７】
（１）  索引付けされる属性を有する述語：たとえばＳＹＭＢＯＬ識別子を含む述語などの一般的な述語など、この集合に属する述語グループに対してはビットマップ索引が作成される。
【００５８】
（２）  保存される属性を有する述語：この集合に属する述語グループは解析されて、＜演算子，ＲＨＳ定数＞列に対して定められる索引なしで述語表に保存される。
【００５９】
（３）  疎述語：この集合に属する述語はその元の形で保存される。或る式に対して１つよりも多くの疎述語が存在するときには、それらは１つの論理積に組合される。なお、他のものとグループ化できないすべての述語に対して述語表に列の新たな集合を加えることは、必ずしも効率的ではない。したがって、実施例に従うと、疎述語に対する条件式を保持するために、述語表に別個のＶＡＲＣＨＡＲ２列、すなわちＰＡＲＴＩＡＬ＿ＣＯＮＤＩＴＩＯＮが定められる。述語表中の他の列とは異なり、この列は索引付けされず、１つまたはそれ以上の述語定義を論理積の形で保持できる。
【００６０】
述語は、その左辺を計算するコストと、式集合においてその左辺が起こる頻度とに基づいて、上記の集合の１つに分けられる。述語に対する評価コストは、それが属する集合に依存する。
【００６１】
前述のような分類に関する述語の評価に含まれるステップは以下のとおりである。
【００６２】
（１）  索引付けされる属性：複合属性（すなわち述語グループのＬＨＳ）の１回の計算、および計算値を用いたビットマップ索引の１つまたはそれ以上の範囲走査
（２）  保存される属性：複合属性の１回の計算、および計算値とこのグループ中のすべての述語のＲＨＳとの比較
（３）  疎述語：疎述語を表わす部分式の解析、およびデータ値の代入による部分式の評価
式集合評価の際に、実施例に従うと、式は以下のように３段階でフィルタリングされる。
【００６３】
段階１：索引付けされる属性集合に属する述語は、そこに定められるビットマップ索引に対するいくつかの範囲走査を行なうことによってテストされる。これらの走査の結果を組合せる（ビットマップＡＮＤ演算）ことによって、これらの述語が所与のデータ項目に対してすべて真である式の集合を得る。
【００６４】
この段階の合計コストは
Ｉ＊Ｃ１１＋Ｎ１＊Ｃ１２＊ｌｏｇ（Ｅ１）＋Ｃ１３＊Ｅ２
と定められ、ここで
Ｉはフィルタリングに用いられるビットマップ索引の数であり、
Ｅ１はフィルタリングされる式の数であり、
Ｃ１１は索引当たりの平均ビットマップ索引処理コストであり、
Ｃ１２＊ｌｏｇ（Ｅ１）は１つの索引ルックアップの平均コストであり、
Ｃ１３は行識別子を用いて述語表から１つの行をフェッチするコストであり、
Ｅ２は段階１において真と評価される式の数であり、
Ｎ１はビットマップ索引当たりのルックアップの平均数である。
【００６５】
段階１の結果は、索引付けされる属性集合に属するすべての述語に対して真と評価する式の集合である。
【００６６】
段階２：段階１において真と評価されたすべての式に対して、保存される属性集合に属する述語がテストされる。
【００６７】
この段階の合計コストは
Ｓ＊Ｃ２＊Ｅ２
と定められ、ここで
Ｓは式当たりの保存される属性の平均数であり、
Ｃ２は一度の比較の平均コストであり、
Ｅ２は段階１において真と評価される式の合計数である。典型的には、作業集合は段階１においてかなり狭くされ、Ｅ２＜＜Ｅ１である。
【００６８】
段階２の結果は、索引付けまたは保存される属性集合に属する述語に対して真と評価する式の集合である。
【００６９】
段階３：段階２の後に真であるすべての式に対し、これらの式に対する疎述語（あれば）が評価される。
【００７０】
この段階の合計コストは、
Ｐ＊Ｃ３＊Ｅ３
と定められ、ここで
Ｐは式に対する疎述語の確率であり、
Ｃ３は疎述語の解析および評価の平均コストであり、
Ｅ３はフィルタリングの段階２の後に真である式の合計数である。
【００７１】
段階３の結果は、所与のデータ項目に対して真と評価する式の集合である。なお、前述の索引に基づく評価以外の代替的なアクセスプランが用いられてもよい。
【００７２】
図１に例示されるような、条件式として株取引者および取引における彼らの関心に関する情報を保存するデータベース表ＴＲＡＤＥＲＳを考える。年齢が３０歳未満で、ニューヨークに住み、データ項目（ＳＹＭＢＯＬ＝“ＯＲＣＬ”，ＰＲＩＣＥ＝３１，ＣＨＡＮＧＥ＝５．２）に関心を持つすべての取引者（ＴＲＡＤＥＲＳ）を見出すために、ＴＲＡＤＥＲＳ表に対して発行できる照会の一例を以下に示す。
【００７３】
【数７】
2005525657.tif 000009
【００７４】
実際には、この照会は述語表および述語表上のビットマップ索引を用いて式をフィルタリングしてもよい。式フィルタ索引は、所与のデータ項目によって真と評価するすべての式に対する行ｉｄ（rowids）を戻す。ＳＥＬＥＣＴ（選択）ステートメント中の残りの述語が対応する行に対して評価されて、照会に応答する。ＩＮＴＥＲＥＳＴ列上の式フィルタ索引に加えて、もしＴＲＡＤＥＲＳ表がＣＩＴＹ（都市）およびＡＧＥ（年齢）列において定められる本来のまたは拡張可能な索引を有するときには、最適化プログラムがアクセスコストに基づいてこれらの索引の１つまたはそれ以上を選択して、上記の照会に応答してもよい。
【００７５】
ＴＲＡＤＥＲＳ表に新たな行が挿入されるか、または既存の式のいくつかが更新されるときには、式フィルタ索引はこれらの変更を反映するように自動的に維持される。
【００７６】
前述の照会例が例示するとおり、ここに記載される技術は式フィルタリング演算をデー
タベース演算に一体化する。情報購読−発行システムの状況においては、式およびフィルタリング機構のデータベースシステムへの一体化の結果として、利用者と発行者の両方からの相互フィルタリングを行なうことができ、また標準ＳＱＬステートメントを用いることによって効率的に行なうことができる。したがって、表を結合して照会に述語を加えて式をさらにフィルタリングすることにより、マルチドメイン照会が可能である。さらに、式を保存する表をデータ項目を保存する表に結合することにより、データの所与の集合に対する式集合の一括評価が可能である。
【００７７】
先行アプローチは、システムユーザまたはクライアントの名前、電話番号および居住地などの特徴を、購読式に表わされるデータにおける彼らのそれぞれの関心から分離する。関心と個人的特徴とのこの統合によって、多くのアプリケーションが利益を得ることができる。たとえば、照会を実行して「株Ｘが価格Ｙを超えることに関心を持つ、ニューヨークのすべての取引者」または「車両Ｚに関心を持つ、私の店から１０マイル以内に住むすべての顧客」を戻すことができる。重要なことに、この実施例は、式の状況に基づく式の最適なフィルタリングを容易にする。たとえば、株取引の状況においては、この状況は、大多数のユーザは株記号によって表わされる特定の株についての関心を持つので、ＳＹＭＢＯＬ属性における述語をグループ化することによって、また、ＳＹＭＢＯＬ属性を含む述語に関連する演算子および定数を索引付けすることによって、データの効率的なフィルタリングをもたらす。
【００７８】
データベース中の式を管理するためのプロセス
図２は、データベース中の式を管理するためのプロセスを例示するフローチャートである。図１の表を付加的に参照して図２を説明する。
【００７９】
ブロック２０２において、第１の条件式を含む第１の照会が受取られる。たとえば、第１の照会はＩＮＳＥＲＴまたはデータベースロード演算を介して受取られてもよい。実施例において、条件式はＳＱＬ  ＷＨＥＲＥ文節の形であることが期待される。さらに、あらゆるＳＱＬ  ＷＨＥＲＥ文節が式として扱われてもよい。代替的な実施例においては、ＳＱＬ照会以外の形を有し、またあらゆる型の照会以外の形を有する条件式が予期される。たとえば、ユーザはデータにおける関心を簡単なテキストの入力を介して指定してもよく、それは表の列に保存するためのＶＡＲＣＨＡＲ２またはＣＬＯＢなどの適切なデータ形式に直接変換される。
【００８０】
実施例において、第１の照会は、利用者から、情報購読システムまたはその他の事象もしくは内容に基づく情報発行システムに受取られ、ここで式は、特定の利用者が関心を持つデータに対してデータが満たす必要のある基準を指定する。よって、第１の照会は、本質的にデータを処理して適切な利用者に対するディスパッチまたは発行を行なうシステムデータに関する第１のレベルのフィルタリングのための機構として働き得る。
【００８１】
ブロック２０４において、第１の照会の第１の条件式は、前述において説明し図１の列１０６として示すように、表の列におけるデータとして表わされる。たとえば、式を構成する１つまたはそれ以上の述語は、それに対してＳＱＬまたはその他の照会言語が演算でき、かつデータベース管理システムが管理できるデータ形式に符号化される。なお、図１の表のＩＮＴＥＲＥＳＴ列１０６における式の表現は説明の目的のためのものであり、ここに示されるような形をとるものではない。むしろ、ＩＮＴＥＲＥＳＴ列または式表現が保存されるあらゆる類似の列に保存される式は、実際には従来どおり適切なデータ形式に符号化される。
【００８２】
任意のブロック２０６においては、ブロック２０４において条件式をデータとして保存した表の列に対して索引が作成される。この実施例において、索引は上述のとおりに作成
される。
【００８３】
索引付けするステップは、基準の第１の集合のそれぞれの基準に関連付けられた述語識別子に基づいて、式の集合からの述語をグループ化するステップを含む。この例を続けると、述語グループ識別子は、ＳＹＭＢＯＬ、ＰＲＩＣＥおよびＣＨＡＮＧＥを含んでもよい。述語演算子および定数の集合は、それぞれの述語識別子に関連して述語表中に保存される。たとえば、ＳＹＭＢＯＬに対する述語グループ化は、演算子が「同等」であり定数が“ＯＲＣＬ”など、演算子と定数との組合せの集合を表わす述語表中のエントリを有してもよく、ＰＲＩＣＥに対する述語グループ化は、「同等かそれ以上」および“３１”などの、演算子と定数との組合せを含む述語表中のエントリを有してもよい。これらの演算子および定数の集合は、その目的に対して適切なあらゆる従来の態様で符号化されてもよい。次に、特定の述語識別子に関連する述語演算子および定数の集合に基づいて、連結ビットマップ索引または索引の別の形が作成される。たとえば、データフィルタリングプロセスの一部として述語すなわち式を高速かつ効率的に評価するために、述語識別子ＳＹＭＢＯＬに対して、述語表のそれぞれの列において表わされる演算子および定数の組合せの集合が索引付けされる。
【００８４】
ブロック２０８において、１つまたはそれ以上の基準の第１の集合を指定する第２の照会が受取られる。次の照会は第２の照会の一例である。
【００８５】
【数８】
2005525657.tif 000010
【００８６】
この照会は、ＳＹＭＢＯＬが“ＯＲＣＬ”に等しく、ＰＲＩＣＥが３１より大きいかそれに等しく、ＰＲＩＣＥにおけるＣＨＡＮＧＥが５．２より大きいかそれに等しいという基準を指定する。第２の照会はたとえば、データベースアプリケーションのユーザから受取られてもよい。
【００８７】
実施例において、第２の照会は、情報購読システムまたはその他の事象もしくは内容に基づく情報発行システムの発行者から受取られ、ここで式は、特定の利用者に対して発行されるデータに対してデータが満たす必要のある基準の集合を指定する。よって第２の照会は、本質的にデータを処理して適切な利用者に対するディスパッチまたは発行を行なうシステムデータに関する第２のレベルのフィルタリングのための機構として働き得る。
【００８８】
ブロック２１０において、第２の照会が実行されて、列１０６における条件式が基準の第１の集合を満たすかどうかに少なくとも基づいてデータが選択される。たとえば、第２の照会の実行によってとりわけ、特定のデータ項目がデータ列１０６中の保存される式において表わされる条件または条件の集合を満たすかどうかが判断される。言い換えると、購読システムの状況において、照会のＷＨＥＲＥ文節の第１の部分（ＡＮＤ論理積の前）において指定される基準を満たすデータに対して、利用者の式において指定される条件または述語を通じて、関心を示す利用者がいるかどうかが判断される。
【００８９】
実施例において、第２の照会は基準の第２の集合をさらに指定し、ここでブロック２１０における第２の照会の実行は、列１０２、１０４など、式列以外の１つまたはそれ以上
の列におけるデータが第２の基準を満たすかどうかに基づいてデータを選択するステップを含む。たとえば、ＷＨＥＲＥ文節の第２の部分（ＡＮＤ論理積の後）は、他の列、すなわちＣＩＴＹおよびＡＧＥを考慮して、処理される所与のデータ項目が、ＣＩＴＹ（列１０４）が「ニューヨーク」に等しくかつＡＧＥ（列１０２）が３０未満であるという基準を付加的に満たすかどうかを判断することを指定する。ブロック２０６において作成される索引は任意であるが、索引が作成される場合には、第２の照会の実行はその索引を用いて条件式を効率的に評価できる。
【００９０】
実際には、第２の照会はフィルタリングの１つよりも多くのレベルまたは方向を考慮するための相互フィルタリング機構として動作できる。たとえば、上述の第２の照会は関心をフィルタリングする利用者および発行者のデータの両方を考慮する。重要なことに、記載されるプロセスは、基準の第２の集合が、誰に対して特定の情報を発行または提供できるか、またはすべきかに関するセキュリティまたは権限付与基準を表わすことによって、情報セキュリティに関する実施において動作できる。
【００９１】
データベース表の列にデータとして保存される式を評価するためのプロセス
図３Ａは、表の列にデータとして保存される式集合を評価するためのプロセスを例示するフローチャートである。
【００９２】
ブロック３０２において、式集合の各式からの各述語は、索引付けされる属性述語、保存される属性述語、および疎述語のうちの１つに分類される。索引付けされる属性述語は前述のとおり、索引付けされるために選択される述語であり、ここで索引は、それぞれの述語識別子に関連して述語表のそれぞれの列に保存される演算子および定数属性の集合に基づいている。
【００９３】
保存される属性述語は、その演算子および定数属性がそれぞれの識別子に関連して述語表のそれぞれの列に保存される述語であるが、それに対しては索引が作成されない。たとえば、保存される属性述語は、それらの識別子が式集合において十分に共通して用いられないか、またはそれらが基礎的属性（例、ＣＨＡＮＧＥ／ＰＲＩＣＥ）による演算を含む複合述語であるために、索引付けされなくてもよい。
【００９４】
疎述語は前述のとおり、それに関連する述語識別子が式集合において共通でない述語である。たとえば、疎述語は、ＢＥＴＷＥＥＮ演算子、同じ属性上の複数の演算子、関数、およびＬＩＫＥ演算子を伴う述語に由来するものであってもよい。疎述語ならびに関連の演算子および定数は、述語表中にデータとして保存される。
【００９５】
ブロック３０４において、式集合はブロック３０２において行なわれた述語の分類に基づいてフィルタリングされる。図３Ｂは、ブロック３０４の、述語分類に基づいて式をフィルタリングするステップを例示するフローチャートである。
【００９６】
ブロック３０４Ａにおいて、索引付けされる属性述語が第１にフィルタリングされることにより、その式に対して索引付けされる属性述語のすべてが所与のデータ項目に対して真である１つまたはそれ以上の式を含む式の第１の集合が得られる。第２に、ブロック３０４Ｂにおいて、式の第１の集合の保存される属性述語がフィルタリングされることにより、その式に対して保存される属性のすべてが所与のデータ項目に対して真である１つまたはそれ以上の式を含む式の第２の集合が得られる。第３に、ブロック３０４Ｃにおいて、式の第２の集合の疎述語があればそれがフィルタリングされることにより、その式に対して述語のすべてが所与のデータ項目に対して真である１つまたはそれ以上の式を含む式の第３の集合が得られる。よって、データ項目は式において指定される基準を満たす。
【００９７】
ハードウェア概要
図４は、この発明の実施例を実施し得るコンピュータシステム４００を例示するブロック図である。コンピュータシステム４００は、情報を通信するためのバス４０２またはその他の通信機構と、情報を処理するためにバス４０２に結合されるプロセッサ４０４とを含む。コンピュータシステム４００はまた、情報およびプロセッサ４０４によって実行される命令を保存するためにバス４０２に結合される、ランダムアクセスメモリ（ＲＡＭ）またはその他の動的記憶装置などの主メモリ４０６を含む。主メモリ４０６はまた、プロセッサ４０４によって実行される命令の実行の際に一時的変数またはその他の中間情報を保存するために用いられてもよい。コンピュータシステム４００はさらに、静的情報およびプロセッサ４０４に対する命令を保存するためにバス４０２に結合される読出専用メモリ（ＲＯＭ）４０８またはその他の静的記憶装置を含む。情報および命令を保存するために、磁気ディスク、光ディスク、または光磁気ディスクなどの記憶装置４１０が設けられ、バス４０２に結合される。
【００９８】
コンピュータシステム４００はバス４０２を介して、コンピュータユーザに情報を表示するための陰極線管（ＣＲＴ）または液晶ディスプレイ（ＬＣＤ）などのディスプレイ４１２に結合されてもよい。情報およびコマンド選択をプロセッサ４０４に通信するために、英数字およびその他のキーを含む入力装置４１４がバス４０２に結合される。別の種類のユーザ入力装置は、方向情報およびコマンド選択をプロセッサ４０４に通信し、かつディスプレイ４１２上のカーソルの動きを制御するための、マウス、トラックボール、またはカーソル方向キーなどのカーソル制御４１６である。この入力装置は典型的に、第１の軸（例、ｘ）および第２の軸（例、ｙ）の２軸における自由度２を有し、それによって装置は平面における位置を指定できる。
【００９９】
この発明は、ここに記載される技術を実施するためのコンピュータシステム４００の用法に関する。この発明の実施例の１つに従うと、これらの技術は、主メモリ４０６に含まれる１つまたはそれ以上の命令の１つまたはそれ以上の連続を実行するプロセッサ４０４に応答して、コンピュータシステム４００によって行なわれる。このような命令は、記憶装置４１０などの別のコンピュータ読取可能媒体から主メモリ４０６に読込まれてもよい。主メモリ４０６に含まれる連続する命令の実行により、プロセッサ４０４はここに記載されるプロセスステップを行なう。代替的な実施例においては、ソフトウェア命令の代わりに、またはそれと組合せてハードワイヤード回路を用いてこの発明を実施してもよい。すなわち、この発明の実施例は、ハードウェア回路およびソフトウェアのいかなる特定の組合せにも制限されない。
【０１００】
ここで用いられる「コンピュータ読取可能媒体」という用語は、実行のためにプロセッサ４０４に命令を与えることに関係するあらゆる媒体を示す。このような媒体は、不揮発性媒体、揮発性媒体、および伝送媒体を含むがそれに制限されない多くの形をとり得る。不揮発性媒体はたとえば、記憶装置４１０などの、光、磁気、または光磁気ディスクを含む。揮発性媒体は、主メモリ４０６などの動的メモリを含む。伝送媒体は、バス４０２を含むワイヤを含む、同軸ケーブル、銅線および光ファイバを含む。伝送媒体はまた、無線波および赤外データ通信の際に生じるものなどの、音波または光波の形もとり得る。
【０１０１】
コンピュータ読取可能媒体の一般的な形はたとえば、フロッピーディスク、フレキシブルディスク、ハードディスク、磁気テープ、またはあらゆるその他の磁気媒体、ＣＤ−ＲＯＭ、あらゆるその他の光媒体、パンチカード、紙テープ、孔のパターンを有するあらゆるその他の物理的媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、フラッシュ−ＥＰＲＯＭ、あらゆるその他のメモリチップもしくはカートリッジ、以下に説明する搬送波、またはコンピュータが読取可能なあらゆるその他の媒体を含む。
【０１０２】
実行のためにプロセッサ４０４に１つまたはそれ以上の命令の１つまたはそれ以上の連続を運ぶステップには、さまざまな形のコンピュータ読取可能媒体が関係し得る。たとえば、命令は最初は、遠隔コンピュータの磁気ディスクに保持されていてもよい。遠隔コンピュータはその動的メモリに命令をロードし、その命令をモデムを用いて電話線を通じて送信できる。コンピュータシステム４００に対してローカルなモデムは、電話線からデータを受信し、赤外送信機を用いてそのデータを赤外信号に変換できる。赤外検出器は赤外信号中に保持されるデータを受信でき、適切な回路がそのデータをバス４０２に配置できる。バス４０２はデータを主メモリ４０６に運び、プロセッサ４０４はそこから命令を検索して実行する。主メモリ４０６が受取る命令は、プロセッサ４０４による実行の前または後に、記憶装置４１０に任意に保存されてもよい。
【０１０３】
コンピュータシステム４００はまた、バス４０２に結合される通信インターフェイス４１８を含む。通信インターフェイス４１８は、ローカルネットワーク４２２に接続されるネットワークリンク４２０に結合する２方向のデータ通信を提供する。たとえば、通信インターフェイス４１８は、対応する種類の電話線へのデータ通信接続を提供する統合サービスデジタル網（ＩＳＤＮ）カードまたはモデムであってもよい。別の例として、通信インターフェイス４１８は、互換性のローカルエリアネットワーク（ＬＡＮ）へのデータ通信接続を提供するＬＡＮカードであってもよい。ワイヤレスリンクが実施されてもよい。このような実施のいずれにおいても、通信インターフェイス４１８は、さまざまな型の情報を表わすデジタルデータストリームを運ぶ電気、電磁気または光信号を送信および受信する。
【０１０４】
ネットワークリンク４２０は典型的に、１つまたはそれ以上のネットワークを通じて他のデータ装置へのデータ通信を提供する。たとえば、ネットワークリンク４２０は、ホストコンピュータ４２４またはインターネットサービスプロバイダ（ＩＳＰ）４２６によって操作されるデータ設備へのローカルネットワーク４２２を通じた接続を提供してもよい。続いてＩＳＰ４２６は、現在一般的に「インターネット」４２８と呼ばれる世界的なパケットデータ通信ネットワークを通じたデータ通信サービスを提供する。ローカルネットワーク４２２およびインターネット４２８はどちらも、デジタルデータストリームを運ぶ電気、電磁気または光信号を用いる。コンピュータシステム４００へ、およびそこからデジタルデータを運ぶ、さまざまなネットワークを通じた信号ならびにネットワークリンク４２０上および通信インターフェイス４１８を通じた信号は、情報を搬送する搬送波の例示的な形である。
【０１０５】
コンピュータシステム４００は、ネットワーク、ネットワークリンク４２０および通信インターフェイス４１８を通じて、プログラムコードを含む、メッセージを送信してデータを受信できる。インターネットの例において、サーバ４３０は、インターネット４２８、ＩＳＰ４２６、ローカルネットワーク４２２および通信インターフェイス４１８を通じて、アプリケーションプログラムに対する要求されるコードを送信してもよい。
【０１０６】
受信されるコードは受信されてすぐにプロセッサ４０４により実行されても、および／または、後の実行のために記憶装置４１０またはその他の不揮発性記憶装置に保存されてもよい。この態様で、コンピュータシステム４００は搬送波の形のアプリケーションコードを得てもよい。
【０１０７】
拡張および代替案
この発明の代替的な実施例は、前述の記載を通じて、実施例の状況の理解を最も容易にする場所に記載されている。さらに、この発明について、特定の実施例を参照しながら説明した。しかし、この発明のより広い趣旨および範囲から逸脱することなくさまざまな変更および修正が行なわれ得ることが明らかとなるだろう。たとえば、ＳＱＬを用いる実施
が示されたが、ここに説明される技術はＳＱＬとの使用に制限されず、その他のデータ照会言語も適用可能である。別の例として、利用者／発行者システムの状況における実施が示されたが、この発明の実施例の利点および用法はこの状況に制限されない。もう１つの例として、述語表の列に連結ビットマップ索引が作成される実施が示された。しかし、実施例はこうした索引には制限されず、データ表の複数の列を索引付けするために好適なその他の索引型も適用可能である。したがって、明細書および図面は、制限的な意味ではなく例示的な意味に考えられる。
【０１０８】
加えて、この記載においては特定のプロセスステップが特定の順序で示されており、特定のステップを識別するために英字および英数字ラベルが用いられているかもしれない。記載において特定的に述べられない限り、この発明の実施例は必ずしもこうしたステップを実施するあらゆる特定の順序に制限されない。特に、ラベルはステップを識別する利便性のためにのみ用いられており、こうしたステップを実行する特定の順序を指定または要求することは意図されない。
【図面の簡単な説明】
【０１０９】
【図１】ここに記載されるプロセスまたはステップの例を支持するために用いられる表の例である。
【図２】データベース中の式を管理するためのプロセスを例示するフローチャートである。
【図３】図３Ａは、表の列においてデータとして保存される式集合を評価するためのプロセスを例示するフローチャートである。図３Ｂは、述語分類に基づいて式をフィルタリングするステップを例示するフローチャートである。
【図４】この発明の実施例を実施し得るコンピュータシステムを例示するブロック図である。
【図１】
2005525657.tif 000011
【図２】
2005525657.tif 000012
【図３Ａ】
2005525657.tif 000013
【図３Ｂ】
2005525657.tif 000014
【図４】
2005525657.tif 000015
【国際調査報告】
2005525657.tif 000016
2005525657.tif 000017
2005525657.tif 000018
2005525657.tif 000019
2005525657.tif 000020