SQLアタマアカデミー

第6回 SQLで木構造を扱う~入れ子区間モデル (2)稠密性について

この記事を読むのに必要な時間:およそ 1 分

稠密性(ちょうみつせい)について

前回から見えるように,整数から有理数へ範囲を広げることの利点は非常に大きいのですが,その理由は,有理数が整数にはない稠密性(ちょうみつせい:density)という性質を持っていることにあります。あまり日常で使う言葉ではありませんが,直感的に言えば物がぎっしり詰まっているということです。もう少し数学的に厳密に書くと,

  • x<yを満たす任意の数x,yについて,x<m<yとなる数mが存在する

となります。平たく言えば,どんな2つの数の間(区間)にも,まだまだ無限に数がある,ということです。

ここでキーとなるのは「任意の」という言葉です。特定のx, yではなく,大小関係を満たすあらゆる数のペアについて成立することがキモです。たとえば,1と2の間には,0.5という数が存在します。今度は1と0.5の間で見ても,0.25というさらに中間の数が存在します。後は同じ手順で,1と0.25の間には0.125,1と0.125の間には0.0625…と無限に続けられます図7)⁠

図7 どんな2つの数の間にも無限に数が存在する

図7 どんな2つの数の間にも無限に数が存在する

すなわち稠密性とは,夢のようなリソース無限の原則なのです。私たちは,すぐに枯渇する整数の井戸とは違う,汲めども尽きぬ魔法の泉を手に入れてしまったのです注3)⁠

なおこれは余談ですが,上記の話からゼノンのパラドックスを想起した人もいるでしょう。⁠アキレスは絶対に亀に追いつけない」とか「飛ぶ矢は静止している」という,あれです。あの逆説の鍵もまた,⁠どれほど微小な区間にも無限の点が含まれている」という空間の稠密性を前提していることにありました。神速のアキレスといえども,無限の点を走破することはできない。よって,アキレスは亀に追いつけない,というわけです。

しかし,アキレスにとっては致命傷になったこの特性も,DBエンジニアにとっては天の恵みです。ありがたく利用させていただきましょう。

注3)
もちろん,無限なのはあくまで理論上の話で,実装上はシステムの有効桁数に制限されます。残念ながら,現実世界のリソースはつねに有限です。したがってノード追加を繰り返すと,いずれ整数のときと同じ資源の枯渇は起きます(そこまで巨大な木を現実にシステムで扱うことがあれば,ですが)⁠

COLUMN 整数から有理数への一般化の歴史

ここでちょっと歴史的な話をすると,この整数から有理数への一般化は,リレーショナルデータベースがよって立つ集合論のたどった道と似ています。

集合論の創始者カントールは,有名な対角線論法によって,さまざまな無限集合の大きさを比較する方法を示しました。そのとき彼は,最初に整数の集合からはじめ,その後に有理数や実数の集合へ拡張するという方法をとったのです。

入れ子区間モデルの源流の一つは,このカントールの仕事にあります(もう一つの源流は,後でお話しましょう)⁠

著者プロフィール

ミック

SI企業に勤務するDBエンジニア。主にデータウェアハウス業務に従事している。自身のサイト「リレーショナル・データベースの世界」でデータベースとSQLについての技術情報を公開している。『Web+DB Press』で「SQLアタマアカデミー」を連載中。

著書:『達人に学ぶ SQL徹底指南書』(翔泳社、2008)訳書:J.セルコ『SQLパズル 第2版』(翔泳社、2007)

SQLアタマアカデミー:サポートページ

コメント

  • 稠密 は「ちゅうみつ」と読みます。

    紹介いただいてから間が空きましたが読ませていただいております。

    Commented : #1  KAZAMAI_NaruTo (2013/05/03, 02:40)

コメントの記入