\chapter{序論} \label{ch:introduction}
\pagenumbering{arabic}

\section{研究背景と目的}
ブロードバンド環境やモバイル端末の普及により、ウェブサービスの利用者数は急激に伸びている。
リクエスト数の増加を予想することは困難であり、負荷が増大した場合に容易に拡張できるスケーラビリティが求められる。
ここでいうスケーラビリティとは、利用者や負荷の増大に対し、単なるリソースの追加のみでサービスの質を維持することのできる性質のことである。

ウェブサービスにおけるスケーラビリティを実現するための難点の一つとして、データベースが挙げられる。
本研究の目的は、スケーラビリティを実現するデータベースの実装である。
ウェブサービスにおけるスケーラビリティを実現するためには、並列にデータにアクセスできる設計が必要となる。
本研究では並列にデータへアクセスする手法として、非破壊的木構造を利用する。
非破壊的木構造では、排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる。

データベースの実装には、純粋関数型言語 Haskell を用いる。
Haskell は、モダンな型システムを持ち、型推論と型安全により簡潔で信頼性の高いプログラムを書くことが可能である\cite{types}。
また、Haskellは純粋であるため、関数は引数が同じならば必ず同じ値を返すことが保証されている。
これは、並列処理において並列化に適した部分が分かりやすくなるというメリットがあり、また状態に依存したバグから解放されることも意味する。

本論文では、Haskellを用いて非破壊的木構造データベースを実装し、スケーラビリティを実現できることを明らかにする。
\newpage

\section{本論文の構成}

本論文では、データベースの実装によって得られた知見について述べる。

第\ref{ch:haskell}章では、純粋関数型言語 Haskell の特徴及び Haskell を用いた並列プログラミングについて述べる。
第\ref{ch:design}章では、非破壊的木構造を用いたスケーラビリティ確保の方法について考察し、Haskellを用いたデータベースの設計について述べる。
第\ref{ch:impl}章では、Haskellを用いた非破壊的木構造データベースの実装と、その利用方法について述べる。
第\ref{ch:bench}章では、実装したデータベースの性能評価を行う。
実装したデータベースを用いて、簡単な掲示板ウェブアプリケーションを開発し、Java による非破壊的木構造データベースとの比較を行う。