増永教授のDB特論②「SQLの計算完備性」

1. はじめに

 SQL:1999 で再帰問合せ（recursive query）が導入されました．これにより SQL（本稿ではSQL:1999 及びそれ以降の SQL を総じて SQL ということにします）は SQL 自体で計算完備（computationally complete）あるいはチューリング完全（Turing complete）になったと言われています．しかしながら，それを証明してみなさいと言われると頭を抱えることになるかもしれません．そこで，本稿ではいくつかの文献を参照しながら，その証明の道筋を示してみたいと思います．
 ご存じのように，一般にプログラミング言語は計算完備だと言われています．なぜならば，プログラミング言語はあらゆるアルゴリズムを書き表すことが出来るからです．一方，SQL はリレーショナル代数演算をすべて書き表すことができるのでリレーショナル完備（relationally complete）と言われています．したがって，これら 2 つの性質を併せ持つ SQL はリレーショナル完備でかつ計算完備なデータベース言語となり，SQL の再帰問合せを駆使することによりあらゆるデータベースアプリケーション開発が行えるという枠組みが与えられたことになります．以下，SQL の計算完備性の証明とその意義を見ていきましょう．

2. SQL が計算完備であることを証明する道筋

 SQL が計算完備であることを証明する筋道は次の通りです．

 以下，巡回タグシステム，SQL の計算完備性，考察，と続きます．

3. 巡回タグシステム

 巡回タグシステム（cyclic tag system, CTS）[2] はタグシステムをシミュレートでき，したがって，計算完備であることが証明されるわけですが，ここではそこには深入りせず，まず，CTS とはどのようなシステムなのかを見ていきましょう．

【定義1】（CTS）

 CTS は 3 項組(A, P, I)である．ここに，A はアルファベット，P は生成規則群，I は初期単語を表す．

• A – 記号 0 と 1 からなるアルファベット，すなわちA={0, 1}．A で構成される（空も含む）有限の文字列を単語（words）と呼ぶ．
• P – 生成規則群．生成規則は単語の巡回リストになっている．
• I – 初期単語を表す．

CTS の動作は次の通りである．

• 動作 – 初期単語 I が与えられる．生成規則は単語の巡回リストになっているので，まず初期単語 I に巡回リストの先頭の単語から順次適用して初期単語を変換して新たな単語を生成していく．生成規則については，巡回リストの最後の単語を適用したら，次は先頭に戻る．アルファベットは 0 か 1 からなるので，変換の対象となる単語の左端の記号は 0 か 1 のいずれかである．もし左端の記号が 1 であれば，そのときの生成規則に示された単語を右端に追加し（この動作を「タグ付けする」という），0 であれば何も追加しない．どちらの場合も左端の記号を 1 つだけ削除する．

 理解を深めるために CTS の簡単な計算例を見てみましょう．

【CTSの計算例】

A={0, 1}

P=(1→11, 1→10, 1→ε)

 CTS では（上記のごとく）「0 であれば何も追加しない」ので，「1→」は自明と見なしてよいから，P=(1→11, 1→10, 1→ε)を単にP=(11, 10, ε)と書いてよい．なお，リスト P=(11, 10, ε)の要素は CTS の計算において，先頭から末尾の順に繰り返して適用されるので，それらに順に，1, 2, 3 と生成規則番号を付与することにする．
 そこで，初期単語 I をそれぞれ (a) 00001，(b) 10101，(c) 01100，(d) 11111 とした時の巡回タグシステムの動作を示す[3]．なお，生成関係を⊦i （i∈{1, 2, 3}）で表すこととする．このとき，単語の先頭が 0 の場合には生成後の単語はその先頭の 0 が削除されるだけなので，スペースを省略するために生成後の単語は書かないこととする．なお，CTS を提案した Cook はその停止条件を明示しなかったとのことであるが（タグシステムが停止するときに CTS も停止するように作られたということ），CTS の計算例を見てみると，その停止条件は，単語が消滅してしまうか（halt disappeared，消滅停止），ある所から単語の出現が周期的になってしまうか（halt periodic，周期的停止），のいずれかになるようである．

