ホーム » 2022 (ページ 2)

年別アーカイブ: 2022

2024年4月
 123456
78910111213
14151617181920
21222324252627
282930  

検索・リンク

データべースの設計と正規形

データベースの設計において、重要な正規形についての説明

正規形

データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。

第一正規形は、すべての要素が原子値である条件を満たせばいい。 要素の中が複数の項目であったり表形式のデータがあると、 表構造のリレーショナルデータベースにはできない。


キーの説明超キー(スーパーキー)とは、データベースで1つのデータを 選び出すために必要なデータ項目であり、複数の項目で1データを指定 できる場合もある。

候補キーとは、必要最小限の項目となっているものを指す。 1項目が抜けても選別できなくなるようであれば、候補キーとは言わない。 主キーとは、候補キーのなかで管理の都合上便利なもの。

データ項目の値が決まると、他のデータ項目が自動的に決まるものは、 従属関係があるという。

第1正規化 第2正規化

第二正規形は、部分従属がなく、すべての非キーデータ項目が、候補キーに 完全従属する場合をいう。

  • 完全従属とは、候補キーを構成する全てのデータ項目に、非キーデータ項目が従属していること。
  • 部分従属とは、候補キーを構成するデータ項目の一部のデータ項目に、非キー項目が従属していること。

この例において、単価は商品が決まれば自動的に求まる情報。 (単価が日々変化することはないという条件で…) これは、部分従属となる。他に部分従属となっている属性は何か?

  • 推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。

第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。

第3正規化

上記の例では、単価と個数が決まれば、金額が求まる推移従属の関係が含まれている。

おまけ:BC正規形,第4,5正規形

この他にも、 さらに非キーからキーに関数従属性がある場合にそれを取り除く、 ボイスコッド正規形(BC正規化)。 「対称性のある多値従属性(キーを決めると複数データが該当)」を分解して得られる第4正規形や、 「元になるテーブルの結合従属性を維持して分解することにより得られる第5正規形などがある。

トップダウン設計・ボトムアップ設計

データベースの設計にあたって、実際の設計手順の説明を行う。

トップダウン設計では、対象業務を記述し、その中から名詞となっている実体を抽出する。 さらに動詞や形容詞のように記載されている関連を抽出する。 抽出した実体・関連では、あいまいであったり冗長であったりするので、整理したうえで、 その実体・関連をER図に表す。

ボトムアップ設計では、対象業務で実際に使われている入力帳票や結果の出力などを 見ながら、第1正規形を満たすように表を作っていく作業からおこなう。

トップダウン設計やボトムアップ設計で、 ER図や第一正規形を満たすような表が出来上がったら、 その属性の中で従属性を確認しながら、第2正規形・第3正規形へと整理していく。

2分木による構文木とデータベースとB木

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 ) ) ;
}

理解度確認

  • 上記プログラム中の(A)~(F)の型を答えよ。

2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。

B木の構造

2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータ d0, … , d2N-1 と、2N+1本のポインタ p0, … , p2N から構成される。pの先には、di-1< x < di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2Nを保存する。下図は位数2のB木の例を示す。

B木からデータの検索

データを探す場合は、ノード内のデータ di の中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O( log ) となる。

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木の部分と、赤で示す順次処理を行うためのシーケンスセットの部分から構成される。

トランスポート層・TCPとUDP

サブネット同士をつなぐプロトコルとして IPプロトコル を紹介したが、MACアドレスとIPアドレスの対応付けを行う ARP の説明や、パケットのルーティングを司る RIP の説明が不十分だったので、前回資料を補足説明を行う。

  • DHCP(IPアドレスの貸し出し)
  • ARP(IPとMACアドレスの対応付け)
  • RIP(ルータの経路情報のやりとり)
  • IPv4とプライベートアドレス
  • NAT と P2P通信
  • IPv6アドレス.

データ通信ではノイズなどの影響で通信に失敗することがある。これらを補うためのTCPがある。

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番号ACK番号という情報がついており、3wayハンドシェーク時には、相手のSEQ番号に1を加えたACK番号をつけてパケットを返送する。これにより、どの通信に対する返事か判るようにしている。さらに、実際のデータを送信する際には、受け取ったデータ長をSEQ番号に加えた値を、ACK番号にして受信に成功したことを相手に伝える。これにより、小分けにされたパケットで次に何を送れば良いのか判別できる。

