# HG changeset patch # User tatsuki # Date 1414558408 -32400 # Node ID 12e1cf2e91663e77733c1eb5e750141e0752a91f # Parent 9b65d79399ff9d264ae3b8d20b89fe2aa462e87a ver2.0 diff -r 9b65d79399ff -r 12e1cf2e9166 midterm.pdf Binary file midterm.pdf has changed diff -r 9b65d79399ff -r 12e1cf2e9166 midterm.tex --- a/midterm.tex Wed Oct 29 12:23:01 2014 +0900 +++ b/midterm.tex Wed Oct 29 13:53:28 2014 +0900 @@ -26,27 +26,37 @@ \thispagestyle{fancy} \section{研究目的} -実際の業務システム等で、アカウント管理を行う際に既存のDatabaseでは、過去のversionのデータを参照を行えなかったり、木構造のデータ型を入れる際に面倒だったり、問題がある。\\ -そこで、当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用いたデータベースであるJungleを開発している。\\ -Jungleは非破壊で過去のデータを変更しないので、過去のデータを簡単に参照できたり、Jungle自体が木構造データベースなので、木構造のデータをそのまま格納出来る。\\ -本研究ではJungleに、検索API、Index、過去データの参照の実装を行い、 -その後、当研究室と共同研究を行っているSymphonies社が開発しているアカウント管理システムmaTrixにJungleを組み込む。 + +当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用い> +たデータベースであるJungleを開発している。 + + +業務システムでアカウント管理を行う際に既存のDatabaseでは、木構造のデータ型を入れる処理の煩雑さや、過去のversionにおけるデータの参照が出来ないと言った問題がある。 + + +Jungleは非破壊で過去のデータを変更しないので、過去のデータを参照することができる。Jungleは木構造のデータベースなので、木構造のデータをそのまま格納出来る。 + + +本研究ではJungleに、検索API、Index、過去データの参照の実装を行った。 +さらに、当研究室と共同研究を行っているSymphonies社が開発した、アカウント管理システムmaTrixにJungleを組み込む。 \section{maTrix} -maTrixとはSymphonies社が開発しているアカウント管理、許諾判定システムのことである。\\ -matrixは人、役職、役割、権限と言った木構造の組織、ポリシーファイルの２つのデータを持っている。maTrixが保持している人、役職、役割等のデータはお互いに参照している。 +maTrixとはSymphonies社が開発した、アカウント管理、許諾判定システムのことである。\\ +maTrixは人、役職、役割、権限と言った木構造の組織、ポリシーファイルの２つのデータを持っている。maTrixが保持している人、役職、役割等のデータはお互いに参照している。 ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。\\ 組織のデータ、ポリシーファイル共に木構造のデータであるため、木構造のデータベースであるJungleには、そのまま格納できる。\\ また、maTrixは、いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持するので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。\\ -maTrixはデータをxml形式で出力することが可能なので、xml形式で出力されたmaTrixの人、組織等のデータをJungleに格納するために、SAXを用いて、Jungle用のxmlReaderを作成した。xmlReaderを作成したことにより、実際にmaTrixから出力されたデータをJungleに取り込み、本格的なテストが行えるようになった。 +maTrixはデータをxml形式で出力することが出来る。 + + +xml形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のxmlReaderを作成した。xmlReaderを作成したことにより、実際にmaTrixから出力されたデータをJungleに取り込み、テストを行うことを可能にした。 \section{検索APIの実装} -Jungleは、データを格納するAPIは実装されていたが、データの検索を行うAPIの実装は行われていなかった。\\ -本研究ではJava8の新機能であるlambda式を用いてデータの検索を行うfind関数の実装を行った。\\ -以下にfind関数の使い方を示したソースコードを記述する。\\ +Java8の新機能であるlambda式を用いてデータの検索を行うfind関数の実装を行った。\\ +図1にfind関数の使い方を示したソースコードを記述する。\\ {\scriptsize - \begin{itembox}[l]{JungleのQuery部分のソースコード} + \begin{itembox}[l]{図1} \begin{verbatim} Iterator> pairPersonIterator = traverser.find((TreeNode node) -> { @@ -60,89 +70,106 @@ \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)も実装した。 +find関数は引数にQuery、String key、String valueの3つを取る。条件に一致したNodeと、そのNodeまでのPathを１つにまとめたPairのIteratorを返す。\\ + -\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{table} + \begin{tabular}{|l|c|r|}\hline + 引数 & 関数での使われ方 \\\hline + Query & 探索の条件を記述したInterface(図2) \\\hline + Key & 後述するIndexを使うために使用する \\\hline + value & 後述するIndexを使うために使用する \\\hline + \end{tabular} + \end{table} + - \begin{itembox}[l]{Indexのデータの型} - {\scriptsize\begin{verbatim} TreeMap>>>\end{verbatim}}\\\\ +{\scriptsize + \begin{itembox}[l]{図2} + \begin{verbatim} + public interface Query { + boolean condition(TreeNode node); + } + \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)も実装した。 + + \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形式で実装する。\\ + + + \begin{itembox}[l]{図3} +{\scriptsize\begin{verbatim} TreeMap>>>\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の定義} + 図3はIndexの型である。 + + + 最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapで、 + このTreeMapに対しkeyでgetを行うと、keyに対応するIndexを取得できる。 + 取得したIndexに対し、valueでgetを行うと、valueの値を持つNodeと、そのNodeまでのPathの２つをPairのListが返ってくる。\\ + %もう少しわかりやすく + + + \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 { + public interface IndexEditor { Either - edit(TreeNode root,TransactionManager txManager, - TreeEditor editor,TreeOperationLog log, - TreeMap>>> index); -} + edit(TreeNode root,TransactionManager txManager, + TreeEditor editor,TreeOperationLog log, + TreeMap>>> index); + } \end{verbatim}}\\\\ \end{itembox} \\ \section{maTrixに必要なQueryの作成} - 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下の探索を可能にした\\ + 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下の探索を可能にした。\\ {\scriptsize - \begin{itembox}[l]{今回追加実装したcompareの定義} + \begin{itembox}[l]{図5} \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の設計手法を確立させる必要がある。\\ + 実際にmaTrixとJungleの接続を行い、既存のmaTrixとJunglemaTrixの性能を評価し、本当に早くなったのか確かめる。この時にIndexの性能も評価する。 + + + Jungleは、過去のversionのTreeを保持しているので、 + 過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。 + + + Jungleは比較的自由にデータを格納することができる。なので、Jungleを実際に使用する際に、どこまでを一つの木として扱うか、等をまとめたJungleDBの設計手法を確立させる必要がある。 - \begin{thebibliography}{9} + \begin{thebibliography}{9} - \bibitem{1} - 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装 - \bibitem{2} - 大城信康 分散Database Jungleに関する研究 - \bibitem{3} - Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界 - \end{thebibliography} + \bibitem{1} + 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装 + \bibitem{2} + 大城信康 分散Database Jungleに関する研究 + \bibitem{3} + Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界 + \end{thebibliography} - \end{document} + \end{document}