ホーム » 2023 (ページ 2)
年別アーカイブ: 2023
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)の説明・ソース・動作検証、考察
AVL木と2分ヒープ
2分探索木へのデータ追加と不均一な木の成長
先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。
しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか？
- 86, 53, 11 – 降順のデータ
- 12, 24, 42 – 昇順のデータ
この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。
AVL木
このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで検索回数を改善できる。例えば、以下のような木では、赤の左側に偏っている。
このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、木の段数を均一に近づけることができる。この例では、11,65,92の木が、右回転して 11 の木の位置が上がっている。(右回転)
この様に、左右の枝の大きさが不均一な場所を見つけ、右回転や左回転を行う処理を繰り返すことで、段数が均一な2分探索木に修正ができる。この様な処理でバランスの良い木に修正された木は、AVL木と呼ばれる。
理解確認
- 木の根からの段数を求める関数 tree_depth() を作成せよ。
例えば、上のAVL木の説明の図であれば、4段なので4を返すこと。
// 木の段数を数える関数
_____ tree_depth( _______________ p ) {
if ( p == NULL ) {
return _____ ;
} else {
int d_L = ______________ ;
int d_R = ______________ ;
if ( d_L > d_R )
return _____ ;
else
return _____ :
}
}
// pをつなぎ替え上部を返り値で返す。
struct Tree*rot_right( struct Tree* p ) {
struct Tree* pl = p->left ;
struct Tree* pr = pl->right ;
pl->right = p ;
p->left = = pr ;
return pl ;
}
int main() {
printf( "%d¥n" , tree_depth( top ) ) ;
top = rot_right( top ) ;
return 0 ;
}
2分ヒープ(binary heap)
2分探索木では、１つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。
これらの問題の解決法の１つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝は 2×i+1 番目、右の枝は 2×i+2 番目であることが判る。
このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、O(log(N))で挿入が可能となる。
int a[ 7 ] = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;
// 2分ヒープを表示
void print_heap( int array[] , int idx , int size ) {
if ( idx < size ) {
// 左の枝を表示
print_heap( array , 2*idx + 1 , size ) ;
// 真ん中の枝を表示
printf( "%d " , array[ idx ] ) ;
// 右の枝を表示
print_heap( array , 2*idx + 2 , size ) ;
}
}
// 2分ヒープから key を検索
int find_heap( int array[] , int idx , int size , int key ) {
while( idx < size ) {
if ( array[ idx ] == key )
return idx ; // 見つかったら配列の番号を返す
else if ( array[ idx ] _____ key ) // 何が入るか考えよう
idx = ________________ ;
else
idx = ________________ ;
}
return -1 ; // 見つからなかったら、-1 を返す
}
int main() {
print_heap( a , 0 , 7 ) ;
if ( find_heap( a , 0 , 7 , 65 ) >= 0 )
printf( "Find!!¥n" ) ;
return 0 ;
}
レポート課題
以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。
- 名前(name)と電話番号(phone)
- 名前(name)と誕生日(year,mon,day)
- 名前(name)とメールアドレス(mail)
プログラムは以下の機能を持つこと。
- 1行1件でデータを入力し、2分木に追加できること。
- 全データを昇順(or降順)で表示できること。
- 検索条件を入力し、目的のデータを探せること。
レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。
集約関数と副問い合わせ
特殊な条件演算子
WHERE 節の中で使える特殊な条件演算子を紹介する。
... AND ... WHERE S.業者番号 <= 100 AND S.業者番号 >= 200 ; ... OR ... WHERE S.業者番号 >= 100 OR S.業者番号 <= 200 ; NOT ... WHERE NOT S.業者番号 >= 100 ; ... IN ... WHERE S.業者番号 IN ( 'S1' , 'S4' ) ; ... BETWEEN A AND B WHERE S.優良度 BETWEEN 50 AND 100 ; ... LIKE ... WHERE S.業者名 LIKE 'A_C社' ; _ は任意の1文字 ABC社 ADC社 WHERE S.業者名 LIKE 'A%社' ; % は任意の0～N文字 A社, AA社 ABC社 ... IS NULL WHERE S.業者名 IS NULL WHERE S.業者名 IS NOT NULL
集約関数
集約関数は、SQL の SELECT の射影部分で使える関数で、出力対象となった項目に対して、COUNT(),SUM(),AVG()といった計算を行うもの。
COUNT() - 項目の数 SUM() - 項目の合計 AVG() - 項目の平均 MAX() - 項目の最大値 MIN() - 項目の最低値 SELECT COUNT(S.業者番号) FROM S WHERE S.優良度 > 20 ;
集合計算
複数の SQL の結果に対し、集合和, 集合積, 集合差などの処理を行う。
... UNION ... 集合和 ... EXPECT ... 集合差 ... INTERSECT ... 集合積 SELECT S.業者名 FROM S WHERE S.所在 = '福井' UNION SELECT S.業者名 FROM S WHERE S.所在 = '東京'
SQLの副問い合せ
前節の結合処理は時として効率が悪い。このような場合は、副問い合わせを用いる場合も多い。
SELECT S.業者名, S.所在
FROM S
WHERE S.業者番号 IN
( SELECT SG.業者番号
FROM SG
WHERE SG.商品番号 = 'G2'
AND SG.在庫量 >= 200 ) ;
まず、『◯ IN { … }』 の比較演算子は、◯が{…}の中に含まれていれば真となる。また、SQLの中の (…) の中が副問い合わせである。
この SQL では、副問い合わせの内部には、テーブル S に関係する要素が含まれない。この場合、副問い合わせ(商品番号がG2で在庫量が200以上)は先に実行される。
{ (S1,G2,200), (S2,G2,400), (S3,G2,200), (S4,G2,200) }が該当し、その業者番号の{ S1, S2, S3, S4 }が副問い合わせの結果となる。最終的に SELECT … FROM S WHERE S.業者番号 IN { ‘S1’, ‘S2’, ‘S3’, ‘S4’ } を実行する。
相関副問い合わせ
SELECT G.商品名, G.色, G.価格
FROM G
WHERE 'S4' IN
( SELECT SG.業者番号
FROM SG
WHERE SG.商品番号 = G.商品番号 ) ;
この副問い合わせでは、内部に G.商品番号 が含まれており、単純に()内を先に実行することはできない。こういった副問い合わせは、相関副問い合わせと呼ばれる。
処理は、Gのそれぞれの要素毎に、副問い合わせを実行し、その結果を使って WHERE節の判定を行う。WHERE節の選択で残った結果について、射影で商品名,色,価格が抽出される。
// 概念の説明用に、C言語風とSQL風を混在して記載する
for( int i = 0 ; i < sizeofarray( G ) ; i++ ) {
SELECT SG.業者番号 FROM SG
WHERE SG.商品番号 = G[i].商品番号 を実行
if ( WHERE 'S4' IN 副query の結果が真なら ) {
printf( ... ) ;
}
}
// 全てのG 副queryの結果 WHERE 射影
// G1 -> {S1,S2}
// G2 -> {S1,S2,S3,S4} -> ◯ -> (ノート,青,170)
// G3 -> {S1}
// G4 -> {S1,S4} -> ◯ -> (消しゴム,白,50)
// G5 -> {S1,S4} -> ◯ -> (筆箱,青,300)
// G6 -> {S1}
演習課題
Paiza.io などを使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。
さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。
考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。