Binary file cas.pdf has changed

Binary file midterm.pdf has changed

--- a/midterm.tex	Wed Oct 29 21:13:48 2014 +0900
+++ b/midterm.tex	Thu Oct 30 02:58:41 2014 +0900
@@ -1,5 +1,6 @@
 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
 \usepackage[dvips]{graphicx}
+\usepackage[dviout]{graphicx}
 \usepackage[dvipdfm]{graphicx}
 \usepackage{ascmac}
 \usepackage{fancyhdr}
@@ -29,13 +30,20 @@
 
 当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。
 Jungle DBの有効性を示すために、 本研究では検索API、Index、過去データの参照の実装を行う。
-Jungleが実用DBとしての性能を持っているかどうかを調べるために、アカウント管理システムmaTrixの実装と評価を行う。
+Jungleが実用DBとしての性能を持っているかどうかを調べるために、アカウント管理システムmaTrixへ組み込み、評価を行う。
 
-Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。
+Jugnleの木は、子供を複数持つノード(*図1)からなる。子供は順序付けられており、任意の位置で作成削除することができる。
 ノードには属性名と属性値の組があり、データベースのレコードとして使うことができる。Index は、このレコードの属性に
 対して作成する。任意の木で、属性値に対応する複数のノード、そして必要ならば、そこまでのパスの組を返す。
 ここでパスとは、ルートから木をたどるのに必要な各ノードの子供の番号のリストである。
-
+\\
+\\
+\\
+\\
+\begin{figure}[h]
+\includegraphics[width=2cm, bb=0 0 172 200]{node.pdf}
+\end{figure}
+\\\\\\
 maTrixは、アカウント管理、許諾判定システムである。
 maTrixは人、役職、役割、権限と言った木構造の組織、許諾のポリシーを決めるXACMLファイルをデータベースとして持つ。
 いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持する必要がある。
@@ -48,18 +56,18 @@
 
 \section{maTrixに必要なデータベースの構築}
 
-組織構造は木構造なので Jungle の木酵素にそのままマッピングできる。Persons, Organiations, RoleDescription の三つの木を一つのJungleの木として格納する。
+組織構造は木構造なので Jungle の木構造にそのままマッピングできる。Persons, Organiations, RoleDescription の三つの木を一つのJungleの木として格納する。
 XACMLは、XMLなので木構造を持つ。XACMLは、組織構造中の人や役職を id として参照する。
 具体的な許諾では、 例えば、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。
 XML形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。
 
 \section{検索APIの設計と実装}
 
-図\ref{query}は 組織構造木から、key:valueの組が、"element":"Person"のデータの組み合わせを持ったNodeと、そのNodeまで>のPathのPairのiteratorを返すQueryのAPIの例を示している。
+図2は組織構造木から、key:valueの組が、"element":"Person"のデータの組み合わせを持ったNodeと、そのNodeまでのPathのPairのiteratorを返すQueryのAPIの例を示している。
 \verb+(TreeNode node) -> {}+ は、引数\verb+node+を持つ Java 8 のλ式である。
 
 {\scriptsize
- \begin{itembox}[l]{Sample Query}
+ \begin{itembox}[l]{図2 Sample Query}
 \begin{verbatim}
 Iterator<Pair<TreeNode, NodePath>> pairPersonIterator = 
                           traverser.find((TreeNode node) -> {
@@ -71,15 +79,14 @@
   return false;
 }, "element", "Person");
 \end{verbatim}
-\label{query1}
 \end{itembox}
 }\\
 
 \verb+find+は引数に\verb+Query+、\verb+String key+、\verb+String value+の3つを取る。\verb+key+ はIndexの対象となる属性名である。
 
-Queryは図\ref{interface}で定義されたinterfaceである。実行されるQuery は ノードを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数が定義されている必要がある。
+Queryは図3で定義されたinterfaceである。実行されるQuery は ノードを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数が定義されている必要がある。
 {\scriptsize
-  \begin{itembox}[l]{Query interface}
+  \begin{itembox}[l]{図3 Query interface}
   \begin{verbatim}
   public interface Query {
     boolean condition(TreeNode node);
@@ -95,29 +102,51 @@
 これにより、前の版の木のIndexの最大共有するこが可能であり、複数の木の版すべてに対するIndexをサポートすることが可能になる。
 Jungle DB は分散DBなので、 on-th-fly つまり必要になったDBノード毎に作成する。
 
+\newpage
 {\scriptsize
-  \begin{itembox}[l]{図3}
+  \begin{itembox}[l]{図4 Indexの型} 
   \begin{verbatim}
 TreeMap<String, TreeMap
       <String, List<Pair<TreeNode, NodePath>>>> index;
 \end{verbatim}
   \end{itembox}
 }\\
-図3にはJungleDBにおけるIndexの型を記述した
+図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)を用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。IndexはCASの前に作成され
-元の木と同時に更新される。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{これから作業}
+\section{これからの作業}
 
 実際にmaTrixとJungleの接続を行い、既存のmaTrixとJunglemaTrixの性能を評価する。
 
@@ -136,8 +165,6 @@
 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装
 \bibitem{2}
 大城信康 分散Database Jungleに関する研究
-\bibitem{3}
-Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界
 \end{thebibliography}
 
 \end{document}

Binary file node.pdf has changed

Binary file path.pdf has changed