JPH09190452A - データベース質問をコンピュータで実行する方法 - Google Patents

データベース質問をコンピュータで実行する方法

Info

Publication number
JPH09190452A
JPH09190452A JP8311770A JP31177096A JPH09190452A JP H09190452 A JPH09190452 A JP H09190452A JP 8311770 A JP8311770 A JP 8311770A JP 31177096 A JP31177096 A JP 31177096A JP H09190452 A JPH09190452 A JP H09190452A
Authority
JP
Japan
Prior art keywords
predicates
predicate
relation
question
new
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.)
Pending
Application number
JP8311770A
Other languages
English (en)
Inventor
Alon Yitzchak Levy
ワイ．レビー アロン
Inderpal Singh Mumick
エス．マーニック インダーパル
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.)
Nokia of America Corp
Original Assignee
Lucent Technologies Inc
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 Lucent Technologies Inc filed Critical Lucent Technologies Inc
Publication of JPH09190452A publication Critical patent/JPH09190452A/ja
Pending 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/2453—Query optimisation
    • G06F16/24534—Query rewriting; Transformation
    • G06F16/24537—Query rewriting; Transformation of operators
    • 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/24554—Unary operations; Data partitioning operations
    • G06F16/24556—Aggregation; Duplicate elimination
    • 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
    • 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
    • Y10S707/99934—Query formulation, input preparation, or translation

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

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、集合制約（aggreg
ation constraint）を正規制約（ordinary constrain
t）に変換する方法に関し、特にデータベース質問の最
適化の際に用いられる方法に関する。
【０００２】
【従来の技術】データベースシステムは、大量のデータ
を蓄積し、アクセスするのに広く用いられている。シス
テムユーザは、蓄積されたデータが組織化された方法を
利用する質問により、蓄積されたデータの一部にアクセ
スすることができる。多くの現在のデータベースシステ
ムは、リレーショナルデータベースシステムである。こ
のようなシステムにおいては、データは一組の関係（リ
レーション）に組織化され、各リレーションはデータの
クラスを規定する属性（attribute）と称するコラム
（列）とデータの関連値を含むチュープル（tuple）と
称するロウ（行）とを有する。例えば、会社の従業員に
関する情報は、４個の属性を有する従業員リレーション
（relation）に蓄積可能である。第１の属性は各従業員
の名前を含み、第２の属性は各従業員の給与を、第３の
属性は各従業員の地位を、そして第４の属性は、各従業
員の就業開始日を含む。各チュープル、即ちロウ（行）
は、一人の従業員に対するこれら４種類のクラスの情報
の全てを含む。
【０００３】２種類のリレーションが、リレーショナル
データベースシステム内に存在する。１つはベースリレ
ーションで、その中にデータ値が実際に蓄積され、もう
１つはビューリレーションで、これは特定の質問を解決
する際に中間ステップとして、ベースリレーションから
構成される。リレーショナルデータベースシステムに、
提出される質問は、この質問に応答して情報が発見され
るこれらのリレーションを表す。この質問（query）
は、関連情報の範囲の境界を定める述語（predicate）
を提供する。例えば、＄３０，０００以上稼ぐ全ての従
業員の名前に対する質問は、「給与が＄３０，０００以
上である」という述語を有する。データプロセッサが、
この質問に対する解答を得るために、上記の代表的な従
業員のリレーションを見ようとすると、これらのチュー
プルのみからそのサラリーの属性が＄３０，０００以上
である関連情報を選択する。このため、「給与が＄３
０，０００以上である」＝この質問に対する解答の制約
である。
【０００４】何種類かの質問は、集合を伴う。集合が発
生するのは、必要な情報が単一のチュープルの属性では
なく、複数のチュープルに跨る関数を適用した結果であ
るような場合である。集合の関数の例は、ＭＩＮ，ＭＡ
Ｘ，ＳＵＭ，ＡＶＧ，ＣＯＵＮＴを含む。集合関数のよ
り完全なリストは、Jim Melton and Alan R. Simon,著
の「 Understanding the New SQL: A Complete Guide
(Morgan Kaufmann Publishers Inc. 1993)」に開示され
ている。寄り集まりの属性に対する制限に関連する述語
は、集合述語として知られている。集合述語の一例は、
＄３０，０００以上稼ぐ従業員の数を見いだすという質
問である。この質問に対する解答は、従業員の名前の属
性にＣＯＵＮＴ関数を適用することである。
【０００５】しばしば、質問に対する解答は、１つある
いは複数の小質問（Subquery）を解決する中間ステップ
に関連する。例えば１０の部門（division）を有する会
社は、各部門に対し従業員のリレーションのデータベー
スを有する。「会社の中の全ての従業員から最も高い給
与の従業員を見いだせ」という質問があると、データプ
ロセッサシステムは、この解答に対し、１つのリレーシ
ョンのみをサーチすることはできない。その代わりに、
データプロセッサシステムは、各リレーションの中で最
も給与の高い従業員を探しだし、各部門内の最高給与の
従業員からなるビューリレーションを生成する。このビ
ューリレーションが「各部門の最高給与の従業員を見い
だせ」という小質問に対する解答である。元の質問「会
社内で最高給与の従業員を探し出す」は、この小質問に
対する解答から給与の属性内に蓄積された最大値を有す
るチュープルを選択することにより得られる。
【０００６】多くのリレーショナルデータベースシステ
ムに対する質問は、ＳＱＬと称する言語で書かれる。Ｓ
ＱＬで記載された質問は、この項が質問に応答するデー
タが見いだされる属性を表すＳＥＬＥＣＴ項と、ＳＥＬ
ＥＣＴ項内で命名された属性が見いだされるそれらのリ
レーションを表すＦＲＯＭ項と、ＳＥＬＥＣＴ項内で命
名された１つあるいは複数の属性に適用されるべき述語
を表すＷＨＥＲＥ項を有する。
【０００７】以下の説明は、ＳＱＬの質問の一例で、図
４には図１の２つのベースリレーションに基づいて、そ
の解答が図２，３の２つのビューリレーションを解く中
間ステップを必要とするような calls（１０）と顧客
（customers）（１１） と潜在的顧客（ptCustomers）
（２０）と wellCalled（３０）とが示されている。こ
の質問は、誰からでもかかってくる最長の呼が比較的短
いようなエリアコード（市外局番）に長い呼を行ったこ
とのある顧客に目標を定めて郵便を発送するための情報
を収集するマーケッティング関連の質問である。この質
問は、その検索（サーチ）を特定のエリアコードに長期
に亘って電話をかける顧客に制限している。この質問に
対する解答は、２つのベースリレーションから２つのビ
ューリレーションを先ず規定することである。
【０００８】図１の２つのリレーションは、前年度に電
話ネットワークを介して成された、全ての電話の呼に関
係する情報を含む。リレーションの calls（１０）は、
ネットワーク上の呼に関係する情報を蓄積し、この情報
には発信エリアコードと番号（ＦｒｏｍＡＣとＦｒｏｍ
Ｔｅｌ）と宛先エリアコードと番号（ＴｏＡＣとＴｏＴ
ｅｌ）と呼の長さと日付が含まれる。ネットワーク上の
エリアコードを含む各番号は、チュープルに関連し、そ
して６個の属性は、各番号に蓄積された６種類の情報を
表す。各顧客の名前、そのエリアコード（ＡＣ）と電話
番号（Ｔｅｌ）とネットワーク内の会員レベル（通常、
silver, gold）（MemLevel）が customers（１１）内に
蓄積される。したがって、このリレーションは、それぞ
れが４個の属性を有する各顧客に対するチュープルを含
み蓄積された情報の４種類のタイプを表す。
【０００９】ptCustomers（２０）は、その会員レベル
がシルバーである顧客のみを考慮し、各これらの顧客か
らあらゆるエリアコードに掛けられた最長長さの呼を計
算し、最長長さの呼とそのエリアコードに電話を掛けた
顧客の最も早い日付を計算する。wellCalled（３０）
は、前年度にネットワークを介して成された全ての呼の
中で、各エリアコードに成された最長呼を計算する。図
４の質問は、特定のエリアコードに対して最初の呼を１
９９４年４月１日以前に行い、そのエリアコードへの最
長の呼が１０分以上で、そして且つこれらのエリアコー
ドには誰もが１００分以上の電話を掛けたことがないよ
うな場所であるような顧客を識別する ptCustomers（２
０）からのチュープルを選択する。この最長長さと最も
早い日付は、それぞれ calls（１０）の日付属性と長さ
属性に対し、ＭａｘとＭｉｎの集合関数を適用すること
により計算できる。
【００１０】この質問とビュー定義の両方は、Select-F
rom-Where 項を利用する。質問は、属性内に蓄積された
情報、ＡＣ，Ｔｅｌ，ＭａｘＬｅｎ，ＭｉｎＤａｔｅを
ＳＥＬＥＣＴし、wellCalled（３０）と ptCustomers
（２０）をＦＲＯＭし、wellCalled（３０）の属性Ｔｏ
ＡＣ内に蓄積された情報が ptCustomers（２０）の属性
ＴｏＡＣ内に蓄積された情報と、wellCalled（３０）の
属性ＭａｘＬｅｎに蓄積された値が１００以下で、 ptC
ustomers（２０）の属性ＭａｘＬｅｎ内に蓄積された値
が１０以上で、 ptCustomers（２０）の属性ＭｉｎＤａ
ｔｅ内に蓄積された情報が１９９４年４月１日以前であ
るような同一の情報であるようなＷＨＥＲＥでこれらの
チュープルに対してのみ行う。
【００１１】同様に図２，３のSelect-From-Where 項
は、ベースリレーションcalls（１０）とcustomers（１
１）に基づいて、それぞれビュー ptCustomers（２０）
と wellCalled（３０）を規定する。Select-From-Where
項以外にもビューリレーションは、Groupby 項によっ
ても規定できる。この Groupby項は、特定された属性に
対し、同一の値を有するリレーションを規定する全ての
チュープルを、ビューリレーション内の単一のチュープ
ルに結合することにより、ビューのチュープルを規定す
るのを補助する。例えば図２において、 calls（１０）
内で属性ＴｏＡＣに蓄積された同一情報を有する全ての
チュープルと、ベースリレーションの customers（１
１）内に属性ＡＣとＴｅｌ内に蓄積された同一情報を有
する全てのチュープルは、ptCustomers（２０）内の単
一のチュープルに結合される。
【００１２】多くのデータベースは、大規模であるがた
めに質問に対する効率的な応答が必要不可欠である。質
問最適化「query optimization」という用語は、質問に
応答するのに必要な時間とメモリ資源を減少するため
に、必要な計算を組織化するのに用いる技術を意味す
る。最適化の方策は、質問を解決するために計算しなけ
ればならない述語の数を減少し、この述語をできるだけ
早く、適用することである。このため最も給与の高い従
業員を見いだすという質問は、ビューリレーションを構
成する際に最大サラリー述語を適用することにより最適
化される。
【００１３】できるだけ早く述語を適用する様々な技術
が公知であるが、これらは通常、質問再書き込みアルゴ
リズム「query rewrite algorithms」と称する。これら
の技術のあるものは、「predicate push-down techniqu
es」と称し、これは JeffreyD. Ullman 著の「Principl
es of Database and Knowledge-Base Systems, (Comput
er Science Press 1989)」に開示されている。
【００１４】関連する特許出願として、Query Optimiza
tion by Predicate Move-Aroundという名称の米国特許
出願第 08/254,215号（出願日１９９４年６月６日）に
は、質問グラフ（query graph） 近傍で、述語をそのア
プリケーションが最も高率となるような特定のノードに
移行させる一般的最適化技術が記載されている。この質
問グラフは、質問の小質問（subquery）と、ビューがブ
ロック、あるいはノードを形成するような質問の絵画的
表示である。この質問グラフの使用は、公知である、例
えばその文献としては、Inderpal S. Mumick, et al.
著の「Magic isRelevant, in Proceedings of ACM SIGM
OD, at 247-58 (International Conference on Managem
ent of Data, May 23-25, 1990) 」の論文と、Hamid Pi
rahesh,et al. 著の「Extensible/Rule Based Query Re
write Optimization, in Starburst, in Proceedings o
f ACM SIGMOD at 39-48 (International Conference on
Management of Data, June 2-5, 1992)」の論文と、Ind
erpal S. Mumick と Hamid Pirahesh 著の「Implementa
tion of Magic in Starburst, in Proceedings of ACM
SIGMOD (International Conference on Management of
Data, May 25-27,1994)」の論文と、Alon Levy, et al.
著の「Query Optimization by Predicate Movearound,
in Proceedings of the 20th International Conferen
ce on Very Large Databases at 96-107 (Jorge Bocca,
et al., eds. September 12-15,1994)」の論文が上げ
られる。
【００１５】決定サポートシステム（decision-support
systems）のような高級なデータベースアプリケーショ
ンにおいては、質問は、それは多くの小質問とビューに
より非常に複雑となる。これらの複雑な質問を従来方法
により最適化することは困難である。その理由は、これ
らの複数の質問を表す質問ブロックは、常時合併できる
というものではなく、従来のコストをベースにしたプラ
ンオプティマイザ（plan optimizers） は、一時に１つ
の質問ブロックしか扱うことができず、そのために適用
が難しい。特にプランオプティマイザは、集合に関連す
る質問を処理するのには非効率的である。
【００１６】集合述語は、大きなデータベースアプリケ
ーションにおいては、非常に重要である。このような大
きなデータアプリケーションでは、複雑な決定支援質問
（decision-support queries）は、複数のベースリレー
ションに１つあるいは複数の異なる集合関数を適用し、
そして、多くの述語を集合ビューに適用することにより
データを取り出さなければならない。一方、集合は、公
知の技術による質問の最適化を困難にし、時にはそれを
不可能にするが、集合は必要不可欠なものであり、集合
質問の最適化は、集合述語の操作に関連し、大きなスケ
ールのデータベースシステムにとっては必要不可欠なも
のである。
【００１７】集合述語を操作することが重要なのは、質
問の最適化の場合だけでなく、ロジックプログラミン
グ，制約プログラミング，制約データベース，グローバ
ルインフォメーションシステム等の他のアプリケーショ
ンについても言えることである。例えば、グローバルイ
ンフォメーションシステムにおいては、述語をプッシュ
ダウンする技術では、多くの入手可能な外部データベー
スの内、どれがある質問に関連しているかを決定するた
めに質問グラフを用いている。集合述語が関連している
ような場合には、集合述語を操作する方法が必要とな
る。
【００１８】集合に関連する質問を最適化する従来の方
法は、その最適化能力に限界があった。例えば、Kennet
h Ross, et al. 著の「Foundations of Aggregation Co
nstraints, in, Principles and Practice of Constrai
nt Programming (Alan Borning, ed. 1994. LNCS 874)
」では、著者は、わずか２つの特定の集合のケースを
考慮しているだけである。この第１のケースは、ビュー
における単一のgroupby操作に関連し、これらは任意の
線形制約（arbitrary linear constraints）を含む述語
を推論するためにイントラ−リレーションの推論手順を
提供する。第２の場合においては、著者は、グループ分
け操作（grouping operation）内で単一の集合関数のケ
ースを取り扱うビュー−トゥ−リレーション（view-to-
relation）推論手順を提供している。しかし、制約言語
と与えられたフレームワークの理由付けは、質問を最適
化するのに必要な様々な種類の述語の推論を可能にして
いない。
【００１９】関連した小質問内の集合を有する質問を最
適化することに対し、次に述べるマジックセットのトラ
ンスフォーメンションにより脱相関（decorrelation）
と小質問をビューに変換する方法により、相関する小質
問内の集合を有する質問を最適化することに対する研究
が行われている。これに関しては、Won Kim 著の「OnOp
timizing An SQL-Like Nested Query, in, ACM Transac
tions on Database Systems, (September 1982)」と、R
ichard A. Ganski と Harry K. T. Wong. 著の「Optimi
zation of Nested SQL Queries Revisited, in, Procee
dings of ACMSIGMOD at 23-33 (International Confere
nce on Management of Data, May 1987)」と、Umeshwar
Dayal 著の「Of Nests and Trees: A Unified Approac
h toProcessing Queries that Contain Nested Subquer
ies, Aggregates, and Quantifiers, in, Proceedings
of the Thirteenth International Conference on Very
Large Databases VLDB at 197-208 (September 1-4, 1
987)」と、M. Muralikrishna 著の「Improved Unnestin
g Algorithms for Join Aggregate SQL Queries, in, P
roceedings of the Eighteenth International Confere
nce on Very Large Databases VLDB at 91-102 (August
23-27, 1992)」と、Mumick 著の「Magic is Relevant,
supra; and Mumick, Implementation of Magic in Sta
rburst,supra」に記載されている。
【００２０】Surajit Chaudhuri と Kyuseok shim 著の
「Including Groupby in Query Optimization, in, Pro
ceedings of the 20th International Conference on V
eryLarge Databases at 354-66 (Bocca et al., eds.,
September 12-15, 1994) 」は、同一の質問ブロック内
で、ジョイン操作あるいはセレクション操作を行う前
に、グループ分け操作を実行することが可能であるとい
うことを教示している。脱相関とジョインとグループ分
け（grouping）を交換することは、質問グラフが与えら
れた一組の述語の構造を変化することになるが、与えら
れた質問を解くために最も最適な述語を提供することは
できない。
【００２１】
【発明が解決しようとする課題】したがって本発明の目
的は、１つの述語あるいは両方の述語が集合述語である
ような２つの述語の間の関係（relationship）を表す手
段を提供することである。さらに本発明の目的は、全て
の集合述語が関数ターム（functional terms）によって
表されるような新たな制約言語を教示するものである。
【００２２】さらに本発明の目的は、データベースアプ
リケーション内の集合述語を操作する方法を提供するこ
とである。そして特に本発明は、集合に関連するデータ
ベース質問に対し、解答を最適化する方法を提供するこ
とである。さらにまた本発明の目的は、全ての集合述語
は、関係（relationship）が示され、そして新たな述語
が推論されるような形態で表すことである。
【００２３】
【課題を解決するための手段】本発明によれば新たな述
語は、表現形式（representative form） の集合述語を
含む一組の初期述語から推論される。別法として本発明
のこれらの表現形式における集合述語は、質問に対する
解答を最適化する際に、有効な新たな述語を取り出すこ
とはないが、推論が行われる一組の初期述語から取り出
されるものである。さらに本発明の方法は、表現形式
（representative form） における集合述語を識別する
方法を提供する。このような表現形式は、質問に対する
解答を最適化するのに有益な新たな述語を取り出すこと
に関連するものである。所望の最適化体系に従って、全
ての推論を引きだした後、完全な組の述語（初期で且つ
新たな）は、冗長且つ自明（axiomatic） の推論を削除
し、そしてこれらの推論は、その表現形式の中で残留す
るものである。
【００２４】
【発明の実施の形態】本発明による集合述語を操作する
第１ステップとしては、集合述語を表す制約言語を規定
することが必要である。この制約言語は、複数の集合述
語の間の関係（relationship）が示される形態で表示し
なければならない。本発明によるこのような有益な制約
言語は、集合に関連する述語のクラスを指定する（数
１）の関数（functional term） を用いる。この式にお
いて、Ｒはリレーションかベースかビューを表す。Ｘ
（このＸの下線は、（数１）における上付きのバーを表
し、以下同様とする）は、関係Ｒの属性を表し、グルー
プ分けリストを構成する。Ａは、関係Ｒの属性Ｙに適用
される集合関数（functional）を表す。例えば、Ａ1に
亘ってグループ分けされた、関係Ｒの属性Ａ2 の最大値
は、常にＡ2 の最小値以上である。複数の集合述語間の
関係は、以下のように示すことができる。
【数２】
【００２５】複数の集合述語の間の関係が示されると、
複数の集合述語を含む初期の組の述語から新たな述語を
推論するフレームワークが得られる。異なる最適化系
は、異なるタイプの推論を必要とし、且つ質問を最適化
するために関連する推論された述語を指図するが、初期
の組の述語から新たな述語を推論する能力は、それらが
全て共有しなければならない必須要件である。上記のよ
うな関数により集合述語を表すことにより、推論は複数
の集合述語から引き出され、それ故に集合を含む質問を
最適化し、同時にまた他のデータベースのアプリケーシ
ョンを最適にする。
【００２６】単純な例として例えば、リレーションＲ
（Ａ，Ｂ，Ｃ）で、Ａ，Ｂ，ＣはＲの属性であり、述語
Ｃ1 はリレーションＲ内の各チュープルに対し、Ｂ内の
データは、Ｃ内のデータ以下である、即ち数３の場合を
考える。
【数３】 すると３個の新たな述語Ｃ2 ，Ｃ3 ，Ｃ4 がＣ1 から推
論され以下の３つの式が得られる。
【数４】 上記の式は、リレーションｐ内の全てのチュープルに対
し、Ｂ内の値はＣ内の値以下であり、その場合グループ
分けされた属性の特定の組の全てのチュープルに対し、
Ｂの最小値は、Ｃの最小値以下であることを意味し、
【数５】 上記の式は、グループ分けされた属性のある所定の組の
全てのチュープルに対し、Ｂの最小値は、Ｂの最大値未
満であることを意味する。
【００２７】関係式（２）から下記の新たな述語が推論
できる。
【数６】
【００２８】関係式（３）から別の新たな述語が推論で
きる。
【数７】
【００２９】関係式（１）と述語Ｃ2，Ｃ3から第３の新
たな述語が推論できる。
【数８】
【００３０】初期の組の述語から新たな述語を推論する
ために３種類の推論が通常用いられる。第１のタイプで
あるリレーション−トゥ−ビュー（relation-to-view）
推論を用いてビューに関連する項とビューを規定する関
係式に関連する項との間の関係式を推論し、規定するリ
レーション上の初期の述語からビュー上の新たな述語を
導き出す。第２のタイプの推論は、イントラ−リレーシ
ョン（intra-relation）推論である。これは、同一のリ
レーションに関連する複数の項の間の新たな関係式を導
出するために用いられる。第３のタイプの推論は、ビュ
ー−トゥ−リレーション（view-to-relation）推論であ
る。これはリレーション−トゥ−ビュータイプの逆のも
のであり、リレーションにより規定されたビュー上の述
語からリレーション上の新たな述語を導出するために用
いられる。
【００３１】これら３種類の推論のタイプは、Hamid Pi
rahesh, et al.著の「Extensible/Rule Based Query Re
write Optimization in Starburst, supra」に記載され
た Starburstオプティマイザのような質問オプティマイ
ザあるいは述語 move-aroundアルゴリズムに自然と適合
する。リレーション−トゥ−ビュー（Relation-to-vie
w）推論は、述語ムーブアラウンドの述語プルアップフ
ェーズ内で実行され、ビュー−トゥ−リレーション推論
は、プッシュダウンフェーズ内で実行される。そしてイ
ントラ−リレーション推論は、質問グラフのノード内
で、述語の減少的閉鎖（deductive closure） を実行し
ながら両方のフェーズで行われる。
【００３２】上記の制約言語でもって、新たな組の述語
を得るために集合述語でもってリレーション−トゥ−ビ
ュー推論とイントラ−リレーション推論とビュー−トゥ
−リレーション推論とを行うことが可能となる。以下に
代表的な関係式と表現形式の集合述語に関連する推論を
３種類の推論の各々に対し示す。
【００３３】１．リレーション−トゥ−ビュー推論この
リレーション−トゥ−ビュー推論においては、複数の属
性間の述語と、ビューの関数とは、リレーションの述語
から推論できる。このリレーションは、selection, pro
jection, cross product, union, grouping, aggregati
on 等の操作を組み合わせることによってビューを規定
する。図７の代表的なビューＶ７０についてを参照する
と、Ｖ７０の属性は、リレーションＥ1 とＥ2 の属性か
ら得られる。ビューのチュープルは、Ｅ1 内のチュープ
ルのサブセットであるので、Ｖ７０に対する最大値は、
Ｅ1 からの最大値以上にはなり得ない。この関係を次に
示す。
【数９】
【００３４】リレーション−トゥ−ビュー推論は、ビュ
ーがどのように規定されるかによって、様々な関係式と
なる。ビューＶは、別のリレーションＥの属性のサブセ
ットの projection により規定される。Ｖ，Ｘ1 の属性
のセットは、Ｅ，Ｘ2 の属性のセットのサブセットであ
る。すると属性Ｙを含むＶの属性のグルーピングに対し
ても、同一のグループがＥに対し存在する。したがっ
て、Ｖ内のＹに対し、ＭＡＸあるいはＭＩＮ関数を適用
することは、Ｅ内のＹにＭＡＸあるいはＭＩＮを適用す
ることに等しい。これは次のように表される。
【数１０】 ここでＡは、ＭＡＸあるいはＭＩＮの集合関数のいずれ
かである。
【００３５】複製物が保存される場合、言い換えるとＥ
内の全ての類似値（like-value）チュープルは、個々の
チュープルと同様にビュー内で projectされる場合に
は、ＳＵＭ，ＡＶＧ，ＣＯＵＮＴの関数に対し真実とな
る。複製物が保存されていない場合には、下記の式数１
１が、ＳＵＭ，ＣＯＵＮＴ集合関数に対し当てはまる。
【数１１】
【００３６】ビューＶは、規定リレーション（defining
relation）Ｅ の全ての属性の１部あるいは全部のチュ
ープルの selectionにより規定される。Ｖは、Ｅよりも
少ない数あるいは同一の数のチュープルを有する。した
がって、グルーピングリスト（grouping list） ＸがＸ
1 のサブセットであり、ＹがＸ1 の属性の場合には以下
の関係式が存在し、上記の制限言語を用いて以下のよう
に示すことができる。
【数１２】
【００３７】Ｖが、一組の属性Ｘ1 であるリレーション
Ｅ1 と一組の属性Ｘ2 であるリレーションＥ2 とのクロ
スプロダクトの結果である場合（Ｘ1 とＸ2 は異なる）
には、別の組の関係式が成立する。この場合にＶは、両
方の組の属性Ｘ1 とＸ2 を有する。Ｘ1 のサブセットで
ある属性の各グループと（ここでＹは、Ｘ1 の属性であ
る）の場合には次式の関係式が成り立つ。
【数１３】 ここでサイズ（Ｅ2 ）は、リレーションＥ2 内のチュー
プルの数である。
【００３８】Ｖは、２つのリレーションＥ1，Ｅ2 の un
ion により規定でき、この両方のＥ1 ，Ｅ2 は属性Ｘ1
の同一の組を有する。この場合次式の関係式が成り立
ち、上記の関数（functional ferms）でもって表すこと
ができる。
【数１４】
【００３９】Ｖの属性は、Ｅの属性のいくつかをグルー
プ分け（grouping）し、Ｅの１つあるいは複数の他の属
性に集合関数を適用することにより規定できる。ここで
グルーピングリストは、Ｘ1 で規定され、且つ集合関数
の組と対応する集合した属性は、共にＺとして示され、
属性のリストＸ1 上のＥ内の特定の属性Ｙi 上に特定の
関数Ａi が、Ｖ内のＺi に等しいような関係式は、以下
に示される。ここでＺi＝Ａi（Ｙi）
【数１５】 さらにＶ内の属性のＭＡＸとＭＩＮは、Ｅ内の同一属性
のＭＡＸとＭＩＮに等しい。ここでＶとＥは、同一の g
rouping リストを有し、以下で示される。
【数１６】 しかし、Ｖ内の属性のＣＯＵＮＴは、Ｅ内の同一属性の
ＣＯＵＮＴ以下である。その理由は、ＶはＥよりもより
少ないチュープルを有するからである。
【数１７】
【００４０】２．イントラ−リレーション推論質問の最
適化に対し、重要な第２のタイプの推論は、イントラ−
リレーション推論である。これらの推論は、同一のリレ
ーションの複数の関数間の述語を推論するのに用いられ
る。同一のリレーションに関係する複数の関数間の関係
式は、集合関数が変化し、groupby リストが変化し、あ
るいは集合属性が変化するような関数（funcional term
s）に関連する。特殊な関係式は、集合した属性が grou
pingリストのメンバーである場合に推論される。
【００４１】イントラ−リレーション推論の一例とし
て、ある属性の最大値は、その属性の最小値以上である
場合を考える。同様にある属性の最大値は、その属性の
全ての値の平均以上である。これらの関係式は、異なる
集合関数を有する項に関係し、次式で表される。
【数１８】 集合関数のみが変化するような同様なイントラ−リレー
ション推論は、Keneth Ross, et al. 著の「Foundation
s of Aggregation Constraints, supra.」に見いだされ
る。これらの関係式は、syntax を用いて表現できる。
【００４２】別のイントラ−リレーション推論は、grou
ping リストＸ1 は、第２の関数のgrouping リストＸ2
のサブセットであるような１つの関数に関連する。例え
ば本発明の制約言語を用いると以下のように表すことが
できる。
【数１９】
【００４３】第３のイントラ−リレーション推論は異な
る集合属性を有する２つの関数に関連する。同一のグル
ーピングに対しては、各リレーション内のチュープルの
数が同一でチュープルの数に等しいカウントＣＯＵＮＴ
は、両方の属性に対し、同一である。このことは、次式
で示される。
【数２０】 さらにまたＲ内の各Ｙ1 が、各Ｙ2 以下の場合には、次
式が成立する。
【数２１】 Ｙ1 が定数Ｋ未満の場合には、上記の関係式は、以下の
ように単純化できる。
【数２２】
【００４４】第４のイントラ−リレーション推論は、 g
rouping リスト内の属性の１つである集合属性に関連す
る。この場合、属性Ｘi 内の各値に対し、１個のチュー
プルのみが存在するだけであるので、各チュープルに対
するＸiの maximum, minimumあるいは平均は、そのチュ
ープルのＸi の値である。このことは次式で表すことが
できる。
【数２３】
【００４５】３．ビュー−トゥ−リレーション推論最後
にビュー−トゥ−リレーション推論を用いて、リレーシ
ョンにより規定されるビューに関連する１つあるいは複
数の初期述語からリレーション上の述語を推論する。ビ
ューが集合関数に関係する場合には、このビュー−トゥ
−リレーション推論は、ビューに無関係な定義リレーシ
ョン（defining rilation）内のこれらのチュープルを
削除することにより計算をより単純にする事ができる。
したがって、このビューは、より少ないチュープルに対
する集合（aggregating）を行うことにより計算可能で
ある。
【００４６】以下の例を用いて、リレーション上のどの
述語が selectionにより規定されるビューＶから推論で
きるかをいかに決定するかを説明する。述語は、以下に
示すように、集合関数を含む初期の組の述語から推論可
能である。一組の非集合述語Ｘと、一組の集合述語Ｚを
有するビューＶを規定するリレーション内で適用される
一組の述語は、Ｚに関連しないＶ内の全ての述語を含
む。ここで各Ｚi に対する特定の集合関数Ａi は、ＭＡ
ＸあるいはＭＩＮディレクションで集合述語Ｚiは、対
応するＹi 項により置換される。
【００４７】一例を示すとＶは、属性Ｘ1 ，Ｘ2 ，Ｚ
1 ，Ｚ2 を有し、ここで、Ｚi ＝Ａi（Ｙi ）と述語
（Ｘ1 ≦Ｘ2 ），（Ｚ1 ≧５），（Ｚ2 ≦２）を有する
と仮定する。ここでＡ1 ＝ＭＡＸ，Ａ2 ＝ＭＩＮであ
る。述語（Ｘ1 ≦Ｘ2 ）は、Ｖの計算に適用される、言
い換えるとＶのグルーピング操作（grouping operatio
n）の前に適用される。その理由は、それはグルーピン
グ操作から得られたＶとＥ内の同一の値を有する全体の
グループに適用されるからである。さらにまたＹ1 が５
よりも大きいようなチュープルのみがＺ1 の計算に関係
し、同様にＹ2 が２よりも小さいチュープルのみがＺ2
の計算に関係する。しかし、Ｙ2≦２のチュープルは、
実際にはＹ1 の maximum を含むものであり、これら２
つの述語の結合（conjunction） は、Ｅ内では適用でき
ない。これらの述語分解（disjunction）である、（Ｘ1
≦Ｘ2）and（Ｙ2≦２ or Ｙ1≧５）は、Ｅ内で適用可能
である。
【００４８】この特殊な例から抽象的原理に移行するた
めに、集合に関連しないＶ内の全ての述語は、Ｅ内で適
用される。さらにまた変数あるいは定数以上のＺi に関
係する全ての述語（ここでＡi は、ＭＡＸ）あるいは変
数または定数以下のＺi に関係する全ての述語（ここで
Ａi は、ＭＩＮ）は、Ｅ内でＺi をＹi で置換すること
により適用される。集合関数ＡＶＧ，ＳＵＭ，ＣＯＵＮ
Ｔに関連する述語は、Ｅ内では適用されない。どの述語
もＶ内の集合に関連しない場合には、集合に関連しない
述語のみがＥ内で適用される。
【００４９】４．実施例本発明の一実施例を図４の質問
に適用した例を次に示す。上記した質問は、長時間電話
をある時間特定の領域に掛けた顧客に関する情報を求め
ている。３つの述語がこの質問の解答に関連する情報の
範囲を制限する。先ず第１に問題の領域への長時間電話
は、１００分未満でなければならない。第２に顧客のそ
の領域への長時間電話は、１０分以上でなければならな
い。第３の顧客のその領域への最も早い時期の電話の呼
は、１９９４年４月１日以前でなければならない。
【００５０】この質問に対する最適の解放プロセスは、
それぞれ図５のビュー wellCalled（５０）と、図６の
ptCustomers（６０）とを含む。これらのビューは、図
３，４のそれとは以下の点で異なる。第１に特定の領域
への長時間電話を全ての電話の呼から選択する前に、特
定の電話の呼の範囲は、１０分以上の電話の呼に制限さ
れる。この質問は、１０分以上の長電話にのみ関連する
ために、長電話を選択するプロセス（比較チュープルを
必要とする）は、１０分未満の全ての呼が、先ず削除さ
れ、より少しの比較されるべきチュープルが残される場
合にはより単純になる。
【００５１】第２にベースリレーション呼（１０）のチ
ュープルは、２つのベースリレーションを組み合わせ p
tCustomers（６０）内の選択された属性を集合する前に
は、１０分以上の長電話か、あるいは１９９４年４月１
日以前の電話のいずれかに制限される。ここでより効率
的にするには、質問の解答に対する影響を有しないチュ
ープルを取り除きそれにより後続の操作をより単純化す
ることである。
【００５２】最適のビュー（５０），（６０）に導かれ
る推論は、ここに開示した制約言語により表される関係
式に関連する。３種類の推論に対し、上記の関係式を参
照すると図５，６に示された新たな述語は次のようにな
る。関係式（３），（４），（７），（８）から潜在的
顧客ビュー（６０）とその規定リレーション呼（１０）
との間の新たな関係式ｃ１とｃ２は次のように表され
る。
【数２４】 関係式（２２），（２３）から同一のリレーション呼
（１０）の項の間の新たな関係式ｃ３，ｃ４が推論され
る。
【数２５】 関係式（１７）から新たな関係式ｃ５，ｃ６，ｃ７が推
論される。
【数２６】 関係式ｃ１，ｃ３から別の関係式ｃ８が推論される。
【数２７】 関係式ｃ５，ｃ６，ｃ７，ｃ８から容易に次のことが分
かる。
【数２８】 上記の式からさらに次のことが推論できる。
【数２９】 ｗ．ＴｏＡＣ＝ｐ．ＴｏＡＣであるので、述語（ｃ９）
ｗ．ＭａｘＬｅｎ≧ｐ．ＭａｘＬｅｎは、質問の中で推
論できる。この項から新たな述語ｃ１１が導かれる。
【数３０】 述語ｃ１２，ｃ１３は公知である。
【数３１】 ビュー−トゥ−リレーション推論を関係式ｃ１１，ｃ１
２，ｃ１３に適用することにより、新たなビュー wellC
alled （５０）に対し、述語ｃ１４をビューｐｔＯ（６
０）に対し、新たな述語ｃ１５が得られる。
【数３２】 これら２つの新たな関係式は、リレーション呼（１０）
に対する最終述語となる。
【数３３】
【００５３】前述したように、上記の推論が成される正
確な場所は、選択された最適化技術に基づいている。述
語 move-around最適化技術に対しては、述語は次の３段
階でもって推論される。次に図８において、同図は、図
４の質問グラフを示し、図９は、本発明のベーシックス
テップを表すフローチャートを示す。図４の質問は、本
発明を用いて最適化され、本発明と以下に述べる move-
around最適化技術を用いて最適化される。
【００５４】ブロック９１に示すように、集合に関連す
る質問から先ず初め、全ての集合述語は、ブロック９２
に示すようなその表現形式に変換される。一実施例にお
いては、これは関数数１を用いる。ブロック９３におい
て、新たな述語は、例えば、move-around 最適化技術の
ような選択の最適化技術を用いて推論される。
【００５５】初期化フェーズの間、ＳＥＬＥＣＴノード
は、それぞれのＷＨＥＲＥクローズ中に現れる全ての述
語を受領し、ＧＲＯＵＰＢＹノードは、それぞれのＷＨ
ＥＲＥクローズとＨＡＶＩＮＧクローズ内に現れる全て
の述語を受領する。より詳細な説明は、米国特許出願０
８／２５４，２１５を参照のこと。したがって、図４の
質問に対しては、関係式ｃ１−ｃ４，ｃ８，ｃ１２−ｃ
１３が推論され、それぞれのボックス内に配置される。
【００５６】述語pullup相の間、述語は、質問グラフか
らトップノードに、即ち、チャイルドノードからペアレ
ントノードに、推論される。例えば、ノード８３内の述
語を用いて、ノード８５内の述語を推論し、ノード８４
内の述語を用いて、ノード８６内の述語を推論する。従
って、関係式ｃ５ーｃ７が推論され、それぞれのペアレ
ントボックスにプルアップ（pullup）される。
【００５７】次に述語プッシュダウンフェーズにおい
て、述語はペアレントノード（parentnode）からチャイ
ルドノード（child node） へ推論される。図４の質問
に関しては、関係式ｃ９−ｃ１１とｃ１４−ｃ１６が、
推論されそれぞれのチャイルドボックスにプッシュダウ
ンされる。
【００５８】この時点でブロック９３は完了し、ブロッ
ク９４は、新たな述語は質問を解くのに有益か否かを決
定するために検査される。有益でない述語は、ブロック
９５で廃棄される。これらは最初に現れたときに適用さ
れるだけの２度以上現れる述語と、関数に関連する述語
と真実であると保証される述語とを含む。関数に関連す
る述語は、質問を解くプログラムがこの関数を認識しな
い場合には、除去する必要がある。質問を解く際に、関
数に関連する述語を実行するのは、コストが高いことが
予想されるので、オプティマイザプログラム（optimize
r program） だけは、複数の述語間の関係式を示し、新
たな述語を推論する関数を認識するよう設計される。か
くして関数に関連する述語は、ブロック９６で述語を解
く前に、ブロック９５で取り除かれる。
【００５９】今まで見てきた通り、関連関数に関する推
論を導き出すと、新たな述語となる。この新たな述語の
一部は、質問を最適化するが、そうでないものもある。
一般的に真実であることが保証されている自明的述語
は、役には立たない。さらに、集合関数に関連するこれ
ら新たな述語は、最適化により達成された効率を減少さ
せるために、実行するにはコストが高すぎる。このため
に、この理由により質問を最適化するのに役立たない、
これら新たな述語は、質問を解く前に廃棄される。
【００６０】新たな述語の一部のものは、質問を解くの
には、用いられないことがあるので、新たな有効な述語
とならないような最初の集合述語を識別することが望ま
しい。したがって、本発明の他の実施例においては、通
常の述語を導出するのに関連する関数のみを用いて、質
問を最適化するために新たな述語を推論する。この実施
例においては、新たな述語が推論された後、それらを取
り除く必要性は、これら新たな述語をまとめて回避する
ことにより減少する。新たな述語が推論される前に関数
に関連する初期述語を検査し、質問を最適化するのには
役立つことにはならない述語となるようなこれら述語を
識別する。そしてこれら新たな述語は廃棄される。この
追加された決定ステップは、図１０のブロック９７，９
８で示される。
【００６１】ブロック９７、９８を実行するために、関
数に関連する述語は、質問を最適化するのにも関連し、
（ｉ）質問が集合を行う際に、依存するリレーションＲ
あるいは質問が集合を行う際依存するビューを規定する
関係Ｒと、（ｉｉ）groupbyリストとＲ内の集合属性Ｙ
あるいは groupbyリストの projection とＲを規定する
別のリレーションの集合属性に関連するものとして識別
される。関連 groupbyリストと集合した属性対のセット
は、シンボルＧＬR で表される。
【００６２】関連関数は、質問グラフを用いても識別す
ることができる。Ｒは、全てのベースリレーションと、
質問グラフ内のノードを groupbyノードにフィーリング
する、あるいはノードを groupbyノードにラベル付けす
る関係内にリーディングするようラベルを付すようなリ
レーションを含む。
【００６３】ＧＬR は、対を含み groupbyリストＧＬ
は、Ｒにより供給される groupbyノード内で使用され属
性Ｙは、 groupbyノード内で集合され、groubyリストの
projection からなる全ての対と、属性ＹをＲに提供す
る関係式からなる。関数からＲとＧＬR に関連する、こ
れらの項への推論を制限することにより、関連する新た
な述語のみが得られる。
【００６４】図１，４，５−６，８において、Ｒは、ｐ
ｔＯ（２３）と、calls（８２）と、customers（８１）
とを含み、ＧＬptOは、２つの対（｛ＡＣ，Ｔｅｌ，Ｔ
ｏＡＣ，｝長さ）と（｛ＡＣ，Ｔｅｌ，ＴｏＡＣ｝，Ｄ
ａｔｅ）とを含み、ＧＬcalls は、３個の対（｛Ｆｒｏ
ｍＡＣ，ＦｒｏｍＴｅｌ，ＴｏＡＣ｝，長さ），（｛Ｆ
ｒｏｍＡＣ，ＦｒｏｍＴｅｌ，ＴｏＡＣ｝，Ｄａｔ
ｅ），（｛ＴｏＡＣ｝，長さ）とそしてＧＬcustomers
は、空のセットである。したがって、関連する関数のみ
と上記で識別されたリレーションに関連する項と、grou
pby リストと属性は、次のようになる。
【数３４】 実際には、図４の質問の最適化は、これらの関数にのみ
関連する。
【００６５】
【発明の効果】以上述べた本発明の方法は、汎用マイク
ロプロセッサで実現できる。関数（数１）は、読みだし
可能なメモリ内にストアされ、各集合述語をそれぞれの
表現形式に変換するステップは、ソフトウェアで実現で
きる。別法として、専用マイクロプロセッサを用いて、
一般的な関数と読みだし専用メモリＲＯＭ内にストアさ
れた変換ステップを用いて本発明の方法を実現できる。
いずれの実現方法においても読みだし可能なメモリは、
その表現形式で集合述語をストアするために具備し、質
問最適化技術を実現するのに必要なときまで蓄積するの
に具備される。この関数と上述した推論ルールは、制約
言語と述語解析用にオプティマイザが用いる推論メカニ
ズムの一部から構成される。
【図面の簡単な説明】
【図１】ＳＱＬ標示による calls と customers とのベ
ースリレーションを表す図
【図２】ＳＱＬ標示で表された図１のベースリレーショ
ンから構成されたビューptCustomers を表す図
【図３】ベースリレーションの calls から構成され
た、ＳＱＬ標示によるビュー wellCalled を表す図
【図４】ＳＱＬ標示による図２の２つのビューリレーシ
ョンから構成されたマーケッティング（marketing） 質
問を表す図
【図５】ＳＱＬ標示による最適化後の図３のビューを表
す図
【図６】ＳＱＬ標示による最適化後の図２のビューを表
す図
【図７】２つのリレーションＥ1，Ｅ2により規定され、
いかなる集合も含まない代表的ビューＶを表す図
【図８】図４の質問用の質問グラフを表す図
【図９】本発明の第１実施例を表すフローチャート図
【図１０】本発明の第２実施例を表すフローチャート図
───────────────────────────────────────────────────── フロントページの続き (71)出願人 596077259 600 Ｍｏｕｎｔａｉｎ Ａｖｅｎｕｅ, Ｍｕｒｒａｙ Ｈｉｌｌ， Ｎｅｗ Ｊｅ ｒｓｅｙ 07974−0636Ｕ．Ｓ．Ａ. (72)発明者 インダーパル エス．マーニック アメリカ合衆国，ニュージャージー、バー クレー ハイツ、スウェンソン サークル 85

