[解決済み] SQL、あるいはTSQLはチューリング完全か？

質問

今日、会社でこんな話が出ました。 私はそんなことをする予定はないのですが、理論的にはSQLでコンパイラを書くことはできるのでしょうか？ 一見したところ、多くの問題のクラスで非常に面倒ではありますが、チューリング完全であるように私には見えます。

もしチューリング完全でないとしたら、そうなるためには何が必要ですか？

注：私はSQLでコンパイラを書くようなことをしたいとは思っていませんし、それは愚かなことだとも思っていますので、そのような議論を避けられるのであれば、感謝します。

どのように解決するのですか？

PL/SQLやPSMのような真の「スクリプティング」拡張がなくても、SQLはチューリングコンプリートできることがわかりました（これらは真のプログラミング言語として設計されているので、ちょっとズルいですね）。

で 本スライドのセット Andrew Gierth は、CTE と Windowing SQL がチューリングコンプリートであることを 循環タグシステム であり、チューリング完全であることが証明されています。CTE機能は、自分自身を参照することができる名前付き部分式を作成し、それによって問題を再帰的に解決することを可能にするものである。

興味深いのは、CTEはSQLをプログラミング言語にするために追加されたのではなく、宣言型クエリ言語をより強力な宣言型クエリ言語にするために追加されたという点です。C++で言えば、メタプログラミング言語を作るつもりはなかったのに、テンプレートがチューリング完全であることが判明したようなものです。

あ、その SQLのマンデルブロー集合 の例も非常に印象的です :)