Mercurial > hg > Papers > 2016 > tatsuki-prosym
changeset 53:bc2f679ff4d8
fix purpose of resaerch.
author | Kazuma Takeda |
---|---|
date | Fri, 23 Dec 2016 00:28:06 +0900 |
parents | b37ab31d5f12 |
children | 51a2d20e57bf |
files | Slide/prosym.md Slide/slide_map.xmind |
diffstat | 2 files changed, 71 insertions(+), 9 deletions(-) [+] |
line wrap: on
line diff
--- a/Slide/prosym.md Mon Dec 19 00:02:27 2016 +0900 +++ b/Slide/prosym.md Fri Dec 23 00:28:06 2016 +0900 @@ -1,18 +1,81 @@ title: ソフトウェア内部で使用するのに適した木構造データベースJungle author: Tatsuki Kanagawa -profile: 琉球大学理工学研究科 +author: Kazuma Takeda +author: Shinji Kono +profile: 琉球大学 lang: Japanese code-engine: coderay -# 研究目的 -[](要素を説明するところではサブセクションにしてある) -プログラムからデータを分離して扱うデータベースにはデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。 +# データベースの歴史 + +コンピュータでは常に簡略化が行われてきた。 +その中でデータベースとして採用されてきたのが + +# 階層型データベース + +データの関係性をツリー構造で定義し、プログラム内部ではその定義を利用してデータへのアクセスする。 +しかし、新しい木構造を作るたびにデータ重複が発生し、冗長化が問題となった。 +そこで採用されたのが + +# ネットワーク型データベース + +CODASYL型データモデルを準拠に作られたデータベース。 +階層型データベースのデータ冗長化を排除したもの。 +データをノード単位で整理し、データ間の関係性を定義する。 +しかし、データの関係性が複雑になっているため、データのネットワーク構造を安易に変更できないと言った問題がある。 +そこで開発されたのが + +# リレーショナルデータベース +階層型データベースやネットワーク型データベースの持つ問題点を解決し、データとプログラムの独立性を高めたデータベース。 +しかし、プログラムからデータを分離して扱うデータベースにはデータ構造とRDBの表構造のインピーダンス・ミスマッチという問題がある。 + +# インピーダンス・ミスマッチ + +もともとは電気工学の言葉。 +抵抗の異なる素材の間に電磁波を流すと、境界面で反射が起こって効率よく伝達できないことを意味する。 + +つまり、データベースの世界ではオブジェクト指向プログラミングとリレーショナルデータベースの間の不一致で起こることをいう。 +(例があった方がいいかな?) + + +# 近年 + +NoSQLと呼ばれるデータベースが開発、利用されている。 -- ORMapper -- Json +## Key-Value Store +データをKeyとValueのHash形式でもつ。 +完全一致検索しかできないが高速で動作する。 + +その例としてCassandraがある。 + + +## ドキュメント指向データベース +スキーマが必要ななく使用できる。 +複雑な検索条件でデータを取得できる。 + +その例としてMongoDBがある。 + +# Mongo Database -などにより、不定形のデータ構造を格納できる機能拡張もなされてきたが、複雑な構造をメモリ上に構築しているため、これらの方法でもまだギャップがある。 +ドキュメント指向型のデータベースである。 +NoSQLのパフォーマンス、スケーラビリティに優れている。 +なお、パフォーマンスを向上させるため、トランザクション、リレーショナルと言った機能は実装されていない。 + +Key-Value Storeでは完全一致検索しかできないが、 +RDBのような検索クエリの機能を持たせることで複雑な検索が可能になっている。 + +# 現在の課題 -今回提案する木構造データベースJungleはプログラム内部に直接木構造を構築する。 +コンピュータのCPU性能は格段によくなった。しかし、これ以上CPUの性能が大幅に向上するとは思えない。 +一方、データは膨大化している。 +CPUを物理的に増やすことで、解決はできるが、有限な物であるため一時的な解決方法にしかならない。 + +そこで並列処理という手法が考えられる。 +トランザクションの機能を排除した、MongoDBでは並列で動くアプリケーションには向いていない。 + +# 提案 + +今回トランザクションの機能を備え、スケーラビリティにも優れた木構造データベースJungleを提案する。 + トランザクションは木のルートをアトミックに入れ替えることで実現する。 また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。 @@ -49,7 +112,6 @@ </div> 以降はJungleの構造をAPIとともに紹介。 -[](70分あるので入れてもいいかな) # 木の生成