クエリ評価

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

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

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

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

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

クエリ評価の複雑さは、非巡回クエリ、連言クエリ、連言クエリの和集合、Datalog、正規パスクエリなど、さまざまなクエリクラスについて研究することができ、一階述語論理や単項二階述語論理などの論理形式まで研究できます。

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

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