Mercurial > hg > Papers > 2015 > tatsuki-thresis

comparison abst.tex @ 11:7736b4d79048

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
abst update
author tatsuki
date Tue, 17 Feb 2015 16:33:49 +0900
parents 6826f31f10c0
children 558dcd1a4583
comparison
equal deleted inserted replaced
10:5053959a1d75 11:7736b4d79048
16 \setlength{\textheight}{261mm} 16 \setlength{\textheight}{261mm}
17 \setlength{\footskip}{0mm} 17 \setlength{\footskip}{0mm}
18 \pagestyle{empty} 18 \pagestyle{empty}
19 19
20 \begin{document} 20 \begin{document}
21 \title{分散機構造データベースJungleによる\\企業向け企業システム} 21 \title{分散木構造データベースJungleによる\\企業向け許認可システム}
22 22
23 \author{金川竜己 \\ 指導教員 河野真治 {} } 23 \author{金川竜己 \\ 指導教員 河野真治 {} }
24 \date{Knowledge is tree strucuture.I Want DataBase to easily store Tree strucuture.laboratory have developed a database Jungle.Jungle which has non-destructive tree strucuture and distributed.Symphony company has developed enterprise Authorization system.we build a enterprise Authorization system on Jungle.And I was a test of the Jungle.Locate the required API, which was implemented.I have implemented a three API ,Search API, Index, Access to the past of Tree.Results came out by the measurement}
25 \maketitle 24 \maketitle
25 \begin{abstract}Knowledge is tree strucuture. We want DataBase to easily store Tree strucuture. laboratory have developed a database Jungle. Jungle which has non-destructive tree strucuture and distributed. Symphony company has developed enterprise Authorization system. We build a enterprise Authorization system on Jungle. And I was a test of the Jungle. Locate the required API, which was implemented. I have implemented a three API , Search API, Index, Access to the past of Tree. we was able to build a practical application on the result Jungle\end{abstract}
26 \thispagestyle{fancy} 26 \thispagestyle{fancy}
27 27
28 \section{分散木構造データベースJungle} 28 \section{分散木構造データベースJungle}
29 当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。 29 当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。
30 JungleのTreeは複数個の子を持つノードからなり、ノードは属性名と属性値の組のデータを保持することが可能である。それらをデータベースのレコードとして扱う。 30 非破壊的木構造は、一度生成した木を上書きせず、データの編集はルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う。
31 当研究では、共同研究を行っているSymphonies社が開発している、組織の中の許認可を管理するアプリケーションmaTrixにJungleを組み込み、実装すべきAPIの洗い出しを行い、その後実用DBとしての性能があるか実証実験を行う。 31 そのため、非破壊的木構造は検索中の木が変更されないことが保証されているので、破壊的木構造に比べてスケールアウトがしやすくなっている。
32
33 当研究では、共同研究を行っているSymphonies社が開発している、組織の中の許認可を管理するアプリケーションmaTrixにJungleを組み込み、実装すべきAPIの洗い出しを行い、その後実用データベースとしての性能があるか実証実験を行う。
32 34
33 \section{組織中の許認可管理\\アプリケーションmaTrix} 35 \section{組織中の許認可管理\\アプリケーションmaTrix}
34 maTrixは、人、役職、役割、権限と言った木構造のデータと、許認可判断用のポリシーファイルを持つ。 36 maTrixは、人、役職、役割、権限と言った木構造のデータと、許認可判断用のポリシーファイルを持つ。
35 maTrixの組織構造は、データ同士がidを用いて参照を行い表現しており、version毎に版管理している。 37 maTrixの組織構造は、データ同士がidを用いて参照を行い表現しており、version毎に版管理している。
36 組織構造は木構造なので Jungleの木構造にそのままマッピングできる。 38 また、maTrixが許認可判断に用いるポリシーファイルはXACMLファイル形式で記述されており、XACMLは、組織構造中の人や役職をidを用いて参照する。
37
38 また、maTrixが許認可判断に用いるポリシーファイルはXACMLファイル形式で記述されており、XACMLは、組織構造中の人や役職をidとして参照する。
39 つまり、XACMLを用いて許認可の判断を下すためには、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。 39 つまり、XACMLを用いて許認可の判断を下すためには、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。
40 40
41 maTrixがXML形式で出力したデータを、Jungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。 41 %maTrixがXML形式で出力したデータを、Jungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。
42 読み込んだXACMLTreeからデータを取り出して、Jungle上で許認可判定を行う、XACMLInterpreterの実装も行った。 42 %読み込んだXACMLTreeからデータを取り出して、Jungle上で許認可判定を行う、XACMLInterpreterの実装も行った。
43 43
44 44
45 \section{検索APIの設計と実装} 45 \section{Jungle上での\\maTrixのデータ構造の表現}
46 maTrixの人、組織、役割、権限等のデータは木構造なので Jungleの木構造にそのままマッピングできる。
47 実際のmaTrixのデータ構造の一部(表\ref{list:PersonTree})と、そのデータを実際に格納したJungleTree(図\ref{fig:PersonTree})を以下に記す。
48 \begin{figure}[h]
49 \begin{center}
50 \includegraphics[height = 8cm , bb=0 0 398 367]{fig/TreePersonJungle.pdf}
51 \caption{Jungle上での人物Treeの表現例(1)}
52 \label{fig:PersonTree}
53 \end{center}
54 \end{figure}
46 55
56 \clearpage
57 \begin{table}[h]
58 \caption{図\ref{fig:PersonTree}に対応したXML}
59 \label{list:PersonTree}
60 \begin{center}
61 \begin{tabular}{|l|} \hline
62 \verb|<|Persons\verb|>| \\
63 \ \verb|<|Person id="p:1" type="Person"\verb|>| \\
64 \ \ \verb|<|PersonData\verb|>| \verb|<|/PersonData\verb|>| \\
65 \ \verb|<|/Person\verb|>| \\
66 \ \verb|<|Person id="p:2" type="Person"\verb|>| \\
67 \ \ \verb|<|PersonData\verb|>| \verb|<|/PersonData\verb|>| \\
68 \ \verb|<|/Person\verb|>| \\
69 \verb|<|/Persons\verb|>|\\ \hline
70 \end{tabular}
71 \end{center}
72 \end{table}
73 しかし、maTrixの一部のデータ構造がJungleに対応していないため、その部分のみJungleにあった形に修正を行い格納している。Jungle上で表現できないデータの例を以下に記す(\ref{list:PersonTree2})。
74
75 \begin{table}[h]
76 \caption{Jungle上で表現できないデータ例}
77 \label{list:PersonTree2}
78 \begin{center}
79 \begin{tabular}{|l|} \hline
80 \verb|<|Ids\verb|>|r:10 r:34\verb|<|/Ids\verb|>| \\
81 \hline
82 \end{tabular}
83 \end{center}
84 \end{table}
85
86 Jungleは、TreeNodeにデータを格納する際、String　KeyとByteBuffer attributeの組み合わせで保持している。
87 しかし、1つのkeyに対して複数のattributeを持つことは出来ないので、図\ref{list:PersonTree2}の様に、1つの要素に複数の値がある場合などはそのままではデータを格納できない。
88 しかし、表\ref{list:maTrixDataChild}の様にデータ構造を変更すればJungleに格納できるようになる。
89 \begin{table}[h]
90 \caption{Jungleに対応したデータ例}
91 \label{list:maTrixDataChild}
92 \begin{center}
93 \begin{tabular}{|l|} \hline
94 \verb|<|Ids\verb|>| \\
95 \ \verb|<|Id\verb|>|r:10\verb|<|/Id\verb|>| \\
96 \ \verb|<|Id\verb|>|r:34\verb|<|/Id\verb|>| \\
97 \verb|<|/Ids\verb|>| \\
98 \hline
99
100 \end{tabular}
101 \end{center}
102 \end{table}
103
104 maTrixの人、組織等のデータはお互いにIdを用いて相互参照を行い組織情報を表現している。
105 Jungle上でのmaTrixの組織構造の表現は、Treeに対するIdの検索を用いて表現すれば良い。
106 また、maTrixがXML形式で出力したデータを、Jungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。
107
108 \section{Jungle上での検索APIの設計と実装}
47 JungleのTreeに対して検索を行うfind関数の実装を行った。 109 JungleのTreeに対して検索を行うfind関数の実装を行った。
48 以下にfind関数の定義を記述する。 110 以下にfind関数の定義を記述する。
49 111
50 {\scriptsize 112
51 \begin{itembox}[l]{find関数の定義} 113 \begin{itembox}[l]{find関数の定義}
52 \begin{verbatim} 114 \begin{verbatim}
53 publicIterator<TreeNode> 115 public Iterator<TreeNode> find
54 find(finalQueryquery,finalStringkey,StringsearchValue); 116 (Query query ,String key,String Value);
55 \end{verbatim} 117 \end{verbatim}
56 \end{itembox} 118 \end{itembox}
57 } 119
58 120
59 find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。 121 find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。
60
61 第一引数には以下に記載してある、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterfaceQueryを。 122 第一引数には以下に記載してある、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterfaceQueryを。
62 第二、第三引数の、String key、String valueはIndexの取得を行うために使用する。 123 第二、第三引数の、String key、String valueはIndexの取得を行うために使用する。
63 124
64 {\scriptsize 125
65 \begin{itembox}[l]{Queryinterface} 126 \begin{itembox}[l]{Queryinterface}
66 \begin{verbatim} 127 \begin{verbatim}
67 publicinterfaceQuery{ 128 publicinterfaceQuery{
68 booleancondition(TreeNodenode); 129 booleancondition(TreeNodenode);
69 } 130 }
70 \end{verbatim} 131 \end{verbatim}
71 \label{interface} 132 \label{interface}
72 \end{itembox} 133 \end{itembox}
73 }
74 134
135 find関数を実際に使用して、maTrixがデータにアクセスする際に使用する関数を全て実装し、実際に、XACMLを用いて許認可を行えるようにした。
75 136
76 {\scriptsize 137 \section{まとめ}
77 \begin{itembox}[l]{find Sample} 138 本研究は、実際に使われている組織の中の許認可を判断するアプリケーションmaTrixのデータ構造をどのようにJungle上で表現するかを設計し、実際にmaTrixのデータ構造を格納した。
78 \begin{verbatim} 139 そして実際にmaTrixで使われているデータアクセス関数を実装し、実際にJungle上に実用的な業務アプリケーションの構築に成功した。
79 Iterator<TreeNode> pairPersonIterator= 140 本研究は、PCIホールディングス株式会社と株式会社Symphonyとの共同研究である。
80 traverser.find((TreeNodenode)->{
81 Stringelement=node.getAttributes().getString("element");
82 if(element==null)
83 returnfalse;
84 if(element.equals("Person"))
85 return true;
86 return false;
87 },"element","Person");
88 \end{verbatim}
89 \label{query}
90 \end{itembox}
91 }
92
93 実際にfind関数を使った例とコードの解説を行う。
94
95 find Sampleは、第2、第3引数の"element"-"Person"を用いて、これらの値に対応したIndexが登録されているかを調べる、Indexがある場合はIndexを使用し値を返す。Indexがない場合は、Treeから深さ優先でTreeNodeを取得していく。
96
97 取得したTreeNodeを引数に与え、boolean Query.condition(TreeNode)を実行し、condition中で、TreeNodeのAttributeに対してgetを行い探索対象のデータをTreeNodeが保持しているかを調べ、データを持っていた場合はTrueを、持っていなかった場合はFalseを返す
98
99 conditionの返り値が、Trueだった場合、TreeNodeを返す。今までの処理をもう一度繰り返す。
100
101 find関数を使用し、実際にmaTrixがデータにアクセスする際に使用する関数を全て実装した。
102
103 \section{Indexの実装}
104 Jungleの探索はTreeを全探索するので、探索の計算量はO(n)である。
105 そこで、Indexを使用することで効率よく探索を行えるようにする。
106 Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っていることが望ましい。
107 そこで、メモリの消費量を抑え、各versionのTreeにIndexをもたせる方法として、FunctionalJavaのTreeMapを使用したIndexの実装を行った。
108 FunctionalJavaのTreeMapは、データの更新が行われた際に、一度作られたTreeに対して更新を行わず過去のTreeを
109 再利用し、更新後のTreeMap新しく返すため、メモリの使用量を抑えつつ複数のversionでIndexを保持できる。
110
111 Indexの型は以下のように定義した。
112 {\scriptsize
113 \begin{itembox}[l]{Indexの型}
114 \begin{verbatim}
115 TreeMap<String key,TreeMap<String value,
116 List<TreeNode>>>>
117 \end{verbatim}
118 \end{itembox}
119 }
120 最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapである。
121 このTreeMapに対しkeyでgetを行うと、keyに対応するIndexが登録されている場合、Indexを取得でき、取得したIndexに対し
122 valueでgetを行うと、valueの値を持つNodeのListが返ってくる。
123
124 {\large ParentIndex}
125
126 TreeNodeでgetを行うと、親Nodeを返すParentIndexを実装した。
127 ParentIndexの型は、以下の様に定義した。
128 {\scriptsize
129 \begin{itembox}[l]{Indexの型}
130 \begin{verbatim}
131 TreeMap$<$TreeNode,TreeNode$>$
132 \end{verbatim}
133 \end{itembox}
134 }
135
136 ParentIndexを用いることで、TreeNodeからNodePathを取得できるようになり、Indexで取得したTreeNodeのデータ編集を行えるようになった。
137
138 \section{getOldTree}
139 JungleのTreeはversion毎にUNIQUEなrevisionIdを持つ。
140 アクセスしたいTreeのrevisionIdを引数に取り、過去のTreeのデータの取得とrevisionIdの比較を繰り返すことで過去のTreeにアクセスする関数をgetOldTree実装した。
141 以下にgetOldTreeの定義を示す。
142 {\scriptsize
143 \begin{itembox}[l]{Indexの型}
144 \begin{verbatim}
145 public Either<Error, JungleTree> getOldTree(long revision);
146 \end{verbatim}
147 \end{itembox}
148 }
149
150 \section{検索APIの測定}
151 Jungleに対する検索APIの測定を行う。
152 測定には、maTrixが保持しているデータにアクセスする際に用いる関数のうちの１つを使用した。
153 実験の結果は図\ref{fig:isActive}となる。横軸は人物Treeにいる人の数を表しており、縦軸は探索にかかった時間を表している。
154
155 \begin{figure}[h]
156 \begin{center}
157 \includegraphics[height=5cm , bb=0 0 360 252]{fig/isActive.pdf}
158 \caption{inActiveの実行時間}
159 \label{fig:isActive}
160 \end{center}
161 \end{figure}
162
163 isActiveの実行時間は、Indexを使用しない場合は、Personの数が増えると比例して増えていくのに対し、Indexを使用するとPersonの数が増えても実行時間は変わらず、Indexを使用しない場合と比較し、極めて高速に実行できた。
164
165
166
167
168 \thispagestyle{fancy} 141 \thispagestyle{fancy}
169 \begin{thebibliography}{9} 142 \begin{thebibliography}{9}
170 143
171 \bibitem{1} 144 \bibitem{1}
172 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装 145 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装
173 \bibitem{2} 146 \bibitem{2}
174 大城信康 分散Database Jungleに関する研究 147 大城信康 分散Database Jungleに関する研究
175 \bibitem{3} 148 \bibitem{3}
176 Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界 149 Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界
177 \end{thebibliography} 150 \end{thebibliography}
178 本研究は、PCIホールディングス株式会社と\\株式会社Symphonyとの共同研究である。
179 \end{document} 151 \end{document}