SQL _ 入れ子集合、入れ子区間モデルでサイトマップ作成:SQLite

入れ子集合モデルでサイトマップ　by SQLite

入れ子集合モデルを利用したツリー型サイトマップ構築のために必要となるSQL文を概観してみます。まずは、SQLiteでつくる場合。MySQLの構文は次のページに

データベースファイル
SQLiteでは、１ファイル１データベースなので、１ファイル内に全てのテーブルを作ります。
テーブル構造
３つのテーブルに分けて情報管理をします。
以下、SQLiteの構文に沿って、識別子(テーブル名やカラム名)を[] でくくっています。
- [pageinfo] : ページ名に紐付く情報テーブル
```
CREATE TABLE [pageinfo](
 [pageid]  char  PRIMARY KEY  NOT NULL
,[pagename]  NOT NULL	/* ページ表題 */
,[uri]    	/* リンク表示用URI */
,[modify] DATE  CHECK( modify like '____-__-__')
,[file]   	/* ページ更新日チェック用のfilepath */
,[memo]   	/* ページ説明 */
);
```
  ※　pageid は他のテーブルでpageを特定するために使います。pageidをauto increment で数値にすると、pageidを見ただけでは、ページ名が判らず、入力時や再編集の時に面倒なので、自分で区別をつけられる最小コード文字列を入れることにしました。
  SQLite では、カラムの型は、基本無視されるので、記述していません。プログラム上どんなデータをいれておきたいかのメモ的に char やdateを入れています。日付は、日付関数が解釈しやすいように、check構文で書式を決めています。
- [nestset] : ツリー構造用
  「入れ子集合（nest set）」または、「入れ子区間」を利用して、左位置（小さい方）と右位置（大きい方）とで、階層の内外をわけて、内部階層を樹木状に分岐することで、ツリー構造を形成します。カラム名は、単純にleft, right としてしまうと予約語とかぶり、常に識別子用のくくりが必要になるので、以下では、_pos を接尾辞としています。
```
CREATE TABLE [nestset](
 [pageid]   CHAR PRIMARY KEY NOT NULL	/* [pageinfo]テーブル との関連付け用 */
,[left_pos]   float UNIQUE  NOT NULL
,[right_pos]  float UNIQUE  NOT NULL
  CHECK (left_pos < right_pos)
);
 CREATE INDEX tree_index ON [nestset] ([left_pos] ASC);
```
  ※　サイトマップ内での表示順は、left_pos でツリー構造になる。
  表示順を変えたい時は、整数を使う場合、密に並んでいると兄弟分岐ページのleft_pos と right_posも軒並み変更が必要になりますが、とびとびにしておけば、間に挿入も可能。であれば、最初から、float として、小数値表記で無限の区間を得られる。
  ※　SQLで木構造を扱う～入れ子区間モデルに区間値を実数で扱う方法が紹介されている
  ※　「入れ子集合モデル（Nest Set）」については、「SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル」を御参照下さい。
  ※　左右データの整合性については、上記では left_pos < right_pos しかチェックしていないが、互いのカラムの他の行に同じデータがあってもツリー構造が壊れるので、プログラムからinsert前にチェックするか、triggerをつけて阻止するなどが、必要だろう。
- [history] : 更新履歴
```
create table [history](
 [id] INTEGER  PRIMARY KEY	/* 登録順保持 */
,[pageid]  	/* [pageinfo]との関連づけ用  */
,[modify]  DATE  CHECK( modify like '____-__-__')
,[comment] 
);
 CREATE INDEX newer_index ON [history] ([modify] DESC, [id] DESC);
```
  ※　ページ更新日順に登録していれば、登録順のid は必要ないかもしれないけど、後日データを編集したりすることもあるので、行特定のためにidを付けます。

data sample

サンプルなので架空データとしています。

[pageinfo]用データ


