title: ソフトウェア内部で使用するのに適した木構造データベースJungle
author: Tatsuki Kanagawa
author: Kazuma Takeda
author: Shinji Kono
profile: 琉球大学
lang: Japanese
code-engine: coderay
# データベースの歴史

コンピュータでは常に簡略化が行われてきた。
[](入りをどうするかまだ)

# 階層型データベース

データの関係性をツリー構造で定義し、プログラム内部ではその定義を利用してデータへのアクセスする。

## 問題点

親子関係でしかデータを表現できないため、
新しい木構造を作るたびにデータ重複が発生し、冗長化する。


# ネットワーク型データベース

CODASYLデータモデルともいう。

参照関係で表現が可能になった。そのため、複数参照されているものを一箇所にまとめることで
階層型のボトルネックであったデータ冗長化を排除することができる。

データをノード単位で整理し、データ間の関係性を定義する。

## 問題点

データ間のリンク関係は物理的な実装に近かった。
そのため、安易にはデータの変更を行うことができないと言った問題がある。

# CODASYLデータモデル

COBOLで多く用いられたデータベースの仕様。

現在のネットワーク型のほとんどがこれを準拠に作られている。
この特徴としてはデータ操作言語とデータ記述言語を分離している。

# リレーショナルデータベース
階層型データベースやネットワーク型データベースの持つ問題点を解決し、データとプログラムの独立性を高めたデータベース。

## 問題点

プログラムからデータを分離して扱うデータベースではデータ構造とRDBの表構造のインピーダンス・ミスマッチが起こる。

# インピーダンス・ミスマッチ

もともとは電気工学の言葉。
抵抗の異なる素材の間に電磁波を流すと、境界面で反射が起こり、効率よく伝達できないことを意味する。

つまり、データベースの世界ではオブジェクト指向プログラミングで使用するデータ構造とリレーショナルデータベースに格納されているデータの間にあるギャップのことをいう。
この問題に対応するためにO/R Mapperと呼ばれるフレームワークを使う。

# O/R Mapper

オブジェクトに対する操作を行うとORMapperがSQLを発行し、処理を行ってくれる。
SQLを直接扱う場面は減るがSQLを理解しなくてもいいというわけではない。

Javaや.NETにもORMapperがあるが、PythonのpeeweeやRubyのActiveRecordなどスクリプト言語にもある。


# 近年

NoSQLと呼ばれるデータベースが開発、利用されている。

CPUやメモリに比べて低速なストレージ性能を分散させ、
ネットワーク型のボトルネックを極力排すること目的とされている。

# Key-Value Store

データをKeyとValueのHash形式でもつ。

完全一致検索しかできないが高速で動作する。

# カラム指向

RDBと同様に表を持つ。

カラム単位でデータを保持する。

大量のデータを読み書きするのに最適とされている。

例:

<div style="text-align: center;">
　<img src="./images/cassandra.png" alt="message" width="300">
</div>

# ドキュメント指向データベース

スキーマが必要ななく使用できる。

複雑な検索条件でデータを取得できる。

例:

<div style="text-align: center;">
　<img src="./images/mongo.png" alt="message" width="300">
</div>

# mongo Database

<div style="text-align: center;">
　<img src="./images/mongo.png" alt="message" width="300">
</div>

ドキュメント指向型のデータベースである。

NoSQLのパフォーマンス、スケーラビリティに優れている。

なお、パフォーマンスを向上させるため、トランザクション、リレーショナルの機能は実装されていない。

Key-Value Storeでは完全一致検索しかできないが、
RDBのような検索クエリの機能を持たせることで複雑な検索が可能になっている。

# 現在の課題

コンピュータのCPU性能は格段によくなった。しかし、これ以上CPUの性能が大幅に向上するとは思えない。

一方、データは膨大化している。

CPUを物理的に増やすことで、解決はできるが、有限な物であるため一時的な解決方法にしかならない。

そこで並列処理という手法が考えられる。

トランザクションの機能を排除した、MongoDBでは並列で動くアプリケーションには向いていない。

RDBではトランザクションが実装されているのでもちろん並列アプリケーションに向いていると言える。
しかし、先ほど述べた、オブジェクト指向プログラミングとリレーショナルデータベースの間ではインピーダンス・ミスマッチが起こってしまう。

# 提案

データベースの背景を踏まえ、
今回トランザクションの機能を備え、スケーラビリティにも優れた木構造データベースJungleを提案する。

トランザクションは木のルートをアトミックに入れ替えることで実現する。
また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。

まずはJungleの仕様部分から説明する。

# Jungleデータベース

JungleデータベースはJavaで実装されている。
木構造型のデータベースで、プログラム上に直接木構造を構築する。

