ホーム » スタッフ » 斉藤徹 » 講義録

講義録」カテゴリーアーカイブ

2021年11月
 123456
78910111213
14151617181920
21222324252627
282930  

最新の投稿(電子情報)

アーカイブ

カテゴリー

データベーステスト前授業

本来は、データベースの正規形に関連する話題を説明する予定であったが、後期の中間試験以降の範囲なので、新しい内容の説明は止めることとした。代わりに、過去のテスト問題の事例を示し、レポート課題を作成する時間とした。

Linux演習

Linux演習資料

理解度確認

B木とデータベース

2分探索木の考え方を拡張したもので、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(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の例 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 ) ;

B+木

データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。下図で示すB+木では、青で示す検索用のB木の部分と、赤で示す順次処理を行うためのシーケンスセットの部分から構成される。

ホスト言語とのインタフェースとERモデル

今日は、前半でホスト言語とSQLのインタフェースとその問題点について説明し、後半では次の章の目標となる適切なデータベース設計のための導入を説明する。

ホスト言語とのインタフェースと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インジェクションで発生した有名な事件では、以下のようなものがある。

対策としては、ユーザが入力したデータを用いて SQL 命令を実行する場合は、ユーザ入力をSQLとして悪用されないように、シングルクオートなどをエスケープするなどの処理が必要となる。さまざまな手法があるので、SQL無効化の専用関数を用いるべき。

また、データベースシステムは、ネットワーク経由でSQLによる処理を行うが、データベースサーバ自体がインターネットに接続されていて、パスワード攻撃によりデータベース本体に不正アクセスが行われる場合もある。一般的なデータベースを用いたシステムは、フロントエンドのWebサーバ、スレーブDBサーバ、マスタDBサーバの三層構成をとることが多いが、バックエンドのデータベースは、インターネットから隔離しフロントエンドのWebサーバのみ接続できるようにするのが一般的である。

データベースに接続する場合はパスワードにより利用者を限定することができるが、データベースシステム自体がインターネットに接続されていると、パスワード総当たり攻撃(ブルートフォース攻撃)や、パスワードスプレー攻撃(総当たり攻撃は、短時間でパスワード失敗が多発するのでシステムで接続拒否するのが一般的。これを回避するために時間をかけて総当たり攻撃をする手法)により、情報漏洩が発生する。


データベースの設計

リレーショナル・データベースでは、データは表形式であればなんでも良い訳ではない。

例えば、学生の成績データが以下のような構造であった場合、

 ID   | name   | grade | subject  | teacher
------+--------+-------+----------+---------
20101 | aoyama |   1   | database | saitoh
20101 | aoyama |   1   | software | murata
20002 | suzuki |   2   | database | saitoh
20002 | suzuki |   2   | compiler | nishi
30203 | yamada |   3   | media    | ogoshi
  • 修正不整合: 授業担当が saitoh → takaku のように変更になったら、複数のテーブルを修正しなければならない。大量のレコード修正は、時間がかかるし、その途中にシステムダウンしたらデータの整合性に問題が発生するかも。
  • 挿入不整合: 新しい科目 internet を追加したいけど、受講学生が決まらないとデータを挿入できない。
  • 削除不整合: yamada が受講を取りやめたら、科目 media も消えてしまう。

これらを考慮すると、以下のような3つの表で設計するべきである。

学生                      受講            科目
ID    | name   | grade    ID   | SubID   SubID | subject | teacher
------+--------+-------  ------+-------  ------+----------+--------
20101 | aoyama | 1       20101 | 1001     1001 | database | saitoh → takaku
20002 | suzuki | 2       20101 | 1002     1002 | software | murata
30203 | yamada | 3       20002 | 1001     1003 | compiler | nishi
                         20002 | 1003     1004 | media    | ogoshi
                  消す→ 30203 | 1004     1005 | internet | foobar → 追加

データベースの設計では、(1)概念設計、(2)論理設計、(3)物理設計が行われる。

  • 概念設計:概念スキーマの決定(実体・関係モデルを使う)。上記の受講データベースの設計例
  • 論理設計:論理スキーマの決定。関係データベースで実装?ほかのデータベース?
  • 物理設計:物理スキーマの決定。データの格納方法や管理方法を決める。

実体関連モデル(ERモデル)

