# HG changeset patch # User Kazuma Takeda # Date 1482608960 -32400 # Node ID ae97e8fe3d89ee1bee458ca63ac6a7ab63b7d881 # Parent 8b13db57ebe91c40a9719431d063abb85f61af0b add pdf file and fix md. diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/badLayoutTree.pdf Binary file Slide/images/badLayoutTree.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/benchMark.pdf Binary file Slide/images/benchMark.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/contentTree.pdf Binary file Slide/images/contentTree.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/goodLayoutTree.pdf Binary file Slide/images/goodLayoutTree.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/layoutTree.pdf Binary file Slide/images/layoutTree.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/multiComponent.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Slide/images/multiComponent.graffle Sun Dec 25 04:49:20 2016 +0900 @@ -0,0 +1,1258 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle6 + 163.7.0.243167 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {1118, 1566}} + Class + SolidGraphic + ID + 2 + Style + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColorProfiles + + + data + + AAACJGFwcGwEAAAAbW50clJHQiBYWVogB98ACgAOAA0ACAA5YWNz + cEFQUEwAAAAAQVBQTAAAAAAAAAAAAAAAAAAAAAAAAPbWAAEAAAAA + 0y1hcHBs5bsOmGe9Rs1LvkRuvRt1mAAAAAAAAAAAAAAAAAAAAAAA + AAAAAAAAAAAAAAAAAAAKZGVzYwAAAPwAAABlY3BydAAAAWQAAAAj + d3RwdAAAAYgAAAAUclhZWgAAAZwAAAAUZ1hZWgAAAbAAAAAUYlhZ + WgAAAcQAAAAUclRSQwAAAdgAAAAgY2hhZAAAAfgAAAAsYlRSQwAA + AdgAAAAgZ1RSQwAAAdgAAAAgZGVzYwAAAAAAAAALRGlzcGxheSBQ + MwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA + AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA + AAAAAAB0ZXh0AAAAAENvcHlyaWdodCBBcHBsZSBJbmMuLCAyMDE1 + AABYWVogAAAAAAAA81EAAQAAAAEWzFhZWiAAAAAAAACD3wAAPb// + //+7WFlaIAAAAAAAAEq/AACxNwAACrlYWVogAAAAAAAAKDgAABEL + AADIuXBhcmEAAAAAAAMAAAACZmYAAPKwAAANUAAAE7YAAAn8c2Yz + MgAAAAAAAQxCAAAF3v//8yYAAAeTAAD9kP//+6L///2jAAAD3AAA + wG4= + + space + 0c23c45ae9b201f35db0195c7ae905477d83da5b + + + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2016-11-09 22:49:51 +0000 + Creator + sister_clown + DisplayScale + 1.0000 cm = 1.0000 cm + GraphDocumentVersion + 12 + GraphicsList + + + Class + LineGraphic + Head + + ID + 3 + + ID + 41 + Points + + {358.5, 224} + {358.5, 354} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 38 + Info + 1 + + + + Bounds + {{205.5, 109}, {306.00000000000006, 71}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 20 + + ID + 40 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 NodeName : \ +displayinfomation} + + TextRelativeArea + {{0, 0}, {1, 1}} + + + Bounds + {{314, 18}, {89, 47}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 39 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Node1} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{205.5, 64}, {306.00000000000006, 160}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 38 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0.0 + + + + Bounds + {{205.5, 11}, {306.00000000000006, 53}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 37 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0.0 + + + + Bounds + {{205.5, 452}, {306.00000000000006, 71}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 20 + + ID + 36 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 NodeName : \ +Multi@Component} + + TextRelativeArea + {{0, 0}, {1, 1}} + + + Bounds + {{380.03389830508462, 760.75}, {355.93220338983053, 71}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 20 + + ID + 33 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 displayComponentName : \ +diaryText@Component} + + TextRelativeArea + {{0, 0}, {1, 1}} + + + Bounds + {{380.03389830508451, 667}, {355.93220338983053, 47}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 29 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Node4} + + TextRelativeArea + {{0, 0}, {1, 1}} + + + Bounds + {{11.858997931509862, 667}, {348.50471156056108, 47}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 28 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Node3} + + TextRelativeArea + {{0, 0}, {1, 1}} + + + Bounds + {{314, 361}, {89, 47}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 24 + + ID + 27 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 Node2} + + TextRelativeArea + {{0, 0}, {1, 1}} + Wrap + NO + + + Bounds + {{10.24764421971949, 760.75}, {348.50471156056108, 71}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Font + HiraKakuPro-W3 + Size + 20 + + ID + 25 + Shape + Circle + Style + + fill + + Color + + b + 0.97457300000000002 + g + 0.99806399999999995 + r + 1 + + Draws + NO + + shadow + + Color + + a + 0.75 + b + 0.94523000000000001 + g + 0.98711599999999999 + r + 1 + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1504\cocoasubrtf760 +{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +{\*\expandedcolortbl;;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs40 \cf0 displayComponentName :\ +diaryImage@Component} + + TextRelativeArea + {{0, 0}, {1, 1}} + + + Class + LineGraphic + Head + + ID + 9 + Info + 2 + + ID + 15 + Points + + {358.5, 567} + {558, 660} + + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0.0 + g + 0.0 + r + 1 + space + 0c23c45ae9b201f35db0195c7ae905477d83da5b + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 6 + Info + 1 + + + + Class + LineGraphic + Head + + ID + 7 + Info + 2 + + ID + 13 + Points + + {358.5, 567} + {183.96288209606996, 660} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + 0 + Join + 0 + Legacy + + TailArrow + 0 + + + Tail + + ID + 6 + Info + 1 + + + + Bounds + {{380.03389830508473, 713}, {355.93220338983053, 177.5}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 10 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0.0 + g + 0.0 + r + 1 + space + 0c23c45ae9b201f35db0195c7ae905477d83da5b + + + + Text + + VerticalPad + 0.0 + + + + Bounds + {{380.03389830508468, 660}, {355.93220338983053, 53}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 9 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + stroke + + Color + + b + 0.0 + g + 0.0 + r + 1 + space + 0c23c45ae9b201f35db0195c7ae905477d83da5b + + + + Text + + VerticalPad + 0.0 + + + + Bounds + {{9.710526315789366, 713}, {349.57894736842132, 177.5}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 8 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0.0 + + + + Bounds + {{9.1734084118592989, 660}, {349.57894736842132, 53}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 7 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0.0 + + + + Bounds + {{205.5, 407}, {306.00000000000006, 160}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 6 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0.0 + + + + Bounds + {{205.5, 354}, {306.00000000000006, 53}} + Class + ShapedGraphic + FontInfo + + Font + HiraKakuProN-W3 + Size + 12 + + ID + 3 + Magnets + + {0, 1} + {0, -1} + {1, 0} + {-1, 0} + + Style + + shadow + + Draws + NO + + + Text + + VerticalPad + 0.0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 2 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + レイヤー 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoLineLength + 0.20000000298023224 + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2016-12-24 19:36:18 +0000 + Modifier + kazuma + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + キャンバス 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 2 + WindowInfo + + CurrentSheet + 0 + Expanded_Canvases + + Frame + {{0, 4}, {1440, 773}} + ShowInfo + + ShowRuler + + Sidebar + + SidebarWidth + 230 + TopSlabHeight + 33 + VisibleRegion + {{-337, 0}, {1792, 1230}} + Zoom + 0.5 + ZoomValues + + + キャンバス 1 + 0.5 + 1 + + + + + diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/multiComponent.pdf Binary file Slide/images/multiComponent.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/multiComponent01.pdf Binary file Slide/images/multiComponent01.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/multiComponent02.pdf Binary file Slide/images/multiComponent02.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/multiComponent04.pdf Binary file Slide/images/multiComponent04.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/images/multiComponent05.pdf Binary file Slide/images/multiComponent05.pdf has changed diff -r 8b13db57ebe9 -r ae97e8fe3d89 Slide/prosym.md --- a/Slide/prosym.md Fri Dec 23 17:22:01 2016 +0900 +++ b/Slide/prosym.md Sun Dec 25 04:49:20 2016 +0900 @@ -6,9 +6,13 @@ # はじめに -データベース +データベースは1960年代後半に階層型、ネットワーク型により注目が集まった。 + +CODASYLの規格によりデータ操作言語とデータ記述言語の分離を主流とした。 -プログラムからデータを分離して扱うデータベースには、 +その後RDBが主流になった。 + +しかし、プログラムからデータを分離して扱うデータベースには、プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 @@ -40,11 +44,15 @@ そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 -並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 +並列処理が中心となってきている今のアプリケーションには向いているとは言えない。 + +つまり、この拡張はRDBよりの拡張であり、並列処理を含むプログラミングからの要請とのミスマッチが残っている。データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 +その例としてCassandraや、mongoDBが挙げられる。 + しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 # 提案 @@ -52,8 +60,11 @@ 当研究室ではこれらの問題を解決した煩雑なデータ設計が必要のないJungleデータベースを提案している。トランザクションは木のルートをアトミックに入れ替えることで実現する。 + また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。 + プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 + また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。Jungleは分散構成も可能である。 @@ -158,7 +169,8 @@ Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。 JungleTreeEditorクラスには編集を行うために、次の定義されているAPIが実装されている。 -また、ノードを指定して編集を行う際にNodePathクラスを用いる。 + +また、ノードを指定して編集を行う際にNodePathクラスを用いる。 # NodePath @@ -210,7 +222,7 @@ # JungleのAPI Jungleの木を編集する例を記載する。 -以下のコードは木からEditorを取得し、変数editorNodePathので指定したノードに新しい子ノードを追加したものである。 +以下のコードは木からEditorを取得し、変数editorNodePathで指定したノードに新しい子ノードを追加したものである。 ``` Java JungleTreeEditor editor = tree.getTreeEditor(); @@ -223,29 +235,26 @@ ``` -[]() - # Jungle を用いたアプリケーション Jungleの特性を生かし、アプリケーションを構築した。 - maTrix -- BBS - Rendering Engine -- Unity # maTrix 実際に企業で運用されている許認可管理アプリケーション。 + 人物、役職、役割、権限、組織の木構造のデータとポリシーファイルを持つ。 maTrixのデータ構造は以下のようになっている。

