情報構造論のテスト返却と雑談
今日は、後期中間試験明けということで、テスト返却。昨年のテストは、説明問題中心になり簡単だったとの反省から、若干穴埋め問題・プログラム記述問題を増やした。しかし、蓋を開けてみたら平均点87点の好成績。テスト直後に記述問題で難しかったって感想言ってたくせに…。
メモリ経由の盗み見
ただ、テスト直後の間違いの確認で、定義されていない変数に何が入っているのかというのを疑問に思っている人がいたので、解説。
void foo() {
int x ;
printf( "%d¥n" , x ) ; // 何が表示されるのか？
}
JavaScript で基本を習っている学生さんだと、undefined とか null とか入っていると思う人も多い。基本的に、局所変数はスタックを使うので、スタックに残っている前の値。いろんなデータがあるからこそ、ゴミ(どんな値が入っているか不明)いうことを説明。
特に、セキュリティという視点だと、Aさんとの通信処理が終わって、Bさんの処理を行う場合、プログラムの不備をみつけたBさんが、局所変数の配列に残っているデータをうまく読むことができたら、Aさんとの通信内容をBさんが盗み見れる可能性もあることを説明。
また、局所変数だけでなく、ヒープメモリも同様の問題をはらんでいる。ヒープメモリは free() で返却されたメモリ領域を、あとで違う人に malloc() で貸し出す。malloc() のデータ領域にも、他の人のデータが入っているかも…と説明する。
再利用によるデータ流出
malloc() + free() の雑談をしていて、これはまさに「神奈川県のデータ流出事件」と同じ構図なので、「「データ領域の再利用でデータ流出』で今ニュースになってるの知ってる？」と学生に聞いてみた。
でも、神奈川のネタに気づく学生さんが居ない。あらためて、こういう時事ネタのニュースを見ていないと感じたので、「みんな4年だとすぐに就職活動の人も多いのに、時事ネタ知らないのはまずいよ」と意識喚起。
その上で、HDDデータ消去のやり方を解説、クイックフォーマット・完全フォーマットの違いや、軍のデータを扱う場合は、残留時期を読み取る可能性もあるので、ランダムデータを4回書き込むといった解説をする。
VMware PlayerでLinux
授業の中で unix 環境を体験してもらうために、vmware player を使う準備
VMware Workstation Playerのインストール
- VMware Workstation Playerのページ より、Windows(無償版)をダウンロードし、インストールを行う。
Ubuntu 18 Desktop 版の起動イメージ
起動した状態のイメージを作っておきたかったが、Freeの環境では無理っぽいな。インストール作業を授業時間内にやるか…
授業アンケートをスマホ対応
授業アンケートのシステムを、スマホの画面に合わせるようにしてみた。
データベースの設計とER図
データベースの設計
リレーショナル・データベースでは、データは表形式であればなんでも良い訳ではない。
例えば、学生の成績データが以下のような構造であった場合、
ID | name | grade | subject | teacher ------+--------+-------+----------+--------- 20101 | aoyama | 1 | database | saitoh 20101 | aoyama | 1 | software | murata 20002 | suzuki | 2 | database | saitoh 20002 | suzuki | 2 | compiler | nomura 30203 | yamada | 3 | media | ogoshi
- 修正不整合: 授業担当が saitoh → sasaki のように変更になったら、複数のテーブルを修正しなければならない。大量のレコード修正は、時間がかかるし、その途中にシステムダウンしたらデータの整合性に問題が発生するかも。
- 挿入不整合: 新しい科目 internet を追加したいけど、受講学生が決まらないとデータを挿入できない。
- 削除不整合: yamada が受講を取りやめたら、科目 media も消えてしまう。
これらを考慮すると、以下のような3つの表で設計するべきである。
学生 受講 科目
ID | name | grade ID | SubID SubID | subject | teacher
------+--------+------- ------+------- ------+----------+--------
20101 | aoyama | 1 20101 | 1001 1001 | database | saitoh → sasaki
20002 | suzuki | 2 20101 | 1002 1002 | software | murata
30203 | yamada | 3 20002 | 1001 1003 | compiler | nomura
20002 | 1003 1004 | media | ogoshi
消す→ 30203 | 1004 1005 | internet | foobar → 追加
データベースの設計では、(1)概念設計、(2)論理設計、(3)物理設計が行われる。
- 概念設計：概念スキーマの決定(実体・関係モデルを使う)。上記の受講データベースの設計例
- 論理設計：論理スキーマの決定。関係データベースで実装？ほかのデータベース？
- 物理設計：物理スキーマの決定。データの格納方法や管理方法を決める。
実体関連モデル(ERモデル)
データベース設計では、実体関連モデル(ERモデル:Entity-Relation model)が使われる。 実体とは、モデル化しようとする対象で独立した存在となれるもの。 実体が持つ色々な特性は属性と呼ばれる。 属性の取りうる値の集合を定義域、同一種類の実体の集まりを実体集合と呼ぶ。 関連とは、実体同士の相互関係をモデル化したもの。
実体関連図(ER図)では、実体を長方形、関連をひし形、属性を楕円で表現する。 属性で、キーとなるものには下線をつけて表す。
ER図で調べると、実際にはもっと細かい規定で表現が行われている。 参考：IDEF1X表記とIE表記
CTF の練習問題
情報セキュリティ関係の学生の興味を引き出すために、関連のイベントに学生さんに参加してもらっている。でも、なかなか基本知識がないと参加も難しい。
こういった情報セキュリティの基本に興味を持ってもらうために、Capture The Flag という大会がある。といっても、全国の大会だとレベルが高すぎるので、まずは興味を持ってもらうための基本問題を作ったので公開しておく。
講義録に動くサンプルコードを併記
長男からプログラミングの授業の質問が LINE で流れてきて、大学の先生の資料を覗き見。その大学の課題ではサンプルコードの配布がしっかりしている。私の講義録でもサンプルコードは掲載しているけど、プロジェクタで掲示しながら授業をするため、#include 行を省略したり、main を void 宣言したりと、そのまま入れても動かない。
そこで、ダウンロードすれば「そのまま動くサンプルコード」を積極的に入れるようにしてみよう。
まずは、後期の情報構造論の半分ほどのサンプルコードを動く様に加筆し、テキストファイルへのリンクを埋め込んだ。
データベースについても、学内向けのSQLite3を使った実験環境にて動作ができるように、若干の改良を加え、リンクを埋め込んだ。
前期分は、来年度の授業の中で修正していこう。
B木とデータベース
2分探索木の考え方を拡張したもので、B木がある。
B木の構造
2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。
B木からデータの検索
データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(logN) となる。
B木へのデータの追加
B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。
ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。
データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。
B木とデータベース
このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。
データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。
データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。
((リレーショナル・データベースの例)) STUDENT RESULT ID | name | grade | course ID | subject | point -----+----------+-------+-------- -----+---------+------- 1001 | t-saitoh | 5 | EI 1001 | math | 83 1002 | sakamoto | 4 | E 1001 | english | 65 1003 | aoyama | 4 | EI 1002 | english | 90 ((SQLの例)) select STUDENT.name, RESULT.subject, RESULT.point --射影-- from STUDENT , RESULT --結合-- where STUDENT.ID == RESULT.ID -- 串刺し -- --選択-- and RESULT.point >= 60 ; ((上記SQLをC言語で書いた場合)) for( st = 0 ; st < 3 ; st++ ) // 結合 for( re = 0 ; re < 3 ; re++ ) if ( student[ st ].ID == result[ re ].ID // 選択 && result[ re ].point >= 60 ) printf( "%s %s %d" , // 射影 student[ st ].name , result[ re ].subject , result[ re ].point ) ;
B+木
データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。
そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。
GROUP BY-HAVINGとCREATE VIEW
先週に引き続き、2つのSQLとそれと同じ処理のプログラム作成の課題に取り組む。
演習だけでは進度が少ないので、SQL で説明できなかった、GROUP BY-HAVING と CREATE VIEW の説明
GROUP BY HAVING
GROUP BY-HAVING では、指定されたカラムについて同じ値を持つレコードがグループ化される。SELECT 文に指定される集約関数は、グループごとに適用される。HAVING は、ある条件を満たす特定のグループを選択するための条件で、WHERE と違い、集約関数が使える。
SELECT SG.商品番号, SUM(SG.在庫量) FROM SG GROUP BY SG.商品番号 HAVING SUM(SG.在庫量) >= 500 ;
- 実験環境でGROUP-BY-HAVING(学内のみ)
このSQLを実行すると、SG のテーブルから、商品番号が同じものだけをあつめてグループ化される。そのグループごとに在庫量のデータの合計SUMを集約し、500以上のデータが出力される。
CREATE VIEW
今までで述べてきたSQLでは、実際のテーブルを対象に、結合・選択・射影を行う命令であり、これは概念スキーマと呼ばれる、対象となるデータベース全体を理解したプログラマによって扱われる。
しかし、プログラムの分業化を行い、例えば結果の表示だけを行うプログラマにしてみれば、全てのデータベースの表を考えながらプログラムを作るのは面倒である。そこで、結合・選択・射影の演算の結果で、わかりやすい単純な表となったものであれば、初心者のデータベースプログラマでも簡単に結果を扱うことができる。このような外部スキーマを構成するための機能が、ビューテーブルである。
-- 優良業者テーブルを作る --
CREATE VIEW 優良業者 ( 業者番号 , 優良度 , 所在 )
AS SELECT S.業者番号, S.優良度, S.所在
FROM S
WHERE S.優良度 >= 15 ;
-- 優良業者テーブルから情報を探す --
SELECT *
FROM 優良業者
WHERE 優良業者.所在 = '福井' ;
ビューテーブルに対する SQL を実行すると、システムによっては予め実行しておいた CREATE VIEW の AS 以下の SQL の実行結果をキャッシュしておいて処理を行うかもしれない。システムによっては SQL の命令を 副クエリを組合せた SQL に変換し、処理を行うかもしれない。しかし、応用プログラマであれば、その SQL がどのように実行されるかは意識する必要はほとんど無いであろう。
ただし、ビューテーブルに対する 挿入・更新・削除といった演算を行うと、データによっては不整合が発生することもあるので注意が必要である。
春江東小学校でIchigoJam出前授業
11/17(日)に、春江東小学校さんからの依頼により、IchigoJam でのプログラミング体験の出前授業を行いました。
HIT2019にて優秀賞
第６回ビジネスモデル発見＆発表会 北陸大会と第６回G空間×ICT北陸まちづくりトライアルコンクール、起業家甲子園・起業家万博 北陸予選を兼ねたHIT2019にて、3EIの佐野くんが優秀賞となりました。
