このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

NoSQLデータベースのメリット・デメリットを考えてみる(やや圏論風)

「NoSQLデータベース」の意味は広範で曖昧です。僕が想定しているのは主にMongoDBです。その前提でお読みください。

データベースの構成要素を、「コレクション」「レコード」「フィールド」と呼ぶことにします。MongoDBでは、「レコード」ではなくて「ドキュメント」と言いますが、普通の意味の「文書」と混同されるのがイヤなので「レコード」にします。レコードは入れ子構造を許す(かも知れない)ので、フィールドの識別にはフィールド名ではなくてフィールドパスが必要です。

次の2点はNoSQLデータベースの弱点としてよく指摘されることです。

  1. トランザクションが出来ない。
  2. ジョインが出来ない。

これら(特にジョイン)について分析し、あまり指摘されないNoSQLデータベースのメリットにも触れます。

内容:

  1. トランザクション:多くを望まない
  2. RDBのジョインとデカルト的能力
  3. 部分関数と集合値関数
  4. 部分関数と集合値関数を使ったジョインもどき
  5. コレクションのユニオン
  6. 射影と埋め込み(projection-embedding)
  7. まとめ

トランザクション:多くを望まない

NoSQLデータベースでも、単一レコードへのアトミックな操作はたいていサポートされています。また、「比較してから変更する」(Compare and Swap)を割り込み無しで実行できることも多いので、単一レコードに関して整合性を維持しながら更新することは可能でしょう。

「比較してから変更する」が出来るなら、クライアント主導でトランザクション処理を行うことは可能です。これについては、最近書いた次の2つの記事を参照してください。

  1. トランザクションの3つの方式
  2. 楽観的並行性制御

これで、単一レコードの整合性を守ることは出来ますが、複数レコードにまたがる整合性の維持は困難です。MongoDBには$atomicオプションなんてのがありますが、これもロールバックはされないので、あてにはできません。

複数レコードにまたがる整合性が必要だったり、単一レコードであってもロックとロールバックで処理したいときは、NoSQLでは無理があります。要するに向いてないのです。トランザクションへの強い要求があるときは、他の道具と手段を考えたほうがいいでしょう。

RDBのジョインとデカルト的能力

SとTがRDBのテーブルだとします。SとTはレコード(ロー)の集合だと解釈しましょう。ジョインとは、直積集合 S×T を作って、適当な条件で絞り込んだ結果です。pを二項の述語(真偽値を値とする二引数の関数)だとして、ジョインJ(の集合)は次のように書けます。

  • J = {(s, t)∈S×T | p(s, t) }

二項の述語 p(s, t) として最もよく使われるのは、フィールド(カラム)値の等式です。「レコードsのフィールドfの値」を s.f と書くことにすると、s.f = t.g のような等式ですね。この場合のJは:

  • J = {(s, t)∈S×T | s.f = t.g }

この形のジョインは等値ジョインと呼ばれることがあります。レコードsのフィールドfの値は、f(s) と書いても同じことです。フィールド値参照は関数とみなせるのです。そうすると:

  • J = {(s, t)∈S×T | f(s) = g(t) }

フィールドfとgの値の領域(RDB用語の「ドメイン」)をAとすると、f:S→A、g:T→A という関数ですが、f'(s, t) = f(s)、g'(s, t) = g(t) とすれば、f', g':S×T→A とみなせます。