データベース設計では、実体関連モデル(ERモデル:Entity-Relation model)が使われる。 実体とは、モデル化しようとする対象で独立した存在となれるもの。 実体が持つ色々な特性は属性と呼ばれる。 属性の取りうる値の集合を定義域、同一種類の実体の集まりを実体集合と呼ぶ。 関連とは、実体同士の相互関係をモデル化したもの

実体関連図(ER図)では、実体を長方形、関連をひし形、属性を楕円で表現する。 属性で、キーとなるものには下線をつけて表す。

ER図で調べると、実際にはもっと細かい規定で表現が行われている。 参考:IDEF1X表記とIE表記

演算子と2分木による式の表現

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 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

逆ポーランド記法の式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '
// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
         //    ~~~~~~~~(B)
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}
' ; p++ ) { if ( isdigit( *p ) ) { // ~~(A) // 数字はスタックに積む push( *p - '0' ) ; // ~~~~~~~~(B) } else if ( *p == '+' ) { // 演算子+は上部2つを取出し int r = pop() ; int l = pop() ; // 加算結果をスタックに積む push( l + r ) ; } else if ( *p == '*' ) { // 演算子*は上部2つを取出し int r = pop() ; int l = pop() ; // 乗算結果をスタックに積む push( l * r ) ; }//~~~~~~~~~~~~~(C) } // 最終結果がスタックに残る return pop() ; } void main() { printf( "%d\n" , rpn( "123*+" ) ) ; }

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

   +
  / \
 1   *
    / \
   2   3

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝が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 ) ) ;
}

理解度確認

  • push(),pop() のスタックは、保存と取り出しの順序を表す単語の頭文字4つを使って何と呼ばれるか?
  • 上記プログラム中の(A)~(F)の型を答えよ。

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 ;

この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 がどのように実行されるかは意識する必要はほとんど無いであろう。

ただし、ビューテーブルに対する 挿入・更新・削除といった演算を行うと、データによっては不整合が発生することもあるので注意が必要である。

SQL言語

教科書の流れに沿ってSQLの言語について、再掲

  • スキーマ定義
    • CREATE – 実テーブル、ビューテーブルの定義
    • GRANT – 権限の定義
  • スキーマ操作
    • DROP – 実テーブル、ビューテーブルの削除
    • REVOKE – 権限の削除
    • ALTER – テーブルの変更
    • ADD – カラムの追加
  • データ操作
    • SELECT, INSERT, DELETE, UPDATE – レコードの検索、追加・削除・更新
    • トランザクション処理
      • データベースでは、原子性などを満たすためにデータベースへの更新履歴を保持している。これらの更新履歴をデータベースに反映させ確定する処理がトランザクション処理。
      • COMMIT – データベースの更新処理を確定
      • ROLLBACK – データベースの更新処理を取り消す

昨年度の資料では、次のネタも入っていたけど、後半の授業を演習時間とするため、説明はここまで。

意思決定木と構文解析

前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:うちの子供が発熱した時))
       38.5℃以上の発熱がある?
      no/         \yes
   元気がある?        むねがひいひい?
 yes/    \no      no/     \yes
