Mercurial > hg > Papers > 2016 > tatsuki-prosym
changeset 37:eea008c85b3b
add bib
author | tatsuki |
---|---|
date | Thu, 01 Dec 2016 18:53:43 +0900 |
parents | 215d5ce839b7 |
children | 0bb8c8489f2c |
files | abst.tex compareDatabase.tex introduction.tex jungle.tex maTrix.tex main.tex prosym.bib |
diffstat | 7 files changed, 133 insertions(+), 20 deletions(-) [+] |
line wrap: on
line diff
--- a/abst.tex Thu Dec 01 17:49:11 2016 +0900 +++ b/abst.tex Thu Dec 01 18:53:43 2016 +0900 @@ -1,10 +1,10 @@ \begin{abstract} プログラムからデータを分離して扱うデータベースには、 -プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。 -データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 -データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 +プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチ\cite{Atkinson:1995:OPO:615224.615226}という問題がある。 +データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapper\cite{Lamb:1991:ODS:125223.125244}\cite{Henry:2001:OVJ:367884.367889}や、 +データベース自体も、表に特化したKey Value Store\cite{cassandra09} \cite{cassandra}や、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 -今回提案する木構造データベースJungleはプログラム内部に直接木構造を構築する。 +今回提案する木構造データベースJungle\cite{kono11b} \cite{kono11e}はプログラム内部に直接木構造を構築する。 そして、木のルートをアトミックに入れ替えることでトランザクションを実現する。 また、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を採る。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。
--- a/compareDatabase.tex Thu Dec 01 17:49:11 2016 +0900 +++ b/compareDatabase.tex Thu Dec 01 18:53:43 2016 +0900 @@ -1,5 +1,5 @@ \section{OR-MapperとJungleの検索の比較} -本章ではJungleとOR-Mapperの検索方法の比較を行う。 +本章ではJungleとOR-Mapper\cite{Henry:2001:OVJ:367884.367889}の検索方法の比較を行う。 検索には、人間関係を表した木構造データを用いる。 MySqlでは、表\ref{User}の構造を持つテーブルuserを用いて木構造を表現する。 @@ -38,7 +38,7 @@ しかし、深さが変わると上記のSQLは使用できないうえ、SQL文が長くわかりづらくなる。 なので、特定のユーザー以下のノードを全て取得する場合は、プログラム内で再帰的に複数回SQLを発行する必要がある。 -しかしJungleでは以下の一回の検索で全てのノードを取得することが可能である。 +しかし、Jungleでは以下の一回の検索で全てのノードを取得することが可能である。 以下にJungleでの検索コードを記述する。 \begin{lstlisting}[frame=lrbt,label=index,numbers=left]
--- a/introduction.tex Thu Dec 01 17:49:11 2016 +0900 +++ b/introduction.tex Thu Dec 01 18:53:43 2016 +0900 @@ -2,13 +2,13 @@ プログラム中のデータ構造とRDBの表構造には大きなギャップがある。これはインピーダンスミスマッチと呼ばれている。 例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 -レコードをプログラム中のオブジェクトに対応させるOR Mapという技術では、これを本質的には解決することはできない。 +レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、これを本質的には解決することはできない。 そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。 しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 並列処理を含むプログラミングからの要請とのミスマッチが残っている。 -当研究室では、これらの問題を解決した煩雑なデータ設計が必要のない Jungleデータベースを提案している。 +当研究室では、これらの問題を解決した煩雑なデータ設計が必要のない Jungleデータベース\cite{kono11e}を提案している。 本論文では、実際にJungleを用いたアプリケーションをいくつか構築することで、Jungleに実用データベースとしての表現力、性能があるかを確かめるとともに、どのような木構造がアプリケーションに向いているかを調べる。 その際の設計指針はRDBとは異なり複雑である。これはプログラムのデータ構造そのものの設計に相当する。 Jungleは、その意味でプログラミングの視点から見たデータベースになっている。
--- a/jungle.tex Thu Dec 01 17:49:11 2016 +0900 +++ b/jungle.tex Thu Dec 01 18:53:43 2016 +0900 @@ -8,7 +8,7 @@ Jungleは、データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{nonDestractTreeEdit})。 -その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{nonDestractTreeEdit}の例ではノードB D Eは編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。 +その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{nonDestractTreeEdit}の例ではノードB 、D、 Eは編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。 これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安全に読み出せるという特徴がある。 しかし、書き込み時の手間は大きくなる。
--- a/maTrix.tex Thu Dec 01 17:49:11 2016 +0900 +++ b/maTrix.tex Thu Dec 01 18:53:43 2016 +0900 @@ -1,5 +1,5 @@ \section{許認可管理アプリケーション\\maTrix} -本章では、Jungle上に実際に企業で運用されている許認可管理アプリケーションmaTrixを実装し、Jungleにデータベースとしての表現力、機能の十分性、実用的な性能があるか実証実験を行なう。 +本章では、Jungle上に実際に企業で運用されている許認可管理アプリケーションmaTrixを実装し、Jungleにデータベースとしての表現力、機能の十分性、実用的な性能があるか実証実験を行なう\cite{kngw15a}。 maTrixは、人物、役職、役割、権限、組織の木構造のデータとポリシーファイルを持つ。maTrixの組織構造は、それぞれの木構造がidを用いた参照を行うことで表現される。また、maTrixは過去のアクセス要求を全て保存する。アクセス要求は当時の組織構造を参照しているため、過去の組織構造にアクセス可能にするため、組織構造は版管理されている。 @@ -130,7 +130,7 @@ \subsection{性能測定} maTrixの実装後、Jungleに実用的な性能があるか確かめるために測定を行った。 -比較対象にはMongoDBを選択した。 +比較対象にはMongoDB\cite{mongodb2013}を選択した。 図\ref{fig:compare}はmongoDBとJungleの速度比較のグラフである。 比較は10000人分のデータに対するアクセスの処理時間で行い、mongoDBへのアクセスはjsを用いて行った。 \begin{figure}[h]
--- a/main.tex Thu Dec 01 17:49:11 2016 +0900 +++ b/main.tex Thu Dec 01 18:53:43 2016 +0900 @@ -76,16 +76,16 @@ %\end{acknowledgment} % BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \bibliographystyle{ipsjsort} -% \bibliography{ref} +\bibliographystyle{ipsjsort} +\bibliography{prosym} % BibTeX を使用しない場合 -\begin{thebibliography}{9} -\bibitem{latex}玉城将士、谷成雄,河野真治 : \textbf{Cassandraを使ったスケーラビリティのあるCMSの設計 }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2011. -\bibitem{latex}玉城将士 : \textbf{非破壊的木構造を用いた分散CMSの設計と実装 }. 琉球大学理工学研究科修士論文、2013 -\bibitem{latex}大城信康 、杉本優 、河野真治 : \textbf{Data Segment の分散データベースへの応用}. 日本ソフトウェア科学会第30回大会論文集. 、2013 -\bibitem{latex}大城信康 : \textbf{分散Database Jungleに関する研究}. 琉球大学理工学研究科修士論文、2014 -\bibitem{latex}金川竜己、河野真治 : \textbf{非破壊的木構造データベースJungleとその評価 }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2015. -\end{thebibliography} +%\begin{thebibliography}{9} +%\bibitem{latex}玉城将士、谷成雄,河野真治 : \textbf{Cassandraを使ったスケーラビリティのあるCMSの設計 }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2011. +%\bibitem{latex}玉城将士 : \textbf{非破壊的木構造を用いた分散CMSの設計と実装 }. 琉球大学理工学研究科修士論文、2013 +%\bibitem{latex}大城信康 、杉本優 、河野真治 : \textbf{Data Segment の分散データベースへの応用}. 日本ソフトウェア科学会第30回大会論文集. 、2013 +%\bibitem{latex}大城信康 : \textbf{分散Database Jungleに関する研究}. 琉球大学理工学研究科修士論文、2014 +%\bibitem{latex}金川竜己、河野真治 : \textbf{非破壊的木構造データベースJungleとその評価 }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2015. +%\end{thebibliography} \end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/prosym.bib Thu Dec 01 18:53:43 2016 +0900 @@ -0,0 +1,113 @@ + +@inproceedings{cassandra09, + author = {Lakshman, Avinash and Malik, Prashant}, + title = {Cassandra: structured storage system on a P2P network}, + booktitle = {PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing}, + year = {2009}, + isbn = {978-1-60558-396-9}, + pages = {5--5}, + location = {Calgary, AB, Canada}, + doi = {http://doi.acm.org/10.1145/1582716.1582722}, + publisher = {ACM}, + address = {New York, NY, USA}, + } + +@article{cassandra, + author = "Avinash Lakshman and Prashant Malik.", + title = "Cassandra - a decentralized structured storage system", + journal = "LADIS", + year = "2003", + month = "March" +} + +@inproceedings{kono11b, + title="{Cassandraを使ったスケーラビリティのあるCMSの設計}", + author={玉城将士 and 谷成雄 and 河野真治}, + booktitle="情報処理学会システムソフトウェアとオペレーティング・システム研究会", + month="April", + year=2011 +} + +@inproceedings{kono11e, + title= "{ Cassandraと非破壊的構造を用いたCMSのスケーラビリティ検証環境の構築}", +author={玉城 将士 and 河野 真治}, + booktitle="日本ソフトウェア科学会第 28 回大会(2011 年度)論文集 ", + month="Sep", + year=2011 +} + +@inproceedings{kngw15a, + title= "{非破壊的木構造データベースJungleとその評価}", +author={金川竜己 and 河野 真治}, + booktitle="情報処理学会システムソフトウェアとオペレーティング・システム研究会", + month="May", + year=2015 +} + +@article{Henry:2001:OVJ:367884.367889, + author = {Henry, Kevin}, + title = {Objective Viewpoint: JDBC \&Mdash; Java Database Connectivity}, + journal = {Crossroads}, + issue_date = {March 2001}, + volume = {7}, + number = {3}, + month = mar, + year = {2001}, + issn = {1528-4972}, + pages = {3--ff.}, + url = {http://doi.acm.org/10.1145/367884.367889}, + doi = {10.1145/367884.367889}, + acmid = {367889}, + publisher = {ACM}, + address = {New York, NY, USA}, +} + +@article{Lamb:1991:ODS:125223.125244, + author = {Lamb, Charles and Landis, Gordon and Orenstein, Jack and Weinreb, Dan}, + title = {The ObjectStore Database System}, + journal = {Commun. ACM}, + issue_date = {Oct. 1991}, + volume = {34}, + number = {10}, + month = oct, + year = {1991}, + issn = {0001-0782}, + pages = {50--63}, + numpages = {14}, + url = {http://doi.acm.org/10.1145/125223.125244}, + doi = {10.1145/125223.125244}, + acmid = {125244}, + publisher = {ACM}, + address = {New York, NY, USA}, + keywords = {C++, ObjectStore, database (persistent) programming languages, object-oriented programming}, +} + +@article{Atkinson:1995:OPO:615224.615226, + author = {Atkinson, Malcolm and Morrison, Ronald}, + title = {Orthogonally Persistent Object Systems}, + journal = {The VLDB Journal}, + issue_date = {July 1995}, + volume = {4}, + number = {3}, + month = jul, + year = {1995}, + issn = {1066-8888}, + pages = {319--402}, + numpages = {84}, + url = {http://dl.acm.org/citation.cfm?id=615224.615226}, + acmid = {615226}, + publisher = {Springer-Verlag New York, Inc.}, + address = {Secaucus, NJ, USA}, + keywords = {database programming languages, orthogonal persistence, persistent application systems, persistent programming languages}, +} + +@article{mongodb2013 , + author = {Rupali Arora and Rinkle Rani Aggarwal}, + title = {Modeling and Querying Data in MongoDB}, + year = {2013}, + journal = "International Journal of Scientific and Engineering Research", + volume = "4", + number = "5", + pages = "141" +} +