JPH0652225A - ファイル検索方法及びシステム - Google Patents

ファイル検索方法及びシステム

Info

Publication number
JPH0652225A
JPH0652225A JP5098280A JP9828093A JPH0652225A JP H0652225 A JPH0652225 A JP H0652225A JP 5098280 A JP5098280 A JP 5098280A JP 9828093 A JP9828093 A JP 9828093A JP H0652225 A JPH0652225 A JP H0652225A
Authority
JP
Japan
Prior art keywords
mark
column
row
matrix
records
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP5098280A
Other languages
English (en)
Other versions
JP2845392B2 (ja
Inventor
Yau C Lau
ヤウ・チョン・ラウ
Eric J Mozdy
エリック・ジョン・マッツディ
John A Oleszkiewicz
ジョン・アンソニー・オレスズキーウィッチ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH0652225A publication Critical patent/JPH0652225A/ja
Application granted granted Critical
Publication of JP2845392B2 publication Critical patent/JP2845392B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2455—Query execution
    • G06F16/24553—Query execution of query operations
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2455—Query execution
    • G06F16/24553—Query execution of query operations
    • G06F16/24561—Intermediate data storage techniques for performance improvement
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】 【目的】 垂直方向にデータベースファイルを検索する
ためのシステムを提供する。 【構成】 データベースファイルの全てのレコードに対
して共通のフィールドからアクセスされたデータ要素と
１以上の検索引き数との一致あるいは不一致を指示する
マークからなる２次元マトリクスが作成される。ファイ
ルの全てのレコードを通じる一つのパスの後に作成され
たこのマークからなるマトリクスは、連続するレコード
間でデータ要素値が検索引き数によって特定されたある
系列を持つレコードを識別する。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、データベース検索シス
テム、特に、連続するレコードの特定フィールド中のデ
ータ要素値の特定された系列(sequence)を有するデータ
ベース中で、レコードを識別することを可能とする検索
システムに関する。
【０００２】
【従来の技術】典型的なデータベースファイルは、一連
の行および列からなる。各行が固定長を有し、１レコー
ドのそれぞれのために、データ項目を保持する。データ
ベースファイルの各列あるいは各フィールドがパラメー
タファミリーのそれぞれのパラメータのために値を保持
する。データベースファイルの一例は、しばしば従業員
レコードのファイルの用語で記述される。各レコードが
氏名、住所、年齢、給与、部署等のような多数のフィー
ルドあるいはパラメータを含む。
【０００３】この種のデータベースの典型的な用途は、
各レコードのパラメータがある基準を満足しなければな
らない従業員レコードを返答するために、データベース
を検索あるいは照会することである。一例として、５０
才以上で、＄５０，０００．００より少ない給与の者を
部署Ｄ８２あるいはＤ７５から従業員レコードを返答す
る。各レコードがそれらのフィールドにおいて検査さ
れ、ロジックが実行され、若し、全てのパラメータが特
定値と一致するならば、ユーザにとって利用可能とされ
る。
【０００４】他の種類のデータベースファイルとして
は、事象あるいは時間経過の各系列のためのレコードか
らなる歴史的なファイルとして特徴付けられるものがあ
る。フィールドあるいはパラメータがその時間経過に存
在していた値を保持する。このレコードは、日、月、年
等を表現でき、また、パラメータが種々の測定された、
特性を保持する。上述の用途は、特定のレコードの種々
のパラメータが特定の検索引き数あるいは基準を満足す
るレコードを返答するために利用可能である。
【０００５】上述の用途は、水平方向的として特徴付け
ることができる検索あるいは照会を含む。すなわち、フ
ァイルの水平方向の行あるいはレコードのそれぞれの複
数のパラメータが検索引き数と比較される。返答される
レコードは、検索引き数の全てと一致するパラメータを
持たねばならない。
【０００６】本発明のもとになる歴史的なデータベース
ファイルの利用は、非常に多くのコンピュータ回路、バ
ス、およびコンピュータ動作の数千サイクルに関して値
を記録するためのレジスタのために作成されるファイル
を含む。作成されたファイルの解析は、しばしば特定の
サイクルの系列あるいはシリーズ中に存在するパラメー
タあるいはフィールドの値の知識を必要とする。一例と
して、命令系列がＡＤＤ、ＳＵＢＴＲＡＣＴ、ＤＩＶＩ
ＤＥであり、値１０、２０、５を持ったメモリアドレス
レジスタのレコードが識別される。
【０００７】上述の例で必要なことは、水平方向の検索
というよりは、垂直方向の検索である。一つの特定のレ
コード中のパラメータ間ではなく、連続するレコードの
１列中のパラメータ値の関係から所望の情報が生じる。
データベースファイルの水平方向の検索のための典型的
な検索あるいは照会プログラムは、不適切である。
【０００８】
【発明が解決しようとする課題】本発明の一つの目的
は、垂直方向においてデータベースを検索するためのシ
ステムを提供することにある。
【０００９】本発明の他の目的は、連続するレコード間
で、パラメータ値関係を有するレコードを識別するため
に、データベースファイルを検索するためのシステムを
提供することにある。
【００１０】本発明のさらなる目的は、連続するレコー
ドの同一のパラメータが特定された系列の値を有するレ
コードを識別するために、データベースファイルを検索
するためのシステムを提供することにある。
【００１１】
【課題を解決するための手段】これらの目的、他の態様
および利点は、２次元マトリクス（行列）あるいはマー
クのアレイ（配列）を作成するシステム内でなし遂げら
れる。以下ではこれをマークマトリクスと呼ぶ。マーク
マトリクスは、データベースファイル内のレコード数と
等しい行の数「Ｎ」を有する。検索システムに対して提
示される検索引き数の数と等しい列の数「Ｍ」を有し、
各列が関連する検索引き数を表す。
【００１２】データベースの特定のパラメータ、フィー
ルド、あるいは列は、行１から行Ｎまでアクセスされ、
データ要素値がＭ個のそれぞれの検索引き数と比較され
る。マークマトリクスの行１からＮまでのそれぞれの対
応する列において、一致あるいは不一致指示がＭ個の検
索引き数のために、マークマトリクス内に入力される。
【００１３】データベースファイルを通る単一のパスが
完了すると、一致および不一致指示のパターンがマーク
マトリクス内で検査される。検索引き数の系列を検索
し、従って、所望のレコード番号は、若し、ある行の列
１の一致からマークマトリクスのＭ番目あるいは最終の
列における一致指示に向かって、マークマトリクスの連
続する行および列を通じて、検索パターンが進むなら
ば、識別される。
【００１４】データベースファイルの２以上パラメー
タ、フィールド、あるいは列が検索引き数の２以上のセ
ットと比較されうる。一致および不一致の指示を有する
マークマトリクスが検索引き数の各セットのために作成
される。同様に、データベースを通る一つのパスと、２
以上のマークマトリクスの作成の後に、マトリクスが論
理的にＡＮＤされ、結果マークマトリクスが作成され
る。一致および不一致指示からなる結果マトリクスは、
上述と同じように検索され、２以上の列の値の系列が検
索引き数の２以上のセットを満足するレコードが識別さ
れる。
【００１５】
【実施例】一般的なデータベースの検索あるいは照会と
本発明による検索性能との間の基本的な相違点につい
て、以下の表１と関連して説明する。検索引き数を示す
照会に応答する典型的な水平方向検索は、データベース
ファイルの各レコード中の種々のフィールド間の関係を
テストし、若し、レコード中の全てのフィールドが検索
引き数を満足するならば、レコードを戻す。本発明は、
照会あるいは検索引き数のセットを満足するレコードの
ＩＤを戻す。照会あるいは検索引き数のセットは、デー
タベースファイルの引き続くレコード中の同一の列から
のデータ要素の値間の特定の関係を要求する。
【００１６】
【表１】 問題：データフィールド値が系列（１，４，１６）を有する 開始および終了レコードを見つけよ。 レコード番号 データフィールド マークマトリクス １ ２ ３ １ １ ＝ ． ． ２ ３ ． ． ． ３ １ ＝ ． ． ４ ４ ． ＝ ． ５ １６ ． ． ＝ ６ ２２ ． ． ． ７ ４ ． ＝ ． ８ １６ ． ． ＝ − − − − − − Ｎ ６ ． ． ． 解答：３，５
【００１７】上述のマークマトリクスを作成するための
方法について続いて説明する。示されているデータフィ
ールドは、データベースファイルのＮ個のレコードの全
てに対して共通のフィールドから得られたデータの列を
表す。与えられた問題は、Ｎ個のデータ要素の値と３個
の検索引き数とを比較することを要求する。Ｎ×３のマ
ークマトリクスが作成される。
【００１８】本発明の重要な特徴は、データベースの垂
直列内のＮ個のデータ要素の単一のアクセスのみが必要
なことである。各データ要素は、データベースの行から
アクセスされているので、それは、３個の検索引き数と
比較され、検索引き数と関連する列中で、マークマトリ
クスの対応する行が一致（＝）あるいは不一致（．）と
してマークされる。＝あるいは、．の表示がマトリクス
中に蓄えられる符号化文字であるけれども、典型的に
は、マトリクスの全ての要素が最初に２値の（ｂｉｎａ
ｒｙ）秒０＾ にセットされ、引き数と一致することを
示す２値の。1^ に変更される。
【００１９】各データ要素と検索引き数との値の関係の
指示を有するマークマトリクスが作成されている時に
は、一致あるいは不一致の指示が行１および列１で始ま
るマトリクスの各行で検出される指示に依存する検索パ
ターンを作成する。表１において、行１列１（１，１）
における一致によって、検索が行２列２（２，２）をテ
ストすることになる。不一致．を検索することによっ
て、３，１における次のテストがなされる。そこでの一
致によって、スタック中に番号３の記録がなされ、一致
が生じる４，２のテストによって、一致が検出される
５，３のテストがなされる。本発明の方法に対して与え
られる種々の問題の解答は、検索パターンがマークマト
リクス中のある行の列１における一致からそれに続く行
および最終列Ｍ（表１の例では、列３）の一致へ進む時
は、常に分かる。これによって、スタック中の番号５の
記録がなされ、これらのレコードがレコード４ととも
に、問題中の引き数によって与えられる値の系列を満足
するので、問題の解答が３，５となる。
【００２０】表１の例では、検索が行６の列１において
継続し、残りの不一致の指示のために、列２へ進むこと
がない。マークマトリクスの行Ｎに到達する時に、検索
が終了する。
【００２１】本発明は、表１中に提起されているような
問題を解決するためと考えられるけれども、データベー
スを通る単一のパスの後でマークマトリクスが一旦作成
されると、他の問題が解決されうる。一例として、マト
リクスを検索してフィールド中で１の値を持つレコード
あるいはレコード数を決定することは、非常に容易であ
る。また、１６が続いている４の値を有するレコードが
何かという他の問題に対しても回答しうる。検索は、列
２および３のみをテストして、解答４，５および７，８
を戻すと定式化しうる。
【００２２】図１および図２は、マークマトリクスの作
成と、表１で提起された問題のためにマトリクスを検索
するためのロジックの概略図である。データ処理システ
ムのメモリ内に蓄えられるデータベースファイルは、図
１中で一般的に１０として示される。データベース１０
が１からＮと番号付けられたレコード１１、あるいは列
からなる。各レコード１１は、複数のデータ要素フィー
ルド１２から構成され、また、各フィールド１２は、１
以上の２進ビットの列１３から構成される。ユーザは、
データベース１０を識別し、蓄えた後で、データ要素値
の検索中にアクセスされうるフィールド１２、あるいは
特定の列１３を特定する。フィールド１２あるいは列１
３の特定は、全てのレコード１１に対して共通のパラメ
ータあるいはデータを明らかにし、従って、本発明によ
り可能な垂直検索で使用されるデータの列を作成する。
【００２３】ここで、ユーザが所望の検索引き数を特定
したとする。これらは、検索引き数レジスタ１４に入力
される。表１で提示された問題に従って、値１，４，お
よび１６が各レジスタ１４に入力される。図１に示すよ
うに、任意の個数Ｍの検索引き数が入力されうる。
【００２４】検索引き数の個数、表１の場合では３を特
定することによって、図１において１５で一般的に示さ
れるマークマトリクスのために必要とされる列の数をユ
ーザが指示する。このことは、Ｎ行１６およびＭ列１７
を有するＮ×Ｍの２次元マトリクスを作成する。図１で
は、３が示されているが、Ｍ個の列１７まで可能であ
る。
【００２５】アドレスカウンタ１８がデータベース１０
およびマークマトリクス１５の両者の行１からＮまでを
アクセスする。データベース１０のフィールド１２ある
いは列１３のデータ要素が連続してアクセスされ、ライ
ン１９を介してコンパレータ２０へ与えられる。アクセ
スされた各データ要素は、コンパレータ２０において、
レジスタ１４の検索引き数の値と比較される。データベ
ース１０の行１１とマークマトリクス１５の行１６がア
クセスされるので、レジスタ１４の引き数と各データ要
素との比較結果は、マークマトリクス１５の適切な列１
７に記憶されるべき２値の１を生じさせる。図１に示さ
れる２値の１および０のパターンは、表１の＝および．
のパターンに一致している。
【００２６】図２は、表１の例で検出される解答を提供
するロジックの概略図である。１からＮまでの行と１か
ら３までの列とを有するマークマトリクス１５が示され
ている。アドレスカウンタ２１は、各列１７に関して、
より大きな連続する行をアクセスするように設計され、
それによってマークマトリクス１５の３個の連続する行
および列からの読出しがなされる。連続する行および列
の２値の１あるいは０が論理的なＡＮＤゲート２２に対
して与えられる。図２に示すように、全ての３個の入力
が２値の１である時に、ライン２３に出力が発生する。
【００２７】ライン２３の付勢によって、ライン２４上
のアドレスカウンタ２１の内容が、ゲート２５を介して
レジスタ２７のスタック２６の第１のロケーションに渡
される。ライン２３上の出力によって、アドレスインク
リメンタ２８がスタック２６の次のレジスタ２７をアク
セスし、若し、マークマトリクス１５の全ての行１６を
通じてアドレスカウンタ２１が進む時に、他の値が見出
されるならば、その値が記憶される。検索引き数の数が
既知であり、最終レコードが番号５であるから、最初の
レジスタ番号「３」のみが記憶される必要がある。図２
のハードウエアロジックは、マークマトリクス１５の列
１から列３まで斜め方向に進む一致指示のパターンを見
つける。
【００２８】図１および図２は、本発明を実現するロジ
ックを示す。本発明の好ましい実施例は、図１のマーク
マトリクス１５を作成するのに種々のステップを遂行す
るために、また、提示された問題に依存してマークマト
リクス中に記録される一致あるいは不一致指示をテスト
する時に、検索パターンを変化させるために、プログラ
ミングを利用する。
【００２９】図３は、マークマトリクスの指示を作成す
るのに必要なプログラミングステップを示す。３０にお
いて、データベースファイルのＮ個のレコードのＮ個の
データ要素が特定される。これは、アクセスされている
レコードのフィールドあるいは列の数の大きさＫを有す
るステップを含む。３１において、マークマトリクスの
Ｎ×Ｍの２次元マトリクスが特定される。
【００３０】３２において、データ要素の列中のＮ個の
データ要素のそれぞれのアクセスがアクセスされ、Ｍ個
の検索引き数と比較される。３３において、一致あるい
は不一致指示が決定される。３４において、一致（＝あ
るいは２値の１）がその引き数と関連するマークマトリ
クスの適切な列に記録される。若し、データ要素がどの
引き数とも一致しないならば、他の決定が３５において
なされる。問題によっては、いくつかの検索引き数が
「無関心」（ don^t care") （＊）と指定される。その
ような例について引続き説明する。無関心＊は、マトリ
クス位置に関して２値の１を記録する。説明される無関
心位置では、図１中の４の値を蓄える第２の検索引き数
レジスタ１４が「＊」を蓄え、マークマトリクス１５の
列２の各行で、＊あるいは１を蓄えるために有効とされ
る。若し、検索引き数が＊であれば、３６において、関
連する列が＊あるいは２値の１によってマークされる。
若し、検索引き数が無関心であり、データ要素がどの検
索引き数とも一致しないならば、３７において、マーク
マトリクスの＊あるいは＝の何れも有しない全ての列が
不一致．あるいは２値の０によってマークされる。
【００３１】３８において、全てのＮ個のデータがアク
セスされたかどうかが決定される。若し、そうでないな
らば、３９において、データベースの次の行あるいはデ
ータ要素がアクセスされ、マークマトリクスの次の行が
次の比較のためにアクセスされる。Ｎに到達すれば、マ
ークマトリクスの作成が４０において終了する。
【００３２】次の表２と図４は、マークマトリクスの作
成と、無関心「＊」の検索引き数を用いるマトリクスの
検索パターンの横切り(traversal) を説明するために使
用される。
【００３３】
【表２】 問題：データフィールド値が系列（一つの介在レコードを有する３に続く４）を 有する開始および終了レコードを見つけよ。 レコード番号 データフィールド マークマトリクス １ ２ ３ １ １ ． ＊ ． ２ ３ ＝ ＊ ． ３ １ ． ＊ ． ４ ４ ． ＊ ＝ ５ １６ ． ＊ ． ６ ３ ＝ ＊ ． ７ ４ ． ＊ ＝ ８ １６ ． ＊ ． ９ ５ ． ＊ ． − − − Ｎ ６ ． ＊ ． 解答：２，４
【００３４】表２の問題文は、各行で無関心「＊」を指
示するために、マークマトリクスの列２が必要である。
２次元マークマトリクスの簡単さから、マークの所望の
パターンのためにマトリクスを検索するためのプログラ
ムステップの設計は、容易に分かる。図４は、上述の回
答を検索するために必要なステップを示し、データ系列
中のレコード６および７の記録が除かれる。
【００３５】４１、４２および４３において、マトリク
スの検索がマークマトリクスの行１、列１で開始する。
表２の例では、４４へ向かって不一致のパスＢがとら
れ、マトリクスの列１で連続する行の検査が継続する。
若し、例において３の値を持つレコードが存在しないな
らば、ステップ４５は、最終レコードＮに到達するま
で、継続する。
【００３６】パスＢの一部は、この例では、レコード番
号２の値３を検出するのに有効なステップ４６である。
このレコード番号は、プログラムステップ中のパスＡの
一部として４７において、スタック中に記録される。提
示される問題に対するマークマトリクスを使用する解答
の基本的方法は、最終列（最大Ｍ）で一致が見つかるま
で、マトリクスの行から行へ、および列から列へ進むこ
とである。この基本的方法は、プログラムステップの４
８において開始される。
【００３７】表２の例に従うと、行３および列２を検査
することにより、無関心指示＊が見つけられ、ステップ
が４９へ進み、ここで、行４、列３が試験され、一致が
見つけられる。５０において、プログラムがパスＡへ戻
り、４７において、スタック中にレコード番号４が記録
される。ステップ４８が最大Ｍ（３）に到達したことを
検出すると、ステップ５１および５２が有効となり、解
答２，４を永続的に記録し、また、ステップ４３へパス
１に沿って行５、列１で検索が継続される。
【００３８】４６において、行６、列１における一致が
見つけられ、検索がステップ４７および４８に戻る。レ
コード番号６が４７において、スタックへ記録される。
４８において、行７、列２における無関心＊が見つけら
れ、ステップが行８、列３の検査４９に進み、そこでは
一致指示を見つけられない。ステップ５３は、スタック
から記録されたレコード番号６を消去し、検索を行９、
列１において、パス１へ戻る。
【００３９】上述のマークマトリクス作成の例は、検索
引き数とデータ要素とが等しいことを期待しているが、
マークマトリクスの作成のためのプログラムステップを
セットアップする時に、値の範囲を指定することができ
る。次の表３は、かかる例である。
【００４０】
【表３】 問題：どの年に在庫指数が２５０から３００へ 増加したか。 第１の引き数２５０ 第２の引き数２５０＜指数＜３００ 第３の引き数３００ 年度 指数 マークマトリクス １ ２ ３ ７０ ２５０ ＝ ． ． ７１ ２６０ ． ＝ ． ７２ ２３０ ． ． ． ７３ ３００ ． ． ＝ − − − − − − ８５ ２５０ ＝ ． ． ８６ ２７０ ． ＝ ． ８７ ２５５ ． ＝ ． ８８ ３００ ． ． ＝ − − − 解答：８５，８８
【００４１】この例では、問題により示される値の範囲
の結果として、マークマトリクスの列２をマークするプ
ログラムステップあるいはロジックによって、第２の検
索引き数レジスタ１４およびコンパレータ２０を取り替
えるように、図１に示されるロジックの概略図が変形さ
れる。上述のように、マークマトリクスの検索のための
プログラムステップは、行から行へ、並びに列１から開
始して、列３（Ｍ）で一致が見つけられるまで、列から
列へ進むように設計される。上述の例では、７２年で不
一致を見つけることによって、次の行の列１で検索が開
始させられる。
【００４２】本発明による２次元マークマトリクスは、
データ処理システムを試験するために、種々のレジスタ
および信号のサンプリングの期間で、作成される極めて
多数のレコードを有するデータベースファイルを検索す
るのに、非常に適している。多くの動作サイクルの歴史
的データは、特定の値の系列のに関して検出されなけれ
ばならず、また、レコード中の数フィールドの特定の系
列を含むサイクルの解析を必要とする。表４は、この結
果を生じさせるために、本発明の性能を実証するもので
ある。
【００４３】
【表４】 問題：データがフィールド１内に系列１，４，３を持ち 且つフィールド２内に系列２，４，６を持つ レコードを見つけよ。 レコード フィー マトリクス１ フィー マトリクス２ 結 果 ルド１ １ ２ ３ ルド２ １ ２ ３ １ ２ ３ １ １ ＝ ． ． ２ ＝ ． ． ＝ ． ． ２ ４ ． ＝ ． ４ ． ＝ ． ． ＝ ． ３ ３ ． ． ＝ ５ ． ． ． ． ． ． ４ １ ＝ ． ． ２ ＝ ． ． ＝ ． ． ５ ７ ． ． ． ４ ． ＝ ． ． ． ． ６ １ ＝ ． ． ２ ＝ ． ． ＝ ． ． ７ ４ ． ＝ ． ４ ． ＝ ． ． ＝ ． ８ ３ ． ． ＝ ６ ． ． ＝ ． ． ＝ 解答：６，８
【００４４】この例では、検索引き数の第１および第２
のセットがレコードの第１および第２のフィールドから
のデータ要素と比較され、第１および第２の２次元マー
クマトリクスが作成される。第１および第２のマークマ
トリクスは、前述のように作成される。結果としてのマ
ークマトリクスは、第１および第２のマトリクスの結果
をＡＮＤすることで作成される。そして結果マトリクス
は、前述のように検索され、結果マトリクスの列３が到
達されるまで、行の列１から斜めに行から行へ、並びに
列から列へ進むパターンが見つけられる。
【００４５】図５は、今述べた関係を示す。２以上のマ
ークマトリクス５４が５５で組み合わされ、５６におい
て、結果マークマトリクスが作成される。結果マークマ
トリクス５６が５７において、問題文に従って検索さ
れ、５８において、問題文を満足するレコード番号の出
力を提供する。
【００４６】本発明による２個の２次元マークマトリク
スの作成と、マトリクスを検索するために、プログラム
されることが可能な種々の方法は、並列処理技術によっ
てその概念を実現することに対して適合していることを
示唆する。図６は、並列処理の概略図である。メモリあ
るいはデータベース６０は、数個の中央処理ユニット
（ＣＰＵ）へ接続されるとともに、これらにより共有さ
れる。各ＣＰＵ６１がライン６２を介して受け取られた
検索引き数のセットを蓄えるために、それ自身の記憶装
置あるいはキャッシュを有している。ＣＰＵ記憶装置あ
るいはキャッシュは、データベース６０を、あるいは少
なくとも、ライン６３を介して受け取られたデータベー
ス中の全てのレコードの特定のフィールドからのデータ
要素を蓄える。各ＣＰＵ６１がマークマトリクス（Ｍ
Ａ）を作成し、これが他のＣＰＵ６５に対してライン６
４を介して出力される。ＣＰＵ６５は、全てのマークマ
トリクスを結合するようにプログラムされ、また、問題
文に従って結果マークマトリクスの検索を行う。ライン
６６上のＣＰＵ６５の出力が全ての検索引き数条件と問
題文と一致するデータベースのレコードのＩＤである。
【００４７】
【発明の効果】本発明により、垂直方向にデータベース
ファイルを検索するためのシステムを提供することがで
きる。
【図面の簡単な説明】
【図１】データ要素および１以上の検索引き数間の関係
を示すためのマークマトリクスを作成するためのロジッ
クを示す概略図である。
【図２】検索引き数と一致するレコードのためにマーク
マトリクスを検索する方法を示す概略図である。
【図３】本発明によりマークマトリクスを作成する方法
を示すデータ流れ図である。
【図４】データベースファイル中でレコード間の特定の
垂直関係のために、本発明に従ってマークマトリクスを
検索する方法を示すデータ流れ図である。
【図５】データベースファイルの１以上のフィールドの
垂直検索のために、２以上のマークマトリクスを結合す
るためのロジックを示す概略図である。
【図６】本発明の複数のマークマトリクスが並列処理技
術を用いてどのように実現されるかを示す概略図であ
る。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 エリック・ジョン・マッツディ アメリカ合衆国、ペンシルバニア州メッド ビル、ベルモントドライブ 1157 (72)発明者 ジョン・アンソニー・オレスズキーウィッ チ アメリカ合衆国、ニューヨーク州ポキプ シ、ホーランドコート ８

Claims (10)

    【特許請求の範囲】
  1. 【請求項１】 複数のデータの列を有するレコードから
    なるファイルを検索する方法であって、 Ａ．Ｍ個の検索引き数を特定するステップと、 Ｂ．ファイルのＮ個のレコードからデータをアクセスす
    るステップと、 Ｃ．上記Ｍ個の検索引き数と上記Ｎ個のレコードのデー
    タ要素を比較するステップと、 Ｄ．Ｎ個のデータ要素のそれぞれとＭ個の検索引き数の
    それぞれとの値の関係を指示するマークからなるＮ×Ｍ
    のマトリクスを作成するステップと、 Ｅ．各マークによって指示される値の関係に従って、上
    記Ｎ×Ｍのマークマトリクスを検索するステップとから
    なる上記方法。
  2. 【請求項２】 上記検索ステップＥは、ＮおよびＭ次元
    のマーク間の部分的関係を特定するためのものである請
    求項１に記載の方法。
  3. 【請求項３】 Ｆ．上記特定された部分関係のマークを
    有する上記Ｎ個のレコードのレコード番号を記録するス
    テップをさらに有する請求項２に記載の方法。
  4. 【請求項４】 上記ステップＣのデータ要素は、Ｎ個の
    レコードの全てに対して共通の列からなり、それによっ
    て、Ｎ個のデータ要素からなる列を作成するようになさ
    れる請求項３に記載の方法。
  5. 【請求項５】 上記ステップＤの値の関係が一致、不一
    致あるいは無関心を含む請求項４に記載の方法。
  6. 【請求項６】 上記ステップＤの一致関係が等しい、等
    しいかより大きい、等しいかより小さい、より小さい、
    より大きいを含む請求項５に記載の方法。
  7. 【請求項７】 上記ステップＤにおいて作成されたマー
    クマトリクスがＮ行および１からＭまでの列を有し、 上記ステップＥにおいて特定された部分関係は、 行Ｘの列１に一致指示を含み、列Ｍで一致が検出される
    まで、行から行へ、並びに次の連続する列へ進む一致指
    示が続くものである請求項６に記載の方法。
  8. 【請求項８】 上記ステップＦにおいて記録されるレコ
    ード番号は、マークマトリクスの行Ｘと関連するレコー
    ド番号と、列Ｍ中で検出されたマークマトリクスの行と
    関連するレコード番号とを含む請求項７に記載の方法。
  9. 【請求項９】 複数のデータの列を有するレコードから
    なるファイルを検索する方法であって、 Ａ．Ｓ個の検索引き数からなる第１のセットとＴ個の検
    索引き数からなる少なくとも第２のセットを特定するス
    テップと、 Ｂ．ファイルのＮ個のレコードの全てに対して共通のデ
    ータ要素フィールドからなる複数の第１の列と、ファイ
    ルのＮ個のレコードの全てに対して共通のデータ要素フ
    ィールドからなる複数の少なくとも第２の列とをアクセ
    スするステップと、 Ｃ．上記第１のデータフィールドからのＮ個のデータ要
    素のそれぞれと、上記Ｓ個の検索引き数のそれぞれとの
    値の関係を指示するマークからなる第１のＮ×Ｓのマト
    リクスと、上記第２のデータフィールドからのＮ個のデ
    ータ要素のそれぞれと、上記Ｔ個の検索引き数のそれぞ
    れとの値の関係を指示するマークからなる少なくとも第
    ２のＮ×Ｔのマトリクスとを作成するステップと、 Ｄ．上記第１および第２のマークマトリクスからのマー
    クを論理的に結合して、第３のＮ×Ｕ（Ｕは、Ｓおよび
    Ｔと等しい）の第３のマトリクスを形成するステップ
    と、 Ｅ．各マークによって指示される値の関係に従って上記
    第３のＮ×Ｕのマークマトリクスを検索するステップと
    からなる上記方法。
  10. 【請求項１０】 Ｎ個のレコードからなり、各レコード
    が複数の２値データ要素の列からなり、全てのレコード
    中のデータ要素に共通の列がＮ個のデータ要素の垂直列
    からなる、データベースファイルを検索するためのシス
    テムであって、 上記Ｎ個のデータ要素を蓄えるための記憶手段と、 Ｍ個の検索引き数を蓄えるための引き数記憶手段と、 Ｎ行Ｍ列からなる２次元マークマトリクスを作成し、蓄
    えるためのマーク記憶手段と、 上記データ記憶手段と上記マーク記憶手段とに結合さ
    れ、各上記データ要素と上記マーク記憶手段の対応する
    行をアクセスするための手段と、 上記データ記憶手段および上記引き数記憶手段の上記ア
    クセス手段と結合され、上記データ要素のそれぞれと上
    記Ｍ個の検索引き数とを比較するための手段と、 上記Ｍ個の比較手段の各出力を上記マーク記憶手段の上
    記Ｍ列の対応するものに結合し、上記マーク記憶の１行
    中に、上記マーク記憶の行と関連するデータ要素と上記
    マーク記憶の上記列の一つと関連する上記Ｍ個の検索引
    き数の一つとの間の一致を指示するとともに、蓄えるた
    めの手段と、 上記マーク記憶手段を横切り、上記マーク記憶の行の列
    １から次の行の列Ｍまで進む、一致指示のパターンを上
    記行および上記列内で検出するための検索手段と、 一致指示の上記パターンを検出した結果として、上記マ
    ーク記憶の開始および終了の行の行番号、従ってレコー
    ド番号を記録するための手段とからなる上記システム。
JP5098280A 1992-06-04 1993-04-26 ファイル検索方法及び装置 Expired - Lifetime JP2845392B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US893297 1992-06-04
US07/893,297 US5377348A (en) 1992-06-04 1992-06-04 System for searching a data base by creating a marking matrix in which two dimensional patterns control the search and selection

Publications (2)

Publication Number Publication Date
JPH0652225A true JPH0652225A (ja) 1994-02-25
JP2845392B2 JP2845392B2 (ja) 1999-01-13

Family

ID=25401354

Family Applications (1)

Application Number Title Priority Date Filing Date
JP5098280A Expired - Lifetime JP2845392B2 (ja) 1992-06-04 1993-04-26 ファイル検索方法及び装置

Country Status (4)

Country Link
US (1) US5377348A (ja)
EP (1) EP0572807A2 (ja)
JP (1) JP2845392B2 (ja)
CA (1) CA2092629C (ja)

Families Citing this family (49)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2502023B2 (ja) * 1992-04-13 1996-05-29 インターナショナル・ビジネス・マシーンズ・コーポレイション デ―タ・ファイルの比較方法及びシステム
US5649181A (en) * 1993-04-16 1997-07-15 Sybase, Inc. Method and apparatus for indexing database columns with bit vectors
US5794229A (en) * 1993-04-16 1998-08-11 Sybase, Inc. Database system with methodology for storing a database table by vertically partitioning all columns of the table
US5794228A (en) * 1993-04-16 1998-08-11 Sybase, Inc. Database system with buffer manager providing per page native data compression and decompression
US5852821A (en) * 1993-04-16 1998-12-22 Sybase, Inc. High-speed data base query method and apparatus
US5918225A (en) * 1993-04-16 1999-06-29 Sybase, Inc. SQL-based database system with improved indexing methodology
JP3602596B2 (ja) * 1995-02-22 2004-12-15 株式会社東芝 ドキュメントファイリング装置および方法
US6484168B1 (en) * 1996-09-13 2002-11-19 Battelle Memorial Institute System for information discovery
DE19715723A1 (de) * 1997-04-15 1998-11-12 Dci Datenbank Fuer Wirtschafts Array-Verfahren
US6185559B1 (en) 1997-05-09 2001-02-06 Hitachi America, Ltd. Method and apparatus for dynamically counting large itemsets
EP1049030A1 (en) 1999-04-28 2000-11-02 SER Systeme AG Produkte und Anwendungen der Datenverarbeitung Classification method and apparatus
AU7100600A (en) * 1999-09-03 2001-04-10 Whamtech, L.P. Index relational processor
US7043488B1 (en) 2000-01-21 2006-05-09 International Business Machines Corporation Method and system for storing hierarchical content objects in a data repository
US6611840B1 (en) 2000-01-21 2003-08-26 International Business Machines Corporation Method and system for removing content entity object in a hierarchically structured content object stored in a database
US7613993B1 (en) 2000-01-21 2009-11-03 International Business Machines Corporation Prerequisite checking in a system for creating compilations of content
US6839701B1 (en) 2000-01-21 2005-01-04 International Business Machines Hitmask for querying hierarchically related content entities
US7356766B1 (en) 2000-01-21 2008-04-08 International Business Machines Corp. Method and system for adding content to a content object stored in a data repository
US8589777B1 (en) 2000-01-21 2013-11-19 International Business Machines Corporation Method and system for calculating cost of a compilation of content
US7089239B1 (en) 2000-01-21 2006-08-08 International Business Machines Corporation Method and system for preventing mutually exclusive content entities stored in a data repository to be included in the same compilation of content
US6449627B1 (en) 2000-01-21 2002-09-10 International Business Machines Corp. Volume management method and system for a compilation of content
US6986102B1 (en) 2000-01-21 2006-01-10 International Business Machines Corporation Method and configurable model for storing hierarchical data in a non-hierarchical data repository
US7401097B1 (en) 2000-01-21 2008-07-15 International Business Machines Corporation System and method for creating compilations of content
US7346844B1 (en) 2000-01-21 2008-03-18 International Business Machines, Corporation Method and system for moving content in a content object stored in a data repository
US7076494B1 (en) 2000-01-21 2006-07-11 International Business Machines Corporation Providing a functional layer for facilitating creation and manipulation of compilations of content
US7340481B1 (en) 2000-01-21 2008-03-04 International Business Machines Corp. Method and system for adding user-provided content to a content object stored in a data repository
MXPA02012251A (es) * 2000-06-09 2004-08-12 Nguyen Thanh Ngoc Metodo y aparato para administracion de compilacion de datos y conocimiento.
EP1182577A1 (en) 2000-08-18 2002-02-27 SER Systeme AG Produkte und Anwendungen der Datenverarbeitung Associative memory
US9177828B2 (en) 2011-02-10 2015-11-03 Micron Technology, Inc. External gettering method and device
EP1288792B1 (en) 2001-08-27 2011-12-14 BDGB Enterprise Software Sàrl A method for automatically indexing documents
US6823329B2 (en) * 2002-04-02 2004-11-23 Sybase, Inc. Database system providing methodology for acceleration of queries involving functional expressions against columns having enumerated storage
US7089266B2 (en) 2003-06-02 2006-08-08 The Board Of Trustees Of The Leland Stanford Jr. University Computer systems and methods for the query and visualization of multidimensional databases
US7756907B2 (en) 2003-09-16 2010-07-13 The Board Of Trustees Of The Leland Stanford Jr. University Computer systems and methods for visualizing data
US7243165B2 (en) * 2004-01-14 2007-07-10 International Business Machines Corporation Parallel pattern detection engine
US7800613B2 (en) * 2004-12-02 2010-09-21 Tableau Software, Inc. Computer systems and methods for visualizing data with generation of marks
US8099674B2 (en) 2005-09-09 2012-01-17 Tableau Software Llc Computer systems and methods for automatically viewing multidimensional databases
US7999809B2 (en) * 2006-04-19 2011-08-16 Tableau Software, Inc. Computer systems and methods for automatic generation of models for a dataset
US8321357B2 (en) 2009-09-30 2012-11-27 Lapir Gennady Method and system for extraction
US9158833B2 (en) 2009-11-02 2015-10-13 Harry Urbschat System and method for obtaining document information
US9152883B2 (en) 2009-11-02 2015-10-06 Harry Urbschat System and method for increasing the accuracy of optical character recognition (OCR)
US9213756B2 (en) 2009-11-02 2015-12-15 Harry Urbschat System and method of using dynamic variance networks
US9613102B2 (en) 2014-04-01 2017-04-04 Tableau Software, Inc. Systems and methods for ranking data visualizations
US9424318B2 (en) 2014-04-01 2016-08-23 Tableau Software, Inc. Systems and methods for ranking data visualizations
US20150278214A1 (en) 2014-04-01 2015-10-01 Tableau Software, Inc. Systems and Methods for Ranking Data Visualizations Using Different Data Fields
US10896297B1 (en) 2017-12-13 2021-01-19 Tableau Software, Inc. Identifying intent in visual analytical conversations
US11055489B2 (en) 2018-10-08 2021-07-06 Tableau Software, Inc. Determining levels of detail for data visualizations using natural language constructs
US11030255B1 (en) 2019-04-01 2021-06-08 Tableau Software, LLC Methods and systems for inferring intent and utilizing context for natural language expressions to generate data visualizations in a data visualization interface
US11042558B1 (en) 2019-09-06 2021-06-22 Tableau Software, Inc. Determining ranges for vague modifiers in natural language commands
CN112232700B (zh) * 2020-11-04 2024-01-09 广州宸祺出行科技有限公司 一种优化的专车指派的方法及系统
CN117539717B (zh) * 2023-11-23 2024-05-14 国网黑龙江省电力有限公司牡丹江供电公司 一种基于数据分析的器件工况智能监管系统及方法

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS6244829A (ja) * 1985-08-22 1987-02-26 Matsushita Graphic Commun Syst Inc パタ−ン抽出方法

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5206949A (en) * 1986-09-19 1993-04-27 Nancy P. Cochran Database search and record retrieval system which continuously displays category names during scrolling and selection of individually displayed search terms
JP2715465B2 (ja) * 1988-08-31 1998-02-18 日本電気株式会社 記号列照合装置
US5179643A (en) * 1988-12-23 1993-01-12 Hitachi, Ltd. Method of multi-dimensional analysis and display for a large volume of record information items and a system therefor
US5224038A (en) * 1989-04-05 1993-06-29 Xerox Corporation Token editor architecture
WO1990016036A1 (fr) * 1989-06-14 1990-12-27 Hitachi, Ltd. Procede de recherche documentaire a prerecherche hierarchique, appareil a cet effet, et dispositif a disque magnetique destine a cet appareil
DE69131941T2 (de) * 1990-10-05 2000-06-08 Microsoft Corp System und verfahren für informationsauffindung
US5150430A (en) * 1991-03-15 1992-09-22 The Board Of Trustees Of The Leland Stanford Junior University Lossless data compression circuit and method

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS6244829A (ja) * 1985-08-22 1987-02-26 Matsushita Graphic Commun Syst Inc パタ−ン抽出方法

Also Published As

Publication number Publication date
EP0572807A2 (en) 1993-12-08
CA2092629C (en) 1998-06-30
JP2845392B2 (ja) 1999-01-13
US5377348A (en) 1994-12-27
CA2092629A1 (en) 1993-12-05
EP0572807A3 (ja) 1994-01-19

Similar Documents

Publication Publication Date Title
JP2845392B2 (ja) ファイル検索方法及び装置
US6523030B1 (en) Sort system for merging database entries
US4554631A (en) Keyword search automatic limiting method
US6266660B1 (en) Secondary index search
JP3104708B2 (ja) 関係データベースシステムの表を結合する方法
US6185557B1 (en) Merge join process
EP0054588B1 (en) Interactive data retrieval apparatus
US5579515A (en) Method of checking index integrity in a DB2 database
US6446066B1 (en) Method and apparatus using run length encoding to evaluate a database
KR20010083096A (ko) 가치-사례-연결을 통한 컴퓨터에 의해 구현되는데이터베이스
US7039650B2 (en) System and method for making multiple databases appear as a single database
JPH08255176A (ja) データベースのテーブルを比較する方法及びシステム
CN100419746C (zh) 信息检索方法
US3402394A (en) Content addressable memory
US4332014A (en) Data retrieval system
US6778946B1 (en) Methods and apparatus for processing ranked fuzzy cartesian queries
EP0170443A2 (en) Method for searching an association matrix
CA2202217A1 (en) Method and apparatus for classifying raw data entries according to data patterns
JPH01219927A (ja) データベースの情報検索方式
JPH03137772A (ja) データベース利用システム
JPS633351A (ja) バツフア検索制御方式
JPH03108063A (ja) 後方一致検索方法および装置
JPH0312337B2 (ja)
JPS63147234A (ja) 論理型言語の節選択処理方式
JPH06124306A (ja) 同時出現性対応インデックス検索方式