--- a/Slide/prosym.md	Fri Dec 23 12:57:48 2016 +0900
+++ b/Slide/prosym.md	Fri Dec 23 17:22:01 2016 +0900
@@ -1,145 +1,61 @@
 title: ソフトウェア内部で使用するのに適した木構造データベースJungle
-author: Tatsuki Kanagawa
-author: Kazuma Takeda
-author: Shinji Kono
+author: Tatsuki Kanagawa, Kazuma Takeda, Shinji Kono
 profile: 琉球大学
 lang: Japanese
 code-engine: coderay
-# データベースの歴史
-
-コンピュータでは常に簡略化が行われてきた。
-[](入りをどうするかまだ)
-
-# 階層型データベース
-
-データの関係性をツリー構造で定義し、プログラム内部ではその定義を利用してデータへのアクセスする。
 
-## 問題点
-
-親子関係でしかデータを表現できないため、
-新しい木構造を作るたびにデータ重複が発生し、冗長化する。
+# はじめに
 
-
-# ネットワーク型データベース
-
-CODASYLデータモデルともいう。
+データベース
 
-参照関係で表現が可能になった。そのため、複数参照されているものを一箇所にまとめることで
-階層型のボトルネックであったデータ冗長化を排除することができる。
-
-データをノード単位で整理し、データ間の関係性を定義する。
-
-## 問題点
-
-データ間のリンク関係は物理的な実装に近かった。
-そのため、安易にはデータの変更を行うことができないと言った問題がある。
-
-# CODASYLデータモデル
+プログラムからデータを分離して扱うデータベースには、
+プログラム中のデータ構造とRDBの表構造の<u>インピーダンスミスマッチ</u>という問題がある。
 
-COBOLで多く用いられたデータベースの仕様。
-
-現在のネットワーク型のほとんどがこれを準拠に作られている。
-この特徴としてはデータ操作言語とデータ記述言語を分離している。
+データベースのレコードをプログラム中のオブジェクトとして使える<u>OR Mapper</u>や、
+データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
 
-# リレーショナルデータベース
-階層型データベースやネットワーク型データベースの持つ問題点を解決し、データとプログラムの独立性を高めたデータベース。
+しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。
 
-## 問題点
-
-プログラムからデータを分離して扱うデータベースではデータ構造とRDBの表構造のインピーダンス・ミスマッチが起こる。
 
 # インピーダンス・ミスマッチ
 
-もともとは電気工学の言葉。
-抵抗の異なる素材の間に電磁波を流すと、境界面で反射が起こり、効率よく伝達できないことを意味する。
+プログラム中のデータ構造とRDBの表構造には大きなギャップがある。これはインピーダンスミスマッチと呼ばれている。
 
-つまり、データベースの世界ではオブジェクト指向プログラミングで使用するデータ構造とリレーショナルデータベースに格納されているデータの間にあるギャップのことをいう。
-この問題に対応するためにO/R Mapperと呼ばれるフレームワークを使う。
+例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。
+
+プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。
 
 # O/R Mapper
 
-オブジェクトに対する操作を行うとORMapperがSQLを発行し、処理を行ってくれる。
-SQLを直接扱う場面は減るがSQLを理解しなくてもいいというわけではない。
-
-Javaや.NETにもORMapperがあるが、PythonのpeeweeやRubyのActiveRecordなどスクリプト言語にもある。
-
-
-# 近年
+データベースのレコードをプログラム中のオブジェクトとして使える。
 
-NoSQLと呼ばれるデータベースが開発、利用されている。
-
-CPUやメモリに比べて低速なストレージ性能を分散させ、
-ネットワーク型のボトルネックを極力排すること目的とされている。
-
-# Key-Value Store
-
-データをKeyとValueのHash形式でもつ。
+オブジェクトに対する操作を行うとORMapperがSQLを発行し、処理を行ってくれる。
 
-完全一致検索しかできないが高速で動作する。
-
-# カラム指向
-
-RDBと同様に表を持つ。
-
-カラム単位でデータを保持する。
-
-大量のデータを読み書きするのに最適とされている。
+PythonのpeeweeやRubyのActiveRecordなどスクリプト言語にもある。
 
-例:
+しかしレコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、これを本質的には解決することはできない。
 
-<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のパフォーマンス、スケーラビリティに優れている。
+そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。
 