通信で、パケット分割して送って、その一つ毎の返答を待つと、通信の待ち時間が増えてしまう。このため、相手が受け取り可能であれば、一度に前回の2倍のパケットを返信を待たずに送る。(ウィンドウサイズの拡大)

チェックサムとタイムアウト

通信では、送る途中でデータにノイズが混入したり、パケットが消失することがある。このため、パケットにはパケットのチェックサム(バイトデータを加算した値)を付けて送り、受信時に比較してノイズ混入を確認する。こういった際には、パケットが正しく届かない。パケットが消失したりして、通信相手からの返送が届かないで一定の待ち時間が経過することをタイムアウトと呼ぶ。この時、返信パケットにはデータのSEQ番号とACK番号の情報があるため、受け取りに失敗したパケットが判別できるので、送り側は失敗したパケットを再送する。

受け取り側は、同じくSEQ番号やACK番号を元にパケットの順番を正しく並べ戻すことができる。

TCP FINパケット

通信を切断する場合には、相互に切断して良いか確認する4回の通信で終了する。

UDP

TCPによる通信は、相手側からの受け取った返事を待ちながら通信を行う。このため、通信にかかる時間を要する。また、複数の利用者に一斉にデータをばらまくブロードキャスト通信では、個別のパケット欠落を修復しようとすると、処理が複雑になる。

これらの対応策として、UDP(User Datagram Protocol)がある。これは、TCP通信でのパケット分割や再送処理を行わない極めて単純な送信方法である。このため、相手側に正しくデータが送られる保証はない。確実に相手に送る必要があれば、確認や再送は上位プロトコルの責任となる。

UDP通信は、動画・音声配信などのリアルタイム性のある通信で、正しく通信ができず一時的に動画が止まるなり音声が止まっても、問題が少ないような場合に有効となる。

ICMP/ping

IPプロトコルのプロトコルの1つとして ICMP (Internet Control Message Protocol) がある。このプロトコルは、ネットワーク機器(ノード)の間で、通信の確認をするためのもので、ping コマンドや traceroute コマンドで使われる。

基本的に、パケットを相手コンピュータに送り、返事が返ってくる。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とかインターネット・プロトコル・スイート と呼ぶ。

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

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

学生(実体)

ID name grade
20101 aoyama 1
20002 suzuki 2
30203 yamada 3
受講(関係)

ID SubID
20101 1001
20101 1002
20002 1001
20002 1003
30203 1004

30203を消してもmedia
の科目のデータは残る。

科目(実体)

SubID Subject teacher
1001 database saitoh
1002 software murata
1003 compiler nishi
1004 media ogoshi
1005 internet foobar

saitoh→takakuに変更したら
複数のレコードを要修正。

internetを追加しても問題なし。

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

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

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

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

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

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

演算子と言語処理系

前回追加で説明した逆ポーランド記法などの説明を再掲したうえで、構文解析といった言語処理系の話を解説する。

逆ポーランド記法

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

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

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

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

に分けられる。

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

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

