トップ » バックナンバー » Vol.12 » データベースの理論とその発展

Accumu Vol.12

データベースの理論とその発展

寺下 陽一

1 データベース理論の始まりとその実用化

現代のデータベース技術はその中核部分が厳密な数学理論に基づいて発展させられてきたという点で,数多くあるコンピュータ/ITの諸技術の中でも非常にユニークである。もちろん,他の技術においても理論が使われていないわけではなく,例えばプログラミング言語の設計や実装においては言語理論が,また3次元グラフィックスにおいては微分幾何学を中心とする計算幾何学の理論が重要な役割を果たしている。更に,コンピュータの最も中枢にある論理回路はブール代数に基づいて設計されているのはよく知られた事実である。しかし,現代の関係型データベースについては,そもそもデータベースの為の理論が提唱され,発展させられてきたのである。すなわち,関係型データベースの定義から始まり,それに伴う代数系(関係代数)の理論,データベースの設計に関する正規化理論などがまず構成され,その抽象的な世界をITの現場で実用化するという過程をたどっているのである。これは素粒子物理学において,まず理論が提唱され,それを実験・観測によって実証するというプロセスと似た,理論先行型の技術分野ということができるであろう。

関係型データベースの理論は,IBM研究所研究員であったE.F.Coddが1970年に発表した有名な論文(A Relational Model of Data for Large Shared Data Banks)にその基礎を置く。データベースという言葉あるいは概念はそれ以前から存在し,それを企業情報システムの形成に利用するため様々な努力がなされてきた。「階層型データベース」,「ネットワーク型データベース」などのデータモデルが考案され広く実用化されてきた。しかし,これらのデータモデルは理論的な枠組みに基づくものではなく,現場の要請に応じて様々なデータ構造化手法が組み込まれてきたものである。その結果として,これらのデータモデルを基に実装されたデータベース製品(DBMS:DataBaseManagement System)は時と共にどんどん複雑化し,これらを利用するためには極めて熟練したプログラマが必要とされるようになっていた。

Coddの関係型データモデルは,数学でいう「関係」の概念に基づいたデータモデルである。すなわち,データベースに含まれるべきすべてのデータを複数個の表形式で表現し,これらの表を「関係」と見なすことにより,データベースを集合論的に定式化したものである。以前のデータモデルが,ポインタとか繰返し構造のような物理構造に伴う複雑な構成要素を持っているのに対し,関係型モデルは「関係」という構造のみに基づき,それ以外の構成要素を全く必要としない,極めて単純化されたものであったため,発表当時は関係者の間で非常に大きな反響を呼んだ。

しかし,この新しいモデルの有用性について大きな期待が寄せられたからといって,このモデルがすぐに実用化されるということにはならなかった。その理由として第一に,当時は既に階層型やネットワーク型データベースが実用化され,この方式のDBMS(IBM社のIMS,Cullinet Software社のIDMSなど)を提供するソフトウェア・ベンダーやこれらの製品を利用して情報システムを構築中であった企業ユーザは既に多大な人的資源と資金を投入していたため,これらの投資を無視して新方式のものに移行するということは到底不可能であったという事情がある。第二に,関係型モデルは高度に抽象化されたものであるため,これを実装するためにはソフトウェア技術上の困難があり,また当時のハードウェア(CPUと二次記憶装置)ではとてもパワー不足であったからである。

だからといって,実用化があきらめられたというわけではなく,Coddの所属するIBM社のサンホゼ研究所では彼の論文が発表された直後頃から実験用の関係型DBMSの製作に着手されていた。この実験用システムは”System R“と言い,このシステムで用いられたクエリ言語は SEQUEL と呼ばれていた。現在広く用いられているSQLの前身である。また,カリフォルニア大学バークレー校でも実験用システムの製作が進められ,これは INGRES と呼ばれていた。