-なお、パフォーマンスを向上させるため、トランザクション、リレーショナルの機能は実装されていない。
-
-Key-Value Storeでは完全一致検索しかできないが、
-RDBのような検索クエリの機能を持たせることで複雑な検索が可能になっている。
-
-# 現在の課題
-
-コンピュータのCPU性能は格段によくなった。しかし、これ以上CPUの性能が大幅に向上するとは思えない。
+しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、
+並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、
+並列処理を含むプログラミングからの要請とのミスマッチが残っている。
 
-一方、データは膨大化している。
-
-CPUを物理的に増やすことで、解決はできるが、有限な物であるため一時的な解決方法にしかならない。
+データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
 
-そこで並列処理という手法が考えられる。
-
-トランザクションの機能を排除した、MongoDBでは並列で動くアプリケーションには向いていない。
-
-RDBではトランザクションが実装されているのでもちろん並列アプリケーションに向いていると言える。
-しかし、先ほど述べた、オブジェクト指向プログラミングとリレーショナルデータベースの間ではインピーダンス・ミスマッチが起こってしまう。
+しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。
 
 # 提案
 
-データベースの背景を踏まえ、
-今回トランザクションの機能を備え、スケーラビリティにも優れた木構造データベースJungleを提案する。
+当研究室ではこれらの問題を解決した煩雑なデータ設計が必要のないJungleデータベースを提案している。
 
 トランザクションは木のルートをアトミックに入れ替えることで実現する。
 また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。
+プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。
+また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。Jungleは分散構成も可能である。
+
 
 まずはJungleの仕様部分から説明する。
 
@@ -151,12 +67,9 @@
 木は複数のノードの集合でできており、その木の集合によりJungleが構成されている。
 ノードは自身の子のリストと属性名と属性値の組でデータを持つ。これはデータベースのレコードに値する。
 通常のレコードと異なるのは、ノードに子どもとなる複数のノードがつくところである。
+
 なお、親から子への片方向の参照しか持たない。
 
-[]( 理由はノードをコピーするときにその参照までもコピーしないといけないし、特定のノードから探って行くので子は誰が知る必要はない)
-
-[]( ノードの図入れた方が良い？)
-
 データの変更は一度生成した木を上書きせず、ルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。
 その際にルートをアトミックに入れ替える。
 [](失敗時の具体的な意味Either)
@@ -165,37 +78,44 @@
 　<img src="./images/nonDestractTreeEdit.pdf" alt="message" width="600">
 </div>
 
-# JungleのAPI
+# Jungleの木
 
 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");
+// Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す
+JungleTree  createNewTree(String treeName)
+
+// JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す
+JungleTree  getTreeByName(String treeName)
+
 ```
 
-# NodePath
+# Jungleの木
+
+Jungleの例を記載する。
+
+以下のコードは、Jungleの木を"TreeName"で生成し取得する。
 
-Jungleでは、木のノードの位置をNodePathクラスを使って表す。
+``` Java
+jungle.createNewTree("TreeName");
+JungleTree tree = jungle.getTreeByName("TreeName");
+```
 
-NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。
+# TreeNode
 
-また、ルートノードは例外として-1と表記される。
+Jungleが保持している木は、複数のノードの集合で出来ている。
+ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
+ノードに対するアクセスは、TreeNodeクラスに記述されているAPIを用いて行われる。
 
-<div style="text-align: center;">
-　<img src="./images/NodePath.pdf" alt="message" width="400">
-</div>
+``` Java
+// ノードの子供を扱うChildrenオブジェクトを返す
+Children  getChildren()
 
+// ノードが保持しているデータを扱うAttribteオブジェクトを返す
+Attribute getAttribute()
+
+```
 
 # Eitherクラス
 
@@ -214,7 +134,96 @@
 
 ```
 
