Mercurial > hg > Papers > 2014 > nobuyasu-master
annotate paper/chapter2.tex @ 6:f47f11ea0e28
Added non destructive tree edit
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 12 Jan 2014 03:03:35 +0900 |
parents | a6aa6af4b80f |
children | 8afa5d2f1459 |
rev | line source |
---|---|
4
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \chapter{木構造データベースJungleの分散設計} |
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 \section{木構造データベースJungle} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
3 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
4 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
5 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
6 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
7 ここではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる. |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
8 \subsection{破壊的木構造} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
9 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
10 図\ref{fig:destractive}は破壊的木構造の編集を表している. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
11 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
12 \begin{figure}[htpb] |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
13 \begin{center} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
14 \includegraphics[scale=0.8]{figures/destructive_tree.pdf} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
15 \caption{破壊的木構造の編集} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
16 \label{fig:destractive} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
17 \end{center} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
18 \end{figure} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
19 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
20 破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
21 この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
22 いる場合は木の走査が終わるまで書き換えをまたなければならない. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
23 これではロックによりスケーラビリティが損なわれてしまう. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
24 |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
25 \subsection{非破壊的木構造} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
26 非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
27 非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
28 行い新しく木構造を作成することで行われる. |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
29 図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している. |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
30 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
31 \begin{figure}[htpb] |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
32 \begin{center} |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
33 \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
34 \caption{非破壊的木構造の編集} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
35 \label{fig:nondestractive} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
36 \end{center} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
37 \end{figure} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
38 |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
39 非破壊的木構造におけるデータ編集の手順を以下に示す. |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
40 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
41 \begin{itemize} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
42 \item test1 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
43 \item test2 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
44 \end{itemize} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
45 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
46 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
47 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
48 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
49 \caption{非破壊的木構造の編集1} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
50 \label{fig:nondestractive_edit1} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
51 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
52 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
53 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
54 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
55 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
56 \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
57 \caption{非破壊的木構造の編集2} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
58 \label{fig:nondestractive_edit2} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
59 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
60 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
61 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
62 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
63 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
64 \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
65 \caption{非破壊的木構造の編集3} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
66 \label{fig:nondestractive_edit3} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
67 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
68 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
69 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
70 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
71 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
72 \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
73 \caption{非破壊的木構造の編集4} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
74 \label{fig:nondestractive_edit4} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
75 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
76 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
77 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
78 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
79 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
80 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
81 |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
82 非破壊的木構造により, 木構造を編集しながら走査することが可能となる. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
83 |
4
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 \section{Jungleの分散データベース設計} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
85 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
86 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
87 |
4
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 \section{Jungleの永続性の設計} |
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 |