--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/abst.tex	Tue Feb 17 12:54:31 2015 +0900
@@ -0,0 +1,179 @@
+\documentclass[twocolumn,twoside,9.5pt]{jarticle}
+\usepackage[dvips]{graphicx}
+\usepackage{ascmac}
+\usepackage{picins}
+\usepackage{fancyhdr}
+\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{分散機構造データベースJungleによる\\企業向け企業システム}
+
+\author{金川竜己  \\ 指導教員 河野真治 {} }
+\date{abst}
+\maketitle
+\thispagestyle{fancy}
+
+\section{分散木構造データベースJungle}
+当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。
+JungleのTreeは複数個の子を持つノードからなり、ノードは属性名と属性値の組のデータを保持することが可能であり、それらをデータベースのレコードとして扱う。
+当研究では、共同研究を行っているSymphonies社が開発している、組織の中の許認可を管理するアプリケーションmaTrixにJungleを組み込み、実装すべきAPIの洗い出しを行い、その後実用DBとしての性能があるか実証実験を行う。
+
+\section{組織中の許認可管理\\アプリケーションmaTrix}
+maTrixは、人、役職、役割、権限と言った木構造のデータと、許認可判断用のポリシーファイルを持つ。
+maTrixの組織構造は、データ同士がidを用いて参照を行い表現しており、version毎に版管理している。
+組織構造は木構造なので Jungleの木構造にそのままマッピングできる。
+
+また、maTrixが許認可判断に用いるポリシーファイルはXACMLファイル形式で記述されており、XACMLは、組織構造中の人や役職をidとして参照する。
+つまり、XACMLを用いて許認可の判断を下すためには、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。
+
+maTrixがXML形式で出力したデータを、Jungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。
+読み込んだXACMLTreeからデータを取り出して、Jungle上で許認可判定を行う、XACMLInterpreterの実装も行った。
+
+
+\section{検索APIの設計と実装}
+
+JungleのTreeに対して検索を行うfind関数の実装を行った。
+以下にfind関数の定義を記述する。
+
+{\scriptsize
+\begin{itembox}[l]{find関数の定義}
+\begin{verbatim}
+publicIterator<TreeNode>
+find(finalQueryquery,finalStringkey,StringsearchValue);
+\end{verbatim}
+\end{itembox}
+}
+
+find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。
+
+第一引数には以下に記載してある、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterfaceQueryを。
+第二、第三引数の、String key、String valueはIndexの取得を行うために使用する。
+
+{\scriptsize
+\begin{itembox}[l]{Queryinterface}
+\begin{verbatim}
+publicinterfaceQuery{
+  booleancondition(TreeNodenode);
+}
+\end{verbatim}
+\label{interface}
+\end{itembox}
+}
+
+
+{\scriptsize
+\begin{itembox}[l]{find Sample}
+\begin{verbatim}
+Iterator<TreeNode> pairPersonIterator=
+  traverser.find((TreeNodenode)->{
+  Stringelement=node.getAttributes().getString("element");
+  if(element==null)
+    returnfalse;
+  if(element.equals("Person"))
+    return true;
+  return false;
+},"element","Person");
+\end{verbatim}
+\label{query}
+\end{itembox}
+}
+
+実際にfind関数を使った例とコードの解説を行う。
+
+find Sampleは、第2、第3引数の"element"-"Person"を用いて、これらの値に対応したIndexが登録されているかを調べる、Indexがある場合はIndexを使用し値を返す。Indexがない場合は、Treeから深さ優先でTreeNodeを取得していく。
+
+取得したTreeNodeを引数に与え、boolean Query.condition(TreeNode)を実行し、condition中で、TreeNodeのAttributeに対してgetを行い探索対象のデータをTreeNodeが保持しているかを調べ、データを持っていた場合はTrueを、持っていなかった場合はFalseを返す
+
+conditionの返り値が、Trueだった場合、TreeNodeを返す。今までの処理をもう一度繰り返す。
+
+find関数を使用し、実際にmaTrixがデータにアクセスする際に使用する関数を全て実装した。
+
+\section{Indexの実装}
+Jungleの探索はTreeを全探索するので、探索の計算量はO(n)である。
+そこで、Indexを使用することで効率よく探索を行えるようにする。
+Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っていることが望ましい。
+そこで、メモリの消費量を抑え、各versionのTreeにIndexをもたせる方法として、FunctionalJavaのTreeMapを使用したIndexの実装を行った。
+FunctionalJavaのTreeMapは、データの更新が行われた際に、一度作られたTreeに対して更新を行わず過去のTreeを
+再利用し、更新後のTreeMap新しく返すため、メモリの使用量を抑えつつ複数のversionでIndexを保持できる。
+
+Indexの型は以下のように定義した。
+{\scriptsize
+\begin{itembox}[l]{Indexの型}
+\begin{verbatim}
+TreeMap<String key,TreeMap<String value,
+                         List<TreeNode>>>>
+\end{verbatim}
+\end{itembox}
+}
+最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapである。
+このTreeMapに対しkeyでgetを行うと、keyに対応するIndexが登録されている場合、Indexを取得でき、取得したIndexに対し
+valueでgetを行うと、valueの値を持つNodeのListが返ってくる。
+
+{\large ParentIndex}
+
+TreeNodeでgetを行うと、親Nodeを返すParentIndexを実装した。
+ParentIndexの型は、以下の様に定義した。
+{\scriptsize
+\begin{itembox}[l]{Indexの型}
+\begin{verbatim}
+TreeMap$<$TreeNode,TreeNode$>$
+\end{verbatim}
+\end{itembox}
+}
+
+ParentIndexを用いることで、TreeNodeからNodePathを取得できるようになり、Indexで取得したTreeNodeのデータ編集を行えるようになった。
+
+\section{getOldTree}
+JungleのTreeはversion毎にUNIQUEなrevisionIdを持つ。
+アクセスしたいTreeのrevisionIdを引数に取り、過去のTreeのデータの取得とrevisionIdの比較を繰り返すことで過去のTreeにアクセスする関数をgetOldTree実装した。
+以下にgetOldTreeの定義を示す。
+{\scriptsize
+\begin{itembox}[l]{Indexの型}
+\begin{verbatim}
+public Either<Error, JungleTree> getOldTree(long revision);
+\end{verbatim}
+\end{itembox}
+}
+
+\section{検索APIの測定}
+Jungleに対する検索APIの測定を行う。
+測定には、maTrixが保持しているデータにアクセスする際に用いる関数のうちの１つを使用した。
+実験の結果は図\ref{fig:isActive}となる。横軸は人物Treeにいる人の数を表しており、縦軸は探索にかかった時間を表している。
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[height=5cm , bb=0 0 360 252]{fig/isActive.pdf}
+\caption{inActiveの実行時間}
+\label{fig:isActive}
+\end{center}
+\end{figure}
+
+isActiveの実行時間は、Indexを使用しない場合は、Personの数が増えると比例して増えていくのに対し、Indexを使用するとPersonの数が増えても実行時間は変わらず、Indexを使用しない場合と比較し、極めて高速に実行できた。
+
+
+
+
+\thispagestyle{fancy}
+\begin{thebibliography}{9}
+
+\bibitem{1}
+玉城将士 非破壊的木構造を用いた分散CMSの設計と実装
+\bibitem{2}
+大城信康 分散Database Jungleに関する研究
+\bibitem{3}
+Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界
+\end{thebibliography}
+本研究は、PCIホールディングス株式会社と\\株式会社Symphonyとの共同研究である。
+\end{document}

