\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{ascmac}
\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のデータを参照を行えなかったり、木構造のデータ型を入れる際に面倒だったり、問題がある。\\
そこで、当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用いたデータベースであるJungleを開発している。\\
Jungleは非破壊で過去のデータを変更しないので、過去のデータを簡単に参照できたり、Jungle自体が木構造データベースなので、木構造のデータをそのまま格納出来る。\\
本研究ではJungleに、検索API、Index、過去データの参照の実装を行い、
その後、当研究室と共同研究を行っているSymphonies社が開発しているアカウント管理システムmaTrixにJungleを組み込む。

\section{maTrix}
maTrixとはSymphonies社が開発しているアカウント管理、許諾判定システムのことである。\\
matrixは人、役職、役割、権限と言った木構造の組織、ポリシーファイルの２つのデータを持っている。maTrixが保持している人、役職、役割等のデータはお互いに参照している。
ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。\\
組織のデータ、ポリシーファイル共に木構造のデータであるため、木構造のデータベースであるJungleには、そのまま格納できる。\\
また、maTrixは、いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持するので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。\\
maTrixはデータをxml形式で出力することが可能なので、xml形式で出力されたmaTrixの人、組織等のデータをJungleに格納するために、SAXを用いて、Jungle用のxmlReaderを作成した。xmlReaderを作成したことにより、実際にmaTrixから出力されたデータをJungleに取り込み、本格的なテストが行えるようになった。

\section{検索APIの実装}
Jungleは、データを格納するAPIは実装されていたが、データの検索を行うAPIの実装は行われていなかった。\\
本研究ではJava8の新機能であるlambda式を用いてデータの検索を行うfind関数の実装を行った。\\
以下にfind関数の使い方を示したソースコードを記述する。\\

{\scriptsize
 \begin{itembox}[l]{JungleのQuery部分のソースコード}
\begin{verbatim}
Iterator<Pair<TreeNode, NodePath>> pairPersonIterator = 
                          traverser.find((TreeNode node) -> {
  String element = node.getAttributes().getString("element");
  if (element == null)
    return false;
  if (element.equals("Person"))
    return true;
  return false;
}, "element", "Person");
\end{verbatim}
\end{itembox}
}\\
find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeと、そのNodeまでのPathを１つにまとめたPairのIteratorを返す。\\
第一引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterface　Queryを。
第二、第三引数の、String key、String valueは後述するIndexを使うために使用する。\\
{\scriptsize
\begin{itembox}[l]{Interface Queryの定義}
\begin{verbatim}
public interface Query {
    boolean condition(TreeNode node);
}
\end{verbatim}
\end{itembox}
}\\
find関数の処理の流れは、まず初めに、Indexがあるかどうかを調べる、indexがある場合はIndexを使用し探索を行う。Indexがない場合は、Indexを作成しながらTreeを全探索する。\\
上記のJungleのQuery部分のソースコードは、"Person"というデータを持ったNodeと、そのNodeまでのPathのPairのiteratorを返す。\
検索APIは、他に特定のNode以下に対して検索を行うfindInSubTree(Query,node,key,value)も実装した。

\section{Indexの実装}
Jungleの探索はTreeを全探索するので、探索の計算量はO(n)となり、非常に効率が悪い。しかし、Indexを使用することで効率よく探索を行えるようになる。Indexの実装には、functionalJavaのTreeMapを使用した。\\
TreeMapは、KeyとValueのペアを用いて赤黒木を構築する。赤黒木の長所として、ソート済み二分木の探索なので計算量がO(logN)であること、データ編集時の最悪計算量がデータ構造のうちで最善のものの１つであるので、安定した速度でデータの編集が行える。また、TreeMapはimmutableなので一度作られたTreeに対して更新が行われない、つまり新しい要素を追加した際は、新しくTreeMapを作る。なのでTreeは、各versionごとに固定のIndexを持つことが出来る、また、新しくTreeを作る際に、過去のTreeの一部を再利用するのでメモリの使用量を抑えることが出来る、ということがあげられる。\\
Indexは各ユーザーがローカルにIndexを持つon the fly形式で実装する。\\


    \begin{itembox}[l]{Indexのデータの型}
 {\scriptsize\begin{verbatim} TreeMap<String key,
            TreeMap<String value,List<Pair<TreeNode,NodePath>>>>\end{verbatim}}\\\\
    \end{itembox}
    最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapである。
    このTreeMapに対しkeyでgetを行うと、keyに対応するIndexが登録されている場合、Indexを取得できる。
    取得したIndexに対しvalueでgetを行うと、valueの値を持つNodeと、そのNodeまでのPathの２つをPairにまとめたListが返ってくる。\\
    \\
  IndexのUpdate\\
  Indexの更新はIndexEditorを用いて行う。\\
  JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、Nodeのadd、delete、値のput、deleteを行う。Treeに対して変更を加えると、それに伴い、Indexも更新する必要が出てくる。そこでJungleTreeEditorの機能を拡張し、IndexJungleTreeEditorを作成した。\\
  IndexJungleTreeEditorでは、Treeの更新と同時にIndexEditorを用いてIndexの更新も行い、Treeに対して両方の更新をCommitする。
  \begin{itembox}[l]{IndexEditorの定義}
{\scriptsize\begin{verbatim}
public interface IndexEditor {
    Either<Error, IndexJungleTreeEditor> 
        edit(TreeNode root,TransactionManager txManager, 
        TreeEditor editor,TreeOperationLog log,
        TreeMap<String, TreeMap<String, 
        List<Pair<TreeNode,  NodePath>>>> index);
}
  \end{verbatim}}\\\\
    \end{itembox}
    \\


    \section{maTrixに必要なQueryの作成}
    maTrixは、許諾判定を行う際に、組織構造に対してQueryを行う。
    maTrixとJungleの接続を行うにあたり、組織構造に対するQueryは必要不可欠である。\\
    当研究ではmaTrixにJungleを接続するのに必要なQuery15個を完成させた。maTrixのQueryを実装するにあたって、問題となったのが、特定のNodeの子供に対してのindexを使った検索である。
    Indexには、Tree全体のデータが入っているのでIndexを使用した検索は必然的にTree全体に対する検索になる。\\
    この問題は、NodePathに、関数compare()を実装し解決した。
    関数compareは引数に比較対象のNodePathを受け取り、そのPathが自分の下にあるかどうかを調べる関数である。\\
    compareを使用することにより、特定のNode下の探索を行う際、特定のNodeのPathとIndexで取ってきた結果に対し、compareを使い、フィルタリングを行うことで、Indexを用いた特定のNode下の探索を可能にした\\
{\scriptsize
  \begin{itembox}[l]{今回追加実装したcompareの定義}
  \begin{verbatim}
  public boolean compare(NodePath path);
  \end{verbatim}
  \end{itembox}
}\\
    \section{これから行うべきこと}
    性能評価\\
      IndexとmaTrixのQueryの実装が終わり、maTrixに接続する準備が整ったので、実際にmaTrixとJungleの接続を行い、既存のmaTrixとjunglemaTrixの性能を評価し、本当に早くなったのか確かめる。この時にIndexの性能も評価する。\\
      \\
      過去のversionの参照APIの実装\\
      Jungleは、過去のversionのTreeを保持しているので、簡単に参照できるはずである。
      過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。
\\
\\
Jungleの設計手法の確立\\
Jungleは比較的自由にデータを格納することができるので、Jungleを実際に使用する際に、どこまでを一つの木として扱うか、等をまとめたJungleDBの設計手法を確立させる必要がある。\\

      \begin{thebibliography}{9}

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

      \end{document}