第4章 データとモデル.

Presentation on theme: "第4章 データとモデル."— Presentation transcript:

1 第4章 データとモデル

2 本章の目的 コンピュータで情報をあつかいたい → 情報を”うまく表現”しなければならない ”うまい表現”＝「データモデル」
コンピュータで情報をあつかいたい　　　　　　　　　→ 情報を”うまく表現”しなければならない ”うまい表現”＝「データモデル」 データモデル データを体系的に扱うためのモデル データ コンピュータの処理対象となる，符号化された情報 本章では「データモデル」を概観する

3 データのモデル化 モデル化 モデル化のやりかた 対象からモデルを作ること 対象のなかで興味がある要素を書き下す
天体，質量，価値，需要，集積度，権力，意味，音階，画素，など 要素間の関係をルールとして規定していく コンピュータの場合，要素間の関係は操作/演算/計算としてとらえられる

4 モデル化の例 太陽と地球 → ２つの点 地球が 太陽の周りを回る動き → 時間をパラメタとした演算

5 完全性 対象の要素が全て表現できる 完全性がないモデル 対象の操作も考えてモデルを作る場合，対象の操作に対応する演算がモデルに必要 実数
人名漢字

6 一意性 モデルの1つの要素が対象の1つの要素に対応 一意性がないモデル 下二桁で表された西暦 性のみで表された名前

7 忠実性 対象の1つの要素がモデルの1つの要素に対応 忠実性がないモデル 対象とモデルの関係が一意性と逆 "半分"を表す有理数表現
実数の指数表現

8 整合性 対象で成り立つべき規則がモデルでも成り立つ 整合性がないモデル 整合性が成り立たないモデルでは，操作も含めて対象がうまく表現できない
コンピュータで表された実数

9 無冗長性 同じ情報が表現の複数箇所に現れることがない 冗長性を利用する例 論理データモデルでは冗長性がない方が良い
物理データモデルでは意図的に冗長な表現を用いることがある 冗長性を利用する例 学生証番号と氏名の両方を解答用紙に記入

10 拡張性 データモデルを変更したときに，既存のデータの表現を変更せずに新しいデータを表現できる モデルを拡張した例
データモデルは外的要因の変化や応用が拡大につれて変化していく モデルを拡張した例 電話番号： 先頭に184/186を追加 郵便番号： 7桁に変更 IPアドレス： IPv4 → IPv6

11 データモデルのレベル 概念モデル 論理モデル(論理レベル) 物理モデル 人間が対象を認識するレベル ビットよりハイレベル
いろいろな対象に普遍 これから話題にするものは主にこれ 物理モデル ビットでの表現のレベル

12 代表的なデータモデル 集合モデル ネットワークモデル 階層モデル 関係モデル 論理モデル オブジェクト指向モデル

13 集合モデル 集合モデル 集合モデルの演算 グループを対象とするモデル 共通部分（積集合）： A ∩ B 和集合（和集合）： A ∪ B

