SQLite3学習 再帰クエリ（WITH RECURSIVE）

　リスト、ツリー、グラフに使える。

成果物

• github

情報源

• https://www.sqlite.org/lang_with.html
• https://asai-atsushi.blog.so-net.ne.jp/2016-03-06

with句

構文

with >           > CTE-table-name > as > (select-statement);
     > recursive >                  ,  <

• CTE=Common Table Expressions
• CTEは単一のSQLステートメントの期間のみ存在する一時ビューのように機能する

テーブル種別	用途
通常の共通テーブル	一時ビュー。サブクエリを排して読みやすくする
再帰的な共通テーブル	ツリーやグラフ。

再帰的な共通テーブル

1. select-statementは、右端の複合演算子がUNIONまたはUNION ALLのいずれかの複合選択でなければならない
2. ASキーワードの左側に指定されたテーブルCTE-table-nameは、複合選択の右端のSELECTステートメントrecursive-selectのFROM句に1回だけ出現し、それ以外には出現しないようにすべき
3. 複合選択の右端のSELECTは、集計関数またはウィンドウ関数を使用してはならない

CTE-table-name > as > (initial-select > union       > recursive-select);
                                        union > all >

• recursive-selectは複合でなく単純選択(SELECT)でなければならない
• recursive-selectにはorder by, limit/offsetを含めることができる

再帰テーブルCTE-table-nameの算出法

1. initial-selectを実行し、結果をキューに追加します。
2. キューが空ではない間：
   1. キューから単一の行を抽出します。
   2. その単一の行を再帰的なテーブルに挿入します
   3. 抽出した単一の行が再帰テーブル内の唯一の行であると仮定し、recursive-selectを実行して、すべての結果をキューに追加します。

　上記の基本手順は、次の追加ルールによって変更される場合があります。

• UNION演算子がinitial-selectをrecursive-selectに接続する場合、同じ行が以前にキューに追加されていない場合にのみ、キューに行を追加します。繰り返し行が再帰ステップによってキューから既に抽出されている場合でも、繰り返し行はキューに追加される前に破棄されます。演算子がUNION ALLの場合、initial-selectと recursive-selectの両方によって生成されたすべての行は、たとえそれらが繰り返されていても常にキューに追加されます。行が繰り返されるかどうかを判断するとき、NULL値は互いに等しく、他の値とは等しくありません

• LIMIT句が存在する場合、ステップ2bで再帰テーブルに追加される行の最大数を決定します。制限に達すると、再帰は停止します。ゼロの制限は、再帰テーブルに行が追加されないことを意味し、負の制限は、再帰テーブルに追加できる行の数に制限がないことを意味します

• OFFSET句が存在し、正の値Nがある場合、最初のN行が再帰テーブルに追加されないようにします。最初のN行は、再帰選択によって引き続き処理されます。それらは、再帰テーブルに追加されません。すべてのOFFSET行がスキップされるまで、行はLIMITを満たすためにカウントされません

• ORDER BY句が存在する場合、ステップ2aでキューから行が抽出される順序を決定します。ORDER BY句がない場合、行が抽出される順序は未定義です。（現在の実装では、ORDER BY句を省略した場合、キューはFIFOになりますが、アプリケーションは変更される可能性があるため、その事実に依存すべきではありません。）

1〜10の値を返す

WITH RECURSIVE
  cnt(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM cnt WHERE x<10)
SELECT x FROM cnt;

コード	概要
cnt(x)	CTE=Common Table Expressions。テーブル名cnt, 列xの一時ビューを作成した
VALUES(1)	initial-select。cntテーブルのx列に挿入する
UNION ALL	重複行があっても挿入する
SELECT x+1 FROM cnt WHERE x<10	cntテーブルのx列値が10未満の行を抽出してx+1した値を返す
SELECT x FROM cnt;	一時ビュー(CTE)のx列を全行返す

　なお、今回は重複しないのでUNION ALLからALLを省いても同じ結果になる。ただしUNION ALLのほうがメモリ消費が少ない。UNIONは重複チェックが必要になり、全行データをメモリに保持せねばならないから。可能なかぎりUNION ALLにすべき。

WITH RECURSIVE
  cnt(x) AS (VALUES(1) UNION SELECT x+1 FROM cnt WHERE x<10)
SELECT x FROM cnt;

　VALUES(1)はSELECT 1に置換できる。limit句で制限できる。

WITH RECURSIVE
  cnt(x) AS (
     SELECT 1
     UNION ALL
     SELECT x+1 FROM cnt
      LIMIT 10
  )
SELECT x FROM cnt;

