データべースの設計と正規形
昨年度までの試験問題を例に解説を行い、その後、データベースの設計において、重要な正規形についての説明の導入。
正規形
データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。一般的に不整合が発生しないためには、以下の第1正規形、第2正規形、第3正規形を満たすように表を分ければよい。
第一正規形は、すべての要素が原子値である条件を満たせばいい。 要素の中が複数の項目であったり表形式のデータがあると、 表構造のリレーショナルデータベースにはできない。
- 中央省庁のデータ表記を統一：河野太郎行政・規制改革担当相のTweet
データベースと直接関係しないけど、データは原子値じゃないと困るというお話。 - 雑談 正しいデータとして扱えるドキュメントとは…
キーの説明：超キー(スーパーキー)とは、データベースで１つのデータを 選び出すために必要なデータ項目であり、複数の項目で１データを指定 できる場合もある。
候補キーとは、必要最小限の項目となっているものを指す。 １項目が抜けても選別できなくなるようであれば、候補キーとは言わない。 主キーとは、候補キーのなかで管理の都合上便利なもの。
データ項目の値が決まると、他のデータ項目が自動的に決まるものは、 従属関係があるという。
 |
 |
| 第1正規化 | 第2正規化 |
第二正規形は、部分従属がなく、すべての非キーデータ項目が、候補キーに 完全従属する場合をいう。
- 完全従属とは、候補キーを構成する全てのデータ項目に、非キーデータ項目が従属していること。
- 部分従属とは、候補キーを構成するデータ項目の一部のデータ項目に、非キー項目が従属していること。
この例において、単価は商品が決まれば自動的に求まる情報。 (単価が日々変化することはないという条件で…) これは、部分従属となる。他に部分従属となっている属性は何か？
- 推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。
第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。
 |
