Mercurial > hg > Papers > 2015 > tatsuki-thresis

comparison abst.tex @ 7:7848919edb48

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add abst
author tatsuki
date Tue, 17 Feb 2015 12:54:31 +0900
parents
children 6826f31f10c0
comparison
equal deleted inserted replaced
6:b0fd781e3b05 7:7848919edb48
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
2 \usepackage[dvips]{graphicx}
3 \usepackage{ascmac}
4 \usepackage{picins}
5 \usepackage{fancyhdr}
6 \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
7 \rhead{}
8 \cfoot{}
9
10 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
11 \setlength{\headheight}{0mm}
12 \setlength{\headsep}{5mm}
13 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
14 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
15 \setlength{\textwidth}{181mm}
16 \setlength{\textheight}{261mm}
17 \setlength{\footskip}{0mm}
18 \pagestyle{empty}
19
20 \begin{document}
21 \title{分散機構造データベースJungleによる\\企業向け企業システム}
22
23 \author{金川竜己 \\ 指導教員 河野真治 {} }
24 \date{abst}
25 \maketitle
26 \thispagestyle{fancy}
27
28 \section{分散木構造データベースJungle}
29 当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。
30 JungleのTreeは複数個の子を持つノードからなり、ノードは属性名と属性値の組のデータを保持することが可能であり、それらをデータベースのレコードとして扱う。
31 当研究では、共同研究を行っているSymphonies社が開発している、組織の中の許認可を管理するアプリケーションmaTrixにJungleを組み込み、実装すべきAPIの洗い出しを行い、その後実用DBとしての性能があるか実証実験を行う。
32
33 \section{組織中の許認可管理\\アプリケーションmaTrix}
34 maTrixは、人、役職、役割、権限と言った木構造のデータと、許認可判断用のポリシーファイルを持つ。
35 maTrixの組織構造は、データ同士がidを用いて参照を行い表現しており、version毎に版管理している。
36 組織構造は木構造なので Jungleの木構造にそのままマッピングできる。
37
38 また、maTrixが許認可判断に用いるポリシーファイルはXACMLファイル形式で記述されており、XACMLは、組織構造中の人や役職をidとして参照する。
39 つまり、XACMLを用いて許認可の判断を下すためには、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。
40
41 maTrixがXML形式で出力したデータを、Jungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。
42 読み込んだXACMLTreeからデータを取り出して、Jungle上で許認可判定を行う、XACMLInterpreterの実装も行った。
43
44
45 \section{検索APIの設計と実装}
46
47 JungleのTreeに対して検索を行うfind関数の実装を行った。
48 以下にfind関数の定義を記述する。
49
50 {\scriptsize
51 \begin{itembox}[l]{find関数の定義}
52 \begin{verbatim}
53 publicIterator<TreeNode>
54 find(finalQueryquery,finalStringkey,StringsearchValue);
55 \end{verbatim}
56 \end{itembox}
57 }
58
59 find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。
60
61 第一引数には以下に記載してある、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterfaceQueryを。
62 第二、第三引数の、String key、String valueはIndexの取得を行うために使用する。
63
64 {\scriptsize
65 \begin{itembox}[l]{Queryinterface}
66 \begin{verbatim}
67 publicinterfaceQuery{
68 booleancondition(TreeNodenode);
69 }
70 \end{verbatim}
71 \label{interface}
72 \end{itembox}
73 }
74
75
76 {\scriptsize
77 \begin{itembox}[l]{find Sample}
78 \begin{verbatim}
79 Iterator<TreeNode> pairPersonIterator=
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}
169 \begin{thebibliography}{9}
170
171 \bibitem{1}
172 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装
173 \bibitem{2}
174 大城信康 分散Database Jungleに関する研究
175 \bibitem{3}
176 Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界
177 \end{thebibliography}
178 本研究は、PCIホールディングス株式会社と\\株式会社Symphonyとの共同研究である。
179 \end{document}