入れ子集合モデルでサイトマップ by MySQL
入れ子集合モデルを利用したツリー型サイトマップ構築のために必要となるSQL文を概観してみます。 ここでは、MySQLでつくる場合。SQLiteの構文は前のページに
テーブル構造
3つのテーブルに分けて情報管理をします。
以下、MySQLの構文に沿って、識別子(テーブル名やカラム名)を`` でくくっています。`pageinfo` : ページ名に紐付く情報テーブル
※ pageid は他のテーブル でpageを特定するために使います。pageidをauto increment で数値にすると、pageidを見ただけでは、ページ名が判らず、手入力時や再編集の時に面倒なので、自分で区別をつけられる最小コード文字列を入れることにしました。CREATE TABLE `pageinfo`( `pageid` varchar(10) PRIMARY KEY NOT NULL ,`pagename` varchar(100) NOT NULL comment "ページ表題" ,`uri` varchar(255) comment "リンク表示用URI" ,`modify` date ,`file` varchar(255) comment "ページ更新日チェック用のfilepath" ,`memo` text comment "ページ説明" ) CHARACTER SET utf8 ENGINE=innodb ;
※ ページ名やメモに多バイト文字を使うので、文字コードも明示、更新にtransaction を使うなら innodb にする必要もある。`nestset` : ツリー構造用
「入れ子集合(nest set)」または、「入れ子区間」を利用して、左位置(小さい方)と右位置(大きい方)とで、階層の内外をわけて、内部階層を樹木状に分岐することで、ツリー構造を形成します。 カラム名は、単純にleft, right としてしまうと予約語とかぶり、常に識別子用のくくりが必要になるので、以下では、_pos を接尾辞としています。
※ mysql の場合, after INSERT で、insertしたばかりの行を削除することはできない(行ロックがかかっている)ので、 before INSERT や、before UPDATE で、実行前にチェックして、delete 文は実際はエラー終了して、不正データが挿入されるのを防ぐ。 エラー内容は、ちょっとあさってなメッセージになるが、そこはプログラム側で制御。CREATE TABLE `nestset`( `pageid` varchar(10) PRIMARY KEY NOT NULL /* `pageinfo`テーブル との関連付け用 */ ,`left_pos` double UNIQUE NOT NULL ,`right_pos` double UNIQUE NOT NULL ) ENGINE=innodb ; -- mysqlでは、check構文は無効なので、trigger で、左右値の大小を規定します。 -- insert したものが不正データなら、insert前にerror を発生させてストップ delimiter | CREATE TRIGGER `treeins_lr_chk` before INSERT on `nestset` FOR EACH ROW begin if NEW.left_pos >= NEW.right_pos or (exists (select * from `nestset` t where NEW.left_pos = t.right_pos) ) or (exists (select * from `nestset` t where NEW.right_pos = t.left_pos) ) then delete from `nestset` where pageid = NEW.pageid ; else set @dum = ''; end if; end ; | -- update 時も、update前に不良データなら、error を発生させてストップ CREATE TRIGGER `treeup_lr_chk` before UPDATE on `nestset` FOR EACH ROW begin if NEW.left_pos >= NEW.right_pos or (exists (select * from `nestset` t where NEW.left_pos = t.right_pos) ) or (exists (select * from `nestset` t where NEW.right_pos = t.left_pos) ) then delete from `nestset` where pageid = NEW.pageid ; else set @dum = ''; end if; end ; | delimiter ;
ただし、insert ignore で実行すると、トリガーエラーも無視されて、insert が実行されてしまうので、SQL文作成時には注意。
※ サイトマップ内での表示順は、order by left_pos asc でツリー構造になる。
表示順を変えたい時は、整数を使う場合、密に並んでいると兄弟分岐ページのleft_pos と right_posも軒並み変更が必要になりますが、とびとびにしておけば、間に挿入も可能。 であれば、最初から、double として、小数値表記で無限の区間(実際には、小数点以下13-15桁ほどあれば、十分だろう)を得られる。 SQLiteでは、カラム型に意味はないのでfloat としたが、MySQLでは、型に厳密なので、なるべく桁の多い小数値を表せれる用にdouble とする。2進数誤差を気にするなら、NUMERIC(20,15) などとします。 大小比較はするけど、ある固定値とぴったり同じかをみることは少ないし、自己結合なら、同じ行のデータは同じとなるはずなので、問題はないかとおもう。
※ SQLで木構造を扱う~入れ子区間モデルに区間値を実数で扱う方法が紹介されている
※ 「入れ子集合モデル(Nest Set)」の詳細については、 「SQLで木と階層構造のデータを扱う(1)―― 入れ子集合モデル」 を御参照下さい。`history` : 更新履歴
※ ページ更新日順に登録していれば、登録順のid は必要ないかもしれないけど、後日データを編集したりすることもあるので、行特定のためにidを付けます。CREATE TABLE `history`( `id` int auto_increment PRIMARY KEY NOT NULL /* 登録順保持 */ ,`pageid` varchar(10) /* `pageinfo`との関連づけ用 */ ,`modify` date ,`comment` text , index `newer_index` (`modify` DESC, `id` DESC) ) CHARACTER SET utf8 ENGINE=innodb ;
data sample
サンプルなので架空データとしています。`pageinfo`用データ
※ 日付データは、MySQLが解釈する日付形式 YYYY-MM-DD で入力します。INSERT INTO `pageinfo` VALUES ('tools','小道具箱','/','2012-08-23','/index.shtml','プログラム小道具') , ('phptools','php 小道具箱','/php/','2012-12-25','/php/index.php','phpプログラムリスト') , ('sitemap','サイトマップ','/php/samplemap.php','2012-12-05','/php/data/map.sqlite','ツリー型サイトマップ') , ('history','更新履歴','/php/samplehistory.php','2012-12-05','/php/data/map.sqlite','サイト更新履歴') , ('sqlmap','php sqliteでサイトマップ','/php/map/index.shtml','2012-12-25','/php/map/index.shtml','サイトマップの作り方') ;
※ 一度に複数行insert 可能なので、上記は、1SQL文で書いています。`nestset`用データ
5つくらいなら、適当に考えて数値をいれてもよいのだが、多くなると、プログラムで、位置判定させて、データを作っていく方がよい。INSERT INTO `nestset` VALUES ('tools', 0.0 , 1.0) , ('phptools', 0.1, 0.2) , ('sitemap' , 0.9, 0.99) , ('history' , 0.95, 0.96) , ('sqlmap' , 0.13, 0.14) ;
`history`用データ
INSERT INTO `history` VALUES (null,'tools','2012-08-23','サイト開設') , (null,'phptools','2012-09-05','php ページ設置') , (null,'sitemap','2012-12-05','サイトマップ設置') , (null,'history','2012-12-05','更新履歴設置') , (null,'sqlmap' ,'2012-12-25','php sqlite サイトマップ構築解説') , (null,'phptools','2012-12-25','php ページリスト更新') ;
データ一覧SQL文
サイトマップのツリー表示
※ 親階層数を、サブクエリで求めています。 入れ子区間の定義から、親の区間 parent.left_pos から parent.right_pos の間に、求める子ノード値 t.left_pos があるので、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 , TIMESTAMPDIFF(DAY, m.modify, CURDATE()) as pastdays from `nestset` as t inner join `pageinfo` as m on t.pageid = m.pageid order by t.left_pos ; -- 取得データ例 +----------+----------+--------+--------------------------+------------------------+------------+----------------------+----------+ | pageid | left_pos | plevel | name | uri | modify | comment | pastdays | +----------+----------+--------+--------------------------+------------------------+------------+----------------------+----------+ | tools | 0 | 0 | 小道具箱 | / | 2012-08-23 | プログラム小道具 | 975 | | phptools | 0.1 | 1 | php 小道具箱 | /php/ | 2012-12-25 | phpプログラムリスト | 851 | | sqlmap | 0.13 | 2 | php sqliteでサイトマップ | /php/map/index.shtml | 2012-12-25 | サイトマップの作り方 | 851 | | sitemap | 0.9 | 1 | サイトマップ | /php/samplemap.php | 2012-12-05 | ツリー型サイトマップ | 831 | | history | 0.95 | 2 | 更新履歴 | /php/samplehistory.php | 2012-12-05 | サイト更新履歴 | 831 | +----------+----------+--------+--------------------------+------------------------+------------+----------------------+----------+
t.left_pos between parent.left_pos and parent.right_pos この条件にマッチするものは親と自分ノードとなり、その個数-1 を親階層数としています。
pastdaysのところは、mysqlの日付関数を使って、サイトの更新日`pageinfo`.modify から何日たっているかを算出しています。この日数により、新着マークを出すのが目的です。// php でのulタグによるツリー構造出力 ソース <?php $stmt = /* 上記sql実行結果用リソースを$stmtに代入、PDO接続など省略 */ ; $rows = $stmt->fetchAll(PDO::FETCH_ASSOC ); // 全行、ハッシュ配列 で取得 $p = -1; // 初期値 = rootの親階層数0 -1 = -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タグを付けるかを決めます。
※ さらに親階層情報も同時に表示したい場合には、 `nestset`テーブルから、祖先から子までの pageid リストを 経路列挙のように取り出しておき、 さらに、`pageinfo`テーブルからも、pageid , pagename , uri を取り出して、pageid をキーとする配列に入れて、php側でpageidでひもづけて出力していきます。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
経路列挙のような親pageidのリストなら、これをサブクエリとして、元の`history`テーブルに連結しても、無駄はあまりない。逆に`pageinfo`側データは、別に取り出すことになるので、こちらには不要// `nestset`の自己結合で 「.」文字で連結した親pageidのリストを得る select t.pageid , GROUP_CONCAT( p.pageid ORDER BY p.left_pos SEPARATOR '.') as pagepath from `nestset` as t join `nestset` as p on t.left_pos between p.left_pos and p.right_pos group by t.pageid
あと、`pageinfo`テーブルからも、pageid , pagename , uri を取り出して、pageid をキーとする配列に入れておけば、上記のpagepath内各pageid部分にリンクタグ付きで置き換えが可能となる。select h.id as hid , h.pageid , h.modify as hmodify, h.comment as comment , t.pagepath from `history` as h left join ( select c.pageid , GROUP_CONCAT( p.pageid ORDER BY p.left_pos SEPARATOR '.') as pagepath 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 ; -- 取得データ例 +-----+----------+------------+---------------------------------+-----------------------+ | hid | pageid | hmodify | comment | pagepath | +-----+----------+------------+---------------------------------+-----------------------+ | 6 | phptools | 2012-12-25 | php ページリスト更新 | tools.phptools | | 5 | sqlmap | 2012-12-25 | php sqlite サイトマップ構築解説 | tools.phptools.sqlmap | | 4 | history | 2012-12-05 | 更新履歴設置 | tools.sitemap.history | | 3 | sitemap | 2012-12-05 | サイトマップ設置 | tools.sitemap | | 2 | phptools | 2012-09-05 | php ページ設置 | tools.phptools | | 1 | tools | 2012-08-23 | サイト開設 | tools | +-----+----------+------------+---------------------------------+-----------------------+ 6 rows in set (0.31 sec)
// pageid にひも付く、pagename,uri 取り出しSQL select pageid, pagename, uri from `pageinfo`
// php での`pageinfo`情報取り出し ソース <?php $stmt = /* `pageinfo`情報取り出しsql実行結果用リソース */ ; $pagehash = array(); while( $row = $stmt->fetch(PDO::FETCH_ASSOC ) ){ $pagehash[$row['pageid']] = $row; } ?>
// 更新履歴データ取り出しsql select h.id as hid, h.pageid as pageid, h.modify as hmodify, h.comment as comment , t.pagepath from `history` as h left join ( select c.pageid , group_concat( p.pageid order by p.left_pos separator '.') as pagepath 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 での更新履歴出力 ソース <?php $stmt = /* 更新履歴データ取り出し実行結果用リソース */ ; $rows = $stmt->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['pagepath']) ){ /* ツリーの経路が得られれば、リンク可能ページ */ $plist = explode('.', $row['pagepath'] ); $parent ='/'; $len = count($plist) -1; for( $j=0; $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`= ( select min(`left_pos`) from `nestset`) ;
- 自分の外側となる親がいないという条件で記述、こちらだと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 ) ;
- left が最小値である
あるpageidページ(例'sqlmap')までの祖先nodeの`pageinfo`情報全部取得
自己結合を使います。select p.left_pos, i.* from `nestset` as t join `nestset` as p on ( t.left_pos between p.left_pos and p.right_pos ) and t.pageid = 'sqlmap' left join `pageinfo` as i on p.pageid = i.pageid 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文
ページ情報の新規追加
※ 同階層の既存pageidより後方に終端ノードとなるページを追加する場合をまず考えてみましょう。
※ 各テーブルのinsert文は既に列挙されていますが、最小限のデータ入力とするために必要な項目を列挙しますと、- `pageinfo`の全カラムデータ , modifyについては、file のパスからファイルの更新日を取得する場合には新たな入力は不要。
- `history`.comment , modifyについては、`pageinfo`.`modify`と同じにするなら新たな入力は必要ないが、別な日付に設定したい時に必要。
- `nestset` については、親となるページのpageidと、どの兄弟の後に追加するのかの兄用pageid とがあれば、左右は算出可能。
よって、直接 `nestset` のカラムデータを指定する必要はない。
ノードの左右位置指定方法
子ノードの左右位置指定は、親ノード の left,right 内で 指定兄sibling の right より後方位置で、そのsiblingよりさらに後方の弟siblingのleft の前方位置 となる
親の最初の兄弟にするときは、sibling にも親のpageidを指定することにする
親parent 兄sibling、挿入対象this、後方nextsib の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,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になる。以下、まずは基礎データ取得用SQL文。- それぞれを得る select 文
-- 1 前方値. :sibling_pageid のright 取得 select "preleft" as pos_name , right_pos from `nestset` where pageid = :sibling_pageid ; -- :sibling_pageid = :parent_pageid のときは、parent.leftを抽出 select "preleft" as pos_name , 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 をいっぺんに取得
MySQL では、transaction 内で、select 文から得たデータをinsertやupdateに使うときは、 先に実行する select 文に for upadate をつけておきます。 これにより、該当テーブルに行ロックがかかります。-- 1. parent_pgaid と sibling_pageid とが異なるとき select "pre_left" as pos_name , right_pos from `nestset` where pageid = :sibling_pageid union all 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_name , left_pos from `nestset` where pageid = :parent_pageid union all select "post_right" , min(seq) from `seq_view` where seq > ( select left_pos from `nestset` where pageid = :parent_pageid ) ;
※ 以下に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($myinputs['pageid'] ,':pagename'=>$myinputs['pagename'] ,':uri'=>$myinputs['uri'] ,':modify'=>$pagemodify ,':file'=>$myinputs['filepath'] ,':memo'=>$myinputs['memo'] ); /* query 実行 省略 */ // 2. `nestset` テーブル : 初回は左右固定、初回以外はselectしてデータ作成の切り分け必要 if( /* `nestset` の行数チェック、0行の場合 */ ){ $data = array(':pageid'=>$myinputs['pageid'], ':left'=> 0.0 , ':right'=> 1.0 ); }else{ // 前方後方位置データ取得 /* mysql での注意点 2カ所に同じ名前のnamed holder を使うときは、接続時オプションでemulate modeとすること */ 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 = :siblingid union all select "post_right" , min(seq) from `seq_view` where seq > ( select right_pos from `nestset` where pageid = :siblingid ) for upadate SSS; }else{ $data = array( ':parentid'=>$myinputs['parentid'] ); $sql = <<<SSS select "pre_left" as pos_name , left_pos as position from `nestset` where pageid = :parentid union all select "post_right" , min(seq) from `seq_view` where seq > ( select left_pos from `nestset` where pageid = :parentid ) for upadate SSS; } // 計算元データ取得 $stmt = $pdo->prepare($sql); $stmt->execute($data); $result = $stmt->fetchAll(PDO::FETCH_ASSOC); foreach($result 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'] ); } } $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 もそのまま10進数表記で書き出してくれる */ $stmt->bindValue( ':right' , $data[':right'] , PDO::PARAM_INT ); $stmt->execute(); // 3. `history` テーブル $sql = <<<SSS INSERT 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として求められるので、この1/3位置に対象ノード群をはめ込む。
対象ノードの元位置も、先の前方後方位置取得時に一緒に求めて, :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に紐付く位置情報を削除することで、サイトマップ表示には、そのページは表示されなくなります。
また、下位階層を持っていても、そのノードだけ削除すると、内部にあった下位層は、そのまま直接元の親の、削除ノード位置部分にはめ込まれた格好になるので、ツリー構造が崩れることはありません。
よって、プログラムコンセプトとして、下位層をどのように扱うかによって、以下の様に全削除トリガーをいれるか、1ノード削除で、ツリーのすげ替え状態はそのままとするかを決めることになるでしょう。
残したいノードは先に移動しておいたとして、下位も全削除となるトリガーを作成する場合
※ このtriggerを作っている場合で下位を残したい場合は、先に残したい下位ノードを別の親へ移してから削除を行う必要があります。delimiter | 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 ; |
ノード左右値の検証と、データ間隔の整地
検証
上記の編集SQLが正しく動作しているか、または、手動で、数値を入れ込んだときに正しく入れ子になっているかを検証します。
※ seq_viewは、union にて、leftとrightを1カラムにまとめたviewテーブルです。- root check
-- 1a. 最大値と最小値は、同じ pageid に属するか、つまり root はひとつか。さらに、最小値はleft由来で、最大値はright由来か 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 , ( case when ( select min(left_pos)=( select min(seq) from `seq_view` ) from `nestset` ) then "minimum left is minimum" else "bad minimum " end ) mincheck , ( case when ( select max(right_pos)=( select max(seq) from `seq_view` ) from `nestset` ) then "maximum right is maximum" else "bad maximum " end ) maxcheck ; -- 1b. root 検証その2 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 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 ) ; -- ※ MySQL は outer join = left outer なので、実際には root の検証はこのSQLではできない -- 取得データ例 +------------+------------+----------+ | pid | cid | validate | +------------+------------+----------+ | sitemap | history | ok | | tools | phptools | ok | | tools | sitemap | ok | | phptools | sqlmap | ok | | history | NULL | leaf | | sqlmap | NULL | leaf | +------------+------------+----------+ 6 rows in set (0.00 sec) -- from句のparent , children の順を入れ替えれば、root 検証が可能になるが、その場合 leaf が出てこなくなる。
- 重複値チェック
-- 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 は1行のみに出現し、pageidが複数出てきたりしないことを検証
先に insertやupdate用のtrigger を作って、ignoreは使わずエラー無視しないようにしてデータ作成していれば、異常値が挿入されることはないはず。
前出の下位削除トリガーを設定せずに、rootノードを削除すると、複数root状態になる。 下位削除トリガーがある状態で、rootノードを削除すると、全削除になる。 なので、いずれにしても、rootノードは削除しないように注意。- root check
整地
floatやdouble で 1/3 位置挿入を繰り返していると、部分的にかなり近い数値になりすぎたりして、同値と見なされてしまっても困るので、ときどき、データ量を考慮しつつ、left , right の間隔を振り直すとよい。
データ変更の考え方は、同じ範囲で変更していると齟齬が発生することがあるので、まずは、全部を、現在範囲の外で等間隔に付け替える。
最初に、root を 0.0 - 1.0 としたので、とりあえず1以上で連番を振る。
その後、(連番値-1)/(連番最大値-1) をすべての値に適用すれば、最初の、0.0 - 1.0 の範囲に等間隔に収まる。
件数は先に求めておけば、連番最大値:rmax はわかるので、seq_viewを使って、変更テーブルを作り直せば、一回で左右値の振り直しができるはず? とおもったが、下位削除トリガーが設定されていると、replace文で(delete and insertなので)同じ行に作業しようとしたとしてエラーが発生する。 よって、temporary に作りなおしてから、書き戻すのがよいようだ。-- 件数 * 2 = 連番最大値 select count(pageid) *2 -1 as renmax from `nestset` ; -- :renmax は、 連番最大値 - 1 とする -- まずは、temporary 作成 create temporary table `temp_nest` ( `pageid` varchar(10) , `left_pos` double , `right_pos` double ) select pageid , (min(ren)-1)/:renmax as left_pos , (max(ren)-1)/:renmax as right_pos from ( select s1.seq , s1.pageid , count(s2.seq) as 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 ; -- 以下10件のデータふり直し状況 +------------+---------------------+---------------------+ | pageid | left_pos | right_pos | +------------+---------------------+---------------------+ | tools | 0 | 1 | | phptools | 0.05263157894736842 | 0.21052631578947367 | | sqlmap | 0.10526315789473684 | 0.15789473684210525 | | sql | 0.2631578947368421 | 0.7368421052631579 | | mysql_date | 0.3157894736842105 | 0.3684210526315789 | | sql_date | 0.42105263157894735 | 0.4736842105263158 | | sqlite_dat | 0.5263157894736842 | 0.5789473684210527 | | sqlite_cal | 0.631578947368421 | 0.6842105263157895 | | sitemap | 0.7894736842105263 | 0.9473684210526315 | | history | 0.8421052631578947 | 0.8947368421052632 | +------------+---------------------+---------------------+ 10 rows in set (0.00 sec) -- データ入れ替え、万一、元データと新しいデータ(別のpageid)のなかにかち合うデータがあると、 -- 先に設定したupdateトリガーでエラーが発生するので、truncate で全削除後に一括insert -- truncate は drop and create なので、下位削除トリガーは発動しない。 truncate `nestset` ; insert into `nestset` select pageid, left_pos , right_pos from `temp_nest` ;
[設置日 2015-04-25] : 初回設置 [最終更新日 ] - それぞれを得る select 文