|
24
|
1 \section{非破壊的木構造データベースJungle}
|
|
|
2 Jungleは等研究室が開発を行っているデータベースで、Javaを用いて実装されている。
|
|
15
|
3
|
|
1
|
4 Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。
|
|
24
|
5 ノードは自身の子のListと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
|
|
|
6 通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
|
|
|
7 また、ノード同士はListを用いた参照で木構造を構築しているため、親から子への片方向の参照しか持たない。
|
|
15
|
8
|
|
|
9
|
|
24
|
10 Jungleは、データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{nonDestractTreeEdit})。
|
|
31
|
11 その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{nonDestractTreeEdit}の例ではノードB D Eは編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。
|
|
24
|
12 これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安定して読み出せるという特徴がある。
|
|
|
13 しかし、書き込み時の手間は大きくなる。
|
|
|
14
|
|
29
|
15
|
|
|
16
|
|
24
|
17 \begin{figure}[h]
|
|
|
18 \begin{center}
|
|
|
19 \includegraphics[height = 2.5cm , bb=0 0 511 188]{images/nonDestractTreeEdit.pdf}
|
|
|
20 \caption{非破壊的木構造の木の編集}
|
|
|
21 \label{nonDestractTreeEdit}
|
|
|
22 \end{center}
|
|
|
23 \end{figure}
|
|
|
24
|
|
31
|
25 \newpage
|
|
|
26 通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能であり、実際、そのような機能が実装されている。この木をそのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
|
|
24
|
27 %特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
|
|
31
|
28 特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となる。つまり、アプリケーションに合わせて木を設計しない限り、
|
|
24
|
29 十分な性能を出すことはできない。逆に言えば、正しい木の設計を行えば高速な処理が可能である。
|
|
|
30
|
|
|
31 Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
|
|
|
32 Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
|
|
|
33 持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの
|
|
|
34 部分について考察する。
|
|
|
35
|
|
3
|
36 \subsection{木の生成}
|
|
24
|
37 初めにJungleにおける木の生成について述べる。
|
|
|
38 Jungleは複数の木を一意な名前を利用して管理しており、名前を利用することで作成、編集、削除を行う。
|
|
|
39 以下にJungleが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。
|
|
3
|
40 \begin{table}[htb]
|
|
|
41 \begin{center}
|
|
|
42 \caption{Jungleに実装されているAPI}
|
|
|
43 \begin{tabular}{|l|l|} \hline
|
|
21
|
44 JungleTree &Jungleに新しく木を生成する \\
|
|
|
45 createNewTree( &木の名前が重複した場合 \\
|
|
|
46 String treeName) &生成に失敗しnullを返す。 \\ \hline
|
|
|
47 JungleTree &JungleからtreeNameと名前が \\
|
|
|
48 getTreeByName( &一致するtreeを取得する。 \\
|
|
|
49 String treeName) &名前が一致するTreeがない場合 \\
|
|
|
50 &取得は失敗しnullを返す \\ \hline
|
|
3
|
51 \end{tabular}
|
|
|
52 \label{jungleAPI}
|
|
|
53 \end{center}
|
|
|
54 \end{table}
|
|
|
55
|
|
31
|
56 \newpage
|
|
24
|
57 \subsection{TreeNode}
|
|
31
|
58 Jungleが保持している木は、複数のノードの集合で出来ている。
|
|
|
59 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
|
|
|
60 ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。
|
|
24
|
61
|
|
|
62 \begin{table}[htb]
|
|
|
63 \begin{center}
|
|
|
64 \caption{TreeNodeに実装されているAPI}
|
|
|
65 \begin{tabular}{|l|l|} \hline
|
|
|
66 Children &ノードの子供を扱う \\
|
|
|
67 getChildren() &Childrenクラスを返す。 \\ \hline
|
|
|
68 Attribute &ノードが保持しているデータを \\
|
|
|
69 getAttribute() &扱うAttribteクラスを返す。 \\ \hline
|
|
|
70 \end{tabular}
|
|
|
71 \label{TreeNodeAPI}
|
|
|
72 \end{center}
|
|
|
73 \end{table}
|
|
|
74
|
|
|
75 Childrenクラスは表\ref{Children}に記述されたAPIを、Attributeクラスは表\ref{Attribute}に記述されたAPIを提供する。
|
|
|
76 これらを利用しノードの子供や、保持する値にアクセスする。
|
|
|
77 \begin{table}[htbH]
|
|
|
78 \begin{center}
|
|
|
79 \caption{Childrenに実装されているAPI}
|
|
|
80 \begin{tabular}{|l|l|} \hline
|
|
|
81 int size() &子供の数を返す。 \\ \hline
|
|
|
82 Either &ノードが持つ子供の中から、 \\
|
|
|
83 \textless Error,TreeNode\textgreater &変数numで指定された \\
|
|
|
84 at(int num) &位置にある子どもを返す。 \\ \hline
|
|
|
85 \end{tabular}
|
|
|
86 \label{Children}
|
|
|
87 \end{center}
|
|
|
88 \end{table}
|
|
|
89
|
|
|
90
|
|
|
91 関数children.at(int num)が返すEither\textless Error,TreeNode\textgreater クラスは、変数numで指定した場所に子ノードがあればTreeNodeクラスを、無かった場合はErrorクラスを持つ型である。
|
|
|
92
|
|
|
93
|
|
|
94
|
|
|
95 \begin{table}[htbH]
|
|
|
96 \begin{center}
|
|
|
97 \caption{Attributeに実装されているAPI}
|
|
|
98 \begin{tabular}{|l|l|} \hline
|
|
|
99 ByteBuffer &ノードが持つ値から、 \\
|
|
|
100 get(String key) &属性名 keyとペアの属性値 \\
|
|
|
101 &をByteBuffer型で返す。 \\ \hline
|
|
|
102 String &ノードが持つ値から、\\
|
|
|
103 getString(String key) &属性名 key とペアの属性値 \\
|
|
|
104 &をString型で返す。 \\ \hline
|
|
|
105 \end{tabular}
|
|
|
106 \label{Attribute}
|
|
|
107 \end{center}
|
|
|
108 \end{table}
|
|
|
109
|
|
31
|
110 \newpage
|
|
24
|
111 以下にルートノードの2番目の子供から、属性名 nameとペアになっている属性値を取得するサンプルコードを記述する。
|
|
|
112 \begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
|
|
|
113 JungleTree tree = jungle.getTreeByName("TreeName");
|
|
|
114 TreeNode root = tree.getRootNode();
|
|
|
115 Children children = root.getChildren();
|
|
|
116 Either<Error,TreeNode> either = children.at(2);
|
|
|
117 if (either.isA())
|
|
|
118 throw new IllegalStateException();
|
|
|
119 TreeNode child = either.b();
|
|
|
120 Attribute attribute = child.getAttribute();
|
|
|
121 String value = attribute.getString("name");
|
|
|
122 \end{lstlisting}
|
|
|
123
|
|
|
124 \begin{enumerate}
|
|
|
125 \item Jungleから名前を指定して木を取得する。
|
|
|
126 \item (1)で取得した木のルートノードを取得する。
|
|
|
127 \item (2)で取得したルートノードからChildren型の子ノードを取得する。
|
|
|
128 \item (3)で取得した変数childrenから2番目の子供を取得する。
|
|
|
129 \item 2番目の子供が取得できたかを調べる。
|
|
|
130 \item 取得できていなかった場合Exceptionを投げる。
|
|
|
131 \item 取得に成功していた場合、eitherから子ノードを受け取る。
|
|
|
132 \item (7)で取得した子ノードからAttributeを取得する。
|
|
|
133 \item (8)で取得したAttributeから属性名 nameがペアの値を取得する。
|
|
|
134 \end{enumerate}
|
|
|
135
|
|
|
136
|
|
8
|
137 \subsection{NodePath}
|
|
31
|
138 Jungleでは、木のノードの位置をNodePathクラスを使って表す。
|
|
24
|
139 NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。また、ルートノードは例外として-1と表記される。
|
|
|
140 NodePathクラスが\textless -1,1,2,3\textgreater を表している際の例を図\ref{NodePath}に記す。
|
|
8
|
141 \begin{figure}[h]
|
|
|
142 \begin{center}
|
|
29
|
143 \includegraphics[height = 6cm , bb=0 0 568 455]{images/nodePath.pdf}
|
|
8
|
144 \caption{NodePath}
|
|
21
|
145 \label{NodePath}
|
|
8
|
146 \end{center}
|
|
|
147 \end{figure}
|
|
2
|
148
|
|
24
|
149
|
|
|
150
|
|
|
151 \newpage
|
|
|
152
|
|
|
153 \subsection{木の編集API}
|
|
|
154 Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。
|
|
|
155 JungleTreeEditorクラスには編集を行うために、表\ref{editor}で定義されているAPIが実装されている。
|
|
2
|
156
|
|
|
157 \begin{table}[htb]
|
|
|
158 \begin{center}
|
|
|
159 \caption{Editorに実装されているAPI}
|
|
|
160 \begin{tabular}{|l|l|} \hline
|
|
24
|
161 Either &変数pathで指定した場所 \\
|
|
|
162 \textless Error,JungleTreeEditor\textgreater &にある、ノードの子供の \\
|
|
|
163 addNewChildAt( &変数posで指定した位置に\\
|
|
|
164 NodePath path, &子ノードを追加する。 \\
|
|
|
165 int pos) & \\ \hline
|
|
|
166 Either &変数pathで指定した場所 \\
|
|
|
167 \textless Error,JungleTreeEditor\textgreater &にある、ノードの子供の \\
|
|
|
168 deleteChildAt( &変数posで指定した位置の\\
|
|
|
169 NodePath path, &子ノードを削除する。 \\
|
|
|
170 int pos) & \\ \hline
|
|
|
171 Either &変数pathで指定した場所 \\
|
|
|
172 \textless Error,JungleTreeEditor\textgreater &にあるノードに、 \\
|
|
|
173 putAttribute( &属性名 変数key \\
|
|
|
174 NodePath path, &属性値 変数valu \\
|
|
|
175 String key, &のペアで値を挿入する。 \\
|
|
|
176 ByteBuffer value) & \\ \hline
|
|
|
177 Either &変数pathで指定した場所 \\
|
|
|
178 \textless Error,JungleTreeEditor\textgreater &にあるノードが持つ、 \\
|
|
|
179 deleteAttribute( &属性名 変数keyとペアで \\
|
|
|
180 NodePath path, &保存されているデータを \\
|
|
|
181 String key) &削除する。 \\ \hline
|
|
|
182 Either &変数pathで指定した場所 \\
|
|
|
183 \textless Error,JungleTreeEditor\textgreater &にある、ノードの変数num\\
|
|
|
184 moveChild( &で指定された位置の子供を\\
|
|
|
185 NodePath path &変数moveの方向に\\
|
|
|
186 ,int num, &移動させる。 \\
|
|
|
187 String move) & \\ \hline
|
|
|
188 Either &ルートノードの上に新しい\\
|
|
|
189 \textless Error,JungleTreeEditor\textgreater &ルートノードを追加する\\
|
|
|
190 pushPop() &線形のTree等を作る際に\\
|
|
|
191 &使用することで計算量を\\
|
|
|
192 &O(n)からO(1)にできる。\\ \hline
|
|
2
|
193 \end{tabular}
|
|
|
194 \label{editor}
|
|
|
195 \end{center}
|
|
|
196 \end{table}
|
|
|
197
|
|
|
198
|
|
31
|
199 編集後に返されるJungleTreeEditorクラスは、編集後の木構造を保持しているため、編集前の木構造を保持しているJungleTreeEditorクラスとは別のオブジェクトである。
|
|
24
|
200 編集を行った後は、関数editor.success()で今までの編集をコミットすることができる。その際他のJungleTreeEditorクラスによって木が更新されていた場合はコミットに失敗する。
|
|
3
|
201 その場合は最初からやり直す必要がある。
|
|
|
202
|
|
31
|
203 以下にJungleTreeEditorクラスを用いて、木の編集を行うサンプルコードを記述する。
|
|
2
|
204
|
|
|
205 \begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
|
|
|
206 JungleTreeEditor editor = tree.getTreeEditor();
|
|
21
|
207 DefaultNodePath editNodePath = new DefaultNodePath();
|
|
|
208 Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
|
|
|
209 if (either.isA())
|
|
2
|
210 throw new IllegalStateException();
|
|
|
211 editor = either.b();
|
|
|
212 editor.success();
|
|
|
213 \end{lstlisting}
|
|
|
214
|
|
|
215 \begin{enumerate}
|
|
31
|
216 \item 関数tree.getEditor()で編集を行う木から、JungleTreeEditorクラスを取得する。
|
|
|
217 \item 次に変更するノードの場所を示す、NodePathクラスを作成する。
|
|
|
218 \item 関数editor.addNewChildAt()を用いて、変数pathで指定したノードの子供の0番目に子ノードを追加する。
|
|
24
|
219 \item 返り値の変数EitherがErrorクラスを保持していないか(編集に失敗していないか)を確認する。
|
|
|
220 \item Errorクラスを保持していた場合Exceptionを投げる。
|
|
|
221 \item 編集に成功していた場合、編集後のJungleTreeEditorクラスを取得する。
|
|
|
222 \item (6)で取得したJungleTreeEditorクラスを用いて木の変更をコミットする。
|
|
2
|
223 \end{enumerate}
|
|
3
|
224
|
|
31
|
225 これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。
|