Claims (32)

    【特許請求の範囲】
  1. 【請求項１】 １つあるいは複数の集合述語を有する初
    期の組の述語に関連する、データベース質問をコンピュ
    ータで実行する方法において、（Ａ）前記集合述語の少
    なくとも１つを前記集合述語に関連する関係式を表すの
    に適当な表現形式（representative form） に変換する
    ステップと、（Ｂ）前記初期の組の述語から前記表現形
    式を用いて、１つあるいは複数の新たな述語を推論する
    ステップと、（Ｃ）前記新たな述語を用いて前記データ
    ベース質問を解くステップとを有することを特徴とする
    データベース質問をコンピュータで実行する方法。
  2. 【請求項２】 前記表現形式は、下記の数式によりシン
    ボル化された関数であり、 【数１】 前記Ｒは、１つあるいは複数の属性を有するリレーショ
    ンであり、前記Ｘ（下線は関数式で上線を意味する）
    は、グループ分けされたＲの前記属性を表し、前記Ａ
    は、Ｒの属性Ｙに適用される集合関数であることを特徴
    とする請求項１の方法。
  3. 【請求項３】 前記（Ｂ）のステップは、前記他の述語
    からリレーション内の述語を推論するステップを含むこ
    とを特徴とする請求項１の方法。
  4. 【請求項４】 前記（Ｂ）のステップは、前記第１リレ
    ーションを規定する１つまたは複数の第２リレーション
    内の述語から第１リレーション内の述語を推論するステ
    ップを含むことを特徴とする請求項１の方法。
  5. 【請求項５】 前記（Ｂ）のステップは、前記第１リレ
    ーションにより規定される第２リレーション内の述語か
    ら第１リレーション内の述語を推論するステップを含む
    ことを特徴とする請求項１の方法。
  6. 【請求項６】 前記（Ｂ）のステップは、（Ｂ１）前記
    質問に関連する前記表現形式内の前記集合述語を識別す
    るステップと、（Ｂ２）前記表現形式内の前記関連集合
    述語から１つあるいは複数の新たな述語を推論するステ
    ップとを有することを特徴とする請求項１の方法。
  7. 【請求項７】 前記（Ｂ）のステップは、（Ｂ１）前記
    質問に関連する前記（数１）の式の前記集合述語を識別
    するステップと、（Ｂ２）前記（数１）の式の前記関連
    集合述語から１つあるいは複数の新たな述語を推論する
    ステップとを有することを特徴とする請求項２の方法。
  8. 【請求項８】 前記（数１）の式の関連集合述語は、Ｒ
    と groupbyリストと、集合属性対ＧＬR を含むものであ
    り、前記Ｒは、前記質問がそれにより集合を形成するリ
    レーションと、前記質問がそれにより集合を形成するビ
    ューを規定するリレーションとを含み、前記ＧＬR は、
    groupby リストとＲ内の集合した属性と、groupby リス
    ト内の projection と、Ｒを規定するリレーションの集
    合した述語とを含むことを特徴とする請求項７の方法。
  9. 【請求項９】 前記（Ｂ）ステップは、（Ｂ１）前記の
    新たな述語の１つあるいは複数が前記質問を解くのに有
    効であるか否かを決定するステップと、（Ｂ２）前記の
    有効でない新たな述語を削除するステップとを含むこと
    を特徴とする請求項１の方法。
  10. 【請求項１０】 前記（Ｂ）ステップは、（Ｂ１）前記
    の新たな述語の１つあるいは複数が前記質問を解くのに
    有効であるか否かを決定するステップと、（Ｂ２）前記
    の有効でない新たな述語を削除するステップとを含むこ
    とを特徴とする請求項２の方法。
  11. 【請求項１１】 前記（Ｂ２）のステップは、自明な述
    語を削除するステップを含むことを特徴とする請求項９
    または１０の方法。
  12. 【請求項１２】 前記（Ｂ２）のステップは、冗長な述
    語を削除するステップを含むことを特徴とする請求項９
    または１０の方法。
  13. 【請求項１３】 前記（Ｂ２）のステップは、表現形式
    の全ての述語を削除するステップを含むことを特徴とす
    る請求項９の方法。
  14. 【請求項１４】 前記（Ｂ２）のステップは、（数１）
    の式に関連する全ての述語を削除するステップを含むこ
    とを特徴とする請求項１０の方法。
  15. 【請求項１５】 前記（Ｂ）のステップは、述語プッシ
    ュダウン（pushdown）最適化技術を実行することを特徴
    とする請求項１または２の方法。
  16. 【請求項１６】 前記（Ｂ）のステップは、述語ムーブ
    −アラウンド（move-around） 最適化技術を実行するこ
    とを特徴とする請求項１または２の方法。
  17. 【請求項１７】 １つあるいは複数の集合述語を有する
    初期の組の述語に関連する、データベース質問を実行す
    るコンピュータシステムにおいて、（Ａ）前記集合述語
    の少なくとも１つを前記集合述語に関連する関係式を表
    すのに適当な表現形式（representative form） に変換
    する手段と、（Ｂ）前記初期の組の述語から前記表現形
    式を用いて、１つあるいは複数の新たな述語を推論する
    手段と、（Ｃ）前記新たな述語を用いて前記データベー
    ス質問を解く手段とを有することを特徴とするデータベ
    ースの質問を実行するコンピュータシステム。
  18. 【請求項１８】 前記表現形式は、前記（数１）の式に
    よりシンボル化された関数であり、前記Ｒは、１つある
    いは複数の属性を有するリレーションであり、前記Ｘ
    （下線は関数式で上線を意味する）は、グループ分けさ
    れたＲの前記属性を表し、Ａは、Ｒの属性Ｙに適用され
    る集合関数であることを特徴とする請求項１７のシステ
    ム。
  19. 【請求項１９】 前記（Ｂ）の手段は、前記他の述語か
    らリレーション内の述語を推論する手段を含むことを特
    徴とする請求項１７のシステム。
  20. 【請求項２０】 前記（Ｂ）の手段は、前記第１リレー
    ションを規定する１つまたは複数の第２リレーション内
    の述語から第１リレーション内の述語を推論する手段を
    含むことを特徴とする請求項１７のシステム。
  21. 【請求項２１】 前記（Ｂ）の手段は、前記第１リレー
    ションにより規定される第２リレーション内の述語から
    第１リレーション内の述語を推論する手段を含むことを
    特徴とする請求項１７のシステム。
  22. 【請求項２２】 前記（Ｂ）の手段は、（Ｂ１）前記質
    問に関連する前記表現形式内の前記集合述語を識別する
    手段と、（Ｂ２）前記表現形式内の前記関連集合述語か
    ら１つあるいは複数の新たな述語を推論する手段とを有
    することを特徴とする請求項１７のシステム。
  23. 【請求項２３】 前記（Ｂ）の手段は、（Ｂ１）前記質
    問に関連する前記（数１）の式の前記集合述語を識別す
    る手段と、（Ｂ２）前記（数１）の式の前記関連集合述
    語から１つあるいは複数の新たな述語を推論する手段と
    を有することを特徴とする請求項１８のシステム。
  24. 【請求項２４】 前記（数１）の式の関連集合述語は、
    Ｒと groupby リストと、集合属性対ＧＬR を含むもの
    であり、前記Ｒは、前記質問がそれにより集合を形成す
    るリレーションと、前記質問がそれにより集合を形成す
    るビューを規定するリレーションとを含み、前記ＧＬR
    は、groupby リストとＲ内の集合した属性と、groupby
    リスト内の projection と、Ｒを規定するリレーション
    の集合した述語とを含むことを特徴とする請求項２３の
    システム。
  25. 【請求項２５】 前記（Ｂ）手段は、（Ｂ１）前記の新
    たな述語の１つあるいは複数が前記質問を解くのに有効
    であるか否かを決定する手段と、（Ｂ２）前記の有効で
    ない新たな述語を削除する手段とを含むことを特徴とす
    る請求項１７のシステム。
  26. 【請求項２６】 前記（Ｂ）手段は、（Ｂ１）前記の新
    たな述語の１つあるいは複数が前記質問を解くのに有効
    であるか否かを決定する手段と、（Ｂ２）前記の有効で
    ない新たな述語を削除する手段とを含むことを特徴とす
    る請求項１８のシステム。
  27. 【請求項２７】 前記（Ｂ２）の手段は、自明な述語を
    削除する手段を含むことを特徴とする請求項２５または
    ２６のシステム。
  28. 【請求項２８】 前記（Ｂ２）の手段は、冗長な述語を
    削除する手段を含むことを特徴とする請求項２５または
    ２６のシステム。
  29. 【請求項２９】 前記（Ｂ２）の手段は、表現形式の全
    ての述語を削除する手段を含むことを特徴とする請求項
    ２５のシステム。
  30. 【請求項３０】 前記（Ｂ２）の手段は、（数１）の式
    に関連する全ての述語を削除する手段を含むことを特徴
    とする請求項２４のシステム。
  31. 【請求項３１】 前記（Ｂ）の手段は、述語プッシュダ
    ウン（pushdown）最適化技術を実行することを特徴とす
    る請求項１７または１８のシステム。
  32. 【請求項３２】 前記（Ｂ）の手段は、述語ムーブ−ア
    ラウンド（move-around） 最適化技術を実行することを
    特徴とする請求項１７または１８のシステム。
JP8311770A 1995-12-27 1996-11-22 データベース質問をコンピュータで実行する方法 Pending JPH09190452A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/579,537 US6088524A (en) 1995-12-27 1995-12-27 Method and apparatus for optimizing database queries involving aggregation predicates
US579537 2000-05-24

Publications (1)

Publication Number Publication Date
JPH09190452A true JPH09190452A (ja) 1997-07-22

Family

ID=24317318

Family Applications (1)

Application Number Title Priority Date Filing Date
JP8311770A Pending JPH09190452A (ja) 1995-12-27 1996-11-22 データベース質問をコンピュータで実行する方法

Country Status (4)

Country Link
US (1) US6088524A (ja)
EP (1) EP0791882A1 (ja)
JP (1) JPH09190452A (ja)
CA (1) CA2190790A1 (ja)

Families Citing this family (79)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6199063B1 (en) * 1998-03-27 2001-03-06 Red Brick Systems, Inc. System and method for rewriting relational database queries
US6411952B1 (en) * 1998-06-24 2002-06-25 Compaq Information Technologies Group, Lp Method for learning character patterns to interactively control the scope of a web crawler
US7197570B2 (en) * 1998-07-22 2007-03-27 Appstream Inc. System and method to send predicted application streamlets to a client device
US6574618B2 (en) 1998-07-22 2003-06-03 Appstream, Inc. Method and system for executing network streamed application
US20010044850A1 (en) 1998-07-22 2001-11-22 Uri Raz Method and apparatus for determining the order of streaming modules
US6311221B1 (en) 1998-07-22 2001-10-30 Appstream Inc. Streaming modules
US6460027B1 (en) * 1998-09-14 2002-10-01 International Business Machines Corporation Automatic recognition and rerouting of queries for optimal performance
US7167853B2 (en) * 1999-05-20 2007-01-23 International Business Machines Corporation Matching and compensation tests for optimizing correlated subqueries within query using automatic summary tables
US6847962B1 (en) * 1999-05-20 2005-01-25 International Business Machines Corporation Analyzing, optimizing and rewriting queries using matching and compensation between query and automatic summary tables
US6430550B1 (en) * 1999-12-03 2002-08-06 Oracle Corporation Parallel distinct aggregates
US6526403B1 (en) * 1999-12-17 2003-02-25 International Business Machines Corporation Method, computer program product, and system for rewriting database queries in a heterogenous environment
US6983315B1 (en) 2000-01-18 2006-01-03 Wrq, Inc. Applet embedded cross-platform caching
US7051315B2 (en) 2000-09-26 2006-05-23 Appstream, Inc. Network streaming of multi-application program code
US6757894B2 (en) 2000-09-26 2004-06-29 Appstream, Inc. Preprocessed applications suitable for network streaming applications and method for producing same
US6915290B2 (en) * 2001-12-11 2005-07-05 International Business Machines Corporation Database query optimization apparatus and method that represents queries as graphs
US7263512B2 (en) * 2002-04-02 2007-08-28 Mcgoveran David O Accessing and updating views and relations in a relational database
US20080010241A1 (en) * 2002-04-02 2008-01-10 Mcgoveran David O Computer-implemented method for managing through symbolic abstraction of a membership expression multiple logical representations and storage structures
US7620664B2 (en) * 2002-04-02 2009-11-17 Mcgoveran David O Computer-implemented method for translating among multiple representations and storage structures
US6983275B2 (en) * 2002-04-16 2006-01-03 International Business Machines Corporation Optimizing database query by generating, determining the type of derived predicate based on monotonicity of the column generating expression for each remaining inequality predicate in the list of unexamined predicates
US6947948B2 (en) * 2002-04-23 2005-09-20 International Business Machines Corporation Version-enabled, multi-typed, multi-targeting referential integrity relational database system and methodology
US6950815B2 (en) * 2002-04-23 2005-09-27 International Business Machines Corporation Content management system and methodology featuring query conversion capability for efficient searching
US6999966B2 (en) * 2002-04-23 2006-02-14 International Business Machines Corporation Content management system and methodology for implementing a complex object using nested/recursive structures
US6944627B2 (en) * 2002-04-23 2005-09-13 International Business Machines Corporation Content management system and methodology employing a tree-based table hierarchy featuring arbitrary information retrieval from different locations in the hierarchy
US6938050B2 (en) 2002-04-23 2005-08-30 International Business Machines Corporation Content management system and methodology employing a tree-based table hierarchy which accomodates opening a dynamically variable number of cursors therefor
US7035854B2 (en) * 2002-04-23 2006-04-25 International Business Machines Corporation Content management system and methodology employing non-transferable access tokens to control data access
US7082455B2 (en) * 2002-04-23 2006-07-25 International Business Machines Corporation Method and apparatus of parameter passing of structured data for stored procedures in a content management system
US7299225B2 (en) * 2002-11-26 2007-11-20 International Business Machines Corporation High performance predicate push-down for non-matching predicate operands
US7392246B2 (en) * 2003-02-14 2008-06-24 International Business Machines Corporation Method for implementing access control for queries to a content management system
US7668801B1 (en) * 2003-04-21 2010-02-23 At&T Corp. Method and apparatus for optimizing queries under parametric aggregation constraints
US7171398B2 (en) * 2003-10-16 2007-01-30 International Business Machines Corporation Outer and exception join to inner join normalization
US7467386B2 (en) 2004-01-16 2008-12-16 International Business Machines Corporation Parameter passing of data structures where API and corresponding stored procedure are different versions/releases
US20050210023A1 (en) * 2004-03-18 2005-09-22 Renato Barrera Query optimizer using implied predicates
US7739262B2 (en) * 2004-03-19 2010-06-15 Microsoft Corporation Enforcing currency and consistency constraints in database query processing
US7480652B2 (en) * 2005-10-26 2009-01-20 Microsoft Corporation Determining relevance of a document to a query based on spans of query terms
US7873627B2 (en) * 2006-01-18 2011-01-18 Microsoft Corporation Relational database scalar subquery optimization
US7464084B2 (en) * 2006-01-30 2008-12-09 International Business Machines Corporation Method for performing an inexact query transformation in a heterogeneous environment
US7814052B2 (en) 2006-11-03 2010-10-12 Salesforce.Com, Inc. Implementing formulas for custom fields in an on-demand database
US7769755B2 (en) * 2006-11-30 2010-08-03 Microsoft Corporation Efficient execution of aggregation queries
US8832073B2 (en) * 2007-06-29 2014-09-09 Alcatel Lucent Method and apparatus for efficient aggregate computation over data streams
US8140548B2 (en) 2008-08-13 2012-03-20 Microsoft Corporation Constrained physical design tuning
US8290891B2 (en) * 2009-06-15 2012-10-16 Nokia Corporation Method and apparatus of dynamic rules insertion by agents
US8925034B1 (en) 2009-06-30 2014-12-30 Symantec Corporation Data protection requirements specification and migration
US8387047B1 (en) 2009-08-03 2013-02-26 Symantec Corporation Method of virtualizing file extensions in a computer system by determining an association between applications in virtual environment and a file extension
US8352937B2 (en) * 2009-08-03 2013-01-08 Symantec Corporation Streaming an application install package into a virtual environment
US8090744B1 (en) 2009-08-26 2012-01-03 Symantec Operating Corporation Method and apparatus for determining compatibility between a virtualized application and a base environment
US8473444B1 (en) 2009-08-28 2013-06-25 Symantec Corporation Management of actions in multiple virtual and non-virtual environments
US8438555B1 (en) 2009-08-31 2013-05-07 Symantec Corporation Method of using an encapsulated data signature for virtualization layer activation
US8458310B1 (en) 2009-09-14 2013-06-04 Symantec Corporation Low bandwidth streaming of application upgrades
US8566297B1 (en) 2010-01-14 2013-10-22 Symantec Corporation Method to spoof data formats from image backups
US8290912B1 (en) 2010-01-29 2012-10-16 Symantec Corporation Endpoint virtualization aware backup
US8495625B1 (en) 2010-07-27 2013-07-23 Symantec Corporation Method and system for creation of streamed files on-demand
US9881034B2 (en) 2015-12-15 2018-01-30 Mongodb, Inc. Systems and methods for automating management of distributed databases
US8996463B2 (en) 2012-07-26 2015-03-31 Mongodb, Inc. Aggregation framework system architecture and method
US10614098B2 (en) 2010-12-23 2020-04-07 Mongodb, Inc. System and method for determining consensus within a distributed database
US9740762B2 (en) 2011-04-01 2017-08-22 Mongodb, Inc. System and method for optimizing data migration in a partitioned database
US10977277B2 (en) 2010-12-23 2021-04-13 Mongodb, Inc. Systems and methods for database zone sharding and API integration
US10713280B2 (en) 2010-12-23 2020-07-14 Mongodb, Inc. Systems and methods for managing distributed database deployments
US10366100B2 (en) * 2012-07-26 2019-07-30 Mongodb, Inc. Aggregation framework system architecture and method
US11615115B2 (en) 2010-12-23 2023-03-28 Mongodb, Inc. Systems and methods for managing distributed database deployments
US10740353B2 (en) 2010-12-23 2020-08-11 Mongodb, Inc. Systems and methods for managing distributed database deployments
US10262050B2 (en) 2015-09-25 2019-04-16 Mongodb, Inc. Distributed database systems and methods with pluggable storage engines
US9805108B2 (en) 2010-12-23 2017-10-31 Mongodb, Inc. Large distributed database clustering systems and methods
US10346430B2 (en) 2010-12-23 2019-07-09 Mongodb, Inc. System and method for determining consensus within a distributed database
US10997211B2 (en) 2010-12-23 2021-05-04 Mongodb, Inc. Systems and methods for database zone sharding and API integration
US11544288B2 (en) 2010-12-23 2023-01-03 Mongodb, Inc. Systems and methods for managing distributed database deployments
US8572031B2 (en) 2010-12-23 2013-10-29 Mongodb, Inc. Method and apparatus for maintaining replica sets
US11403317B2 (en) 2012-07-26 2022-08-02 Mongodb, Inc. Aggregation framework system architecture and method
US11544284B2 (en) 2012-07-26 2023-01-03 Mongodb, Inc. Aggregation framework system architecture and method
US10872095B2 (en) 2012-07-26 2020-12-22 Mongodb, Inc. Aggregation framework system architecture and method
US10102248B2 (en) * 2012-10-10 2018-10-16 TmaxData Co., Ltd. Join type for optimizing database queries
US9880776B1 (en) 2013-02-22 2018-01-30 Veritas Technologies Llc Content-driven data protection method for multiple storage devices
US10303726B2 (en) * 2014-11-13 2019-05-28 Sap Se Decoupling filter injection and evaluation by forced pushdown of filter attributes in calculation models
US10496669B2 (en) 2015-07-02 2019-12-03 Mongodb, Inc. System and method for augmenting consensus election in a distributed database
US10846411B2 (en) 2015-09-25 2020-11-24 Mongodb, Inc. Distributed database systems and methods with encrypted storage engines
US10423626B2 (en) 2015-09-25 2019-09-24 Mongodb, Inc. Systems and methods for data conversion and comparison
US10673623B2 (en) 2015-09-25 2020-06-02 Mongodb, Inc. Systems and methods for hierarchical key management in encrypted distributed databases
US10671496B2 (en) 2016-05-31 2020-06-02 Mongodb, Inc. Method and apparatus for reading and writing committed data
US10776220B2 (en) 2016-06-27 2020-09-15 Mongodb, Inc. Systems and methods for monitoring distributed database deployments
US10866868B2 (en) 2017-06-20 2020-12-15 Mongodb, Inc. Systems and methods for optimization of database operations

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5197005A (en) * 1989-05-01 1993-03-23 Intelligent Business Systems Database retrieval system having a natural language interface
US5355474A (en) * 1991-09-27 1994-10-11 Thuraisngham Bhavani M System for multilevel secure database management using a knowledge base with release-based and other security constraints for query, response and update modification
US5367675A (en) * 1991-12-13 1994-11-22 International Business Machines Corporation Computer automated system and method for optimizing the processing of a query in a relational database system by merging subqueries with the query
US5412804A (en) * 1992-04-30 1995-05-02 Oracle Corporation Extending the semantics of the outer join operator for un-nesting queries to a data base
US5488722A (en) * 1993-05-28 1996-01-30 International Business Machines Corporation System and method for automating implementation and execution of constraint most likely to be violated in a database
US5574900A (en) * 1994-02-25 1996-11-12 International Business Machines Corporation System and method for optimizing parallel processing of database queries
US5659725A (en) * 1994-06-06 1997-08-19 Lucent Technologies Inc. Query optimization by predicate move-around
US5511190A (en) * 1995-01-20 1996-04-23 Tandem Computers, Inc. Hash-based database grouping system and method
US5546576A (en) * 1995-02-17 1996-08-13 International Business Machines Corporation Query optimizer system that detects and prevents mutating table violations of database integrity in a query before execution plan generation
US5548755A (en) * 1995-02-17 1996-08-20 International Business Machines Corporation System for optimizing correlated SQL queries in a relational database using magic decorrelation
US5535385A (en) * 1995-05-19 1996-07-09 At&T Corp. Dealing with side effects of transactions in data base systems using a multi-set algebra
US5655080A (en) * 1995-08-14 1997-08-05 International Business Machines Corporation Distributed hash group-by cooperative processing

Also Published As

Publication number Publication date
CA2190790A1 (en) 1997-06-28
EP0791882A1 (en) 1997-08-27
US6088524A (en) 2000-07-11

Similar Documents

Publication Publication Date Title
JPH09190452A (ja) データベース質問をコンピュータで実行する方法
US7111020B1 (en) Incremental refresh of materialized views containing rank function, and rewrite of queries containing rank or rownumber or min/max aggregate functions using such a materialized view
US7599953B2 (en) System and method for segmented evaluation of database queries
US6026390A (en) Cost-based maintenance of materialized views
US5564047A (en) Trigger generation in an active database management system
O'Neil et al. Multi-table joins through bitmapped join indices
AU772754B2 (en) System and method for rewriting relational database queries
US5659725A (en) Query optimization by predicate move-around
US5963936A (en) Query processing system that computes GROUPING SETS, ROLLUP, and CUBE with a reduced number of GROUP BYs in a query graph model
US6643646B2 (en) Analysis of massive data accumulations using patient rule induction method and on-line analytical processing
US6931418B1 (en) Method and system for partial-order analysis of multi-dimensional data
US7171399B2 (en) Method for efficient query execution using dynamic queries in database environments
EP0877327B1 (en) Method and apparatus for performing a join query in a database system
US7171408B2 (en) Method of cardinality estimation using statistical soft constraints
US6105020A (en) System and method for identifying and constructing star joins for execution by bitmap ANDing
JP3640346B2 (ja) データベース管理システムにおける集合述部および検索
US6311179B1 (en) System and method of generating associations
US7010516B2 (en) Method and system for rowcount estimation with multi-column statistics and histograms
US20090024571A1 (en) Supporting aggregate expressions in query rewrite
CA2178263A1 (en) Method and apparatus for a complete sql subquery elimination process
US6408291B1 (en) Precomputing reference collections in a decision support system
US7577647B2 (en) Combining nested aggregators
US6931392B1 (en) Real-time decision support system
US20140188924A1 (en) Techniques for ordering predicates in column partitioned databases for query optimization
US20050108204A1 (en) System and method for managing OLAP summary tables