IBMの実験システムは1980年代初頭に商業化され,SQL/DS,およびDB2という名称で市場に出されるようになった。カリフォルニア大学のシステムは1970年代の終わり頃に商業化され,実験システムと同名の INGRES という商品名で市場に出されるようになった。その当時の関係型システムは,(まだパソコンが普及する以前であったから)当然のことながら大型や中型のメインフレーム用のものであった。IBMのDB2の場合は,それ以前から同社から出されていたIMS(階層型DBMS)がまだ全盛であり,殆どのIBMユーザはこれを用いて情報システムを構築していたため,DB2はIMSと競合するような形になり,これらのユーザサイトにおいては少なからず混乱を引き起こした。

小型システム(パソコン)用の関係型システムは1980年代の後期になってから現れるようになった。PARADOX,dBaseIV,WATCOM-SQLなどが挙げられる。これらのシステムは「関係型」とはいうものの,厳密的な意味での関係型モデルには沿っていないものもあり,また,異なった製品間の互換性についても問題があった。しかしその後,本来的な関係型モデルへの忠実度は高くなり,同時に異なる製品間の互換性も著しく改良された。現在,Windows システムで一般的に用いられている ACCESS は関係型システムとしてかなり完成度の高いものである。一方,ネットワーク環境でのデータベース利用(クライアント・サーバシステム)に関しては,ORACLE システムが市場の大きなシェアを占めているのは周知のとおりである。

2 関係型データモデルの理論

関係型データモデルの理論では,データの集まりをすべて表(Table)の形で表すのを基本としている。ただし,理論的には「表」という言葉の代わりに「関係」という用語を用いており,厳密には「表」と「関係」は同じものではない。情報システムなどで対象となるデータはすべて複数個の関係として編成される。どのような関係を何種類編成すればよいか,すなわちデータベースをどのように設計すべきかは,「正規化理論」という理論によってその指針が与えられることになっている。「表」の代わりに「関係」という理論的に厳密な用語を用いると同時に,それに関連する他の概念も厳密に定義された理論用語が用いられる。表における「行」の代わりに「タプル」,「列」の代わりに「属性」,またデータ値に対して定義される「データ型」の代わりに「値域(ドメイン)」という用語を用いる。「関係はタプルの集合」であり,「関係の集合がデータベース」となる。

「部品―納入業者―納入実績」データベース

図1は有名なデータベースの教科書”An Introduction to Database Systems“(C. J. Date 著)で解説用に用いられる例題データベース「部品<S1, 佐藤工業, 20, 東京>,<S2, 中村機器, 10, 大阪>,・・・がタプルであり,この関係は5個のタプルから成っている。また,この関係は,SNUM,SNAME,STATUS,CITY という4個の属性を持っている。SNUMに対するドメインは「業者番号として可能な文字列の集合」,SNAMEに対しては「業者名として可能な文字列の集合」,STATUSに対しては「業者の状況コードとして可能な数の集合」(正の値のみ,おそらくは100以下),CITYに対するドメインは「日本の都市名の集合」となる。

これら関係については種々の演算が定義されており,このような演算の系は「関係代数(Relational Algebra)」と呼ばれている。演算には1個の関係を対象とする「単項演算」と,2個の関係を対象とする「二項演算」がある。また,これらの演算の中には従来の集合論で用いられ,よく知られているもの(Union, Intersection,Product 等々)と,関係データベース専用のものがある。もちろん,データベース理論にとって重要なのは後者である。これらの演算を用いてデータベースの検索(クエリ)を行うことができる。図1を用いて主要な演算の適用例を示してみよう。

まず,「選択」演算(SELECT)。これは単項演算であり,与えられた関係において指定されたタプルだけを抽出して新たな関係を作り出す。演算記号としてσ(シグマ)が用いられる。例えば,

σCITY= '大阪' (S)

とすると,図2(a)のような結果が得られる。(大阪所在の業者のみが抽出される。)

関係代数

次に,「射影」演算(PROJECT)。これも単項演算であり,与えられた関係において指定された属性だけを抽出して新たな関係を作り出す。演算記号としてπ(パイ)が用いられる。例えば,