with >           > CTE-table-name > as > (select-statement);
     > recursive >                  ,  <

組織の階層構造を表す

CREATE TABLE org(
  name TEXT PRIMARY KEY,
  boss TEXT REFERENCES org,
  height INT,
  -- other content omitted
);

WITH RECURSIVE
  works_for_alice(n) AS (
    VALUES('Alice')
    UNION
    SELECT name FROM org, works_for_alice
     WHERE org.boss=works_for_alice.n
  )
SELECT avg(height) FROM org
 WHERE org.name IN works_for_alice;

　必ず単一のボスがいる。「アリス」の組織全員の平均身長を計算する。

家系図

　親が二人いる。

CREATE TABLE family(
  name TEXT PRIMARY KEY,
  mom TEXT REFERENCES family,
  dad TEXT REFERENCES family,
  born DATETIME,
  died DATETIME, -- NULL if still alive
  -- other content
);

　「アリス」の先祖を探す。存命のみ。

WITH RECURSIVE
  parent_of(name, parent) AS
    (SELECT name, mom FROM family UNION SELECT name, dad FROM family),
  ancestor_of_alice(name) AS
    (SELECT parent FROM parent_of WHERE name='Alice'
     UNION ALL
     SELECT parent FROM parent_of JOIN ancestor_of_alice USING(name))
SELECT family.name FROM ancestor_of_alice, family
 WHERE ancestor_of_alice.name=family.name
   AND died IS NULL
 ORDER BY born;

　parent_ofは通常の共通テーブル。ancestor_of_aliceは再帰的な共通テーブル。ancestor_of_aliceはrecursive-selectのfrom句で使われている。

グラフ

　バージョン管理システムVCSは通常、プロジェクトの進化するバージョンを有向非巡回グラフDAGとして保存する。プロジェクトの各バージョンを「チェックイン」と呼ぶ。1つのチェックインには、0個以上の親を含めることができる。ほとんどのチェックイン（最初のチェックインを除く）には単一の親があるが、マージの場合、チェックインには2つまたは3つ以上の親がある。チェックインとそれらが発生する順序を追跡するスキーマは、次のようになる。

CREATE TABLE checkin(
  id INTEGER PRIMARY KEY,
  mtime INTEGER -- timestamp when this checkin occurred
);
CREATE TABLE derivedfrom(
  xfrom INTEGER NOT NULL REFERENCES checkin, -- parent checkin
  xto INTEGER NOT NULL REFERENCES checkin,   -- derived checkin
  PRIMARY KEY(xfrom,xto)
);
CREATE INDEX derivedfrom_back ON derivedfrom(xto,xfrom);

　このグラフは非周期的。そして、すべての子チェックインのmtimeは、そのすべての親のmtime以上であると想定している。ただし、前の例とは異なり、このグラフには、2つのチェックイン間で長さが異なる複数のパスがありうる。

　@BASELINEをチェックインするために、（DAG全体の数千および数千の先祖のうちの）最新の20の先祖を知りたい。（これに似たクエリがFossil VCS によって使用され、チェックの最新のN個の先祖が表示される。例：http://www.sqlite.org/src/timeline?p=trunk&n=30）

WITH RECURSIVE
  ancestor(id,mtime) AS (
    SELECT id, mtime FROM checkin WHERE id=@BASELINE
    UNION
    SELECT derivedfrom.xfrom, checkin.mtime
      FROM ancestor, derivedfrom, checkin
     WHERE ancestor.id=derivedfrom.xto
       AND checkin.id=derivedfrom.xfrom
     ORDER BY checkin.mtime DESC
     LIMIT 20
  )
SELECT * FROM checkin JOIN ancestor USING(id);

他

order byによる深さ優先と幅優先

order byによる深さ優先と幅優先

begin transaction;
CREATE TABLE org(
  name TEXT PRIMARY KEY,
  boss TEXT REFERENCES org
) WITHOUT ROWID;
INSERT INTO org VALUES('Alice',NULL);
INSERT INTO org VALUES('Bob','Alice');
INSERT INTO org VALUES('Cindy','Alice');
INSERT INTO org VALUES('Dave','Bob');
INSERT INTO org VALUES('Emma','Bob');
INSERT INTO org VALUES('Fred','Cindy');
INSERT INTO org VALUES('Gail','Cindy');
commit;

-- 深さ優先
WITH RECURSIVE
  under_alice(name,level) AS (
    VALUES('Alice',0)
    UNION ALL
    SELECT org.name, under_alice.level+1
      FROM org JOIN under_alice ON org.boss=under_alice.name
     ORDER BY 2
  )