--- a/chapter4.tex	Tue Feb 17 09:54:03 2015 +0900
+++ b/chapter4.tex	Tue Feb 17 12:54:31 2015 +0900
@@ -18,7 +18,7 @@
 
 find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。
 第一引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterfaceQueryを。
-第二、第三引数の、String key、String valueはIndexを使うために使用する。
+第二、第三引数の、String key、String valueはIndexの取得を行うために使用する。
 
 \begin{itembox}[l]{QueryInterfaceの定義}
 \begin{verbatim}
@@ -87,7 +87,7 @@
 TreeMapは、KeyとValueのペアを用いて赤黒木を構築する。
 赤黒木の長所として、ソート済み二分木の探索なので計算量がO(logN)であることがあげられる。
 
-それに加え、FunctionalJavaのTreeMapは、データの更新が行われた際に、一度作られたTreeに対して更新を行わず過去のTreeを再利用し、更新後のTreeMap新しく返すため、メモリの使用量を抑えつつ複数のversionのTreeMapを保持できる。
+それに加え、FunctionalJavaのTreeMapは、データの更新が行われた際に、一度作られたTreeに対して更新を行わず過去のTreeを再利用し、更新後のTreeMap新しく返すため、メモリの使用量を抑えつつ複数のversionでIndexを保持できる。
 
 Indexの型を以下に記す。
 \begin{itembox}[l]{Queryinterface}

--- a/chapter7.tex	Tue Feb 17 09:54:03 2015 +0900
+++ b/chapter7.tex	Tue Feb 17 12:54:31 2015 +0900
@@ -36,5 +36,4 @@
 \end{figure}
 
 isActiveの実行時間は、Indexを使用しない場合は、Personの数が増えると比例して増えていくのに対し、Indexを使用するとPersonの数が増えても実行時間は変わらなかった。
-この結果より、JungleのIndexの計算量はO(logn)であることがわかる。