πSNAME,CITY (S)

とすると,図2(b)のような結果が得られる。(業者の名称と所在地のみが示される。)

実用上もっとも重要なのは「結合」演算(JOIN)である。これは2個以上の関係を共通の属性の値によって1個の関係に結合してしまうものであり,記号 記号 が用いられる。図2(c)のように,

SP 記号 S.SNUM=SP.SNUM S

にすると,関係SPのタプルと関係SのタプルについてSNUM値の等しいもの同士を連結した新しいタプルからなる別の関係が作られる。すなわち,元々のSPにおいては業者番号だけしかなかったのを,業者名や所在地なども一緒に示したいときにこの結合演算が用いられる。後に述べる関係モデルの正規化理論において,あるデータベースに属する関係はすべて冗長度が最小限(すなわち情報の重複が最小限)であることが要求されているため,冗長を含むような結果(理論的には業者番号だけで良いところを,業者名等の冗長な情報を含む)を求めるときにこの連結演算が欠かせないことになる。

データベースの検索を(理論的に)行うには,上記の関係代数の他に「関係計算(Relational Calculus)」と呼ばれる体系がある。これは人工知能分野でよく用いられる述語論理に基礎をおいたものであり,必要とする情報を探すための条件を記述するための記法を提供する。関係代数が「手続き的」言語と言われるのに対し,関係計算は「宣言的」言語と言われる。図3は関係計算(正確にはタプル関係計算)による検索の例を示す。

関係計算によるデータベース検索

図3(a)は「大阪所在の業者を抽出せよ」というクエリを関係計算で表現したものである。tは個々のタプルを表す変数で「タプル変数」と呼ばれる。縦棒以降は抽出すべきタプルに関する条件である。S(t)は,「tがSに属する」という条件を示す。図3(b)は「部品P2を納入している業者を抽出せよ」というクエリである。この場合,それぞれSとSPのタプルを表すtとuという2個のタプル変数が用いられており,これら2個の関係を関連付けて検索する方法を示している。すなわち関係代数の場合の連結演算に対応するものである。記号∃は存在限定子と呼ばれる述語論理の記号であり,∃u(…)は,「…という条件を満足するuが存在する」という条件を示す。u.SNUM=t.SNUMという条件により関係Sと関係SPが関連付けられていることがわかる。

理論的な立場からいうと,関係代数を用いても,あるいは関係計算を用いても,どちらの方法でもデータベースの検索が可能である。実際,関係代数の検索能力と関係計算の検索能力は同等であることが理論的に証明されている。しかし,実用的な立場からいうと,一般のユーザがこのような数学的な記法には馴染み難いので,もう少し分かり易い検索言語が提案された。これがSQL(Structured Query Language)である。SQLは基本的には関係計算にのっとった宣言型(記述型)の言語であり,存在限定子∃も含まれている半面,関係代数の概念も取り入れられている。特に連結(JOIN)の概念はSQLに取り入れられているだけではなく,関係データベースの利用において中心的な役割を果たしている。

念のため述べると,SQLは単なる検索言語であるだけにとどまらず,データベース更新の為の諸機能,さらにデータベースの定義機能から管理機能をも含む大規模な言語体系となっている。

3 関係型データベースのための設計理論

Coddは当初の論文において,関係データベースの検索機能(関係代数,関係計算)の理論的定式化を示したのみではなく,データベースの設計に関する理論体系をも提案した。これはデータベースの正規化理論と呼ばれるものである。データベースの設計とは,構築中の情報システムに含むべきすべてのデータ項目を最も「望ましい」形の関係の集合として編成する作業ということができる。「望ましい」というのは, 「すっきりしている」,「意味が分かり易い」,「無駄がない」,といった言葉で言い換えることもできるのであるが,このような直感的な言葉を理論的に明確化しようとするのが正規化理論である。