一般に、u, v:X→Y という2つの関数による等式(方程式) u(x) = v(x) の解集合を Eq(u, v) と書くことにすると、等値ジョインJは、J = Eq(f', g') と書けます。圏論をご存知のかたは、これが集合圏における等値核(イコライザーの定義であると分かるでしょう。最初に直積をとっているので、全体としてはプルバック(ファイバー積)です。

等値ジョイン(圏的にはプルバック)が構成出来ることは、直積と等値核が作れることと同値です*1圏論では、このような操作が出来る能力をデカルト(cartesian)という形容詞で表します*2。つまり、RDB(SQLDB)は、集合圏におけるデカルト的能力を具現しているのです。

部分関数と集合値関数

NoSQLデータベースは、デカルト的能力を十分には持ちません。RDBのように、直積や等値ジョイン(プルバック、ファイバー積)を自由自在には作れない、ということです。しかし、そこそこの実用性を持ったジョインもどきなら作れます。それを説明するために、まずは部分関数と集合値関数について述べます。

通常、関数(または写像) f:A→B と言った場合、次が仮定されます。

  1. 集合Aのどんな要素aに対しても、f(a) が一意に決まっている。
  2. 値 f(a) は、集合Bの(単一の)要素である。

一番目の条件を次のようにゆるめると部分関数の定義になります。

  • 集合Aの要素aで、f(a) が決まってないものがあってもよい。

もう少し正確に言うと、集合Aの部分集合Dがあって、fは D→B という(普通の意味の)関数になっていることです。Dの外でfは未定義です。fに対するDを、Def(f) と書くことにします。Def(f)⊆A で、a∈Def(f) ⇔ (f(a) が決まっている) です。

二番目の条件を次のようにゆるめると集合値関数の定義になります。

  • 値 f(a) は、集合Bの部分集合である。

つまり、f(a)⊆B となります。f(a) として単元集合か空集合だけを許すと、それは実質的に部分関数と同じことになります。複数の要素を含む集合が値の時は、「値が複数ある」とも言えるので多値関数とも言います。ただし、「多値」の意味は色々あるようですが。

モナドをご存知のかたには、部分関数は集合圏上の付点モナド(Myabeモナド)のクライスリ射、集合値関数は共変ベキ集合モナドのクライスリ射であることを注意しておきます。さらに、共変ベキ集合モナドのクライスリ圏は、関係の圏Relと圏同値となることも重要な事実です。

部分関数と集合値関数を使ったジョインもどき

これから述べるジョインもどきは、RDBの外部ジョインと少し似ています。関係のグラフ(関係そのものとも言える)や依存積(dependent product)と呼ばれる集合の構成法とも関連します。この構成では、直積やファイバー積のような対称性は持ちません。2つの集合(コレクション)のどちらか一方が主役となります。

f:A→B を部分関数とします。f(a)が未定義のとき、特殊な値⊥(ボトム)を使って f(a) = ⊥ としておきます。これは、部分関数と付点集合(pointed set)圏の射を対応付けたものです。部分関数 f:A→B は、A→(B + {⊥}) という普通の関数ともみなせるわけです。B + {⊥} を B と略記することにします。

さて、部分関数fを使ったAとBのジョインもどき A×fB を次のように定義します。

  • fB = {(a, b)∈A×B | b = f(a) }

例えば、A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} で、Bは整数全体、fを「3で割った整数商、割り切れないときは未定義」とします。すると、A×fB は次の集合になります。

  • {(1,⊥), (2,⊥), (3,1), (4,⊥), (5,⊥), (6,2), (7,⊥), (8,⊥), (9,3), (10,⊥)}

fB を作る際に、Bが巨大な集合でもそれは問題になりません。必要なことはAの全ての要素をスキャンすることです。Aがあまり大きくなくて、a∈A に対して f(a) を求めること(参照、あるいは計算)がさほどの負担でないなら、A×fB の構成は許容できるコスト内で可能な場合が多いでしょう。

fB のなかでペア(二項タプル)の右側が⊥であるものをふるい落とすと、形式上は等値ジョインになります。ただし、方程式の解集合というよりは、「参照をたどってかき集めた結果」というオモムキの集合です。RDBジョインの宣言的な特性が弱まり、処理方式と方向性が意識された構成法になります。

F:f:A→B が集合値関数(Fは、A→Pow(B) という普通の関数と同値)のときも同様で、

  • FB = {(a, b)∈A×B | b ∈ F(a) }

と定義されます。A = {0, 1, 2, 3, 4} で、Bは整数全体、F(a)を「aの約数の集合」とすれば、

  • FB = {(1,1), (2,1), (2,2), (3,1), (3,3), (4,1), (4,2), (4,4)}

