# HG changeset patch # User tatsuki # Date 1414580742 -32400 # Node ID 75e8aac9a4b51c599290010a7f1cbbafd1c2954a # Parent 12e1cf2e91663e77733c1eb5e750141e0752a91f ver 3.0 diff -r 12e1cf2e9166 -r 75e8aac9a4b5 midterm.pdf Binary file midterm.pdf has changed diff -r 12e1cf2e9166 -r 75e8aac9a4b5 midterm.tex --- 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>>>\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 - edit(TreeNode root,TransactionManager txManager, - TreeEditor editor,TreeOperationLog log, - TreeMap>>> index); - } - \end{verbatim}}\\\\ - \end{itembox} - \\ +{\scriptsize + \begin{itembox}[l]{図3} + \begin{verbatim} +TreeMap>>> 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}