Google App Engineでも柔軟に階層構造データを扱えるかもしれない-入れ子集合モデル

ここでいう階層構造とは木構造の事です。

Google App Engineで階層構造のデータを扱う場合

いろいろアプローチはあると思いますが、たとえば、

自己参照をつかって親のキーを保持する場合だと、
GAEはRDBMSのようなサブクエリや、OracleのCONNECT BYのような関数が使えない為、
親子関係を取得する場合に面倒くさい事になります。

他には、リストプロパティ等を使って祖先パスを保持する方法等もあるとおもいますが、
階層構造に変更が発生するようなデータを扱う場合は変更が面倒くさい事になります。

とはいえ、
そんなに頻繁にカテゴリの階層構造が変わるようなシステムはあまり無いと思いますので、
上記の方法でも問題ないわけですが、

もし頻繁に更新するような階層構造データを扱う場合はどうするか？

入れ子集合モデルが良くね？って思いつきです。

入れ子集合モデルについてご存知で無い方はこちらのページがわかりやすいです。
http://www.geocities.jp/mickindex/database/db_tree_ns.html

具体的に、

次の図のデータを使って話を進めます。

この図を入れ子集合モデルで表すと次のようになります。

カテゴリのモデルはこんな感じにしました。

public class Tree implements Serializable {
    public Tree() {
    }

    public Tree(String name, double left, double right) {
        key = Datastore.createKey(TreeMeta.get(), name);
        this.left = left;
        this.right = right;
        this.leftAndRight = new ArrayList<Double>();
        leftAndRight.add(left);
        leftAndRight.add(right);
    }
    @Attribute(primaryKey = true)
    private Key key;

    //左端
    private double left;
    //右端
    private double right;
    //左端と右端を両方入れておくリスト
    private List<Double> leftAndRight;
    
    他省略…
}

1.子孫カテゴリをまとめて取得する

「デスクトップ」の子孫カテゴリ、「一体型」と「単体」を取得してみます。

            List<Tree> trees =
                Datastore.query(m)
                    .filter(
                        m.leftAndRight.greaterThan(2d),
                        m.leftAndRight.lessThan(7d))
                    .asList();

2.祖先をパスを取得

「モバイル」の祖先カテゴリ、「パソコン」と「ノート」を取得してみます。

            // 祖先を全てゲット。
            List<Tree> trees =
                Datastore
                    .query(m)
                    .filter(m.left.lessThan(13d))
                    .filterInMemory(new InMemoryFilterCriterion() {
                        @Override
                        public boolean accept(Object model) {
                            Tree e = (Tree) model;
                            return e.getRight() > 14d;
                        }
                    })
                    .sort(m.left.asc)
                    .asList();

3.親カテゴリを追加する

「ノート」と「タブレット」の上に「ノート？」を追加してみます。

            Tree e = new Tree("ノート？", 7.5, 17.5);
            Datastore.put(e);

4.子を追加する

「タブレット」の下に「iPad」を追加してみます。

            Tree e = new Tree("iPad", 16.1, 16.2);
            Datastore.put(e);

5.カテゴリを入れ替える

「単体」と「大型」を入れ替えてみます。

            Tree e = new Tree("単体", 9, 10);
            Datastore.put(e);

            e = new Tree("大型", 5, 6);
            Datastore.put(e);

6.カテゴリを子孫毎入れ替える

「デスクトップ」を子孫毎、「普通」と入れ替えてみます。

            Tree e = new Tree("デスクトップ", 11, 12);
            Datastore.put(e);

            e = new Tree("普通", 2, 7);
            Datastore.put(e);

            e = new Tree("一体型", 3, 4);
            reNumber(2, 7, 11, 12, e);
            Datastore.put(e);

            e = new Tree("単体", 5, 6);
            reNumber(2, 7, 11, 12, e);
            Datastore.put(e);
    }

    // これでいいかな？
    private void reNumber(double fromLeft, double fromRight, double toLeft,
            double toRight, Tree tree) {

        double fromDist = fromLeft - fromRight;
        double toDist = toLeft - toRight;

        double left =
            (tree.getLeft() - fromLeft) * (toDist / fromDist) + toLeft;
        double right =
            (tree.getRight() - fromLeft) * (toDist / fromDist) + toLeft;
        tree.setLeft(left);
        tree.setRight(right);

    }

で、

GAEで階層構造データを扱う場合、入れ子集合モデルだと必ず上手くいくという事ではないです。
実際に扱うデータの利用方法等を考えて判断する必要がありますが、検討する価値はあると思います。