Mercurial > hg > Papers > 2017 > tatsuki-master

--- a/abstract_eng.tex	Fri Feb 10 16:01:17 2017 +0900
+++ b/abstract_eng.tex	Sat Feb 11 01:11:59 2017 +0900
@@ -1,4 +1,5 @@
-\begin{abstract_eng}
+\chapter*{Abstract}
+
 Relational DataBase(RDB) has problem of impedance mismatch.
 Exist an OR Mapper that can use database records as objects in program.
 and DB has been expand such as table specialization KVS and Json correspondence.
@@ -24,4 +25,3 @@
 benchmark was confirm the speedup of the tree editing function.
 And Jungle able to read data faster than PostgreSQL and MongDB.

-\end{abstract_eng}
--- a/chapter1.tex	Fri Feb 10 16:01:17 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,372 +0,0 @@
-\chapter{木構造データベースJungle}
-Jungleは、当研究室が開発を行っているデータベースで、Javaを用いて実装されている。
-Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
-ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
-通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
-Jungleでは、親から子への片方向の参照しか持たない。
-
-通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。
-この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
-%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
-特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、
-十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。
-
-Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
-Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
-持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では基本的に分散実装部分ではなく on memory DBの
-部分について考察する。
-本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。
-
-\section{破壊的木構造}
-破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。
-図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している。
-
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
-    \caption{破壊的木構造の編集}
-    \label{fig:destractive}
-  \end{center}
-\end{figure}
-
-破壊的木構造は、編集を行う際に木のロックを掛ける必要がある。
-この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、
-閲覧者がいる場合は木の走査が終わるまで書き換えを待たなければならない。
-
-\section{非破壊的木構造}
-データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。
-その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。
-
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
-    \caption{非破壊的木構造の編集}
-    \label{fig:nondestractive}
-  \end{center}
-\end{figure}
-
-非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に
-ルートノードを更新するときだけである。
-データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、
-書き込み時の手間は大きくなる。
-
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
-    \caption{非破壊的木構造による利点}
-    \label{fig:nondestractive_merit}
-  \end{center}
-\end{figure}
-
-\section{NodePath}
-Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。
-{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。
-{\tt NodePath}クラスを用いて{\tt< -1,1,2,3>}を表している際の例を図\ref{NodePath}に記す。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.7]{figures/nodePath.pdf}
-\caption{NodePath}
-\label{NodePath}
-\end{center}
-\end{figure}
-
-\section{Either}
-Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。
-AにはのError、Bには処理に成功した際の返り値の型が入る。
-Eitherは、AかBどちらかの値しか持たない。
-以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。
-\begin{table}[htb]
-\begin{center}
-\caption{Eitherに実装されているAPI}
-\begin{tabular}{|p{15em}|p{24em}|}        \hline
-{\tt boolean isA()} & EitherがAを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
-{\tt boolean isB()} & EitherがBを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
-{\tt A a()} & Aの値を取得する。\\ \hline
-{\tt B b()} & Bの値を取得する。\\ \hline
-\end{tabular}
-\label{EitherAPI}
-\end{center}
-\end{table}
-
-{\tt Either<A、B>}は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。
-{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。
-
-
-\section{木の生成}
-初めにJungleにおける木の生成について述べる。
-Jungleは複数の木構造を、名前を利用して作成・編集・削除を行い管理している。
-以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。
-
-\begin{table}[htb]
-  \begin{center}
-  \caption{Jungleに実装されているAPI}
-    \begin{tabular}{|p{15em}|p{24em}|}        \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}
-
-
-\section{JungleTree}
-Jungleは複数の木の集合で出来ている。
-ユーザーは、この木に対して検索や編集を行う。
-以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す
-\begin{table}[htb]
-\begin{center}
-\caption{JungleTreeに実装されているAPI}
-\begin{tabular}{|p{15em}|p{24em}|}        \hline
-{\tt TreeNode getRootNode()} &木のルートノードを取得する。   \\ \hline
-{\tt long revision()} & 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。 \\ \hline
-{\tt JungleTreeEditor getJungleTreeEditor()} & 木へ変更を加えるEditorを取得する。\\ \hline
-{\tt Either<Error, JungleTree> getOldTree(long revision)} & 引数で指定したint revisionに等しいバージョンの木を取得する。 \\ \hline
-{\tt InterfaceTraverser getTraverser()} & 木の検索を行うTraverserを取得する。 \\ \hline
-{\tt Either<Error, TreeNode> getNodeOfPath(NodePath path)} & {\tt NodePathで指定した位置と値なるノードを取得する。}  \\ \hline
-{\tt NodePath getNodePath(TreeNode node)} & 引数で渡したノードの位置を表す{\tt NodePath}を返す。\\ \hline
-\end{tabular}
-\label{JungleTreeAPI}
-\end{center}
-\end{table}
-
-
-\section{TreeNode}
-Jungleの木構造は、複数のノードの集合で出来ている。
-ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
-ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。
-
-\begin{table}[htb]
-  \begin{center}
-    \caption{TreeNodeに実装されているAPI}
-    \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
-      {\tt Children getChildren()} & ノードの子供を扱うChildrenオブジェクトを返す。\\ \hline
-      {\tt 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}{|p{15em}|p{24em}|}                                  \hline
-      {\tt int size()}  &  子供の数を返す。\\ \hline
-      {\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。   \\ \hline
-    \end{tabular}
-  \label{Children}
-  \end{center}
-\end{table}
-
-
-
-\begin{table}[htbH]
-  \begin{center}
-    \caption{Attributeに実装されているAPI}
-    \begin{tabular}{|p{15em}|p{24em}|} \hline
-      {\tt ByteBuffer get(String key)}   &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。 \\ \hline
-      {\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。 \\ \hline
-    \end{tabular}
-  \label{Attribute}
-  \end{center}
-\end{table}
-
-\newpage
-以下にルートノードの2番目の子供から、属性名 {\tt 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())
-  return either.a();
-TreeNode child = either.b();
-Attribute attribute = child.getAttribute();
-String value = attribute.getString("name");
-\end{lstlisting}
-
-\begin{enumerate}
-  \item Jungleから名前が{\tt "TreeName"}の木を取得する。
-  \item 取得した木のルートノードを取得する。
-  \item 木のルートノードから{\tt Children}を取得する。
-  \item 3で取得した{\tt Children}から2番目の子供を取得する。
-  \item 関数{\tt Either.isA()}を用いて、2番目の子供が取得できたかを調べる。
-  \item 取得できていなかった場合{\tt Either.a()}でErrorを返す。
-  \item 取得に成功していた場合、{\tt Either.b()}で子ノードを取得する。
-  \item 取得した子ノードから{\tt Attribute}クラスを取得する。
-  \item 取得した{\tt attribute}から属性名 {\tt name}とペアの属性値を取得する。
-\end{enumerate}
-
-\section{木の編集API}
-Jungleの木の編集は{\tt JungleTreeEditor}クラスを用いて行われる。
-{\tt JungleTreeEditor}クラスには編集を行うために、表\ref{editor}で定義されているAPIが実装されている。
-
-\begin{table}[htb]
-  \begin{center}
-    \caption{Editorに実装されているAPI}
-    \begin{tabular}{|p{15em}|p{24em}|}        \hline
-      {\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path,  int pos)} &
-      変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置に子ノードを追加する\\ \hline
-      {\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)}      &
-      変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline
-      {\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} &
-      変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline
-      {\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}&
-      変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されている属性値を削除する。\\ \hline
-      {\tt Either<Error, JungleTreeEditor> moveChild( NodePath path,int num,String move)} &
-      変数{\tt path}で指定した場所にあるノードの、変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline
-      {\tt Either<Error, JungleTreeEditor> pushPop()} &
-      ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline
-      {\tt Either<Error, JungleTreeEditor> success()}  &
-      木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
-    \end{tabular}
-  \label{editor}
-  \end{center}
-\end{table}
-
-
-
-編集後に返される{\tt JungleTreeEditor}クラスは、編集後の木構造を保持しているため、編集前の木構造を保持している{\tt JungleTreeEditor}クラスとは別のオブジェクトである。
-編集を行った後は、関数{\tt editor.success()}で今までの編集をコミットすることができる。他の{\tt JungleTreeEditor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
-その場合は、木の編集を最初からやり直す必要がある。
-
-以下に{\tt 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())
-  return either.a();
-editor = either.b();
-editor.success();
-\end{lstlisting}
-
-\begin{enumerate}
-  \item 関数{\tt tree.getEditor()}で編集を行う木から、{\tt JungleTreeEditor}クラスを取得する。
-  \item 次に変更するノードの場所を示す、{\tt NodePath}クラスを作成する。
-  \item 関数{\tt editor.addNewChildAt()}を用いて、変数{\tt path}で指定したノードの子供の0番目に子ノードを追加する。
-  \item 返り値の変数{\tt either}が{\tt Error}クラスを保持していないか(編集に失敗していないか)を確認する。
-  \item {\tt Error}クラスを保持していた場合{\tt Either.a()}でErrorを返す。
-  \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。
-  \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。
-\end{enumerate}
-
-また、木に対して行われた変更は、Logとして書き出される。
-これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。
-
-
-\section{検索APIの実装}
-これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。
-しかし、木に問い合わせを行う検索APIが実装されていなかったため、属性名 {\tt key} 属性値 {\tt value}の組で検索を行うAPIの実装を、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて行った。
-以下に検索を行う関数{\tt find}の定義を記述する。
-\begin{lstlisting}[frame=lrbt,label=query,numbers=left]
-public Iterator<TreeNode> find(Query query, String key, String searchValue);
-\end{lstlisting}
-
-関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を。
-第二、第三引数には、Indexを用いた絞込に使用する{\tt String key、String value}を取り、条件に一致したノードの{\tt Iterator}を返す。
-{\tt 関数find}の使用例を以下に記す
-
-\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
-InterfaceTraverser traverser = tree.getTraverser(true);
-Iterator<TreeNode> resultNodeIterator = traverser.find((TreeNode node) -> {
-    String personId = node.getAttributes().getString("name");
-      if (personId == null) return false;
-        return personId.equals("kanagawa");
-}, "belong", "ryukyu");
-\end{lstlisting}
-
-
-上記コードについて解説する。
-\begin{enumerate}
-  \item 木の走査を行う{\tt Traverser}クラスを取得する。
-
-  \item Indexから{\tt find}の第2、第3引数である、属性名 {\tt belong}、属性値 {\tt ryukyu}の組のデータを持つノードを取得し、Queryに渡す(ノードの絞込を行う)。
-
-  \item 引数のノードから関数{\tt getAttributes().getString("name")}で属性名 {\tt name}とペアになっている属性値を取得する。
-
-  \item 属性値が{\tt null}だった場合、このノードには属性名が{\tt name}の組のデータは存在しないので、{\tt false}を返し次のノードの評価を行う。
-
-  \item 属性値が{\tt null}でなかった場合、{\tt kanagawa}と一致するかどうかを調べ結果を返す。
-
-\end{enumerate}
-
-このコードの結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータが入ったノードが取得できる。
-
-
-\section{Indexの実装}
-Jungleには、検索の際に使用するIndexが無かったため、実装を行った。
-Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。
-よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。
-既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
-その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
-このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
-Jungleとの違いは、木の回転処理が入ることである。
-これにより複数の版全てに対応したIndexをサポートすることが可能になった。
-以下にJungleにおけるIndexの型を記述する
-
-\begin{lstlisting}[frame=lrbt,label=index,numbers=left]
-TreeMap<String key,TreeMap<String attribute,List<TreeNode> node> index> indexMap
-\end{lstlisting}
-
-JungleのIndexは{\tt IndexMap}内に保持されている。
-属性名で{\tt IndexMap}に{\tt get}を行うと、対応したIndexが取得できる。
-取得したIndexに属性値で{\tt get}を行うと、ノードのリストが返ってくる。
-以下にIndexから属性名 name 属性値 kanagawaのデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。
-
-\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
-Optional<TreeMap<String, List<TreeNode>>> indexOp = indexMap.get("name");
-if (!indexOp.isPresent())
-  return new NulIterator<TreeNode>();
-TreeMap<String, List<TreeNode>> index = indexOp.get();
-Optional<List<TreeNode>> nodeListOp = index.get("kanagawa");
-if (!nodeListOp.isPresent())
-  return new NulIterator<TreeNode>();
-return nodeListOp.get().iterator();
-\end{lstlisting}
-
-
-\begin{enumerate}
-\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt name}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。
-
-\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。
-
-\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
-
-\item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。
-
-\item 取得したIndexに、検索で使用する属性値{\tt kanagawa}で{\tt get()}を行う。すると、属性名 {\tt name} 属性値{\tt  kanagawa}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。
-
-\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt name} 属性値 {\tt kanagawa}を持つノードを木が持っているか)を調べる。
-
-\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
-
-\item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。
-
-\end{enumerate}
-
-JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。
-
-\subsection{Log}
-Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。
-NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。
-Jungle によるデータの編集は TreeOperation が複数集まった単位で commit されていく.
-この TreeOperation の集まりを TreeOperationLog という。
-TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す.
-\begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
-public interface TreeOperationLog extends Iterable<TreeOperation>
-{
-  public TreeOperationLog add(NodePath _p,NodeOperation _op);
-  public TreeOperationLog append(TreeOperationLog _log);
-  public int length();
-}
-\end{lstlisting}
-
-\verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている。
-addやappendメソッドを使ってTreeOperationを積み上げていくことができる。
-
-
-\newpage
--- a/chapter2.tex	Fri Feb 10 16:01:17 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,201 +0,0 @@
-\chapter{Differential Jungle Tree}
-Jungleの木の変更の手間は木の形によって異なる。
-特に線形の木は、変更の手間がO(n)となってしまう。
-線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。
-しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまうため、正順の木を構築する際は、PushPopを使用できない。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.3]{figures/PushPopDemerit.pdf}
-\caption{PushPopの問題点}
-\label{fig:pushpop}
-\end{center}
-\end{figure}
-
-その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築できるDifferential Jungle Treeの実装を行った。
-Differential Jungle Treeは、木のバージョンごとに、自身の末尾のノードを持つ。
-
-\newpage
-\section{Differential Tree Context}
-
-Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持する。
-表\ref{TreeContext}にTreeContextが保持するデータを記述する。
-\begin{table}[htb]
-\begin{center}
-\caption{TreeContextが保持している値}
-\begin{tabular}{|l|}        \hline
-{\tt } 自身のルートノード\\ \hline
-{\tt } 1つ前のversionのTreeContext\\ \hline
-{\tt } 編集のログ\\ \hline
-{\tt } 木のuuid    \\ \hline
-{\tt } 木の名前    \\ \hline
-{\tt } 木のversion    \\ \hline
-{\tt } 木の検索に使うTraverser    \\ \hline
-\end{tabular}
-\label{TreeContext}
-\end{center}
-\end{table}
-
-Differential Jungle Treeでは、現在のバージョンの木構造の末尾ノード保持することが可能な DifferentialTreeContext 作成した。
-
-
-\section{末尾ノードを使用した木の編集}
-Differential Jungle Treeの木の編集は、Default Jungle Treeと同じようにEditorを使用して行う。
-違いは、Default Jungle TreeのEditorは、木の編集を行った後、木の複製を行い過去の木を保持するのに対して、Differential Jungle TreeのEditorは、Sub Treeを保持しており、そのSub Treeに対して破壊的に編集を行う。
-そして、Commitを行う際に、構築したSub Treeを末尾ノードにAppendすることで木の編集を行う。
-そうすることで、木の複製を行う必要が無いため、木の変更の手間はO(1)で行える。
-
-また、Differential TreeはSub Treeに対する変更しか行えないため、一度Commitした木に対して変更は行えない。
-図\ref{fig:EditDifTree}にDifferential Treeの編集の流れを記述する。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.28]{figures/EditDifferencialTree.pdf}
-\caption{末尾ノードを使用した木の編集}
-\label{fig:EditDifTree}
-\end{center}
-\end{figure}
-
-\newpage
-\begin{enumerate}
-\item  木から{\tt getTreeEditor}でEditorを取得する。(このとき取得するEditorはSub Treeを持つ)
-\item  SubTreeに対して{\tt addNewChild(<-1,0>)}を実行し、ノードの追加を行う。
-\item  Commitを行い、Treeの末尾ノードにSub TreeをAppendする。
-\end{enumerate}
-
-また、Differential TreeのIndexのアップデートは、Commit 時に Sub Treeの中身をIndexに追加するだけで良い。
-
-
-\section{Differential Jungle Treeの整合性}
-
-Differential Jungle Treeに対する変更が競合した場合、先にCommitを行った方の変更が適応される。
-末尾ノードへのAppendは、破壊的な変更であるため、Commit成功後に行う。
-そうすることで、編集が競合した際の整合性を保っている。
-
-
-また、Differential Jungle Treeは、木を破壊的に変更する。
-よって、過去の木を取得し、変更を加えた場合、末尾ノードに複数のSub TreeがAppendされてしまい、木の整合性が崩れてしまう。
-その問題を解決するため、Differential Jungle Treeでは、末尾ノードは一つしか子ノードを持つことができない。
-
-ソースコード\ref{src:Append}にSub TreeのAppend部分のコードを記述する。
-
-\begin{lstlisting}[frame=lrbt,label=src:Append,caption=Sub TreeのAppend部分のコード,numbers=left]
-Either<Error, TreeNode> appendSubTree(TreeNode subTreeRoot) {
-  TreeNode appendedNode = treeContext.getEndNode();
-  TreeNodeChildren children = appendedNode.getChildren();
-  if (children.size() != 0)
-    return DefaultEither.newA(APPEND_FAILD);
-  return children.addNewChildAt(0, subTreeRoot);
-}
-\end{lstlisting}
-
-ソースコード\ref{src:Append}の解説を行う。
-
-\begin{enumerate}
-\item 関数{\tt appendSubTree}でSub TreeのAppendを行う。引数にSub Treeのルートを持つ。
-\item TreeContextから末尾ノードを取得する。
-\item 末尾ノードからChildrenを取得する。
-\item 末尾ノードにSub TreeがすでにAppendされているか(子供を持っているか)を調べる。
-\item 他のSub TreeがAppendされている(今編集を行っているのが過去の木)場合、木のAppendは失敗するため、エラーを返す。
-\item そうでない場合、Sub Treeを末尾ノードにAppendする。
-\end{enumerate}
-
-このように、末尾ノードが複数の子を持つことを禁止することで、過去の木を取得した際の木の整合性を保証している。
-
-\section{Commit Operation}
-Default Jungle Treeでは、木に対しての変更は全てメインの木に対する変更であるため、Logに書き出された全ての変更を一回の Commit で行える。
-しかし、Differential Jungle Treeの変更は、Editorが保持しているsubTreeに対する変更を加えた後、 Commit 時にメインの木にAppendを行っている。
-そのため、適切なタイミングでCommitを行わないと、実際に行われた変更とズレが生じて、正しい木を構築できない。
-
-以下に、Logからの木の構築をする際に、一回のCommitでは適切なDifferential Treeを構築できない例を記す。
-\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=適切な木を構築できないLogの例,numbers=left]
-1.[APPEND_CHILD:<-1>:pos:0]
-2[COMMIT]
-3.[APPEND_CHILD:<-1>:pos:0]
-4.[APPEND_CHILD:<-1,0>:pos:0]
-\end{lstlisting}
-
-大文字の英字はLogとして書き出された Operation の種類を表す。
-\verb|<>| により囲まれている数字は NodePath を示す。
-NodePath の表記以降は、ノードの position などの情報を表している。
-[COMMIT]は、実際の木を構築した際にCommitが行われたタイミングを表す。
-
-[COMMIT]のタイミングでCommitを行わず、全ての変更を加えた後にCommitを行った場合、Editor 内部の Sub Treeに、図\ref{fig:badDifTreeCreate}のような変更が加えられ、Append後、図\ref{fig:badDifTree}のような木が構築される。
-
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/badDifTreeCreate.pdf}
-\caption{適切なタイミングでCommitを行わない木の復元の流れ}
-\label{fig:badDifTreeCreate}
-\end{center}
-\end{figure}
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/BadDifTree.pdf}
-\caption{適切なタイミングでCommitを行わなかった木}
-\label{fig:badDifTree}
-\end{center}
-\end{figure}
-
-\clearpage
-
-しかし、実際には、図\ref{fig:createGoodDifTree1}、図\ref{fig:createGoodDifTree2}のような変更が加えられる。
-以下に、適切に Commit を行った場合の木の編集の流れを記述する。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/goodDifTreeCreate1.pdf}
-\caption{適切なタイミングでCommitを行なう、木の復元の流れ(1回目のCommit前、Sub Tree)}
-\label{fig:createGoodDifTree1}
-\end{center}
-\end{figure}
-
-
-1. 木からEditorを取得し、Sub Treeのルートノードの0番目に子ノードを追加する。
-
-\vspace{0.15in}
-2. そして、Commitを行い、1で構築したSub Treeをメインの木にAppendする
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/goodDifTreeCreate2.pdf}
-\caption{適切なタイミングでCommitを行なう、木の復元の流れ(2回目のCommit前、Sub Tree)}
-\label{fig:createGoodDifTree2}
-\end{center}
-\end{figure}
-
-3. 木からEditorを取得し、Sub Tree のルートノードの0番目に子ノードを追加する。
-
-\vspace{0.15in}
-4. 続いて、Sub Treeの{\tt <-1, 0>} 番目にあるノードの、0番目の子供にノードを追加する。
-
-\vspace{0.15in}
-5. 最後に2度目の Commit を行い、Sub Treeをメインの木にAppendする。
-
-\vspace{0.15in}
-
-結果、図\ref{fig:goodDifTree}のような木が構築される。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/goodDifTree.pdf}
-\caption{適切なタイミングでCommitを行なった木の変更。}
-\label{fig:goodDifTree}
-\end{center}
-\end{figure}
-
-このように、Logとして書き出されたTreeOperationから、適切な構造のDifferential Treeを復元するためには、木の構築時と同じタイミングでCommitを行う必要がある。
-そのため、Commitのタイミングを、Logとして書き出し、適切なタイミングでCommitを行えるようにした。
-
-
-
-
-\section{Differential Jungle Treeの検索}
-Differential Treeは、木を破壊的に編集する。
-そのため、過去の木から特定の値を持ったノードを取得する際、全てのノードを走破した場合その版の木には無いはずのノードが取得できてしまうことがある。
-そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する検索を実装した。
-
-Indexを使用した検索を行う場合、各版に対応したIndexがあるため、Default Treeと検索の方法は変わらない。
-
--- a/chapter3.tex	Fri Feb 10 16:01:17 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,317 +0,0 @@
-\chapter{Red Black Jungle Tree}
-Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
-Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。
-そこで、ノードの挿入を行うと木のバランスを取る、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。
-
-\section{Red Black Tree}
-Red Black Treeは二分探索木の一つで、以下の条件を満たした木のことである。
-
-\begin{enumerate}
-\item ノードは赤か黒の色を持つ。
-\item ルートノードの色は黒。
-\item 全ての葉は黒である。
-\item 赤いノードの子は黒色である。
-\item 全ての葉からルートまでのパスには、同じ個数の黒いノードがある。
-\end{enumerate}
-
-Red Black Treeは、データの挿入、削除時に、上記の条件を崩さないように木のバランスを取る。
-この条件により、Red Black Treeはデータの検索、削除、探索をO(log n)で行える。
-
-\section{Red Black Jungle Treeの作成}
-Red Black Jungle Treeを作成するため、Jungleに{\tt createNewRedBlackTree(String treeName, String balanceKey)}を実装した。
-これは、第一引数{\tt treeName}で受け取った名前の、第二引数{\tt balanceKey}とペアになる属性値でバランスを取るRed Black Treeを構築する。
-
-またこれ以降の説明で使用するbalanceKeyは、Red Black Jungle Treeを作成する時に設定したkey、BalanceValueは属性名 BalanceKeyとペアの属性値のことである。
-
-\section{Red Black Jungle Treeの編集}
-Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKeyとそのペアの属性値が必要になる。
-しかし、JungleTreeEditorには、ノードと値を同時に追加するAPIは存在しなかったため、新しく実装した。
-また、Red Black Jungle Treeにおいて、特定の属性名と属性値のペアを持つノードを削除するAPIも同時に実装した。
-表\ref{NewEditorAPI}に新しく実装したAPIを記述する。
-
-\begin{table}[htb]
-\begin{center}
-\caption{新たにJungle Tree Editorに定義したAPI}
-\begin{tabular}{|p{15em}|p{24em}|}        \hline
-{\tt Either<Error, JungleTreeEditor> addNewChildAndPutAttribute(NodePath path, int pos, String key, ByteBuffer value)} & pathで指定した位置にあるノードのpos番目に、属性名 keyと属性値 valueの組を持つノードを追加する。\\ \hline
-{\tt Either<Error, JungleTreeEditor> deleteChildAt(String Key, ByteBuffer value)} & 木から特定の属性名 keyと属性名 valueを持っているノード検索し、削除する。\\ \hline
-\end{tabular}
-\label{NewEditorAPI}
-\end{center}
-\end{table}
-
-
-Red Black Jungle Tree Editorは、既存のJungle Tree EditorとくらべてAPIの使い方が異なる。
-具体的にはaddNewChildAtでPathが使われなかったりする。
-表\ref{EditorDifference}にDefault Jungle Tree EditorとRed Black Jungle Tree EditorのAPIの使い方の違いを記述する。
-
-\begin{table}[htb]
-\begin{center}
-\caption{Red Black Jungle TreeとDefault Jungle TreeのAPIの違い}
-\begin{tabular}{|p{15em}|p{24em}|}        \hline
-{\tt  Either<Error, JungleTreeEditor> addNewChildAt(NodePath path, int pos)} & pathとposは使用せず、属性名 balanceKey 属性値 "Default Value"を持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 \\ \hline
-{\tt  Either<Error, JungleTreeEditor> addNewChildAt(NodePath path, int pos, String key, String value)} & pathとposは使用せず、属性名 key 属性値 valueを持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 第二引数にBalanceKey以外の値を渡した場合、バランスが取れない為、ノードの挿入は失敗する。\\ \hline
-{\tt  Either<Error, JungleTreeEditor> replaceNewRootNode()} &  赤黒木は、新しくルートを追加する意味が無いので使用しない。実行した場合エラーを返す。\\ \hline
-{\tt  Either<Error, JungleTreeEditor> moveChild(NodePath path, int childNum, String move)} &  ノードを動かすと木のバランスが崩れるため使用しない。実行した場合エラーを返す。 \\ \hline
-\end{tabular}
-\label{EditorDifference}
-\end{center}
-\end{table}
-
-
-
-\section{Jungle Red Black Treeへのデータの挿入}
-Jungle Red Black Treeへのデータの挿入は、以下の手順で行われる。
-
-\begin{enumerate}
-\item 挿入を行うノードのBalanceValueと、現在のノードBalanceValueを比較する。
-\item 比較の結果、大きかった場合右に、小さかった場合左のノードに進む。
-\item 挿入を行う場所にたどり着くまで、１・２を繰り返す。
-\item 現在の位置に、赤色でノードを挿入する。
-\item 木のバランスを取りながら、ルートまでの経路の複製を行う。その際Defaul Jungle Treeと同じように、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。
-\end{enumerate}
-
-Jungle Red Black Treeのバランスは、データ挿入時の状態によって、次の5パターンに分けられる。
-
-\subsection{データ挿入時のバランス ケース1}
-
-\begin{enumerate}
-\item ノードを挿入した位置がルート
-\end{enumerate}
-挿入時上記の条件を満たしている場合、ルートノードの色を黒に変更することで木のバランスを取る。
-ルートノードの色を黒に変更しても、左右のSub Treeの黒の個数が一つ増えるだけなので、Red Black Treeの条件は守られる。
-
-
-\subsection{データ挿入時のバランス ケース2}
-\begin{enumerate}
-\item 挿入したノードinsの親ノードBが黒。
-\end{enumerate}
-
-バランス時、上記の条件を満たしている場合、Red Black Treeの条件は崩れないため、そのまま赤色でノードを挿入して問題はない。%(図\ref{fig:RedBlackTreeInsert1})。
-
-%\begin{figure}[htpb]
-%\begin{center}
-%\includegraphics[scale=0.5]{figures/RedBlackTreeInsert1.pdf}
-%\caption{データ挿入時のバランス2}
-%\label{fig:RedBlackTreeInsert1}
-%\end{center}
-%\end{figure}
-
-
-\subsection{データ挿入時のバランス ケース3}
-\begin{enumerate}
-\item 挿入したノードinsの親の親ノードAが黒。
-\item ノードAの両方の子ノードB・Cが赤。
-\end{enumerate}
-
-バランス時、上記の条件を満たしている場合、ノードB・Cを黒に、ノードAを赤に変更する(図\ref{fig:RedBlackTreeInsert2})。
-
-また、本章の図に表記されている四角のノードの色は、Red Black Treeの条件を守られているなら問わず、それ以下の子ノードは省略してあるものとする。
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.5]{figures/RedBlackTreeInsert2.pdf}
-\caption{データ挿入時のバランス3}
-\label{fig:RedBlackTreeInsert2}
-\end{center}
-\end{figure}
-
-バランス後、ノードAを新しくノードinsとして再帰的に木のバランスを行う。
-この変更は最悪の場合ルートまで続く。
-
-\subsection{データ挿入時のバランス ケース4}
-\begin{enumerate}
-\item 挿入したノードinsの親の親ノードAが黒。
-\item ノードAの、挿入したノード側の子ノードBが赤。
-\item 逆側の子ノードCが黒。
-\item ノードinsがノードBの木の中心側の子。
-\end{enumerate}
-
-バランス時、上記の条件を満たしている場合、ノードBを中心に外側に回転処理を行い(\ref{fig:RedBlackTreeInsert3})、次節に記述するバランス5を行う。
-その際、ノードBをinsとして扱う。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.5]{figures/RedBlackTreeInsert3.pdf}
-\caption{データ挿入時のバランス4}
-\label{fig:RedBlackTreeInsert3}
-\end{center}
-\end{figure}
-
-
-\subsection{データ挿入時のバランス ケース5}
-\begin{enumerate}
-\item 挿入したノードinsの親の親ノードAが黒。
-\item ノードAの、挿入したノード側の子ノードBが赤。
-\item 逆側の子ノードCが黒
-\item ノードinsがノードBの木の外側の子。
-\end{enumerate}
-
-バランス時、上記の条件を満たしている場合、ノードAを中心に内側に回転処理を行い、回転後ノードAとノードBの色を入れ替える。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.5]{figures/RedBlackTreeInsert4.pdf}
-\caption{データ挿入時のバランス5}
-\label{fig:RedBlackTreeInsert4}
-\end{center}
-\end{figure}
-
-
-赤黒木は、データ挿入時にこれらの処理を行うことで、木のバランスを取る。
-
-
-\section{Jungle Red Black Treeのノード削除}
-Jungle Red Black Treeのノード削除は、以下の手順で行われる。
-
-\begin{enumerate}
-\item 削除を行うノードを検索する。
-\item ノードに子が無い場合削除を行う。
-\item 片側に部分木(子ノード)がある場合、ノードを削除した後、部分木のルートを昇格させる。
-\item 両側に部分木(子ノード)がある場合は、左部分木の最大の値を持つノードの値を取得し、削除を行うノードと同じ色に変更した後、置換する。
-\item 昇格させたノードを削除する(ここで削除させるノードは部分木の最大値であるため、子ノードは1つ以下、つまり削除の手順2・3どちらかの手順で削除できる)。
-\item 削除したノードから、木のバランスを取りながら、ルートまでの経路の複製を行う。その際Defaul Jungle Treeと同じように、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。
-\end{enumerate}
-
-
-RedBlackTreeのバランスは、ノード削除時の状態によって、次の6パターンに分けられる。
-また。これ以降削除対象のノードと置換したノードを、ノードrepと記述する。
-\subsection{データ削除時のバランス ケース1}
-
-\begin{enumerdte}
-\item 削除したノードが赤の場合。
-\end{enumerate}
-
-上記の条件を満たしている場合、木の経路にある黒ノードの数は変らないためバランスを行う必要はない。
-
-\begin{enumerate}
-\item 削除したノードが黒。
-\item 削除したノードの子ノードrepが赤。
-\end{enumerate}
-
-上記の条件を満たしている場合は、、ノードrepを置き換える際に赤から黒に色を変えることで木のバランスを取る。
-
-以降、削除したノードの子の色が黒の場合のパターンについて記述する。
-\subsection{データ削除時のバランス ケース2}
-\begin{enumerate}
-\item ノードrepがルートに置き換えられた。
-\end{enumerate}
-
-上記の条件を満たしている場合、全ての経路の黒ノード数が1つ減った状態で条件が成立しバランスは終了する。
-
-\subsection{データ削除時のバランス ケース3}
-\begin{enumerate}
-\item 削除したノードが黒。
-\item ノードrepが黒。
-\item ノードA・B・C・D・E・Fが黒。
-\end{enumerate}
-
-バランス時、上記の条件を満たしている場合、ノードBを赤に変える(図\ref{fig:RedBlackTreeDelete1})。
-そうすることで、ノードB・E・F以下の黒ノードの階層が減って、ノードA以下の木のバランスが回復する。
-その後、Aを新たなノードrepとして木のバランスを行う。
-このバランスは最悪の場合ルートまで続き、ケース2で終了する。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/RedBlackTreeDelete1.pdf}
-\caption{データ削除時のバランス3}
-\label{fig:RedBlackTreeDelete1}
-\end{center}
-\end{figure}
-
-\subsection{データ削除時のバランス ケース4}
-\begin{enumerate}
-\item 削除したノードが黒。
-\item ノードrepが黒。
-\item ノードA・C・D・E・Fが黒
-\item ノードBが赤。
-\end{enumerate}
-
-上記の条件を満たしている場合、ノードAを中心に外側に回転、その後ノードAを赤に、ノードBを黒に変更する(図\ref{fig:RedBlackTreeDelete2})。
-その後、ノードrepを基準に再び木のバランスを行う。
-この時のバランスは、図\ref{fig:RedBlackTreeDelete2}における、ノードEの子供の色に応じてケース5・6・7のどれかに帰着する。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/RedBlackTreeDelete2.pdf}
-\caption{データ削除時のバランス4}
-\label{fig:RedBlackTreeDelete2}
-\end{center}
-\end{figure}
-
-\subsection{データ削除時のバランス ケース5}
-\begin{enumerate}
-\item 削除したノードが黒。
-\item ノードrepが黒。
-\item ノードB・C・D・E・Fが黒
-\item ノードAが赤。
-\end{enumerate}
-
-上記の条件を満たしている場合、ノードAを黒に、ノードBを赤に変更する。
-そうすることで、ノードA側の右側のSub Treeの黒の深さを変えることなく、左側のSub Treeの黒の深さが1つ増え、バランスが取れる。
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/RedBlackTreeDelete3.pdf}
-\caption{データ削除時のバランス5}
-\label{fig:RedBlackTreeDelete3}
-\end{center}
-\end{figure}
-
-\subsection{データ削除時のバランス ケース6}
-\begin{enumerate}
-\item 削除したノードが黒。
-\item ノードrepが黒。
-\item ノードB・C・D・Fが黒。
-\item ノードEの色が赤。
-\end{enumerate}
-
-上記の条件を満たしている場合、ノードBを中心に外側に回転、その後、ノードEを黒に、ノードBを赤に変更する。
-そして、データ削除時のバランス ケース7に帰着する。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/RedBlackTreeDelete4.pdf}
-\caption{データ削除時のバランス6}
-\label{fig:RedBlackTreeDelete4}
-\end{center}
-\end{figure}
-
-
-\subsection{データ削除時のバランス ケース7}
-\begin{enumerate}
-\item 削除したノードが黒。
-\item ノードrepが黒。
-\item ノードB・C・Dが黒。
-\item ノードFの色が赤。
-\end{enumerate}
-
-上記の条件を満たしている場合、ノードAを中心にノードrep側に回転、その後、ノードAとノードBの色を交換し、ノードFを黒にする。
-そうすることで、ノードE・Fの黒の深さを変えること無く、ノードrepの黒の深さを1増やせるため、木のバランスが取れる。
-
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.45]{figures/RedBlackTreeDelete5.pdf}
-\caption{データ削除時のバランス7}
-\label{fig:RedBlackTreeDelete5}
-\end{center}
-\end{figure}
-
-Red Black Jungle Treeは、これらの処理を行うことで、データの挿入・削除時にこれらの処理を行うことで、木のバランスを保っている。
-また、Red Black Jungle Treeは自身の木構造がIndexとしての機能を持つため、木の編集を行った際に別途Indexを構築する必要はない。
-
-\section{Jungle Red Black Treeの検索}
-Red Black Jungle Treeへの検索は、Red Black Jungle Tree Traverserを用いて行う。
-Red Black Jungle Treeは、Indexを持たないため、Traverser.find(Query query, String balanceKey, String balanceValue)の第二・第三引数は、木を作成する時に設定したbalanceKey・属性名 balanceKeyとペアのbalanceValueを取る。
-balanceKeyを使ったデータの検索は以下の手順で行う。
-
-\begin{enumerate}
-\item 現在のノードから、findの第二引数で取得した、属性名 BalanceKeyとペアになっている属性値 valueを取得する。
-\item 1で取得した属性値 valueと、findの第三引数で取得したbalanceValueを比較する。
-\item 比較の結果、大きかった場合、右に、小さかった場合左のノードに進む。
-\item 同じ値を持つノードを発見するか、葉にたどり着くまで1~3を繰り返す。
-\item 同じ値を持つノードを発見したら、そのノードを返す。
-\item 葉までたどり着いた場合、その木は対応するノードを持っていないため
-\item 5で取得したノードが、第一引数のqueryの条件に一致するか確かめる。
-\item 一致する場合そのノードを返す。
-\end{enumerate}
-
-これらの実装により、Red Black Jungle Treeは、木の構築・検索の機能を持つ。
--- a/chapter4.tex	Fri Feb 10 16:01:17 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,49 +0,0 @@
-\chapter{Jungleを使ったアプリケーション}
-本章では、これまで開発をしたJungleを使用したアプリケーションを記述する。
-
-
-\section{Jungle Tree ブラウザ}
-
-Jungleの木に対する変更において、{\tt JungleTreeEditor}クラスを用いる方法はプログラム上では便利だが、手動で変更するのには向いていない。
-よって、組み込みWEBサーバーであるJettyを使用し、Servletとして木の表示と編集を実現した。
-
-\subsection{木構造の表示}
-JungleTreeブラウザにおいて、Jungle DBはWEBサーバー内に存在し、それから表示に必要なHTMLを生成してブラウザに転送する。
-%図\ref{printNode}は、サーバからデータを送り、ブラウザ上でノードを可視化するまでの流れである。
-この流れは、Jungleの{\tt NodePath}の処理を除けば通常のデータベースのレコードの表示と同等である。
-
-編集するノードのパスはURLで記述されている。例えば、
-{\small
-  \verb! http://localhost/showBoardMessage?!
-    \verb!           bname=Layout&path=-1,0,2!
-}
-などとなる。
-
-以下にJungleTreeブラウザを用いて、ノードを表示するまでの流れを記述する。
-\begin{enumerate}
-\item ユーザーは表示したいノードのパスをURLでJungleTreeブラウザに送る。
-\item JungleTreeブラウザは、WEBサーバ内にあるJungleから、対応した木を取得する。
-\item JungleTreブラウザは、パスで指定した位置のノードを木から取得する。
-\item 取得したノードの中身を、JungleTreeブラウザが表示する。
-\end{enumerate}
-
-
-\subsection{Jungle Tree ブラウザを使った木の編集}
-%図\ref{JungleEdit}はブラウザを用いたJungleの木の更新の流れである。
-以下にJungle Treeブラウザを用いた木の編集の流れを示す。
-\begin{enumerate}
-\item ユーザーはJungleTreeブラウザで編集したいノードを表示するページに移動する 。
-\item ユーザーはJungleTreeブラウザに木の変更要求を送る。
-\item JungleTreeブラウザはWebサーバー内にあるJungleから、対応した木を取得する。
-\item 編集を行う木から、{\tt JungleTreeEditor}クラスを取得し、木の変更を行う。
-\item 木の変更をJungleにコミットする。
-\item 木の変更の結果を表示する。
-\end{enumerate}
-
-パスを使用することにより、木の変更をRestfulに行うことができるように見えるが、木のパスは特定の木の版に固有のものである。
-ブラウザとWEBサーバは、セッションで結合されており、そのセッションが同じ版の木を編集していれば問題なく成功する。
-ただし、編集し終わった時に、他の編集が割り込んでいたら、その編集は無効となる。
-%この点が既存のRDBとは異なる。
-また巨大な木を操作する時には、Pathを直接URLに含むことはできないので、他の工夫が必要になると考えられる。
-このアプリケーションでは任意の木を取り扱うので、木の大きさの現実的な制限を除けば木の設計の問題はない。
-
--- a/chapter5.tex	Fri Feb 10 16:01:17 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,156 +0,0 @@
-\section{HTML Rendering Engine}
-HTMLRenderingEngineは、出力するデータが記述されたContents Tree、出力する形式が記述されたLayout Treeの2つの木構造を持ち、これらを参照しながらhtmlのレンダリングを行う。
-またレンダリングする例題は日記を選択した。
-
-\subsection{Contents TreeのJungle上での表現}
-RenderingEngineではContents Treeに図\ref{contentTree}のように出力するデータを格納した。
-
-\begin{figure}[h]
-\begin{center}
-\includegraphics[scale=0.25]{figures/contentTree.pdf}
-\caption{ContentTree}
-\label{contentTree}
-\end{center}
-\end{figure}
-
-
-RootNodeはContentの{\tt title}、日時、レンダリングする時に参照するLayoutTreeのNodeNameを持つ。
-そして子ノードが日記の本文等のデータを持つ。
-表\ref{NodeAttribute}にノードが保持しているContentsの一覧を記述する。
-
-\begin{table}[htb]
-\begin{center}
-\caption{ノードが保持しているContents一覧}
-\begin{tabular}{|p{15em}|p{24em}|}        \hline
-属性名         & 属性値                             \\ \hline
-component      & レンダリングする際に参照するLayoutTreeのNodeName  \\ \hline
-title          & 日記のタイトル                      \\ \hline
-date(rootNode) & 日記の日時                          \\ \hline
-type           & そのノードが保持しているContextType。 text(日記本文) or image(画像データ)  \\ \hline
-body           & 日記の本文                           \\ \hline
-date(image)    & 画像の保存日時                       \\ \hline
-fileName       & 画像の名前                           \\ \hline
-\end{tabular}
-\label{NodeAttribute}
-\end{center}
-\end{table}
-
-\subsection{Layout}
-htmlの出力形式を定義するLayoutは、複数のComponentからなる。
-表\ref{LayoutTreeTable}に、LayoutTreeの主要要素を記す。
-Layout Treeには図\ref{layoutTree}のようにデータを格納した。
-また、LayoutTreeはノード同士が{\tt NodeName}を用いて参照を行う。
-
-
-\begin{figure}[h]
-\begin{center}
-\includegraphics[scale=0.25]{figures/LayoutTree.pdf}
-\caption{LayoutTree}
-\label{layoutTree}
-\end{center}
-\end{figure}
-
-
-\begin{table}[htbH]
-\begin{center}
-\caption{LayoutTreeの主要な要素}
-\begin{tabular}{|p{15em}|p{24em}|}        \hline
-属性名              & 属性値                     \\ \hline
-NodeName            &ノードの名前。ノード同士の参照時に用いられる。例外としてルートノードだけはdisplayinformationという名前を持つ\\ \hline
-displayComponent    &参照するノードの名前。          \\ \hline
-Name                &この属性名で取得できる値を持つNodeNameを持つノードを参照する。\\ \hline
-use                 &このノードが、どのContentsに対してのLayoutを持つかを記述するタグ。表\ref{tag}にタグとContentsの対応を記述する。\\ \hline
-その他              &css等と同じ様な記述を行う。 例 属性名 {\tt font} 属性値 {\tt fontSize}など                \\ \hline
-\end{tabular}
-\label{LayoutTreeTable}
-\end{center}
-\end{table}
-
-
-Layout Treeは、ルートノードに属性名 {\tt NodeName} 属性値 {\tt displayinformation} の値を持つ(図\ref{layoutTree}では{\tt Node1}が該当する)。
-ルートノードは、子ノードに複数のComponentを保持する(図\ref{layoutTree}では{\tt Node2}、{\tt Node3}がそれに該当する)。
-{\tt Node2}は、属性名 {\tt use} 属性値 {\tt image}のペアでタグを保持しているため、日記の画像表示に対応する記述が行われている。
-{\tt Node3}は、属性名 {\tt use} 属性値 {\tt text}のペアでタグを保持しているため、日記の本文に対応する記述が行われている。
-表\ref{tag}にタグとContentsの対応を記述する。
-
-\begin{table}[htb]
-\begin{center}
-\caption{tagとcontentsの対応}
-\begin{tabular}{|p{15em}|p{24em}|}        \hline
-tag   & content          \\ \hline
-image & 画像の表示       \\ \hline
-cals  & table            \\ \hline
-date  & 日付の表示       \\ \hline
-text  & 日記の本文       \\ \hline
-title & 日記のタイトル   \\ \hline
-\end{tabular}
-\label{tag}
-\end{center}
-\end{table}
-
-
-Layoutが複数のComponentを参照する際は図\ref{multiComponent}のような木構造を構築する(この木はLayoutTreeの一部であり、本来は参照先のノード等が存在している)。
-\begin{figure}[h]
-\begin{center}
-\includegraphics[scale=0.25]{figures/multiComponent.pdf}
-\caption{複数のComponentを参照するLayout}
-\label{multiComponent}
-\end{center}
-\end{figure}
-
-図\ref{multiComponent}の例では、{\tt diaryMulti@component}は{\tt diaryText@component}と{\tt diaryImage@component}を参照している。
-
-以下に図\ref{contentTree}のContentsTree、図\ref{multiComponent}のLayoutTreeの２つを使用した、レンダリングの流れを記述する。
-\begin{enumerate}
-
-\item  ContentsTreeのルートノードは、属性名 {\tt component} 属性値 {\tt Multi@Component}の組を持つので、LayoutTreeの{\tt Node2}を参照する。
-
-\item {\tt Node2}は自身のNodeNameしか持たないので、子ノードである{\tt Node3、Node4}に記述されているデータの参照を行う。
-
-\item {\tt Node3}は属性名 {\tt displayComponentName} 属性名 {\tt dialyImage@Component}の組を持つため、NodeNameが{\tt dialyImage@Component}のノードを参照している。
-
-\item レンダリングエンジンは、参照先のノードに記述されたルールに則ってHtmlを生成する。
-
-\item {\tt Node3}は、これ以上データを持たないため、次は{\tt Node4}を参照する。
-
-\item {\tt Node4}は属性名 {\tt displayComponentName} 属性名 {\tt dialyText@Component}の組を持つため、NodeNameが{\tt dialyText@Component}のノードを参照している。
-
-\item レンダリングエンジンは、参照先のノードに記述されているルールに則ってhtmlを生成する。
-
-\end{enumerate}
-
-(4)、(7)で参照しているノードに関しては、図\ref{layoutTree}の{\tt Node2、Node3}の様な記述が行われている。
-
-\subsection{Layout Treeのデータ設計}
-Jungleは汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能である。
-しかし、設計を行うことでより効率的に木構造を扱うことが可能になる。
-図\ref{goodLayoutTree}、図\ref{badLayoutTree}は同じデータを格納した２つの木の一部である。
-
-
-\begin{figure}[h]
-\begin{center}
-\includegraphics[scale=0.25]{figures/goodLayoutTree.pdf}
-\caption{コードとギャップのないLayoutの格納方法}
-\label{goodLayoutTree}
-\end{center}
-\end{figure}
-
-\begin{figure}[h]
-\begin{center}
-\includegraphics[scale=0.25]{figures/badLayoutTree.pdf}
-\caption{コードとギャップのあるLayoutの格納方法}
-\label{badLayoutTree}
-\end{center}
-\end{figure}
-
-
-図\ref{goodLayoutTree}のTreeは、１つのノードにレンダリングに必要な値が全て格納されている。
-そのため、レンダリングを行う際、複数のノードをまたぐ必要が無く、簡潔にコードを書くことができる。
-
-
-
-一方、図\ref{badLayoutTree}の木はレンダリングする際に必要な値が複数ノードに分散されて保存されている。
-そのため、全てのノードを参照し、値を集める処理を行う必要があり、コードの可読性が下がり余計な処理も増えてしまう。
-これより、Jungleの木構造を効率的に扱うためには、設計手法を確率する必要があることがわかる。
-
-
--- a/judge.tex	Fri Feb 10 16:01:17 2017 +0900
+++ b/judge.tex	Sat Feb 11 01:11:59 2017 +0900
@@ -18,7 +18,7 @@

 \vspace{1cm}
 \underline{\hspace{6cm}印}\\
