Mercurial > hg > Papers > 2016 > tatsuki-prosym
changeset 21:27f92e7af1fc
prefix
author | tatsuki |
---|---|
date | Mon, 28 Nov 2016 19:55:58 +0900 |
parents | e81a5eb2a60f |
children | b43817a9297d |
files | abst.tex bbs.tex images/contentTree.graffle images/contentTree.pdf introduction.tex jungle.tex maTrix.tex main.tex renderingEngine.tex summary.tex |
diffstat | 10 files changed, 178 insertions(+), 142 deletions(-) [+] |
line wrap: on
line diff
--- a/abst.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/abst.tex Mon Nov 28 19:55:58 2016 +0900 @@ -5,7 +5,7 @@ データベース自体もRDBと方向の違う表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 今回提案する木構造データベースJungleはプログラム内部に直接木構造を構築し、そのルートをアトミックに入れ替えることでトランザクションを実現する。 -また木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取る。 +また木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を採る。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。Jungleは分散構成も可能である。 本論文ではJungleデータベースの構造とこれを用いたアプリケーション、実装時に発生した問題と解決方法について解説する。
--- a/bbs.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/bbs.tex Mon Nov 28 19:55:58 2016 +0900 @@ -1,27 +1,25 @@ \section{Jungle Tree ブラウザ} -Jungleの複数の木をブラウザ上で表示し変更できるするアプリケーションを作成した。 -実装時木に対する変更をEditorを用いる方法はプログラム上では便利だが、Jungleの木を手動で変更するのには向いていない。 -組み込みWEBサーバーであるJettyを使用し、Servletとして表示と変更を実現した。 +Jungleの木に対する変更において、JungleTreeEditorを用いる方法はプログラム上では便利だが、手動で変更するのには向いていない。 +よって、組み込みWEBサーバーであるJettyを使用し、Servletとして木の表示と編集を実現した。 \subsection{木構造の表示} Jungle DBはWEBサーバー内に存在し、それから表示に必要なHTMLを生成してブラウザに転送する。 図\ref{printNode}は、サーバからデータを送りブラウザ上でNodeを可視化するまでの流れである。 -この流れはPathの処理を除けば通常のデータベースのレコードの表示と同等である。 +この流れはJungleのNodePathの処理を除けば通常のデータベースのレコードの表示と同等である。 \begin{figure}[h] \begin{center} -\includegraphics[height = 6cm , bb=0 0 622 497]{images/printNodeValue.pdf} +\includegraphics[height = 6cm , bb=0 0 516 416]{images/printNodeValue.pdf} \caption{ブラウザを使用したNodeの可視化} \label{printNode} \end{center} \end{figure} \begin{enumerate} -\item Userは表示したいNodeのPathをWeb Serverに送る -\item JettyはJungleから木を取得する -\item 木からNodePathの位置にあるNodeを取得する -\item Nodeの中身をブラウザに送信する -\item ブラウザがNodeの中身を表示する +\item Userは表示したいNodeのPathをJungleTreeブラウザに送る +\item JungleTreeブラウザはJungleから木を取得する +\item 木からPathの位置にあるNodeを取得する +\item Nodeの中身をJungleTreeブラウザが表示する \end{enumerate} @@ -35,7 +33,7 @@ \begin{figure}[h] \begin{center} -\includegraphics[height = 10cm , bb=0 0 622 971]{images/TreeEdit.pdf} +\includegraphics[height = 10cm , bb=0 0 516 795]{images/TreeEdit.pdf} \caption{ブラウザを介した木の編集} \label{JungleEdit} \end{center} @@ -43,12 +41,13 @@ 図\ref{JungleEdit} \begin{enumerate} -\item Userはブラウザで編集したいNodeを表示するページに移動する -\item ブラウザに木の変更要求を送る -\item ブラウザはJungleから対応した木を取得する +\item UserはJungleTreeブラウザで編集したいNodeを表示するページに移動する +\item JungleTreeブラウザに木の変更要求を送る +\item JungleTreeブラウザはJungleから対応した木を取得する \item 木からEditorを取得する \item Editorを使用して木の変更を行う \item 木の変更をJungleにコミットする +\item 木の変更の結果を表示する \end{enumerate} Pathを使用することにより木の変更をRestfulに行うことができるように見えるが、木のPathは特定の木の版に固有のものである。
--- a/images/contentTree.graffle Thu Nov 10 20:20:05 2016 +0900 +++ b/images/contentTree.graffle Mon Nov 28 19:55:58 2016 +0900 @@ -6,21 +6,26 @@ <integer>0</integer> <key>ApplicationVersion</key> <array> - <string>com.omnigroup.OmniGraffle6</string> - <string>156.11.0.206384</string> + <string>com.omnigroup.OmniGraffle</string> + <string>139.16.0.171715</string> </array> <key>AutoAdjust</key> <true/> <key>BackgroundGraphic</key> <dict> <key>Bounds</key> - <string>{{0, 0}, {1118.0000095367432, 783}}</string> + <string>{{0, 0}, {1118, 783}}</string> <key>Class</key> <string>SolidGraphic</string> <key>ID</key> <integer>2</integer> <key>Style</key> <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> <key>stroke</key> <dict> <key>Draws</key> @@ -41,9 +46,9 @@ <key>Creator</key> <string>sister_clown</string> <key>DisplayScale</key> - <string>1.0000 cm = 1.0000 cm</string> + <string>1.000 cm = 1.000 cm</string> <key>GraphDocumentVersion</key> - <integer>11</integer> + <integer>8</integer> <key>GraphicsList</key> <array> <dict> @@ -109,8 +114,8 @@ <key>Align</key> <integer>0</integer> <key>Text</key> - <string>{\rtf1\ansi\ansicpg932\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} + <string>{\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural @@ -182,8 +187,8 @@ <key>Text</key> <dict> <key>Text</key> - <string>{\rtf1\ansi\ansicpg932\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} + <string>{\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc @@ -253,8 +258,8 @@ <key>Text</key> <dict> <key>Text</key> - <string>{\rtf1\ansi\ansicpg932\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} + <string>{\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc @@ -324,8 +329,8 @@ <key>Text</key> <dict> <key>Text</key> - <string>{\rtf1\ansi\ansicpg932\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} + <string>{\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc @@ -397,8 +402,8 @@ <key>Align</key> <integer>0</integer> <key>Text</key> - <string>{\rtf1\ansi\ansicpg932\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} + <string>{\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural @@ -471,15 +476,15 @@ <key>Align</key> <integer>0</integer> <key>Text</key> - <string>{\rtf1\ansi\ansicpg932\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} + <string>{\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural -\f0\fs36 \cf0 title : diary_title\ - date : diary_date\ +\f0\fs36 \cf0 title : diary_title\ + date : diary_date\ \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc -\cf0 component : diaryMulti@Component}</string> +\cf0 component : Multi@Component}</string> </dict> <key>TextRelativeArea</key> <string>{{0, 0}, {1, 1}}</string> @@ -871,9 +876,9 @@ <key>MasterSheets</key> <array/> <key>ModificationDate</key> - <string>2016-11-10 09:38:02 +0000</string> + <string>2016-11-28 09:01:55 +0000</string> <key>Modifier</key> - <string>Kazuma</string> + <string>sister_clown</string> <key>NotesVisible</key> <string>NO</string> <key>Orientation</key> @@ -902,7 +907,7 @@ <key>NSPaperSize</key> <array> <string>size</string> - <string>{595.00000476837158, 842}</string> + <string>{595, 842}</string> </array> <key>NSPrintReverseOrientation</key> <array> @@ -942,16 +947,18 @@ <integer>1</integer> <key>WindowInfo</key> <dict> - <key>BottomSlabHeight</key> - <real>414</real> <key>CurrentSheet</key> <integer>0</integer> - <key>Expanded_Canvases</key> + <key>ExpandedCanvases</key> <array/> <key>Frame</key> - <string>{{0, 4}, {1193, 773}}</string> - <key>ShowInfo</key> - <true/> + <string>{{298, 232}, {1193, 773}}</string> + <key>ListView</key> + <false/> + <key>OutlineWidth</key> + <integer>142</integer> + <key>RightSidebar</key> + <false/> <key>ShowRuler</key> <true/> <key>Sidebar</key> @@ -959,7 +966,7 @@ <key>SidebarWidth</key> <integer>230</integer> <key>VisibleRegion</key> - <string>{{-5, 101}, {646, 616}}</string> + <string>{{-5, 86}, {948, 631}}</string> <key>Zoom</key> <real>1</real> <key>ZoomValues</key>
--- a/introduction.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/introduction.tex Mon Nov 28 19:55:58 2016 +0900 @@ -1,5 +1,7 @@ -\section{Jungle DBによるインピーダンスミスマッチの解決} + +\section{はじめに} +\subsection{Jungle DBによるインピーダンスミスマッチの解決} プログラム中のデータ構造とRDBの表構造には大きなギャップがある。これはインピーダンスミスマッチと呼ばれている。 例えばRPGゲーム中のユーザが持つアイテムという単純なものでもRDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 プログラム中ではユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 @@ -11,28 +13,26 @@ \subsection{非破壊的木構造データベースJungle} -当研究室では、これらの問題を解決した煩雑なデータ設計が必要のない Jungle データベースを提案している。 -Jungleはプログラム内部に直接木構造を構築し、そのルートをアトミックに入れ替えることでトランザクションを実現する。 -また木構造の表現に単一リンクを用い、変更を非破壊的つまり、元の木を保存しつつ、新しい木を構築する方法を取る。 -これにより複数のスレッドからでも木構造を安全に扱うことができる。 -プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にいちいちデータベースに問い合わせる必要がない。また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。 -本研究では実際にJungle上に実際に複数のアプリケーションを実装し、Jungleの表現力、機能の十分性、実用的な性能があるか、実証実験を行った。その時に明らかになった木構造データベースの問題点についても考察する。 +当研究室では、これらの問題を解決した煩雑なデータ設計が必要のない Jungleデータベースを提案している。 Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。 ノードは自身の子のListと属性名と属性値の組を持ち、データベースのレコードに相当する。 通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。 +また、ノード同士はListを用いた参照で木構造を構築しているため、親から子への片方向の参照しか持たない。 -Jungleは データの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う。 + +Jungleは データの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う。 これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安定して読み出せるという特徴がある。 しかし、書き込み時の手間は大きくなる。 -通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJasonで記述された構造をデータベースを設計することなく読み込むことが可能であり、実際、そういう機能が実装されている。この木をそのままデータベースとしてしようすることも可能である。しかし、木の変更の手間は木の構造に依存する。 -特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、 +通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJasonで記述された構造をデータベースを設計することなく読み込むことが可能であり、実際、そういう機能が実装されている。この木をそのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。 +%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、 +特に非破壊木構造を採用しているJungleでは木構造の変更の手間はO(1)からO(n)となる。つまり、アプリケーションに合わせて木を設計しない限り、 十分な性能を出すことはできない。逆に言えば、正しい木の設計を行えば高速な処理が可能である。 Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを握れば、その上で木構造として自由にアクセスして良い。 Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。 -持続性のある分散のードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの +持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの 部分について考察する。 本論文では、
--- a/jungle.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/jungle.tex Mon Nov 28 19:55:58 2016 +0900 @@ -8,39 +8,37 @@ 本節ではJungle DBのAPIについて解説する。 -\subsection{Jungleのデータ構造} - \subsection{木の生成} -Jungleには木を生成、管理を行うAPI(*表\ref{jungleAPI})が実装されている。 +Jungleには木の生成・管理を行うAPI(表\ref{jungleAPI})が実装されている。 \begin{table}[htb] \begin{center} \caption{Jungleに実装されているAPI} \begin{tabular}{|l|l|} \hline -createNewTree( &Jungleに新しく木を生成する \\ -String treeName) &木の名前が重複した場合 \\ - &生成に失敗する \\ \hline -getTreeByName( &JungleからtreeNameと名前が \\ -String treeName) &一致したtreeを取得する \\ - &名前が一致するTreeがない場合 \\ - &取得は失敗する \\ \hline +JungleTree &Jungleに新しく木を生成する \\ +createNewTree( &木の名前が重複した場合 \\ +String treeName) &生成に失敗しnullを返す。 \\ \hline +JungleTree &JungleからtreeNameと名前が \\ +getTreeByName( &一致するtreeを取得する。 \\ +String treeName) &名前が一致するTreeがない場合 \\ + &取得は失敗しnullを返す \\ \hline \end{tabular} \label{jungleAPI} \end{center} \end{table} - +\newpage \subsection{NodePath} -JungleのNodeの位置はNodePathを使って表される。 -NodePathはrootNodeからスタートし、ノードの子供の場所を次々表すことで対象のNodeの場所を表す。 +JungleのNodeの位置はNodePathを使って表す。 +NodePathはrootNodeからスタートし、対象のNodeまでの経路を、数字を用いて指し示すことで対象のNodeの場所を表す。また、rootNodeは例外として-1と表記される。 +NodePathが\textless -1,1,2,3\textgreater を表している際の例を図\ref{NodePath}に記す。 \begin{figure}[h] \begin{center} \includegraphics[height = 4cm , bb=0 0 313 301]{images/nodePath.pdf} \caption{NodePath} -\label{goodLayoutTree} +\label{NodePath} \end{center} \end{figure} -\newpage \subsection{木の編集} Jungleの木の編集はJungleTreeEditorを用いて行われる。 JungleTreeEditorには表\ref{editor}で定義されているAPIが実装されている。 @@ -49,25 +47,26 @@ \begin{center} \caption{Editorに実装されているAPI} \begin{tabular}{|l|l|} \hline -addNewChildAt( &pathで指定した場所にある \\ -NodePath path, &Nodeの子供のpos番目にNodeを \\ -int pos) &追加する \\ \hline -deleteChildAt( &pathで指定した場所にある \\ -NodePath path, &Nodeのpos番目の子ノードを \\ -int pos) &削除する \\ \hline -putAttribute( &pathで指定した場所にある \\ -NodePath path, &Nodeに属性名 key \\ -String key, &属性値 valueのペアで \\ -ByteBuffer value) &値を挿入する \\ \hline -deleteAttribute( &pathで指定した場所にある \\ -NodePath path, &Nodeが持つ属性名keyとペアで \\ -String key) &保存されているデータを削除する \\ \hline -moveChild( &pathで指定された位置にある \\ -NodePath path &NodeのchildNum番目の \\ -,int childNum, &childをmoveの方向に移動させる \\ -String move) & \\ \hline -pushPop() & rootNodeの上に \\ - & Nodeを追加する \\ \hline +addNewChildAt( &pathで指定した場所にある \\ +NodePath path, &Nodeの子供のpos番目にNodeを \\ +int pos) &追加する。 \\ \hline +deleteChildAt( &pathで指定した場所にある \\ +NodePath path, &Nodeのpos番目の子ノードを \\ +int pos) &削除する。 \\ \hline +putAttribute( &pathで指定した場所にある \\ +NodePath path, &Nodeに属性名 key \\ +String key, &属性値 valueのペアで \\ +ByteBuffer value) &値を挿入する。 \\ \hline +deleteAttribute( &pathで指定した場所にある \\ +NodePath path, &Nodeが持つ属性名keyとペアで \\ +String key) &保存されているデータを削除する。 \\ \hline +moveChild( &pathで指定された位置にある \\ +NodePath path &NodeのchildNum番目の \\ +,int childNum, &childをmoveの方向に移動させる。 \\ +String move) & \\ \hline +pushPop() & rootNodeの上に新しいrootNodeを追加する。 \\ + & 線形のTree等を作る際に使用することで \\ + & 計算量をO(n)からO(1)にできる。 \\ \hline \end{tabular} \label{editor} \end{center} @@ -84,30 +83,26 @@ 編集を行った後は、editor.success()で今までの編集をコミットすることができる。その際他のJungleTreeEditorによって木が更新されていた場合はコミットに失敗する。 その場合は最初からやり直す必要がある。 - -以下にJungleTreeEditorを使ったサンプルコードを記述する +以下にJungleTreeEditorを使ったサンプルコードを記述する。 \begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode] JungleTreeEditor editor = tree.getTreeEditor(); -DefaultNodePath root = new DefaultNodePath(); -Either<Error, JungleTreeEditor> either = editor.addNewChildAt(root, 0); -if (either.isA()) { +DefaultNodePath editNodePath = new DefaultNodePath(); +Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0); +if (either.isA()) throw new IllegalStateException(); -} editor = either.b(); editor.success(); \end{lstlisting} \begin{enumerate} -\item tree.getEditor()でtreeからJungleTreeEditorを取得する -\item 次に変更するノードの場所を指すNodePathを作成する -\item editor.addNewChildAtでpathで指定したノードの子供の0番目に子ノードを追加する -\item 返り値のEitherがErrorを保持していないか(編集に失敗していないか)を確認する -\item Errorを保持していた場合Exceptionを投げる -\item Editorを持っていた場合木の変更をコミットする +\item tree.getEditor()でtreeからJungleTreeEditorを取得する。 +\item 次に変更するノードの場所を指すNodePathを作成する。 +\item editor.addNewChildAtでpathで指定したノードの子供の0番目に子ノードを追加する。 +\item 返り値のEitherがErrorを保持していないか(編集に失敗していないか)を確認する。 +\item Errorを保持していた場合Exceptionを投げる。 +\item 編集に成功していた場合、編集後のEditorを取得する。 +\item (6)で取得したEditorを用いて木の変更をコミットする。 \end{enumerate} -これらのAPIによりJungleは木構造を格納する機能を持っている。 - -\subsection{その他のJungle} -他には当研究室で開発を行っている並列分散フレームワークAliceを用いて実装された分散木構造データベースJungle、Haskell版Jungleなどもある。 +これらのAPIによりJungleは木構造を格納、編集する機能を持っている。
--- a/maTrix.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/maTrix.tex Mon Nov 28 19:55:58 2016 +0900 @@ -1,26 +1,32 @@ \section{許認可管理アプリケーション\\maTrix} Jungle Treeブラウザを実装した後、Jungle上に実際に企業で運用されている許認可管理アプリケーションmaTrixを実装し、データベースとしての表現力、機能の十分性、実用的な性能があるか、実証実験を行なった。 -maTrixは、人、役職、役割、権限、組織等の木構造のデータとポリシーファイルを持つ。maTrixの組織構造はデータ同士がidを用いた参照を行うことで表現される。また組織構造は版管理されている。 +maTrixは、人物、役職、役割、権限、組織等の木構造のデータとポリシーファイルを持つ。maTrixの組織構造はデータ同士がidを用いた参照を行うことで表現される。また、maTrixは過去のアクセス要求を全て保存する。アクセス要求は当時の組織構造を参照しているため、組織構造は版管理されている。 ポリシーファイルは、データに対するアクセス要求が許可されるか否認されるかを判断するためのルールを誰が(Target)、何を(Resource)、どうできるか(Action)の3つの要素で記述されている。maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う。 -ポリシーファイルは組織構造中の人や役職をidを用いて参照している。つまり、ポリシーファイルを用いて許認可を下すためには、その人がどこの組織に所属して。その役割がどの権限を持っているかを返す検索が必要になる。 +ポリシーファイルは組織構造中の人や役職をidを用いて参照している。つまり、ポリシーファイルを用いて許認可を下すためには、その人がどこの組織に所属して、その役割がどの権限を持っているかを返す検索が必要になる。 本章ではmaTrixをJungle上に実装する際の問題点、解法について記述する。 \subsection{Jungle上でのmaTrixデータ構造の表現} -maTrixの人、組織、役割、権限等のデータ構造は木構造なので、Jungleの木構造にそのままマッピングできる。 -実際のmaTrixのデータ構造の一部を格納したJungleTree(図\ref{fig:PersonTree})を以下に記す。 +maTrixの人物、組織、役割、権限等のデータ構造は木構造なので、Jungleの木構造にそのままマッピングできる。 +実際のmaTrixのデータ構造の一部である人物のデータを格納したJungleTree(図\ref{fig:PersonTree})を以下に記す。 \begin{figure}[h] \begin{center} \includegraphics[height = 7cm , bb=0 0 398 367]{images/TreePersonJungle.pdf} -\caption{Jungle上での人物Treeの表現例(1)} +\caption{Jungle上での人物Treeの表現例} \label{fig:PersonTree} \end{center} \end{figure} -また、maTrixは自身のデータをXML形式で書き出すことが可能である。書き出したデータをJungleに格納するためにXMLReaderの実装も行った。 +図\ref{fig:PersonTree}の人物TreeにはmaTrixで使用される人のデータが記述されている。 +属性名 element 属性値 Personsのデータを持つNode1の子ノードである、Node2、Node3に人物のデータが格納されている。 +Node2は属性名 element、属性値 Personを持っている。これはこのNodeが人物のデータを持っていることを表す。 +属性名 Person-id、属性値 p:1 はこのノードに記述された人物のmaTrix上でのIDを表す。 +他の役職、役割、権限といった木構造はこのIDを用いて参照を行うことで組織構造を構築する。 +Node2、Node3は子ノードに人物の名前、参照する役割等、Idのデータを持つが、今回は省略している。 -\newpage +また、maTrixは自身のデータをXML形式で書き出すことが可能である。書き出したデータをJungleに格納するために汎用XMLReaderの実装も行った。 + \subsection{Indexの実装} % Jungleに含まれる複数の木のノードを相互参照したい % 木のノードにIDを割ふってIndexを用いて参照する @@ -40,7 +46,7 @@ JungleのIndexはIndexMap内に保持されている。 属性名でIndexMapにgetを行うと、対応したIndexが取得できる。 -その取得したIndexに属性値で検索を行うと対応したノードのリストが返ってくる。 +その取得したIndexに属性値で検索を行うと、対応したノードのリストが返ってくる。 \subsection{検索APIの実装} @@ -73,11 +79,11 @@ 上記コードについて解説する。 \begin{enumerate} -\item Treeの走破を行うTraverserを取得する。 +\item Treeの走査を行うTraverserを取得する。 \item Indexからfindの第2、第3引数である、element、personの組のデータを持つNodeを取得する。 -\item 2で取得したNodeを第1引数のQueryに渡す(以下Query内の解説 +\item 2で取得したNodeを第1引数のQueryに渡す。 \item 引数のノードからgetAttributes().getString("Personid")で属性名がPersonidの属性値を取得する。
--- a/main.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/main.tex Mon Nov 28 19:55:58 2016 +0900 @@ -35,14 +35,14 @@ \affiliate{PROSYM}{プログラミング・シンポジウム幹事団} \author{金川 竜己}{Kanagawa Tatsuki}{}[k158585@ie.u-ryukyu.ac.jp] -\author{武田和馬}{Hiroki MIZUNO}{IPSJ}[hanako@prosym.ipsj.or.jp] -\author{河野真治}{Hiroki MIZUNO}{}[hanako@prosym.ipsj.or.jp] +\author{武田和馬}{Takeda Kazuma}{}[e135768@ie.u-ryukyu.ac.jp] +\author{河野真治}{Kouno shinji}{IPSJ}[kono@ie.u-ryukyu.ac.jp] % はじめに \input{abst.tex} \begin{jkeyword} -プログラミング・シンポジウム,データベース、Java、Jungle +データベース、Java、Jungle \end{jkeyword} \maketitle
--- a/renderingEngine.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/renderingEngine.tex Mon Nov 28 19:55:58 2016 +0900 @@ -12,8 +12,8 @@ \begin{figure}[h] \begin{center} -\includegraphics[height = 6cm , bb=0 0 835 645]{images/contentTree.pdf} -\caption{ContextTree} +\includegraphics[height = 6cm , bb=0 0 682 533]{images/contentTree.pdf} +\caption{ContentTree} \label{contentTree} \end{center} \end{figure} @@ -38,7 +38,7 @@ \end{center} \end{table} - +\newpage \subsection{Layout} htmlの出力形式を定義するLayoutは複数のComponentからなる。 Layout Treeには図\ref{layoutTree}のようにデータを格納した。 @@ -46,16 +46,16 @@ \begin{figure}[h] \begin{center} -\includegraphics[height = 9cm , bb=0 0 955 1153]{images/Layout Tree.pdf} -\caption{Layout Tree} +\includegraphics[height = 9cm , bb=0 0 750 941]{images/LayoutTree.pdf} +\caption{LayoutTree} \label{layoutTree} \end{center} \end{figure} -Layout TreeはNodeName : displayinformationの組で値を保持するNode1の子に複数のComponentを保持する -ComponentはdisplayComponentName -\textgreater NodeNameの単一的な参照を行っている。 +図\ref{layoutTree}より、Layout Treeは、属性名 NodeName 属性値 displayinformationの組で値を持つNode1の子に、Node2、Node3といった複数のComponentを保持する。 +Node2は、属性名 displayComponentName、属性値 dialy@Componentの組を持つため、それの値を持つNode、つまりNode3へ単一的な参照を行っている。 Node3は、"use" = "text"のペアでタグを保持しているため、Contents Treeの日記の本文に対応する記述が行ってあることがわかる。 -表\ref{tag}にタグとContentsの対応を記述する +表\ref{tag}にタグとContentsの対応を記述する。 \begin{table}[htb] \begin{center} @@ -72,12 +72,28 @@ \end{center} \end{table} +以下に図\ref{contentTree}のContentsTree、図\ref{layoutTree}のLayoutTreeの2つを使用した、レンダリングの流れを記述する。 +\begin{enumerate} +\item ContentTreeのRootNodeに属性名 component 属性値 sample@Componentの組を持つため、今回はsample@Componentのルールに則ってレンダリングすることがわかる。 + +\item ContentTreeは、属性名 component 属性値 sample@Componentの組を持つNode、つまりNode2を参照する。 + +\item Node2は属性名 displayComponentName 属性名 dialyText@Componentを持つため、Node3を参照する。 + +\item Node3は属性名 use 属性値 textを持つため、Node3にはtextをレンダリングする際のルールが書かれていることがわかる。 + +\item レンダリングエンジンはNode3に記述されているルールに則ってhtmlを生成する。 + +\end{enumerate} + +今回の例では、Component同士の参照を記述するためにNode2を追加しているが、本来は意味のないNodeであるため省略される。 + \newpage layoutが複数のComponentを参照する際は図\ref{multiComponent}のような木構造を構築する。 \begin{figure}[h] \begin{center} -\includegraphics[height = 6cm , bb=100 0 918 676]{images/multiComponent.pdf} +\includegraphics[height = 6cm , bb=0 0 749 559]{images/multiComponent.pdf} \caption{複数のComponentを参照するLayout} \label{multiComponent} \end{center} @@ -88,41 +104,53 @@ \subsection{Layout Treeのデータ設計} Jungleは汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能である。 しかし、設計を行うことでより効率的に木構造を扱うことが可能になる。 -図\ref{goodLayout Tree}、図\ref{badLayout Tree}は同じデータを格納した2つの木の一部である。 +図\ref{goodLayoutTree}、図\ref{badLayoutTree}は同じデータを格納した2つの木の一部である。 \begin{figure}[h] \begin{center} -\includegraphics[height = 4cm , bb=0 0 422 322]{images/goodLayout Tree.pdf} +\includegraphics[height = 4cm , bb=0 0 356 276]{images/goodLayoutTree.pdf} \caption{コードとギャップのないLayoutの格納方法} -\label{goodLayout Tree} +\label{goodLayoutTree} \end{center} \end{figure} \begin{figure}[h] \begin{center} -\includegraphics[height = 8cm , bb=0 0 1263 932]{images/badLayout Tree.pdf} +\includegraphics[height = 8cm , bb=0 -100 714 665]{images/badLayoutTree.pdf} \caption{コードとギャップのあるLayoutの格納方法} -\label{badLayout Tree} +\label{badLayoutTree} \end{center} \end{figure} -図\ref{goodLayout Tree}のTreeは、1つのNodeにRenderingに必要な値が全て格納されている。 +図\ref{goodLayoutTree}のTreeは、1つのNodeにRenderingに必要な値が全て格納されている。 そのため、Renderingを行う際、複数のNodeをまたぐ必要が無く、簡潔にコードを書くことができる。 -一方、図\ref{badLayout Tree}のTreeはRenderingする際に必要な値が複数Nodeに分散されて保存されている。 +一方、図\ref{badLayoutTree}のTreeはRenderingする際に必要な値が複数Nodeに分散されて保存されている。 そのため、全てのNodeを参照し、値を集める処理を行う必要があり、コードの可読性が下がり余計な処理も増えてしまった。 \subsection{性能評価} -本節では、図\ref{goodLayout Tree}の木と図\ref{badLayout Tree}を使った2つのRenderinEngineの性能測定を行い、木の構造が実行速度にどれだけ影響するかを確かめる。 +本節では、図\ref{goodLayoutTree}の木と図\ref{badLayoutTree}を使った2つのRenderinEngineの性能測定を行い、木の構造が実行速度にどれだけ影響するかを確かめる。 測定は100000回のRenderingRequestを処理するまでの時間の比較で行う。 -図\ref{fig:BenchMark}が性能測定結果のグラフである。 -設計を行った木の方が高速にRenderingを行えている。 +測定結果を表\ref{BenchMark}に記す。 +これより、設計を行った木の方が高速にRenderingを行えている。 + +\begin{table}[htb] + \begin{center} + \caption{性能評価} + \begin{tabular}{|c|c|} \hline + 使用した木 & 処理時間 \\ \hline + 設計を行った木 & 249s \\ \hline + 設計を行わなかった木 & 277s \\ \hline + \end{tabular} + \label{BenchMark} + \end{center} +\end{table} %\begin{figure}[h] %\begin{flushleft}
--- a/summary.tex Thu Nov 10 20:20:05 2016 +0900 +++ b/summary.tex Mon Nov 28 19:55:58 2016 +0900 @@ -1,10 +1,11 @@ -\newpage \section{まとめ} -本研究では非破壊データベースJungleにBBS、許認可管理アプリケーションmaTrix、HtmlRenderingEngineの3つを実装した。 -BBSを実装したことにより、ブラウザから木構造の確認、編集が行えるようになり、ユーザーは煩雑なEditorから開放された。 +本研究では非破壊データベースJungleにJungleTreeブラウザ、許認可管理アプリケーションmaTrix、HtmlRenderingEngineの3つを実装した。 +JungleTreeブラウザを実装したことにより、ブラウザから木構造の確認、編集が行えるようになった。 次に、Jungle上に許認可管理アプリケーションmaTrixの実装を行い、Jungleに実用データベースとしての表現力、機能の十分性、実用的な性能があるか実証実験を行った。 maTrixは複数の木がお互いにIdを用いた参照を行い組織構造を表現していたが、JungleではIndexを用いた参照で表現した。 -また、測定の結果mongoDBより高速に動作したため、Jungleは、実用アプリケーションを実装できるほどの表現力、機能、性能があることを証明できた。 +また、測定の結果mongoDBの約500倍高速に動作した。 +これはJungleがon memoryなのに対し、MongoDBはmmapを用いてデータにアクセスしているからである。 +maTrixの実装により、Jungleは、実用アプリケーションを実装できるほどの表現力、機能、性能があることを証明できた。 最後にJungleを使った例題アプリケーションとしてRenderingEngineの実装を行った。 その際Jungleのデータ構造でプログラムの処理量、コードの可読性が異なることがわかった。 性能測定では、データ設計を行った木構造を利用したほうが高速に動作した。