-## ポリシーファイル +# ポリシーファイルデータに対するアクセス要求が許可されるか否認されるかを判断するためのルール、 @@ -266,40 +275,289 @@ - 過去のアクセス要求を全て保存する - ファイルポリシーを用いた場合の人物検索 -# 実装部分 +# Indexの実装 + +Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持しているため、全ての版に独立したIndexが必要となる。 + +そのため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。 + +既存のTreeMapでは、一度Indexの複製を行った後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 + +よって、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。 + +このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。 + +Jungleとの違いは、木の回転処理が入ることである。 + + +# Indexの実装 + +これにより複数の版全てに対応したIndexをサポートすることが可能になった。 +以下にJungleにおけるIndexの型を記述する + +``` Java +TreeMap node> index> indexMap +``` + +JungleのIndexはIndexMap内に保持されている。 + +属性名でIndexMapにgetを行うと、対応したIndexが取得できる。 + +取得したIndexに属性値でgetを行うと、ノードのリストが返ってくる。 + +# Indexからノードのiteratorを取得するサンプルコード + +Indexから属性名 name 属性値 Kanagawa のデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。 + +``` Java +Optional>> indexOp = indexMap.get("name"); +if (!indexOp.isPresent()) + return new NulIterator(); +TreeMap> index = indexOp.get(); +Optional> nodeListOp = index.get("kanagawa"); +if (!nodeListOp.isPresent()) + return new NulIterator(); +// 持っていた場合OptionalオブジェクトからノードリストのIteratorを返す。 +return nodeListOp.get().iterator(); +``` -Indexをつけて、検索部分も実装した。 -子から親への参照が必要になったのでParentIndexを実装した +・属性名"name"でgetを行うと対応したIndexが包まれて返ってくる。 + +・中身が入っているか確認、入っていた場合Indexを取得する。 + +・取得したIndexに、検索で使用する属性値"kanagawa"でgetを行う。属性名"name" 属性値kanagawaの値を持つノードのリストが、Optionalクラスに包まれて返ってくる。 + +・中身が入っているか確認、入っていた場合OptionalオブジェクトからノードリストのIteratorを返す。 + +# 検索APIの実装 + +Indexを実装したことにより、Idを用いた組織構造の表現は可能になった。 + +しかし、組織構造に問い合わせを行う検索APIが実装されていなかったため、属性名key 属性値valueの組で検索を行うAPIの実装を、木の走査を行うTraverserクラス内に、lambda式を用いて行った。 + +以下に検索を行う関数findの定義を記述する。 + +``` Java +public Iterator find(Query query, String key, String searchValue); +``` + +関数findは引数に、Query query、String key、String valueの3つの引数を取り、条件に一致したノードのIteratorインタフェースを返す。 + -## ParentIndex +第1引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterface Queryを、第2、第3引数の、String key、String ValueはIndexを用いた絞込みに使用する。 + +# 関数findを用いた検索APIのサンプルコード -ノードを投げるとその親がReturnされる。 +``` Java +InterfaceTraverser traverser = tree.getTraverser(true); +Iterator resultNodeIterator = traverser.find((TreeNode node) -> { + String personId = node.getAttributes().getString("Personid"); + if (personId == null) return false; + return personId.equals("p:2"); +}, "element", "Person"); +``` + +・Traverserクラスは木の走査を行う。まずは木から取得してくる。 + +・Indexからfindの第２、第３引数である、属性名"element" 属性値"Person"の組のノードを取得し、Queryに渡す。 + +・引数のノードから関数getAttributes().getString("Personid")で属性名Personidとペアになっている属性値を取得する。 + +・属性値がnullだった場合、このノードには属性名がPersonidの組のデータは存在しないので、falseを返し次のノードの評価を行う。 + +・属性値がnullでなかった場合、p:2と一致するかどうかを調べ結果を返す。 # HTML Rendering Engine Jungleの特性を生かしたRendering Engineを開発した。 + 今回は例題として、日記(ブログ)を選択した。 # 構造 -- LayoutTree +- LayoutTree 出力する形式が記述された木 -- ContentTree +- ContentTree 出力するデータが記述された木これら２つを参照しながらレンダリングを行う。 +# ContentTree + +RenderingEngineではContents Treeに以下のように出力するデータを格納した。 + +