様子をみる 氷枕で病院  解熱剤で病院  速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。

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分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

  • インタプリタ(interpreter:通訳)
    • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
  • コンパイラ(compiler:翻訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
  • トランスレーター
    • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
      最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
  • バイトコードインタプリタ
    • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
  • エミュレーター
    • 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
      近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。

      • 同じCPUで異なるOSを動かす場合は、CPU仮想化。

に分けられる。

C言語で機械語が生成されるまで

C言語のプログラムから、機械語の命令が生成されるまでは、以下のような処理が行われる。
一般的にコンパイラの処理というと、ソースコードから機械語を生成するまでの処理を指すが、C言語ではプリプロセッサ処理を含んだり、コンパイラの処理(ソースコードからオブジェクトファイル生成まで)のほかにリンク処理を含んで使われることも多い。

foo.c C言語のソース
↓     プリプロセッサ処理
foo.c(#行の無いC言語のソース)
↓     コンパイラ
foo.obj(オブジェクトファイル/中間コード)
↓
(+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの)
↓     リンカ(リンケージエディタ)
foo.exe

コンパイラの処理

コンパイラが命令を処理する際には、以下の処理が行われる。

  1. 字句解析(lexical analysys)
    文字列を言語要素(token)に分解
  2. 構文解析(syntax analysys)
    tokenの並び順に意味を反映した構造を生成
  3. 意味解析(semantics analysys)
    命令に合わせた中間コードを生成
  4. 最適化(code optimization)
    中間コードを変形して効率よいプログラムに変換
  5. コード生成(code generation)
    実際の命令コード(オブジェクトファイル)として出力

バイトコードインタプリタとは

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
 ↓       Java コンパイラ
foo.class (中間コード)
 ↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

トークンと正規表現(字句解析)

規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言     「abd|acd」は、abd または acd にマッチする。
グループ化 「a(b|c)d」は、真ん中の c|b をグループ化
量化    パターンの後ろに、繰り返し何回を指定
      ? 直前パターンが0個か1個
       「colou?r」
      * 直前パターンが0個以上繰り返す
       「go*gle」は、ggle,gogle,google
      + 直前パターンが1個以上繰り返す
       「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
      「[0-9]+」012,31415,...数字の列
^     行頭にマッチ
$     行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

構文とバッカス記法

言語の文法を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

  +
 / \
1   *
   / \
  23   456

理解度確認

  • インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
  • 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。

集約関数と副問い合わせ

特殊な条件演算子

WHERE 節の中で使える特殊な条件演算子を紹介する。

... AND ...
   WHERE S.業者番号 <= 100 OR S.業者番号 >= 200 ;
... OR ...
   WHERE S.業者番号 >= 100 AND 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}

演習課題

SQLの実験環境を使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。

さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。

考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。

AVLと2分ヒープ

前回、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分探索木では、1つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。

これらの問題の解決法の1つとして、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 ;
} 

SQLの基本

先週の、関係データベースの導入説明を終えて、実際のSQLの説明。

SQLの命令

SQL で使われる命令は、以下のものに分類される。((参考資料))

  • データ定義言語 – CREATE, DROP, ALTER 等
  • データ操作言語 – INSERT, UPDATE, DELETE, SELECT 等
  • データ制御言語 – GRANT, REVOKE 等 (その他トランザクション制御命令など)

create user

データベースを扱う際の create user 文は、DDL(Data Definition Language)で行う。

CREATE USER ユーザ名
    IDENTIFIED BY "パスワード"

grant

テーブルに対する権限を与える命令。

GRANT システム権限 TO ユーザ名
   データベースシステム全体に関わる権限をユーザに与える。
   (例) GRANT execute ON admin.my_package TO saitoh
GRANT オブジェクト権限 ON オブジェクト名 TO ユーザ名
   作られたテーブルなどのオブジェクトに関する権限を与える。
   (例) GRANT select,update,delete,insert ON admin.my_table TO saitoh
REVOKE オブジェクト権限 ON オブジェクト名 TO ユーザ名
   オブジェクトへの権限を剥奪する。

ただし、後に示す実験環境では、データベースのシステムにSQLiteを用いている。SQLite はネットワーク対応型のデータベースではないため、データベースをアクセスするユーザや権限の概念が存在しない。

create table

実際にテーブルを宣言する命令。構造体の宣言みたいなものと捉えると分かりやすい。

CREATE TABLE テーブル名
   ( 要素名1  型 , 要素名2 型 ... ) ;
   PRIMARY KEY 制約
   1つの属性でのキーの場合、型の後ろに"PRIMARY KEY"をつける、
   複数属性でキーとなる場合は、要素列の最後に PRIMARY KEY(要素名,...) をつける。
   これによりKEYに指定した物は、重複した値を格納できない。

型には、以下の様なものがある。(Oracle)
   CHAR( size)  : 固定長文字列 / NCHAR国際文字
   VARCHAR2( size ) : 可変長文字列 / NVARCHAR2...
   NUMBER(桁) :指定 桁数を扱える数
   BINARY_FLOAT / BINARY_DOUBLE : 浮動小数点(float / double)
   DATE : 日付(年月日時分秒)
   SQLiteでの型
   INTEGER : int型
   REAL : float/double型
   TEXT : 可変長文字列型
   BLOB : 大きいバイナリデータ

DROP TABLE テーブル名
   テーブルを削除する命令

insert,update,delete

指定したテーブルに新しいデータを登録,更新,削除する命令

INSERT INTO テーブル名 ( 要素名,... ) VALUES ( 値,... ) ;
   要素に対応する値をそれぞれ代入する。
UPDATE テーブル名 SET 要素名=値 WHERE 条件
   指定した条件の列の値を更新する。