INSERT INTO  [pageinfo] VALUES ('tools','小道具箱','/','2007-12-23','/index.shtml','プログラム小道具');
INSERT INTO  [pageinfo] VALUES ('phptools','php 小道具箱','/php/','2009-12-05','/php/index.php','phpプログラムリスト');
INSERT INTO  [pageinfo] VALUES ('sitemap','サイトマップ','/php/samplemap.php','2009-12-05','/php/data/map.sqlite','ツリー型サイトマップ');
INSERT INTO  [pageinfo] VALUES ('history','更新履歴','/php/samplehistory.php','2009-12-05','/php/data/map.sqlite','サイト更新履歴');
INSERT INTO  [pageinfo] VALUES ('sqlmap','php sqliteでサイトマップ','/php/map/index.shtml','2009-12-05','/php/map/index.shtml','サイトマップの作り方');

※　日付データは、SQLiteの日付関数が解釈する形式 YYYY-MM-DD で入力します。

[nestset]用データ

５つくらいなら、適当に考えて数値をいれてもよいのだが、多くなると、プログラムで、位置判定させて、データを作っていく方がよい。


INSERT INTO  [nestset] VALUES ('tools', 0.0 , 1.0);
INSERT INTO  [nestset] VALUES ('phptools', 0.1,  0.2);
INSERT INTO  [nestset] VALUES ('sitemap' , 0.9,  0.99);
INSERT INTO  [nestset] VALUES ('history' , 0.95, 0.96);
INSERT INTO  [nestset] VALUES ('sqlmap'  , 0.13, 0.14);

[history]用データ


INSERT INTO  [history] VALUES (null,'tools','2007-11-11','サイト開設');
INSERT INTO  [history] VALUES (null,'phptools','2007-11-11','php ページ設置');
INSERT INTO  [history] VALUES (null,'sitemap','2010-01-11','サンプルサイトマップ設置');
INSERT INTO  [history] VALUES (null,'history','2010-01-11','サンプル更新履歴設置');
INSERT INTO  [history] VALUES (null,'sqlmap' ,'2010-01-17','php sqlite サイトマップ構築解説');

データ一覧SQL文

サイトマップのツリー表示


SELECT  t.pageid, t.left_pos
 , ( select count(*) -1 from [nestset] as parent 
     where  t.left_pos between parent.left_pos and parent.right_pos
   ) as plevel
 , m.pagename as name, m.uri as uri, m.modify as modify, m.memo as comment
 , julianday('now', 'localtime') - julianday(m.modify, 'localtime') as pastdays
  FROM [nestset] as t , [pageinfo] as m ON t.pageid = m.pageid
  ORDER BY t.left_pos ;

※　親階層数を、サブクエリで求めています。入れ子区間の定義から、親の区間 parent.left_pos から parent.right_pos の間に、求める子ノードがあるので、
t.left_pos between parent.left_pos and parent.right_pos この条件にマッチするものは親と自分ノードとなり、その個数-1 を親階層数としています。
pastdaysのところは、サイトの更新日[pageinfo].modify から何日たっているかを算出しています。この日数により、新着マークを出すのが目的です。

 php でのulタグによるツリー構造出力
<?php
  $res  = /* 上記sql実行結果用リソースを$resに代入、PDO接続など省略 */ ;
  $rows = $res->fetchAll(PDO::FETCH_ASSOC );//  全行、ハッシュ配列　で取得
  $p = -1;  // 初期値 = rootの親階層数 -1
  $newstr = '<span style="color:red;">new</span>';
  $newdays= 31;
  foreach($rows as $row){
    $starter= "\n";
    $rp = intval( $row['plevel'] );  // 自分までの階層レベル; intvalは整数変換
    //  階層レベルチェック：
    if( $p< $rp ){  // 子の開始
      $p ++;
      $starter .= '<ul><li>';
    }else {
      if( ($dp= $p-$rp) > 0 ){
      // 前の 子の終了 </ul> をstarterに入れて閉じる
        $p = $rp;
        $starter .= str_repeat('</li></ul>', $dp);
      }
      // 現在levelの開始
      $starter .= '</li><li>';
    }
    $puri = htmlspecialchars($row['uri']);
    $pname= htmlspecialchars($row['name']);
    $new = '';
    if($newdays > $row['pastdays'] ){
      $new = $newstr;
    }
    print <<<OUT
$starter <a href="$puri" >$pname</a> ({$row['modify']}) $new 
OUT;
  }
  echo str_repeat('</li></ul>', $p+1);  // 残りの親階層+rootの閉じ