木は複数のノードの集合でできており、その木の集合によりJungleが構成されている。
ノードは自身の子のリストと属性名と属性値の組でデータを持つ。これはデータベースのレコードに値する。
通常のレコードと異なるのは、ノードに子どもとなる複数のノードがつくところである。
なお、親から子への片方向の参照しか持たない。

[]( 理由はノードをコピーするときにその参照までもコピーしないといけないし、特定のノードから探って行くので子は誰が知る必要はない)

[]( ノードの図入れた方が良い？)

データの変更は一度生成した木を上書きせず、ルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。
その際にルートをアトミックに入れ替える。
[](失敗時の具体的な意味Either)

<div style="text-align: center;">
　<img src="./images/nonDestractTreeEdit.pdf" alt="message" width="600">
</div>

# JungleのAPI

Jungleは複数の木を名前を利用して管理しており、名前により作成・編集・削除を行う。
まずはJungleの例を見てもらいたい。

以下のコードは、ルートノードの2番目の子どもから、属性名"name"とペアになっている属性値を取得する。

``` Java
JungleTree tree = jungle.getTreeByName("TreeName");
TreeNode root = tree.getRootNode();
Children children = root.getChildren();
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    throw new IOException();
TreeNode child = either.b();
Attribute attribute = child.getAttribute();
String value = attribute.getString("name");
```

# NodePath

Jungleでは、木のノードの位置をNodePathクラスを使って表す。

NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。

また、ルートノードは例外として-1と表記される。

<div style="text-align: center;">
　<img src="./images/NodePath.pdf" alt="message" width="400">
</div>


# Eitherクラス

Jungleでは例外を投げる時にEitherクラスを用いて行う。

- 失敗時はA
- 成功時はB

を包んで返す。

``` Java
Either<Error,TreeNode> either = children.at(2);
if (either.isA()) 
    throw new IOException();
TreeNode child = either.b();

```

[](なぜ Functionalに書かなかった？もしかしてJava8からだから実装当時はまだなかった？)

# Jungle を用いたアプリケーション

Jungleの特性を生かし、アプリケーションを構築した。

- maTrix
- BBS
- Rendering Engine
- Unity

# maTrix

実際に企業で運用されている許認可管理アプリケーション。
人物、役職、役割、権限、組織の木構造のデータとポリシーファイルを持つ。

maTrixのデータ構造は以下のようになっている。

<div style="text-align: center;">
　<img src="./images/TreePersonJungle.pdf" alt="message" width="600">
</div>

## ポリシーファイル

データに対するアクセス要求が許可されるか否認されるかを判断するためのルール、

- 誰が(Target)
- 何を(Resource)
- どうできるか(Action)

の３つの要素を持っている。
maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う。

ポリシーファイルは組織構造中の人や役職をidを用いて参照している。

- 許認可を下すためには、その人がどこの組織に所属して、その役割がどの権限を持っているかを返す検索が必要。

# maTrixでは

- 組織構造は、それぞれの木構造がidを用いた参照を行う
- 過去のアクセス要求を全て保存する
- ファイルポリシーを用いた場合の人物検索

## maTrixでのJungleの問題点

- JungleではIndexを持っていない
- 検索部分がない

# 改良

Indexをつけて、検索部分も実装した。
子から親への参照が必要になったのでParentIndexを実装した

## ParentIndex

ノードを投げるとその親がReturnされる。

# 性能評価

mongoDBとの性能を比較した。

# BBS

JungleTreeEditorは手動での変更には向いていない。
ブラウザ上で変更できるようにした。
仕様は以下の通りである。

- WebサーバJettyを利用し、 ServletによりViewを生成
- JungleDBをJettyに組み込む

## 木構造の表示

NodePathを除けば、通常のデータベースのレコードと同じである。

NodePathはURLのGetパラメータとして指定する。

``` HTML

http://localhost/showBoardMessage?bname=Layout&path=-1,0,2

```
[](イメージしやすい図があれば良さそう)

## 木構造の編集

変更したいページに移動し、木を取得し、
データをPostすることでCreateもしくは、Updateを行う。

# HTML Rendering Engine

Jungleの特性を生かしたRendering Engineを開発した。
今回は例題として、日記(ブログ)を選択した。

# 構造

- LayoutTree

出力する形式が記述された木

- ContentTree

出力するデータが記述された木

これら２つを参照しながらレンダリングを行う。




# Unity

ゲームエンジンUnity上で動くデータベースとしてJungleをC#に書き換え、実装を行なった。


# まとめ

今回は...


[](プロシン発表時間 セッション4 1/7 8:50 - 10:10)