+ +- RootNodeはContentのtitle、日時、レンダリングする時に参照するLayoutTreeのNodeNameを持つ。 +そして子ノードが日記の本文等のデータを持つ。 + +# Nodeが持つAttribute + +NodeAttributeにノードが保持しているContentsの一覧を以下に記述する。 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

component	レンダリングする際に参照するLayoutTreeのNodeName
title	日記のタイトル
date(rootNode)	日記の日時
type	そのノードが保持しているContextType。 text(日記本文) or image(画像データ)
body	日記の本文
date(image)	画像の保存日時
fileName	画像の名前

+ +# LayoutTree + +LayoutTreeには次のようにデータを格納した。 + +

+ +# LayoutTreeの主な要素 + + + + + + + + + + + + + + + + + + + + + + +

NodeName	ノードの名前。ノード同士の参照時に用いられる。例外としてルートノードだけはdisplayinformationという名前を持つ
displayComponent	参照するノードの名前
Name	この属性名で取得できる値を持つNodeNameを持つノードを参照する
use	このノードが、どのContentsに対してのLayoutを持つかを記述するタグ。表\ref{tag}にタグとContentsの対応を記述する
その他	css等と同じ様な記述を行う。例属性名font 属性値fontSize

+ +# multiComponent + +Layoutが複数のComponentを参照する際は以下のような木構造を構築する。 + +