?>

更新履歴に祖先リストをつける

※　まずは、ページ名とリンク情報を付けるため、[pageinfo] テーブルと結合します。また、[nestset].pageid の存在有無によって、リンク用Aタグを付けるかを決めます。


SELECT  h.id as hid
 , m.pagename as pagename,  m.uri as uri 
 , h.modify as hmodify, h.comment as comment
 , t.pageid as linkcheck
  FROM [history] as h LEFT JOIN [pageinfo] as m  ON  h.pageid = m.pageid
    LEFT JOIN [nestset] as t ON m.pageid = t.pageid
  ORDER BY  hmodify desc,hid desc  LIMIT 30 OFFSET 0 ;

※　さらに親階層情報も同時に表示したい場合には、[nestset]から、祖先から子までの　pageid　リストを経路列挙のように取り出しておき、さらに[pageinfo]テーブルからも、pageid , pagename , uri を取り出して、pageid をキーとする配列に入れて、php側でpageidでひもづけて出力していきます。


//[nestset]の自己結合で 「.」文字で連結した親pageidのリストを得る
SELECT  t.pageid , group_concat('.', p.pageid) as pageroute
  FROM  [nestset] as t 
   join  [nestset] as p on  t.left_pos between p.left_pos and p.right_pos
   group by  t.pageid

経路列挙のような親pageidのリストを得るサブクエリを、historyに結合して、必要データを取り出します。


SELECT  h.id as hid
 , m.pagename as pagename,  m.uri as uri 
 , h.modify as hmodify, h.comment as comment
 , t.pageid as linkcheck , t.pageroute
  FROM [history] as h LEFT JOIN [pageinfo] as m  ON  h.pageid = m.pageid
    LEFT JOIN  
     ( SELECT  c.pageid , group_concat('.', p.pageid) as pageroute
         FROM  [nestset] as c
         join  [nestset] as p on  c.left_pos between p.left_pos and p.right_pos
         group by  c.pageid
     ) as t ON h.pageid = t.pageid
  ORDER BY  hmodify desc,hid desc  LIMIT 30 OFFSET 0 ;

あと、[pageinfo]テーブルから先に、pageid , pagename , uri を取り出して、pageid をキーとする配列に入れておけば、上記の pageid リスト部分に置き換えが可能となる。


//  pageid にひも付く、pagename,uri 取り出しSQL
select pageid, pagename, uri  from [pageinfo] ;
<?php
	$res  = /* 上記sql実行結果用リソース */ ;
	$pagehash = array();
	while( $row = $res->fetch(PDO::FETCH_ASSOC ) ){
		$pagehash[$row['pageid']] = $row;
	}
?>

// 更新履歴データ取り出しsql
SELECT  h.id as hid, h.modify as hmodify, h.comment as comment , h.pageid as pageid
 , t.pageid as linkcheck , t.pageroute as route
  FROM [history] as h 
    LEFT JOIN  
     ( SELECT  c.pageid , group_concat('.', p.pageid) as pageroute
         FROM  [nestset] as c
         join  [nestset] as p on  c.left_pos between p.left_pos and p.right_pos
         group by  c.pageid
     ) as t ON h.pageid = t.pageid
  ORDER BY  hmodify desc,hid desc  LIMIT 30 OFFSET 0 ;