14 ・意味ネットワーク （後述）(skip可）
4.3 代表的なモデルと演算 １. 集合モデル 2. ネットワークモデル ・意味ネットワーク （後述）(skip可） ・実体関連モデル(ERモデル）（後述）(skip可） 3. 階層モデル（木構造　　）(オイラー図） 　　・ 階層的ファイルシステム ・ 日本の住所 　　・ 図書の分類 十進分類法(Dewey)

15 グラフモデル ノードとエッジから構成される ラベル付きグラフ 有向エッジ，弧： 方向を持つエッジ
道路ネットワーク/組織図/pert図/意味ネットワークなど様々な領域で幅広く用いられる ノード エッジ

16 集合の視覚的表現 ベン図 A ∩ B A ∪ B A B A B A − B A B

17 階層モデル 階層モデル(木構造) 生物の分類図のような，枝分かれの構造 有向グラフの特殊なもの，と見ることもできる
例： コンピュータのファイルシステム 生物の分類図 ファイルシステム

18 色々な木 - 順序木 順序木 例１： (2+3)*12 例２： (2+3)*((2+3)/12) 分岐先に順序をつけた木
共通の部分式 (2+3) をまとめて、DAG(Directed Acyclic Graph) として表せる

19 色々な木 - ゲーム木 ゲーム木 ゲームの状態を木構造で表したもの ゲーム木を使うと
勝ち状態に至る経路を探索することで，強いコンピュータゲームプレーヤーを作ることができる 必勝法のある/なしなど，ゲームの性質を考えることができる ○×ゲームのゲーム木

20 意味ネットワーク (imi-network.html参照)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 意味ネットワーク（いみねっとわーく）は人間の記憶の一種である意味記憶の構造を表すためのモデルである。 意味ネットワークはコリンズとキリアンによって考えられた。 人間の記憶は、コンピュータの記憶と異なる構造を持つので、ビットやバイトといった情報量で表すことができない。そのため、このようなモデルが必要となる。集合論を基礎としたモデルなどもある。 ノード（円）が概念、リンク（矢印）が関係を表す。 リンクには「である（isa）」、「もつ（hasa）」などがある。

21 実体関連モデル ＥＲモデル(skip可) 世界を実体(entity)と関連(relation)の集まりとして見るモデル
実体と実体のあいだの関連をもつ 実体と実体のあいだの関連で表現すると、実体の属性が変化しても、属性だけが変化したことになる HTML(sinsyuu-u.html) 参照。

22 実体と関連の表現の例 40歳の山田と40歳の田中が1985年4月1日に結婚した 40歳の山田 1985年4月1日に結婚 40歳の田中

23 実体関連図の例 40歳の山田と40歳の田中が1985年4月1日に結婚した 実体： 男性 属性： 名前，年齢 関連： 結婚 属性： 結婚記念日
実体： 女性 属性： 名前，年齢

24 巡回セールスマン問題 (ＮＰ困難) http://www.tsp.gatech.edu/
ネットワーク上の最適化問題　　 最短路問題 ハミルトン閉路問題　　(ＮＰ完全) 巡回セールスマン問題　(ＮＰ困難) 参照： d15112-DATA.gif, d15112-Solution.gif, d15112-Maze.gif, ピーターセングラフ

25 関係モデル 関係モデル 関係 ”関係”によるモデル化 実際に関係のある組を集めたデータ
例： 「山口君が東京に住んでいて，　　　　　　　　　　　　　 電話番号は 」という事実　　　　　　　 → 山口，東京， の関係

26 関係モデル - 正規化 正規化 同じデータが何回も出てくるような，冗長な関係を，分割して簡潔な関係にすること 名前の関係 電話番号の関係
住所の関係

27 関係の項目のひとつに識別番号を入れると、冗長性がなくなる
第一正規化　　２次元の表にする 番号　 名前　 所属 g456 小泉 {１5組,水泳部｝ 非正規型リレーション 番号　 名前　 所属 g456 小泉 １5組 g456 小泉 水泳部 正規型リレーション

28 発注番号 取引ＩＤ 会社名 　　日付 　 品名 価格 a プラス / コピー紙 a プラス /26　　椅子 a プラス / 本棚 a プラス / 机 c 小泉商店 7/ 机 c 小泉商店 7/ 椅子 c 小泉商店 7/ 鉛筆 c 小泉商店 7/ 消しゴム 第一正規形の例

29 関係を冗長性がなくなるように、複数の関係に分解することを正規化という
発注番号と品名が主キーになっていて、あとはそれからきまる。この２つをあわせて復号キーという。 正規形への分割では、属性を１カ所変更しても、他の属性値はそのままでしよい。 記憶領域の無駄遣いをしないですむ。

30 発注番号 取引ＩＤ 会社名 　　 日付 　 a プラス /26 c 小泉商店 7/1 発注番号 品名 価格 コピー紙 椅子 本棚 机 机 椅子 鉛筆 消しゴム 第２正規形