ホーム » スタッフ » 斉藤徹

斉藤徹」カテゴリーアーカイブ

2019年11月
« 10月    
 12
3456789
10111213141516
17181920212223
24252627282930

最近の投稿(電子情報)

アーカイブ

カテゴリー

意思決定木と構文解析

前回までの授業で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 ) ;
      scant( "%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:通訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
  • トランスレーター
    • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
  • バイトコードインタプリタ
    • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う

に分けられる。

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

  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記法問題にて理解度を確認せよ。

Visual Studio Code で印刷

実験や授業課題のレポート提出で、プログラムを印刷したものを提出してくれるけど、行を移動しながら何度もスクリーンキャプチャで保存した画像ファイルをWordに貼り付けて提出している人が多い。

いままでなら、「秀丸エディタで印刷してよ…」とか言ってたけど、最近は Visual Studio Code を利用しているみたいで、「プログラムの印刷の仕方がわからない」という人が多いようだ。

実際、Visual Studio Code はたまにしか使わないけど、確かに基本機能の中には印刷機能がないな….

今時、プログラムリストなんて紙媒体で印刷しないもんなんだろうけど、プログラム課題のレポートなら、コードは証拠だからな。

Visual Studio Code の PrintCode

こういう場合は、Visual Studio Code の拡張機能の PrintCode をインストールすればいい。

印刷する時は、F1 キーを押して、拡張コマンドの入力で printcode と打てば印刷される。

ただし、PrintCode は JavaScript を使って HTML を生成し印刷を行うため、Windowsでデフォルトブラウザが Internet Explorer の場合は動かない。このためデフォルトブラウザの変更により Chrome などを使う様に変更しておく必要あり。

Sublime Text なら Print to HTML

同じく、エディタが Sublime Text を使っているのなら、これも印刷機能が付いていないので、”Print to HTML”パッケージをインストールし、あとは、Shift+Alt+P で HTML 用に出力できるのでブラウザ側で印刷を行う。

コンパイラの技術と関数電卓プログラム(2)

前半では、1文字の数字と簡単な演算子で表現される計算式を再帰下降パーサで計算する処理で、 演習を行った。

後半は、さらに実際のコンパイラに近いものとして、 C言語で広く使われている、字句解析ツール(lexical analyzer : lex or flex)、 構文解析ツール(parser : yacc or bison) を使って、 さらに現実的な関数電卓プログラムを作ってみる。

lex or flex による字句解析

lexは、字句解析のプログラムを自動生成するツール。 “%%”行の内側に、正規表現によるルールとその処理(アクション)を書き並べる。 また、“%{ … %}”の内側に、その処理に必要なC言語のソースを書き、 lex で処理を行うと、lex.yy.c というC言語のソースを出力する。

lex.yy.c の中には、yylex() という関数が自動的に作られ、構文解析ツールから呼び出される。

# flex は、lex の改良版。

(( mycalc.l ))
%{
#include <stdio.h>
// yaccが出力するヘッダファイル
#include "y.tab.h"

int yywrap( void )
{
   // 1: スキャナ終了
   // 0: yyin を切り替えて継続
   return 1 ;
}
%}
%%
"+"  return ADD ;
"-"  return SUB ;
"*"  return MUL ;
"/"  return DIV ;
"\n" return CR  ;
[0-9][0-9]* {
   // 入力はyytextに格納されている。
   int temp ;
   sscanf( yytext , "%d" , &temp ) ;
   yylval.int_value = temp ;
   // 返り値は、字句(トークン)の種別を表す定数
   return INT_LITERAL;
}
%%

このプログラムを、lex で処理させると、“+” 記号に ADD という定数記号を割り振るとか、数字列” [0-9][0-9]* “をみつけると、文字列から数値を生成(sscanf)して、その場合の記号に INT_LITERAL という定数記号を割り振る…といった処理のプログラムを生成してくれる。(INT_LITERALは構文解析側で定義する定数)

yacc or bison

yacc ( Yet Another Compiler Compiler ) もしくはその改良版の bison は、構文解析のプログラムを自動生成してくれるツールである。構文をBNF記法で記載すると、字句解析ツール(lex等)を呼び出しながら構文に合わせたトークンの出現に応じた状態遷移のための「遷移テーブル」を自動生成し、 その遷移テーブルを用いた処理のプログラムをC言語で出力してくれる。

字句解析プログラムは、様々なトークンとデータを返す。このデータには様々な場合考えられるので、 そのトークンに合わせたデータの型を “%union” の中に記載(C言語の共用体参照)する。 “%%”〜”%%” の間には、BNF記法の(ルール)と、それに対応する処理(アクションは“{ }”の中の部分)を記載する。最初の“%{ … %}”の間には、処理に必要なC言語を記載する。

# bison(水牛)は、yacc(山牛)の改良版。

(( mycalc.y ))
%{
#include <stdio.h>
#include <stdlib.h>

// yacc が定義する内部関数のプロトタイプ宣言
#define YYDEBUG 1
extern  int  yydebug ;
extern  int  yyerror( char const* ) ;
extern  char *yytext ;
extern  FILE *yyin ;

// 最初に呼び出される関数yyparse()
extern  int  yyparse( void ) ;

// 字句解析を呼び出す関数yylex()
extern  int  yylex( void ) ;
%}

// 字句(トークン)の定義
%union {
   int  int_value;
}
%token <int_value>  INT_LITERAL
%token ADD SUB MUL DIV CR
%type  <int_value>   expression term primary_expression

%%
// 構文の定義
line_list  : line                // 行の繰り返し
           | line_list line
           ;

line       : expression CR       { printf( ">>%d\n" , $1 ) ; }
           ;

expression : term
           | expression ADD term { $$ = $1 + $3 ; }
           | expression SUB term { $$ = $1 - $3 ; }
           ;

term       : primary_expression
           | term MUL primary_expression { $$ = $1 * $3 ; }
           | term DIV primary_expression { $$ = $1 / $3 ; }
           ;

primary_expression
           : INT_LITERAL
           ;
%%

// 補助関数の定義
int yyerror( char const* str )
{
   fprintf( stderr , "parser error near %s\n" , yytext ) ;
   return 0 ;
}
int main( void )
{
   yydebug = 0 ;        // yydebug=1 でデバッグ情報表示
   yyin = stdin ;
   if ( yyparse() ) {   // 構文解析を開始
      fprintf( stderr , "Error ! Error ! Error !\n" ) ;
      exit( 1 ) ;
   }
}

このプログラムを、yacc で処理すると、expression$1 ADD$2 term$3のルール「加算式($1) +($2) 乗算式($3)」という文になっている部分を見つけると、そのルールに対応するアクション“{ $$ = $1 + $3 ; }”「$1(加算式部分の値)と、$3(乗算式の部分)の値を加えて、$$(式の結果)を求める」といった処理を生成してくれる。yyparse() 関数を呼び出すと、構文の一番最上部の line_list に相当する処理が起動される。yyerror()は、構文解析の途中で文法エラーになった時に呼び出される関数。

生成されるパーサの内容に興味があるなら、生成される y.tab.c の内容を読むと良い。

make と Makefile

これらのプログラムでは、字句解析プログラム mycalc.l から生成された lex.yy.c, y.tab.h と, 構文解析プログラム mycalc.y から生成された y.tab.c を組合せて1つの実行ファイルにコンパイルする。 これらの手順は煩雑なので、make ツールを使う。

make は、 Makefile に記載されている“ターゲット”と、それを作るために必要な“依存ファイル”、 “依存ファイル”から”ターゲット”を生成する処理“アクション”から構成される。 make は、ターゲットと依存ファイルの更新時間を比較し、 必要最小限の処理を行う。

基本的な Makefile の書き方は、

ターゲット: 依存ファイル...
        アクション       # アクションの前はタブ

の様に書き、依存ファイルが更新されていたら、アクションを実行し、ターゲットを更新する。

以下に、今回の課題で使用する Makefile を示す。

(( Makefile ))
# 最終ターゲット
mycalc:	y.tab.o lex.yy.o
        gcc -o mycalc y.tab.o lex.yy.o

# 構文解析処理
y.tab.o: mycalc.y
        bison -dy mycalc.y	# -dy : yacc互換モード
        gcc -c y.tab.c

# 字句解析処理
lex.yy.o: mycalc.l mycalc.y
        flex -l mycalc.l        # -l : lex互換モード
        gcc -c lex.yy.c
clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o

(( ファイルの依存関係のイメージ図 ))
mycalc.l           mycalc.y
  |     \           |
lex.yy.c  y.tab.h  y.tab.c
  |            \    |
lex.yy.o        y.tab.o
        \    /
         mycalc

この課題にあたり、後半の実験では flex, bison などの unix 系プログラミング環境を利用する。

macOS の利用者であれば MacPorts や、Windows 利用者であれば、wsl(Windows subsystem for Linux) などをインストールし実行すること。

今回の実験であれば、linux(Debian系)ならば、”sudo apt-get install flex bison gcc make” にて、必要なパッケージをインストールして実験を行うこと。

再帰下降パーサのサンプルコード

再帰下降パーサ・サンプル

授業でもやっていない再帰下読みの説明でもあり、 簡単なサンプルコードを示したいけど、Webで探しても全体的に大きなプログラムばかりで、 再帰関数をどう記述していくか解かりにくい。 ということで、+,-,*,/と数字1桁という条件で、字句解析無しのサンプルコードを書いてみた。

// 再帰下読みの基本の一番短いサンプル
//
//   字句解析は面倒なので、
//   演算子は1文字のみ、定数は数字1桁だけとする。

#include <stdio.h>
#include <ctype.h>

// 括弧の無い +,-,*,/ だけの式の処理
//
//   今回は以下の構文だけとする。
//   以下のような文法の書き方をバッカス記法(BNF)と言う。
//
// exp_PLUS_MINUS ::= exp_MUL_DIV '+' exp_PLUS_MINUS
//                  | exp_MUL_DIV '-' exp_PLUS_MINUS
//                  | exp_MUL_DIV
//                  ;
// exp_MUL_DIV    ::= DIGIT '*' exp_MUL_DIV
//                  | DIGIT '/' exp_MUL_DIV
//                  | DIGIT
//                  ;
// DIGIT          ::= [0-9] ;

// 構文解析に使う関数のプロトタイプ宣言
int exp_PLUS_MINUS( char* , char** ) ;
int exp_MUL_DIV( char* , char** ) ;

// PLUS,MINUSだけの式
//   構文解析関数の引数
//   pc:   解析する文字列の先頭
//   endp: 解析が終わった場所
int exp_PLUS_MINUS( char* pc , char** endp ) {
   // left=乗除算式
   int left = exp_MUL_DIV( pc , endp ) ;

   if ( **endp == '+' ) {
      // right=加減算式
      int right = exp_PLUS_MINUS( *endp + 1 , endp ) ;
      return left + right ;
   } else if ( **endp == '-' ) {
      // right=加減算式
      int right = exp_PLUS_MINUS( *endp + 1 , endp ) ;
      return left - right ;
   } else {
      // 乗除算式を返す
      return left ;
   }
}

// MUL,DIVだけの式
//   DIGITに相当する構文木の処理は、組み込んでしまう。
int exp_MUL_DIV( char* pc , char** endp ) {
   if ( isdigit( *pc ) ) {
      // left=数値
      int left = *pc - '0' ;
      *endp = pc + 1 ;
      if ( **endp == '*' ) {
         // right=乗除算式
         int right = exp_MUL_DIV( *endp + 1 , endp ) ;
         return left * right ;
      } else if ( **endp == '/' ) {
         // right=乗除算式
         int right = exp_MUL_DIV( *endp + 1 , endp ) ;
         return left / right ;
      }
      // 数値を返す
      return left ;
   } else {
      printf( "Error\n" ) ;
      return 0 ;
   }
}

// 課題(1): () を含む処理にしたかったら、
//          BNF の構文木は、どう直すべきか?
// 課題(2): () を含む処理、空白を無視する処理、
//          定数式が複数桁を使える処理。

int main() {
   char* e = NULL ;
   printf( "%d\n" , exp_PLUS_MINUS( "1+2*3" , &e ) ) ;
   printf( "%d\n" , exp_PLUS_MINUS( "1*2+3" , &e ) ) ;
   return 0 ;
}

理解確認

  • このプログラムでは演算子は、右結合だろうか?、左結合だろうか?

コンパイラの技術と関数電卓プログラム(1)

コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、printf( “%d” , eval( “1+2*3”) ) みたいな計算プログラムを作成する。

計算式から、計算処理を行う場合、演算子の優先順位を正しく処理できることが求められる。
一般的には、計算の機械語を生成する場合、データを準備して計算という方法であり、 逆ポーランド記法変換が行われる。
たとえば、”1+2*3″は、”1,2,+,3,*” といった表記に改められ、変換後の式は スタックを用いて、「値はpush,演算子はpop,pop,計算して,push」という 単純なルールで処理すれば、計算を行うことができる。

字句解析と構文解析

このような、計算式の処理を実行する場合、”1“,”+“,”2“,”✳︎“,”3“という 字句に切り分ける処理を、字句解析という。 この結果から、”式✳︎式”なら掛け算、”式+式”は足し算といった、 前後の字句の組合せから、構文木を生成する処理は、構文解析という。 コンパイラであれば、この後、最適化コード生成などが行われる。

C言語であれば、コンパイル前後には以下の処理が行われる。

  • プリプロセッサ処理
    ↓(#の無いCコード)
  • コンパイル処理
    • 字句解析
    • 構文解析
    • コード生成

    ↓(中間コード)

  • リンク処理 ← ライブラリ
  • 機械語

字句解析と正規表現

字句(トークン)の切り出しでは、その文法を説明する際には、正規表現なども用いられる。

簡単な正規表現
 . 任意の文字
 * 直前の0回以上の繰り返し
 + 直前の1回以上の繰り返し
 [0-9a-z] カッコの中の文字のいずれか - は範囲を示す。
 (a|b|c) 丸カッコの|区切りのうちのどれか。
 (例) C言語の変数の正規表現 [a-zA-Z_][a-zA-Z0-9_]*

構文解析の方法

構文解析では、構文を状態遷移として考え、この式の後にくる可能性のある状態は? という考えで解析を行う。 このような構文は、一般的にバッカス・ナウア記法(BNF)などで表現されることが多い。 また、簡単な構文解析であれば、

などが用いられる。

再帰下降パーサ

簡単な再帰下降パーサの演習として、1桁の数字と+,*演算子の処理プログラムを 考える。

加減,乗除の式のバッカス記法(BNF)
exp_加減 ::= exp_乗除 '+' exp_乗除
          | exp_乗除 '-' exp_乗除
          | exp_乗除
          ;
exp_乗除 ::= DIGIT '*' exp_乗除
          | DIGIT '/' exp_乗除
          | DIGIT
          ;
DIGIT   ::= [0-9]
          ;

練習として、上に示す再帰下降パーサに、 (1) “(“,”)” を含めた場合の、BNF 記法を考え、(2) 数値として複数桁が使えるようにし、 (3) 式を読みやすくする空白を処理できるように 改造せよ。

専攻科実験・コンパイラと関数電卓プログラム作成

  • コンパイラの技術と関数電卓プログラム(1)
    • 課題
      • 複数桁の数字が使えること。
      • 式中に空白が使えること。
      • 何らかの演算子を追加すること。
        • (例) %,単項演算子のマイナスなど
      • 演算子が左結合か右結合か確認すること。
      • オプション課題
        • 変数が使えること。
          (変数名は1文字のA-Zといったもので良い)
    • レポート内容
      • コンパイラ技術の概要、課題(1)の説明・最終的なBNF記法・ソース・動作検証、考察
  • コンパイラの技術と関数電卓プログラム(2)
    • 課題
      • 基本的に、lex+yaccで(1)と同様の課題完成を目指す。
    • レポート内容
      • lex,yaccの概要、課題(2)の説明・ソース・動作検証、考察

SQLで集約関数と集合計算

基本的なSQL命令のための集約関数などの追加を説明のうえ、演習課題に取り組んでもらう。
来週も後半を演習時間とする予定。

特殊な条件演算子

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(SG.業者番号) FROM SG WHERE SG.優良度 > 100 ;

集合計算

複数の SQL の結果に対し、集合和, 集合積, 集合差などの処理を行う。

... UNION ...  集合和
... EXPECT ... 集合差
... INTERSECT ... 集合積

SELECT S.業者名 FROM S WHERE S.所在 = '福井'
UNION
SELECT S.業者名 FROM S WHERE S.所在 = '東京'

演習課題

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

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

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

SQLと結合

SQLの基礎

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

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

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

// 結合
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.業者番号 のような選択を記載する。最後に、結果として欲しいデータを抽出する射影を記載する。

// 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 , "福井" } ,
   :
} ;

// 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の副問い合せ

前節の結合処理は時として効率が悪い。このような場合は、副問い合わせを用いる場合も多い。

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}

Thunderbirdの送信時エンコーディングがJISじゃなかった

とある先生から、メールが文字化けで読めないとの連絡があった。古いメールソフトを使っているとのことだったけど、私はThunderbirdで極力プレインテキストで送っているからJISコードだろうし古いメールソフトでも読めるはず…と思っていたけど、確かめると @kosen-ac.jp が BASE64 で送られていたり、@gmail.com が quoted-printable だったり。

設定を再確認したら、設定のフォントと文字エンコーディングで、デフォルトエンコーディングがUTF-8になってた。古い人間なので、送受信もデフォルトエンコーディングが「JIS(iso-2022-jp)」、「可能な限り返信でもデフォルトエンコーディングを使用」に設定を行った。

うーむ、ちゃんとJISに設定したのに、@gmail.com のメールのタイトルが、”=?UTF-8?B?…”になってら。

専攻科創造デザイン演習で特許調査実習

今日の専攻科1年の創造デザイン演習では、特許調査実習ということで日本弁理士会の方に協力をいただき、具体的な調査のやり方を実習。

特許情報プラットフォームJ-PlatPat に接続し、様々な検索方法を習いました。