2009年12月16日 「実践編-14　レコード・アット・ア・タイム 法」 を読む >> 目次にもどる
2018年10月 1日 補遺 　


　

　本編の題名を 「レコード・アット・ア・タイム （record-at-a-time） 法」 としていますが、本編で説明している技術は、従来の 「レコード・アット・ア・タイム 法」──すなわち、index-key （特に、unique-key） を使って、レコード 単位に アクセス する やりかた──ではなくて、indexing （B-tree 構造） です。

　「木 （tree）」 は、離散数学の 「グラフ （graph）」 の領域で説明されます。数学では、基本閉路をふくんでいない グラフ を 「森 （forest）」 とか 「林」 といい、連結な無閉路 グラフ を 「木」 と云います。特に、コンピュータ・サイエンス では、「木」 には 1つの 「根 （root）」 があることを前提にするので、「木」 と謂えば、ふつう、「根付き木 （rooted tree）」 のことを云います。さて、「閉路」 とか 「連結」 については数学の書物を読んでもらうとして、「木」 は有向 グラフ の特殊形であって、「根付き木」 が indexing で使われています。Indexing に流用されている 「根付き木」 の しくみ を 145ページ に単純な図で示しました。

　以下の単純な 「木」 を例にして、「検索法」 を説明します。 


　　　　　　　　　　　　　　r ○
　　　　　　　　　　　　　　／　＼
　　　　　　　　　　　　　／　　　＼
　　　　　　　　　　 y1 ○　　　　　○ y2
　　　　　　　　　　　／　＼
　　　　　　　　　　／　　　＼
　　　　　　　 x1 ○　　　　　○ x2
　「根付き木」 では、ルート r から頂点 x1, x2, y2 への道があり、y1 は この道のうえの頂点であるとき、y1 を x1, x2 の 「祖先」 であると云い、x1, x2 は y1 の 「子孫」 であると云います。そして、特に、y1, x1 （および、y1, x2） が 「辺」 であれば、y1 を x1 （および、x2） の 「親」 と云い、x1 （および x2） を 「子」 と云います。

　「子」 を持たない頂点を 「葉 （leaf）」 と云います──この例では、x1, x2 および y2 が 「葉」 です。

　「木」 では、「子」 のあいだには、「関係」 が定められていないのですが、「子」 のあいだに 「並び」 が定められている 「木」 を 「順序木 （ordered tree）」 と云います。「木」 と云えば、ふつう──特に断りがなければ──「根付き順序木」 を指します （下図参照）。


　　　　　　　　　　　　　　r ○
　　　　　　　　　　　　　　／　＼
　　　　　　　　　　　　　／　　　＼
　　　　　　　　　　 y1 ○─────○ y2
　　　　　　　　　　　／　＼
　　　　　　　　　　／　　　＼
　　　　　　　 x1 ○─────○ x2
　さて、「根付き順序木」 において、検索の基本法には、以下の 2つが考えられます。

　（1） DFS （Depth First Search）
　（2） BFS （Breadth First Search）

　DFS は、「階」 関係の道を辿る やりかた で──たとえば、(r, y1) (y1, x1) (y1, x2) (r, y2) ──、BFS は 「次数」 の道を辿る やりかた です──たとえば、(y1, y2) (x1, x2)。

　「木」 を indexing として使ったときに弱点となるのが、「たぐる」 「揺らぐ」 という点です。この弱点を本編 （実践編-14） で述べています。そして、RDB プロダクト に搭載された indexing （CRATED INDEX） は、セット・アット・ア・タイム 法と無関係であることを本編で指摘しておきました。 □

　



[ 補遺 ] （2018年10月 1日）

　セット・アット・ア・タイム 法と indexing は無関係です （セット・アット・ア・タイム 法には indexing は無用です）。プロダクト としての RDB が indexing を搭載しているのは、それぞれの RDB ベンダー の都合にすぎない。当初 RDB は、（マシーン・パワー が弱かったので） セット・アット・ア・タイム 法では パフォーマンス が悪かった。悪い パフォーマンス を補うために、RDB ベンダー は indexing を搭載してきたというのが歴史的事実です。

　E. F. Codd 氏が提唱した セット・アット・ア・タイム 法に対して最初に反論した人物が Bill Inmon 氏です。Bill Inmon 氏は、定型業務・多量 データ・多量 トランザクション （たとえば、生産管理 システム） に対して セット・アット・ア・タイム 法を使う有用性はないと反論していました。Bill Inmon 氏が レコード・アット・ア・タイム 法の有力な データベース と考えていたのは MODEL204 です──MODEL204 は、inverted indexing を搭載した データベース です。私は、当時、米国の ADR 社で DATACOM/DB （inverted indexing を搭載した 「RDB 型」 データベース） を指導されていて、Bill Inmon 氏の論説に同意していました。Bill Inmon 氏の論説を読んだのは、今から 30数年前のことなので私の記憶が曖昧なのですが、彼の論説は ComputerWorld 紙あるいは DATAMATION 紙に記載されていたと思います。

　確かに、定型業務・多量 データ・多量 トランザクション には レコード・アット・ア・タイム 法のほうが セット・アット・ア・タイム 法に比べて、有用です。しかし、いっぽうで、レコード・アット・ア・タイム 法は indexing を外れた情報検索には対応しにくい。そのために、後々、Bill Inmon 氏は、「目的べつの ファイル」 を用意することを提唱しました──それが Data Mart です。そして、Data Mart を起点にして、Data Warehouse が論じられるようになった。いっぽうで、RDB は indexing を搭載するようになった。

　実は、私が INDEX-only を思い付く切っ掛けとなったのが、Bill Inmon 氏の論説と DATACOM/DB の indexing のひとつである Generic Search だったのです。すなわち、レコード・アット・ア・タイム 法を セット・アット・ア・タイム 法のように使えばいい、ということ。






　 << もどる HOME すすむ >>
　 目次にもどる