\section{はじめに}
\subsection{Jungle DBによるインピーダンスミスマッチの解決}
プログラム中のデータ構造とRDBの表構造には大きなギャップがある。これはインピーダンスミスマッチと呼ばれている。
例えばRPGゲーム中のユーザが持つアイテムという単純なものでもRDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。
プログラム中ではユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。
レコードをプログラム中のオブジェクトに対応させるOR Mapという技術では、これを本質的には解決することはできない。
そこで、 MySQLやPosgreSQLなどはJsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。
しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、
並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、
並列処理を含むプログラミングからの要請とのミスマッチが残っている。

\subsection{非破壊的木構造データベースJungle}

当研究室では、これらの問題を解決した煩雑なデータ設計が必要のない Jungleデータベースを提案している。

Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。
ノードは自身の子のListと属性名と属性値の組を持ち、データベースのレコードに相当する。
通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
また、ノード同士はListを用いた参照で木構造を構築しているため、親から子への片方向の参照しか持たない。


Jungleは データの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う。
これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安定して読み出せるという特徴がある。
しかし、書き込み時の手間は大きくなる。

通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJasonで記述された構造をデータベースを設計することなく読み込むことが可能であり、実際、そういう機能が実装されている。この木をそのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
特に非破壊木構造を採用しているJungleでは木構造の変更の手間はO(1)からO(n)となる。つまり、アプリケーションに合わせて木を設計しない限り、
十分な性能を出すことはできない。逆に言えば、正しい木の設計を行えば高速な処理が可能である。

Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを握れば、その上で木構造として自由にアクセスして良い。
Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの
部分について考察する。

本論文では、
実際に、Jungleを用いたアプリケーションをいくつか構築し、どのような木構造がアプリケーションに向いているかを調べる。
その際の設計指針はRDBとは異なり複雑である。これはプログラムのデータ構造そのものの設計に相当する。
Jungleは、その意味でプログラミングの視点から見たデータベースになっている。