Mercurial > hg > Papers > 2014 > tatsuki-midterm

changeset 4:75e8aac9a4b5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ver 3.0
author tatsuki
date Wed, 29 Oct 2014 20:05:42 +0900
parents 12e1cf2e9166
children 0fc8736218d4
files midterm.pdf midterm.tex
diffstat 2 files changed, 49 insertions(+), 73 deletions(-) [+]
line wrap: on
line diff
Binary file midterm.pdf has changed
--- a/midterm.tex	Wed Oct 29 13:53:28 2014 +0900
+++ b/midterm.tex	Wed Oct 29 20:05:42 2014 +0900
@@ -16,7 +16,7 @@
 \setlength{\textwidth}{181mm}
 \setlength{\textheight}{261mm}
 \setlength{\footskip}{0mm}
-\pagestyle{empty}
+\pagestyle{\empty}
 
 \begin{document}
 \title{Database Jungleに関する研究}
@@ -27,34 +27,33 @@
 
 \section{研究目的}
 
-当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用い>
-たデータベースであるJungleを開発している。
+当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用いたデータベースであるJungleを開発している。
 
 
-業務システムでアカウント管理を行う際に既存のDatabaseでは、木構造のデータ型を入れる処理の煩雑さや、過去のversionにおけるデータの参照が出来ないと言った問題がある。
+本研究ではJungleに、検索API、Index、過去データの参照の実装を行う。
+その後、Jungleが実用DBとしての性能を持っているかどうかを調べるために、当研究室と共同研究を行っているSymphonies社が開発した、アカウント管理シ
+ステムmaTrixにJungleを組み込む。
 
-
-Jungleは非破壊で過去のデータを変更しないので、過去のデータを参照することができる。Jungleは木構造のデータベースなので、木構造のデータをそのまま格納出来る。
+\section{maTrix}
+maTrixとはSymphonies社が開発した、アカウント管理、許諾判定システムのことである。
 
 
-本研究ではJungleに、検索API、Index、過去データの参照の実装を行った。
-さらに、当研究室と共同研究を行っているSymphonies社が開発した、アカウント管理システムmaTrixにJungleを組み込む。
-
-\section{maTrix}
-maTrixとはSymphonies社が開発した、アカウント管理、許諾判定システムのことである。\\
-maTrixは人、役職、役割、権限と言った木構造の組織、ポリシーファイルの２つのデータを持っている。maTrixが保持している人、役職、役割等のデータはお互いに参照している。
-ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。\\
-組織のデータ、ポリシーファイル共に木構造のデータであるため、木構造のデータベースであるJungleには、そのまま格納できる。\\
-また、maTrixは、いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持するので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。\\
-maTrixはデータをxml形式で出力することが出来る。
+maTrixは人、役職、役割、権限と言った木構造の組織、ポリシーファイルの２つのデータを持っており、maTrixが保持している人、役職、役割等のデータはお互いに参照している。
+ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。
 
 
+組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。
+
+
+また、maTrixは、いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持するので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。
+
+
+maTrixはデータをxml形式で出力することが出来る。
 xml形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のxmlReaderを作成した。xmlReaderを作成したことにより、実際にmaTrixから出力されたデータをJungleに取り込み、テストを行うことを可能にした。
 
 \section{検索APIの実装}
-Java8の新機能であるlambda式を用いてデータの検索を行うfind関数の実装を行った。\\
-図1にfind関数の使い方を示したソースコードを記述する。\\
-
+Jungleに対し、Treeに対して検索を行うMethod findを実装した。図1は実際にfindを行っているコードである。Treeを探索し、key:valueの組が、"element":"Person"のデータの組み合わせを持ったNodeと、そのNodeまで>のPathのPairのiteratorを返している。
+図1の引数のQueryはlambda式を用いて実装している。
 {\scriptsize
  \begin{itembox}[l]{図1}
 \begin{verbatim}
@@ -70,17 +69,11 @@
 \end{verbatim}
 \end{itembox}
 }\\
