--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Makefile	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,27 @@
+# target name
+TARGET=main
+
+# dependencies
+$(TARGET).pdf : $(TARGET).dvi
+	dvipdfmx $<
+
+$(TARGET).dvi : $(wildcard **/*.tex) $(TARGET).tex
+	platex $(TARGET).tex
+	platex $(TARGET).tex
+	platex $(TARGET).tex
+
+
+# commands
+.PHONY : clean all open remake
+
+clean:
+	rm -f *.dvi *.aux *.log *.pdf *.ps *.gz *.bbl *.blg *.toc *~ *.core *.cpt
+
+all: $(TARGET).pdf
+
+open: $(TARGET).pdf
+	open $(TARGET).pdf
+
+remake:
+	make clean
+	make all

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/abst.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,6 @@
+\begin{abstract}
+プログラムからデータを分離してRDBとして扱う手法には、プログラム中のデータ構造とRDBの表構造がマッチしないという問題が知られており、データベース自体もRDBと方向の違う表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
+今回提案する木構造データベースJungleはプログラム内部に直接木構造を構築し、そのルートをアトミックに入れ替えることでトランザクションを実現する。
+また木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取る。プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。Jungleは分散構成も可能である。
+本論文ではJungleデータベースの構造とこれを用いたアプリケーション、実装時に発生した問題と解決方法について解説する。
+\end{abstract}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/application.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,2 @@
+\section{Jungle上に実装したアプリケーション}
+本章では実際にJungleを使用した例題アプリケーションの実装、その際に発生した問題とその解決方法について記述する。

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bbs.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,1 @@
+bbsについて書く

Binary file images/.DS_Store has changed

Binary file images/TreePersonJungle.pdf has changed

Binary file images/mongoJungleperfomance.pdf has changed

Binary file images/transactionPersecond.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/introduction.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,8 @@
+\section{研究目的と背景}
+プログラムからデータを分離してRDBとして扱う手法には、プログラム中のデータ構造とRDBの表構造がマッチしないという問題が知られている。
+例えばRPGゲーム中のユーザが持つアイテムという単純なものでもRDBではユーザとアイテムの組をキーとする巨大な表として管理することになり、ユーザオブジェクトが持つアイテムリストというプログラムの中のデータ構造とのギャップが大きい。
+Mapなどの手法や持続的データ構造などの研究が行われてきたが解決には至っていない。一方でデータベース自体もRDBと方向の違う表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
+当研究室では、こ れらの問題を解決した煩雑なデータ設計が必要のない データベースを目指して非破壊的木構造データベースJungleを開発している。
+Jungleはプログラム内部に直接木構造を構築し、そのルートをアトミックに入れ替えることでトランザクションを実現する。
+また木構造の表現に単一リンクを用い、変更を非破壊的つまり、元の木を保存しつつ、新しい木を構築する方法を取る。プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。Jungleは分散構成も可能である。
+本研究では実際にJungle上に実際に複数のアプリケーションを実装し、Jungleの表現力、機能の十分性、実用的な性能があるか、実証実験を行う。

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jungle.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,7 @@
+\section{非破壊的木構造データベースJungle}
+\subsection{Jungleのデータ構造}
+Jungleは複数の木の集合からなり木は複数のノードの集合で出来ている。
+ノードは自身の子のListと属性名と属性値の組を持つ。
+Jungleは非破壊的木構造であるためデータの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う。
+そのため、読み込みと書き込みを同時に行うことができる。
+他にも本研究室で開発を行っている分散フレームワークAliceを用いて作られた分散木構造データベースJungle。Unityに対応したC\#版Jungleもある。

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/maTrix.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,120 @@
+\section{許認可管理アプリケーション\\maTrix}
+maTrixは、人、役職、役割、権限、組織等の木構造のデータとポリシーファイルを持つ。maTrixの組織構造はデータ同士がidを用いた参照を行うことで表現される。また組織構造は版管理されている。
+ポリシーファイルは、データに対するアクセス要求が許可されるか否認されるかを判断するためのルールを誰が(Target)、何を(Resource)、どうできるか(Action)の3つの要素で記述されている。maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う。
+ポリシーファイルは組織構造中の人や役職をidを用いて参照している。つまり、ポリシーファイルを用いて許認可を下すためには、その人がどこの組織に所属して。その役割がどの権限を持っているかを返す検索が必要になる。
+本章ではmaTrixをJungle上に実装する際の問題点、解法について記述する。
+
+\subsection{Jungle上でのmaTrixデータ構造の表現}
+maTrixの人、組織、役割、権限等のデータ構造は木構造なので、Jungleの木構造にそのままマッピングできる。
+実際のmaTrixのデータ構造の一部を格納したJungleTree(図\ref{fig:PersonTree})を以下に記す。
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[height = 7cm , bb=0 0 398 367]{images/TreePersonJungle.pdf}
+\caption{Jungle上での人物Treeの表現例(1)}
+\label{fig:PersonTree}
+\end{center}
+\end{figure}
+
+また、maTrixは自身のデータをXML形式で書き出すことが可能である。書き出したデータをJungleに格納するためにXMLReaderの実装も行った。
+
+\subsection{Indexの実装}
+Jungle上でのmaTrixの組織構造の表現はIdを用いたIndexの参照を用いて表現する。
+しかし、JungleにはIndexが無かったため実装を行った。
+Jungleは過去の版のデータを全て保持しているため、全ての版に独立したIndexが必要となる。
+そのため、Indexを破壊すること無く更新する必要があったため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
+このTreeMapは、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
+これにより複数の版全てに対応したIndexをサポートすることが可能になった。
+以下にJungleにおけるIndexの型を記述する
+
+\begin{verbatim}
+TreeMap<String key,TreeMap<String attribute,
+  List<TreeNode> node> index> indexMap
+\end{verbatim}
+
+JungleのIndexはIndexMap内に保持されている。
+属性名でIndexMapにgetを行うと、対応したIndexが取得できる。
+その取得したIndexに属性値で検索を行うと対応したノードのリストが返ってくる。
+
+
+\subsection{検索APIの実装}
+Indexを実装したことにより、Idを用いた組織構造の表現は可能になった。
+しかし、組織構造に対する問い合わせを行うための検索APIが実装されていなかったため、属性名:属性値で検索を行うAPIの実装をlambda式を用いて行った。
+以下に検索を行う関数findの定義を記述する。
+\begin{lstlisting}[frame=lrbt,label=query,numbers=left]
+public Iterator<TreeNode> find(Query query, 
+               String key, String searchValue);
+\end{lstlisting}
+
+find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。
+第1引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterface Queryを。
+第2、第3引数の、String key、String valueはIndexを用いた絞込みに使用する。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("Personid");
+    if (personId == null)
+      return false;
+    if (personId.equals("p:4"))
+      return true;
+    return false;
+    }, "element", "person");
+\end{lstlisting}
+
+上記コードについて解説する。
+\begin{enumerate}
+\item Treeの走破を行うTraverserを取得する。
+
+\item Indexからfindの第2、第3引数である、element、personの組のデータを持つNodeを取得する。
+
+\item 2で取得したNodeを第1引数のQueryに渡す(以下Query内の解説
+
+\item 引数のノードからgetAttributes().getString("Personid")で属性名がPersonidの属性値を取得する。
+
+\item 属性値がnullだった場合、このNodeには属性名がPersonidの組のデータは存在しないのでfalseを返し次のNodeの評価を行う。
+
+\item 属性値がnullでなかった場合、p:4と一致するかどうかを調べ結果を返す。
+
+\end{enumerate}
+
+findはQueryと条件が一致したNodeのIteratorを返す。
+
+\subsection{Nodeの親をたどるIndex}
+maTrixがJungleに検索を行う際に親をたどる処理が必要になったが、Jungleは親から子への単一リンクしか持っていなかった。
+しかし、Jungleは非破壊という性質上、子に親への参照をもたせることが難しいため、Nodeを渡すと親Nodeを返すParentIndexを実装した。
+
+
+\if0
+\subsubsection{性能測定}
+maTrixの実装後、性能測定を行った。
+図\ref{fig:compare}はmongoDBとJungleの速度比較のグラフである。
+比較は10000人分のデータに対するアクセスの処理時間で行い、mongoDBへのアクセスはjsを用いて行った。
+\begin{figure}[h]
+\begin{center}
+\includegraphics[height = 5cm , bb=0 0 360 252]{images/mongoJungleperfomance.pdf}
+\caption{mongoDBとの比較}
+\label{fig:compare}
+\end{center}
+\end{figure}
+
+Jungleは、mongodbの約500倍の性能が出ている。
+その理由として、mongoDBがmmapを用いてディスクのデータにアクセスしているのに対し、Jungleは全てのデータがメモリ上にあること。
+また、mongoDBは通信を介してアクセスされるが、Jungleは通信を介さないためだと考えられる。
+
+
+図\ref{fig:transactionPersecond}は、Jungleの書き込みが、どれだけ読み込みに影響があるかを測定したグラフである。
+複数スレッドからJungleに読み込みだけを行った場合と、1スレッドだけ書き込みを行い、残りのスレッドで読み込み行った場合で測定を行った。
+\begin{figure}[h]
+\begin{center}
+\includegraphics[height = 5cm , bb=0 0 360 252]{images/transactionPersecond.pdf}
+\caption{TransactionPerSecond}
+\label{fig:transactionPersecond}
+\end{center}
+\end{figure}
+
+Jungleでは書き込みと読み込みを同時に行っても性能低下はおこらなかったため、設計通りの性能が出たといえる。
+\fi

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,80 @@
+% withpage: ページ番号をつける (著者確認用)
+  % english: 英語原稿用フォーマット
+  \documentclass{ipsjprosym}
+  %\documentclass[withpage,english]{ipsjprosym}
+  \usepackage{listings,jlisting}
+  \usepackage[dvips]{graphicx}
+  \usepackage{latexsym}
+  \usepackage{comment}
+  \lstset{%
+    language={Java},
+      basicstyle={\footnotesize},%
+        identifierstyle={\footnotesize},%
+        commentstyle={\footnotesize\itshape},%
+        keywordstyle={\footnotesize\bfseries},%
+        ndkeywordstyle={\footnotesize},%
+        stringstyle={\footnotesize\ttfamily},
+      frame={tb},
+      breaklines=true,
+      columns=[l]{fullflexible},%
+        numbers=left,%
+        xrightmargin=0zw,%
+        xleftmargin=1zw,%
+        numberstyle={\scriptsize},%
+        stepnumber=1,
+      numbersep=0.5zw,%
+        lineskip=-0.5ex%
+  }
+
+\begin{document}
+
+% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\title{ソフトウェア内部で使用するのに適した\\木構造データベースJungle}
+
+\affiliate{IPSJ}{情報処理学会}
+\affiliate{PROSYM}{プログラミング・シンポジウム幹事団}
+
+\author{金川 竜己}{Kanagawa Tatsuki}{IPSJ}[k158585@ie.u-ryukyu.ac.jp]
+\author{プロシン 花子}{Hiroki MIZUNO}{PROSYM}[hanako@prosym.ipsj.or.jp]
+
+% はじめに
+\input{abst.tex}
+
+\begin{jkeyword}
+\end{jkeyword}
+
+\maketitle
+
+% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% 研究目的
+\input{introduction.tex}
+
+% 非破壊的木構造データベースJungle
+\input{jungle.tex}
+
+% Jungle上に実装したアプリケーションの説明
+%\input{application.tex}
+
+%BBSについて
+\input{bbs.tex}
+
+%許認可管理アプリケーションmaTrix
+\input{maTrix.tex}
+
+%Jungle RenderingEngine
+\input{renderingEngine.tex}
+\begin{acknowledgment}
+謝辞が必要であれば，ここに書く．
+\end{acknowledgment}
+
+% BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \bibliographystyle{ipsjsort}
+% \bibliography{ref}
+
+% BibTeX を使用しない場合
+\begin{thebibliography}{9}
+\bibitem{latex} 奥村晴彦, 黒木裕介: \textbf{LaTeX2e美文書作成入門}. 技術評論社, 2013.
+\end{thebibliography}
+
+\end{document}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/renderingEngine.tex	Wed Nov 09 10:05:42 2016 +0900
@@ -0,0 +1,6 @@
+\section{HtmlRenderingEngine}
+HtmlRenderingEngineは、htmlとして出力するデータが記述されたContextTree、どのように出力するか記述されたLayoutTreeの２つの木構造を持つ。
+Renderingを行う際には、LayoutTreeのNodeを順番に参照し、それに対応した出力データをContextTreeから取得する。
+その後、出力部分が確定次第出力していく。
+
+\subsection{Jungle上でのLayoutTreeの}