# HG changeset patch
# User tatsuki
# Date 1485905109 -32400
# Node ID c1d7270965c549a0536bafcbf304b0527ffbc63b
# Parent  c1b81e802b25101eaf921632dfcac9b1126560d6
add databases.tex jungleTreeBrowser renderingEngine.tex

diff -r c1b81e802b25 -r c1d7270965c5 databases.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/databases.tex	Wed Feb 01 08:25:09 2017 +0900
@@ -0,0 +1,49 @@
+%もう少し詳しく書く
+\chapter{既存のデータベース}
+本章では, まずデータベースの種類であるRelational DatabaseとNoSQL について記述する。
+次に、データベースに値を格納する際に、発生する問題であるインピータンスミスマッチについて触れ、
+最後に既存のデータベースの例として、PostgreSql・MongoDB・Cassandraについて記述する。
+
+\section{Relational Database}
+Relational Database(RDB)は、列と行からなる2次元のテーブルにより実装されるデータベースである。
+RDBが保持しているデータへのアクセスは、SQLを用いて行われる。
+テーブルに格納されるデータ型として、文字列・数値・日付・BOOL型があり、システムによりデータに型が強制される。
+RDBはスキーマの決まったデータを扱うことに長けている。
+また、既存のテーブルを結合することで、１つのテーブルとして扱うことが可能である。
+RDBの例として、MySQL・PostgreSQLなどがある。
+
+\section{NoSQL}
+NoSQLはNot Only SQLの略で、SQLを使わないデータベースのことを指す。
+NoSQLデータベースはRDBとは違いスキーマがない。
+そのため、扱おうとしているデータの形が決まっていなくても気軽に使うことができる。
+NoSQLの例として、MongoDB・Cassandra・当研究室で開発を行っているJungleなどがある。
+
+
+\section{インピータンスミスマッチ}
+インピータンスミスマッチとは、プログラム中のデータ構造とRDBの表構造の間に生まれるギャップのことである。
+例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。
+プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。
+レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、これを本質的には解決することはできない。
+そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。
+しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、
+並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、
+並列処理を含むプログラミングからの要請とのミスマッチが残っている。
+
+
+\section{MongoDB}
+MongoDB は2009年に公開された NoSQL のデータベースである。
+JSON フォーマットのドキュメントデータベースであり、スキーマが無い
+リレーショナルテーブルに例えられる。
+スキーマが無いため、事前にデータの定義を行う必要がなく、同じコレクションであっても、他のドキュメントが持っていないフィルドやデータ型をドキュメントに含めることができる。
+そのためリレーショナルデータベースに比べてデータの追加・削除が行いやすい。
+
+
+\section{Cassandra}
+Cassandraは2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである。
+データは4次元か、5次元の連想配列のようになっている。
+4次元の場合、{\tt [KeySpace][ColumnFamily][Key][Column]}・\\
+5次元の場合{\tt [KeySpace][ColumnFamily][Key][SuperColumn][Column]} の形で値にアクセスする。
+例えば、SuperColumnに対して特定のKeyでアクセスを行うと、KeyとペアのColumnが返ってくる。
+このように、Cassandraはネストしているデータに対して、Keyを使ってアクセスを行う。
+また、Column等は、予めデータの型を定義する必要がないため、柔軟にデータを格納できる。
+Cassandraは、スキーマレスな NoSQL データベースである。
diff -r c1b81e802b25 -r c1d7270965c5 jungleTreeBrowser.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jungleTreeBrowser.tex	Wed Feb 01 08:25:09 2017 +0900
@@ -0,0 +1,49 @@
+\chapter{Jungleを使ったアプリケーション}
+本章では、Jungleを使用した例題アプリケーションを記述する。
+
+
+\section{Jungle Tree ブラウザ}
+
+Jungleの木に対する変更において、{\tt JungleTreeEditor}クラスを用いる方法はプログラム上では便利だが、手動で変更するのには向いていない。
+よって、組み込みWEBサーバーであるJettyを使用し、Servletとして木の表示と編集を実現した。
+
+\subsection{木構造の表示}
+JungleTreeブラウザにおいて、Jungle DBはWEBサーバー内に存在し、それから表示に必要なHTMLを生成してブラウザに転送する。
+%図\ref{printNode}は、サーバからデータを送り、ブラウザ上でノードを可視化するまでの流れである。
+この流れは、Jungleの{\tt NodePath}の処理を除けば通常のデータベースのレコードの表示と同等である。
+
+編集するノードのパスはURLで記述されている。例えば、
+{\small
+  \verb! http://localhost/showBoardMessage?!
+    \verb!           bname=Layout&path=-1,0,2!
+}
+などとなる。
+
+以下にJungleTreeブラウザを用いて、ノードを表示するまでの流れを記述する。
+\begin{enumerate}
+\item ユーザーは表示したいノードのパスをURLでJungleTreeブラウザに送る。
+\item JungleTreeブラウザは、WEBサーバ内にあるJungleから、対応した木を取得する。
+\item JungleTreブラウザは、パスで指定した位置のノードを木から取得する。
+\item 取得したノードの中身を、JungleTreeブラウザが表示する。
+\end{enumerate}
+
+
+\subsection{Jungle Tree ブラウザを使った木の編集}
+%図\ref{JungleEdit}はブラウザを用いたJungleの木の更新の流れである。
+以下にJungle Treeブラウザを用いた木の編集の流れを示す。
+\begin{enumerate}
+\item ユーザーはJungleTreeブラウザで編集したいノードを表示するページに移動する 。
+\item ユーザーはJungleTreeブラウザに木の変更要求を送る。
+\item JungleTreeブラウザはWebサーバー内にあるJungleから、対応した木を取得する。
+\item 編集を行う木から、{\tt JungleTreeEditor}クラスを取得し、木の変更を行う。
+\item 木の変更をJungleにコミットする。
+\item 木の変更の結果を表示する。
+\end{enumerate}
+
+パスを使用することにより、木の変更をRestfulに行うことができるように見えるが、木のパスは特定の木の版に固有のものである。
+ブラウザとWEBサーバは、セッションで結合されており、そのセッションが同じ版の木を編集していれば問題なく成功する。
+ただし、編集し終わった時に、他の編集が割り込んでいたら、その編集は無効となる。
+%この点が既存のRDBとは異なる。
+また巨大な木を操作する時には、Pathを直接URLに含むことはできないので、他の工夫が必要になると考えられる。
+このアプリケーションでは任意の木を取り扱うので、木の大きさの現実的な制限を除けば木の設計の問題はない。
+
diff -r c1b81e802b25 -r c1d7270965c5 renderingEngine.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/renderingEngine.tex	Wed Feb 01 08:25:09 2017 +0900
@@ -0,0 +1,156 @@
+\section{HTML Rendering Engine}
+HTMLRenderingEngineは、出力するデータが記述されたContents Tree、出力する形式が記述されたLayout Treeの2つの木構造を持ち、これらを参照しながらhtmlのレンダリングを行う。
+またレンダリングする例題は日記を選択した。
+
+\subsection{Contents TreeのJungle上での表現}
+RenderingEngineではContents Treeに図\ref{contentTree}のように出力するデータを格納した。
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[scale=0.25]{figures/contentTree.pdf}
+\caption{ContentTree}
+\label{contentTree}
+\end{center}
+\end{figure}
+
+
+RootNodeはContentの{\tt title}、日時、レンダリングする時に参照するLayoutTreeのNodeNameを持つ。
+そして子ノードが日記の本文等のデータを持つ。
+表\ref{NodeAttribute}にノードが保持しているContentsの一覧を記述する。
+
+\begin{table}[htb]
+\begin{center}
+\caption{ノードが保持しているContents一覧}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+属性名         & 属性値                             \\ \hline
+component      & レンダリングする際に参照するLayoutTreeのNodeName  \\ \hline
+title          & 日記のタイトル                      \\ \hline
+date(rootNode) & 日記の日時                          \\ \hline
+type           & そのノードが保持しているContextType。 text(日記本文) or image(画像データ)  \\ \hline
+body           & 日記の本文                           \\ \hline
+date(image)    & 画像の保存日時                       \\ \hline
+fileName       & 画像の名前                           \\ \hline
+\end{tabular}
+\label{NodeAttribute}
+\end{center}
+\end{table}
+
+\subsection{Layout}
+htmlの出力形式を定義するLayoutは、複数のComponentからなる。
+表\ref{LayoutTreeTable}に、LayoutTreeの主要要素を記す。
+Layout Treeには図\ref{layoutTree}のようにデータを格納した。
+また、LayoutTreeはノード同士が{\tt NodeName}を用いて参照を行う。
+
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[scale=0.25]{figures/LayoutTree.pdf}
+\caption{LayoutTree}
+\label{layoutTree}
+\end{center}
+\end{figure}
+
+
+\begin{table}[htbH]
+\begin{center}
+\caption{LayoutTreeの主要な要素}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+属性名              & 属性値                     \\ \hline
+NodeName            &ノードの名前。ノード同士の参照時に用いられる。例外としてルートノードだけはdisplayinformationという名前を持つ\\ \hline
+displayComponent    &参照するノードの名前。          \\ \hline
+Name                &この属性名で取得できる値を持つNodeNameを持つノードを参照する。\\ \hline
+use                 &このノードが、どのContentsに対してのLayoutを持つかを記述するタグ。表\ref{tag}にタグとContentsの対応を記述する。\\ \hline
+その他              &css等と同じ様な記述を行う。 例 属性名 {\tt font} 属性値 {\tt fontSize}など                \\ \hline
+\end{tabular}
+\label{LayoutTreeTable}
+\end{center}
+\end{table}
+
+
+Layout Treeは、ルートノードに属性名 {\tt NodeName} 属性値 {\tt displayinformation} の値を持つ(図\ref{layoutTree}では{\tt Node1}が該当する)。
+ルートノードは、子ノードに複数のComponentを保持する(図\ref{layoutTree}では{\tt Node2}、{\tt Node3}がそれに該当する)。
+{\tt Node2}は、属性名 {\tt use} 属性値 {\tt image}のペアでタグを保持しているため、日記の画像表示に対応する記述が行われている。
+{\tt Node3}は、属性名 {\tt use} 属性値 {\tt text}のペアでタグを保持しているため、日記の本文に対応する記述が行われている。
+表\ref{tag}にタグとContentsの対応を記述する。
+
+\begin{table}[htb]
+\begin{center}
+\caption{tagとcontentsの対応}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+tag   & content          \\ \hline
+image & 画像の表示       \\ \hline
+cals  & table            \\ \hline
+date  & 日付の表示       \\ \hline
+text  & 日記の本文       \\ \hline
+title & 日記のタイトル   \\ \hline
+\end{tabular}
+\label{tag}
+\end{center}
+\end{table}
+
+
+Layoutが複数のComponentを参照する際は図\ref{multiComponent}のような木構造を構築する(この木はLayoutTreeの一部であり、本来は参照先のノード等が存在している)。
+\begin{figure}[h]
+\begin{center}
+\includegraphics[scale=0.25]{figures/multiComponent.pdf}
+\caption{複数のComponentを参照するLayout}
+\label{multiComponent}
+\end{center}
+\end{figure}
+
+図\ref{multiComponent}の例では、{\tt diaryMulti@component}は{\tt diaryText@component}と{\tt diaryImage@component}を参照している。
+
+以下に図\ref{contentTree}のContentsTree、図\ref{multiComponent}のLayoutTreeの２つを使用した、レンダリングの流れを記述する。
+\begin{enumerate}
+
+\item  ContentsTreeのルートノードは、属性名 {\tt component} 属性値 {\tt Multi@Component}の組を持つので、LayoutTreeの{\tt Node2}を参照する。
+
+\item {\tt Node2}は自身のNodeNameしか持たないので、子ノードである{\tt Node3、Node4}に記述されているデータの参照を行う。
+
+\item {\tt Node3}は属性名 {\tt displayComponentName} 属性名 {\tt dialyImage@Component}の組を持つため、NodeNameが{\tt dialyImage@Component}のノードを参照している。
+
+\item レンダリングエンジンは、参照先のノードに記述されたルールに則ってHtmlを生成する。
+
+\item {\tt Node3}は、これ以上データを持たないため、次は{\tt Node4}を参照する。
+
+\item {\tt Node4}は属性名 {\tt displayComponentName} 属性名 {\tt dialyText@Component}の組を持つため、NodeNameが{\tt dialyText@Component}のノードを参照している。
+
+\item レンダリングエンジンは、参照先のノードに記述されているルールに則ってhtmlを生成する。
+
+\end{enumerate}
+
+(4)、(7)で参照しているノードに関しては、図\ref{layoutTree}の{\tt Node2、Node3}の様な記述が行われている。
+
+\subsection{Layout Treeのデータ設計}
+Jungleは汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能である。
+しかし、設計を行うことでより効率的に木構造を扱うことが可能になる。
+図\ref{goodLayoutTree}、図\ref{badLayoutTree}は同じデータを格納した２つの木の一部である。
+
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[scale=0.25]{figures/goodLayoutTree.pdf}
+\caption{コードとギャップのないLayoutの格納方法}
+\label{goodLayoutTree}
+\end{center}
+\end{figure}
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[scale=0.25]{figures/badLayoutTree.pdf}
+\caption{コードとギャップのあるLayoutの格納方法}
+\label{badLayoutTree}
+\end{center}
+\end{figure}
+
+
+図\ref{goodLayoutTree}のTreeは、１つのノードにレンダリングに必要な値が全て格納されている。
+そのため、レンダリングを行う際、複数のノードをまたぐ必要が無く、簡潔にコードを書くことができる。
+
+
+
+一方、図\ref{badLayoutTree}の木はレンダリングする際に必要な値が複数ノードに分散されて保存されている。
+そのため、全てのノードを参照し、値を集める処理を行う必要があり、コードの可読性が下がり余計な処理も増えてしまう。
+これより、Jungleの木構造を効率的に扱うためには、設計手法を確立する必要があることがわかる。
+
+