<?php
	$res  = /* 上記sql実行結果用リソース */ ;
	$rows = $res->fetchAll(PDO::FETCH_ASSOC );	//  全行、ハッシュ配列
	$rcnt = count($rows);
	print <<<OUT
<table border='1'>
<caption>サイト新着履歴  新着順 {$rcnt}件</caption>
<thead><tr><th>登録番号</th><th>更新日</th><th>ページ名</th><th>コメント</th><th>/ 親ツリー /</th></tr></thead>
<tbody>
OUT;
	foreach($rows as $row ){
		$parent = '';
		if(! empty( $row['route']) ){
			$plist = explode('.', $row['route'] );
			$parent ='/';
			$len = count($plist) -2;
			for( $j=1; $j<$len ; $j++){
				$path   = $plist[$j];
				$parent .= ' <a href="'
					.htmlspecialchars($pagehash[$path]['uri']).'">'
					.htmlspecialchars($pagehash[$path]['pagename'])
					.'</a> /';
			}
			$path   = $plist[$len];	//  終端は、履歴対象ページ
			$pdata = '<a href="'
					.htmlspecialchars($pagehash[$path]['uri']).'">'
					.htmlspecialchars($pagehash[$path]['pagename'])
					.'</a>';
		}else{
			$pdata ='<del>'.htmlspecialchars($pagehash[$row['pageid']]['pagename']).'</del>';
		}
		$memo = htmlspecialchars($row['comment']);
		print <<<OUT
<tr><td>{$row['hid']}</td><td>{$row['hmodify']}</td>
<td>{$pdata}</td><td>{$memo}</td><td>{$parent}</td>
</tr>
OUT;
	}
	print <<<OUT
</tbody></table>
OUT;
?>

root node の　pageid取得

left が最小値である


SELECT pageid FROM [nestset]  WHERE  [left_pos]= min([left_pos])  ;

自分の外側となる親がいないという条件で記述、こちらだとrootが複数になっていないかもチェックできる。


select pageid from [nestset] c
 where  not exists 
   ( select * from [nestset] p where c.left_pos > p.left_pos and c.right_pos < p.right_pos )
 ;

あるpageidページ(例'sqlmap')までの祖先nodeの[pageinfo]情報全部取得


SELECT p.left_pos, p.pageid , i.*
 FROM [nestset] as  t 
   left join [nestset]  as p on  t.left_pos between parent.left_pos and parent.right_pos
   left join [pageinfo] as i on  p.pageid = i.pageid
 WHERE  t.pageid = 'sqlmap'
 order by p.left_pos

あるpageidページ(例'phptools')の子孫nodeの[pageinfo]情報全部取得

自己結合を使います。


select c.left_pos,   i.*
 from `nestset` as  t 
    join [nestset]  as c on ( c.left_pos between t.left_pos and t.right_pos ) and   t.pageid = 'phptools'
   left join [pageinfo] as i on  p.pageid = i.pageid
 order by c.left_pos
 ;

データ更新SQL文

ページ情報の新規追加

※　同階層の既存pathidより後方に終端ノードとなるページを追加する場合をまず考えてみましょう。
※　各テーブルのinsert文は既に列挙されていますが、最小限のデータ入力とするために必要な項目を列挙しますと、

[pageinfo]の全カラムデータ , modifyについては、file のパスからファイルの更新日を取得する場合には新たな入力は不要。
[history].comment , modifyについては、[pageinfo].[modify]と同じにするなら新たな入力は必要ないが、別な日付に設定したい時に必要。

[nestset] については、親となるページのpageidと、どの兄弟の後に追加するのかの兄弟pageid　とがあれば、挿入は可能。よって、直接 [nestset] のカラムデータを指定する必要はない。

ノードの左右位置指定方法