これは、p(a, b) ≡ (b∈F(a)) という述語に関して、RDBのジョイン操作と事実上同じことをアプリケーションによる計算で行うことになります。計算のコストで考えると、aに対する F(a) を求めるのが大変だと A×FB の構成は困難になります。実際的には、“軽いF”が望ましいことになり、“重いF”では実用にならないでしょう。

部分関数fや集合値関数F(より一般にモナドのクライスリ射)の選び方に依存しますが、fやFが“軽い”場合は、上記の A×fB、A×FB (と、これらの変種)は、NoSQLデータベースでも実行可能なジョイン的操作と言えると思います。

コレクションのユニオン

RDB(SQLDB)では、2つのテーブルSとTのユニオン(合併)は制限がきつくて、実行できるケースは稀です。しかし、スキーマレスのNoSQLデータベースでは、コレクションの合併にほとんど制限がありません。2つのコレクションのユニオンを物理的に生成するにはコストがかかりますが、論理的なユニオン(ビューとしのてユニオン)の実現は容易です。

圏論的には、ユニオン(直和)はジョイン(直積)の双対です。RDBは直積が自由に作れてデカルト的能力を持ちましたが、そのRDBが苦手とするユニオンをNoSQLデータベースでは自由に作れます。デカルト的の双対であるデカルト能力をNoSQLデータベースは持つと言えるでしょう。

コレクションへの分割が、何らかのセマンティックな分類によりされているとすると、ユニオンを作ることは、異なる種類のデータを混ぜてしまうことなので、違和感があることもあります。しかし、「分類が細かすぎた」とか、「分類は無意味だった」という事態もあるので、ユニオンが自由に作れることはNoSQLデータベースのメリットの一つに数えてよいことです(「多品種少量データとMongoDB」も参照)。

射影と埋め込み(projection-embedding)

RDBのSELECT文では射影という概念があります。レコードの一部分を取り出すことです。射影によって得られた元レコードの一部分をサブレコードと呼ぶことにします。コレクション全体に射影をほどこすと、サブレコードの集合が得られます。

逆に、サブレコードが与えられたとき、そのサブレコードに対応するフルレコードを自然に作れるでしょうか? 例えば、{従業員ID, 姓, 名, 生年月日, 所属部署} というフィールド群を持つレコードのサブレコードが {従業員ID, 名, 生年月日} として与えられたとき、これを“補完”することができるか? ということです。

サブレコードに対する自然な補完が存在するとき、その補完方法は、サブレコードの集合をフルレコードの集合に埋め込む写像を与えます。埋め込み写像(embedding)は、射影写像(projection)と対(EPペア)になるものです。EPペアは、圏的領域理論(categorical domain theory)でも使われている概念です。

埋め込みの構成可能性は、SQLであるかNoSQLであるかで決まる問題ではありません。しかし、未定義なフィールドや空配列を持つフィールドなどを安直に許容するNoSQLデータベースでは、相対的に「埋め込みが構成しやすい」とは言えます。EPペアが構成できると、部分と全体のあいだを行ったり来たりしたり、不完全なデータを取り扱う操作が楽になります。

不完全なデータ/部分情報を扱う場合は、NoSQLデータベースの「埋め込みが構成しやすい」という特性を活かせるでしょう。

まとめ

  1. レコード単位の整合性の維持はNoSQLデータベースでも可能である(ことが多い)。
  2. クライアント主導の、単一レコードに対するトランザクションも可能であることが多い。
  3. それ以上のトランザクション処理は期待すべきではない。
  4. 自由にジョインは作れない。
  5. 部分関数f、集合値関数Fに対する A×fB と A×FB はジョイン的操作であり、実用的に使えることがある。
  6. コレクションのユニオンが制限なしに使えることは、NoSQLデータベースのメリットである。
  7. 射影と対になる埋め込みの構成しやすさは、不完全なデータ/部分情報を扱う場合はメリットとなる。

*1:終対象の存在を仮定しますが、ダミーの単一レコードが入ったテーブルを固定するだけのことです。

*2:有限完備とも言います。