正規化理論においては,設計を始める前は混沌状態にある多種多様なデータを段階的に整理していくが,この整理する過程を正規化と言う。正規化の達成度には何段階かある。最も弱い段階の第1正規形から始まって,第2正規形,第3正規形(Boyce-Codd正規形),第4正規形,第5正規形まで提案されている。理論的には第5正規形が最も望ましいとされるが,実用的には整理されすぎて関係の個数が多くなりすぎ,処理の手続きがかえって煩雑になる場合が多いため,通常は第3正規形で大体十分であるとされている。正規化を進めていく際の中心的な指針となるのが「関数従属性」の概念である。これはデータベースに含まれる種々のデータ項目間の意味的な(semantic)従属関係を明確にするものである。この従属関係を決定するためには,企業等の情報システム設計において対象となる種々のデータ項目の機能・役割を明確にし,それらの有機的な関係を分析する必要がある。

データベースの正規化(多くの場合,第3正規形)は実際のデータベース管理においてどのような意義を持つのであろうか。漠然とした「望ましい形」という直感的な要請を定式化することにより,実用上でも重要な効果を持つものであることが正規化理論で明確に示されている。適切な正規化処理をすることにより得られる主要な効果として,①種々の更新操作(挿入,変更,削除)を行う時に発生する可能性のある整合性違反を防止かつ制御できる,②不必要なNull値(未知データなど)の使用を回避し,集計計算やジョイン演算を円滑に行うことができる,③不適切なデータベース設計の場合に生じるジョイン不整合性を回避することができる,などである。

現在市販されているDBMSやシステム設計ツールの多くは,データベースの設定に際して正規形のチェックや正規化を支援するための機能を備えている。このような機能は,安定かつ管理の容易な情報システムを構築する際の大きな助けとなっている。

4 関係型データベースの発展と拡張

最初のCoddの論文が発表されて30年余,その間関係データベースはデータ管理技術の中核的な手段となり,多くの情報システムの構築において重要な貢献を成し遂げてきた。しかし,その間のハードウェアの高性能化,ソフトウェア技術の急速な発展,コンピュータ利用分野の飛躍的な拡大に呼応して,関係データベースの理論・技術についても様々な発展拡張がなされている。ここではその中から「推論型データベース」,「オブジェクト関係型データベース」,および「データウェアハウス」を紹介する。

4‐1 推論型データベース

先に述べたように,関係データベースにおける関係の操作(クエリ)は関係計算(Relational Calculus)によって完全に表現できることが証明されている。ところがこの関係計算は(一階)述語論理に基づいたものであり,これは人工知能分野の中心課題である推論機構の基礎となる理論である。従って,関係データベースに推論機構を組み込むことは非常に自然な機能拡張と考えることができる。

関係データベースを述語論理の枠組みで見ると,各関係のタプルは1個の事実(fact)を示している。例えば,Supply(納入する)という述語が定義されているとすると,

Supply (S1, P5, 100)

は,S1がP5を100個納入したという事実を示している。この3個の引数のうちいずれかを変数にし,例えば,

Supply (S1, P5, x)

とすると,これは「S1はP5を何個納入したか?」というクエリになる。このクエリに答えるには,この質問をユニフィケーションという操作を用いて必要なタプルを探し出すことになる。推論機構を可能にするためには,これに加えて規則(rule)を導入する必要がある。規則は変数を含む述語表現間に「if-then」型の関係で示される。これらの規則と事実を基にし,与えられた質問に対してユニフィケーションを反復(多くの場合,再帰的に)適用し,解答を探し出すことになる。これらの事実や規則,そしてクエリを表現するために,Datalogという言語が用意されているが,これは人工知能分野で以前から用いられてきたPrologの一種である。

推論型データベース用のソフトウェアとしては,LDL (Logic Data Language) ,NAIL! ,CORALなどがある。

4‐2 オブジェクト関係型データベース

