東方算程譚

Oriental Code Talk ── επιστημηが与太をこく、弾幕とは無縁のシロモノ。

目次

Blog 利用状況

ニュース

著作とお薦めの品々は

著作とお薦めの品々は
東方熱帯林へ。

あわせて読みたい

わんくま

  1. 東京勉強会#2
    C++/CLI カクテル・レシピ
  2. 東京勉強会#3
    template vs. generics
  3. 大阪勉強会#6
    C++むかしばなし
  4. 東京勉強会#7
    C++むかしばなし
  5. 東京勉強会#8
    STL/CLRによるGeneric Programming
  6. TechEd 2007 @YOKOHAMA
    C++・C++/CLI・C# 適材適所
  7. 東京勉強会#14
    Making of BOF
  8. 東京勉強会#15
    状態遷移
  9. 名古屋勉強会#2
    WinUnit - お気楽お手軽UnitTest

CodeZine

  1. Cで実現する「ぷちオブジェクト指向」
  2. CUnitによるテスト駆動開発
  3. SQLiteで組み込みDB体験（2007年版）
  4. C++/CLIによるCライブラリの.NET化
  5. C# 1.1からC# 3.0まで～言語仕様の進化
  6. BoostでC++0xのライブラリ「TR1」を先取りしよう (1)
  7. BoostでC++0xのライブラリ「TR1」を先取りしよう (2)
  8. BoostでC++0xのライブラリ「TR1」を先取りしよう (3)
  9. BoostでC++0xのライブラリ「TR1」を先取りしよう (4)
  10. BoostでC++0xのライブラリ「TR1」を先取りしよう (5)
  11. C/C++に対応した、もうひとつのUnitTestFramework ─ WinUnit
  12. SQLiteで"おこづかいちょう"
  13. STL/CLRツアーガイド
  14. マージ・ソート : 巨大データのソート法
  15. ヒープソートのアルゴリズム
  16. C++0xの新機能「ラムダ式」を次期Visual Studioでいち早く試す
  17. .NETでマンデルブロ集合を描く
  18. .NETでマンデルブロ集合を描く(後日談)
  19. C++/CLI : とある文字列の相互変換(コンバージョン)
  20. インテルTBBによる選択ソートの高速化
  21. インテルTBB3.0 によるパイプライン処理
  22. Visual C++ 2010に追加されたSTLアルゴリズム
  23. Visual C++ 2010に追加されたSTLコンテナ「forward_list」
  24. shared_ptrによるObserverパターンの実装
  25. .NETでマンデルブロ集合を描く(番外編) ── OpenCLで超並列コンピューティング
  26. StateパターンでCSVを読む
  27. 状態遷移表からStateパターンを自動生成する
  28. 「ソートも、サーチも、あるんだよ」～標準C++ライブラリにみるアルゴリズムの面白さ
  29. インテルTBBの同期メカニズム
  30. なぜsetを使っちゃいけないの?
  31. WPFアプリケーションで腕試し ～C++でもWPFアプリを
  32. C++11 : スレッド・ライブラリひとめぐり
  33. Google製のC++ Unit Test Framework「Google Test」を使ってみる
  34. メールでデータベースを更新するココロミ
  35. Visitorパターンで遊んでみたよ
  36. Collection 2題：「WPFにバインドできる辞書」と「重複を許す検索set」
  37. Visual C++ 2012：stateless-lambdaとSQLiteのぷち拡張
  38. 「Visual C++ Compiler November 2012 CTP」で追加された6つの新機能

@IT

  1. Vista時代のVisual C++の流儀（前編）Vista到来。既存C／C++資産の.NET化を始めよう！
  2. Vista時代のVisual C++の流儀（中編）MFCから.NETへの実践的移行計画
  3. Vista時代のVisual C++の流儀（後編） STL/CLRによるDocument／Viewアーキテクチャ
  4. C++開発者のための単体テスト入門 第1回 C++開発者の皆さん。テスト、ちゃんとしていますか？
  5. C++開発者のための単体テスト入門 第2回 C++アプリケーションの効率的なテスト手法（CppUnit編）
  6. C++開発者のための単体テスト入門 第3回 C++アプリケーションの効率的なテスト手法（NUnit編）

AWARDS


Microsoft MVP
for Visual Developer - Visual C++


Wankuma MVP
for いぢわる C++


Nyantora MVP
for こくまろ中国茶

Xbox

Links

記事カテゴリ

書庫

日記カテゴリ

Databaseおんちです

ええ、Databaseおんちです。
Databaseが必要なほどに大量のデータを扱うことが稀なもので。

で、ですね、今木構造のデータを扱っております。

ナミヘイ
 |
 +-- サザエ
 |    |
 |    +-- タラ
 |
 +-- カツオ
 |
 +-- ワカメ

みたいな。
木構造をテーブルに納めるときのスキーマってどんな形式になるんでしょか。