-find関数は引数にQuery、String key、String valueの3つを取る。条件に一致したNodeと、そのNodeまでのPathを１つにまとめたPairのIteratorを返す。\\
+
+findは引数にQuery、String key、String valueの3つを取る。
+Queryはinterfaceで、図2にあるようにNodeを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数を定義してある。
 
 
-  \begin{table}
-  \begin{tabular}{|l|c|r|}\hline 
-  引数 & 関数での使われ方   \\\hline 
-    Query & 探索の条件を記述したInterface(図2)   \\\hline 
-    Key & 後述するIndexを使うために使用する  \\\hline 
-    value & 後述するIndexを使うために使用する   \\\hline 
-    \end{tabular}
-    \end{table}
 
 
 
@@ -93,58 +86,41 @@
   \end{verbatim}
   \end{itembox}
 }\\
-    find関数は、まず初めに、Indexがあるかどうかを調べる。indexがある場合はIndexを使用し探索を行う。Indexがない場合は、Indexを作成しながらTreeを全探索する。\\
-    図1のJungleのQuery部分のソースコードは、"Person"というデータを持ったNodeと、そのNodeまでのPathのPairのiteratorを返す。\
-    検索APIは、他に特定のNode以下に対して検索を行うfindInSubTree(Query,node,key,value)も実装した。
+
+検索APIは、他に特定のNode以下に対して検索を行うfindInSubTree(Query,node,key,value)も実装した。
 
