# 2020-07-27 輪読 「タブロー決定問題の複雑性」
後述する定理は、タブロークエリ間の包含関係と等価性を決定することがNP完全であり、タブロークエリ最小化はNP困難であることを示す。

## Theorem 6.2.10
$q, q^{'}$ はタブロークエリと仮定する。(a), (b), (c)がNP完全問題である。

a) $q \subseteq q^{'}$であるか？
b) $q \equiv q^{'}$であるか？
c) $q^{'}$のタブローのfree tupleが消されることによって$q$のタブローが与えられると仮定する。この時、$q \equiv q^{'}$であるか？
- free tupleは変数もしくは定数の組

もし$q, q^{'}$が定数を持たない型付けされたタブロークエリの単一関係になるよう制限されていたとしたら、これらの結果は依然として正しい。

## (a)の証明
証明は、"Exact Cover"問題から異なるタブロークエリ問題への簡約化(問題の転換?)。
- [Exact Cover](https://muscle-keisuke.hatenablog.com/entry/2015/11/05/145901)とは、集合Xに含まれる被覆でちょうど全ての要素を1つずつ含む被覆のこと
- Exact Cover問題はNP完全である
- タブロークエリのcontainmentの決定問題がNP完全であることを示したい


今、我々はexact cover問題のインスタンス$\epsilon = (X,S)$から型付けされたタブロークエリのペア$q_{\epsilon}, q_{\epsilon^{'}}$への多項式変換を描く。そして、この構造はNP-完全でない結果を得るために多くの手段に適用される。この構造は6.8に書かれている。


- ここから簡約化の方法を示す

E = (X, S) をexact cover問題のインスタンスとする。
S = {S1,...,Sm}. A1,...,An,B1,...,Bm を異なる属性のリストとし，Rは、この集合をソートとして持つように選択される。$q_{\epsilon}, q_{\epsilon^{'}}$はリレーションR上にあり、両方のクエリはt = <A1 : a1,...,An : an>を持つ。ここで a1,...,an は相異なる変数である。
b1,...,bmおよびc1,...,cm を m 個の異なる変数の追加集合とする。$q_{\epsilon}$のTableau $T_{\epsilon}$はn個のタプルを持ち、$q_{\epsilon^{'}}$のTableau $T_{\epsilon^{'}}$はm個のタプルを持つ。

構成を説明するために、E = (X, S) をExact Cover問題のインスタンスとする。
ここで、X = {x1, x2, x3, x4}と、S = {S1, S2, S3}である。
S1＝｛x1, x3｝である。
S2＝｛x2, x3, x4｝である。
S3 = {x2, x4}となる。

(X, S)に対応するタブロークエリqξとq′ξを図6.8に示す。(ここでは，空欄の項目は区別された新しい変数を示す)
ξ = (X, S) が充足可能であり，q′ξ ⊆ qξ であることに注意すること。

より一般的には，Exact Cover問題の与えられたインスタンス ξ = (X, S) に対して，X が S の中でExact Coverを持っていることを検証することは簡単である(qξ′ ⊆ qξ の場合のみ)。
定理の(b)と(c)の部分の検証は，演習6.16に委ねる。
多項式時間でcontainmentと等価性が決定可能な型付きtableau問い合わせのサブクラスを、演習6.21で検討する。

---

NP完全性の結果はしばしば難解であることを示唆しているが、前述の結果との関連では、この結論は妥当ではないかもしれない。
- NP完全性を示したが、データベースの大きさとは関係ないのであまり関係ないかもしれない

そこにある複雑さは は、基礎となる保存データの観点からではなく、クエリのサイズに対して相対的に測定される。
n-way joinが与えられると、System Rオプティマイザは、n個の関係の異なる順序に基づいて、n個の評価戦略を考慮する可能性がある。これらはクエリのサイズによっては指数関数的になるかもしれない。
- n個のjoinの順番を全て試すことはできない(n!通り全てを試すことは現実的でない)

多くの場合、最小のタブロー（または最適な左から右への結合）の検索は、データが最初のクエリよりもはるかに大きいために整えられるかもしれない。より一般的には PartD.(12章から)では、「データの複雑さ」と「クエリ式の複雑さ」の両方を見ていく。前者はデータのサイズに対する複雑さに焦点を当て、後者はクエリのサイズに対する複雑さに焦点を当てる。