Mercurial > hg > Papers > 2016 > tatsuki-prosym
changeset 54:51a2d20e57bf
add image, add nosql description.
author | Kazuma Takeda |
---|---|
date | Fri, 23 Dec 2016 08:34:24 +0900 |
parents | bc2f679ff4d8 |
children | bb4bb252e101 |
files | Slide/images/NodePath.pdf Slide/images/TreePersonJungle.pdf Slide/images/cassandra.png Slide/images/mongo.png Slide/prosym.md |
diffstat | 5 files changed, 99 insertions(+), 68 deletions(-) [+] |
line wrap: on
line diff
--- a/Slide/prosym.md Fri Dec 23 00:28:06 2016 +0900 +++ b/Slide/prosym.md Fri Dec 23 08:34:24 2016 +0900 @@ -8,57 +8,97 @@ # データベースの歴史 コンピュータでは常に簡略化が行われてきた。 -その中でデータベースとして採用されてきたのが # 階層型データベース データの関係性をツリー構造で定義し、プログラム内部ではその定義を利用してデータへのアクセスする。 -しかし、新しい木構造を作るたびにデータ重複が発生し、冗長化が問題となった。 -そこで採用されたのが + +## 問題点 + +親子関係でしかデータを表現できないため、 +新しい木構造を作るたびにデータ重複が発生し、冗長化する。 + # ネットワーク型データベース -CODASYL型データモデルを準拠に作られたデータベース。 -階層型データベースのデータ冗長化を排除したもの。 +CODASYLデータモデルともいう。 +参照関係で表現が可能になった。そのため、複数参照されているものを一箇所にまとめることで +階層型のボトルネックであったデータ冗長化を排除することができる。 + データをノード単位で整理し、データ間の関係性を定義する。 -しかし、データの関係性が複雑になっているため、データのネットワーク構造を安易に変更できないと言った問題がある。 -そこで開発されたのが + +## 問題点 + +データ間のリンク関係は物理的な実装に近かった。 +そのため、安易にはデータの変更を行うことができないと言った問題がある。 + +# CODASYLデータモデル + +COBOLで多く用いられたデータベース。 +現在のネットワーク型のほとんどがこれを準拠に作られている。 +この特徴としてはデータ操作言語とデータ記述言語を分離している。 # リレーショナルデータベース 階層型データベースやネットワーク型データベースの持つ問題点を解決し、データとプログラムの独立性を高めたデータベース。 -しかし、プログラムからデータを分離して扱うデータベースにはデータ構造とRDBの表構造のインピーダンス・ミスマッチという問題がある。 + +## 問題点 + +プログラムからデータを分離して扱うデータベースではデータ構造とRDBの表構造のインピーダンス・ミスマッチが起こる。 # インピーダンス・ミスマッチ もともとは電気工学の言葉。 -抵抗の異なる素材の間に電磁波を流すと、境界面で反射が起こって効率よく伝達できないことを意味する。 +抵抗の異なる素材の間に電磁波を流すと、境界面で反射が起こり、効率よく伝達できないことを意味する。 つまり、データベースの世界ではオブジェクト指向プログラミングとリレーショナルデータベースの間の不一致で起こることをいう。 -(例があった方がいいかな?) + + +# O/R マッピング + +Object / Relational # 近年 NoSQLと呼ばれるデータベースが開発、利用されている。 +CPUやメモリに比べて低速なストレージ性能を分散させ、 +ネットワークのボトルネックを極力排すること目的とされている。 -## Key-Value Store +# Key-Value Store データをKeyとValueのHash形式でもつ。 完全一致検索しかできないが高速で動作する。 -その例としてCassandraがある。 +# カラム指向 + +RDBと同様に表を持つ。 +カラム単位でデータを保持する。 +大量のデータを読み書きするのに最適とされている。 +例: -## ドキュメント指向データベース +<div style="text-align: center;"> + <img src="./images/cassandra.png" alt="message" width="300"> +</div> + +# ドキュメント指向データベース スキーマが必要ななく使用できる。 複雑な検索条件でデータを取得できる。 -その例としてMongoDBがある。 +例: + +<div style="text-align: center;"> + <img src="./images/mongo.png" alt="message" width="300"> +</div> -# Mongo Database +# mongo Database + +<div style="text-align: center;"> + <img src="./images/mongo.png" alt="message" width="300"> +</div> ドキュメント指向型のデータベースである。 NoSQLのパフォーマンス、スケーラビリティに優れている。 -なお、パフォーマンスを向上させるため、トランザクション、リレーショナルと言った機能は実装されていない。 +なお、パフォーマンスを向上させるため、トランザクション、リレーショナルの機能は実装されていない。 Key-Value Storeでは完全一致検索しかできないが、 RDBのような検索クエリの機能を持たせることで複雑な検索が可能になっている。 @@ -72,22 +112,18 @@ そこで並列処理という手法が考えられる。 トランザクションの機能を排除した、MongoDBでは並列で動くアプリケーションには向いていない。 +トランザクションを備えたRDBはもちろん並列アプリケーションに向いている。 +先ほど述べた、オブジェクト指向プログラミングとリレーショナルデータベースの間ではインピーダンス・ミスマッチが起こってしまう。 + # 提案 +データベースの背景を踏まえ、 今回トランザクションの機能を備え、スケーラビリティにも優れた木構造データベースJungleを提案する。 トランザクションは木のルートをアトミックに入れ替えることで実現する。 また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。 -# この発表では - -- Jungleデータベースの構造 -- WebServer(BBS) -- maTrix -- RenderingEngine -- まとめ - -Jungleデータベースの構造とこれを用いたアプリケーション、実装時に発生した問題と解決方法について解説する。 +まずはJungleの仕様部分から説明する。 # Jungleデータベース @@ -111,66 +147,61 @@ <img src="./images/nonDestractTreeEdit.pdf" alt="message" width="600"> </div> -以降はJungleの構造をAPIとともに紹介。 - -# 木の生成 +# JungleのAPI Jungleは複数の木を名前を利用して管理しており、名前により作成・編集・削除を行う。 -Jungleクラスの木の生成、管理を提供するAPIは以下のようになっている。 +まずはJungleの例を見てもらいたい。 + +以下のコードは、ルートノードの2番目の子どもから、属性名"name"とペアになっている属性値を取得する。 ``` 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(); +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"); ``` -# ノードのChildren +# NodePath + +Jungleでは、木のノードの位置をNodePathクラスを使って表す。 -Childrenクラスで提供されているAPIでTreeNodeにアクセスできる。 +NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。 + +また、ルートノードは例外として-1と表記される。 -``` Java -// Children.java -int size(); -Either<Error, TreeNode> at(int num); -``` +<div style="text-align: center;"> + <img src="./images/NodePath.pdf" alt="message" width="400"> +</div> + + +# Eitherクラス -## Eitherクラス +Jungleでは例外を投げる時にEitherクラスを用いて行う。 -TreeNodeを取ってくる場合Eitherで比較する。 +- 失敗時はA +- 成功時はB + +を包んで返す。 ``` Java -Either<Error, JungleTreeEditor> either = tree.getRootNode ().getChildren ().at (0); -if(either.isA()) { - // throw Exception -} -TreeNode node = either.b(); +Either<Error,TreeNode> either = children.at(2); +if (either.isA()) + throw new IOException(); +TreeNode child = either.b(); + ``` -# ノードのAttribute - -Attributeクラスで提供されているAPIでノードの値にアクセスできる。 - -``` Java -// Attribute.java -ByteBuffer get(String key); -String getString(String key); -``` +[](なぜ Functionalに書かなかった?もしかしてJava8からだから実装当時はまだなかった?) # Jungle を用いたアプリケーション +Jungleの特性を生かし、アプリケーションを構築した。 + - maTrix - BBS - Rendering Engine