オブジェクト指向パラダイム(OOP)に基づいたプログラミング手法,システム開発手法が広く用いられるにつれて,データベースに関してもこの種の手法に適応できるような機能が要求されるようになってきた。また,従来は企業等の日常業務(いわゆるトランザクション業務)に関連するデータを主目標として来たデータベース・アプリケーションがより複雑なデータを対象とするに従い,オブジェクトの概念をも包括できるようなデータモデルが必要となってきた。オブジェクト関係型データベースはこのような要請に応えて開発されたものであり,従来型の関係型データベースを拡張し,オブジェクトを扱えるようにしたものである。この種のシステムの例として,Informix Dynamic Server (IBM社)とOracleを紹介する。

Informix Dynamic Server (IDS)

IDSはユーザ定義のデータ型(OPAQUE, DISTINCT, ROW, COLLECTION),更にユーザ定義関数をサポートしているが,これらの機能をベースにデータ型の継承と,関数の継承が可能となっている。これに加えて,従来のDBMSでは対象とされていなかった特殊な複合型データを扱うために「データブレード」という機構を備えている。データの種類に対応して様々なブレード(Blade:刃)を用意しておき,安全カミソリの刃を取り替えるように,処理の対象となるデータに応じて専用のものをシステムに装着する方式がとられている。

この様なデータブレードが扱うことができる代表的なデータとして,以下のようなものがある。

①2次元図形(点,直線,多角形,経路,円など)。種々の設計図のデータベースに用いられる。

②画像データ(ビットマップ)。基本的な画像 処理用関数(回転,切取り,画像強調など)も組み込まれている。

③地理データ。GISなどで用いられる。

④時系列データ。株価の変動などを扱うことができる。

⑤大規模テキスト。フルテキストの文献検索などに利用される。

このデータブレードはユーザ定義も可能であるので,必要に応じて様々なものが作成され,ライブラリーとして利用できる様になっている。

Oracle

Oracleはバージョン8以降にオブジェクト機能を追加している。ユーザ定義のデータ型が可能で,データ型の一種としてオブジェクトを設定することが可能である。上で述べた複合型データなどはカートリッジという機構で組み込まれるようになっている。バージョン9ではこれらの複合型データも従来型データと全く同じ形式で操作できるようになっている。処理できるデータ型としてXML文書も含まれており,ウェブ上でのドキュメント転送が容易となっている。また,アプリケーション開発用言語としてC,C++,Java,COBOL,PL/SQL,Visual Basicが使えるようになっており,これら言語の持つOOP機能が,プログラムに埋め込まれたSQLとシームレスに動作できるようになっている。

4‐3 データウェアハウス

従来型のデータベースは業務データベース(トランザクション・データベース)とも言われ,日常業務で発生する様々なデータ照会,データ更新を迅速に,的確に,かつ正確に行うことを目標とするものである。従って,データは日常業務に直接関係するものに限られ,複雑性に関してもそれ程高いものではない。

一方,企業経営においては日常業務に直結するデータのみではなく,時間的に遡って現在では用いられていないものとか,地理的に広範囲にまたがるものを基にして様々な経営上の意思決定を行う必要が往々にして発生する。このような意思決定をサポートするシステムをDSS(Decision Support System)というが,これに用いられるデータは日常業務用データに比べて1桁も2桁も大規模なものになる。このようなデータを格納する機構をデータウェアハウスと呼んでいる。

データウェアハウスは業務データベースと異なって総合的な集計・分析に用いられるのが主目的であるので,それほど頻繁に更新される必要はない(いわゆる非活性型データ)。一般に,日常業務では既に用いられなくなった過去のデータをも含めて処理の対象となるのでデータ量は非常に大きくなる。また,頻繁な更新はない代わりに時間とともに累積的に増大していくのが普通である。データウェアハウスに収容すべきデータは一般に非常に多くの多様なデータ源から集められるのでフォーマットや記法を標準化する必要がある。従って,システムへの入力に際しては綿密な前処理・加工などが行われ,そういう意味で業務用データベースにおけるリアルタイム更新とかなり様子が異なり,バッチ処理的な更新操作となる。

データウェアハウスにおけるデータキューブ

