第4章 データとモデル.

Slides:



Advertisements
Similar presentations
0章 数学基礎.
Advertisements

プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
実践!DB逆設計 ~レシートからER図を起こす~
エンティティ・リレーションシップ・モデル
到着時刻と燃料消費量を同時に最適化する船速・航路計画
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
ソフトウェア工学特論III 第10回 その他の図 情報通信工学専攻 GM11013 堀江 真史
リレーショナル・データベース データベース論 第10回.
ひでき 平成17年4月12日 「日本教」モデルを ネットワーク分析する ひでき 平成17年4月12日.
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
CGS カーネルベース 変化するオブジェクトに    進化するデータベースを。.
Shimatterシステムの 初期モデルの正規化
MySQLに接続するデータベースプログラム
    有限幾何学        第8回.
第5章 データベースの設計 5.1 データベース設計の概要 5.2 ERモデルとスキーマ設計 5.3 正規化 5.4 一貫性制約.
続 Entity Framework 入門 SQLWorld #8 サヴロウ.
地理情報システム論 第3回 コンピュータシステムおける データ表現(1)
第2章 データベースのモデル 2.1 論理表現と3層モデル 2.2 階層モデル 2.3 ネットワークモデル 2.4 関係モデル.
2012年度 情報数理 ~ QRコードを作ろう!(1) ~.
2008年度 情報数理 ~ QRコードを作ろう!(1) ~.
UMLの概要と オブジェクト指向の 基本概念
Probabilistic Method 6-3,4
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
Copyright Yumiko OHTAKE
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
ま と め メディアコミュニケーション論Ⅲ 第15回.
10.通信路符号化手法2 (誤り検出と誤り訂正符号)
UML入門 UML PRESS vol.1 より 時松誠治 2003年5月19日.
14.テーブル定義,一対多の関係,多対多の関係, 外部キー,索引(インデックス),データベース操作
2010年度 情報数理 ~ QRコードを作ろう!(1) ~.
お勧めのリンク集                氏名        宮城教育大学 課程、専攻 学籍番号.
A First Course in Combinatorial Optimization Chapter 3(前半)
データベース設計の基礎 HN おいろん.
データ構造とアルゴリズム論 第9章 木構造 平成17年12月20日 森田 彦.
二分探索木によるサーチ.
データベース設計 第2回 データベースモデル(1)
その他の図 Chapter 7.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
卒業研究中間発表 社会情報システム学講座 高橋義昭.
第14章 モデルの結合 修士2年 山川佳洋.
データ構造とアルゴリズム 担当:和田俊和 居室:A603 講義資料等は下記を参照してください.
第3回 アルゴリズムと計算量 2019/2/24.
データモデリング 情報システム学科 島川 博光.
データ構造とアルゴリズム (第3回) ー木構造ー.
予測に用いる数学 2004/05/07 ide.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
データ構造とアルゴリズム論 第9章 木構造 平成29年12月20日 森田 彦.
データ構造とアルゴリズム論 第9章 木構造 平成30年6月27日 森田 彦.
Data Clustering: A Review
データモデリング モデルの基本作法.
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
1-3 UMLの図(ダイアグラム) コンポーネント図 システムの物理的な構成を表現 ソフトウェアコンポーネントの依存性を表現
最低限インターネット ネットワークにつなぎましょ!
第4章 データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題
15.cons と種々のデータ構造.
E-R図 井上卓也.
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
  第3章 論理回路  コンピュータでは,データを2進数の0と1で表現している.この2つの値,すなわち,2値で扱われるデータを論理データという.論理データの計算・判断・記憶は論理回路により実現される.  コンピュータのハードウェアは,基本的に論理回路で作られている。              論理積回路.
地理情報システム論(総)/ 国民経済計算論(商)
地理情報システム論 第4回 コンピュータシステムおける データ表現(2)
リレーショナル・データベース J2EE I (データベース論) 第2回 /
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 2010年6月17日
線形符号(10章).
IPアドレス 平成14年7月9日 峯 肇史 牧之内研究室「UNIX とネットワーク基礎勉強会」Webページ
第3章 関係データベースの基礎 3.1 関係とは 3.2 関係代数.
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
Presentation transcript:

第4章 データとモデル

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

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

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

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

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

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

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

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

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

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

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

集合モデル 集合モデル 集合モデルの演算 グループを対象とするモデル 共通部分(積集合): A ∩ B 和集合(和集合): A ∪ B

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

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

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

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

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

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

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

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

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

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

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

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

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

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

発注番号 取引ID 会社名   日付   品名 価格 492 a61 プラス 4/26 コピー紙 50 492 a61 プラス 4/26  椅子 65 492 a61 プラス 4/26 本棚 330 a61 プラス 4/26 机 148 494 c13 小泉商店 7/1 机 168 494 c13 小泉商店 7/1 椅子 98 494 c13 小泉商店 7/1 鉛筆 15 494 c13 小泉商店 7/1 消しゴム 3 第一正規形の例

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

発注番号 取引ID 会社名    日付   492 a61 プラス 4/26 494 c13 小泉商店 7/1 発注番号 品名 価格 492 コピー紙 50 492 椅子 65 492 本棚 330 492 机 148 494 机 168 494 椅子 98 494 鉛筆 15 494 消しゴム 3 第2正規形