ID 親ID 名前     性別
1  NULL ナミヘイ　♂
2  1    サザエ   ♀
3  2    タラ     ♂
4  1    カツオ   ♂
5  1    ワカメ   ♀

てな感じ? それぞれに"親は誰か"を持つことで木を表現しよかと。
この場合兄弟間に順序が規定されないけどそれはまあいいとして。
んでもってこのとき、"ナミヘイ一族の男/女をそれぞれ列挙せよ"って
なったとき、どんなSQLになるんでしょか?
SQLイッパツじゃ無理で、ナミヘイの子、その子、そのまた子...って
検索にHitしなくなるまで繰り返すですか?

投稿日時 : 2008年2月29日 11:28

コメントを追加

# re: Databaseおんちです 2008/02/29 11:36 Ｒ・田中一郎

僕なら、２つテーブルを作りますね。

一つはID と名前と性別、もう一つは親子関係のみを格納するParentId ChildId だけーのテーブルっすね。

# re: Databaseおんちです 2008/02/29 11:43 επιστημη

ああ、うん、そりゃわかる。
わかるけどそれはこの際トリビアル。
僕がわかんないのは
「節を辿る/列挙するアルゴリズムのSQLによる表現」
です。

# re: Databaseおんちです 2008/02/29 11:43 Ｒ・田中一郎

ああっ、サザエさん一家は人工物じゃないから、サザエさんが複数出現することはないですね orz

>"ナミヘイ一族の男/女をそれぞれ列挙せよ"って
なったとき、どんなSQLになるんでしょか?

これは（ナミヘイ, 男）と指定すると、（カツオ・タラ）の順で結果を返したいってことでですか？

# re: Databaseおんちです 2008/02/29 11:53 επιστημη

順番は規定しませんし、
IDを指定すれば直接あるいは間接的にその子
(つまり子/孫/曾孫/玄孫...)を列挙してくれればえぇです。

僕の手続き型脳は再帰しろとささやくのですが、
SQLの宣言型脳を持ち合わせていないのでSQLで
どう書くのか見当もつかんのです。

# re: Databaseおんちです 2008/02/29 11:56 HaR

初めてコメントできそうな話題が出てきたのでコメントしてみます。( ^^)

私だったらテーブル構造はεπιστημηさんのと同じになりそうですが、取得する時に「自己結合」って方法を使います。
そうすると一つ上の親と子の関係が列挙されたデータセットを取ることができるので、後はループをまわして木構造を再生成する感じになるかなーと。

具体的には
SELECT 親.名前, 子.名前 FROM 一族 AS 親, 一族 AS 子 WHERE 親.ID = 子.親ID

問題は波平以下の子全てを列挙する場合はSQLを複数叩かないとダメってことでしょうか。(SELECTで変える各レコードは「一つ上の親しか知らない」ため(波平→タラ)の関係が出てこない。)

# re: Databaseおんちです 2008/02/29 11:56 levin

順はとりあえず置いておくとして。
　
>"ナミヘイ一族の男/女をそれぞれ列挙せよ"
がDB構築上の要件として既にある前提であれば、私なら「グループ（ここで言うところの"一族"）テーブル」を作る、もしくは家族テーブルに"一族"列を作ります。

# re: Databaseおんちです 2008/02/29 12:02 Ｒ・田中一郎

僕も、普通に再帰で解決しちゃいますね。

これのことかなぁ？
http://www.google.co.jp/search?hl=ja&q=%22%E5%86%8D%E5%B8%B0SQL%22+%E3%81%A8%E3%81%AF&lr=lang_ja

これは面白いお題をもろた。
早速、調べてみようっと。

# re: Databaseおんちです 2008/02/29 12:10 levin

ふむぅ。
再帰は技術としては素敵だと思いますが、私が"一族"で一発分類できるようにした理由は「実行速度」です。
データ量が膨大になればなるほど、where句に指定するような条件に当たる要素は列としてindexを張るなりの措置を予め取っておくのが安全かなぁ、という見解です。
　
でも再帰SQLも面白そう…♪

# re: Databaseおんちです 2008/02/29 12:15 はつね

もし一族って要件があるのならば、一族テーブルをつくるかなー。
triggerとかつかって親IDと子IDを同一一族IDで一族テーブルにINSERT/UPDATE/DELETEするようにして。

#
ところで「一族」ってナミヘイ一族といったらナミヘイの親は含まないでしたっけ？
そうだとしたら一族テーブルは一工夫いりそうだし、やっぱり再帰SQLかな。

# re: Databaseおんちです 2008/02/29 12:16 片桐

ツリー構造なら再帰が有効ですね
数万単位の親子レコードの再帰をやってますが、
SQLServerじゃきちんとインデックスしてやると速さは引けをとらないし。

オラクルはツリー構造検索に特化したインデックス（ビットマップインデックスだっけ？）をもっていたと思うのでそう神経質にならなくても良いはず……だよね？＞某ぱぱを償還しているつもりらしいｗ

# re: Databaseおんちです 2008/02/29 12:19 fufuhehume