データウェアハウスのデータモデルの中心となる概念は,2次元のマトリックス,あるいは3次元以上の高次元のデータキューブといわれるメッシュ型のデータ表示方式である。データキューブの各次元(座標軸)には集計や分析のパラメータとなる項目(販売実績を分析する場合であれば,過去に遡る各四半期,商品項目,営業地域など)を割当て,各々のセルに対応するデータ値(売上実績など)を記録する(図4を参照されたい)。このデータキューブは様々な次元(座標軸)に沿って見る(その次元に関して射影をとる),それらの次元について部分的に圧縮する(ロールアップ,すなわち個々の商品の代わりに商品区分単位で小計を見るなど),あるいは部分を展開して詳しい表示をする(ドリルダウン)といった操作が可能で,様々な視点,視野からの分析ができるようになっている。

データウェアハウスにおけるテーブルの構成

このデータキューブのデータ値は2種類のテーブルによって管理されている(図5を参照されたい)。その一つはファクト・テーブルと呼ばれ,表示の対象となるデータ値を収容すると同時にそのデータ値の由来となるパラメータ値(四半期,商品項目,営業地域などの各次元)への参照値(ポインタ)を含んでいる。これによって参照されるパラメータ値は実際にはいくつかの項目からなるタプルであって,パラメータの種類の各々に関してテーブルとして与えられている。これらのテーブルは次元テーブルと呼ばれている。次元テーブルには個々のパラメータ(例えば商品項目)に関する詳しい情報が収容されている。

データウェアハウスが確立されると,それを基にOLAP(On-line Analytical Processing)システム,データマイニング・システムなどが構築され,高度の経営判断のサポートに活用されることになる。

5 おわりに

筆者がCoddの関係データベース理論に初めて接したのは,1976年から三年計画で進められた文部省特定研究「情報システムの形成過程と学術情報の組織化」に参加した際であった。この研究グループは当時の日本の代表的な情報工学・情報科学の第一線の研究者がすべて参加するという国家的なプロジェクトであり,そこで行われた研究は情報工学・情報科学の実に広範な分野を含むものであった。しかし研究テーマの性格からして中心的な課題はデータベースに関連するものであり,グループの研究者たちの関心は何と言っても当時としては最新のCoddの理論であった。この理論を早急に修得しなければならないということで,リーダーの1人である北川敏男先生の号令の下,グループの全研究者による勉強会が始められた。その時用いられたのがC.J.Dateの教科書である。当時のトップクラスの研究者(現在では日本の情報分野の重鎮の先生方)が,大学院生の勉強会さながらにセミナー室に缶詰になって汗を拭き拭き読み合わせをしていたのが思い起こされる。この教科書も現在では第7版となっており,今年(2003年)の夏ごろには第8版が出るとのことである。第1版に比べるとページ数は3倍以上になっていようか,その間のデータベース研究の発展が凝縮されている書物である。

この著者の他の記事を読む
寺下 陽一
Yoichi Terashita
  • 京都大学理学部宇宙物理学科卒業
  • 米国アイオワ大学大学院に留学,Ph.D.取得
  • アイオワ大学講師,ペンシルバニア州立大学講師を経て,帰国後,KCG創立グループの一員として日本初の情報処理技術教育カリキュラムを作成
  • その後,金沢工業大学に赴任,同大学情報処理工学科の創設に携わり,主任教授,同大学情報処理サービスセンター長を務める
  • 金沢工業大学名誉教授
  • 永らく私立大学情報系教育の振興に貢献
  • 元社団法人私立大学情報教育協会理事
  • JICA(旧国際協力事業団)専門家(情報工学)としてタイ国に3回派遣される
  • 1995年4月本学院に再就任
  • 京都コンピュータ学院洛北校校長,京都コンピュータ学院国際業務部長を経て,2004年4月の京都情報大学院大学の開学に伴い,京都情報大学院大学応用情報技術研究科ウェブビジネス技術専攻主任に就任
  • 現在,京都情報大学院大学副学長

上記の肩書・経歴等はアキューム15号発刊当時のものです。