+ +上の例ではdiaryMulti@componentはdiaryText@componentとdiaryImage@componentを参照している。 + +# レンダリングの流れ + +ContentTreeとLayoutTreeの２つを使用したレンダリングの流れを記述する。 + +・ContentsTreeのルートノードは、属性名 component 属性値 Multi@Componentの組を持つので、LayoutTreeのNode2を参照する。 + +

+ +# レンダリングの流れ + +・Node2は自身のNodeNameしか持たないので、子ノードであるNode3,Node4に記述されているデータの参照を行う。 + +

+ +# レンダリングの流れ + +・Node3は属性名 displayComponentName、属性名 diaryImageの組を持つため、NodeNameがdiaryText@componentのノードを参照している。 + +

+ +# レンダリングの流れ + +・レンダリングエンジンは、参照先のノードに記述されたルールに則ってHtmlを生成する。 + +・Node3は、これ以上データを持たないため、次はNode4を参照する。 + +# レンダリングの流れ + +・Node4は属性名 displayComponentName 属性名 dialyText@Componentの組を持つため、NodeNameがdialyText@Componentのノードを参照している。 + +

+ +・レンダリングエンジンは、参照先のノードに記述されているルールに則ってhtmlを生成する。 + +# 設計 + +Jungleは凡用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することができる。 +しかし、設計を行うことで効率的に木構造を扱うことが可能になります。 +同じデータを格納した２つの木の一部を記述する。 + + +# コードとギャップのある格納 + +

