\chapter{ソフトウェア内部で使用するのに適した 木構造データベース Jungle}
\pagenumbering{arabic}
\section{研究目的}
プログラムからデータを分離して扱うデータベースには、
プログラム中のデータ構造と Relational DataBase(RDB) の表構造のインピーダンスミスマッチという問題がある。
データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、
データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。


そこで当研究室では、これらの問題を解決した、煩雑な設計を行わずプログラム内部に木構造を格納できるデータベース Jungle を提案している。
Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、
木のルートをアトミックに入れ替えることでトランザクションを実現する。
プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。
Jungleは、全体の整合性ではなく、木ごとに閉じた局所的な整合性を保証している。
また、整合性のある木同士をマージすることで新しい整合性のある木を作り出すことも可能であるため、データの伝搬も容易である。

Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。
また、Indexの構築も大幅なネックとなっていた。
そこで、本研究では、Jungleの木の構築・編集機能の改善を行う。
その後、実際にJungleを使用したアプリケーションを開発・運用する。

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


\section{本論文の構成}
本論文では、初めに既存のデータベースについて記述する。
第 3 章では、Jungleの基本的な機能・APIについて記述する。
第 4 章では、Jungleに新しく加えた構成要素について述べる。
第 5 章では、改良後のIndexの実装に使用する非破壊 TreeMap の実装について記述する。
第 6 章では、Indexの差分 Update の実装について記述する。
第 7 章では、線形の木を、正順でO(1)で構築することが可能な、Differential Jungle Tree の実装について記述する。
第 8 章では、自身が Index としての機能を持つ、 Red Black Jungle Treeの実装について記述する。
第 9 章では、実際に Jungle を使用した、例題アプリケーションの実装について記述する。
第 10 章では、今回実装した機能の測定について記述する。