ノードの左右位置指定は、親ノードの left,right 内で指定sibling の right より後方位置で、そのsiblingよりさらに後方のsibling left の前方位置　となる
親の最初の兄弟にするときは、sibling にも親のpageidを指定することにする
親兄弟、挿入対象thisのleft right 関係は、次の順　 parent.left , sibling.right , this,left,this.right , nextsib.left , parent.right 　よってまずは parent.left , sibling.right のうちどちらか大きい方を pre_left とし、 nextsib.left , parent.right のうち小さい方（存在する方）を post_right として式を作る。実数指定なら、this,left,this.right は以下のように算出

this.left  = pre_left + (post_right-pre_left)/3 = (pre_left*2 + post_right)/3
this.right = pre_left + (post_right-pre_left)*2/3 = (pre_left + post_right*2)/3

sibling.right は sibling.pageid からすぐ抽出できる。 nextsib.left　は、sibling　と　親pageid から決定できる。 next が無ければ、親のrightになる。
以下、SQLiteでは、１行１カラムで返ってくるスカラーサブクエリを文字列または比較値として、計算が可能です。

それぞれを得る select 文


-- 1 前方 :sibling_pageid のright 取得
select 'preleft' as pos , right_pos
  from  [nestset]
  where pageid = :sibling_pageid;
--  :sibling_pageid = :parent_pageid のときは、parent.leftを抽出
select 'preleft' as pos , left_pos
  from  [nestset]
  where pageid = :parent_pageid;

-- 2 後方 :sibling_pageid の後方兄弟のleft 取得
--  後方弟の最初、または、兄弟がいなければ、親の最後ということは、
--  左右あわせたテーブルとして、前方値の直後を探せばよい。
--  まずは parent != sibling のとき
select "post_right" as pos_name , min(seq)
  from  ( select left_pos as seq from `nestset` 
         union all
         select right_pos  from `nestset`
        ) as seq_view
  where seq > ( select right_pos from `nestset` where  pageid = :sibling_pageid )
 ;
--  親の先頭挿入 parent = siblingの場合
select "post_right" as pos_name , min(seq)
  from  ( select left_pos as seq from `nestset` 
         union all
         select right_pos  from `nestset`
        ) as seq_view
  where seq > ( select left_pos  from `nestset` where  pageid = :parent_pageid ) 
 ;

seq_view のサブクエリは以降の左右データチェックでも使うので、view に定義


create view [seq_view]
as  select left_pos as seq, pageid from [nestset]
    union all
    select right_pos , pageid  from [nestset]
 ;

pre_left , post_right をいっぺんに取得


-- 1 parent_pgaid と sibling_pageid とが異なるとき
select 'pre_left' as pos , right_pos
  from  [nestset]
  where pageid = :sibling_pageid
union
select 'post_right'  , min(seq)
  from  [seq_view]
  where seq > ( select right_pos from [nestset] where  pageid = :sibling_pageid )
 ;


-- 2 :sibling_pageid = :parent_pageid のとき
select 'pre_left' as pos , left_pos
  from  [nestset]
  where pageid = :parent_pageid
union 
select 'post_right' as pos , min(seq)
  from  [seq_view]
  where seq > ( select left_pos  from [nestset] where  pageid = :parent_pageid )
;

計算元となるデータ取得中に、他のアクセスから変更されると、値が狂ってしまうので、これらはtransaction 内で実行する。

※　以下にphpでpost データを得てinsert するソースの概略を提示します。

<?php 
/*  まずは クロージャによるcallback関数定義、pageidは 英字、数字と _ のみで10文字以内とする  */
$checkid = function($a){  
	 if(preg_match('/^[a-zA-Z0-9_]{1,10}$/', $a) ){	return $a;
	 }
	 return null;
  };

