# HG changeset patch # User Shinji KONO # Date 1478774992 -32400 # Node ID b3350fe86bb79f7a943786d6f5ac2fa39c9574ca # Parent 1e543b67f90efb9edb2df24cb4737fd949e1fad0 intorduction diff -r 1e543b67f90e -r b3350fe86bb7 introduction.tex --- a/introduction.tex Thu Nov 10 19:27:20 2016 +0900 +++ b/introduction.tex Thu Nov 10 19:49:52 2016 +0900 @@ -1,6 +1,6 @@ \section{Jungle DBによるインピーダンスミスマッチの解決} -プログラム中のデータ構造とRDBの表構造には大きなギャップがある。 +プログラム中のデータ構造とRDBの表構造には大きなギャップがある。これはインピーダンスミスマッチと呼ばれている。 例えばRPGゲーム中のユーザが持つアイテムという単純なものでもRDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 プログラム中ではユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 レコードをプログラム中のオブジェクトに対応させるOR Mapという技術では、これを本質的には解決することはできない。 @@ -8,9 +8,34 @@ しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 並列処理を含むプログラミングからの要請とのミスマッチが残っている。 + +\subsection{非破壊的木構造データベースJungle} + 当研究室では、これらの問題を解決した煩雑なデータ設計が必要のない Jungle データベースを提案している。 Jungleはプログラム内部に直接木構造を構築し、そのルートをアトミックに入れ替えることでトランザクションを実現する。 また木構造の表現に単一リンクを用い、変更を非破壊的つまり、元の木を保存しつつ、新しい木を構築する方法を取る。 これにより複数のスレッドからでも木構造を安全に扱うことができる。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にいちいちデータベースに問い合わせる必要がない。また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。 本研究では実際にJungle上に実際に複数のアプリケーションを実装し、Jungleの表現力、機能の十分性、実用的な性能があるか、実証実験を行った。その時に明らかになった木構造データベースの問題点についても考察する。 + +Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。 +ノードは自身の子のListと属性名と属性値の組を持ち、データベースのレコードに相当する。 +通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。 + +Jungleは データの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う。 +これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安定して読み出せるという特徴がある。 +しかし、書き込み時の手間は大きくなる。 + +通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJasonで記述された構造をデータベースを設計することなく読み込むことが可能であり、実際、そういう機能が実装されている。この木をそのままデータベースとしてしようすることも可能である。しかし、木の変更の手間は木の構造に依存する。 +特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、 +十分な性能を出すことはできない。逆に言えば、正しい木の設計を行えば高速な処理が可能である。 + +Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを握れば、その上で木構造として自由にアクセスして良い。 +Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。 +持続性のある分散のードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの +部分について考察する。 + +本論文では、 +実際に、Jungleを用いたアプリケーションをいくつか構築し、どのような木構造がアプリケーションに向いているかを調べる。 +その際の設計指針はRDBとは異なり複雑である。これはプログラムのデータ構造そのものの設計に相当する。 +Jungleは、その意味でプログラミングの視点から見たデータベースになっている。 diff -r 1e543b67f90e -r b3350fe86bb7 jungle.tex --- a/jungle.tex Thu Nov 10 19:27:20 2016 +0900 +++ b/jungle.tex Thu Nov 10 19:49:52 2016 +0900 @@ -1,9 +1,14 @@ -\section{非破壊的木構造データベースJungle} -\subsection{Jungleのデータ構造} +\section{JungleのAPI} + Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。 -ノードは自身の子のListと属性名と属性値の組を持ち、ノードの位置はNodePathで表される。 -Jungleは非破壊的木構造であるためデータの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う。 -そのため、読み込みと書き込みを同時に行うことができる。 +それぞれの木には名前が付いている。 +木の中のノードの位置はNodePathで表される。 +指定されたノードに対する編集を行うJungleTreeEditorを呼び出す。 +編集し終わった後に名前に対する木のルートをアトミックに変更するcommit APIを呼び出す。 +本節ではJungle DBのAPIについて解説する。 + + +\subsection{Jungleのデータ構造} \subsection{木の生成} Jungleには木を生成、管理を行うAPI(*表\ref{jungleAPI})が実装されている。