1998 後期開講 : Database 演習

(このページの最終更新日 )

ここには 1998 年度の IS 研究科 N 専攻のデータベース学演習で用いた資 料があります．利用は御自由ですが，この資料を利用する場合には御自分の責 任で行なって下さい．この資料によって生じたいかなる損害についても山内は 責任を負いません．御意見，御提案などについては歓迎いたします．

Copyright (C) 1998 YAMAUCHI Hitoshi 山内 斉

この演習ではデータベースと関係の深いデータ構造とアルゴリズムについ ての話題をとりあげました．解答例については御相談下されば対処するかもし れません．

課題内容

  1. Java を利用する環境を作る
  2. 二分木の作成
  3. B 木の作成
  4. ハッシュ表の作成
  5. マージソート
  6. SQL に触れてみる
  7. 2 Phase Lock の実装

各資料の課題内容

課題 1 : 1998年10月 7日(水)

  1. 研究室にJavaがインストールされているか確かめ、まだインストールされ ていなければ Sun の Pageから JDK をダウンロードしてインストールしな さい。(注意: ディスク領域を節約するため、1つの研究室で2 人以上がダウンロードしないこと。)
  2. Javaチュートリアルを見て「Hello World」アプリケーション を作成し、実行してみなさい。

課題 2 : 1998年10月14日(水)

  1. 数列 S_1 = {7, 3, 2, 9, 10, 5, 14} を入力し(授業での配布資料)図 2 のような木が生成されることを確認せよ．以下，簡単のため，入力 はこの並びであればどのような形式でも良く，また，入力の key が正 の整数を仮定して良い．
  2. 数列 S_2 = {1, 2, 3, 4, 5, 6, 7, 8, 9} を入力しどのような木が 生成されるかを見よ．入力はこの並びであればどのような形式でも良い．
  3. 数列の入力を数字の key と文字列の組に変更せよ．表 1 の組を入力して木を生成せよ．前処理として行の並びを変更せずに key と文字列を入れかえても良い．

    表 1 
           関根             5648
       伊藤(秀)         5630
       山内             5638
       岡本(秀)         5636
       阪口             5646
       出澤             5645
       神原             5463
       弓場             5640
       前田             5637
       福田             5263
       韓               5625
       小嶋             5627
       佐藤             5643
       長岡             5626
       土屋             5632
       曽和             5635
       藤田             5647
       本多             5641
       小菅             5238
       中村(整)         5451
       弓場             5640
       陳               5631

課題 3 : 1998年10月28日(水)

位数 2 の B 木を作成しデータを挿入するプログラムを作成し，ソースコード と共にレポートを提出すること．ソースコードは今回説明したように E-mail での提出も行なうこと．レポートには，表題:データベース実習， 課題名:「B 木の作成プログラム」とする．実習者の名前，学籍番号を明記すること．締切 は，11/11 のこの時間とする．レポートでは次のことについて論ぜよ． 入力データは以下のものを用いて B 木ができているか試すこと．

課題 4 : 1998年11月11日(水)

ハッシュ表を作成し，データを挿入するプログラムを作成し，ソースコー ドと共にレポートを提出すること．ソースコードはレポートのみならず， E-mailでの提出も行うこと．締切は 11/25 日のこの時間とする．課題名は 「ハッシュ表の作成」とする．

今回の課題では，GNU GENERAL PUBLIC LICENSE をファイルから読み込み，各単語の数を数えよ．このファイルはここから持っていくこと．レポートには単語とその頻度の上 位 20 位までを示すこと．ただし，単語数の頻度別ソートは，作成したプログ ラムの結果から sort などのプログラムを利用して整列してもよい．ソート部 分をプログラミングする必要はない．

課題 5 : 1998年11月25日(水)

次のプログラムの出力 (1000 要素)をマージソートするプログラムを作成しな さい．ただし，メモリ上には最大一度に 500 要素までしか保持してはいけな い．それを越える場合にはファイルに書くこと． 
/**
 * Random Number Generator Copyright (C) 1998 YAMAUCHI Hitoshi 山内 斉
 *  @author YAMAUCHI Hitoshi 山内 斉
 */
import java.io.*;
import java.util.*;

class RandomGen {
    public static void main(String [] arg)
    {
        Random r = new Random(1234);
        for(int i = 0; i < 1000; i++)
        {
            System.out.println(Math.abs(r.nextInt()) % 10000);
        }
    }
}
本来は問題に書くものでないのかもしれないが，この問題の意図は外部ソート を行うことである．したがって，主記憶に入りきらない場合でもソートが可能 であることを実験して欲しい，そこで，たとえば最初の 1000 要素をシーケン シャルに読み， 250要素の 4 つのファイルにする．その後，内部で 250 要素 のソートをマージソートで行う(あくまでマージソートして欲しい)のも良いし， あるいは本当に 1000 要素のファイルまで分解しても良い．

課題 6 : 1998年12月 9日(水)

前準備として PostgreSQL などの SQL の利用可能なデータベースを触れる 環境を用意する．(自分で install しても良いし，既にある環境を利用するな ども可．以下の実験を行えば良い．) 今回はソースが不要なので E-mail での 提出は行わなくて良い．

PostgreSQL のソースは次の場所にある．

課題
  1. student.sql.gz を実行し，各動作について簡単に解説を行うこと．
  2. 表を自分で 1 つ作成し，select 文を実行せよ
  3. 複数の表を作成し，それらに対して select 文を実行せよ

課題 7

今回の演習課題は 2 phase lock の実装を行う．どのような方法をとって も良いが，shell script を用いる方法が簡単であろう．Unix 系の OS では mkdir，ln などの動作が不可分で行なわれるものがある．あるいは lockf を 使うという方法もある．perl は flock を用いることで lock を行うことが可 能である．

簡単な lock の動作は次の図 1 のようにして確認できるだろう (Unix Magazine 1998/11 多治見 寿和，ファイルのロックを参照)．このファイルを lock.sh として

lock.sh & lock.sh & lock.sh

のように起動する．この場合には図中の -f と touch が不可分な命令でな いためにcritical section に同時にいくつものプロセスが入ることができる． 上手くいかない場合には，touch の前に sleep 1 などを入れて不可分性をさ らに高めてやれば良い．

#!/bin/sh 
LOCK=/tmp/lock          # lock file : 存在したら lock 中

while [ -f $LOCK] ; do :; done
touch $LOCK

echo "Here is in critical section (PID = $$)"
sleep 3

rm -f $LOCK
echo "Here is out of critical section (PID = $$)"
exit 0

図 1 正しくない lock のかけ方

課題
copyright (C) 1998 山内 斉 (YAMAUCHI Hitoshi)
最終更新日 :