各ディレクトリにアクセス可能なユーザーのリストを再帰SQLで求める

問題設定

ディレクトリのツリーがある。
各ディレクトリごとに、そのディレクトリへのアクセスを許可するユーザーのリストが定義されており、このリストに入っていないユーザーはそのディレクトリにアクセスできない。
さらに、あるディレクトリにアクセスできないユーザーは、その子孫のディレクトリにもアクセスできない。
このとき、各ディレクトリにアクセスできるユーザーのリストを求めたい。

準備

今回は、例としてこのようなディレクトリのツリーを考える。

ユーザー Caroline はディレクトリ subsub にアクセス可能なユーザーのリストに含まれているが、その親ディレクトリの sub1 にアクセスできないため、ディレクトリ subsub にもアクセスできない。

これをSQLで表現する。
今回は、SQLite3を使用する。

dirs テーブルには、ディレクトリの名前 name とその親ディレクトリの名前 parent を格納する。
親ディレクトリが存在しない場合、parent は NULL である。

accessors テーブルには、ディレクトリの名前 dir とそのディレクトリにアクセス可能なユーザーの名前 name を格納する。

CREATE TABLE dirs (
	name TEXT NOT NULL,
	parent TEXT
);

CREATE TABLE accessors (
	dir TEXT NOT NULL,
	name TEXT NOT NULL
);

INSERT INTO dirs (name, parent) VALUES
	('top', NULL),
	('sub1', 'top'),
	('sub2', 'top'),
	('subsub', 'sub1');

INSERT INTO accessors (dir, name) VALUES
	('top', 'Alice'),
	('top', 'Bob'),
	('top', 'Caroline'),
	('top', 'David'),
	('sub1', 'Bob'),
	('sub1', 'David'),
	('sub2', 'Alice'),
	('sub2', 'David'),
	('subsub', 'Bob'),
	('subsub', 'Caroline');

実際のデータベースでは、

• 主キーを設定する
• 外部キー制約を設定する
• ディレクトリやユーザーの名前を直接格納せずにIDで管理する

などを行ったほうがいい可能性があるが、今回は簡単のため省略する。

再帰SQLとは

再帰SQLでは、SELECT文の実行結果として得られたテーブルを次の入力として用いることで、繰り返しデータを処理して結果を求めることができる。
(SQLite3における) 再帰SQLは、以下の形式で表せる。

WITH RECURSIVE withテーブルの形式 AS (
	非再帰項
	UNION ALL
	再帰項
)
メインクエリ;

これは、以下のように実行される。

1. 空の結果テーブルを用意する
2. 「非再帰項」を実行し、結果をwithテーブルに格納・結果テーブルに追加する
3. 「再帰項」を実行する。このとき、withテーブルの内容を参照できる
4. 「再帰項」を実行した結果が1行以上あれば、実行した結果をwithテーブルに格納・結果テーブルに追加し、3に戻る
   結果が0行の場合は、メインクエリを実行する。このとき、結果テーブルの内容をwithテーブルとして参照できる

詳しくは、以下のページを参照するとよい。

再帰SQL -図解- #Database - Qiita

各ディレクトリにアクセス可能なユーザーを求める

以下のSQLクエリにより、今回の問題において各ディレクトリにアクセス可能なユーザーを求めることができる。

WITH RECURSIVE allowedUsers(dirName, nextDirName, accessor) AS (
	SELECT dirs.name, dirs.parent, accessors.name
	FROM dirs
	INNER JOIN accessors ON dirs.name = accessors.dir
	UNION ALL
	SELECT allowedUsers.dirName, dirs.parent, allowedUsers.accessor
	FROM dirs
	INNER JOIN accessors ON dirs.name = accessors.dir
	INNER JOIN allowedUsers ON dirs.name = allowedUsers.nextDirName
	WHERE allowedUsers.accessor = accessors.name
)
SELECT dirName as dir, accessor
FROM allowedUsers
WHERE nextDirName IS NULL;

まず、非再帰項で以下の組を求める。

• ディレクトリ名
• 次にチェックを行うディレクトリ (親) 名
• そのディレクトリにアクセスできるユーザー名

あるユーザーがあるディレクトリにアクセスできる必要条件の一つは、そのディレクトリのアクセス許可リストにそのユーザーが載っていることである。
この非再帰項は、この条件のチェックに相当する。

次に、再帰項でディレクトリツリーを登り、親のアクセス許可リストのチェックを行う。
あるユーザーが親のアクセス許可リストにも入っていれば、さらにその親のチェックに進むことができる。
一方、親のアクセス許可リストに入っていなければ、登れずにチェックは終了する。

最後に、メインクエリで最後 (親が NULL) まで登れたディレクトリとユーザーの組のリストを取得する。

以下の実行結果が得られた。

dir	accessor
top	Alice
top	Bob
top	Caroline
top	David
sub1	Bob
sub1	David
sub2	Alice
sub2	David
subsub	Bob

前述のディレクトリツリーの各ディレクトリにアクセス可能なユーザーのリストがきちんと求まっているようである。