title: ソフトウェア内部で使用するのに適した木構造データベースJungle
author: Tatsuki Kanagawa
profile: 琉球大学理工学研究科
lang: Japanese
code-engine: coderay
# 研究目的
[](要素を説明するところではサブセクションにしてある)
プログラムからデータを分離して扱うデータベースにはデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。

- ORMapper
- Json

などにより、不定形のデータ構造を格納できる機能拡張もなされてきたが、複雑な構造をメモリ上に構築しているため、これらの方法でもまだギャップがある。

今回提案する木構造データベースJungleはプログラム内部に直接木構造を構築する。
トランザクションは木のルートをアトミックに入れ替えることで実現する。
また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。

# この発表では

- Jungleデータベースの構造
- WebServer(BBS)
- maTrix
- RenderingEngine
- まとめ

Jungleデータベースの構造とこれを用いたアプリケーション、実装時に発生した問題と解決方法について解説する。

# Jungleデータベース

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

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

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

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

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

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

以降はJungleの構造をAPIとともに紹介。
[](70分あるので入れてもいいかな)

# 木の生成

Jungleは複数の木を名前を利用して管理しており、名前により作成・編集・削除を行う。
Jungleクラスの木の生成、管理を提供するAPIは以下のようになっている。

``` Java
/* If the name of the tree duplicates, it fails and returns null */
JungleTree createNewTree(String treeName);

/* If there is no matching Tree name, it fails and returns null  */
JungleTree getTreeByName(String treeName);
```

# 木のノード

Jungleの木は、複数のノードの集合でできている。
ノードは、自身の子のListと属性名と属性値の組でデータをもつ。
ノードへTreeNodeクラスにより提供しているAPIでアクセスする。

``` Java
Children getChildren();
Attribute getAttribute();
```

# ノードのChildren

Childrenクラスで提供されているAPIでTreeNodeにアクセスできる。

``` Java
// Children.java
int size();
Either<Error, TreeNode> at(int num);
```

## Eitherクラス

TreeNodeを取ってくる場合Eitherで比較する。

``` Java
Either<Error, JungleTreeEditor> either = tree.getRootNode ().getChildren ().at (0);
if(either.isA()) {
  // throw  Exception
}
TreeNode node = either.b();
```

# ノードのAttribute

Attributeクラスで提供されているAPIでノードの値にアクセスできる。

``` Java
// Attribute.java
ByteBuffer get(String key);
String getString(String key);
```

# 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)