\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{Database Jungleに関する研究}
\author{115731 金川竜己 {}{} 指導教員 : 指導教員名}
\date{}
\maketitle
\thispagestyle{fancy} 

\section{研究目的}
実際の業務システム等で、アカウントアカウント管理を行う際に既存のDatabaseでは、過去のversionのデータを参照するAPIが無かったり、木構造のデータ型を入れる際に面倒だったり、問題がある。\\
そこで、当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用いたデータベースであるJungleを開発している。\\
Jungleは非破壊で過去のデータを変更しないので、過去のデータを簡単に参照できるはずである(まだ未実装)\\
また、Jungle自体木構造データベースなので木構造をそのまま格納出来るなど様々な利点がある。\\
その後、当研究室と共同研究を行っているSymphoniesが開発しているアカウント認証システムmaTrixにJungleを組み込む

\section{非破壊的木構造}
非破壊的木構造は一度構築した木構造を破壊すること無く、新しい木構造を構成することで木構造を編集する方法である。\\
ここでは通常の破壊的木構造との違いを説明する

\subsection{破壊的木構造}
破壊的木構造は、木構造を編集する際に、木構造を書き換えることにより編集を行う\\
しかし破壊的構造では、並列環境において問題が発生し、閲覧者が読み込みを行っている際に編集者が木構造を書き換えると、閲覧者が参照を開始した時点での木構造ではなく整合性が崩れてしまう。\\
この状態を回避するためには、木構造にアクセスする際には、木構造をロックする。\\
しかしロックすることは、排他処理を行い、木構造を利用している処理が１つであることを保証するものであるため、並列度を下げることになってしまい、破壊的木構造は並列処理に向かないことがわかる
\newline
\newline
\newline
\newline
\newline
\newline
\begin{figure}[!htbp]
  \includegraphics[scale=0.3]{jungle.pdf}
  \caption{木構造の破壊的変更例}
  \label{fig:dest-tree1}
  \end{figure}



\subsection{非破壊的木構造}
その一方で非破壊的木構造は、木構造を書き換えること無く編集を行うため読み書きを並列に行うことが可能である\\
非破壊的木構造の基本的な、木の編集手順は以下の様に行われる
\begin{enumerate}
  \item   変更したいノードまでのパスを求める
  \item   変更したいノードを複製し、複製したノードの内容を変更する
  \item   1で求めた、パス上に存在するノードをルートノードに向かってコピーする。コピーしたノードの子をコピー後のノードの子として追加する
  \item   影響の無いノードは共有する
\end{enumerate}
この編集方法で、破壊的木構造の場合と同様にある時点の木構造を参照している閲覧者と、編集している編集者を考える\\
閲覧者が木構造を参照している中、編集者が非破壊的な編集を行う、破壊的方法とは異なり、元の木構造は破壊されることは無いため編集後も整合性は崩れることはない\\
よってロックを行う必要が無いため並列に読み書きが可能である。\\
また、元の木構造は破壊されることが無いため、自由にコピーを作成しても構わない。すなわち、アクセスの負荷も分散させることが可能である\\

\newpage
\newline
\newline
\newline
\begin{figure}[!htbp]
\begin{flushleft}
  \includegraphics[scale=0.28]{jungle2.pdf}
\end{flushleft}
    \caption{木構造の非破壊的変更例}
      \label{fig:dest-tree1}
        \end{figure}
\section{functionalJava}
JungleではJava上で関数型プログラミングを行うためのFunctionalJavaを使用している。\\
関数言語の特徴として、副作用(変数等の書き換え)がないことがあげられる\\
ここでは後述するIndexの実装で使用したFunctionalJavaのTreeMapについて説明する\\

\subsection{TreeMap}
TreeMapは、FunctionalJavaに実装されているClassで、KeyとValueを用いて赤黒木を構築する\\
赤黒木の長所として、ソート済みの二分木の探索なので計算量がO(logN)であること、最悪計算量がデータ構造のうちで最善のものの１つであるので、安定した速度でデータの編集が行えることの２つがあげられる\\
また新しくTreeを構築する際、過去のTreeの一部を再利用するのでメモリの使用効率が良い\\

\section{Indexの実装}
%\subsection{Node}
%Nodeは、木構造を表現するためのコンポーネントであり、子供と辞書を保持している\\
%辞書はTreeMapを用いて$<$String key,ByteBuffer Value$>$の組み合わせで管理されている\\
%\newline
%\newline
%\begin{figure}[!htbp]
%\begin{flushleft}
%  \includegraphics[scale=0.28]{node.pdf}
%  \end{flushleft}
%      \caption{木構造の非破壊的変更例}
%            \label{fig:dest-tree1}
%                    \end{figure}
\subsection{Indexの型}
Indexのデータの型は\\TreeMap$<$String key,TreeMap\\$<$String value,List$<$Pair$<$TreeNode,NodePath$>>>>$\\となっている\\
最初のTreeMap$<$String ,TreeMap$>$はIndexを格納するTreeMapである。\\
このTreeMapに対しkeyでgetを行うと、対応するIndexが登録されている場合Indexを取得できる\\
取得したIndexに対しValueでgetを行うと、valueの値を持つNodeとそのNodeまでのPathの２つをPairにまとめたものが返ってくる。\\
Indexを使う利点として、探索の計算量が全探索のO(N)からO(logN)になることが挙げられる

\subsection{Indexの作成}
IndexはTreeに対して、探索を行う際に作成される。\\
Treeにおける探索の流れを以下に示す
\begin{enumerate}
  \item まずindexのリストに対して探索する文字列のkeyでgetを行い、対応するIndexが登録されているかどうかを調べる
  \item keyに対応するIndexが登録されている場合は、そのIndexに対しvalueでgetを行いその結果を返す。
  \item 対応するIndexが登録されていなかった場合、TreeをIndexを作りながら全探索を行い、探索結果を返す。
\end{enumerate}

\subsection{Indexの編集}
JungleではTreeの編集にはJungleTreeEditorを使用し、Nodeの追加、削除、値のput、deleteを行える\\
そこでJungleTreeEditorの機能を拡張し、Treeへの変更をIndexに反映するIndexJungleTreeEditorを作成した\\
IndexJungleTreeEditorを使えば、Treeに加えた変更をIndexに反映することが出来る。

\subsection{Indexの削除}
まだ未実装\\
これから実装を行う


\section{過去のversionの参照}
まだ未実装\\
Jungleは非破壊なので、過去のversionのTreeを保持している\\
なので簡単に参照できるはずである\\
これから実装を行う\\

\section{これから行うべきこと}
\begin{enumerate}
  \item Indexの削除APIの実装
  \item 過去のversionの参照APIの実装
  \item Indexを使用した場合の性能評価
  \item Jungleのソースが大分汚くなってきたのでリファクタリング
\end{enumerate}
\begin{thebibliography}{9}

  \bibitem{1}
    玉城将士 非破壊的木構造を用いた分散CMSの設計と実装
  \bibitem{2}
    大城信康 分散Database Jungleに関する研究
  \bibitem{3}
    Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界
  \end{thebibliography}

  \end{document}