# HG changeset patch # User tatsuki # Date 1480416757 -32400 # Node ID 8512227869d52bec4849b9746ebb79a11239a6b3 # Parent 11dc58bf5a2bfa53fd5adec699700575865ff870 zemi diff -r 11dc58bf5a2b -r 8512227869d5 abst.tex --- a/abst.tex Tue Nov 29 18:36:23 2016 +0900 +++ b/abst.tex Tue Nov 29 19:52:37 2016 +0900 @@ -2,10 +2,11 @@ プログラムからデータを分離して扱うデータベースには、 プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。 データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 -データベース自体もRDBと方向の違う表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 +データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 -今回提案する木構造データベースJungleはプログラム内部に直接木構造を構築し、そのルートをアトミックに入れ替えることでトランザクションを実現する。 -また木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を採る。 +今回提案する木構造データベースJungleはプログラム内部に直接木構造を構築する。 +そして、木のルートをアトミックに入れ替えることでトランザクションを実現する。 +また、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を採る。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。Jungleは分散構成も可能である。 本論文ではJungleデータベースの構造とこれを用いたアプリケーション、実装時に発生した問題と解決方法について解説する。 diff -r 11dc58bf5a2b -r 8512227869d5 bbs.tex --- a/bbs.tex Tue Nov 29 18:36:23 2016 +0900 +++ b/bbs.tex Tue Nov 29 19:52:37 2016 +0900 @@ -5,42 +5,25 @@ \subsection{木構造の表示} JungleTreeブラウザにおいて、Jungle DBはWEBサーバー内に存在し、それから表示に必要なHTMLを生成してブラウザに転送する。 -図\ref{printNode}は、サーバからデータを送り、ブラウザ上でノードを可視化するまでの流れである。 +%図\ref{printNode}は、サーバからデータを送り、ブラウザ上でノードを可視化するまでの流れである。 この流れは、JungleのNodePathの処理を除けば通常のデータベースのレコードの表示と同等である。 -\begin{figure}[h] -\begin{center} -\includegraphics[height = 6cm , bb=0 0 622 497]{images/printNodeValue.pdf} -\caption{ブラウザを使用したNodeの可視化} -\label{printNode} -\end{center} -\end{figure} +編集するノードのパスはURLで記述されている。例えば、 +{\small +\verb! http://localhost/showBoardMessage?! +\verb! bname=Layout&path=-1,0,2! +} +などとなる。 \begin{enumerate} -\item ユーザーは表示したいノードのパスを、JungleTreeブラウザに送る。 +\item ユーザーは表示したいノードのパスをURLでJungleTreeブラウザに送る。 \item JungleTreeブラウザは、WEBサーバ内にあるJungleから、対応した木を取得する。 \item JungleTreブラウザは、パスで指定した位置のノードを返す関数、tree.getNodeOfPath()を用いて、木から表示するノードを取得する。 -\item (3)で取得したノードの中身を、JungleTreeブラウザが表示する。 +\item 取得したノードの中身を、JungleTreeブラウザが表示する。 \end{enumerate} \subsection{ブラウザを使った木の編集} -図\ref{JungleEdit}はブラウザを用いたJungleの木の更新の流れである。 -編集するノードのパスはURLで記述されている。例えば、 - -{\small -\verb! http://localhost/showBoardMessage?! -\verb! bname=Layout&path=-1,0,2! -} - -などとなる。 - -\begin{figure}[h] -\begin{center} -\includegraphics[height = 10cm , bb=0 0 622 971]{images/TreeEdit.pdf} -\caption{ブラウザを介した木の編集} -\label{JungleEdit} -\end{center} -\end{figure} +%図\ref{JungleEdit}はブラウザを用いたJungleの木の更新の流れである。 \begin{enumerate} \item ユーザーはJungleTreeブラウザで編集したいノードを表示するページに移動する 。 @@ -54,7 +37,8 @@ パスを使用することにより、木の変更をRestfulに行うことができるように見えるが、木のパスは特定の木の版に固有のものである。 ブラウザとWEBサーバは、セッションで結合されており、そのセッションが同じ版の木を編集していれば問題なく成功する。 -ただし、編集し終わった時に、他の編集が割り込んでいたら、その編集は無効となる。この点が既存のRDBとは異なる。 +ただし、編集し終わった時に、他の編集が割り込んでいたら、その編集は無効となる。 +%この点が既存のRDBとは異なる。 また巨大な木を操作する時には、Pathを直接URLに含むことはできないので、他の工夫が必要になると考えられる。 このアプリケーションでは任意の木を取り扱うので、木の大きさの現実的な制限を除けば木の設計の問題はない。 diff -r 11dc58bf5a2b -r 8512227869d5 jungle.tex --- a/jungle.tex Tue Nov 29 18:36:23 2016 +0900 +++ b/jungle.tex Tue Nov 29 19:52:37 2016 +0900 @@ -1,15 +1,15 @@ \section{非破壊的木構造データベースJungle} Jungleは等研究室が開発を行っているデータベースで、Javaを用いて実装されている。 -Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。 +Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。 ノードは自身の子のListと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。 通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。 -また、ノード同士はListを用いた参照で木構造を構築しているため、親から子への片方向の参照しか持たない。 +Jungleでは、親から子への片方向の参照しか持たない。 Jungleは、データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{nonDestractTreeEdit})。 その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{nonDestractTreeEdit}の例ではノードB D Eは編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。 -これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安定して読み出せるという特徴がある。 +これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安全に読み出せるという特徴がある。 しかし、書き込み時の手間は大きくなる。 @@ -25,8 +25,8 @@ \newpage 通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能であり、実際、そのような機能が実装されている。この木をそのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。 %特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、 -特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となる。つまり、アプリケーションに合わせて木を設計しない限り、 -十分な性能を出すことはできない。逆に言えば、正しい木の設計を行えば高速な処理が可能である。 +特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、 +十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。 Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。 Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。 @@ -36,18 +36,16 @@ \subsection{木の生成} 初めにJungleにおける木の生成について述べる。 Jungleは複数の木を一意な名前を利用して管理しており、名前を利用することで作成、編集、削除を行う。 -以下にJungleが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。 +以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。 \begin{table}[htb] \begin{center} \caption{Jungleに実装されているAPI} \begin{tabular}{|l|l|} \hline -JungleTree &Jungleに新しく木を生成する \\ -createNewTree( &木の名前が重複した場合 \\ -String treeName) &生成に失敗しnullを返す。 \\ \hline -JungleTree &JungleからtreeNameと名前が \\ -getTreeByName( &一致するtreeを取得する。 \\ -String treeName) &名前が一致するTreeがない場合 \\ - &取得は失敗しnullを返す \\ \hline +{\tt JungleTree createNewTree(String treeName) } & +Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。 \\ \hline +{\tt +JungleTree getTreeByName(String treeName)} & + JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す \\ \hline \end{tabular} \label{jungleAPI} \end{center} @@ -64,9 +62,9 @@ \caption{TreeNodeに実装されているAPI} \begin{tabular}{|l|l|} \hline Children &ノードの子供を扱う \\ -getChildren() &Childrenクラスを返す。 \\ \hline +getChildren() &Childrenオブジェクトを返す。 \\ \hline Attribute &ノードが保持しているデータを \\ -getAttribute() &扱うAttribteクラスを返す。 \\ \hline +getAttribute() &扱うAttribteオブジェクトを返す。 \\ \hline \end{tabular} \label{TreeNodeAPI} \end{center} @@ -88,8 +86,8 @@ \end{table} -関数children.at(int num)が返すEither\textless Error,TreeNode\textgreater クラスは、変数numで指定した場所に子ノードがあればTreeNodeクラスを、無かった場合はErrorクラスを持つ型である。 - +関数{\tt children.at(int num)}が返すEither\textless Error,TreeNode\textgreater オブジェクトは、{\tt isA() }でErrorかどうかをチェックすることができる。 +Errorでない場合は{\tt b()}でTreeNodeオブジェクトを取り出すことができる。 \begin{table}[htbH] @@ -123,14 +121,14 @@ \begin{enumerate} \item Jungleから名前を指定して木を取得する。 -\item (1)で取得した木のルートノードを取得する。 -\item (2)で取得したルートノードからChildren型の子ノードを取得する。 -\item (3)で取得した変数childrenから2番目の子供を取得する。 +\item 取得した木のルートノードを取得する。 +\item 木のルートノードからChildren型の子ノードを取得する。 +\item 変数{\tt children}から2番目の子供を取得する。 \item 2番目の子供が取得できたかを調べる。 -\item 取得できていなかった場合Exceptionを投げる。 +\item 取得できていなかった場合{\tt Exception}を投げる。 \item 取得に成功していた場合、eitherから子ノードを受け取る。 -\item (7)で取得した子ノードからAttributeを取得する。 -\item (8)で取得したAttributeから属性名 nameがペアの値を取得する。 +\item 取得した子ノードからAttributeを取得する。 +\item 取得したAttributeから属性名 nameがペアの値を取得する。 \end{enumerate} @@ -154,7 +152,7 @@ Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。 JungleTreeEditorクラスには編集を行うために、表\ref{editor}で定義されているAPIが実装されている。 -\begin{table}[htb] +\begin{table*}[htb] \begin{center} \caption{Editorに実装されているAPI} \begin{tabular}{|l|l|} \hline @@ -193,12 +191,12 @@ \end{tabular} \label{editor} \end{center} -\end{table} +\end{table*} 編集後に返されるJungleTreeEditorクラスは、編集後の木構造を保持しているため、編集前の木構造を保持しているJungleTreeEditorクラスとは別のオブジェクトである。 -編集を行った後は、関数editor.success()で今までの編集をコミットすることができる。その際他のJungleTreeEditorクラスによって木が更新されていた場合はコミットに失敗する。 -その場合は最初からやり直す必要がある。 +編集を行った後は、関数editor.success()で今までの編集をコミットすることができる。他のJungleTreeEditorクラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。 +その場合は、木の編集を最初からやり直す必要がある。 以下にJungleTreeEditorクラスを用いて、木の編集を行うサンプルコードを記述する。 @@ -219,7 +217,7 @@ \item 返り値の変数EitherがErrorクラスを保持していないか(編集に失敗していないか)を確認する。 \item Errorクラスを保持していた場合Exceptionを投げる。 \item 編集に成功していた場合、編集後のJungleTreeEditorクラスを取得する。 -\item (6)で取得したJungleTreeEditorクラスを用いて木の変更をコミットする。 +\item 取得したJungleTreeEditorクラスを用いて木の変更をコミットする。 \end{enumerate} これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。 diff -r 11dc58bf5a2b -r 8512227869d5 main.tex --- a/main.tex Tue Nov 29 18:36:23 2016 +0900 +++ b/main.tex Tue Nov 29 19:52:37 2016 +0900 @@ -8,11 +8,11 @@ \usepackage{comment} \lstset{% language={Java}, - basicstyle={\footnotesize},% - identifierstyle={\footnotesize},% - commentstyle={\footnotesize\itshape},% - keywordstyle={\footnotesize\bfseries},% - ndkeywordstyle={\footnotesize},% + basicstyle={\footnotesize\ttfamily},% + identifierstyle={\footnotesize\ttfamily},% + commentstyle={\footnotesize\itshae},% + keywordstyle={\footnotesize\ttfamily},% + ndkeywordstyle={\footnotesize\ttfamily},% stringstyle={\footnotesize\ttfamily}, frame={tb}, breaklines=true, diff -r 11dc58bf5a2b -r 8512227869d5 renderingEngine.tex --- a/renderingEngine.tex Tue Nov 29 18:36:23 2016 +0900 +++ b/renderingEngine.tex Tue Nov 29 19:52:37 2016 +0900 @@ -1,6 +1,6 @@ -\section{HtmlRenderingEngine} +\section{HTML Rendering Engine} 前章でJungle上にmaTrixを実装し、性能評価を行うことで、Jungleに実用データベースたる表現力、性能があることが確認できた。 -本章ではにJungle上に例題アプリケーションとしてHtmlRenderingEngineの開発を行い、その際に発生した問題、解法について解説する。 +本章ではにJungle上に例題アプリケーションとしてHTML Rendering Engineの開発を行い、その際に発生した問題、解法について解説する。 HtmlRenderingEngineは、出力するデータが記述されたContents Tree、出力する形式が記述されたLayout Treeの2つの木構造を持ち、これらを参照しながらhtmlのレンダリングを行う。 またレンダリングする例題は日記を選択した。