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  Expection
}
TreeNode node = either.b();
```

# ノードのAttribute

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

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

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

## maTrix

[](そのまま利用しているので書き直す必要あり)
許認可管理アプリケーション
maTrixは、人物、役職、役割、権限、組織の木構造のデータとポリシーファイルを持つ。
ポリシーファイルは、データに対するアクセス要求が許可されるか否認されるかを判断するためのルールを、誰が(Target)、何を(Resource)、どうできるか(Action)の3つの要素で記述されている。
ポリシーファイルは組織構造中の人や役職をidを用いて参照している。つまり、ポリシーファイルを用いて許認可を下すためには、その人がどこの組織に所属して、その役割がどの権限を持っているかを返す検索が必要になる。

## BBS

Jetty上で動くServletからのデータベースの接続先としてJungle databaseを用いる。

## Rendering Engine



## Unity

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