Mercurial > hg > Papers > 2016 > tatsuki-prosym

changeset 32:8512227869d5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
zemi
author tatsuki
date Tue, 29 Nov 2016 19:52:37 +0900
parents 11dc58bf5a2b
children 388da5c83f48
files abst.tex bbs.tex jungle.tex main.tex renderingEngine.tex
diffstat 5 files changed, 49 insertions(+), 66 deletions(-) [+]
line wrap: on
line diff
--- 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データベースの構造とこれを用いたアプリケーション、実装時に発生した問題と解決方法について解説する。
--- 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に含むことはできないので、他の工夫が必要になると考えられる。
 このアプリケーションでは任意の木を取り扱うので、木の大きさの現実的な制限を除けば木の設計の問題はない。
 
--- 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は木構造を格納、編集する機能を持っている。
--- 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,
--- 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のレンダリングを行う。
 またレンダリングする例題は日記を選択した。