4. SQLの計算完備性

 さて，巡回タグシステム（CTS）を SQL でシミュレートできれば，SQL はチューリング完全，即ち計算完備であることが示せたことになります．このために，SQL-92 で規格化された CASE 文，そして SQL:1999 で規格化された再帰問合せの機能を用います．以下に示すように，SQL 文で CTS をシミュレートできるので[4]，SQL がチューリング完全であることが示されます．

【CTS をシミュレートする再帰問合せ】

 CTS=(A, P, I)，ここに A={0, 1}, P=(110, 01, 0000), I=1 としてそれをシミュレートする SQL の再帰問合せと実行結果を以下に示す（PostgreSQL 14 で実行）．

■ CTS をシミュレートする SQL の再帰問合せ[4]
 

postgres=# WITH RECURSIVE
postgres-# p(iter, rnum, tag) AS (
postgres(#   VALUES(0,0,1),(0,1,1),(0,2,0),(1,0,0),(1,1,1),(2,0,0),(2,1,0),(2,2,0),(2,3,0)
postgres(# ),
postgres-# r(iter,rnum,tag) AS (
postgres(#   VALUES (0,0,1)
postgres(# UNION ALL
postgres(#   SELECT r.iter+1,
postgres(#     CASE
postgres(#      WHEN r.rnum=0 THEN p.rnum + max(r.rnum) OVER ()
postgres(#      ELSE r.rnum-1
postgres(#     END,
postgres(#     CASE
postgres(#      WHEN r.rnum=0 THEN p.tag
postgres(#      ELSE r.tag
postgres(#     END
postgres(#   FROM
postgres(#    r
postgres(#   LEFT JOIN p
postgres(#    ON (r.rnum=0 and r.tag=1 and p.iter=mod(r.iter, 3))
postgres(#   WHERE
postgres(#    r.rnum>0
postgres(#   OR p.iter IS NOT NULL
postgres(# )
postgres-# SELECT iter, rnum, tag
postgres-# FROM r
postgres-# ORDER BY iter, rnum;

■ PostgreSQL14 での実行結果

ちなみに，この SQL 文がシミュレートした CTS の動作は次のとおりである．

このように CTS を作動させると 14 ステップで消滅停止することになるが，それを上記 SQL 文でシミュレートすると 62 行からなるテーブル r として結果を出力している．このとき，r の最終行は(13, 0, 0)となっており，CTS の 14 ステップでの消滅停止と符合している．

なお，CTS の動作を Python で 114 文字（スペースを含める）で書けるという報告があります[5]．

そもそもプログラミング言語自体は計算完備になるように設計されているから当り前と言えば当たり前ですし，逆に Python で CTS をシミュレートできるから Python は計算完備だと主張しているのでしょうか．あまり深い意味はないと思いますが，他のプログラミング言語でも同様な報告が可能でしょう．

5. 考察

 以上，SQL が計算完備であることを示すことができました．したがって，SQL はリレーショナル完備でかつ計算完備という強力なプログラミング言語であると主張することにやぶさかではないといえます．しかし，だったら，あらゆるデータベースアプリケーションプログラムを SQL の再帰問合せを駆使して書き上げるのか？と問われればそれは別の話になるのではないでしょうか．
 この件に関して，SQL に精通し長年にわたり ISO/IEC JTC1/SC 32 WG 3 (SQL)日本代表を務められた小寺孝氏（日立製作所）に意見を求めたことがあります．氏は，次のような認識を示して下さいました（小寺氏との私信[6]による）．

 筆者も小寺氏の認識に大いに賛同するところです．SQL-87 当時から導入された「埋込みSQL」（embedded SQL）や SQL-92 を拡張する追加規格SQL/PSM (ISO/IEC 9075-4:1996)は，正しく SQL の計算完備性をアプリケーション開発の観点から補う具体的な機能であって，アプリケーションプログラマは「再帰問合せ」[7]，「埋込み SQL」，「SQL/PSM」の持ち合わせる機能をよく理解して，的確なプログラミングに心がけることが肝要ということだと思います．

【謝辞】

【文献】

[1]

[2]

[3]

[4]

[5]

[6]

[7]