http://www.geocities.jp/mickindex/database/idx_database.html
ここに「SQLで木と階層構造のデータを扱う」というページが2つあります。
どちらもかなり興味深い内容ですよ。

# re: Databaseおんちです 2008/02/29 12:28 えムナウ

基本データベースは最適化しましょう。

最適化されたデータベースは要素と関連から成り立っています。
そういう意味では最初のR・田中一郎が正解です。

# re: Databaseおんちです 2008/02/29 12:28 ghost_shell

ぼくもDatabaseおんちです。
SQLでは単純な操作以外書きたくありません。

とりあえず最初の意見（Rさん）のようにしますね。

＃画期的な方法なんて用意されているのか？

# re: Databaseおんちです 2008/02/29 12:31 えムナウ

最後のR・田中一郎も正解です。

# re: Databaseおんちです 2008/02/29 12:33 NyaRuRu

隣接リストモデルと LINQ の組み合わせならこんな感じで．
http://d.hatena.ne.jp/NyaRuRu/20080120/p1

# re: Databaseおんちです 2008/02/29 12:47 HaR

>http://www.geocities.jp/mickindex/database/idx_database.html
>ここに「SQLで木と階層構造のデータを扱う」というページが2つあります。
>どちらもかなり興味深い内容ですよ。

ミックさんのページですね。

入れ子集合モデルを使えば「ナミヘイ配下全部」とかが欲しい時でもSQL一回で取れますね。
再帰SQLもいいとは思ったんですが…OracleとSQL ServerなんかにDBMSが限定されてしまうのがちょっとアレかなーという気はしました。

# re: Databaseおんちです 2008/02/29 13:04 はつね

> オラクルはツリー構造検索に特化したインデックス（ビットマップインデックスだっけ？）
B-Treeインデックス（ちなみにBはバランスドね）？

ビットマップは男女(ISOでは違うけど)のように２値しか持たないようなときに有効かな。
http://www.int21.co.jp/pcdn/oracle/article/ind.html

# re: Databaseおんちです 2008/02/29 13:12 επιστημη

へー WITH RECURSIVE なんつーもんがあるですか。
僕のアタマん中はSQL92どまりなもんだから知るわけねー^^;

# re: Databaseおんちです 2008/02/29 13:18 Streetw☆

オラクルでは、階層問合せができます。LEVEL 疑似列も使えます～
＃空気読めてないですかね（汗

select ID, "名前", "性別", "親ID", level
from "サザエさんの登場人物"
start with "名前" = 'ナミヘイ'
connect by prior ID = "親ID"

結果～
1 ナミヘイ　M　null 1
2 サザエ　　F　1　　2
3 タラ　　　M　2　　3
4 カツオ　　M　1　　2
5 ワカメ　　F　1　　2

# re: Databaseおんちです 2008/02/29 13:37 επιστημη

後学のため訊いておこう。

WITH RECURSIVE とかゆー再帰問い合わせに対応する
LINQ表現ってあるんすか? > 知ってそぉなヒト(半ば名指し♪)

# re: Databaseおんちです 2008/02/29 13:55 NyaRuRu

> WITH RECURSIVE とかゆー再帰問い合わせに対応するLINQ表現ってあるんすか? > 知ってそぉなヒト(半ば名指し?)

SQL は素人なので WITH RECURSIVE についてはよくわからないのですが，恐らく Standard Operators としては無いっす．
うちの Achiral にしても，Linq to Object での tree サポートをかなり自作しています．

Linq to XML あたりには，Descendants() なんかがありますな．

var tree = new XElement("L1",
new XElement("L2",
new XElement("L3"),
new XElement("L3"),
new XElement("L3")
)
);

foreach (var item in root.Descendants())
{
Console.WriteLine(item);
}

# re: Databaseおんちです 2008/02/29 13:59 NyaRuRu

あー下のコード，正しくはこうですね．

foreach (var item in tree.Descendants())
{
Console.WriteLine(item);
}

# re: Databaseおんちです 2008/02/29 14:04 NyaRuRu

たびたびすみません。
引数なしの Descendants だと、直下の子しか返さないですね。

XName でワイルドカードっぽいことできるのかなぁ？

# re: Databaseおんちです 2008/02/29 14:13 NyaRuRu

やっぱり気のせいでした。
Descendants で再帰的に子要素をたどってくれますね。
Console.WriteLine(item.Name); とかにしておけば混乱しなくてよかったかも。

というわけで、XElement に変換すれば tree サポートはそこそこあります < LINQ

# re: Databaseおんちです 2008/02/29 16:45 えムナウ

SQLサーバーなら、再帰 CTE ですね。
http://msdn2.microsoft.com/ja-jp/library/ms175972.aspx

# re: Databaseおんちです 2008/03/03 10:58 trapemiya

えムナウさんに続きまして。

さ・い・き♪
http://blogs.wankuma.com/kaya/archive/2006/10/27/42656.aspx

タイトル
名前
URL
コメント