-[](なぜ Functionalに書かなかった？もしかしてJava8からだから実装当時はまだなかった？)
+# JungleのAPI
+
+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");
+
+```
+
+# Jungleの木の編集
+
+Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。
+
+JungleTreeEditorクラスには編集を行うために、次の定義されているAPIが実装されている。
+また、ノードを指定して編集を行う際にNodePathクラスを用いる。
+
+# NodePath
+
+Jungleでは、木のノードの位置をNodePathクラスを使って表す。
+
+NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。
+
+また、ルートノードは例外として-1と表記される。
+
+<div style="text-align: center;">
+　<img src="./images/NodePath.pdf" alt="message" width="400">
+</div>
+
+# ノードの追加、削除
+
+``` Java
+// 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置子ノードを追加
+Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos)
+
+// 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置の子ノードを削除
+Either<Error, JungleTreeEditor> deleteChildAt( NodePath path, int pos)
+```
+
+# ノードに対してデータの挿入
+
+``` Java
+// 変数pathで指定した場所にあるノードに、属性名 変数key 属性値 変数valueのペアで値を挿入
+Either<Error, JungleTreeEditor> putAttribute( NodePath path, String key, ByteBuffer value)
+
+// 変数pathで指定した場所にあるノードが持つ、属性名 変数keyとペアで保存されているデータを削除
+Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, String key)
+
+```
+
+# 移動、ルートノードの追加、コミット
+
+``` Java
+// 変数pathで指定した場所にある、ノードの変数numで指定された位置の子供を変数moveの方向に移動
+Either<Error, JungleTreeEditor> moveChild( NodePath path, int num, String move)
+
+// ルートノードの上に新しいルートノードを追加。線形の木を作る際に使用することで計算量をO(n)からO(1)にできる
+Either<Error, JungleTreeEditor> pushPop()
+
+// 木へ行った変更をコミット。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗
+Either<Error, JungleTreeEditor> success()
+```
+
+
+# JungleのAPI
+
+Jungleの木を編集する例を記載する。
+以下のコードは木からEditorを取得し、変数editorNodePathので指定したノードに新しい子ノードを追加したものである。
+
+``` Java
+JungleTreeEditor editor = tree.getTreeEditor();
+DefaultNodePath editNodePath = new DefaultNodePath();
+Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
+if (either.isA()) 
+  throw new IllegalStateException();
+editor = either.b();
+editor.success();
+
+```
+
+[]()
 
 # Jungle を用いたアプリケーション
 
@@ -257,12 +266,7 @@
 - 過去のアクセス要求を全て保存する
 - ファイルポリシーを用いた場合の人物検索
 
-## maTrixでのJungleの問題点
-
-- JungleではIndexを持っていない
-- 検索部分がない
-
-# 改良
+# 実装部分
 
 Indexをつけて、検索部分も実装した。
 子から親への参照が必要になったのでParentIndexを実装した
@@ -271,37 +275,6 @@
 
 ノードを投げるとその親が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を開発した。
@@ -320,16 +293,28 @@
 これら２つを参照しながらレンダリングを行う。
 
 
-
-
-# Unity
-
-ゲームエンジンUnity上で動くデータベースとしてJungleをC#に書き換え、実装を行なった。
-
-
 # まとめ
 
-今回は...
+本研究では非破壊データベースJungleにJungleTreeブラウザ、許認可管理アプリケーションmaTrix、HtmlRenderingEngineの3つを実装した。
+
+JungleTreeブラウザを実装したことにより、ブラウザから木構造の確認、編集が行えるようになった。
+
+許認可管理アプリケーションmaTrixの実装を通して、Jungleに実用データベースとしての表現力、機能の十分性、実用的な性能があるか実証実験を行った。
+maTrixは複数の木がお互いにIdを用いた参照を行い組織構造を表現していたが、JungleではIndexを用いた参照で表現した。
+また、測定の結果mongoDBの約500倍高速に動作した。
+これはJungleがon memoryなのに対し、MongoDBはmmapを用いてデータにアクセスしているからである。
+
+maTrixの実装により、Jungleは、実用アプリケーションを実装できるほどの表現力、機能、性能があることを証明できた。
 
+最後に、Jungleを使った例題アプリケーションとしてRenderingEngineの実装を行った。
+その際Jungleのデータ構造でプログラムの処理量、コードの可読性が異なることがわかった。
+性能測定では、データ設計を行った木構造を利用したほうが高速に動作した。
+これはノードをたどる必要が無いからである。
+しかし、単純に1つのノードにデータを記述するとコードの可読性が落ちてしまうこともあるため、可読性と速度を両立できる設計手法を確立する必要があることがわかった。
+
+JungleはRDBと異なり格納するデータの自由度は大きい。
+どのようなデータ構造も、設計を行わず格納できる。
+しかし、十分なパフォーマンスを出すためには、データを最適化する必要がある。
+また、最適な木構造はアプリケーションによって違うため、Jungleの設計手法を確立させる必要がある。
 
 [](プロシン発表時間 セッション4 1/7 8:50 - 10:10)