/* 入力データ取得 php 5.2.0 以降の filter_input_array(INPUT_POST, $args);を利用 */
$args = array(
	  'pageid' => array( 'filter'=>  FILTER_CALLBACK 
			 , 'options' => $checkid 
			 )
	, 'pagename' => array( 'filter'=> FILTER_SANITIZE_STRING	//  tagの除去
			 , 'flag' => FILTER_FLAG_STRIP_LOW
			 )
	, 'uri'      => FILTER_SANITIZE_URL
	, 'filepath' => FILTER_SANITIZE_URL
	, 'memo'     => FILTER_SANITIZE_STRING	//  tagの除去
	, 'parentid' =>  array( 'filter'=>  FILTER_CALLBACK 
			 , 'options' => $checkid 
			 )
	, 'siblingid' =>  array( 'filter'=>  FILTER_CALLBACK 
			 , 'options' => $checkid 
			 )
	, 'comment'  => FILTER_SANITIZE_STRING
	);
$myinputs = filter_input_array(INPUT_POST, $args);
if($myinputs['pageid'] !== null and $myinputs['parentid'] !== null and $myinputs['siblingid'] !== null
){	//  pageid が正しければ、以降を実行
 $sitepath =  $_SERVER['DOCUMENT_ROOT'];	//  入力file path の基準となるディレクトリー指定
 $file = $sitepath.$myinputs['filepath'];
 $pagemodify = date ( 'Y-m-d', (file_exists($file)? filemtime($file) : time()) );
 $hismodify = $pagemodify;

// rollback は、全テーブルで行いたいのでここで transaction  開始しておく: $pdo に接続オブジェクト格納済みとする
$pdo->beginTransaction();
try{
// 名前付きプレースホルダーを使ってデータ入力
// 1. [pageinfo] テーブル  error 時は rollback させるので、 IGNORE は入れない
$sql = <<<SSS
INSERT  INTO  [pageinfo] VALUES (:pageid,:pagename,:uri,:modify,:file,:memo);
SSS;
$data = array(':pageid'=>$myinputs['pageid']
 ,':pagename'=>$myinputs['pagename']
 ,':uri'=>$myinputs['uri']
 ,':modify'=>$pagemodify
 ,':file'=>$myinputs['filepath']
 ,':memo'=>$myinputs['memo'] );
/* query 実行　省略  */

// 2. [nestset] テーブル : 初回は左右固定、初回以外はselectしてデータ作成の切り分け必要
 if( /*  [nestset] の行数チェック、０行の場合 */ ){
  $data = array(':pageid'=>$myinputs['pageid'], ':left'=> 0.0 , ':right'=> 1.0 );
 }else{
  //  前方後方位置データ取得
  if( $myinputs['parentid'] !== $myinputs['siblingid'] ){
   $data = array(':siblingid'=>$myinputs['siblingid'] );
   $sql = <<<SSS
select 'pre_left' as pos_name , right_pos as position
  from  [nestset]
  where pageid = :sibling_pageid
union
select 'post_right' as pos , min(seq)
  from  [seq_view]
  where seq > ( select right_pos from [nestset] where  p.pageid = :sibling_pageid )
SSS;
  }else{
   $data = array( ':parentid'=>$myinputs['parentid'] );
   $sql = <<<SSS
select 'pre_left' as pos_name , left_pos as position
  from  [nestset]
  where pageid = :parent_pageid
union 
select 'post_right' as pos , min(seq)
  from  [seq_view]
  where seq > ( select left_pos  from [nestset] where  pageid = :parent_pageid )
SSS;
  }
//  計算元データ取得
 $stmt = $pdo->prepare($sql);
 $stmt->execute($data);
 $res = $stmt->fetchAll(PDO::FETCH_ASSOC);
 unset($pre_left, $post_right);
 foreach($res  as  $row){
   if( $row['pos_name'] === 'pre_left' ){
     $pre_left = floatval( $row['position'] );
   }else if( $row[pos_name] === 'post_right' ){
     $post_right = floatval( $row['position'] );
   }else if( ! isset($post_right) ){
     $post_right = floatval( $row['position'] );
   }
 }
 $left =  ($pre_left * 2 + $post_right )/3.0 ;
 $right = ($pre_left + $post_right * 2 )/3.0 ;

 $data = array(':pageid'=>$myinputs['pageid']
        , ':left'=> $left
        , ':right'=> $right );
}
$sql = <<<SSS
INSERT INTO  [nestset] VALUES (:pageid ,:left, :right );
SSS;
//  数値データがあるので、bindValue する
$stmt = $pdo->prepare($sql);
$stmt->bindValue( ':pageid' , $data[':pageid'] , PDO::PARAM_STR );
$stmt->bindValue( ':left' , $data[':left'] , PDO::PARAM_INT );	//  float も int もそのまま１０進数表記で書き出してくれる
$stmt->bindValue( ':right' , $data[':right'] , PDO::PARAM_INT );
$stmt->execute();

// 3. [history] テーブル
$sql = <<<SSS
INSERT OR IGNORE INTO  [history] VALUES (null,:pageid,:modify,:comment);
SSS;
$data = array(':pageid'=>$myinputs['pageid']
      , ':modify'=>$hismodify,':comment'=>$myinputs['comment'] );
/* query 実行　省略  */

//  エラー無く実行し得たら、commit ,  pdo の例外発生モードである前提
  $pdo->commit();
 } catch (PDOException $e) {
   echo  "エラー!: rollBackします:". $e->getMessage();
  $pdo->rollback();
}else{
   echo 'bad pageid';
}
?>

ノードの移動
※　あるノードとその下位を含めて、別の親ノードの下層へ移すには、移したい位置の手前にあるノードの終端　と、　後方ノードの先端　の位置を求めて、その間へ詰め込むように、対象ノード群のleft,right を算出します。
移動先の前方後方データは、移動先親のpageid(:parent_pageid) と、挿入したい前方兄弟のpageid(:sibling_pageid) とから、前述のノードの左右位置指定法で$pre_left, $post_rightとして求められるので、この１／３位置に対象ノード群をはめ込む
SQLiteでは、update 文内のサブクエリにも、update対象テーブルを使えるけど、移動対象のトップの left right が先に変更されてしまうと、以降の計算が狂うので、これは、先に前方後方取得時に一緒に求めて, :this_left, :this_right としてプレースホルダーで固定値にする
```
--  はめ込み位置 算出
$up_left  = ( $pre_left*2 + $post_right )/3.0;
$up_right = ( $pre_left + $post_right*2 )/3.0;
--  はめ込み比率
$ratio    = ($up_right - $up_left)/($this_right - $this_left) ;
--  update 文
update [nestset]
  set  left_pos =  :up_left + (  left_pos - :this_left ) * :ratio
    , right_pos =  :up_left + ( right_pos - :this_left ) * :ratio
where  left_pos between :this_left  and  :this_right 
;
```
ページの削除
※　ページ削除後も過去の履歴は残るので、[pageinfo]のレコードは消さずに、[nestset]のpageidに紐付くレコードを削除します。
※　[nestset]のpageidに紐付くpath情報を削除することで、サイトマップ表示には、そのページは表示されなくなります。
また、下位階層を持っていても、そのノードだけ削除すると、内部にあった下位層は、そのまま直接元の親の、削除ノード位置部分にはめ込まれた格好になるので、ツリー構造が崩れることはありません。
よって、プログラムコンセプトとして、下位層をどのように扱うかによって、以下の様に全削除トリガーをいれるか、１ノード削除で、ツリーのすげ替え状態はそのままとするかを決めることになるでしょう。
残したいノードは先に移動しておいたとして、下位も全削除となるトリガーを作成する場合
```
CREATE TRIGGER  [delete_descend]  AFTER  DELETE
 ON  [nestset]
 FOR EACH ROW
 BEGIN
   DELETE FROM [nestset] 
    WHERE [left_pos] between  OLD.[left_pos]  and  OLD.[right_pos] ;
 END ;
```
※　このtriggerを作っている場合で下位を残したい場合は、先に残したい下位ノードを別の親へ移してから削除を行う必要があります。

ノード左右値の検証と、データ間隔の整地

検証

上記の編集ＳＱＬが正しく動作しているか、または、手動で、数値を入れ込んだときに正しく入れ子になっているかを検証します。

root check


--  1 最大値　最小値　同じ id か、つまり root はひとつか
select 
 ( SELECT b.pageid FROM nestset b
    WHERE b.left_pos = ( select min(c.left_pos) from nestset c )
 ) minid
, ( SELECT b.pageid FROM nestset b
    WHERE b.right_pos = ( select max(c.right_pos) from nestset c )
 ) maxid  ;

-- 1b. root 検証その２  root つまり 親がいないノード は一つか
select pageid as root from [nestset] c
 where  not exists 
   ( select * from [nestset] p where c.left_pos > p.left_pos and c.right_pos < p.right_pos )
 ;

入れ子の検証


--  2. 入れ子の検証
SELECT parents.pageid as pid,  children.pageid as cid 
, case when parents.pageid is null then 'root' 
       when children.pageid is null then 'leaf'
       when children.right_pos < parents.right_pos then 'ok' 
       else 'bad node' end as validate
  FROM [nestset] parents  LEFT OUTER JOIN [nestset] children
   ON parents.left_pos =  (SELECT MAX(left_pos)  FROM [nestset] as ancestor
          WHERE children.left_pos > ancestor.left_pos  AND children.left_pos < ancestor.right_pos
      )
--  ※ SQLite は outer join = left outer なので、実際には root の検証はこっちではできない

重複値チェック
※　seq_viewは、union にて、leftとrightを１カラムにまとめたviewテーブルです。


--  3 重複値チェック
SELECT seq, count(*) as cnt , max(pageid) as maxpageid, min(pageid) as minpageid
from  [seq_view]
group by seq
order by seq
--  ※　左右併せて一つの position = seq_view.seq は１行のみに出現し、pageid が複数出てきたりしないことを検証

上記で、エラーデータ発見時に、どうするかは、プログラムコンセプトによる。そのままでは、以降の編集に支障をきたすので、削除または、異常値の変更が必要。

整地

float で 1/3 位置挿入を繰り返していると、循環小数が多く発生するし、２進数保持だと誤差も発生するので、ときどき、データ量を考慮しつつ、left , right の間隔を振り直すとよい。
データ変更の考え方は、同じ範囲で変更していると齟齬が発生することがあるので、まずは、全部を、現在範囲の外で等間隔に付け替える。
最初に、root を 0.0 - 1.0 としたので、とりあえず１以上で連番を振る。
その後、(連番値-1)/(連番最大値-1) をすべての値に適用すれば、最初の、0.0 - 1.0 の範囲に等間隔に収まる。


--  実行前に　最大値、　最小値、　件数　をチェック
SELECT max(right_pos) as max, min(left_pos) as min , count(pageid) cnt 
 FROM nestset ;

-- まずは、１以上の整数連番に変更
replace into [nestset] 
 select  pageid , min(ren) as left_pos , max(ren) as right_pos
 from 
 ( select s1.seq , s1.pageid ,  count(s2.seq) ren 
   from  [seq_view] as s1
     left join  [seq_view] as s2   on s1.seq >= s2.seq
   group by s1.seq, s1.pageid
 ) as temp
group by pageid
;

--  (連番値-1)/(連番最大値-1) を適用
--  件数 * 2 -1 = 連番最大値-1  を rmax に取得しておく
select  count(pageid) *2 -1 as  rmax 
 from [nestset]
 ;

update [nestset] set left_pos = (left_pos-1)/ :rmax
  , right_pos = (right_pos-1)/ :rmax
;

入れ子集合モデルでサイトマップ by SQLite

データベースファイル

テーブル構造

[pageinfo] : ページ名に紐付く情報テーブル

[nestset] : ツリー構造用

[history] : 更新履歴