Mercurial > hg > Papers > 2014 > toma-master

comparison paper/chapter3.tex @ 48:88b11a3afb93

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
describe deos
author Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
date Fri, 07 Feb 2014 01:02:26 +0900
parents e32c9a53310c
children 0a8d66c9ccd1
comparison
equal deleted inserted replaced
47:e32c9a53310c 48:88b11a3afb93
1 \chapter{Haskellによる\\並列データベースの実装}\label{ch:impl} 1 \chapter{Haskellによる\\並列データベースの実装}\label{ch:impl}
2 本章では, 並列データベース Jungle の実装について述べる. 2 　本章では, 並列データベース Jungle の実装について述べる.
3 3
4 \section{木構造データベース Jungle} 4 \section{木構造データベース Jungle}
5 非破壊的木構造データベース Jungle は, Haskell で実装された並列データベースである. 5 非破壊的木構造データベース Jungle は, Haskell で実装された並列データベースである.
6 非破壊的木構造の方法に則った関数を提供する. 6 非破壊的木構造の方法に則った関数を提供する.
7 7
22 Jungle のデータ型について, ひとつずつ説明する. 22 Jungle のデータ型について, ひとつずつ説明する.
23 23
24 \begin{table}[!htbp] 24 \begin{table}[!htbp]
25 \label{tab:components} 25 \label{tab:components}
26 \begin{center} 26 \begin{center}
27 \begin{tabular}{|c||c|c|} \hline
28 型名 & 概要 \\ \hline
29 Jungle & 木の作成・取得を担当する. \\ \hline
30 Tree & 木の名前とルートノードの情報を保持している. \\ \hline
31 Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline
32 \end{tabular}
33 \end{center}
34 \caption{Jungle が持つデータ型}
35 \end{table}
36
37 \begin{table}[!htbp]
38 \label{tab:components}
39 \begin{center}
27 \begin{tabular}{|c||c|} \hline 40 \begin{tabular}{|c||c|} \hline
28 型名 & 概要 \\ \hline 41 型名 & データ構造 \\ \hline
29 Jungle & 木の作成・取得を担当する. \\ \hline 42 Jungle & Jungle (TVar (Map String Tree)) \\ \hline
30 Tree & 木の名前とルートノードの情報を保持している. \\ \hline 43 Tree & Tree (TVar Node) String \\ \hline
31 Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline 44 Node & Node (Map Int Node) (Map String ByteString) \\ \hline
32 \end{tabular} 45 \end{tabular}
33 \end{center} 46 \end{center}
34 \caption{Jungle が持つデータ型} 47 \caption{データ型のデータ構造}
35 \end{table} 48 \end{table}
36 49
37 \subsection{Jungle} 50 \subsection{Jungle}
38 Jungle は木構造の集まりを表現する. 51 Jungle は木構造の集まりを表現する.
39 木には名前がついており, Tree の情報と一緒に保持している. 52 木には名前がついており, Tree の情報と一緒に保持している.
91 これは, 各スレッドから木構造を新たに作成できるようにするためである. 104 これは, 各スレッドから木構造を新たに作成できるようにするためである.
92 STM は, スレッド間でデータを共有するためのツールである. STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される. 105 STM は, スレッド間でデータを共有するためのツールである. STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される.
93 Jungle のデータ構造の Map の前に付いている TVar というのは, Transactional variablesの略で, STM で管理する変数に対して利用する. 106 Jungle のデータ構造の Map の前に付いている TVar というのは, Transactional variablesの略で, STM で管理する変数に対して利用する.
94 107
95 \subsubsection{Jungle と木の作成} 108 \subsubsection{Jungle と木の作成}
96 Jungle は, Mapで木を管理しているため, 複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）. 109 Jungle は, 複数の非破壊的木構造を持つため、Map で木を管理している（図\ref{fig:jungle}）.
97 110
98 \begin{figure}[!htbp] 111 \begin{figure}[!htbp]
99 \begin{center} 112 \begin{center}
100 \includegraphics[scale=0.7]{./images/jungle.pdf} 113 \includegraphics[scale=0.7]{./images/jungle.pdf}
101 \end{center} 114 \end{center}