+ +このTreeはレンダリングする際に必要な値が複数のノードに分散されて保存されている。そのためすべてのノードを参照し、値を集める処理を行う必要があり、コードの可読性が下がる。さらに余分な処理も増えてしまう。 + +# コードとギャップのない格納 + +

+ +このTreeは、１つのノードにレンダリングに必要な値が全て格納されている。 +そのため、レンダリングを行う際、複数のノードをまたぐ必要が無く、簡潔にコードを書くことができる。 + +# 性能評価 + +先ほどのギャップのあるコードの木と、ギャップのないコードの木を使った2つのrenderingEngineの性能測定を行い、木の構造が実行速度にどれだけ影響するかを確かめる。 +測定は100000回のレンダリングリクエストを処理するまでの時間の比較で行う。 + +

+ +測定結果より、Jungleデータベースは、設計を行うとプログラム内のデータ構造とギャップがなく、高速に動作するプログラムを簡潔に記述できるようになる。 + + # まとめ -本研究では非破壊データベースJungleにJungleTreeブラウザ、許認可管理アプリケーションmaTrix、HtmlRenderingEngineの3つを実装した。 +本研究では非破壊データベースJungleに許認可管理アプリケーションmaTrix、HtmlRenderingEngineの3つを実装した。 -JungleTreeブラウザを実装したことにより、ブラウザから木構造の確認、編集が行えるようになった。 - -許認可管理アプリケーションmaTrixの実装を通して、Jungleに実用データベースとしての表現力、機能の十分性、実用的な性能があるか実証実験を行った。 +許認可管理アプリケーションmaTrixの実装を通して、Jungleに実用データベースとしての表現力、機能の十分性、実用的な性能があるか実証実験を行った。 maTrixは複数の木がお互いにIdを用いた参照を行い組織構造を表現していたが、JungleではIndexを用いた参照で表現した。また、測定の結果mongoDBの約500倍高速に動作した。これはJungleがon memoryなのに対し、MongoDBはmmapを用いてデータにアクセスしているからである。