foo.c C言語のソース
↓     プリプロセッサ処理                cpp
foo.c(#行の無いC言語のソース)
↓     コンパイラ                       gcc
foo.obj(オブジェクトファイル/中間コード)  unix系では foo.o
↓
(+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの)
↓     リンカ(リンケージエディタ)          ld
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記法問題にて理解度を確認せよ。
  • ソースプログラムがコンパイラにより機械語が生成されるまでの処理について説明せよ。

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以上のデータが出力される。

業者番号 商品番号 在庫量
S1 G1 300
S1 G2 200
S1 G3 400
S1 G4 200
S1 G5 100
S1 G6 100
S2 G1 300
S2 G2 400
S3 G2 200
S4 G2 200
S4 G4 300
S4 G5 400

※業者番号順
 ⇒
業者番号 商品番号 在庫量 SUM(SG.在庫量)
S1 G1 300 600
(≧500)
S2 G1 300
S2 G2 400 1000
(≧500)
S3 G2 200
S1 G2 200
S4 G2 200
S1 G3 400 400
S1 G4 200 500
(≧500)
S4 G4 300
S1 G5 100 500
(≧500)
S4 G5 400
S1 G6 100 100

※商品番号でグループ化
 ⇒
商品番号 SUM(SG.在庫量)
G1 600
G2 1000
G4 500
G5 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.商品番号 ;

ビューテーブルに対する 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インジェクションで発生した有名な事件では、以下のようなものがある。

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

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

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

コロナ感染数推移

HPに記載されているPDFの感染数を週毎に合計したものの推移。最近増えたな…と思い、上半期について手作業で集計した非公式データなので間違いあるかも。でも、こうやってみると夏の方がピークだったんだな。

AVLと意思決定木と演算子

前回、2分探索木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。

2分探索木へのデータ追加と不均一な木の成長

先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。

しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか?

  • 86, 53, 11 – 降順のデータ
  • 12, 24, 42 – 昇順のデータ

この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。

AVL木

このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで検索回数を改善できる。例えば、以下のような木では、赤の左側に偏っている。(赤の左の枝は深さ=3段、青の枝は深さ=1段)

このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、2分探索木の要件を満たしたまま、木の段数を均一に近づけることができる。この例では、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分探索木に関連したデータ構造の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木を紹介する。

意思決定木

意思決定木の説明ということで、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 を逆ポーランド記法で表現せよ。

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

UMLについて(ソフトウェア工学)

UML(Unified Modeling Language)記法が生まれるまで

巨大なプロジェクトでプログラムを作る場合、対象となるシステムを概念として表現する場合、オブジェクト指向分析(OOA: Object Oriented Analysis)オブジェクト指向設計(OOD: Object Oriented Design)とよばれるソフトウェア開発方法が重要となる。(総称して OOAD – Object Oriented Analysis and Design)

これらの開発方法をとる場合、(1)自分自身で考えを整理したり(2)グループで設計を検討したり(3)ユーザに仕様を説明したりといった作業が行われる。この時に、自分自身あるいはチームメンバーあるいはクライアントに直感的に図を用いて説明する。この時の図の書き方を標準化したものが UML であり、(a)処理の流れを説明するための振る舞い図(以前であればフローチャートやPAD)と、(b)データ構造を説明するための構造図を用いる。

UMLは、ランボーによるOMT(Object Modeling Technique どちらかというとOOA中心)と、 ヤコブソンによるオブジェクト指向ソフトウェア工学(OOSE)を元に1990年頃に 発生し、ブーチBooch法(どちらかというとOOD中心)の考えをまとめ、 UML(Unified Modeling Language)としてでてきた。

UMLでよく使われる図を列記すると、以下の物が挙げられる。

  • 構造図
    • クラス図
    • コンポーネント図
    • 配置図
    • オブジェクト図
    • パッケージ図
  • 振る舞い図
    • アクティビティ図
    • ユースケース図
    • ステートチャート図(状態遷移図)
    • 相互作用図
    • シーケンス図
    • コミュニケーション図(コラボレーション図)

UMLを正しく使うことができるようになれば、UMLで仕様書を書けばそれがそのままプログラムになることが理想的な姿かもしれない。ソフトウェア開発やソフトウェアの保守にソフトウェアツールを利用することは、CASE(Computer Aided Software Engineering)と呼ばれ、そのようなツールをCASEツールと呼ぶ。地元福井の永和システムマネジメントでは、astar* というCASEツールを開発している。


UMLの構造図の書き方の説明。 詳しくは、参考ページのUML入門などが、分かりやすい。

クラス図

クラス図は、構造図の中の基本的な図で、 枠の中に、上段:クラス名、中段:属性(要素)、下段:メソッド(関数)を記載する。 属性やメソッドの可視性を示す場合は、”-“:private、”+”:public、”#”:protected 可視性に応じて、”+-#”などを記載する。

関連

クラスが他のクラスと関係がある場合には、その関係の意味に応じて、直線や矢印で結ぶ。
(a)関連(association):単純に関係がある場合、
(b)集約(aggregation):部品として持つが、弱い結びつき。関係先が消滅しても別に存在可能。(has-a)
(c)コンポジション(composition):部品として持つが強い結びつき。関係先と一緒に消滅。(has-a)
(d)依存(dependency):依存関係にあるだけ
(e)派生(generalization):派生・継承した関係(is-a)
(f)実現(realization): Javaでのinterfaceによる多重継承

上図の例では、乗り物クラスVehicleから自動車Carが派生し(CarからVehicleへの三角矢印―▷)、 自動車は、エンジン(Engine)を部品として持つ(EngineからCarへのひし形矢印―◆)。エンジンは車体と一緒に廃棄なら、コンポジション(C++であれば部品の実体を持つ)で実装する。

自動車は、同じく車輪(Wheel)を4つ持つが、自動車を廃棄してもタイヤは別に使うかもしれないので、集約(部品への参照を持つ)で実装する(WheelからCarへのひし形矢印―◇)。 集約で実装する場合は、C++などであれば、ポインタで部品を持ち、部品の廃棄(delete)は、別に行うことになる。

Javaなどのプログラム言語では、オブジェクトはデータの実体へのポインタで扱われるため、コンポジションと集約を区別して表現することは少ない。

is-a 、has-a の関係

前の課題でのカモノハシクラスで、羽や足の情報をどう扱うべきかで、悩んだ場合と同じように、 クラスの設計を行う場合には、部品として持つのか、継承として機能を持つのか悩む場合がある。 この場合には、“is-a”の関係“has-a”の関係で考えると、部品なのか継承なのか判断しやすい。

たとえば、上の乗り物(Vehicle)クラスと、車(Car)のクラスは、”Car is-a Vehicle” といえるので、is-a の関係。 “Car is-a Engine”と表現すると、おかしいことが判る。 車(Car)とエンジン(Engine)のクラスは、”Car has-a Engine”といえるので、has-a の関係となる。 このことから、CarはVehicleからの派生であり、Carの属性としてEngineを部品として持つ設計となる。

オブジェクト図

クラス図だけで表現すると、複雑なクラス関係では、イメージが分かりづらい場合がでてくる。 この場合、具体的な値を図に書き込んだオブジェクトで表現すると、説明がしやすい場合がある。 このように具体的な値で記述するクラス図は、オブジェクト図と言う。 書き方としては、クラス名の下に下線を引き、中段の属性の所には具体的な値を書き込んで示す。

パッケージ図

パッケージ図は、クラス図をパッケージ毎に分類して記載する図。 パッケージのグループを、フォルダのような図で記載する。


IT専科から引用

コンポーネント図とコンポジット構造図

コンポジット構造図は、クラスやコンポーネントの内部構造を示すもので、コンポーネント図は、複数のクラスで構成される処理に、 インタフェースを用意し、あたかも1つのクラスのように扱ったもの。 接続するインタフェースを飴玉と飴玉を受けるクチのイメージで、提供側を◯───で表し、要求側を⊃──で表す。


IT専科から引用

配置図

配置図は、システムのハードウェア構成や通信経路などを表現するための図。 ハードウェアは直方体の絵で表現し、 デバイスの説明は、”≪device≫”などを示し、実行環境には、”≪executionEnvironment≫” などの目印で表現する。


IT専科から引用

振る舞い図

参考資料をもとに振る舞い図の説明を行う。

ユースケース図

1507131131_211x192.png

ユーザなど外部からの要求に対する、システムの振る舞いを表現するための活用事例や機能を表す図がユースケース図。 システムを構築する際に、最初に記述するUMLであり、システムに対する処理要件の全体像や機能を理解するために記述する。 ユーザや外部のシステムは、アクターとよび人形の絵で示す。楕円でシステムに対する具体的な処理をユースケースとして楕円で記述する。 関連する複数のユースケースをまとめて、サブジェクトとして示す場合もある。

アクティビティ図

処理順序を記述するための図にはフローチャートがあるが、上から下に処理順序を記述するため、縦長の図になりやすい。また、四角枠の中に複雑なことを書けないので、UMLではアクティビティ図を用いる。

初期状態●から、終了状態◉までの手順を示すためのものがアクティビティ図。 フローチャートに無い表現として、複数の処理を並行処理する場合には、フォークノードで複数の処理を併記し、最終的に1つの処理になる部分をマージノードで示す。 通常の処理は、角丸の長方形で示し、条件分岐はひし形で示す。

ステートチャート図(状態遷移図)

ステートチャート図は、処理内部での状態遷移を示すための図。 1つの状態を長丸長方形で示し、初期状態●から終了状態◉までを結ぶ。 1つの状態から、なんらかの状態で他の状態に遷移する場合は、分岐条件となる契機(タイミング)とその条件、およびその効果(出力)を「契機[条件]/効果」で矢印に併記する。 複数の状態をグループ化して表す場合もある。

シーケンス図

複数のオブジェクトが相互にやり取りをしながら処理が進むようなもののタイミングを記述するためのものがシーケンス図。 上部の長方形にクラス/オブジェクトを示し、その下に縦軸にて時系列の処理の流れの線(Life Line)を描く。 オブジェクトがアクティブな状態は、縦長の長方形で示し、そのLife Line間を、やり取り(メッセージ)の線で相互に結ぶ。 メッセージは、相手側からの返答を待つような同期メッセージは、黒塗り三角矢印で示す。 返答を待たない非同期メッセージは矢印で示し、返答は破線で示す。

コミュニケーション図

クラスやオブジェクトの間の処理とその応答(相互作用)と関連の両方を表現する図。

応答を待つ同期メッセージは -▶︎、非同期メッセージは→で表す。複数のオブジェクト間のやりとりの相互作用を表現する。

タイミング図

タイミング図は、クラスやオブジェクトの時間と共に状態がどのように遷移するのかを表現する図。

状態変化の発生するタイミングや、時間的な遅れや時間的な制約を図で明記するために使われる。

オブジェクト指向プログラミング(ソフトウェア工学)

オブジェクト指向プログラミングは、最近の多くのプログラム言語で取り入れられている機能。

今回は、構造化プログラミングオブジェクト指向(クラス,メソッド)、コンストラクタ派生継承仮想関数の概念を紹介する。

オブジェクト指向プログラミングの歴史

最初のプログラム言語のFortran(科学技術計算向け言語)の頃は、処理を記述するだけだったけど、 COBOL(商用計算向け言語)ができた頃には、データをひとまとめで扱う「構造体」(C言語ならstruct {…}の考えができた。(データの構造化)

// C言語の構造体 // データの構造化
struct Person { // 1人分のデータ構造をPersonとする
   char name[ 20 ] ;             // 名前
   int  b_year, b_month, b_day ; // 誕生日
} ;

一方、初期のFortranでは、プログラムの処理順序は、if 文と goto 文で組み合わせて書くこと多く、処理がわかりにくかった。その後のALGOLの頃には、処理をブロック化して扱うスタイル(C言語なら{ 文 … }の複文で 記述する方法ができてきた。(処理の構造化)

      // ブロックの考えがない時代の雰囲気をC言語で表すと
      int i = 0 ;
LOOP: if ( i >= 10 ) goto EXIT ;
         if ( i % 2 != 0 ) goto NEXT ;
            printf( "%d " , i ) ;
NEXT:    i++ ;
      goto LOOP ;   // 処理の範囲を字下げ(インデント)で強調
EXIT:
--------------------------------------------------- 
      // C 言語で書けば
      int i ;
      for( i = 0 ; i < 10 ; i++ ) { // 処理の構造化
         if ( i % 2 == 0 ) {
            printf( "%d¥n" , i ) ;
         }
      }
---------------------------------------------------
      ! 構造化文法のFORTRANで書くと
      integer i
      do i = 0 , 9
        if ( mod( i , 2 ) == 0 ) then
          print * , i
        end if
      end do

このデータの構造化・処理の構造化により、プログラムの分かりやすさは向上し、このデータと処理をブロック化した書き方は「構造化プログラミング(Structured Programming)」 と呼ばれる。

この後、様々なプログラム言語が開発され、C言語などもできてきた。 一方で、シミュレーションのプログラム開発(例simula)では、 シミュレーション対象(object)に対して、命令するスタイルの書き方が生まれ、 データに対して命令するという点で、擬人法のようなイメージで直感的にも分かりやすかった。 これがオブジェクト指向プログラミング(Object Oriented Programming)の始まりとなる。略記するときは OOP などと書くことが多い。

この考え方を導入した言語の1つが Smalltalk であり、この環境では、プログラムのエディタも Smalltalk で記述したりして、オブジェクト指向がGUIのプログラムと親和性が良いことから、この考え方は多くのプログラム言語へと取り入れられていく。

C言語にこのオブジェクト指向を取り入れ C++ が開発される。さらに、この文法をベースとした Java などが開発されている。最近の新しい言語では、どれもオブジェクト指向の考えが使われている。

クラスの導入(構造体でオブジェクト指向もどき)

例えば、名前と年齢の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者データ利用者で分けて 仕事ができる。

// この部分はデータ構造の設計者が書く
// データ構造を記述
struct Person {
   char name[10] ;
   int  age ;
} ;
// データに対する処理を記述
void setPerson( struct Person* p , char s[] , int a ) {
   // ポインタの参照で表記
   strcpy( p->name , s ) ;
   p->age = a ;
}
void printPerson( struct Person* p ) {
   printf( "%s %d¥n" , p->name , p->age ) ;
}
// -------------------------------------------
// この部分は、データ利用者が書く
int main() {
   // Personの中身を知らなくてもいいから配列を定義(データ隠蔽)
   struct Person saitoh ;
   setPerson( &saitoh , "saitoh" , 55 ) ;

   struct Person table[ 10 ] ; // 初期化は記述を省略
   for( int i = 0 ; i < 10 ; i++ ) {
      // 出力する...という雰囲気で書ける(手続き隠蔽)
      printPerson( &table[i] ) ;
   }
   return 0 ;
}

このプログラムの書き方では、mainの中を読むだけもで、 データ初期化とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、setPerson()や、printPerson()という関数の中身についても、 初期化・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。

C++のクラスで表現

上記のプログラムをそのままC++に書き直すと以下のようになる。特徴として 構造体を進化させた class 宣言の中に、データ構造とデータ構造を使う関数をまとめて記述する。

#include <stdio.h>
#include <string.h>

// この部分はクラス設計者が書く
class Person {
private: // ■ クラス外からアクセスできない部分
   // データ構造を記述
   char name[10] ; // メンバーの宣言
   int  age ;
public: // ■ クラス外から使える部分
   // データに対する処理を記述
   void set( char s[] , int a ) { // ■ メソッドの宣言
      // pのように対象のオブジェクトを明記する必要はない。
      strcpy( name , s ) ;
      age = a ;
   }
   void print() {
      printf( "%s %d¥n" , name , age ) ;
   }
} ; // ← 注意ここのセミコロンを書き忘れないこと。

// この部分はクラス利用者が書く
int main() {
   Person saitoh ;
   saitoh.set( "saitoh" , 55 ) ;
   saitoh.print() ;

   // 文法エラーの例
   printf( "%d¥n" , saitoh.age ) ; // ■ age は private なので参照できない。
   return 0 ;
}

用語の解説:C++のプログラムでは、データ構造データの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)とかインスタンス(instance)と呼ぶ。

コンストラクタ

データ構造を扱ううえで、データの初期化や廃棄処理は重要となるが、書き忘れをすることも多い。そこで、C++ ではコンストラクタで初期化を簡単に書ける。

// コンストラクタを使って書く
class Person {
private:
   char name[10] ; // メンバーの宣言
   int  age ;
public:
   Person( char s[] , int a ) { // ■ コンストラクタ
      strcpy( name , s ) ;
      age = a ;
   }
   void print() {
      printf( "%s %d¥n" , name , age ) ;
   }
} ;
int main() {
   Person saitoh( "saitoh" , 57 ) ;  // ■ コンストラクタで宣言&初期化
   return 0 ;
}

派生と継承

オブジェクト指向では、元となったデータ構造(class ? struct ?)を拡張した時の記述が便利。例えば、前述の Person に住所も覚えたかったとしたら どう書くだろうか?

// オブジェクト指向を使わずに記述
// Personを要素として持つ PersonAddr を定義
struct PersonAddr {
   struct Person person ;
   char          addr[ 20 ] ;
} ;
// PersonAddr のメソッド
void setPersonAddr( struct PersonAddr* p , char nm[] , int ag , char ad[] ) {
   setPerson( p->person , nm , ag ) ;
   strcpy( p->addr , ad ) ;
}
void printPersonAddr( struct PersonAddr* p ) {
   printPerson( p->person ) ;
   printf( "%s" , p->addr ) ;
   return 0 ;
}

オブジェクト指向では、こういった場合には、Person を拡張した PersonAddr を定義する。この時、元となるクラス(Person)は基底クラス(あるいは親クラス)拡張したクラス(PersonAddr)は派生クラス(あるいは子クラス)と呼ぶ。

// C++ 流に記述
class PersonAddr : public Person { // ■ Personから派生したPersonAddr
private:        // ~~~~~~~~~~~~~派生
   char  addr[ 20 ] ;
public:
   PersonAddr( char nm[] , int ag , char ad[] )
     : Person( nm , ag ) {         // ■ 基底クラスのコンストラクタで初期化
       strcpy( addr , ad ) ;       // ■ 追加部分の初期化
   }
} ;
int main() {
   Person     tohru( "tohru" , 57 ) ;
   PersonAddr saitoh( "saitoh" , 45 , "Fukui" ) ;
   tohru.print() ;   // tohru 57
   saitoh.print() ;  // saitoh 45 ■ 継承を使って表示
   return 0 ;
}

この例では、saitoh は PersonAddr であり、それを表示するための PersonAddr::print() は定義されていないが、saitoh.print() を実行すると、基底クラスのメソッド Person::print() を使ってくれる。このように基底クラスのメソッドを流用してくれる機能継承と呼ぶ。

仮想関数

前述の継承のプログラムでは、PersonAddr 専用の print() を定義してもいい。また基底クラスと派生クラスが混在する配列を作ることもできる。しかし、以下のようなプログラムでは問題が発生する。

class PersonAddr : public Person {
private:
   char  addr[ 20 ] ;
public:
   PersonAddr( char nm[] , int ag , char ad[] )
     : Person( nm , ag ) {
       strcpy( addr , ad ) ;
   }
   void print() {  // ■ PersonAddr 専用の print() を宣言してもいい
      Person::print() ;  // 基底クラス Person の print() を使う
      printf( "%s" , addr ) ;
   }
} ;
int main() {
   Person     tohru( "tohru" , 57 ) ;
   PersonAddr saitoh( "saitoh" , 45 , "Fukui" ) ;

   Person*    family[] = {  // tohru と saitoh のポインタ配列
      &tohru , &saitoh      // &saitoh は Person* に降格されている
   } ;
   tohru.print() ;   // tohru 57
   saitoh.print() ;  // saitoh 45 Fukui
   for( int i = 0 ; i < 2 ; i++ )  // tohru 57
      family[ i ]->print() ;       // ■ "saitoh 45"としか表示してくれない

   return 0 ;
}

family[] のデータを全部表示したいのなら、”tohru 57, saitoh 45 Fukui” と表示されてほしい。
こういった場合に、データのclassに応じて適切なメソッドを呼び出すメカニズムとして仮想関数がある。

class Person {
private:
   char name[ 20 ] ;
   int  age ;
public:
   Person( char nm[] , int ag ) {
      strcpy( name , nm ) ;
      age = ag ;
   }
   virtual void print() {  // ■ ここに virtual が追加された|仮想関数
      printf( "%s %d" , name , age ) ;
   }
} ;
class PersonAddr : public Person {
private:
   char  addr[ 20 ] ;
public:
   PersonAddr( char nm[] , int ag , char ad[] )
     : Person( nm , ag ) {
       strcpy( addr , ad ) ;
   }
   virtual void print() { // ■ ここに virtual が追加された|仮想関数
      Person::print() ;
      printf( "%s" , addr ) ;
   }
} ;
int main() {
   Person     tohru( "tohru" , 57 ) ;
   PersonAddr saitoh( "saitoh" , 45 , "Fukui" ) ;

   Person*    family[] = {  // tohru と saitoh のポインタ配列
      &tohru , &saitoh
   } ;
   for( int i = 0 ; i < 2 ; i++ )  // tohru 57
      family[ i ]->print() ;       // ■ saitoh 45 Fukui と表示
                                   // print は 仮想関数がそれぞれ定義してあるので
                                   // tohru は、"tohru 57"と表示されるし
   return 0 ;                      // saitoh は、"saitoh 45 Fukui"と表示される。
}

このプログラムでは、Person::print() と PersonAddr::print() がそれぞれ仮想関数で定義されているので、tohru, saitoh の各インスタンスには、型情報が埋め込まれている。このため family[0]->print() では “tohru 57” が表示されるし、family[1]->print() では “saitoh 45 Fukui” が表示される。

多態性・ポリモーフィズム

このように、派生クラスと仮想関数使ってプログラムを書くと、その派生クラスに応じた処理を呼び出すことができる。このように共通の基底クラスから様々な派生クラスを作りながらプログラムを書き、その派生クラス毎にそのデータに応じた処理を実行させることができる。インスタンスがデータ種別に応じた動きをすることは多態性(ポリモーフィズム)と呼ばれる。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー