クエリ評価

Determining the answers to a query on a database

データベース理論において、クエリ評価問題とは、データベースに対するクエリへの回答を決定する問題^[1]である。データベース理論の研究は、データベース、特にリレーショナルデータベースにおいて、さまざまな種類のクエリに回答する際の計算複雑性を決定することを目的としている。

正式な定義

クエリ評価問題は、回答すべきクエリと、そのクエリに回答するためのデータベースという2つの入力を取ります。この問題の出力は、データベース上のクエリに対する回答の集合です。クエリがブールクエリ、つまり「はい」または「いいえ」で答えられるクエリ（例えば、ブール論理積クエリ）である場合、クエリ評価問題は決定問題となります。

クエリ評価問題は通常、特定の種類のクエリとデータベースに対して発生します。例えば、クエリ評価問題の一例として、リレーショナルデータベースにおける結合クエリを評価する問題が挙げられます。

問題の計算の複雑さは、問題の2つの入力が異なるという事実を考慮して、さまざまな方法で測定できます。 ^[2]

クエリ評価問題の複合複雑度は、計算複雑度で通常行われるように、クエリとデータベースの 2 つの入力の関数として測定された場合の計算複雑度です。
データ複雑度とは、クエリが固定で、入力がデータベースのみである場合の計算複雑度です。例えば、あるクラスのクエリに対するクエリ評価が多項式時間のデータ複雑度を持つとは、そのクラスのすべての固定クエリQに対し、データベースDが与えられたときに、 Qの回答をD上で多項式時間で計算できることを意味します。
あまり一般的ではありませんが、クエリ複雑度を研究することもできます。これは、データベースが固定されており、入力がクエリのみである場合の計算複雑度です。これは式複雑度とも呼ばれます。^[3]

クエリクラス

クエリ評価の複雑さは、非巡回クエリ、連言クエリ、連言クエリの結合、データログ、通常パスクエリなど、一階述語論理やモナディック二階述語論理などの論理形式に至るまで、さまざまなクエリクラスについて調査できます。

例えば、ブール論理積クエリの場合、クエリ評価の複雑度はデータ複雑度の多項式であり、 AC0クラスにさえ属します。対照的に、クエリ複雑度と複合複雑度は、3色可能性^[5]からの縮約によりNP完全^[4]です。

ブールクエリと非ブールクエリ

クエリ評価の複雑さは、回答を返すクエリ、あるいはブールクエリ（はい/いいえクエリ）について研究することができます。しかし、多くの場合、ブールクエリの場合に帰着できます。より具体的には、クエリに対する回答の数が常にデータベースサイズの多項式であり、かつ、各回答に対してクエリをブールクエリに書き換えることができる場合、非ブールクエリのクエリ評価を多項式の数のブールクエリ評価問題に帰着させることができます。^[6]

参考文献

^ Kimelfeld, Benny; Kosharovsky, Yuri; Sagiv, Yehoshua (2009-10-01). 「確率的XMLによるクエリ評価」 . The VLDB Journal . 18 (5): 1117– 1140. doi :10.1007/s00778-009-0150-5. ISSN 0949-877X.形式的には、各クエリはそれぞれ異なる計算問題、つまり与えられたデータベース上での評価に関連付けられます。
^ Vardi, Moshe Y. (1982-05-05). 「リレーショナルクエリ言語の複雑性（拡張抄録）」.第14回ACMコンピューティング理論シンポジウム議事録 - STOC '82 . ニューヨーク州ニューヨーク：Association for Computing Machinery. pp. 137– 146. doi :10.1145/800070.802186. ISBN 978-0-89791-070-5。
^ アビテブール, セルジュ; ハル, リチャード; ヴィアヌ, ビクター (1994年12月2日). 『データベースの基礎：論理レベル』（第1版）. マサチューセッツ州レディング: ピアソン. ISBN 978-0-201-53771-0。
^ Greco, Gianluigi; Scarcello, Francesco (2014-06-18). 「連言クエリの解のカウント：構造的およびハイブリッドな追跡可能性」.第33回ACM SIGMOD-SIGACT-SIGARTデータベースシステム原理シンポジウム議事録. PODS '14. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp. 132– 143. doi :10.1145/2594538.2594559. ISBN 978-1-4503-2375-8。
^ De Giacomo, Giuseppe. 「結合クエリ：形式手法」（PDF） .スライド6
^ Amarilli, Antoine; Benedikt, Michael (2020-07-05). 「数値制限付き有限オープンワールドクエリ応答」. ACM Trans. Comput. Logic . 21 (4): 27:1–27:73. arXiv : 2003.02521 . doi :10.1145/3365834. ISSN 1529-3785.我々は常にすべての可能な割り当てを列挙し、多項式的に多数のインスタンスを解くことで問題を解くことができる。

[1] Kimelfeld, Benny; Kosharovsky, Yuri; Sagiv, Yehoshua (2009-10-01). 「確率的XMLによるクエリ評価」 . The VLDB Journal . 18 (5): 1117– 1140. doi :10.1007/s00778-009-0150-5. ISSN 0949-877X.形式的には、各クエリはそれぞれ異なる計算問題、つまり与えられたデータベース上での評価に関連付けられます。

[2] Vardi, Moshe Y. (1982-05-05). 「リレーショナルクエリ言語の複雑性（拡張抄録）」.第14回ACMコンピューティング理論シンポジウム議事録 - STOC '82 . ニューヨーク州ニューヨーク：Association for Computing Machinery. pp. 137– 146. doi :10.1145/800070.802186. ISBN 978-0-89791-070-5。

[3] アビテブール, セルジュ; ハル, リチャード; ヴィアヌ, ビクター (1994年12月2日). 『データベースの基礎：論理レベル』（第1版）. マサチューセッツ州レディング: ピアソン. ISBN 978-0-201-53771-0。

[4] Greco, Gianluigi; Scarcello, Francesco (2014-06-18). 「連言クエリの解のカウント：構造的およびハイブリッドな追跡可能性」.第33回ACM SIGMOD-SIGACT-SIGARTデータベースシステム原理シンポジウム議事録. PODS '14. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp. 132– 143. doi :10.1145/2594538.2594559. ISBN 978-1-4503-2375-8。

[5] De Giacomo, Giuseppe. 「結合クエリ：形式手法」（PDF） .スライド6

[6] Amarilli, Antoine; Benedikt, Michael (2020-07-05). 「数値制限付き有限オープンワールドクエリ応答」. ACM Trans. Comput. Logic . 21 (4): 27:1–27:73. arXiv : 2003.02521 . doi :10.1145/3365834. ISSN 1529-3785.我々は常にすべての可能な割り当てを列挙し、多項式的に多数のインスタンスを解くことで問題を解くことができる。