\section{非破壊的木構造データベースJungle}
Jungleは等研究室が開発を行っているデータベースで、Javaを用いて実装されている。

Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
ノードは自身の子のListと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
Jungleでは、親から子への片方向の参照しか持たない。


Jungleは、データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{nonDestractTreeEdit})。
その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{nonDestractTreeEdit}の例ではノードB D Eは編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。
これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安全に読み出せるという特徴がある。
しかし、書き込み時の手間は大きくなる。



\begin{figure}[h]
\begin{center}
\includegraphics[height = 2.5cm , bb=0 0 511 188]{images/nonDestractTreeEdit.pdf}
\caption{非破壊的木構造の木の編集}
\label{nonDestractTreeEdit}
\end{center}
\end{figure}

\newpage
通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能であり、実際、そのような機能が実装されている。この木をそのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、
十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。

Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの
部分について考察する。

\subsection{木の生成}
初めにJungleにおける木の生成について述べる。
Jungleは複数の木を一意な名前を利用して管理しており、名前を利用することで作成、編集、削除を行う。
以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。
\begin{table}[htb]
\begin{center}
\caption{Jungleに実装されているAPI}
\begin{tabular}{|l|l|}        \hline
{\tt JungleTree createNewTree(String treeName) }    &
Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
{\tt
JungleTree getTreeByName(String treeName)} & 
 JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す       \\ \hline
\end{tabular}
\label{jungleAPI}
\end{center}
\end{table}

\newpage
\subsection{TreeNode}
Jungleが保持している木は、複数のノードの集合で出来ている。
ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。

\begin{table}[htb]
\begin{center}
\caption{TreeNodeに実装されているAPI}
\begin{tabular}{|l|l|}                                  \hline
Children                &ノードの子供を扱う      \\
getChildren()           &Childrenオブジェクトを返す。              \\ \hline
Attribute               &ノードが保持しているデータを  \\
getAttribute()          &扱うAttribteオブジェクトを返す。    \\ \hline
\end{tabular}
\label{TreeNodeAPI}
\end{center}
\end{table}

Childrenクラスは表\ref{Children}に記述されたAPIを、Attributeクラスは表\ref{Attribute}に記述されたAPIを提供する。
これらを利用しノードの子供や、保持する値にアクセスする。
\begin{table}[htbH]
\begin{center}
\caption{Childrenに実装されているAPI}
\begin{tabular}{|l|l|}                                  \hline
int size()                                 &子供の数を返す。           \\ \hline
Either                                     &ノードが持つ子供の中から、 \\
\textless Error,TreeNode\textgreater       &変数numで指定された        \\
at(int num)                                &位置にある子どもを返す。   \\ \hline
\end{tabular}
\label{Children}
\end{center}
\end{table}


関数{\tt children.at(int num)}が返すEither\textless Error,TreeNode\textgreater オブジェクトは、{\tt isA() }でErrorかどうかをチェックすることができる。
Errorでない場合は{\tt b()}でTreeNodeオブジェクトを取り出すことができる。


\begin{table}[htbH]
\begin{center}
\caption{Attributeに実装されているAPI}
\begin{tabular}{|l|l|}                                  \hline
ByteBuffer                   &ノードが持つ値から、     \\
get(String key)              &属性名 keyとペアの属性値       \\
                             &をByteBuffer型で返す。 \\ \hline
String                       &ノードが持つ値から、\\
getString(String key)        &属性名 key とペアの属性値 \\
                             &をString型で返す。 \\ \hline
\end{tabular}
\label{Attribute}
\end{center}
\end{table}

 \newpage
以下にルートノードの2番目の子供から、属性名 nameとペアになっている属性値を取得するサンプルコードを記述する。
\begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
JungleTree tree = jungle.getTreeByName("TreeName");
TreeNode root = tree.getRootNode();
Children children = root.getChildren();
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    throw new IllegalStateException();
TreeNode child = either.b();
Attribute attribute = child.getAttribute();
String value = attribute.getString("name");
\end{lstlisting}

\begin{enumerate}
\item Jungleから名前を指定して木を取得する。 
\item 取得した木のルートノードを取得する。
\item 木のルートノードからChildren型の子ノードを取得する。
\item 変数{\tt children}から2番目の子供を取得する。
\item 2番目の子供が取得できたかを調べる。
\item 取得できていなかった場合{\tt Exception}を投げる。
\item 取得に成功していた場合、eitherから子ノードを受け取る。
\item 取得した子ノードからAttributeを取得する。
\item 取得したAttributeから属性名 nameがペアの値を取得する。
\end{enumerate}