DELETE FROM テーブル名 WHERE 条件
   指定した条件の列を削除する。

select

データ問い合わせは、select文を用いる、 select文は、(1)必要なカラムを指定する射影、(2)指定条件にあうレコードを指定する選択、 (3)複数のテーブルの直積を処理する結合から構成される。

SELECT 射影 FROM 結合 WHERE 選択
   (例) SELECT S.業者番号 FROM S WHERE S.優良度 > 30 ;

理解確認

  • キー・プライマリキー・外部キーについて説明せよ。
  • 上記説明中の、科目テーブルにふさわしい create table 文を示せ。
  • select文における、射影,結合,選択について説明せよ。

SQLの演習環境の使い方

下記URLにアクセスすると、認証画面が表示されるので、情報処理センターのユーザIDとパスワードで、Login する。

以下のような画面が表示されるので、最初に”データベースリセット”を押すこと。

以降、登録済みの処理を実行する場合は、左上のプルダウンメニューから、処理を選んで”バッチ処理実行”を行う。
画面下に、実行された結果が表示される。

教科書内の基本演習のデータを利用したい場合は、”0_Create_DB” , “1_Insert_Data”を実行する。

自分で処理を実行したい場合には、中段のSQLコマンドの欄に、命令を記載する。”create table”や”insert”といった結果を伴わない命令の場合は、”EXEC”を実行。”select” などの実行結果がある場合は、”QUERY”を実行すること。


SQLの基礎

ここまで述べたようにデータベースでは記録されているデータの読み書きは、SQL で行われ、射影・結合・選択を表す処理で構成されることを示した。SQL の機能を理解するために、同じ処理を C 言語で書いたらどうなるのかを示す。

((( 元のSQL )))
SELECT S.業者番号         -- 必要とされるデータを抽出する射影 --
  FROM S                 -- 複数のテーブルを組合せる結合 --
  WHERE S.優良度 >= 20 ;  -- 対象となるデータを選び出す選択 --

((( SQLをC言語で書いたら )))
// 配列の個数を求める #define 文
#define sizeofarray(ARY) (sizeof(ARY) / sizeof(ARY[0]))
// C言語なら... S のデータを構造体宣言で書いてみる。
struct Table_S {
   char 業者番号[ 6 ] ; // 当然、C言語では要素名を
   char 業者名[ 22 ] ;  // 漢字で宣言はできない。
   int  優良度 ;
   char 所在[ 16 ] ;
} S[] = {
   { "S1" , "ABC社" , 20 , "福井" } ,
   :
} ;

// SELECT...をC言語で書いた場合の命令のイメージ
// 結合
for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
   // 選択
   if ( S[i].優良度 >= 20 )
      // 射影
      printf( "%d¥n" , S[i].業者番号 ) ;
}

Sは、テーブル名であり、文脈上対象テーブルが明らかな場合、フィールド名の前の テーブルは省略可能である。

SELECT 業者番号 FROM S WHERE 優良度 >= 20 ;

WHERE 節で記述できる条件式では、= , <>(not equal) , < , > , <= , >= の比較演算子が使える。
# これ以外の演算機能は、次週にて紹介予定。

直積と結合処理

ここで、SQLの最も便利な機能は、直積による結合処理。複数の表を組み合わせる処理。単純な表形式の関係データベースで、複雑なデータを表現できる基本機能となっている。

SELECT SG.商品番号 , S.所在
  FROM S , SG
  WHERE SG.業者番号 = S.業者番号

上記の様に FROM 節に複数のテーブルを書くと、それぞれのテーブルの直積(要素の全ての組み合わせ)を生成する処理が行われる。この機能が結合となる。しかし、これだけでは意味がないので、通常は外部キーが一致するレコードでのみ処理を行うように、WHERE SG.業者番号 = S.業者番号 のような選択を記載する。最後に、結果として欲しいデータを抽出する射影を記載する。

SELECTの結合処理と処理内容

selectでの選択,結合,射影の処理(select 射影 from 結合 where 選択)を理解するために、同じ処理をC言語で書いたらどうなるかを示す。

// C言語なら
struct Table_S {
   char 業者番号[ 6 ] ;
   char 業者名[ 22 ] ;
   int  優良度 ;
   char 所在[ 16 ] ;
} S[] = {
   { "S1" , "ABC社" , 20 , "福井" } ,
   :
} ;
struct Table_SG {
   char 業者番号[ 6 ] ;
   char 商品番号[ 6 ] ;
   int  在庫量 ;
} = SG[] {
   { "S1" , "G1" , 300 } ,
   :
} ;

