Mercurial > hg > Papers > 2014 > nobuyasu-master

annotate paper/chapter2.tex @ 72:97d4c219ae76

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fixed
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sun, 02 Feb 2014 07:33:12 +0900
parents 4e8bfd65768f
children ae161408bc1c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
50
faa708c2958b Added log
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
1 \chapter{木構造データベースJungle}
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
2 Jungle はスケーラビリティのあるCMSの開発を目指して当研究室で開発されている非破壊的木構造データベースである.
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
3 一般的なコンテンツマネジメントシステムではブログツールやWiki・SNSが多く, これらの
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
4 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
5 現在JavaとHaskellによりそれぞれ言語で開発されており本研究で扱うのはJava版である.
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
6
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
7 本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungleにおけるデータ分散の設計について述べる.
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
8 \subsection{破壊的木構造}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
9 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
10 図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している.
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
11
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
12 \begin{figure}[htpb]
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
13 \begin{center}
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
14 \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
15 \caption{破壊的木構造の編集}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
16 \label{fig:destractive}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
17 \end{center}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
18 \end{figure}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
19
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
20 破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
21 この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
22 いる場合は木の走査が終わるまで書き換えをまたなければならない.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
23 これではロックによりスケーラビリティが損なわれてしまう.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
24
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
25 \subsection{非破壊的木構造}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
26 非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
27 非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
28 行い新しく木構造を作成することで行われる.
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
29 図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している.
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
30
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
31 \begin{figure}[htpb]
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
32 \begin{center}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
33 \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
34 \caption{非破壊的木構造の編集}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
35 \label{fig:nondestractive}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
36 \end{center}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
37 \end{figure}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
38
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
39 非破壊的木構造におけるデータ編集の手順を以下に示す.
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
40
7
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
41 \begin{enumerate}
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
42 \item ルートから編集を行うノードまでのパスを調べる(図\ref{fig:nondestractive_edit1}).
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
43 \item 編集を行うノードのコピーをとる. コピーをとったノードへデータの編集を行う(図\ref{fig:nondestractive_edit2}).
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
44 \item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり繋げる(図\ref{fig:nondestractive_edit3}).
8
7072254f5e11 Modified some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
45 \item コピーしたルートノードは編集を行っていないノードへの参照を貼り新しい木構造を作る(図\ref{fig:nondestractive_edit4}).
7
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
46 \end{enumerate}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
47
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
48 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
49 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
50 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
51 \caption{非破壊的木構造の編集手順1}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
52 \label{fig:nondestractive_edit1}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
53 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
54 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
55
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
56 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
57 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
58 \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
59 \caption{非破壊的木構造の編集手順2}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
60 \label{fig:nondestractive_edit2}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
61 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
62 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
63
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
64 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
65 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
66 \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
67 \caption{非破壊的木構造の編集手順3}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
68 \label{fig:nondestractive_edit3}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
69 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
70 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
71
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
72 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
73 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
74 \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
75 \caption{非破壊的木構造の編集手順4}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
76 \label{fig:nondestractive_edit4}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
77 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
78 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
79
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
80 \newpage
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
81
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
82 非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終りえた後に
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
83 ルートノードを更新するときだけである.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
84 データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
85 可能である(図\ref{fig:nondestractive_merit}).
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
86 そのため, 破壊的木構造に比べスケールがしやすくなっている.
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
87
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
88 \begin{figure}[htpb]
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
89 \begin{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
90 \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
91 \caption{非破壊的木構造による利点}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
92 \label{fig:nondestractive_merit}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
93 \end{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
94 \end{figure}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
95
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
96 \newpage
9
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
97
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
98 \section{Jungle におけるデータへのアクセス}
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
99 Jungleにおいてのデータアクセス手段について述べる.
71
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
100 JungleではそれぞれのNodeがattributeを保持する.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
101 attributeはKey-Valueによりデータを保持される.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
102 KeyはString型でValueはByteBufferを使用している.
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
103 Jungleでデータへのアクセスは, このNodeへのアクセスをさす.
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
104 Node へのアクセスは, 木の名前と Node を指すパスにより行える.
71
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
105 このパスはNodePathと呼ばれる(図\ref{fig:nodepath}).
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
106
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
107 \begin{figure}[htpb]
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
108 \begin{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
109 \includegraphics[scale=0.7]{figures/nodepath.pdf}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
110 \caption{Node の attribute と NodePath}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
111 \label{fig:nodepath}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
112 \end{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
113 \end{figure}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
114
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
115
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
116
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
117 \section{Jungle におけるデータ編集}
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
118
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
119 \subsection{NodeOperation}
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
120 Jungle による最小のデータ編集は Node の編集を指す.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
121 Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
122 NodeOperation には次の4つの API が用意されている.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
123 \begin{itemize}
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
124 \item \verb|addNewChild(NodePath _path, int _pos)|\\
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
125 NodePath で指定された Node に子供となる Node を追加する API である.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
126 pos で指定された番号に子供として追加を行う.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
127 \item \verb|deleteChildAt(NodePath _path, int _pos)|\\
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
128 NodePath と pos により指定される Node を削除する API である.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
129 \item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|\\
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
130 Node に attribute を追加する API である.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
131 NodePath は attribute を追加する Node を指す.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
132 \item \verb|deleteAttribute(NodePath _path, String _key)|\\
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
133 \verb|_key| が示す attribute の削除を行う API である.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
134 NodePath は Node を示す.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
135 \end{itemize}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
136
47
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
137 NodeOperationはNodePathとセットで扱わなければならず, このセットを
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
138 TreeOperationという.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
139 TreeOperationが1つのデータ編集の単位になるが, これはあくまで最小のデータ編集の単位である.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
140 Jungle によるデータの編集はTreeOperationが複数集まった単位でcommitされていく.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
141 このTreeOperationの集まりをTreeOperationLogという.
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
142
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
143 \subsection{TreeOperationLog}
47
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
144 Jungle 内部ではTreeOperationは順次ログに積まれていき, 最終的に
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
145 commitされることで編集が完了する.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
146 この時, ログに積まれた複数のTreeOperationはTreeOperationLogとして扱われる.
48
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
147 TreeOperationLogの仕様を\ref{src:treeoperationlog}に示す.
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
148 \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
149 public interface TreeOperationLog extends Iterable<TreeOperation>
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
150 {
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
151 public TreeOperationLog add(NodePath _p,NodeOperation _op);
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
152 public TreeOperationLog append(TreeOperationLog _log);
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
153 public int length();
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
154 }
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
155 \end{lstlisting}
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
156 \verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
157 addやappendメソッドを使ってTreeOperationを積み上げていくことができる.
48
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
158
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
159 次にデータ編集により発生するTreeOperationLogの具体的な例を示す(\ref{src:treelog}).
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
160 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
161 [APPEND_CHILD:<-1>:pos:0]
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
162 [PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
163 [PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
164 [PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
165 \end{lstlisting}
71
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
166 このログはルートノードに対し子ノードを追加し, 追加した子ノードに attribute を3つ追加する際に図れるログである(図\ref{fig:treeoperationlog}).
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
167
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
168 大文字の英字は実行した NodeOperation の種類を表す.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
169 \verb|<>| により囲まれている数字は NodePath を示す.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
170 NodePath の表記以降は Node の position や attribute の情報を表している.
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 61
diff changeset
171
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 61
diff changeset
172 \newpage
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
173 \begin{figure}[htpb]
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
174 \begin{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
175 \includegraphics[scale=0.7]{figures/treeoperationlog1.pdf}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
176 \caption{TreeOperationLog の具体例}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
177 \label{fig:treeoperationlog}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
178 \end{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
179 \end{figure}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
180
71
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
181 ログの動作を表している図\ref{fig:treeoperationlog}の説明を行う.
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
182 まず, \verb|APPEND_CHILD:<-1>:pos:0|によりRoot Nodeの0番目の子供となるNodeの追加を行う.
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
183 次に, 追加を行ったNodeに対して\verb|PUT_ATTRIBUTE<-1,0>| により attribute の情報を持たせていく.
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
184 attributeの内容に作者の情報を表すauther, メッセージの内容を表すmes, そしてタイムスタンプ
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
185 をtimestampとそれぞれキーにすることで追加される.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
186
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
187 以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
188
61
c5c761588168 Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
189 \newpage