\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage[dviout]{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{135768k 武田和馬 {}{} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy} 

\section{非破壊木構造データベース}

当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。
Jungle DBの有効性を示すために、 本研究では検索API、Index、過去データの参照の実装を行う。
Jungleが実用DBとしての性能を持っているかどうかを調べるために、アカウント管理システムmaTrixへ組み込み、評価を行う。

Jugnleの木は、子供を複数持つノード(*図1)からなる。子供は順序付けられており、任意の位置で作成削除することができる。
ノードには属性名と属性値の組があり、データベースのレコードとして使うことができる。Index は、このレコードの属性に
対して作成する。任意の木で、属性値に対応する複数のノード、そして必要ならば、そこまでのパスの組を返す。
ここでパスとは、ルートから木をたどるのに必要な各ノードの子供の番号のリストである。
\\
\\
\\
\\
\begin{figure}[h]
\includegraphics[width=2cm, bb=0 0 172 200]{node.pdf}
\end{figure}
\\\\\\
Unityはゲーム
% ので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。
% これらは、XMLで記述されており、
% maTrixが保持している人、役職、役割等のデータはお互いに参照している。
% ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。
% 組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。

\section{maTrixに必要なデータベースの構築}

組織構造は木構造なので Jungle の木構造にそのままマッピングできる。Persons, Organiations, RoleDescription の三つの木を一つのJungleの木として格納する。
XACMLは、XMLなので木構造を持つ。XACMLは、組織構造中の人や役職を id として参照する。
具体的な許諾では、 例えば、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。
XML形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。

\section{検索APIの設計と実装}

図2は組織構造木から、key:valueの組が、"element":"Person"のデータの組み合わせを持ったNodeと、そのNodeまでのPathのPairのiteratorを返すQueryのAPIの例を示している。
\verb+(TreeNode node) -> {}+ は、引数\verb+node+を持つ Java 8 のλ式である。

{\scriptsize
 \begin{itembox}[l]{図2 Sample 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}
}\\

\verb+find+は引数に\verb+Query+、\verb+String key+、\verb+String value+の3つを取る。\verb+key+ はIndexの対象となる属性名である。

Queryは図3で定義されたinterfaceである。実行されるQuery は ノードを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数が定義されている必要がある。
{\scriptsize
  \begin{itembox}[l]{図3 Query interface}
  \begin{verbatim}
  public interface Query {
    boolean condition(TreeNode node);
  }
  \end{verbatim}
  \label{interface}
  \end{itembox}
}\\

\section{Indexの実装}
Jungleの探索はTreeの全探索の計算量はO(n)である。
Indexの実装には、functionalJavaのTreeMapを使用し、計算量はO(logN)となる。
これにより、前の版の木のIndexの最大共有するこが可能であり、複数の木の版すべてに対するIndexをサポートすることが可能になる。
Jungle DB は分散DBなので、 on-th-fly つまり必要になったDBノード毎に作成する。

\newpage
{\scriptsize
  \begin{itembox}[l]{図4 Indexの型} 
  \begin{verbatim}
TreeMap<String, TreeMap
      <String, List<Pair<TreeNode, NodePath>>>> index;
\end{verbatim}
  \end{itembox}
}\\
図4にはJungleDBにおけるIndexの型を記述した
Jungleでは、木の編集や、特定のNode下のTreeの探索、Nodeの親をたどるためには全てそのNodeへのPathが必要になる、ため、IndexにもそのNodeまでのPathが必要になる。そのため、IndexのNodePathが大きなボトルネックとなっている。

JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、子ノードのadd、delete、属性のput、deleteを行う。
Treeに対して変更を加える時にIndexも更新も行う。

Jungleの木の更新(commit)は、CAS(check and set*図5)を用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。IndexはCASの前に作成され
元の木と同時に更新される。
\\
\\
\\
\\
\\
\\
\begin{figure}[h]
\includegraphics[width=2cm, bb=0 0 172 200]{cas.pdf}
\end{figure}

Indexの更新は変更で影響を受けるすべてのノードに対して行う必要がある。ノードそのものが変更されなくても、パスが影響を受ける場合には、そのノードも更新する必要がある。(*図6)
\\
\\
\\
\\
\begin{figure}[h]
\includegraphics[width=2cm, bb=0 0 160 200]{path.pdf}
\end{figure}



\newpage
\section{特定のNode下のTreeに対するIndexを用いた検索}

特定のノードの下のTreeに対する検索は、比較対象のパスを使って、自分のパス比較すれば良い。Index を使用して対象を絞ってから比較を行う。
ノードの下の木が小さいことが予測される場合は、Indexを使用しないほうが良い性能が得られる場合もある。

\section{これからの作業}

実際にmaTrixとJungleの接続を行い、既存のmaTrixとJunglemaTrixの性能を評価する。

Jungleは、過去のversionのTreeを保持しているので、
過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。

JungleはRDBと異なり木構造のデータを自由に格納することができる。それゆえ木構造の設計の自由度は大きい。
しかし、変更は木が大きいほどルートに集中してしまう。木の分割を行うと、分割した木の間の同期は version 
を介して行う間接的なものとなる。なので、JungleDBの設計手法を確立させる必要がある。

本研究は、PCIホールディングス株式会社と株式会社Symphonyとの共同研究である。

\begin{thebibliography}{9}

\bibitem{1}
玉城将士 非破壊的木構造を用いた分散CMSの設計と実装
\bibitem{2}
大城信康 分散Database Jungleに関する研究
\end{thebibliography}

\end{document}