-（副\hspace{1em}査）\hspace{1em}岡崎 威生 氏
+（副\hspace{1em}査）\hspace{1em}岡崎  威生 氏

 \vspace{1cm}
 \underline{\hspace{6cm}印}\\
Binary file master_paper.pdf has changed
--- a/master_paper.tex	Fri Feb 10 16:01:17 2017 +0900
+++ b/master_paper.tex	Sat Feb 11 01:11:59 2017 +0900
@@ -5,18 +5,27 @@
 \usepackage{here}
 \usepackage{listings,jlisting}
 \usepackage{comment}
+\usepackage{utf}
 %\input{dummy.tex} %% font

-\jtitle{ソフトウェア内部で使用するのに適した 木構造データベース Jungle}
-\etitle{Tree Structure Database Jungle to Use Inside of software}
-\year{平成28年度}
+\pagetitle{修士(工学)学位論文}
+\pagetitleEnglish{Master's Thesis of Engineering}
+
+\jtitle{ソフトウェア内部で使用するのに適した\\ 木構造データベース Jungle}
+\etitle{Tree Structured Database Jungle for software internal use}
+\year{\textbf{2017}年\textbf{3}月}
+\yearEnglish{March 2017}
 \affiliation{\center%
   \includegraphics[clip,keepaspectratio,width=.15\textwidth]
                   {images/u-ryukyu-Mark.eps}\\
                   \vskip10mm
-                  琉球大学大学院 \ 理工学研究科\\ 情報工学専攻}
+                  琉球大学大学院 \ 理工学研究科\\ 情報工学専攻\\
+                  Information Engineering Course\\
+                      Graduate School of Engineering and Science\\
+                      University of the Ryukyus
+                  }

-\author{金川 竜己}
+\author{金川 竜己\\ \rm\textbf{Tatsuki Kanagawa}}

 \marklefthead{% 左上に挿入
   \begin{minipage}[b]{.4\textwidth}