SELECT substr('..........',1,level*3) || name FROM under_alice;

-- 幅優先
WITH RECURSIVE
  under_alice(name,level) AS (
    VALUES('Alice',0)
    UNION ALL
    SELECT org.name, under_alice.level+1
      FROM org JOIN under_alice ON org.boss=under_alice.name
     ORDER BY 2 DESC
  )
SELECT substr('..........',1,level*3) || name FROM under_alice;

Alice
...Bob
...Cindy
......Dave
......Emma
......Fred
......Gail

Alice
...Bob
......Dave
......Emma
...Cindy
......Fred
......Gail

• ORDER BY 2=ORDER BY under_alice.level + 1

マンデルブロ集合の近似値を計算してASCIIアートで出力

マンデルブロ集合の近似値を計算してASCIIアートで出力

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;

数独パズルを解決する

数独パズルを解決する

WITH RECURSIVE
  input(sud) AS (
    VALUES('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')
  ),
  digits(z, lp) AS (
    VALUES('1', 1)
    UNION ALL SELECT
    CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
  ),
  x(s, ind) AS (
    SELECT sud, instr(sud, '.') FROM input
    UNION ALL
    SELECT
      substr(s, 1, ind-1) || z || substr(s, ind+1),
      instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
     FROM x, digits AS z
    WHERE ind>0
      AND NOT EXISTS (
            SELECT 1
              FROM digits AS lp
             WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
                OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
                OR z.z = substr(s, (((ind-1)/3) % 3) * 3
                        + ((ind-1)/27) * 27 + lp
                        + ((lp-1) / 3) * 6, 1)
         )
  )
SELECT s FROM x WHERE ind=0;

やってみる

通常の共通テーブル

begin transaction;
-- 買い物かご
create table cart(
  id  int not null primary key,
  gid int not null,
  num int not null default(1),
  foreign key(gid) references goods(id)
);
-- 商品
create table goods(
  id    int  not null primary key,
  name  text not null,
  price int  not null
);
insert into goods values(1,'おにぎり',100);
insert into goods values(2,'そば',240);
insert into goods values(3,'日替わり弁当',480);
commit;

.headers on
.mode column

with shopping_cart(gid, num) as (select 1, 7 union select 2, 5 union select 3, 2)
select 
 goods.name, 
 shopping_cart.num, 
 (goods.price*shopping_cart.num) as price 
from goods, shopping_cart
where shopping_cart.gid=goods.id;

name        num         price     
----------  ----------  ----------
おにぎり        7           700       
そば          5           1200      
日替わり弁当      2           960       

• 買い物かごテーブルcartは不要だった
• with句により副問合せせずに済んだ

　もし副問合せするなら以下のようになっていた。

select 
 goods.name, 
 shopping_cart.num, 
 (goods.price*shopping_cart.num) as price 
from goods, (select 1 as gid, 7 as num union select 2 as gid, 5 as num union select 3 as gid, 2 as num) as shopping_cart
where shopping_cart.gid=goods.id;

　列名については1行目だけ指定すればOK。なので以下のように省略できる。

select 
 goods.name, 
 shopping_cart.num, 
 (goods.price*shopping_cart.num) as price 
from goods, (select 1 as gid, 7 as num union select 2, 5 union select 3, 2) as shopping_cart
where shopping_cart.gid=goods.id;

　この例だとイマイチありがたみがわからない。別に副問合せでもそれほど汚くない。強いて言うなら、列の宣言が汚い、出現順序や位置がわかりにくい、くらいか。

再帰的な共通テーブル

リスト

　フィボナッチ数列を作ってみる。

私が書いてエラーになったコード。

with recursive 
  fibonacci(idx,value) as (
    select 0,0 union select 1,1 
    union all 
    select max(idx)+1 as idx, sum(value) as value 
      from fibonacci 
      where idx < 10 
      order by idx desc 
      limit 2
  )
select * from fibonacci;

Error: recursive aggregate queries not supported

　以下、同様の問題にぶつかり、SQLite3では解決不可だったらしい……。

• https://stackoverflow.com/questions/55349403/alternative-for-recursive-aggregate-queries-not-supported-in-sqlite3

• https://qiita.com/neko_the_shadow/items/5b905ba702d9830f72c0

with recursive fib (x, a, b) as (
        select 0, cast(0 as int), cast(1 as int) 
    union all
        select x + 1, b, a + b from fib where x < 100
) select x, a from fib;