\subsection{NodePath}
Jungleでは、木のノードの位置をNodePathクラスを使って表す。
NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。また、ルートノードは例外として-1と表記される。
NodePathクラスが\textless -1,1,2,3\textgreater を表している際の例を図\ref{NodePath}に記す。
\begin{figure}[h]
\begin{center}
\includegraphics[height = 6cm , bb=0 0 568 455]{images/nodePath.pdf}
\caption{NodePath}
\label{NodePath}
\end{center}
\end{figure}



\newpage

\subsection{木の編集API}
Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。
JungleTreeEditorクラスには編集を行うために、表\ref{editor}で定義されているAPIが実装されている。

\begin{table*}[htb]
\begin{center}
\caption{Editorに実装されているAPI}
\begin{tabular}{|l|l|}        \hline
Either                                       &変数pathで指定した場所 \\
\textless Error,JungleTreeEditor\textgreater &にある、ノードの子供の \\
addNewChildAt(                               &変数posで指定した位置に\\ 
NodePath path,                               &子ノードを追加する。   \\ 
int pos)                                     &                       \\ \hline
Either                                       &変数pathで指定した場所 \\
\textless Error,JungleTreeEditor\textgreater &にある、ノードの子供の   \\ 
deleteChildAt(                               &変数posで指定した位置の\\ 
NodePath path,                               &子ノードを削除する。   \\
int pos)                                     &                       \\ \hline
Either                                       &変数pathで指定した場所 \\
\textless Error,JungleTreeEditor\textgreater &にあるノードに、       \\
putAttribute(                                &属性名 変数key         \\
NodePath path,                               &属性値 変数valu        \\ 
String key,                                  &のペアで値を挿入する。 \\
ByteBuffer value)                            &                       \\ \hline 
Either                                       &変数pathで指定した場所 \\
\textless Error,JungleTreeEditor\textgreater &にあるノードが持つ、   \\
deleteAttribute(                             &属性名 変数keyとペアで \\ 
NodePath path,                               &保存されているデータを \\
String key)                                  &削除する。             \\ \hline
Either                                       &変数pathで指定した場所 \\
\textless Error,JungleTreeEditor\textgreater &にある、ノードの変数num\\
moveChild(                                   &で指定された位置の子供を\\
NodePath path                                &変数moveの方向に\\
,int num,                                    &移動させる。            \\
String move)                                 &                        \\ \hline  
Either                                       &ルートノードの上に新しい\\
\textless Error,JungleTreeEditor\textgreater &ルートノードを追加する\\
pushPop()                                    &線形のTree等を作る際に\\
                                             &使用することで計算量を\\
                                             &O(n)からO(1)にできる。\\ \hline
\end{tabular}
\label{editor}
\end{center}
\end{table*}


編集後に返されるJungleTreeEditorクラスは、編集後の木構造を保持しているため、編集前の木構造を保持しているJungleTreeEditorクラスとは別のオブジェクトである。
編集を行った後は、関数editor.success()で今までの編集をコミットすることができる。他のJungleTreeEditorクラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
その場合は、木の編集を最初からやり直す必要がある。

以下にJungleTreeEditorクラスを用いて、木の編集を行うサンプルコードを記述する。

\begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
JungleTreeEditor editor = tree.getTreeEditor();
DefaultNodePath editNodePath = new DefaultNodePath();
Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
if (either.isA()) 
  throw new IllegalStateException();
editor = either.b();
editor.success();
\end{lstlisting}

\begin{enumerate}
\item 関数tree.getEditor()で編集を行う木から、JungleTreeEditorクラスを取得する。 
\item 次に変更するノードの場所を示す、NodePathクラスを作成する。
\item 関数editor.addNewChildAt()を用いて、変数pathで指定したノードの子供の0番目に子ノードを追加する。
\item 返り値の変数EitherがErrorクラスを保持していないか(編集に失敗していないか)を確認する。
\item Errorクラスを保持していた場合Exceptionを投げる。
\item 編集に成功していた場合、編集後のJungleTreeEditorクラスを取得する。
\item 取得したJungleTreeEditorクラスを用いて木の変更をコミットする。
\end{enumerate}

これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。