-    \section{Indexの実装}
-    Jungleの探索はTreeを全探索するので、探索の計算量はO(n)となり、非常に効率が悪い。そこで、Indexを使用することで、探索効率の向上を計った。Indexの実装には、functionalJavaのTreeMapを使用した。\\
-      TreeMapは、KeyとValueのペアを用いて赤黒木を構築する。赤黒木は、ソート済み二分木の探索なので計算量がO(logN)である。さらにデータ編集時の最悪計算量が、他の木構造と比べ最善のものの１つであるので、安定した速度でデータの編集が行える。また、FunctionalJavaのTreeMapはimmutableなので一度作られたTreeに対して更新が行われない。つまり新しい要素を追加する際は、新しくTreeMapを作ることになる。なのでTreeは、各versionごとに固定のIndexを持つことが出来る。また、新しくTreeを作る際に、過去のTreeの一部を再利用するのでメモリの使用量を抑えることが出来る。
-
-
-      Indexは各ユーザーがローカルにIndexを持つon the fly形式で実装する。\\
+\section{Indexの実装}
+Jungleの探索はTreeを全探索するので、探索の計算量はO(n)となり効率が悪い。そこで、Indexを使用することで、探索効率の向上を計った。Indexの実装には、functionalJavaのTreeMapを使用したので、Indexを使用した検索の計算量はO(logN)となる\\
+FunctionalJavaのTreeMapはimmutableなので一度作られたTreeに対して更新が行われない。つまり新しい要素を追加する際は、新しくTreeMapを作ることになるが、新しいTreeを作るときに、過去のTreeの一部を再利用するのでメモリの使用量を抑えることが出来る。
 
 
-      \begin{itembox}[l]{図3}
-{\scriptsize\begin{verbatim} TreeMap<String key,
-  TreeMap<String value,List<Pair<TreeNode,NodePath>>>>\end{verbatim}}\\\\
-    \end{itembox}
-    図3はIndexの型である。
-
-
-    最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapで、
-    このTreeMapに対しkeyでgetを行うと、keyに対応するIndexを取得できる。
-    取得したIndexに対し、valueでgetを行うと、valueの値を持つNodeと、そのNodeまでのPathの２つをPairのListが返ってくる。\\
-      %もう少しわかりやすく
+Indexは各ユーザーがローカルにIndexを持つon the fly形式で実装する。
 
 
-      \section{IndexJungleTreeEditorの実装}\\
-        Indexの更新はIndexEditorを用いて行う。図4にIndexEditorの定義を記述する\\
-        IndexEditorのeditはIndexの更新を行い、Index更新後のIndexJungleTreeEditorを返す。
-        JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、Nodeのadd、delete、値のput、deleteを行う。Treeに対して変更を加えると、それに伴い、Indexも更新する必要が出てくる。そこでJungleTreeEditorの機能を拡張し、IndexJungleTreeEditorを作成した。\\
-        IndexJungleTreeEditorでは、Treeの更新と同時にIndexEditorを用いてIndexの更新も行い、Treeに対して両方の更新をCommitする。
-        \begin{itembox}[l]{図4}
-{\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}
-    \\
+{\scriptsize
+  \begin{itembox}[l]{図3}
+  \begin{verbatim}
+TreeMap<String, TreeMap
+      <String, List<Pair<TreeNode, NodePath>>>> index;
+\end{verbatim}
+  \end{itembox}
+}\\
+図3にはJungleDBにおけるIndexの型を記述した\\
+Jungleでは、木の編集や、特定のNode下のTreeの探索、Nodeの親をたどるためには全てそのNodeへのPathが必要になる、ため、IndexにもそのNodeまでのPathが必要になる。そのため、IndexのNodePathが大きなボトルネックとなっている。
 
 
-    \section{maTrixに必要なQueryの作成}
-    maTrixは、許諾判定を行う際に、組織構造に対してQueryを発行する。
-    maTrixとJungleの接続を行うにあたり、組織構造に対するQueryは必要不可欠である。\\
-      maTrixにJungleを接続するのに必要なQuery実装した。maTrixのQueryを実装する際に、問題となったのが、特定のNodeの以下のTreeに対して、indexを使った検索である。
-      Indexには、Tree全体のデータが入っているので、Indexを使用した検索は必然的にTree全体に対する検索になってしまう。\\
-        この問題は、NodePathに、関数compare()を実装し解決した。compareの定義を図5に示す。
-        関数compareは引数に比較対象のNodePathを受け取り、そのPathが自分の下にあるかどうかを調べる関数である。\\
-          compareを使用することにより、特定のNode下の探索を行う際、特定のNodeのPathとIndexで取ってきた結果に対し、compareを使い、フィルタリングを行うことで、Indexを用いた特定のNode下の探索を可能にした。\\
+
+
+
+  \section{IndexJungleTreeEditorの実装}
+    JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、Nodeのadd、delete、値のput、deleteを行う。Treeに対して変更を加えると、それに伴い、Indexも更新する必要が出てくる。そこでJungleTreeEditorの機能を拡張し、IndexJungleTreeEditorを作成した。\\
+    IndexJungleTreeEditorでは、Treeの更新と同時にIndexEditorを用いてIndexの更新も行い、Treeに対して両方の更新をCommitする。この時値のPut、deleteは、Indexから対応するKey,valueを持つIndexを更新すれば良い。しかし、Nodeのadd、deleteは、行うとTreeNodeのPathがズレてしまうため、全てのIndexの全ての値を調べ、PathがずれているIndexを全て修正する必要がある。
+
+\section{特定のNode下のTreeに対するIndexを用いた検索}
+      Indexを用いた検索を行う際に問題になったのが、特定のNodeの下のTreeに対して検索を行う際に、Indexが使えない問題が発生した。
+      なぜなら、Indexには、Tree全体のデータが入っているので、Indexを使用した検索は必然的にTree全体に対する検索になってしまう。\\
+        この問題は、NodePathに、引数に比較対象のNodePathを受け取り、そのPathが自分の下にあるかどうかを調べる関数Compareを実装することで解決した。\\
+          compareを使用することにより、特定のNode下の探索を行う際、Indexで取ってきた結果に対し、compareを使い、フィルタリングを行うことで、Indexを用いた特定のNode下の探索を可能にした。\\
 {\scriptsize
   \begin{itembox}[l]{図5}
   \begin{verbatim}