x           a         
----------  ----------
0           0         
1           1         
2           1         
3           2         
4           3         
5           5         
6           8         
7           13        
8           21        
9           34        
10          55        
11          89        
12          144       
13          233       
14          377       
15          610       
16          987       
...

• x: index
• a: 1つ前の値
• b: 2つ前の値＋1つ前の値

　つまり以下のように処理している。

• b列に合算値を退避させておいて、次のレコードではbの値をa列にセットする

　よってa列とb列は1つずれただけの同じ内容。

x           a           b         
----------  ----------  ----------
0           0           1         
1           1           1         
2           1           2         
3           2           3         
4           3           5         
5           5           8         
6           8           13        
7           13          21        
8           21          34        
9           34          55        
10          55          89        
11          89          144       
12          144         233       
13          233         377       
14          377         610       
15          610         987       
16          987         1597      
...

　ならもうb列の先頭に0を追加すればいいのでは？　と思ったが「前の行」を参照できないせいで不可能。よって前の行のデータを同一行の別列に挿入している。

　この盛大な無駄が気持ち悪い。

ツリー

begin transaction;
create table nodes(
  id     int  not null primary key,
  name   text not null,
  parent int  not null
);
insert into nodes values(1, 'root', 0);
insert into nodes values(2, 'n1', 1);
insert into nodes values(3, 'n11', 2);
insert into nodes values(4, 'n2', 1);
commit;

• https://stackoverflow.com/questions/3897952/creating-a-list-tree-with-sqlite

with recursive 
  tree(id, depth) as (
    select 1, 0
    union all
    select n.id, t.depth+1
      from nodes n inner join tree t on n.parent=t.id
  )
select substr('..........', 0, t.depth+1) || n.name from tree t inner join nodes n on t.id=n.id;

substr('..........', 0, t.depth+1) || n.name
--------------------------------------------
root                                        
.n1                                         
.n2                                         
..n11                                  

　違う。期待値は以下。上記は親がどのレコードであるかすら把握できていない。

　期待値は以下。

root/n1/n11
root/n2

以下のように書いてみたがダメ。

with recursive 
  tree(parent, id, path) as (
    select 0, 1, 'root'
    union all
    select n.parent, n.id, n.parent || '/' || n.name 
      from nodes n inner join tree t on n.id=t.parent
  )
select * from tree;

parent      id          path      
----------  ----------  ----------
0           1           root    

　わからんのでググった。

• https://stackoverflow.com/questions/51585126/how-to-get-a-hierarchical-tree-path-in-sqlite

with recursive paths(id, name, path) as (
    select id, name, name from nodes where parent=0
    union
    select nodes.id, nodes.name, paths.path || '/' || nodes.name
    from nodes join paths where nodes.parent = paths.id
)
select id, path from paths;

id          path      
----------  ----------
1           root      
2           root/n1   
4           root/n2   
3           root/n1/n1

　最後のが見切れてる。

.headers on
.mode list
.separator '|'

id|path
1|root
2|root/n1
4|root/n2
3|root/n1/n11

　できてる。OK。

　何が間違っていたのか。以下のようにするとできた。

with recursive 
  tree(id, name, path) as (
    select id, name, name from nodes where parent=0
    union all
    select n.id, n.name, t.path || '/' || n.name 
      from nodes n inner join tree t on n.parent=t.id
  )
select * from tree;

1|root|root
2|n1|root/n1
4|n2|root/n2
3|n11|root/n1/n11

　再帰テーブル.path || nodes.nameとすべきだった。

　ところで、name列いらないので省略する。

with recursive 
  tree(id, path) as (
    select id, name from nodes where parent=0
    union all
    select n.id, t.path || '/' || n.name 
      from nodes n inner join tree t on n.parent=t.id
  )
select * from tree;

1|root
2|root/n1
4|root/n2
3|root/n1/n11

　ついでにnameでなくidパスも作る。

with recursive 
  tree(id, path, id_path) as (
    select id, name, id from nodes where parent=0
    union all
    select n.id, t.path || '/' || n.name, t.id_path || '/' || n.id 
      from nodes n inner join tree t on n.parent=t.id
  )
select * from tree;

1|root|1
2|root/n1|1/2
4|root/n2|1/4
3|root/n1/n11|1/2/3

グラフ

　RDFのトリプル形式を使う。

begin transaction;
create table nodes(
    id   int  not null primary key,
    name text not null
);
create table edges(
    id   int  not null primary key,
    name text not null
);
create table triples(
    id        int not null primary key,
    subject   int not null references nodes(id),
    predicate int not null references edges(id),
    object    int not null references nodes(id)
);

