JPH02212972A - データベース操作方法 - Google Patents
データベース操作方法Info
- Publication number
- JPH02212972A JPH02212972A JP1329400A JP32940089A JPH02212972A JP H02212972 A JPH02212972 A JP H02212972A JP 1329400 A JP1329400 A JP 1329400A JP 32940089 A JP32940089 A JP 32940089A JP H02212972 A JPH02212972 A JP H02212972A
- Authority
- JP
- Japan
- Prior art keywords
- data item
- data items
- index
- level
- data
- 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
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/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9027—Trees
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9017—Indexing; Data structures therefor; Storage structures using directory or table look-up
- G06F16/902—Indexing; Data structures therefor; Storage structures using directory or table look-up using more than one table in sequence, i.e. systems with three or more layers
-
- 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)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (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
【発明の詳細な説明】
〔発明の技術分野〕
本発明は一般にデータベースシステムに関するものであ
り、とりわけ、再帰的に導出されるデータ項目（ｄａｔ
ｓ ｉｔｅｍ）に関するデータベース構造、及びこうし
たデータ項目をデータベース中に配置する方法に関する
ものである。
り、とりわけ、再帰的に導出されるデータ項目（ｄａｔ
ｓ ｉｔｅｍ）に関するデータベース構造、及びこうし
たデータ項目をデータベース中に配置する方法に関する
ものである。
データベース・システムは益々多種多様となるデータを
記憶し管理するために用いられている。
記憶し管理するために用いられている。
データベース・システムの利用が拡大し、データベース
に記憶されるデータの量が増すにつれて、既存のデータ
ベースシステムを改良しまた、新規でより優れた能力を
備えた新システムを開発するために、多大の努力が傾注
されてきた。
に記憶されるデータの量が増すにつれて、既存のデータ
ベースシステムを改良しまた、新規でより優れた能力を
備えた新システムを開発するために、多大の努力が傾注
されてきた。
データベースへ“問い合わせ” （ｑｕｅｒいるとは、
データベースに対して情報を要求することを意味する。
データベースに対して情報を要求することを意味する。
要求された情報は、データベースに記憶された項目を直
接検索することによって得ることもあるし、あるいはデ
ータベースに記憶されたデー夕項目から導き出されるこ
ともある。
接検索することによって得ることもあるし、あるいはデ
ータベースに記憶されたデー夕項目から導き出されるこ
ともある。
近年いっそう重要になってきたデータベースに対する問
合せのタイプは、再帰的に情報を導き出す間合せである
。こうした間合せは、自分自身を繰返して問合せを行な
う間合せと表現することができる。情報を再帰的に導き
出すには、データベース内におけるデータ項目間の再帰
的なりレーシゴンを評価する必要がある。再帰の数字的
概念に関する一般的な論考については、１９８８年Ａｄ
ｄｉｓｏｎ−Ｉｇｌｅｙ社刊のＪ、Ｂｒａｄｌｅｙによ
るｒｎｔｒｏｄａｅｔｆｏｎ ｔ。
合せのタイプは、再帰的に情報を導き出す間合せである
。こうした間合せは、自分自身を繰返して問合せを行な
う間合せと表現することができる。情報を再帰的に導き
出すには、データベース内におけるデータ項目間の再帰
的なりレーシゴンを評価する必要がある。再帰の数字的
概念に関する一般的な論考については、１９８８年Ａｄ
ｄｉｓｏｎ−Ｉｇｌｅｙ社刊のＪ、Ｂｒａｄｌｅｙによ
るｒｎｔｒｏｄａｅｔｆｏｎ ｔ。
Ｄ−ｉｓｃｒｅｔｅ Ｍａｔｈｅｍａｔｉｃｓ第６章に
ある。また、１９Ｂ６年Ｊｏｈｎ Ｎｉｌｅｙ社刊のｆ
Ｅ、ＲｏｂｅｒｔｓによるＴｈｉｒｉｋｉｎｇＰＳ、ｅ
ｃｕｒｓｉｖｅｌｙも参照のこと。
ある。また、１９Ｂ６年Ｊｏｈｎ Ｎｉｌｅｙ社刊のｆ
Ｅ、ＲｏｂｅｒｔｓによるＴｈｉｒｉｋｉｎｇＰＳ、ｅ
ｃｕｒｓｉｖｅｌｙも参照のこと。
例えば、あるデータベースに１組のデータ項目が収めら
れていて、各データ項目は親子関係を表わしているもの
と仮定する。こうしたデータベース項目のいくつかは以
下のようになるだろう：Ｂ−ｉ１１は、Ｒｉｅｈａｒｄ
の父である； Ａｂｉｇａｔｌは、Ｒ３ｃ−ｈａｒｄの
母である； Ｒｉｃｈａｒｄは、Ｍａｒｙの父である；
Ｊａｎｅは、Ｍａｒｙの母である； Ｊｏｈｎは、Ａｎ
ｄｒａｗの父である；阿ａｒｙは、Ａｎｄｒｅ−の母で
ある；・・・、また、°“ＦχＩＮＤ ＰＡＲＥＮＴＳ
ＯＦ （Ｘ） ’の形式の照会によって、ある人
物の親の名前が戻イ直として得られると仮定する。なお
、ここで、Ｘはその親の名前を見出すべき人物の前２で
ある。ある人物の親の名は、この特定のデータベースの
データ項目を検索することによって直接得られる種類の
情報の一例である。
れていて、各データ項目は親子関係を表わしているもの
と仮定する。こうしたデータベース項目のいくつかは以
下のようになるだろう：Ｂ−ｉ１１は、Ｒｉｅｈａｒｄ
の父である； Ａｂｉｇａｔｌは、Ｒ３ｃ−ｈａｒｄの
母である； Ｒｉｃｈａｒｄは、Ｍａｒｙの父である；
Ｊａｎｅは、Ｍａｒｙの母である； Ｊｏｈｎは、Ａｎ
ｄｒａｗの父である；阿ａｒｙは、Ａｎｄｒｅ−の母で
ある；・・・、また、°“ＦχＩＮＤ ＰＡＲＥＮＴＳ
ＯＦ （Ｘ） ’の形式の照会によって、ある人
物の親の名前が戻イ直として得られると仮定する。なお
、ここで、Ｘはその親の名前を見出すべき人物の前２で
ある。ある人物の親の名は、この特定のデータベースの
データ項目を検索することによって直接得られる種類の
情報の一例である。
上の例について議論を続ければ、ここで注目されるのは
、データベースには祖父母に関する情報が含まれないと
いう点である。しかしながら、こうした情報は例えば、
”ＦＩＮＤ ＰＡＲＥＮＴＳ ＯＦ ＣＦ−ＩＮ
Ｄ ＰＡＲＥＮＴＳ ＯＦ （Ｘ）、１’ トイ−５形
式（７）間合セニヨって、データベース中の情報から再
帰的に導き出せるのは明らかである。要求された情報を
こうした間合せによって提供することが、祖父母と孫の
再帰的なりレーションを評価するということを意味する
。
、データベースには祖父母に関する情報が含まれないと
いう点である。しかしながら、こうした情報は例えば、
”ＦＩＮＤ ＰＡＲＥＮＴＳ ＯＦ ＣＦ−ＩＮ
Ｄ ＰＡＲＥＮＴＳ ＯＦ （Ｘ）、１’ トイ−５形
式（７）間合セニヨって、データベース中の情報から再
帰的に導き出せるのは明らかである。要求された情報を
こうした間合せによって提供することが、祖父母と孫の
再帰的なりレーションを評価するということを意味する
。
さらに複雑な要求の一例は、ＸとＹに共通の祖父母を見
つけよという要求である。これに答えるには、２つの再
帰的リレシータンについて評価しなければならないし、
これら２つの評価の結果はさらに一致を見い出すために
比較しなければならない、これら２つの再帰的リレシー
ジンは互いに再帰的なリレーションと呼ばれる。
つけよという要求である。これに答えるには、２つの再
帰的リレシータンについて評価しなければならないし、
これら２つの評価の結果はさらに一致を見い出すために
比較しなければならない、これら２つの再帰的リレシー
ジンは互いに再帰的なリレーションと呼ばれる。
最近のデータベースのデータ項目によって表わされるリ
レーションは、上の例に比べてはるかに複雑な場合がよ
くある０例えば、定期旅客機のフライトと一対の都市と
のりレージ５ンには、出発時間と到着時間、食事のサー
ビス、利用できる客席数、他の都市への乗り継ぎサービ
ス、料金等も当然含まれるだろう０乗客の要求を満たす
旅行計画を作成するには、相互に関連したいくつかの再
帰的リレーションを評価しなければならない。
レーションは、上の例に比べてはるかに複雑な場合がよ
くある０例えば、定期旅客機のフライトと一対の都市と
のりレージ５ンには、出発時間と到着時間、食事のサー
ビス、利用できる客席数、他の都市への乗り継ぎサービ
ス、料金等も当然含まれるだろう０乗客の要求を満たす
旅行計画を作成するには、相互に関連したいくつかの再
帰的リレーションを評価しなければならない。
再帰的リレーションを評価するのに必要な繰返し数が前
もって分っている場合、そのリレーションの評価は比較
的容易である０例えば、Ｘの祖父母を見つけよという要
求の場合、ちょうど２回の繰返しが必要である。つまり
、１回はＸの両親を見つけ、また１回は、Ｘの両親の両
親を見つける、一方、繰返し数が分らない場合には、そ
の評価ははるかに困難になる。繰返し数の分らない要求
の例としては、Ｘの先祖を全て見つけよという要求があ
る。
もって分っている場合、そのリレーションの評価は比較
的容易である０例えば、Ｘの祖父母を見つけよという要
求の場合、ちょうど２回の繰返しが必要である。つまり
、１回はＸの両親を見つけ、また１回は、Ｘの両親の両
親を見つける、一方、繰返し数が分らない場合には、そ
の評価ははるかに困難になる。繰返し数の分らない要求
の例としては、Ｘの先祖を全て見つけよという要求があ
る。
データベースにおけるデータ量が増すにつれ、またデー
タによって表わされるリレーションの性質が複雑になる
につれて、極めて強力なコンピュータでさえ、複雑な間
合せに応答するのに必要とされる時間は許容できないほ
どに長くなる可能性がある。とりわけ応答を導き出すの
に必要な繰返し数が前もって分らない場合にはそうなる
可能性が高い、従って、再帰的リレーション、とりわけ
、互いに再帰的なリレーションの集合の効率的な評価は
、最近のデータベースシステムの設計において極めて重
大な問題になってきた。この問題の包括的なサーベイは
、１９８６年５月、 Ｗａｓｈｉｎｇｔｏｎ、Ｄ、Ｃ。
タによって表わされるリレーションの性質が複雑になる
につれて、極めて強力なコンピュータでさえ、複雑な間
合せに応答するのに必要とされる時間は許容できないほ
どに長くなる可能性がある。とりわけ応答を導き出すの
に必要な繰返し数が前もって分らない場合にはそうなる
可能性が高い、従って、再帰的リレーション、とりわけ
、互いに再帰的なリレーションの集合の効率的な評価は
、最近のデータベースシステムの設計において極めて重
大な問題になってきた。この問題の包括的なサーベイは
、１９８６年５月、 Ｗａｓｈｉｎｇｔｏｎ、Ｄ、Ｃ。
のＰｒｏｃｅａｄｉｎｇｓ ｏｆ ｔｂｅ ＡＣＭ−５
ＩＧＭＯｎｃｏｎｆｅｒｅｎｃｅ中のＦ、Ｂａｎｃｉｌ
ｂｏｎ とＲ，Ｒａｍａｋｒｉｓｈｎａｎによる“′＾
ｎ Ａｗ＋忙 ａｔｅｕｙ’ｓ Ｉｎｔｒｏｄｕｃｔｉｏｒｉ ｔｏ
Ｒｅｃｕｒｓｆｖｅ Ｑｕｅｒｙ Ｐｒｏ−ｃｅｓｓｉ
ｎｇ Ｓｔｒａｔｓｇｉｅｓ”に発表されている。
ＩＧＭＯｎｃｏｎｆｅｒｅｎｃｅ中のＦ、Ｂａｎｃｉｌ
ｂｏｎ とＲ，Ｒａｍａｋｒｉｓｈｎａｎによる“′＾
ｎ Ａｗ＋忙 ａｔｅｕｙ’ｓ Ｉｎｔｒｏｄｕｃｔｉｏｒｉ ｔｏ
Ｒｅｃｕｒｓｆｖｅ Ｑｕｅｒｙ Ｐｒｏ−ｃｅｓｓｉ
ｎｇ Ｓｔｒａｔｓｇｉｅｓ”に発表されている。
総称的に°″関係代数”と呼ばれる１組の数学的演算子
が、データベース中のデータ項目に対する操作のために
開発された（一般には、１９８６年、Ａ−ｄｄｉｓｏｎ
−Ｗｅｓｌｅｙ社刊のＣ，Ｊ、ＤａｔｅによるＡｒ＋
Ｉｒ１ｔｒｏｄ−ｕｅｔｉｏｎ ｔｏ Ｄａｔａｔ＋ａ
ｓｅ ５ｙｓｔｃｖｓ （第４版）第１巻第１３章参照
のこと）、関係代数は多くの利点をもたらすものであり
、最近のデータシステムの設計において広く用いられて
いるが、関係代数には再帰的リレーションを評価する能
力がない。
が、データベース中のデータ項目に対する操作のために
開発された（一般には、１９８６年、Ａ−ｄｄｉｓｏｎ
−Ｗｅｓｌｅｙ社刊のＣ，Ｊ、ＤａｔｅによるＡｒ＋
Ｉｒ１ｔｒｏｄ−ｕｅｔｉｏｎ ｔｏ Ｄａｔａｔ＋ａ
ｓｅ ５ｙｓｔｃｖｓ （第４版）第１巻第１３章参照
のこと）、関係代数は多くの利点をもたらすものであり
、最近のデータシステムの設計において広く用いられて
いるが、関係代数には再帰的リレーションを評価する能
力がない。
推移的閉包演算子（ｔｒａｎｓｉｔｉｖｅ ｃｌｏｓｕ
ｒｅ ｏｐｅｒ−ａｔｏｒｓ）といった新しい演算子が
関係代数に帰納的関数の評価能力を付与するために提案
されている（１９８７年２月３〜５日、カリフォルニア
州ロサンジエルスでのＰｒｏｃｅｅｄｉｎｇｓ ｏｆ
Ｔｈ１ｒｄ Ｉｒ１ｔｅｒｎａｔｉ。
ｒｅ ｏｐｅｒ−ａｔｏｒｓ）といった新しい演算子が
関係代数に帰納的関数の評価能力を付与するために提案
されている（１９８７年２月３〜５日、カリフォルニア
州ロサンジエルスでのＰｒｏｃｅｅｄｉｎｇｓ ｏｆ
Ｔｈ１ｒｄ Ｉｒ１ｔｅｒｎａｔｉ。
ｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎ
ｇｉｎｅｅｒｉｎｇ中のＲ，Ａｇｒ−ａｗｌによる“Ａ
ｌｐｈａ：Ａｎ Ｅｘｔｅｎｓｆｆｉｏｒ＋ ｏｆ Ｒ
ｅｌａｔｉｏｎａｌＡｌｇｅｂｒａ ｔｏ Ｅｘｐｒｅ
ｓｓ ａ （：１ａｓｓ ｏｆ ＲｅｃｕｒｓｉｖｅＱ
ｕｅｒｉｅｓ ； １９８６年８月、京都でのＰｒ
ｏｃｅｅｄｉｎｇｓｏｆ ｔｈｅ Ｅｌｅｖｅｎｔｈ
Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ
ｏｎνｅｒχｙ Ｌａｒｇｅ Ｄａｔａ Ｂａ５ｅｓ中
のＳ 、 Ｃｅｒ ｉ他による’Ｔｒａｎｓ、４１ａｔ
ｉｏｎ ａｎａ ０ｐｔｉａｉｔｚａｔｔｏｎ ｏｆ
ＬｏｇｉｃＱｕｅｒｉｅｓ：ｔｈｅ Ａｌｇｅｂｒａｉ
ｃ Ａｐｐｒｏａｃｈ’ ）。
ｇｉｎｅｅｒｉｎｇ中のＲ，Ａｇｒ−ａｗｌによる“Ａ
ｌｐｈａ：Ａｎ Ｅｘｔｅｎｓｆｆｉｏｒ＋ ｏｆ Ｒ
ｅｌａｔｉｏｎａｌＡｌｇｅｂｒａ ｔｏ Ｅｘｐｒｅ
ｓｓ ａ （：１ａｓｓ ｏｆ ＲｅｃｕｒｓｉｖｅＱ
ｕｅｒｉｅｓ ； １９８６年８月、京都でのＰｒ
ｏｃｅｅｄｉｎｇｓｏｆ ｔｈｅ Ｅｌｅｖｅｎｔｈ
Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ
ｏｎνｅｒχｙ Ｌａｒｇｅ Ｄａｔａ Ｂａ５ｅｓ中
のＳ 、 Ｃｅｒ ｉ他による’Ｔｒａｎｓ、４１ａｔ
ｉｏｎ ａｎａ ０ｐｔｉａｉｔｚａｔｔｏｎ ｏｆ
ＬｏｇｉｃＱｕｅｒｉｅｓ：ｔｈｅ Ａｌｇｅｂｒａｉ
ｃ Ａｐｐｒｏａｃｈ’ ）。
こうした演算子を用いて、再帰的リレーションｒを評価
するには、 ｒ−ｆ （ｒ） （１）の形
式の再帰的方程式の“最小不動点” （１ｅａｓ ｔｆ
ｆｘｐｏｉｎｔ）を求める必要がある。ここでｆは以下
の段落中で定義される関数である。再帰的リレーション
ｒの最小不動点は下記の判定基準を満たすリレーション
ｒ０として定義される： ｒ” ＝ｆ （ｒ” ） （２）
及び 式ｐ＝ｆ （ｐ）を満たす任意のｐについてｒ“ＣＰ、
（３）１９７９年のＰｒ
ｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｉｘｔｈ ＰＯ
ＰＬ中の＾、Ａｈｏ他によるＵｎｉｖｅｒｓａｌｉｔｙ
ｏｆ Ｄａｔａ Ｒｅｔｒｉｅｖａｌ Ｌａｎｇｕａ
ｇｅｓ″参照のこと。
するには、 ｒ−ｆ （ｒ） （１）の形
式の再帰的方程式の“最小不動点” （１ｅａｓ ｔｆ
ｆｘｐｏｉｎｔ）を求める必要がある。ここでｆは以下
の段落中で定義される関数である。再帰的リレーション
ｒの最小不動点は下記の判定基準を満たすリレーション
ｒ０として定義される： ｒ” ＝ｆ （ｒ” ） （２）
及び 式ｐ＝ｆ （ｐ）を満たす任意のｐについてｒ“ＣＰ、
（３）１９７９年のＰｒ
ｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｉｘｔｈ ＰＯ
ＰＬ中の＾、Ａｈｏ他によるＵｎｉｖｅｒｓａｌｉｔｙ
ｏｆ Ｄａｔａ Ｒｅｔｒｉｅｖａｌ Ｌａｎｇｕａ
ｇｅｓ″参照のこと。
全ての再帰方程式が最小不動点を持つわけではないが、
リレーションｆが単調であれば、その式は最小不動点を
持つことが保証される。ｌ！！係代数演算子だけからな
る関数は単調であり、従って関係代数演算子だけからな
る再帰的方程式は最小不動点を持っている。一般には、
１９５５年６月のＰａｃ−ｉｆｉｃ Ｊｏｕｒｎａｌ
ｏｆ Ｍａｔｈｅｍａｔｔｃｓ第５巻第２号２８５〜３
０９頁に掲載されたＡ、Ｔａｒｓｋ ：による“Ａ
Ｌａｔ−ｔｉｃｅ−Ｔｈｅｏｒｅｔｉｃａｌ Ｆｉｘｐ
ｏｉｎｔ Ｔｈｅｏｒｅｓ＋ ａｎｄ ｉｔｓ Ａ−ｐ
ｐｌｉｃａｔｉｏｎｓ ’を参照のこと。
リレーションｆが単調であれば、その式は最小不動点を
持つことが保証される。ｌ！！係代数演算子だけからな
る関数は単調であり、従って関係代数演算子だけからな
る再帰的方程式は最小不動点を持っている。一般には、
１９５５年６月のＰａｃ−ｉｆｉｃ Ｊｏｕｒｎａｌ
ｏｆ Ｍａｔｈｅｍａｔｔｃｓ第５巻第２号２８５〜３
０９頁に掲載されたＡ、Ｔａｒｓｋ ：による“Ａ
Ｌａｔ−ｔｉｃｅ−Ｔｈｅｏｒｅｔｉｃａｌ Ｆｉｘｐ
ｏｉｎｔ Ｔｈｅｏｒｅｓ＋ ａｎｄ ｉｔｓ Ａ−ｐ
ｐｌｉｃａｔｉｏｎｓ ’を参照のこと。
一対の互いに再帰的なりレーションｒ、及びｒ。
を評価するには、下記の再帰的関係代数式の最小不動点
を求めることが必要になる： ｒｉ −ｒＩ （ｒＩ 、ｒｔ ） （
４）及び ｒｚ ＝ｒｚ （ｒＩ 、ｒｚ ） （
５）さらに−船釣には、互いに再帰的なｎ個の関係式ｒ
、〜ｒ１の組の評価には ｒ、−５，（ｒい・・・・・・ｒｎ） （６）
幹 の形式の１組の再帰的方程式について最小不動点を求め
る必要がある。
を求めることが必要になる： ｒｉ −ｒＩ （ｒＩ 、ｒｔ ） （
４）及び ｒｚ ＝ｒｚ （ｒＩ 、ｒｚ ） （
５）さらに−船釣には、互いに再帰的なｎ個の関係式ｒ
、〜ｒ１の組の評価には ｒ、−５，（ｒい・・・・・・ｒｎ） （６）
幹 の形式の１組の再帰的方程式について最小不動点を求め
る必要がある。
関数ｆｆ は再帰的リレーションの定義を使って定義
される０例えば、２つの互いに再帰的なリレーションｒ
ｌ及びｒオは、下記のＨｏｒｎｊｌＹによって定義され
る： ｒＩ ｃｘ、Ｙ）←ｂ＋ （Ｘ、Ｚ）、ｒｔ （
Ｚ、Ｙ） （７） ｒｚ ｃｘ、Ｙ）”ｒＩ （Ｘ、Ｚ）、ｂよ （ＺＳ
Ｙ） （８） ｒｌ （Ｘ、Ｙ） ←ｌ）、ｃｘ、Ｙ） （９
）ここでｂ１〜ｂ、は基底リレーション（ｂａｓｅ ｒ
ｅ−１ａｔｉｏｎ）であり、ＸＳＹ、、Ｚは基底リレー
ション中のカラムである。関数ｒ、及びｆ２は従って以
下のように与えられる： ｆ＋ （ｒＩ 、ｒｚ ）＝ｂ３ＬＪｂ＋ ０ｒｚ
ｒｔ （ｒＩ 、ｒｘ ）＝ｒ＋ ｏｂｚ
（１１）によって求められる。ここで上式中の演算子０
は合成演算子（ｃｏｍｐｏｓｉｔｉｏｎ ｏｐｅｒａｔ
ｏｒ）である、これは結合（ｊｏｆｎ）の次にターゲッ
ト・リスト中のアトリビュートへの射影（ｐｒｏｊｅｅ
ｔｉｏｎ）を行なう個の互いに再帰的なりレージジンｒ
ｉ を使って以前のように定義される： ｒｌ、 ＝Ｊ ’ Ｕｂｌ Ｏｒｌ Ｏｒｚ ”’Ｏ
ｒｓここで、ｂ、 ｏ 、ｂ、 ｏのうちのいくつか
は空の可能性があるが、計算の終了を保証するため、少
なくともその１つは非空でなければならない。ｂｉのい
くつかは、１つまたは複数以上の他のｂｊから得られる
中間的なりレージジンの可能性がある。
される０例えば、２つの互いに再帰的なリレーションｒ
ｌ及びｒオは、下記のＨｏｒｎｊｌＹによって定義され
る： ｒＩ ｃｘ、Ｙ）←ｂ＋ （Ｘ、Ｚ）、ｒｔ （
Ｚ、Ｙ） （７） ｒｚ ｃｘ、Ｙ）”ｒＩ （Ｘ、Ｚ）、ｂよ （ＺＳ
Ｙ） （８） ｒｌ （Ｘ、Ｙ） ←ｌ）、ｃｘ、Ｙ） （９
）ここでｂ１〜ｂ、は基底リレーション（ｂａｓｅ ｒ
ｅ−１ａｔｉｏｎ）であり、ＸＳＹ、、Ｚは基底リレー
ション中のカラムである。関数ｒ、及びｆ２は従って以
下のように与えられる： ｆ＋ （ｒＩ 、ｒｚ ）＝ｂ３ＬＪｂ＋ ０ｒｚ
ｒｔ （ｒＩ 、ｒｘ ）＝ｒ＋ ｏｂｚ
（１１）によって求められる。ここで上式中の演算子０
は合成演算子（ｃｏｍｐｏｓｉｔｉｏｎ ｏｐｅｒａｔ
ｏｒ）である、これは結合（ｊｏｆｎ）の次にターゲッ
ト・リスト中のアトリビュートへの射影（ｐｒｏｊｅｅ
ｔｉｏｎ）を行なう個の互いに再帰的なりレージジンｒ
ｉ を使って以前のように定義される： ｒｌ、 ＝Ｊ ’ Ｕｂｌ Ｏｒｌ Ｏｒｚ ”’Ｏ
ｒｓここで、ｂ、 ｏ 、ｂ、 ｏのうちのいくつか
は空の可能性があるが、計算の終了を保証するため、少
なくともその１つは非空でなければならない。ｂｉのい
くつかは、１つまたは複数以上の他のｂｊから得られる
中間的なりレージジンの可能性がある。
データベース環境中の再帰的方程式の最小不動点を計算
するさまざまな方法がある。これらの１つである、セミ
ナイーブ法（ｓｅｍｉ−ｎａｉｖｅ ｓ＋ｅｔｈｏｄ）
は、適切な最適化技法と共に利用すると良好な性能が得
られる。これについては以下参照されたい：既出のＦ、
Ｂａｒｌｃｉｌｈｏｎ他； １９８５年Ｓｐｒｉｎｇｅ
ｒ−Ｖｅｒｌａｇ社から出版されたＢｒｏｄｉ’ｌｅ及
びＭｙｌｏｐｏｕｌｏｓ （ｔＪｉ集者）によるＯｎ
Ｋｎｏｗｌｅｄｇｅ Ｂａ５ｅｄ ｌｌａｎａｇｅｍｅ
ｎｔ Ｓｙｓｔｅｍｓ４ｎｔｅｇｒａｔｉｎｇ Ｄａｔ
ａｂａｓｅ ａｎｄ ＡＮ ＳｙｓｔｅｍにおけるＦ、
１１ａｎｃｉｌｈｏｎの”Ｎａ１ｖｅ Ｅｖａｌｕａ目
ｏｎ ｏｆ Ｒｅｃｕｒｓｉｖｅ′１１ｙ Ｄｅｆｉｒ
＋ｅｄ Ｒｅ１ａｔｉｏｎｓ最小不動点を計算するセミ
ナイーブ法は繰返しを行なう方法である。再帰的リレー
シツンｒ及び対応する再帰的方程式ｒ＝ｆ （ｒ）につ
いて、セミナイーブ法では、以下に示すようにこの式の
満たすｒの新しい値を繰返し計算して、それをｒに追加
する。この繰返しはｒの新しい値を見つけることができ
なくなるまで、行なわれる：「０ ニーφ；
（１３）δ、６．＝ｙ（φ） ：
（１４）ｊ：＝０：
（１５）ｉ＋１ｈｉｌｅ （δｒＪ≠φ
）ｄ。
するさまざまな方法がある。これらの１つである、セミ
ナイーブ法（ｓｅｍｉ−ｎａｉｖｅ ｓ＋ｅｔｈｏｄ）
は、適切な最適化技法と共に利用すると良好な性能が得
られる。これについては以下参照されたい：既出のＦ、
Ｂａｒｌｃｉｌｈｏｎ他； １９８５年Ｓｐｒｉｎｇｅ
ｒ−Ｖｅｒｌａｇ社から出版されたＢｒｏｄｉ’ｌｅ及
びＭｙｌｏｐｏｕｌｏｓ （ｔＪｉ集者）によるＯｎ
Ｋｎｏｗｌｅｄｇｅ Ｂａ５ｅｄ ｌｌａｎａｇｅｍｅ
ｎｔ Ｓｙｓｔｅｍｓ４ｎｔｅｇｒａｔｉｎｇ Ｄａｔ
ａｂａｓｅ ａｎｄ ＡＮ ＳｙｓｔｅｍにおけるＦ、
１１ａｎｃｉｌｈｏｎの”Ｎａ１ｖｅ Ｅｖａｌｕａ目
ｏｎ ｏｆ Ｒｅｃｕｒｓｉｖｅ′１１ｙ Ｄｅｆｉｒ
＋ｅｄ Ｒｅ１ａｔｉｏｎｓ最小不動点を計算するセミ
ナイーブ法は繰返しを行なう方法である。再帰的リレー
シツンｒ及び対応する再帰的方程式ｒ＝ｆ （ｒ）につ
いて、セミナイーブ法では、以下に示すようにこの式の
満たすｒの新しい値を繰返し計算して、それをｒに追加
する。この繰返しはｒの新しい値を見つけることができ
なくなるまで、行なわれる：「０ ニーφ；
（１３）δ、６．＝ｙ（φ） ：
（１４）ｊ：＝０：
（１５）ｉ＋１ｈｉｌｅ （δｒＪ≠φ
）ｄ。
ｅｇｉｎ
ｒ Ｊ ” Ｉ ： ；ｒ ｊ Ｕδｆ−’ ；
（１６）δ ｒノ゛’ ：＝ｆ （ｒ
’″’）−１（ｒ’）；ｊ：＝Ｊ＋１；
（１８）ａｎｄ Ｈ ここで、δｒはｒの新しい値、φは空集合、ｊは繰返変
数である。
（１６）δ ｒノ゛’ ：＝ｆ （ｒ
’″’）−１（ｒ’）；ｊ：＝Ｊ＋１；
（１８）ａｎｄ Ｈ ここで、δｒはｒの新しい値、φは空集合、ｊは繰返変
数である。
ｎ個の互いに再帰的なりレージぢンｒＪ からなる集
合の最小不動点を求めるため、式（６）の形をとる互い
に再帰的な１組の式を下記のようにまとめて評価しなけ
ればならない： ｆｏｒ各ｒＨｄ。
合の最小不動点を求めるため、式（６）の形をとる互い
に再帰的な１組の式を下記のようにまとめて評価しなけ
ればならない： ｆｏｒ各ｒＨｄ。
ｒ−二＝φ； （１９）ｆｏｒ各
ｒ−ｄ。
ｒ−ｄ。
δｒ＋’＝ｆｉ（φ） ； （２０）ｊ
：＝０； （２ｍ）ｗｈｉ
ｌｅ （成るδｒ１）≠φ）ｄＯｅｇｉｎ ｒ！ｊ″’ ：Ｗｒｉ ’ （Ｊ６ｒｉ’ （
２２）δｒ１ｊ″） ： ＝ｆ 、 （ｒ 、 ｊ
″−＋＋、ｊ、’゛すｈ （ｒｔ Ｊ 、 ・ｌ
ｒｉ ’ ） ｉ （２３）ｊ：＝ｊ＋１；
（２４）ｅｎｄ ； ｎ個の互いに再帰的な１組のりレージジンの最小不動点
を求め′る差分的（ｄｔｆｆｅｒｅｎｔｆａｌ）アプロ
ーチも提案されている（オーストラリア、メルボＪレン
大学、Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ
５ｃｉｅｎｃｅのＴｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ
８６／７に掲載された、１．Ｂａ１ｂｉｎ他によるＡ
［）ｆｆｆｅｒｅｒｉｔｉａｌ Ａｐｐｒｏａｃｈ
ｔｏ Ｑｕｅｒｙ Ｑｐｔｆｍｉｚａｔｉｏｎ ｉｎ
ａ Ｒｅｃｕｒｓｉｖｅ Ｄｅｄｕｃｔｉｖｅ Ｄａ
ｔａｂａ−ｓｅ”）。このアプローチは以下のように記
述される： げ初期設定 ”） ｆｏｒ各再帰的リレすションｒ５ｄ。
：＝０； （２ｍ）ｗｈｉ
ｌｅ （成るδｒ１）≠φ）ｄＯｅｇｉｎ ｒ！ｊ″’ ：Ｗｒｉ ’ （Ｊ６ｒｉ’ （
２２）δｒ１ｊ″） ： ＝ｆ 、 （ｒ 、 ｊ
″−＋＋、ｊ、’゛すｈ （ｒｔ Ｊ 、 ・ｌ
ｒｉ ’ ） ｉ （２３）ｊ：＝ｊ＋１；
（２４）ｅｎｄ ； ｎ個の互いに再帰的な１組のりレージジンの最小不動点
を求め′る差分的（ｄｔｆｆｅｒｅｎｔｆａｌ）アプロ
ーチも提案されている（オーストラリア、メルボＪレン
大学、Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ
５ｃｉｅｎｃｅのＴｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ
８６／７に掲載された、１．Ｂａ１ｂｉｎ他によるＡ
［）ｆｆｆｅｒｅｒｉｔｉａｌ Ａｐｐｒｏａｃｈ
ｔｏ Ｑｕｅｒｙ Ｑｐｔｆｍｉｚａｔｉｏｎ ｉｎ
ａ Ｒｅｃｕｒｓｉｖｅ Ｄｅｄｕｃｔｉｖｅ Ｄａ
ｔａｂａ−ｓｅ”）。このアプローチは以下のように記
述される： げ初期設定 ”） ｆｏｒ各再帰的リレすションｒ５ｄ。
ｅｇｉｎ
ｒ五Ｃ′＝＝φ： （２５）δｒ
ｉ ＠ ： −ｂ＠ｉ ： （２６
）ｏｒｉｄ ； ぴ繰返し６） Ｊニー０： （２７）ｅｐ
ｅａｔ ｆｏｒ各再帰的γリレーシゴンｒｌｄ。
ｉ ＠ ： −ｂ＠ｉ ： （２６
）ｏｒｉｄ ； ぴ繰返し６） Ｊニー０： （２７）ｅｐ
ｅａｔ ｆｏｒ各再帰的γリレーシゴンｒｌｄ。
ｅｇｉｎ
ｊニーｊ＋１； （２８）ｒ 、
ｊ ： ＝ｒ 、 ｊ−ｔ＋δｒ五’−’； （２９
）Δ ？ｉ ’ ニーｂｌ ｏ （δ
ｒｌ ’−’ Ｏｒ２ ’。
ｊ ： ＝ｒ 、 ｊ−ｔ＋δｒ五’−’； （２９
）Δ ？ｉ ’ ニーｂｌ ｏ （δ
ｒｌ ’−’ Ｏｒ２ ’。
＋′ Ｏｒ、１
Ｕｒ、トＩ ｏδｒ 、 Ｊ −ｒ
ｏｒコｊ Ｏ・・ｏｒ、’
Ｕ・・・
Ｕ ｒ、 ｊ−１ｏｒ、 ｊ−１
ｏ ｒｓ ’−’ ｏ−ｏ ６ ｒ、 ’−’ ）
；δ ｒ、ｊ： ＝Δ ｒｔ ’ −ｒｔ
’ ； （３１）ｎｄ ｕｎｔｉ】全でのδｒ１ノ＝φ これ迄に説明した最小不動点を求める方法は、データベ
ース環境では、別個のアプリケージタン・プログラムで
インプリメントされていた。
；δ ｒ、ｊ： ＝Δ ｒｔ ’ −ｒｔ
’ ； （３１）ｎｄ ｕｎｔｉ】全でのδｒ１ノ＝φ これ迄に説明した最小不動点を求める方法は、データベ
ース環境では、別個のアプリケージタン・プログラムで
インプリメントされていた。
以上から明らかなように、とりわけ、そのリレーション
が互いに再帰的なリレーションである場合および前もっ
て繰返し回数が分らない場合別個のアプリケーション・
プログラムを必要としないでＸ最小不動点を直接計算す
るような手段によって、再帰的に導出されたデータ項目
を、再帰的リレーションの効率的な評価を可能にするや
り方で、データベース中に配置するためのデータ構造及
び方法が必要になる。
が互いに再帰的なリレーションである場合および前もっ
て繰返し回数が分らない場合別個のアプリケーション・
プログラムを必要としないでＸ最小不動点を直接計算す
るような手段によって、再帰的に導出されたデータ項目
を、再帰的リレーションの効率的な評価を可能にするや
り方で、データベース中に配置するためのデータ構造及
び方法が必要になる。
本発明は、最小不動点を直接計算するような手段によっ
て前もって繰返し数を知らなくても互いに再帰的なりレ
ージジンを極めて効率的に評価できるような再帰的に導
き出されたデータ項目のためのデータ構造およびこうし
たデータをデータベースに配置する方法を提供すること
を目的とする。
て前もって繰返し数を知らなくても互いに再帰的なりレ
ージジンを極めて効率的に評価できるような再帰的に導
き出されたデータ項目のためのデータ構造およびこうし
たデータをデータベースに配置する方法を提供すること
を目的とする。
本発明の望ましい実施例では、再帰的に導き出されたデ
ータ項目のためのデータベース構造には、データ項目が
そこから導き出された再帰的リレーションの各繰返し毎
に１つの、複数の階層的繰返しレベル；データ項目をイ
ンデクシングするためのインデクス構造；及び各繰返し
レベルに関連した各種データ項目をリンクさせるための
手段；が含まれる。
ータ項目のためのデータベース構造には、データ項目が
そこから導き出された再帰的リレーションの各繰返し毎
に１つの、複数の階層的繰返しレベル；データ項目をイ
ンデクシングするためのインデクス構造；及び各繰返し
レベルに関連した各種データ項目をリンクさせるための
手段；が含まれる。
インデクス構造には、複数の末端（ｌｅａｆ）ノードを
持ったシーケンス・セット、複数の非末端ノードを持つ
インデクス・セット、及び繰返しレベル・インデクスが
含まれている。シーケンスセットのノードは、インデク
ス・レベルの最低位に順々に配置される。各ノードは、
データ項目の１っへのポインタ、そのデータ項目を一意
的に識別すインデクス・セットのノードは階層的に配置
されていて、最低位レベルから上の複数のインデクス・
レベルを定義している。ここで各レベルのノードはそれ
よりも下のレベルに比べて少なくなっている。各ノード
は、シーケンス・セットのキーの全てを包含している。
持ったシーケンス・セット、複数の非末端ノードを持つ
インデクス・セット、及び繰返しレベル・インデクスが
含まれている。シーケンスセットのノードは、インデク
ス・レベルの最低位に順々に配置される。各ノードは、
データ項目の１っへのポインタ、そのデータ項目を一意
的に識別すインデクス・セットのノードは階層的に配置
されていて、最低位レベルから上の複数のインデクス・
レベルを定義している。ここで各レベルのノードはそれ
よりも下のレベルに比べて少なくなっている。各ノード
は、シーケンス・セットのキーの全てを包含している。
各ノードは、その範囲内での各キー値毎に、その範囲内
の前述のキー値を持つ次に低いレベルのノードに対する
アクセス経路を定義している。
の前述のキー値を持つ次に低いレベルのノードに対する
アクセス経路を定義している。
繰返しレベル・インデクスによって、各繰返しレベルと
そのレベルに関連したデータ項目との間の参照が得られ
る。
そのレベルに関連したデータ項目との間の参照が得られ
る。
実施例の１つでは、所与の繰返しレベルに関連した各デ
ータ項目が、そのレベルに関連したページに割り当てら
れ、当該のレベルのページがまとまって連鎖構造をとる
。別の実施例では、所与の繰返しレベルに関連した個々
のデータ項目が互いに大域的に連鎖構造をとる。
ータ項目が、そのレベルに関連したページに割り当てら
れ、当該のレベルのページがまとまって連鎖構造をとる
。別の実施例では、所与の繰返しレベルに関連した個々
のデータ項目が互いに大域的に連鎖構造をとる。
新しいデータ項目の挿入は以下のようにして行なわれる
：それと同じ繰返しレベルおよび最も近いキー値を有す
る既存のデータを見出し；見出されたこの既存のデータ
に隣接して新しい項目を挿入し；もしデータ項目同志が
大域的にリンクされている場合には同じ繰返しレベルを
持つ他のデータ項目に新しいデータ項目をリンクさせ；
インデクス・セットおよびシーケンス・セットを調整し
て、新しい項目へのサーチ経路を含ませるようにする。
：それと同じ繰返しレベルおよび最も近いキー値を有す
る既存のデータを見出し；見出されたこの既存のデータ
に隣接して新しい項目を挿入し；もしデータ項目同志が
大域的にリンクされている場合には同じ繰返しレベルを
持つ他のデータ項目に新しいデータ項目をリンクさせ；
インデクス・セットおよびシーケンス・セットを調整し
て、新しい項目へのサーチ経路を含ませるようにする。
新しいデータ項目が既存の項目と同じキー値を持ってい
る場合、新しい項目は好ましくは棄てられる。あるいは
、キー値が同じ場合、２つの項目を比較してそれらが同
一である場合に限りで新しい項目が廃棄される。再帰的
リレーションを評価する際、オーバーヘッドを最小限に
おさえて、これらのテストのうちのいずれかを行なうこ
とが可能であり、ある繰返しの間に導き出された全ての
データ項目が廃棄された場合には繰返しが打切られる。
る場合、新しい項目は好ましくは棄てられる。あるいは
、キー値が同じ場合、２つの項目を比較してそれらが同
一である場合に限りで新しい項目が廃棄される。再帰的
リレーションを評価する際、オーバーヘッドを最小限に
おさえて、これらのテストのうちのいずれかを行なうこ
とが可能であり、ある繰返しの間に導き出された全ての
データ項目が廃棄された場合には繰返しが打切られる。
従って、再帰的リレーションの評価に必要な繰返し数が
前もって分からない場合における繰返しをいつ打切るか
に関する効率的なテストが提供される。
前もって分からない場合における繰返しをいつ打切るか
に関する効率的なテストが提供される。
本発明に従って配置されたデータ項目の集合中から、指
定された範囲内の繰返しレベルを持つデータ項目をサー
チすることは、以下のようにして極めて効率的に行なう
ことができる：インデクス・セット中のアクセス経路を
たどってサーチ中の項目に対応する末端ノードに到り、
その繰返しレベルが指定された範囲内にある場合に限っ
てその項目を戻値とする。
定された範囲内の繰返しレベルを持つデータ項目をサー
チすることは、以下のようにして極めて効率的に行なう
ことができる：インデクス・セット中のアクセス経路を
たどってサーチ中の項目に対応する末端ノードに到り、
その繰返しレベルが指定された範囲内にある場合に限っ
てその項目を戻値とする。
以下のようにすることによって、効率的にデータを走査
して、指定された条件を満足しかつ指定された繰返しレ
ベルを有するデータ環を見出すことができる：繰返しレ
ベル索引を利用して指定された範囲内の繰返しレベルを
有する第１のデータでたどる。このやり方で走査を行な
うことによって、要求されたデータ項目がキー値の順序
に従って自動的にならべるられる。
して、指定された条件を満足しかつ指定された繰返しレ
ベルを有するデータ環を見出すことができる：繰返しレ
ベル索引を利用して指定された範囲内の繰返しレベルを
有する第１のデータでたどる。このやり方で走査を行な
うことによって、要求されたデータ項目がキー値の順序
に従って自動的にならべるられる。
入れ子ループ結合（ｎｅｓｔｅｄ １ｏｏｐ ｊｏｉｎ
）は以下のようにして容易に実行できる：指定された繰
返この走査時に見つけたデータ項目の各々について、指
定された繰返しレベルにあるデータ項目の第２の集合を
サーチして突合せを行ない；走査時に見つけた各項目と
、サーチ時に見つけたそれに対応する項目とを結合する
。
）は以下のようにして容易に実行できる：指定された繰
返この走査時に見つけたデータ項目の各々について、指
定された繰返しレベルにあるデータ項目の第２の集合を
サーチして突合せを行ない；走査時に見つけた各項目と
、サーチ時に見つけたそれに対応する項目とを結合する
。
同様にして、併合走査結合（ｍｅｒｇｅ ５ｃａｎ ｊ
ｏｉｒｉ）を以下のようにして行なうことができる：第
１の繰返しレベルにあるデータ項目の第１の集合と第２
の繰返しレベルにあるデータ項目の第２の集合を同時に
走査し；第１の走査で見つけたデータ項目と第２の走査
で見つけたマツチする項目を結合する。
ｏｉｒｉ）を以下のようにして行なうことができる：第
１の繰返しレベルにあるデータ項目の第１の集合と第２
の繰返しレベルにあるデータ項目の第２の集合を同時に
走査し；第１の走査で見つけたデータ項目と第２の走査
で見つけたマツチする項目を結合する。
本発明の他の態様及び利点については、本発明の原理を
例示した添付の図面に関連して行なう以下の詳細説明か
ら明らかになるだろう。
例示した添付の図面に関連して行なう以下の詳細説明か
ら明らかになるだろう。
〔発明の詳細な
説明用の図面に示すように、本発明は再帰的に導出され
たデータをデータベースに配置する新規な構造及び方法
中に体現される。とりわけ繰返し数が前もって分らない
場合に、データベース中の互いに再帰的なリレーション
を直接的に評価する方法が必要とされてきた。
たデータをデータベースに配置する新規な構造及び方法
中に体現される。とりわけ繰返し数が前もって分らない
場合に、データベース中の互いに再帰的なリレーション
を直接的に評価する方法が必要とされてきた。
本発明の構造及び方法は、例えば、互いに再帰的なリレ
ーシランの最小不動点を計算することによって、こうし
たりレーシッンを評価する極めて効率のよい方法を提供
するものである。この結果、新たに提案された演算子に
よって拡張された関係代数技法の利用が可能になり、こ
うした評価に必要とされる繰返し数が前もって分らない
としても、互いに再帰的なりレーションの集合を効率よ
く評価することができるようになる。
ーシランの最小不動点を計算することによって、こうし
たりレーシッンを評価する極めて効率のよい方法を提供
するものである。この結果、新たに提案された演算子に
よって拡張された関係代数技法の利用が可能になり、こ
うした評価に必要とされる繰返し数が前もって分らない
としても、互いに再帰的なりレーションの集合を効率よ
く評価することができるようになる。
図面に例示的に示されているように、本発明の望ましい
実施例では、データ項目Ａ、ＢＳＤ、Ｆ。
実施例では、データ項目Ａ、ＢＳＤ、Ｆ。
Ｇ、Ｈ，Ｍ、Ｎ％Ｐ、、Ｒ％Ｔ１及び、Ｚのような、再
帰的に導出されたデータ項目のためのデータ構造は以下
のものを含んでいる；繰返しレベル・インデクス１０１
に示したレベル１〜３のような、その１つ１つがデータ
項目を導出した再帰的リレーション各繰返しに対応して
おり、所与の繰返し時に導出された全てのデータ項目は
対応する繰返しレベルに対応するようになっている、複
数の階層的繰返しレベル；全体が１０３で表示されてい
る、データ項目をインデクシングするためのインデクス
構造；各繰返しレベルに関連したデータ項目をリンクさ
せζポインタ１０５ 、１０７．１０９のような手段。
帰的に導出されたデータ項目のためのデータ構造は以下
のものを含んでいる；繰返しレベル・インデクス１０１
に示したレベル１〜３のような、その１つ１つがデータ
項目を導出した再帰的リレーション各繰返しに対応して
おり、所与の繰返し時に導出された全てのデータ項目は
対応する繰返しレベルに対応するようになっている、複
数の階層的繰返しレベル；全体が１０３で表示されてい
る、データ項目をインデクシングするためのインデクス
構造；各繰返しレベルに関連したデータ項目をリンクさ
せζポインタ１０５ 、１０７．１０９のような手段。
インデクス構造１０３には、順番にならべられて本構造
の最低位のインデクス・レベルを形成する、ノード１１
３のような複数の末端ノードを持つシーケンス・セット
１１１が含まれている。こうした各ノードは、データ項
目（たとえばポインター１５が指示するデータ項目Ｔ）
の１つに対するポインタ（たとえばポインター１５）、
そのデータ項目を一意的に識別する値゛°５”のような
キー値、及びそのデータ項目に関連したレベル“２”の
ような繰返しレベルの間の参照を提供する。
の最低位のインデクス・レベルを形成する、ノード１１
３のような複数の末端ノードを持つシーケンス・セット
１１１が含まれている。こうした各ノードは、データ項
目（たとえばポインター１５が指示するデータ項目Ｔ）
の１つに対するポインタ（たとえばポインター１５）、
そのデータ項目を一意的に識別する値゛°５”のような
キー値、及びそのデータ項目に関連したレベル“２”の
ような繰返しレベルの間の参照を提供する。
インデクス１０３にはまた、この構造の最低位のインデ
クス・レベルより上のレベル１２１．１２３及び１２５
といった複数のインデクス・レベルを形成するように階
層的に配置されたノード１１９のような、複数の非末端
（ｒｉｏｎ−１ｅａｆ）ノードを備えたインデクス・セ
ット１１７が含まれている。各インデクス・レベルのノ
ードの個数はそれより下のレベルに比べて少なく、また
各ノードはシーケンス・セットのキー値のある範囲を包
含する（ｅｎｃｏｓｐａｓｉｆ） ＊に含まれている。
クス・レベルより上のレベル１２１．１２３及び１２５
といった複数のインデクス・レベルを形成するように階
層的に配置されたノード１１９のような、複数の非末端
（ｒｉｏｎ−１ｅａｆ）ノードを備えたインデクス・セ
ット１１７が含まれている。各インデクス・レベルのノ
ードの個数はそれより下のレベルに比べて少なく、また
各ノードはシーケンス・セットのキー値のある範囲を包
含する（ｅｎｃｏｓｐａｓｉｆ） ＊に含まれている。
各ノードは、その範囲内の任意のキー値について、その
範囲内の前記キー値を存する１段低いレベルのノードへ
の、例えば矢印１２７で表わしたようなアクセス経路を
提供している。
範囲内の前記キー値を存する１段低いレベルのノードへ
の、例えば矢印１２７で表わしたようなアクセス経路を
提供している。
インデクス構造１０３にはまた、各繰返し１．レベルξ
ある実施例では、リンク手段は各繰返しレベルに関連
したデータ項目をリンクする、第２図の矢印１２９のよ
うな入城連鎖参照を有している。
ある実施例では、リンク手段は各繰返しレベルに関連
したデータ項目をリンクする、第２図の矢印１２９のよ
うな入城連鎖参照を有している。
別の実施例では、所与の繰返しレベルに関連した各デー
タ項目は、それぞれその繰返し、レベルに関連している
。第１図に示すページ１３１のようなページに割り当て
られる。リンク手段は各繰返しレベルに関連したページ
をリンクする矢印１０５．１０７ 、１０９のようなペ
ージ・リンク参照を含む。
タ項目は、それぞれその繰返し、レベルに関連している
。第１図に示すページ１３１のようなページに割り当て
られる。リンク手段は各繰返しレベルに関連したページ
をリンクする矢印１０５．１０７ 、１０９のようなペ
ージ・リンク参照を含む。
本発明は再帰的に導出されるデータ項目をＬ述の構造に
従って配置する方法を提供する。
従って配置する方法を提供する。
新しいデータ項目は、それらが導出されたとき、上述し
たデータ構造に挿入される。従って、こうしたデータを
繰返しレベルに従ってクラスタ分けするならば、それら
は通常、発生したときに、順次ページに割り当てられる
。しかし、こうすることは必ずしも必要ではなく、所与
の繰返しレベルの間に導出されたデータ項目がその繰返
しレベルに対応したページに割り当てられる限りは、任
意の順序でページにデータを割り当ててもよい。もちろ
ん、データが繰返しレベルによってクラスタ分けできな
い場合は、各データ項目は同じレベルの他のデータ項目
とチエインされる。
たデータ構造に挿入される。従って、こうしたデータを
繰返しレベルに従ってクラスタ分けするならば、それら
は通常、発生したときに、順次ページに割り当てられる
。しかし、こうすることは必ずしも必要ではなく、所与
の繰返しレベルの間に導出されたデータ項目がその繰返
しレベルに対応したページに割り当てられる限りは、任
意の順序でページにデータを割り当ててもよい。もちろ
ん、データが繰返しレベルによってクラスタ分けできな
い場合は、各データ項目は同じレベルの他のデータ項目
とチエインされる。
新しいデータ項目の挿入は以下のように行なわれる。先
ず新しいデータ項目の繰返しレベルと関連したデータ項
目のうちのどれが新しいデータ項目のキー値に最も近い
キー値を持っているかを同定し、この同定されたデータ
項目に隣接するように、新しいデータ項目をデータベー
スに挿入し、新しいデータ項目の繰返しレベルに関連し
た他のデータ項目に新しいデータ項目をリンクさせる。
ず新しいデータ項目の繰返しレベルと関連したデータ項
目のうちのどれが新しいデータ項目のキー値に最も近い
キー値を持っているかを同定し、この同定されたデータ
項目に隣接するように、新しいデータ項目をデータベー
スに挿入し、新しいデータ項目の繰返しレベルに関連し
た他のデータ項目に新しいデータ項目をリンクさせる。
また新しいデータ項目へのポインタを持つ新しい末端ノ
ードを生成し、シーケンス・セットにこの新しい末端ノ
ードを挿入する。またインデクス・セットを調整して、
新しい末端ノードへの経路を含ませるようにする。イン
デクス・セットは、例えば、Ｃ，Ｊ、ＤａｔｅによるＡ
ｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｄａｔａｂａｓ
ｅ Ｓｙｓｔｅｍｓ （第４版）第１巻の６３〜６７１
に記載されているような、通常のＢ−木のインデクス・
セットを調整するのに用いられているのと同様のやり方
で調整される。データのクラスタ分けが繰返しレベルに
従って行なわれる場合、データ環を正しい繰返しレベル
のページにきちんと割り当てる以外には、何もリンクを
とる必要はない、なんとなれば同じ繰返しレベルに対応
するページ同志は互いにチエインされているからである
。
ードを生成し、シーケンス・セットにこの新しい末端ノ
ードを挿入する。またインデクス・セットを調整して、
新しい末端ノードへの経路を含ませるようにする。イン
デクス・セットは、例えば、Ｃ，Ｊ、ＤａｔｅによるＡ
ｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｄａｔａｂａｓ
ｅ Ｓｙｓｔｅｍｓ （第４版）第１巻の６３〜６７１
に記載されているような、通常のＢ−木のインデクス・
セットを調整するのに用いられているのと同様のやり方
で調整される。データのクラスタ分けが繰返しレベルに
従って行なわれる場合、データ環を正しい繰返しレベル
のページにきちんと割り当てる以外には、何もリンクを
とる必要はない、なんとなれば同じ繰返しレベルに対応
するページ同志は互いにチエインされているからである
。
第３図には新しいデータ項目を挿入するプロセスを示す
、ここで、新しいデータ項目Ｋが大域的データ集合１２
９に追加されたばかりの状態が図示されている。新しい
末端ノード１３３が生成されて、既存の末端ノード１３
５と１３７の間に適正な順序で挿入されている。また、
この挿入により末端ノード１３７かずらされて右へ１つ
分移動している。矢印１３９で示すように、データ項目
にはレベル２の項目減とチエインがとられ、またインデ
クス木は、非末端ノード１１９中の値が変化しているこ
とで示されるように調整されている。矢印１４１で示し
た新しいポインタがノード１３３とデータ項目にの間に
設けられている。
、ここで、新しいデータ項目Ｋが大域的データ集合１２
９に追加されたばかりの状態が図示されている。新しい
末端ノード１３３が生成されて、既存の末端ノード１３
５と１３７の間に適正な順序で挿入されている。また、
この挿入により末端ノード１３７かずらされて右へ１つ
分移動している。矢印１３９で示すように、データ項目
にはレベル２の項目減とチエインがとられ、またインデ
クス木は、非末端ノード１１９中の値が変化しているこ
とで示されるように調整されている。矢印１４１で示し
た新しいポインタがノード１３３とデータ項目にの間に
設けられている。
重複するデータ項目は廃棄するのが望ましい。
これは新しいデータ項目のキー値が同定されたデータ項
目つまり新しいデータ項目をそのすぐ次に配置すべきデ
ータ項目のキー値と同じである場合には、新しいデータ
項目を廃棄することで可能になる。もし望むならば、こ
の新しいデータ項目を廃棄する前にこれら２つのデータ
項目を比較して、それらが同じであるか確認してもよい
。
目つまり新しいデータ項目をそのすぐ次に配置すべきデ
ータ項目のキー値と同じである場合には、新しいデータ
項目を廃棄することで可能になる。もし望むならば、こ
の新しいデータ項目を廃棄する前にこれら２つのデータ
項目を比較して、それらが同じであるか確認してもよい
。
重複するデータ項目を除去する利点は、ある繰返しの間
に発生した全てのデータ項目が廃棄された場合に、繰返
しを中止できるということにある。
に発生した全てのデータ項目が廃棄された場合に、繰返
しを中止できるということにある。
これにより、再帰的なリレーシランの評価に必要とされ
る繰返し回数が分らない場合、繰返しの中止時期に対す
る効率のよいテストが可能になる。
る繰返し回数が分らない場合、繰返しの中止時期に対す
る効率のよいテストが可能になる。
本発明は、既述のように配置されたデータ項目だめの、
極めて効率のよい方法を提供する。このサーチ方法は、
末端ノードが提供するいくつかの経路からアクセス経路
を選択して指定されたキー値に関連した末端ノードを突
きとめ；この突きとめられた末端ノードに関連した繰返
しレベルが指定された範囲内にあるかどうかを判定し；
この判定が肯定の場合に限り前述の突きとめられた末端
ノードに関連したデータ項目を戻す。
極めて効率のよい方法を提供する。このサーチ方法は、
末端ノードが提供するいくつかの経路からアクセス経路
を選択して指定されたキー値に関連した末端ノードを突
きとめ；この突きとめられた末端ノードに関連した繰返
しレベルが指定された範囲内にあるかどうかを判定し；
この判定が肯定の場合に限り前述の突きとめられた末端
ノードに関連したデータ項目を戻す。
本発明はまた、データ項目の集合を走査して、指定され
た条件を満たし、かつン指定された繰返しレベルを持つ
データ項目を見つけるための、極めて効率のよい方法を
提供する。この方法では、繰返しレベル・インデクスを
利用して、指定された繰返しレベルに関連した最初のデ
ータ項目を突きとめ；データ項目のリンクをたどってそ
の繰返しレベルに関連した他のデータ項目を突きとめ；
突きとめられた各データ項目を順次調べて、指定された
条件を満たすかどうか夫々判定し；調べたデータ項目が
指定された条件を満たす場合にはそのデータ項目を取り
出す、走査の間に取り出されたこれらデータ項目はその
キー値に基づく順番で順番に配列される。
た条件を満たし、かつン指定された繰返しレベルを持つ
データ項目を見つけるための、極めて効率のよい方法を
提供する。この方法では、繰返しレベル・インデクスを
利用して、指定された繰返しレベルに関連した最初のデ
ータ項目を突きとめ；データ項目のリンクをたどってそ
の繰返しレベルに関連した他のデータ項目を突きとめ；
突きとめられた各データ項目を順次調べて、指定された
条件を満たすかどうか夫々判定し；調べたデータ項目が
指定された条件を満たす場合にはそのデータ項目を取り
出す、走査の間に取り出されたこれらデータ項目はその
キー値に基づく順番で順番に配列される。
上述のサーチと走査の技法を組み合わせることによって
、入れ子ループ結合や併合走査結合のような結合演算を
行なうことが可能になる。こうした結合を行なう能力に
よって、本発明では最小不動点の効率的な評価ができる
ようになる。
、入れ子ループ結合や併合走査結合のような結合演算を
行なうことが可能になる。こうした結合を行なう能力に
よって、本発明では最小不動点の効率的な評価ができる
ようになる。
入れ子ループ結合を行なう本発明に従った方法では、デ
ータ項目の第１の集合を走査して指定された条件を満た
しかつ指定された繰返しレベルを持つデータ項目を見つ
け；上のステップで見つけた各データ項目毎に、第２の
データ項目の集合をサーチして当該データ項目のキー値
に一致するキー値と、指定された繰返しレベルとを持つ
データ項目を全て見つけ；走査で見つけた各データ項目
毎に、それにサーチで見つけた対応する全データ項目を
結合する。
ータ項目の第１の集合を走査して指定された条件を満た
しかつ指定された繰返しレベルを持つデータ項目を見つ
け；上のステップで見つけた各データ項目毎に、第２の
データ項目の集合をサーチして当該データ項目のキー値
に一致するキー値と、指定された繰返しレベルとを持つ
データ項目を全て見つけ；走査で見つけた各データ項目
毎に、それにサーチで見つけた対応する全データ項目を
結合する。
本発明による併合走査結合を行なう方法では、第１の指
定された繰返しレベルを持つデータ項目の第１の集合と
第２の繰返しレベルを備えたデータ項目の第２の集合と
を同時に走査し；第１の集合の走査において見つけた全
データ項目と第２の集合の任意走査において見つけた整
合する（ｍａ ｔｃ−ｈｉｎｇ）データ項目を結合する
０本質的には、第１の走査は、その走査の際各データ項
目毎に休止し、第２の走査は整合が見つからなくなるま
で、進められる０両方の集合中のデータはキー値による
１＠番に配置されているので、併合走査の動作を完了す
るのには各集合を１回バスするだけですむ。
定された繰返しレベルを持つデータ項目の第１の集合と
第２の繰返しレベルを備えたデータ項目の第２の集合と
を同時に走査し；第１の集合の走査において見つけた全
データ項目と第２の集合の任意走査において見つけた整
合する（ｍａ ｔｃ−ｈｉｎｇ）データ項目を結合する
０本質的には、第１の走査は、その走査の際各データ項
目毎に休止し、第２の走査は整合が見つからなくなるま
で、進められる０両方の集合中のデータはキー値による
１＠番に配置されているので、併合走査の動作を完了す
るのには各集合を１回バスするだけですむ。
本発明の特定の実施例について解説し例示してきたが、
本発明は、以上で解説し例示した特定の形態や構成に限
定されるものではなく、本発明の求の範囲内であれば、
上で特に解説し例示したものとは別様に本発明を実行す
ることが可能である。
本発明は、以上で解説し例示した特定の形態や構成に限
定されるものではなく、本発明の求の範囲内であれば、
上で特に解説し例示したものとは別様に本発明を実行す
ることが可能である。
〔発明の効果〕
以上から明らかなように、本発明のデータ構造及び方法
は、複雑なデータベースの照会に対し効率よく応答する
方法を提供するものである０例えば、評価を行なうのに
必要とされる繰返し回数が前もって分らない場合であっ
ても、オーバーヘッドを最小限にとどめて、リレーショ
ンの最小不動点を計算することにより、互いに再帰的な
１組のりレージ町ンの評価が行なわれる。
は、複雑なデータベースの照会に対し効率よく応答する
方法を提供するものである０例えば、評価を行なうのに
必要とされる繰返し回数が前もって分らない場合であっ
ても、オーバーヘッドを最小限にとどめて、リレーショ
ンの最小不動点を計算することにより、互いに再帰的な
１組のりレージ町ンの評価が行なわれる。
第１図および第２図は本発明の一実施例のデータベース
構造を説明する図、 第３図は第２図に示すデータベース構造への新しいデー
タ項目の挿入を説明する図である。 １０１：繰返しレベル・インデクス １０３：インデクス構造 Ｉｌｌ ニジ−ケンス・セット １２９：大域的データ構造 １３１：ベージ
構造を説明する図、 第３図は第２図に示すデータベース構造への新しいデー
タ項目の挿入を説明する図である。 １０１：繰返しレベル・インデクス １０３：インデクス構造 Ｉｌｌ ニジ−ケンス・セット １２９：大域的データ構造 １３１：ベージ
Claims (22)
- （１）以下の（ａ）ないし（ｃ）を設けてなる、再帰的
に導出されたデータ項目のためのデータベース構造： （ａ）複数の階層的繰り返しレベル：前記繰り返しレベ
ルの各々は前記データ項目が導出される再帰的関係の各
繰り返しに対応し、所与の繰り返しの間に導出される全
てのデータ項目は対応する前記繰り返しレベルに関連付
けられている； （ｂ）以下の（ｂ−１）ないし（ｂ−３）を有し、前記
データ項目をインデクスするインデクス構造： （ｂ−１）シーケンス・セット：順番に配列され前記イ
ンデクス構造の最低位のインデクス・レベルを定義する
複数の末端ノードを有し、前記末端ノードの各々は前記
データ項目の１つへの参照と、当該データ項目を一意的
に識別するキー値と、当該データ項目に関連する繰り返
しレベルとを与える； （ｂ−２）インデクス・セット：階層的に配列され前記
インデクス構造の最低位より上位にある複数のインデク
ス・レベルを定義する複数の非末端ノードを有し、前記
定義される最低位より上位にあるインデクス・レベルの
各々は当該インデクス・レベルの下位のインデクス・レ
ベルよりも少ない個数のノードを有し、前記ノードの各
々は前記シーケンス・セットのキー値の範囲を包含し、
任意のインデクス・レベルの前記ノードの全体は前記キ
ー値の全てを包含し、１つの前記ノードによって包含さ
れる前記キー値の範囲は上位のインデクス・レベルの１
つのノードによって包含される前記キー値の範囲に含ま
れ、前記ノードの各々は当該ノードの前記範囲内に含ま
れる任意の前記キー値について、前記任意のインデクス
・レベルよりも１段低いインデクス・レベルのノードで
あって当該キー値を自己の前記範囲内に含むノードへの
アクセス経路を与える； （ｂ−３）繰り返しレベル・インデクス：前記繰り返し
レベルの各々と当該繰り返しレベルに関連付けられたデ
ータ項目との間の参照を与える； （ｃ）前記繰り返しレベルの各々に関連付けられたデー
タ項目をリンクする手段。 - （２）前記リンクする手段は前記繰り返しレベルの各々
に関連付けられたデータ項目をリンクする大域的連鎖参
照を有することを特徴とする請求項１記載のデータベー
ス構造。 - （３）所与の繰り返しレベルに関連付けられた前記デー
タ項目の各々は当該繰り返しレベルに関連付けられたペ
ージに割り当てられることを特徴とする請求項１記載の
データベース構造。 - （４）前記リンクする手段は各繰り返しレベルに関連付
けられた前記ページをリンクするページ連鎖参照を有す
ることを特徴とする請求項３記載のデータベース構造。 - （５）以下のステップ（ａ）ないし（ｈ）を設け、再帰
的に導出されたデータ項目をデータベース中に配列する
方法： （ａ）複数の階層的繰り返しレベルを定義する：当該繰
り返しレベルの各々は前記データ項目が導出される再帰
的関係の繰り返しの各々に対応する； （ｂ）所与の繰り返しの間に生成された全てのデータ項
目を対応する前記繰り返しレベルに関連付ける； （ｃ）順番に配列された複数の末端ノードを有しインデ
クス構造の最低位のインデクス・レベルを定義するシー
ケンス・セットを定義する； （ｄ）前記末端ノードの各々に、前記データ項目の１つ
へのポインタと当該データ項目を一意的に識別するキー
値と当該データ項目に関連付けられた繰り返しレベルと
を関連付ける； （ｅ）階層的に配列された複数の非末端ノードを有し前
記インデクス構造の前記最低位のインデクス・レベルよ
りも上にある複数のインデクス・レベルを定義する：当
該定義されたインデクスレベルの各々はその下位のイン
デクス・レベルよりも少ないノードを有する； （ｆ）任意のインデクス・レベルにあるノードが全体と
して前記キー値の全てを包含するように、各ノードに前
記キー値の範囲を割り当てる：１つのノードによって包
含される前記範囲は当該ノードのインデクス・レベルの
直上のインデクス・レベルにあるノードによって包含さ
れる範囲に含まれ、各ノードは当該ノードの前記範囲内
の任意のキー値について当該キー値を有し当該ノードの
直下のインデクス・レベルにあるひとつのノードへのア
クセス経路を与える； （ｇ）前記繰り返しレベルの各々と当該繰り返しレベル
に関連付けられているデータ項目の間の参照を与える繰
り返しレベル・インデクスを定義する； （ｈ）各繰り返しレベルの各々に関連付けられているデ
ータ項目をリンクする。 - （６）データ項目をリンクする前記ステップは所与の繰
り返しレベルに関連付けられたデータ項目を大域的に連
鎖させることを含むことを特徴とする請求項５記載のデ
ータ項目をデータベース中に配列する方法。 - （７）新しいデータ項目を前記データベースに挿入する
ために： 前記新しいデータ項目の繰り返しレベルに関連付けられ
たデータ項目の中の何れが前記新しいデータ項目が有す
るキー値に最も近いキー値を有するかを同定し； 前記データベース中で前記同定されたデータ項目の隣に
前記新しいデータ項目を挿入し；前記新しいデータ項目
を前記新しいデータ項目の繰り返しレベルに関連付けら
れた他のデータ項目にリンクし； 前記新しいデータ項目へのポインタを有する新しい末端
ノードを生成し； 前記新しい末端ノードを前記シーケンス・セットへ挿入
し； 前記インデクス・セットが前記新しい末端ノードへの経
路を含むように前記インデクス・セットを調節する ステップを設けたことを特徴とする請求項６記載のデー
タ項目をデータベース中に配列する方法。 - （８）もし前記新しいデータ項目のキー値が前記同定さ
れたデータ項目のキー値と同一であった場合には前記新
しいデータ項目を棄却することを特徴とする請求項７記
載のデータ項目をデータベース中に配列する方法。 - （９）ある繰り返しの間に生成された前記データ項目が
全て棄却された場合に前記再帰的関係の繰り返しを停止
することを特徴とする請求項８記載のデータ項目をデー
タベース中に配列する方法。 - （１０）前記新しいデータ項目が前記同定されたデータ
項目と同一であった場合に前記新しいデータ項目を棄却
することを特徴とする請求項７記載のデータ項目をデー
タベース中に配列する方法。 - （１１）ある繰り返しの間に生成された前記データ項目
が全て棄却された場合に前記再帰的関係の繰り返しを停
止することを特徴とする請求項１０記載のデータ項目を
データベース中に配列する方法。 - （１２）所与の繰り返しレベルに関連付けられたデータ
項目の各々を当該繰り返しレベルに関連付けられたペー
ジに割り当てることを特徴とする請求項５記載のデータ
項目をデータベース中に配列する方法。 - （１３）データ項目をリンクする前記ステップは所与の
繰り返しレベルに関連付けられた前記ページを連鎖させ
ることを特徴とする請求項１２記載のデータ項目をデー
タベース中に配列する方法。 - （１４）新しいデータ項目を挿入するために：前記新し
いデータ項目の繰り返しレベルに関連付けられているデ
ータ項目の何れが前記新しいデータ項目の前記キー値に
最も近いキー値を有しているかを同定し； 前記新しいデータ項目を前記新しいデータ項目の繰り返
しレベルに関連付けられたページ中の前記同定されたデ
ータ項目の隣のロケーションに割当て； 前記新しいデータ項目へのポインタを有する新しい末端
ノードを生成し； 前記新しい末端ノードを前記シーケンス・セットへ挿入
し； 前記新しい末端ノードへの経路を含むように前記インデ
クス・セットを調節する ステップを設けたことを特徴とする請求項１３記載のデ
ータ項目をデータベース中に配列する方法。 - （１５）前記新しいデータ項目のキー値が前記同定され
たデータ項目のキー値と同一であった場合には前記新し
いデータ項目を棄却することを特徴とする請求項１４記
載のデータ項目をデータベース中に配列する方法。 - （１６）ある繰り返しの間に生成された全てのデータ項
目が棄却された場合に前記再帰的関係の繰り返しを停止
することを特徴とする請求項１５記載のデータ項目をデ
ータベース中に配列する方法。 - （１７）前記新しいデータ項目が前記同定されたデータ
項目と同一であった場合は前記新しいデータ項目を棄却
することを特徴とする請求項１４記載のデータ項目をデ
ータベース中に配列する方法。 - （１８）ある繰り返しの間に生成された全てのデータ項
目が棄却された場合に前記再帰的関係の繰り返しを停止
することを特徴とする請求項１７記載のデータ項目をデ
ータベース中に配列する方法。 - （１９）以下のステップ（ａ）ないし（ｃ）を設け、請
求項５の方法に従って配列されたデータ項目の集合をサ
ーチし指定されたキー値および指定された範囲内の繰り
返しレベルを有する全データ項目を見出す方法： （ａ）前記非末端ノードによって与えられる経路からア
クセス経路を選択して前記指定されたキー値に関連付け
られた末端ノードを発見する； （ｂ）前記末端ノードに関連付けられた繰り返しレベル
が前記指定された範囲内であるか否かを判定する； （ｃ）前記判定の結果が肯定的であった場合に前記末端
ノードに関連付けられたデータ項目を戻す。 - （２０）以下のステップ（ａ）ないし（ｄ）を設け、請
求項５の方法に従って配列されたデータ項目の集合を走
査し指定された条件を満足し指定された繰り返しレベル
を有するデータ項目を見出す方法： （ａ）前記繰り返しレベル・インデクスを使用して前記
指定された繰り返しレベルに関連付けられた最初のデー
タ項目を発見する； （ｂ）前記発見されたデータ項目のリンクを辿って前記
指定された繰り返しレベルに関連付けられた他のデータ
項目を発見する； （ｃ）前記発見されたデータ項目の各々についてそれが
前記指定された条件を満足するか否かを確認する； （ｄ）前記確認されたデータ項目が前記指定された条件
を満足した場合に当該データ項目を取り出す：前記走査
の間に戻されるデータ項目はそれらのキー値に従って順
番に並べられる。 - （２１）下記のステップ（ａ）ないし（ｃ）を設け、デ
ータ項目が請求項５の方法に従って配列されたデータベ
ースにおいて入れ子ループ結合を行う方法： （ａ）前記データ項目の第１の集合を走査して指定され
た条件を満足しかつ指定された繰り返しレベルを有する
データ項目を見出す； （ｂ）ステップ（ａ）で見出されたデータ項目の各々に
ついて前記データ項目の第２の集合をサーチし当該デー
タ項目のキー値に対応するキー値および指定された繰り
返しレベルを有するデータ項目を見出す； （ｃ）前記走査中に見出されたデータ項目の各々を前記
サーチ中に見出された対応する全データ項目と結合する
。 - （２２）下記のステップ（ａ）および（ｂ）を設け、デ
ータ項目が請求項５の方法に従って配列されたデータベ
ース・システムにおいてマージ走査結合を行う方法： （ａ）第１の指定された繰り返しレベルを有するデータ
項目の第１の集合および第２の繰り返しレベルを有する
データ項目の第２の集合のサーチを同時に行い； （ｂ）第１の集合の走査で見出された全データ項目を第
２の集合の全走査で見出されたデータ項目の中のマッチ
する全データ項目と結合する。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US28642588A | 1988-12-19 | 1988-12-19 | |
| US286,425 | 1988-12-19 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH02212972A true JPH02212972A (ja) | 1990-08-24 |
| JP2771288B2 JP2771288B2 (ja) | 1998-07-02 |
Family
ID=23098548
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1329400A Expired - Lifetime JP2771288B2 (ja) | 1988-12-19 | 1989-12-19 | データベース操作方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US5546571A (ja) |
| EP (1) | EP0375307B1 (ja) |
| JP (1) | JP2771288B2 (ja) |
| CA (1) | CA2001390C (ja) |
| DE (1) | DE68926849T2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8209440B2 (en) | 2008-05-30 | 2012-06-26 | Fujitsu Limited | Device-configuration-information optimum arrangement method and device-configuration-information optimum arrangement system |
| JP2013016112A (ja) * | 2011-07-06 | 2013-01-24 | Nippon Telegr & Teleph Corp <Ntt> | チャンク生成装置、チャンク読み取り装置、チャンク生成方法及びプログラム |
Families Citing this family (90)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0558505B1 (en) * | 1990-10-05 | 2000-01-26 | Microsoft Corporation | System and method for information retrieval |
| CA2117846C (en) * | 1993-10-20 | 2001-02-20 | Allen Reiter | Computer method and storage structure for storing and accessing multidimensional data |
| US5657437A (en) * | 1993-12-10 | 1997-08-12 | Lucent Technologies Inc. | Data processing apparatus and method including proportional updating of data |
| GB9417314D0 (en) * | 1994-08-27 | 1994-10-19 | Int Computers Ltd | Method for performing joins in a database system |
| JP3549608B2 (ja) * | 1995-04-04 | 2004-08-04 | 富士通株式会社 | 識別子による階層構造データの構造判定方法および装置 |
| US5752241A (en) * | 1995-11-14 | 1998-05-12 | Lucent Technologies Inc. | Method and apparatus for estimating transitive closure and reachability |
| US5787424A (en) * | 1995-11-30 | 1998-07-28 | Electronic Data Systems Corporation | Process and system for recursive document retrieval |
| US5761654A (en) * | 1996-06-05 | 1998-06-02 | Oracle Corporation | Memory structure and method for tuning a database statement using a join-tree data structure representation, including selectivity factors, of a master table and detail table |
| US6374232B1 (en) * | 1996-08-29 | 2002-04-16 | Oracle Corp. | Method and mechanism for retrieving values from a database |
| US5937388A (en) * | 1996-12-05 | 1999-08-10 | Hewlett-Packard Company | System and method for performing scalable distribution of process flow activities in a distributed workflow management system |
| US6014673A (en) * | 1996-12-05 | 2000-01-11 | Hewlett-Packard Company | Simultaneous use of database and durable store in work flow and process flow systems |
| US6115716A (en) * | 1997-03-14 | 2000-09-05 | Nokia Telecommunications Oy | Method for implementing an associative memory based on a digital trie structure |
| FI102424B (fi) | 1997-03-14 | 1998-11-30 | Nokia Telecommunications Oy | Menetelmä muistin toteuttamiseksi |
| FI102426B1 (fi) | 1997-03-14 | 1998-11-30 | Nokia Telecommunications Oy | Menetelmä muistin toteuttamiseksi |
| US6735253B1 (en) | 1997-05-16 | 2004-05-11 | The Trustees Of Columbia University In The City Of New York | Methods and architecture for indexing and editing compressed video over the world wide web |
| US5991756A (en) * | 1997-11-03 | 1999-11-23 | Yahoo, Inc. | Information retrieval from hierarchical compound documents |
| US6442557B1 (en) | 1998-02-27 | 2002-08-27 | Prc Inc. | Evaluation of enterprise architecture model including relational database |
| US6272486B1 (en) * | 1998-04-16 | 2001-08-07 | International Business Machines Corporation | Determining the optimal number of tasks for building a database index |
| US6112209A (en) * | 1998-06-17 | 2000-08-29 | Gusack; Mark David | Associative database model for electronic-based informational assemblies |
| US6601058B2 (en) | 1998-10-05 | 2003-07-29 | Michael Forster | Data exploration system and method |
| US6327587B1 (en) | 1998-10-05 | 2001-12-04 | Digital Archaeology, Inc. | Caching optimization with disk and/or memory cache management |
| US7143434B1 (en) | 1998-11-06 | 2006-11-28 | Seungyup Paek | Video description system and method |
| US7526468B2 (en) * | 1999-01-08 | 2009-04-28 | Computer Associates Think, Inc. | System and method for recursive path analysis of DBMS procedures |
| US6941325B1 (en) * | 1999-02-01 | 2005-09-06 | The Trustees Of Columbia University | Multimedia archive description scheme |
| AU3694300A (en) * | 1999-02-01 | 2000-08-18 | Ibm | Multimedia archive description scheme |
| US6427123B1 (en) | 1999-02-18 | 2002-07-30 | Oracle Corporation | Hierarchical indexing for accessing hierarchically organized information in a relational system |
| US6446085B1 (en) | 1999-06-17 | 2002-09-03 | International Business Machines Corporation | Method and apparatus for processing recursive hard links in a data processing system |
| US6473763B1 (en) | 2000-03-31 | 2002-10-29 | International Business Machines Corporation | System, method and computer program for filtering multi-action rule set |
| US7313692B2 (en) * | 2000-05-19 | 2007-12-25 | Intertrust Technologies Corp. | Trust management systems and methods |
| KR100413967B1 (ko) * | 2000-12-30 | 2004-01-07 | 한국전자통신연구원 | 항해기반 데이터 모델에서 중첩구조 데이터세트의 해석 및변환 방법 |
| AU2002351310A1 (en) | 2001-12-06 | 2003-06-23 | The Trustees Of Columbia University In The City Of New York | System and method for extracting text captions from video and generating video summaries |
| US7058640B2 (en) * | 2003-02-05 | 2006-06-06 | International Business Machines Corporation | Systems, methods, and computer program products to efficiently update multidimensional databases |
| US8229932B2 (en) | 2003-09-04 | 2012-07-24 | Oracle International Corporation | Storing XML documents efficiently in an RDBMS |
| US8694510B2 (en) | 2003-09-04 | 2014-04-08 | Oracle International Corporation | Indexing XML documents efficiently |
| CN1849602A (zh) * | 2003-09-09 | 2006-10-18 | 皇家飞利浦电子股份有限公司 | 用于提供数据的树形结构视图的方法 |
| US7493305B2 (en) | 2004-04-09 | 2009-02-17 | Oracle International Corporation | Efficient queribility and manageability of an XML index with path subsetting |
| US7366735B2 (en) | 2004-04-09 | 2008-04-29 | Oracle International Corporation | Efficient extraction of XML content stored in a LOB |
| US7499915B2 (en) * | 2004-04-09 | 2009-03-03 | Oracle International Corporation | Index for accessing XML data |
| US7680811B2 (en) * | 2004-04-16 | 2010-03-16 | Infoblox Inc. | Set based data store |
| US7930277B2 (en) | 2004-04-21 | 2011-04-19 | Oracle International Corporation | Cost-based optimizer for an XML data repository within a database |
| US20050278301A1 (en) * | 2004-05-26 | 2005-12-15 | Castellanos Maria G | System and method for determining an optimized process configuration |
| US7971191B2 (en) * | 2004-06-10 | 2011-06-28 | Hewlett-Packard Development Company, L.P. | System and method for analyzing a process |
| US7885980B2 (en) * | 2004-07-02 | 2011-02-08 | Oracle International Corporation | Mechanism for improving performance on XML over XML data using path subsetting |
| US8566300B2 (en) | 2004-07-02 | 2013-10-22 | Oracle International Corporation | Mechanism for efficient maintenance of XML index structures in a database system |
| US7236938B2 (en) * | 2004-08-11 | 2007-06-26 | Hewlett-Packard Development Company, L.P. | System and method for refreshing metric values |
| US8412671B2 (en) * | 2004-08-13 | 2013-04-02 | Hewlett-Packard Development Company, L.P. | System and method for developing a star schema |
| US7389296B2 (en) * | 2004-09-02 | 2008-06-17 | International Business Machines Corporation | Method, system and program product for displaying a logical structure |
| US7627547B2 (en) * | 2004-11-29 | 2009-12-01 | Oracle International Corporation | Processing path-based database operations |
| US7921076B2 (en) | 2004-12-15 | 2011-04-05 | Oracle International Corporation | Performing an action in response to a file system event |
| US8131766B2 (en) * | 2004-12-15 | 2012-03-06 | Oracle International Corporation | Comprehensive framework to integrate business logic into a repository |
| US20060167825A1 (en) * | 2005-01-24 | 2006-07-27 | Mehmet Sayal | System and method for discovering correlations among data |
| US8631391B2 (en) | 2005-01-24 | 2014-01-14 | Hewlett-Packard Development Company, L.P. | Method and a system for process discovery |
| US7529790B1 (en) | 2005-01-27 | 2009-05-05 | Hewlett-Packard Development Company, L.P. | System and method of data analysis |
| WO2006096612A2 (en) | 2005-03-04 | 2006-09-14 | The Trustees Of Columbia University In The City Of New York | System and method for motion estimation and mode decision for low-complexity h.264 decoder |
| US7337167B2 (en) * | 2005-04-14 | 2008-02-26 | International Business Machines Corporation | Estimating a number of rows returned by a recursive query |
| US7467145B1 (en) | 2005-04-15 | 2008-12-16 | Hewlett-Packard Development Company, L.P. | System and method for analyzing processes |
| US8423396B1 (en) | 2005-04-28 | 2013-04-16 | Hewlett-Packard Development Company, L.P. | System and method for process discovery |
| US8073841B2 (en) | 2005-10-07 | 2011-12-06 | Oracle International Corporation | Optimizing correlated XML extracts |
| US8356053B2 (en) * | 2005-10-20 | 2013-01-15 | Oracle International Corporation | Managing relationships between resources stored within a repository |
| US20070118510A1 (en) * | 2005-11-18 | 2007-05-24 | Microsoft Corporation | Optimization of leaf-level multi-dimensional calculation using scripts |
| US8949455B2 (en) | 2005-11-21 | 2015-02-03 | Oracle International Corporation | Path-caching mechanism to improve performance of path-related operations in a repository |
| US8510292B2 (en) * | 2006-05-25 | 2013-08-13 | Oracle International Coporation | Isolation for applications working on shared XML data |
| US7499909B2 (en) * | 2006-07-03 | 2009-03-03 | Oracle International Corporation | Techniques of using a relational caching framework for efficiently handling XML queries in the mid-tier data caching |
| US7941451B1 (en) * | 2006-08-18 | 2011-05-10 | Unisys Corporation | Dynamic preconditioning of a B+ tree |
| US9183321B2 (en) | 2006-10-16 | 2015-11-10 | Oracle International Corporation | Managing compound XML documents in a repository |
| US7827177B2 (en) * | 2006-10-16 | 2010-11-02 | Oracle International Corporation | Managing compound XML documents in a repository |
| US7797310B2 (en) | 2006-10-16 | 2010-09-14 | Oracle International Corporation | Technique to estimate the cost of streaming evaluation of XPaths |
| CN101641692A (zh) * | 2006-12-05 | 2010-02-03 | 佛罗里达研究基金会大学 | 非线性动态搜索引擎 |
| US7836098B2 (en) * | 2007-07-13 | 2010-11-16 | Oracle International Corporation | Accelerating value-based lookup of XML document in XQuery |
| US7840609B2 (en) * | 2007-07-31 | 2010-11-23 | Oracle International Corporation | Using sibling-count in XML indexes to optimize single-path queries |
| US7991768B2 (en) | 2007-11-08 | 2011-08-02 | Oracle International Corporation | Global query normalization to improve XML index based rewrites for path subsetted index |
| US8144705B1 (en) * | 2008-03-17 | 2012-03-27 | Juniper Networks, Inc. | Systems and methods for recursively accessing a multi-bank SRAM |
| WO2009126785A2 (en) | 2008-04-10 | 2009-10-15 | The Trustees Of Columbia University In The City Of New York | Systems and methods for image archaeology |
| WO2009155281A1 (en) | 2008-06-17 | 2009-12-23 | The Trustees Of Columbia University In The City Of New York | System and method for dynamically and interactively searching media data |
| US7958112B2 (en) | 2008-08-08 | 2011-06-07 | Oracle International Corporation | Interleaving query transformations for XML indexes |
| US8671069B2 (en) | 2008-12-22 | 2014-03-11 | The Trustees Of Columbia University, In The City Of New York | Rapid image annotation via brain state decoding and visual pattern mining |
| US8219563B2 (en) * | 2008-12-30 | 2012-07-10 | Oracle International Corporation | Indexing mechanism for efficient node-aware full-text search over XML |
| US8126932B2 (en) * | 2008-12-30 | 2012-02-28 | Oracle International Corporation | Indexing strategy with improved DML performance and space usage for node-aware full-text search over XML |
| US8930375B2 (en) * | 2012-03-02 | 2015-01-06 | Cleversafe, Inc. | Splitting an index node of a hierarchical dispersed storage index |
| US10366102B2 (en) * | 2014-02-19 | 2019-07-30 | Snowflake Inc. | Resource management systems and methods |
| US9959299B2 (en) | 2014-12-02 | 2018-05-01 | International Business Machines Corporation | Compression-aware partial sort of streaming columnar data |
| US10909078B2 (en) * | 2015-02-25 | 2021-02-02 | International Business Machines Corporation | Query predicate evaluation and computation for hierarchically compressed data |
| US9875087B2 (en) * | 2015-04-10 | 2018-01-23 | Oracle International Corporation | Declarative program engine for large-scale program analysis |
| US10452655B2 (en) | 2015-10-23 | 2019-10-22 | Oracle International Corporation | In-memory cursor duration temp tables |
| US10783142B2 (en) | 2015-10-23 | 2020-09-22 | Oracle International Corporation | Efficient data retrieval in staged use of in-memory cursor duration temporary tables |
| US10678792B2 (en) * | 2015-10-23 | 2020-06-09 | Oracle International Corporation | Parallel execution of queries with a recursive clause |
| US10642831B2 (en) | 2015-10-23 | 2020-05-05 | Oracle International Corporation | Static data caching for queries with a clause that requires multiple iterations to execute |
| US11645285B2 (en) * | 2018-04-27 | 2023-05-09 | Aras Corporation | Query engine for recursive searches in a self-describing data system |
| US10942891B2 (en) | 2019-03-27 | 2021-03-09 | Ownbackup Ltd. | Reducing number of queries on a relational database |
| WO2023140968A1 (en) * | 2022-01-18 | 2023-07-27 | Craxel, Inc. | Executing hierarchical data space operations |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4128891A (en) * | 1976-12-30 | 1978-12-05 | International Business Machines Corporation | Magnetic bubble domain relational data base system |
| US4514826A (en) * | 1981-05-18 | 1985-04-30 | Tokyo Shibaura Denki Kabushiki Kaisha | Relational algebra engine |
| US4606002A (en) * | 1983-05-02 | 1986-08-12 | Wang Laboratories, Inc. | B-tree structured data base using sparse array bit maps to store inverted lists |
| US5010478A (en) * | 1986-04-11 | 1991-04-23 | Deran Roger L | Entity-attribute value database system with inverse attribute for selectively relating two different entities |
| US4945475A (en) * | 1986-10-30 | 1990-07-31 | Apple Computer, Inc. | Hierarchical file system to provide cataloging and retrieval of data |
| US5062074A (en) * | 1986-12-04 | 1991-10-29 | Tnet, Inc. | Information retrieval system and method |
| US4972349A (en) * | 1986-12-04 | 1990-11-20 | Kleinberger Paul J | Information retrieval system and method |
| US4823310A (en) * | 1987-08-10 | 1989-04-18 | Wang Laboratories, Inc. | Device for enabling concurrent access of indexed sequential data files |
| US4930072A (en) * | 1987-08-31 | 1990-05-29 | At&T Bell Laboratories | Method for computing transitive closure |
| US5021943A (en) * | 1988-08-01 | 1991-06-04 | Motorola, Inc. | Content independent rule based options negotiations method |
| US5050071A (en) * | 1988-11-04 | 1991-09-17 | Harris Edward S | Text retrieval method for texts created by external application programs |
-
1989
- 1989-10-24 CA CA002001390A patent/CA2001390C/en not_active Expired - Fee Related
- 1989-12-18 DE DE68926849T patent/DE68926849T2/de not_active Expired - Fee Related
- 1989-12-18 EP EP89313180A patent/EP0375307B1/en not_active Expired - Lifetime
- 1989-12-19 JP JP1329400A patent/JP2771288B2/ja not_active Expired - Lifetime
-
1993
- 1993-02-16 US US08/018,473 patent/US5546571A/en not_active Expired - Lifetime
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8209440B2 (en) | 2008-05-30 | 2012-06-26 | Fujitsu Limited | Device-configuration-information optimum arrangement method and device-configuration-information optimum arrangement system |
| JP2013016112A (ja) * | 2011-07-06 | 2013-01-24 | Nippon Telegr & Teleph Corp <Ntt> | チャンク生成装置、チャンク読み取り装置、チャンク生成方法及びプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0375307A2 (en) | 1990-06-27 |
| EP0375307A3 (en) | 1992-06-03 |
| CA2001390A1 (en) | 1990-06-19 |
| CA2001390C (en) | 1997-12-30 |
| DE68926849D1 (de) | 1996-08-22 |
| EP0375307B1 (en) | 1996-07-17 |
| JP2771288B2 (ja) | 1998-07-02 |
| US5546571A (en) | 1996-08-13 |
| DE68926849T2 (de) | 1996-11-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH02212972A (ja) | データベース操作方法 | |
| US10585867B2 (en) | Systems and methods for generating partial indexes in distributed databases | |
| EP1222569B1 (en) | Method and systems for making olap hierarchies summarisable | |
| US7769769B2 (en) | Methods and transformations for transforming metadata model | |
| US7814042B2 (en) | Selecting candidate queries | |
| US6424967B1 (en) | Method and apparatus for querying a cube forest data structure | |
| US5717924A (en) | Method and apparatus for modifying existing relational database schemas to reflect changes made in a corresponding object model | |
| US7246108B2 (en) | Reusing optimized query blocks in query processing | |
| US6334125B1 (en) | Method and apparatus for loading data into a cube forest data structure | |
| US8612468B2 (en) | System and method for retrieving data from a relational database management system | |
| JP3914662B2 (ja) | データベース処理方法及び実施装置並びにその処理プログラムを記憶した媒体 | |
| US7356542B2 (en) | DML statements for densifying data | |
| EP1081610A2 (en) | Methods for transforming metadata models | |
| Lee et al. | Path dictionary: A new access method for query processing in object-oriented databases | |
| US7827153B2 (en) | System and method to perform bulk operation database cleanup | |
| US7415461B1 (en) | Apparatus and method for merging results of approximate matching operations | |
| US8452757B2 (en) | Index mechanism for finding nearest matches in a computer system | |
| US8195712B1 (en) | Lattice data set-based methods and apparatus for information storage and retrieval | |
| US7406469B1 (en) | Linear instance mapping for query rewrite | |
| Fong et al. | Data conversion rules from network to relational databases | |
| CA2318302C (en) | Methods and transformations for transforming metadata model | |
| Chao et al. | Estimating temporary files sizes in distributed realtional database systems | |
| Whang | A Physical Database Design Methodology Using the Property of Separability. | |
| Whang et al. | The property of separability and its application to physical database design | |
| CN100547584C (zh) | 在关系数据库系统中用于使数据稠密的dml语句 |