// FROM S
for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
   // FROM SG
   for( int j = 0 ; j < sizeofarray( SG ) ; j++ ) {
      // WHERE S.業者番号 = SG.業者番号
      if ( strcmp( S[i].業者番号 , SG[j].業者番号 ) == 0 ) {
         // SELECT SG.商品番号 , S.所在
         printf( "%s %s¥n" , SG[j].商品番号 , S[i].所在 ) ;
      }
   }
}

(1) i,jの2重forループが、FROM節の結合に相当し、(2) ループ内のif文がWHERE節の選択に相当し、(3) printfの表示内容が射影に相当している。

射影の処理では、データの一部分を抽出することから、1件の抽出レコードが同じになることもある。この際の重複したデータを1つにまとめる場合には、DISTINCT を指定する。

SELECT DISTINCT SG.商品番号, S.所在
   FROM S, SG
   WHERE SG.業者番号 = S.業者番号 ;

上記のプログラムでは、データの検索は単純 for ループで記載しているが、内部で HASH などが使われていると、昇順に処理が行われない場合も多い。出力されるデータの順序を指定したい場合には、ORDER BY … ASC (or DESC) を用いる

SELECT SG.商品番号, S.所在
   FROM S, SG
   WHERE SG.業者番号 = S.業者番号
   ORDER BY S.所在 ASC ;        -- ASC:昇順 , DESC:降順 --

表型のデータと串刺し

FROM に記載する直積のための結合では、2つ以上のテーブルを指定しても良い。

SELECT S.業者名, G.商品名, SG.在庫量
   FROM S, G, SG
   WHERE  S.業者番号 = SG.業者番号  -- 外部キー業者番号の対応付け --
     AND  SG.商品番号 = G.商品番号  -- 外部キー商品番号の対応付け --

// 上記の処理をC言語で書いたら

struct Table_G {
   char 商品番号[ 6 ] ;
   char 商品名[ 22 ] ;
   char 色[ 4 ] ;
   int  価格 ;
   char 所在[ 12 ] ;
} = G[] = {
   { "G1" , "赤鉛筆" , "青" , 120 , "福井" } ,
   :
} ;

// [結合] S,G,SGのすべての組み合わせ
// FROM S -- 結合
for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
   // FROM G -- 結合
   for( int j = 0 ; j < sizeofarray( G ) ; j++ ) {
      // FROM SG -- 結合
      for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) {

         // [選択] 条件でレコードを選び出す
         //   WHERE S.業者番号 = SG.業者番号
         //     AND SG.商品番号 = G.商品番号
         if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0
           && strcmp( SG[k].商品番号 , G[j].商品番号 ) == 0 ) {
            // [射影] 使用するフィールドを出力
            printf( "%s %s %d\n" ,
                    S[i].業者名 , G[j].商品名 , SG[k].在庫量 ) ;
         }
      }
   }
}

ここで結合と選択で実行している内容は、外部キーである業者番号を S から探す、商品番号を G から探している。この、外部キー対応しているものを探すという視点で、上記 C 言語のプログラムを書き換えると、以下のように表せる。

// FROM SG
for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) {
   // 外部キー SG.業者番号に対応するものを S から探す
   for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
      if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 ) {
         // 外部キー SG.商品番号に対応するものを G から探す
         for( int j = 0 ; j < sizeofarray( G ) ; j++ ) {
            if ( strcmp(SG[k].商品番号,G[j].商品番号) == 0 ) {
               printf( "%s %s %d\n" ,
                       S[i].業者名,G[j].商品名,SG[k].在庫量 ) ;
            }
         }
      }
   }
}

このような、複数の表の実体と関係を対応付けた検索を、データベースの専門の人は「データを串刺しにする」という言い方をすることも多い。

また、SQL では、このようなイメージの繰り返し処理を、数行で分かりやすく記述できている。このプログラム例では、キーに対応するものを単純 for ループで説明しているが、SQL ではプライマリキーなら、B木やハッシュなどを用いた効率の良い検索が自動的に行われる。このため、SQLを扱う応用プログラマは、SQLの結合の処理方法は通常はあまり考えなくて良い。