insert into nodes values(1,'I');
insert into nodes values(2,'PI3B+');
insert into nodes values(3,'PI4B');
insert into edges values(1,'love');
insert into edges values(2,'broke');
insert into edges values(3,'buy');
insert into triples values(1,1,1,2);
insert into triples values(2,1,2,2);
insert into triples values(3,1,1,3);
insert into triples values(4,1,3,3);
commit;

　目的語がPI3B+である述語をすべて取得するとき。

select e.name 
from (
  select predicate 
  from triples t where t.object=2
) as s inner join edges e 
on s.predicate=e.id;

love
broken

　述語がloveの目的語をすべて取得するとき。

select n.name 
from (
  select object 
  from triples 
  where predicate=1
) as o inner join nodes n 
on o.object=n.id;

PI3B+
PI4B

　あれ、再帰処理を使うべき状況が思いつかない……。

generate_series

• https://www.sqlite.org/series.html

　1列だけ持つ行を作る。generate_seriesという拡張関数がある。これはコンパイルする必要がある。だが、以下のようにWITH RECURSIVEで再現できる。

構造

WITH RECURSIVE generate_series(value) AS (
  SELECT $start
  UNION ALL
  SELECT value+$step FROM generate_series
   WHERE value+$step<=$end
) ...

0〜10までの連番を11個

WITH RECURSIVE generate_series(value) AS (
  SELECT 0
  UNION ALL
  SELECT value+1 FROM generate_series
   WHERE value+1<=10
)
select * from generate_series;

0
1
2
3
4
5
6
7
8
9
10

0〜99までの値をランダムに11個

WITH RECURSIVE generate_series(value) AS (
  SELECT 0
  UNION ALL
  SELECT value+1 FROM generate_series
   WHERE value+1<=10
)
select (abs(random()) % 100) from generate_series;

78
78
72
7
69
85
72
77
44
7
2

所感

　自力では何一つ思い通りに再帰クエリを書けなかった。悔しすぎる。

対象環境

• 2019-08-13
• Raspbierry pi 3 Model B+
• Raspbian stretch 9.0 2018-11-13
• bash 4.4.12(1)-release
• SQLite 3.29.0

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1218 SMP Tue May 14 00:48:17 BST 2019 armv7l GNU/Linux

前回まで

• SQLite3学習をはじめよう
• SQLite3学習　SQLiteについて
• SQLite3学習　SQLiteの適切な用途
• SQLite3学習　SQLiteの特徴
• SQLite3学習　SQLiteのクセ
• SQLite3学習　データ型とアフィニティ
• SQLite3学習　演算子の一覧
• SQLite3学習　よくある質問
• SQLite3学習　SQLiteダウンロード＆コンパイル
• SQLite3学習　Tclで操作する
• SQLite3学習　ビルドオプション動作確認（SQLITE_ALLOW_URI_AUTHORITY）
• SQLite3学習　面白そうなコンパイルオプション
• SQLite3学習　SQLiteの拡張について
• SQLite3学習　JSON拡張
• SQLite3学習　JSON拡張（json_extract）
• SQLite3学習　JSON拡張（json_each）
• SQLite3学習　JSON拡張（json_tree オブジェクト→行）
• SQLite3学習　JSON拡張（json_tree オブジェクトツリー→行）
• SQLite3学習　JSON拡張（json_tree オブジェクト配列→行）
• SQLite3学習　JSON拡張（json_group_array 行→配列）
• SQLite3学習　JSON拡張（json_group_object 行→オブジェクト）
• SQLite3学習　JSON拡張（json_array_length）
• SQLite3学習　JSON拡張（json_type）
• SQLite3学習　JSON拡張（json_valid）
• SQLite3学習　JSON拡張（json_quote）
• SQLite3学習　JSON拡張（json_array）
• SQLite3学習　JSON拡張（json_object）
• SQLite3学習　JSON拡張（json_patch）
• SQLite3学習　JSON拡張（json_insert）
• SQLite3学習　JSON拡張（json_replace）
• SQLite3学習　JSON拡張（json_set）
• SQLite3学習　JSON拡張（json_remove）
• SQLite3学習　全文検索（FTS5）
• SQLite3学習　全文検索FTSを日本語で使う方法を調べてみた
• 形態素解析MeCabをインストールする
• SQLite3学習　全文検索FTS5のMeCab用トークナイザを実装する
• SQLite3学習　FTS5+MeCabでクエリ構文
• SQLite3学習　FTS5のテーブル作成と初期化
• SQLite3学習　FTS5の補助関数
• SQLite3学習　FTS5のfts5vocab仮想テーブル