| 第3正規化 |
上記の例では、単価と個数が決まれば、金額が求まる推移従属の関係が含まれている。
おまけ：BC正規形,第4,5正規形
この他にも、 さらに非キーからキーに関数従属性がある場合にそれを取り除く、 ボイスコッド正規形(BC正規化)。 「対称性のある多値従属性(キーを決めると複数データが該当)」を分解して得られる第4正規形や、 「元になるテーブルの結合従属性を維持して分解することにより得られる第5正規形などがある。
トランスポート層・TCPとUDP
前回の授業で説明が不足していた DHCP についての説明
DHCP
前回の IP では、異なるサブネットを繋ぐ役割としての Internet Protocol (IP) について説明をした。IP での通信では、IPアドレスが必要だが、正しく接続ができるためには、(1)IPアドレス、(2)サブネットマスク、(3)ゲートウェイアドレス が必要となる。しかし、この情報は初心者には設定が難しいし、IPアドレスが他の利用者と重複させないためには、きちんとした管理が必要となる。
この時に使われるのが DHCP(Dynamic Host Configuration Protocol) であり、通常のパソコンは、IPの自動設定としておけば、DHCP を用いて前述の(1),(2),(3) の情報が自動で設定される。DHCP機能は、一般的にルータや WiFi の AP(アクセスポイント)の中に組み込まれている。
DHCPサーバには、使用可能なIPアドレスを登録しておく。利用者が DHCP クライアントとして接続する際には、ブロードキャストパケットを使い、同じサブネット内に DHCP リクエストを送る。このリクエストを DHCPサーバが受信したら、サーバはクライアントに向かって、貸し出し用の IP アドレスの１つをクライアントに提供する(サブネットマスクやゲートウェイなども提供)。
データ通信ではノイズなどの影響で通信に失敗することがある。これらを補うためのTCPがある。またTCPの通信の欠点を補うUDPがある。この授業では、TCPとUDPによるトランスポート層の説明を行う。
TCP
TCP(Transmission Control Protocol/トランスミッションコントロールプロトコル)では、分割されたパケットを元の順序に組み上げたり、パケットが途中で消えた場合の再送などの処理を行う。この機能により確実に相手に送る機能が実現されている。
3way ハンドシェーク
TCPの通信では、最初に相互に通信が可能かを確認するハンドシェークが行われる。パケットには、SYN,ACK,FINといった種別を表すフラグがついており、SYNは接続確立の要求を表す。ACKは了解を表す。FINは切断要求を表す。通信開始の時には、(1)通信OK?、(2)OKだよ,そっちもOK?、(3)OKだよ! といった3つの通信パケットで確認してから通信を行う。この最初のやり取りを3way ハンドシェークという。
- SYN flood攻撃 – 3wayハンドシェークは、この後に送られてくるパケットを並び替えるためのメモリを準備などが必要となる。このため通信ルールを無視して相手にSYNパケットだけを大量に送ると相手はムダな準備作業により他の通信が困難になる場合がある。
SEQ番号,ACK番号
通信パケットには、SEQ番号(シーケンス番号/32bit)とACK番号(アクノリッジ番号/32bit)という情報がついており、送信元はACK番号を確認することで、どのパケットが正しく届いたのかを認識できる。3wayハンドシェーク時には、相手のSEQ番号に1を加えたACK番号をつけてパケットを返送することで通信が始められることが確認できる。実際のデータを送信する際には、受け取ったデータ長をSEQ番号に加えた値を、ACK番号にして受信に成功したことを相手に伝える。これにより、小分けにされたパケットで次に何を送れば良いのか判別できる。
(Acknowledge = 承認する)
通信で、パケット分割して送って、その一つ毎の返答を待つと、通信の待ち時間が増えてしまう。このため、相手が受け取り可能であれば、一度に前回の2倍のパケットを返信を待たずに送る。(ウィンドウサイズの拡大)
チェックサムとタイムアウト
通信では、送る途中でデータにノイズが混入したり、パケットが消失することがある。このため、パケットにはパケットのチェックサム(バイトデータを加算した値)を付けて送り、受信時に比較してノイズ混入でデータが壊れていないかを確認する。こういった際には、パケットが正しく届かない。パケットが消失したりして、通信相手からの返送が届かないで一定の待ち時間が経過することをタイムアウトと呼ぶ。この時、返信パケットにはデータのSEQ番号とACK番号の情報があるため、受け取りに失敗したパケットが判別できるので、送り側は失敗したパケットを再送する。
受け取り側は、同じくSEQ番号やACK番号を元にパケットの順番を正しく並べ戻すことができる。
TCP FINパケット
通信を切断する場合には、相互に切断して良いか確認する4回の通信で終了する。
UDP
TCPによる通信は、相手側からの受け取った返事を待ちながら通信を行う。このため、通信にかかる時間を要する。また、複数の利用者に一斉にデータをばらまくブロードキャスト通信では、個別のパケット欠落を修復しようとすると、処理が複雑になる。
これらの対応策として、UDP(User Datagram Protocol)がある。これは、TCP通信でのパケット分割や再送処理を行わない極めて単純な送信方法である。このため、相手側に正しくデータが送られる保証はない。確実に相手に送る必要があれば、確認や再送は上位プロトコルの責任となる。
UDP通信は返信を待つ必要がないので、動画・音声配信などのリアルタイム性が求められる通信でよく使われる。UDPは正しく通信ができずパケットが途絶えても、一時的に動画が止まるなり音声が止まるといったように、問題が少ないような場合に有用となる。
ICMP/ping
IPプロトコルのプロトコルの１つとして ICMP (Internet Control Message Protocol) がある。このプロトコルは、ネットワーク機器(ノード)の間で、通信の確認をするためのもので、ping コマンドや traceroute コマンドで使われる。
基本的に、ICMPパケットを相手コンピュータに送り、返事が返ってくるかを確認する。ping や traceroute は、返事が返ってくるまでの時間や、パケットをいくつ送っていくつ返ってきた…などの情報を表示することができ、相手コンピュータまでの通信路が正常かどうかが判断できる。
$ ping www.google.co.jp PING www.google.co.jp (172.217.25.163) 56(84) バイトのデータ 64 バイト応答 送信元 syd09s13-in-f3.1e100.net (172.217.25.163): icmp_seq=1 ttl=115 時間=7.85ミリ秒 64 バイト応答 送信元 syd09s13-in-f3.1e100.net (172.217.25.163): icmp_seq=2 ttl=115 時間=8.02ミリ秒 ^C # 途中で強制終了させるために Ctrl-C で止める ]$ traceroute www.google.co.jp traceroute to www.google.co.jp (172.217.25.163), 30 hops max, 60 byte packets 1 airstation.ei.fukui-nct.ac.jp (192.168.2.1) 0.355 ms 0.529 ms 0.549 ms (略) 9 108.170.243.33 (108.170.243.33) 8.245 ms 108.170.243.65 (108.170.243.65) 6.893 ms 6.936 ms 10 72.14.239.25 (72.14.239.25) 6.899 ms 7.125 ms 72.14.238.23 (72.14.238.23) 7.140 ms 11 syd09s13-in-f163.1e100.net (172.217.25.163) 7.014 ms 7.007 ms 6.961 ms
トランスポート層
OSI参照モデルでは、TCPプロトコルとUDPプロトコルをあわせてトランスポート層と呼び、TCP+UDPとネットワーク層のIPプロトコルでの通信が、今日のインターネット通信の基本プロトコルとなっており、総称して TCP/IPとかインターネット・プロトコル・スイート と呼ぶ。(suite=”一連のものや一緒に機能するものの集まり”/sweetじゃない)
2分木による構文木とデータベースとB木
コンパイラの処理の流れ
構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。
Cコンパイラのソース ↓ プリプロセッサ (#define,#includeなどの処理) ↓ コンパイラ ・字句解析(ソースコードをトークンに切り分ける) ・構文解析(トークンから構文木を生成) ・最適化(命令を効率よく動かすために命令を早い命令に書き換え) ・コード生成(構文木から中間コードを生成) | | リンカでライブラリと結合 （+）←---ライブラリ ↓ 機械語
2項演算と構文木
演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。
＋ ／ ＼ １ ＊ ／ ＼ ２ ３
演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして、上記の構文木のデータを作る処理と、その構文木の値を計算するプログラムを示す。
struct Tree {
int data ;
struct Tree* left ;
struct Tree* right ;
} ;
struct Tree* tree_int( int x ) // 数値のノード
{
struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->data = x ;
n->left = n->right = NULL ;
}
return n ;
}
struct Tree* tree_op( int op , // 演算子のノード
struct Tree* l , struct Tree* r ) {
struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) { // ~~~~~~~~~~~~~~~~~~~~~(D)
n->data = op ;
n->left = l ;
n->right = r ;
}
return n ;
}
// 与えられた演算子の木を計算する関数
int eval( struct Tree* p ) {
if ( p->left == NULL && p->right == NULL ) {
// 数値のノードは値を返す
return p->data ;
} else {
// 演算子のノードは、左辺値,右辺値を求め
// その計算結果を返す
switch( p->data ) {
case '+' : return eval( p->left ) + eval( p->right ) ;
case '*' : return eval( p->left ) * eval( p->right ) ;
} // ~~~~~~~~~~~~~~~(E) ~~~~~~~~(F)
}
}
void main() {
struct Tree* exp = // 1+(2*3) の構文木を生成
tree_op( '+' ,
tree_int( 1 ) ,
tree_op( '*' ,
tree_int( 2 ) ,
tree_int( 3 ) ) ) ;
printf( "%d¥n" , eval( exp ) ) ;
}
理解度確認
- 上記プログラム中の(A)～(F)の型を答えよ。
2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。
B木の構造
2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータ d0, … , d2N-1 と、2N+1本のポインタ p0, … , p2N から構成される。pi の先には、di-1< x < di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。下図は位数2のB木の例を示す。
B木からデータの検索
データを探す場合は、ノード内のデータ di の中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O( log N ) となる。
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の例 2つの表の串刺し)) -- 60点以上の学生名,科目名,点数を出力 -- 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++ ) // 結合(from) for( re = 0 ; re < 3 ; re++ ) if ( student[ st ].ID == result[ re ].ID // 選択(where) && result[ re ].point >= 60 ) printf( "%s %s %d" , // 射影(select) student[ st ].name , result[ re ].subject , result[ re ].point ) ;
- 学生と成績(Paiza.ioでSQL)
- sql-mapping.cxx
B+木
データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。
そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。下図で示すB+木では、青で示す検索用のB木の部分と、赤で示す順次処理を行うためのシーケンスセットの部分から構成される。
ネットワーク層とIPアドレス
前回説明したMACアドレスによるデータリンク層では、１つのサブネットの中で指定した相手にデータを送ることはできる。しかし、データリンク層だけでは、他のサブネットにいる相手にデータを送ることができない。(相手の名前を知っていても、住所を知らなければ郵便は送れない。)
ネットワーク層とIPアドレス(IPv4)
サブネットに分割し、隣接するサブネット、さらには上流のインターネットと通信をするためには、IPアドレスを用いた通信が行われる。
ネットワークに接続する機器には、それぞれユニークな32bitの番号(IPv4アドレス)を割り振る。
コンピュータへのIPアドレスの設定には、(a)IPアドレス,(b)サブネットマスク,(c)ゲートウェイの情報が必要となる。
- IPアドレス: 192.156.145.100 といった、0～255の8bitの値をピリオド区切りで4つ並べて表記するのが一般的。
- サブネットマスク: 255.255.255.0 といった値で、IPアドレスを2進数で書き並べた32bitと、サブネットマスクの32bitで、2進数の論理積をとった値は、ネットワーク番号と呼ばれ、機器が存在する場所を表す。
また、IPアドレスとサブネットマスクの否定と論理積をとった値は、ホスト番号と呼ばれる。
サブネットマスクは、先行する1のbit数で書き表すことも多い。255.255.255.0は、”/24″のように書く。 - ゲートウェイ: 自分自身のネットワーク番号と通信相手のネットワーク番号が異なる場合は、異なるサブネットにいるので、パケットを中継してもらう機器(ルータ,ゲートウェイ)にパケットを送る。
- IPアドレスとクラス: IPアドレスは、先頭8bit をネットワーク番号とするクラスA,16bitのクラスB,24bitのクラスCに分類されている。以前は、IPアドレスを割り当てる企業規模に応じて、大規模な大学だからクラスA、中規模ならクラスB(福井大学は133.7.0.0/16 ←このような書き方はCIDR記法という)、小規模ならクラスCを割り当てていた。(福井高専はCクラスを5本192.156.145～149.0/24 : 福井高専のIPアドレスでは3つのCIDR記法で表現できる。 192.156.145.0/24, 192.156.146.0/23, 192.156.148.0/23)
しかし、最近では IPv4 アドレスの不足から、大きな組織に割り振られた クラスA を再分配しているため、先頭が0～126で始まるアドレスでも大きなネットワーク組織とは限らない。
ユニキャスト、マルチキャスト、ブロードキャスト通信
通信では、機器が1対1でデータを送る(ユニキャスト通信)だけでなく、複数の機器に同時にデータを送りたいこともある。
同じサブネット内の全てにデータを送る時には、ブロードキャスト通信が用いられる。この際には、IPアドレスのサブネットにおけるホスト番号部分が全て1のアドレスを使う。Cクラスの 192.168.11.x/24 のネットワークであれば、192.168.11.255 がブロードキャスト通信用のアドレスとなる。一般的にホスト番号部分が全て0のアドレスは、サブネット全体を表すために使われることから、192.168.11.0 のIPアドレスも通常の通信には使えない。このため、Cクラス(サブネットマスク24bit)であれば、256台-2台(全て0と全て1のホスト番号)を引いた254台の機器が設置できる。(実際には、他のネットワークに接続するためのゲートウェイアドレスも必要なので 253台)
動画などの配信では、ユニキャスト通信が使われると、サーバから通信相手までのルータまでに同じデータが送られてくる。こういった方式では大量の視聴者がいる場合、ネットワークの帯域が埋まってしまい、効率の良い配信ができない。同じデータを同じタイミングで複数の機器に配信したい場合はマルチキャスト通信を使う。IPv4では 224.0.0.0/4 を使う。
ARP(IPアドレスとMACアドレスの橋渡し)
同じサブネットの中では、データリンク層でMACアドレスを用いて通信相手を指定するが、ネットワーク層ではIPアドレスを用いて通信相手を指定する。この違いを埋めるためのプロトコルがARPである。
サブネット内に相手先IPアドレスの指定されたパケット(10.10.22.102)が届くと、通信機器はサブネット内の全ての機器相手に ARPリクエストを送信する。(10.10.22.102はいますか？ブロードキャスト通信を使う)
この時、10.10.22.102 のコンピュータは、自分宛てのパケットがあることを知るので、送信元のコンピュータに、自分のMACアドレスを付けたARPリプライを送り返す。(10.10.22.102は、私 “FE:DC:BA:98:76:54” です!)。送信元は、ARP通信をへらすために、その情報を記憶して、2度目以降は覚えたMACアドレスですぐに通信を始める。
ルータとRIP
ルータは、隣接するサブネットの間に入る機器で、各サブネットにゲートウェイとなるインタフェースを持つ。ルータの内部では受け取ったパケットをどこに流すか…という経路情報が重要となる。
- 静的ルーティング – 末端のルータの設定で、管理者が経路を設定
- 動的ルーティング – 上流ルータでRIPにより設定
経路設定には2種類あり、(a)末端のルータではこのネットワーク番号はどのルータに送るという情報をルータに直接設定する静的ルーティングがとられる。(b)上流のルータでは、末端のルータの設定が変更されることがあるので、ルータ同士がルーティング情報を送りあう動的ルーティングがとられる。動的ルーティングでは、RIPというプロトコルにより、各サブネットのつながっている経路情報が送られてくる。この経路情報を見て、パケットのIPアドレスを見て、パケットの送り先を判断する。(ネットワークの上流では、複数のネットワーク経路を操る BGP などが使われる)
((Windows の場合))
C:> ipconfig
インタフェース名:
IPv4アドレス............192.168.xx.xx
サブネットマスク.........255.255.255.0
デフォルトゲートウェイ....192.168.xx.1
C:> arp -a
インタフェース:
192.168.xx.xx 74-03-xx-xx-xx-xx 動的
192.168.xx.yy B0-05-xx-xx-xx-xx 動的
C:> netstat -r
ネットワーク宛先 ネットマスク ゲートウェイ インタフェース メトリック
0.0.0.0 0.0.0.0 192.168.xx.1 192.168.xx.xx 45
192.168.xx.0 255.255.255.0 ....
((Unix の場合))
$ ifconfig -a # もしくは ip addr
en1: ....
inet 192.168.xx.xx netmask 0xffffff00 ...
$ arp -an # もしくは ip neigh
.... (192.168.xx.xx) at 74:03:xx:xx:xx:xx ...
.... (192.168.xx.yy) at b0:05:xx:xx:xx:xx ...
$ netstat -rn # もしくは ip route
Destination Gateway ...
default 192.168.xx.1 ...
192.168.xx ...
プライベートアドレス
IPv4 では、32bit でコンピュータを識別することから、最大でも 232台≒40億台(4×103×3台)しか識別できない。実際、IPアドレスの管理団体では、2017年度には IPv4 アドレスは使い切った状態となっている。この対応として、その組織やその家庭内だけで使われる IPアドレス である、プライベートアドレスが用いられる。
- 10.0.0.0～10.255.255.255 / 8 – 大きな機関向け
- 172.16.0.0～172.31.255.255 / 12
- 192.168.0.0～192.168.255.255 /16 – 個人向け
プライベートアドレスを利用する組織では、インターネットに接続するルータでは NAT(もしくはNAPT) という機能を内蔵し、プライベートアドレスとグローバルアドレスの変換を行う。
ローカルループバックアドレス
ネットワーク通信では、1つのコンピュータの中でもプロセスとプロセスの間でデータ通信を行うことも多い。この時に使われるIPアドレスは、ローカルループバックアドレスと呼ばれ、IPv4では 127.0.0.1 のIPアドレスを使う。このアドレスには localhost というドメイン名が割り振られる。
IPv6アドレス
IPv4の32bit の IP アドレスでは、40億台のコンピュータを区別することしかできない。そこで、最近では 128bit の IPv6 アドレスが用いられる(256×102412台≒340×1036台)。 IPv6 では、2004:6800:4004:0826:0000:0000:0000:2003 (www.google.co.jp) といった16進数4桁(16bit)を8個を”:”区切りで書き連ねる書き方をする。ただし16進4桁の先行する0や、全部”0000″ は省略して、”2404:6800:4004:826::2003″ と書く。IPv6 は最近では普及がかなり進んでいるが、途中のルータなどがすべて IPv6 に対応する必要があり IPv4 しか使えない組織も多い。
IPv6でも、同じサブネット内だけで使えるIPv6リンクローカルアドレス(fe80::/10)や、同じ組織内だけで使えるIPv6サイトローカルアドレス(fec0::/10)、ループバックアドレス(::1)などが規定されている。
DNS と nslookup
IPアドレスみたいな数字の羅列は覚えることが難しい。このためコンピュータの名前からIPアドレスを調べるサービスがあり、Domain Name Service(DNS) と呼ばれる。詳しい仕組みは ドメイン名の説明の際に行うが、IP アドレスの調べ方を説明する。
ドメイン名から、IP アドレスを調べるには、nslookup (もしくは dig) を使用する。
$ nslookup www.fukui-nct.ac.jp : Non-authoritative answer: Name: www.fukui-nct.ac.jp Address: 104.215.53.205 $ nslookup -query=A www.fukui-nct.ac.jp # IPv4 アドレスの取得 (同上) # もしくは dig www.fukui-nct.ac.jp A +short $ nslookup -query=AAAA www.google.co.jp # IPv6 アドレスの取得 : # もしくは dig www.google.co.jp AAAA +short Non-authoritative answer: Name: www.google.co.jp Address: 2404:6800:4004:826::2003
理解確認
- Formsによる理解度確認問題
- 192.168.11.2/24 のコンピュータから、192.168.1.50にデータを送る場合、どのような処理が行われるか、IPアドレス、サブネットマスク、ゲートウェイ、ネットワーク番号を使って説明せよ。
- 同じサブネット内で相手のIPアドレスが与えられた時、どのようにパケットが送られるか、MACアドレスとARPを交えて説明せよ。
ERモデル
データベースの設計
リレーショナル・データベースでは、データは表形式であればなんでも良い訳ではない。
例えば、学生の成績データが以下のような構造であった場合、
|
- 修正不整合: 授業担当が saitoh → takaku のように変更になったら、複数のテーブルを修正しなければならない。大量のレコード修正は、時間がかかるし、その途中にシステムダウンしたらデータの整合性に問題が発生するかも。
- 挿入不整合: 新しい科目 internet を追加したいけど、受講学生が決まらないとデータを挿入できない。
- 削除不整合: yamada が受講を取りやめたら、科目 media も消えてしまう。
これらを考慮すると、以下のような3つの表で設計するべきである。
■学生(実体)
|
■受講(関係)
30203を消してもmedia |
■科目(実体)
saitoh→takakuに変更したら internetを追加しても問題なし |
データベースの設計では、(1)概念設計、(2)論理設計、(3)物理設計が行われる。
- 概念設計：概念スキーマの決定(実体・関係モデルを使う)。上記の受講データベースの設計例
- 論理設計：論理スキーマの決定。関係データベースで実装？ほかのデータベース？
- 物理設計：物理スキーマの決定。データの格納方法や管理方法を決める。
実体関連モデル(ERモデル)
データベース設計では、実体関連モデル(ERモデル:Entity-Relation model)が使われる。 実体とは、モデル化しようとする対象で独立した存在となれるもの。 実体が持つ色々な特性は属性と呼ばれる。 属性の取りうる値の集合を定義域、同一種類の実体の集まりを実体集合と呼ぶ。 関連とは、実体同士の相互関係をモデル化したもの。
実体関連図(ER図)では、実体を長方形、関連をひし形、属性を楕円で表現する。 属性で、キーとなるものには下線をつけて表す。
ER図で調べると、実際にはもっと細かい規定で表現が行われている。 参考：IDEF1X表記とIE表記
意思決定木と演算子
データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。
意思決定木
意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。
((意思決定木の例:小さい子供が発熱した時)) 38.5℃以上の発熱がある？ no／ ＼yes 元気がある？ むねがひいひい？ yes／ ＼no no／ ＼yes 様子をみる 氷枕で病院 解熱剤で病院 速攻で病院
このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。
struct Tree {
char *qa ;
struct Tree* yes ;
struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
struct Tree* l , struct Tree* r )
{ struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->qa = s ;
n->yes = l ;
n->no = r ;
}
return n ;
}
void main() {
struct Tree* p =
dtree( "38.5℃以上の発熱がある?" ,
dtree( "胸がひぃひぃ?" ,
dtree( "速攻で病院", NULL,NULL ) ,
dtree( "解熱剤で病院",NULL,NULL ) ) ,
dtree( "元気がある?" ,
dtree( "様子をみる", NULL,NULL ) ,
dtree( "氷枕で病院", NULL,NULL ) ) ) ;
// 決定木をたどる
struct Tree* d = p ;
while( d->yes != NULL || d->no != NULL ) {
printf( "%s¥n" , d->qa ) ;
scanf( "%d" , &ans ) ;
// 回答に応じてyes/noの枝に進む。
if ( ans == 1 ) // yesを選択
d = d->yes ;
else if ( ans == 0 ) // noを選択
d = d->no ;
}
// 最終決定を表示
printf( "%s¥n" , d->qa ) ;
}
2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。
逆ポーランド記法
一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。
演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。
中置記法 1+2*3 前置記法 +,1,*,2,3 後置記法 1,2,3,*,+ # 1と「2と3をかけた値」をたす。
後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。
演算子の右結合・左結合
例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？
一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。
ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。
理解度確認
以下の式を指定された書き方で表現せよ。
逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。 中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。
以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。
GROUP BY HAVINGとビューテーブル
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 優良業者.所在 = '福井' ;
-- 文房具データベース --
CREATE VIEW 文房具データベース ( 業者名 , 商品名 , 在庫量 )
AS SELECT S.業者名, G.商品名, SG.在庫量
FROM S, SG, G
WHERE S.業者番号 = SG.業者番号 and SG.商品番号 = G.商品番号 ;
-- VIEWの確認 --
SELECT * FROM 文房具データベース ; -- 串刺ししたデータベースに見える
----- 実行結果 -----
業者名 商品名 在庫量
ABC社 赤鉛筆 300
ABC社 ノート 200
ABC社 消しゴム 400
ABC社 消しゴム 200
ABC社 筆箱 100
ABC社 バインダ 100
LMN社 赤鉛筆 300
LMN社 ノート 400
PQR社 ノート 200
STU社 ノート 200
STU社 消しゴム 300
STU社 筆箱 400
ビューテーブルに対する SQL を実行すると、システムによっては予め実行しておいた CREATE VIEW の AS 以下の SQL の実行結果をキャッシュしておいて処理を行うかもしれない。システムによっては SQL の命令を 副クエリを組合せた SQL に変換し、処理を行うかもしれない。しかし、応用プログラマであれば、その SQL がどのように実行されるかは意識する必要はほとんど無いであろう。
ただし、ビューテーブルに対する 挿入・更新・削除といった演算を行うと、データによっては不整合が発生することもあるので注意が必要である。
SQL言語
教科書の流れに沿ってSQLの言語について、再掲
- スキーマ定義
- CREATE – 実テーブル、ビューテーブルの定義
- GRANT – 権限の定義
- スキーマ操作
- DROP – 実テーブル、ビューテーブルの削除
- REVOKE – 権限の削除
- ALTER – テーブルの変更
- ADD – カラムの追加
- データ操作
- SELECT, INSERT, DELETE, UPDATE – レコードの検索、追加・削除・更新
- トランザクション処理
- データベースでは、原子性などを満たすためにデータベースへの更新履歴を保持している。これらの更新履歴をデータベースに反映させ確定する処理がトランザクション処理。
- COMMIT – データベースの更新処理を確定
- ROLLBACK – データベースの更新処理を取り消す
ホスト言語とのインタフェースとSQLインジェクション
プログラミング言語によっては、その言語の中でSQLを使うために「組み込み型のSQL」が使えるものがある。
(COBOL,PL/Iなど)
動的メモリ管理が得意な最近のPythonやPHPなどの言語であれば、データベース参照の関数が利用できる。
SQLインジェクション
例えば、PHPでは、SQLからデータを取り出す処理は、以下のようになる。
// 検索するユーザID
$id = "t-saitoh" ;
$pdo = new PDO( '...' ) ; // データベースに接続する関数
$sql = "select name from usertable where id='$id'" ;
$query = $pdo->prepare( $sql ) ;
// 取り出せたデータに関する処理 id がプライマリキーならforeachは1回ループのはず
foreach( $query->fetcAll() as $name ) {
// $name に取り出した名前が入っている
}
しかし、$id の部分を、Web の入力フォームなどの値であれば、名前以外の情報が入力される場合もある。
この際に、「 $id = ” ‘ or 1==1 — ‘ ” 」といった値が入っていた場合、SQLで実行される命令は、
$id = "' or 1==1 --'" の場合 $sql = "select name from usertable where id='' or 1==1 -- ''" ;
となってしまい、本来なら1人のデータを抽出する select 命令が、全テーブルに対して該当してしまい、情報漏洩が発生するかもしれない。
「 $id = “‘; drop usertable ; — ‘” 」であれば、usertable が消されてしまい、システムが動かなくなる(サービスを提供できなくする攻撃 = DoS攻撃 – Denial-of-service attack)ことも考えられる。
他にもSQLインジェクションを使う技がある。こちらの CTF の WriteUp などが参考になる。
こういった攻撃手法は、SQLに本来の意図ではないSQL命令を紛れ込ませる攻撃ということで、SQLインジェクションという。
SQLインジェクションで発生した有名な事件では、以下のようなものがある。
- Yahoo! BB 顧客情報漏洩事件 – 100億円を超える被害
- PlayStation Network個人情報流出事件
対策としては、ユーザが入力したデータを用いて SQL 命令を実行する場合は、ユーザ入力をSQLとして悪用されないように、シングルクオートなどをエスケープするなどの処理が必要となる。さまざまな手法があるので、SQL無効化の専用関数を用いるべき。
また、データベースシステムは、ネットワーク経由でSQLによる処理を行うが、データベースサーバ自体がインターネットに接続されていて、パスワード攻撃によりデータベース本体に不正アクセスが行われる場合もある。一般的なデータベースを用いたシステムは、フロントエンドのWebサーバ、スレーブDBサーバ、マスタDBサーバの三層構成をとることが多いが、バックエンドのデータベースは、インターネットから隔離しフロントエンドのWebサーバのみ接続できるようにするのが一般的である。
データベースに接続する場合はパスワードにより利用者を限定することができるが、データベースシステム自体がインターネットに接続されていると、パスワード総当たり攻撃(ブルートフォース攻撃)や、パスワードスプレー攻撃(総当たり攻撃は、短時間でパスワード失敗が多発するのでシステムで接続拒否するのが一般的。これを回避するために時間をかけて総当たり攻撃をする手法)により、情報漏洩が発生する。
CTF問題とセキュリティ(4年実験)
この実験では、セキュリティコンテストのCTF問題(Capture The Flag競技)について、インターネットの仕組みを理解し、その問題の解き方を考え、新しく自分自身でCTF問題を作ってもらいます。
日程
実験は、4週にわたり、以下の日程で行います。
| 週 | 内容 |
| 1 | (前半)暗号・ファイル・Web |
| 2 | |
| 3 | (後半) プログラム作成・インターネット・OS |
| 4 |
前半・後半でそれぞれ、問題例(もしくは自分で見つけたCTF問題)の1つの説明と、自作の問題を新しく作り説明をしてください。
提出物
- 実験の目的
- 問題例(or 自分で見つけたCTF問題)を1つ選び
- 前半・後半それぞれについて
- その問題が情報セキュリティにどう関係しているのか
- 問題の解き方のしくみと解説
- 自作問題について
- 前半・後半それぞれ
- その問題が情報セキュリティにどう関係しているのか
- 問題の解き方、問題の作り方
- しくみと解説
- 提出先はこちらのTeams共有フォルダに。
- 自作問題の例
- サブリミナル効果で隠されたGIF
- 電子透かし
- 学校からアクセスする時だけ、答えが見える。(REMOTE_HOST)
- スマホでアクセスした時だけ、答えが見える。(HTTP_USER_AGENT)
- Google 検索した後だけ、答えが見える。(HTTP_REFERER)
専攻科実験・コンパイラと関数電卓プログラム作成
- コンパイラの技術と関数電卓プログラム(1)
- 再帰下降パーサによる構文解析(LL法)による電卓プログラム作成
- 補助資料：コンパイラの技術と関数電卓プログラム(1-2)
- 課題
- 複数桁の数字が使えること。
- 式中に空白が使えること。
- 何らかの演算子を追加すること。
- (例) %,単項演算子のマイナスなど
- 演算子が左結合か右結合か確認すること。
- オプション課題
- 変数が使えること。
(変数名は1文字のA-Zといったもので良い)
- 変数が使えること。
- レポート内容
- コンパイラ技術の概要、課題(1)の説明・最終的なBNF記法・ソース・動作検証、考察
- コンパイラの技術と関数電卓プログラム(2)
- コンパイラツールを使ったLR構文解析による電卓プログラムの作成
- 補助資料：専攻科実験: unix系 開発環境のインストール
- 課題
- 基本的に、lex+yaccで(1)と同様の課題で参考資料を元に改良を行う。
- レポート内容
- lex,yaccの概要、課題(2)の説明・ソース・動作検証、考察