SQL
SQLite3
sqlite
ポエム

SQL はチューリング完全

More than 1 year has passed since last update.


前置き



自己紹介

icon


  • @utgwkk

  • 工学部情報学科計算機科学コース2回生

  • 第39代副広報

  • root



アンケートです


  • SQL を知ってる

  • SQL を書いたことがある

  • 毎日 SQL を書いてる



SQL とは


SQL(エスキューエル[ˈɛs kjuː ˈɛl]、シークェル[ˈsiːkwəl]、シーケル)は、関係データベース管理システム (RDBMS) において、データの操作や定義を行うためのデータベース言語(問い合わせ言語)である。



  • 要するに、データベースからデータを所望の形で取ってくるときに使う言語

  • プログラミング言語ではないとされている

SELECT * FROM images

WHERE description LIKE '%みりあ%';

SELECT comments.*, entries.user_id as entry_user_id

FROM comments
LEFT JOIN entries ON entries.id = comments.entry_id
AND entries.private = 0
WHERE comments.user_id IN (1552, 2441, 5553)
ORDER BY created_at DESC
LIMIT 10;



チューリング完全とは


  • 万能チューリングマシンと同じ計算能力をもつこと

  • かなり雑に言うと、この言語を使っていろいろなアルゴリズムが書けるという性質

  • SQL はチューリング完全

  • つまり、いろいろなアルゴリズムが書ける!!


チューリング完全であるものの例



SQL プログラミングのための文法


  • ここでは SQLite3 を使います

  • SELECT 文

  • WITH 句

  • CASE WHEN

  • プログラムの実行



SELECT 文


  • DB から取得するデータの形式を指定する文だった

  • 今はそのことは忘れよう

  • 文字列を出力するのに使う


    • ちなむと、SQLite の文字列結合の演算子は ||



  • メソッドに引数を渡すのに使う(後述)

  • メソッドの結果を取得するのにも使う(後述)



WITH 句


  • 副問い合わせに名前をつける

  • 要するに仮想的なテーブルを定義する

  • 実はこれ1つでだいたいなんでもできる


  • 公式ドキュメントで披露されている


for ループ

WITH RECURSIVE

cnt(x) AS (
SELECT 0
UNION ALL
SELECT x+1 FROM cnt
LIMIT 100
)
SELECT x FROM cnt;

は、

for (int i = 0; i < 100; ++i) {

std::cout << i << std::endl;
}

と(ほぼ)等価


メソッド定義


  • 引数を渡すのも WITH 句を使う

  • 2引数をとって n % k を返す iseven メソッドを定義(したつもりになる)


mod.sql

WITH

args(n, k) AS (
SELECT 10, 4
),

cmod(result) AS (
SELECT (n % k)
FROM args
)

SELECT n || ' % ' || k || ' = ' || result
FROM args, cmod;




CASE WHEN


  • 場合分け

  • 要するに if 文

SELECT '5 is ' ||

CASE WHEN 5 % 2 = 0
THEN 'even'
ELSE 'odd'
END



プログラムの実行



  • cat [filename] | sqlite3 で実行できる


  • ideone とか Wandbox でも実行できる





FizzBuzz


fizzbuzz.sql

WITH RECURSIVE

cnt(x) AS (
SELECT 1
UNION ALL SELECT x + 1
FROM cnt
LIMIT 100
),
fizzbuzz(x) AS (
SELECT
CASE WHEN x % 3 = 0
THEN 'Fizz'
ELSE ''
END
||
CASE WHEN x % 5 = 0
THEN 'Buzz'
ELSE ''
END
||
CASE WHEN x % 5 != 0 AND x % 3 != 0
THEN x
ELSE ''
END
FROM cnt
)
SELECT x FROM fizzbuzz;



マンデルブロ集合

https://gyazo.com/356db89f72941d653b0f4c3a3295c305


  • こういう図形の AA を描く

  • 公式サイトから


mandel.sql

WITH RECURSIVE

xaxis(x) AS (VALUES(-2.0) UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2),
yaxis(y) AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0),
m(iter, cx, cy, x, y) AS (
SELECT 0, x, y, 0.0, 0.0 FROM xaxis, yaxis
UNION ALL
SELECT iter+1, cx, cy, x*x-y*y + cx, 2.0*x*y + cy FROM m
WHERE (x*x + y*y) < 4.0 AND iter<28
),
m2(iter, cx, cy) AS (
SELECT max(iter), cx, cy FROM m GROUP BY cx, cy
),
a(t) AS (
SELECT group_concat( substr(' .+*#', 1+min(iter/7,4), 1), '')
FROM m2 GROUP BY cy
)
SELECT group_concat(rtrim(t),x'0a') FROM a;

                                    ....#

..#*..
..+####+.
.......+####.... +
..##+*##########+.++++
.+.##################+.
.............+###################+.+
..++..#.....*#####################+.
...+#######++#######################.
....+*################################.
#############################################...
....+*################################.
...+#######++#######################.
..++..#.....*#####################+.
.............+###################+.+
.+.##################+.
..##+*##########+.++++
.......+####.... +
..+####+.
..#*..
....#
+.



その他の例


  • 深さ優先探索

  • 幅優先探索

  • 数独ソルバ



おわり


  • みなさんもチューリング完全なものでコードを書きましょう

  • 私は Python とか Ruby を使おうと思います

  • ありがとうございました



参考