CatyのJSONストレージとクエリ言語

Catyのデータベースバックエンドの候補としてMongoDBを検討しています。MongoDBのクエリ言語が、現在Catyで実装しているクエリ言語とやたらに似ているんで笑ってしまいました。同じアイディアに基づき、構文もほとんど同じです。比較してみると -- 身贔屓な評価かもしれませんが -- Catyクエリ言語のほうがデキがいいと思います。

Catyでは、JSONデータを保存する貯蔵庫を「JSONストレージ」と身も蓋もない呼び方をしています。今まで紹介したことがなかったのですが、JSONストレージへのクエリ（問い合わせ）言語が存在します。JSONストレージとクエリ言語の設計と実装は、全部Kuwataさんによるものです。いつの間にか出来ていました。

現時点でのJSONストレージは、バックエンドにSQLiteを使っています。JSONデータ構造とRDB的なデータモデルにはセマンティックギャップがあるため、実装が煩雑になり、パフォーマンスやスケーラビリティに懸念があります。そこで、バックエンドを、CouchDBとかMongoDBのようなドキュメント指向データベースに置き換えたいのです。

バックエンドを置き換えても、現在のクエリ言語はそのまま使い続けるつもりです。このクエリ言語はとても使い勝手がいいし、高い整合性を持っています。クエリ言語の具体的な構文は少し風変わりです。ここでは、具体的な構文からは離れて、抽象的・論理的なレベルでクエリ言語を紹介します。（具体的な構文は何種類かあってもよいと思います。）

内容：

1. 準備をほんの少し
   1. ラムダ式のことをほんの少し
   2. JSONデータのことをほんの少し
2. 二項関係による条件
   1. 等号
   2. 数値の大小比較
   3. 文字列のマッチング
   4. 所属（型の判定）
3. 論理結合子
4. 配列の条件
5. オブジェクトの条件
6. ANYとUNDEFINED
7. 配列に関する全称命題と存在命題
8. まとめ

準備をほんの少し

ラムダ式のことをほんの少し

例えば、不等号の記号「≧」は、2変数で真偽値を返す関数と考えることができます。このことをハッキリと表すために、次のような書き方をします。

• λ(x, y).(x≧y)

λ（ラムダ）の直後に引数となる変数を並べ、ピリオドの後に変数を含む式を書くのです。（ラムダ式に関しては「JavaScriptで学ぶ・プログラマのためのラムダ計算」を参照。）不等号「≧」の右側を定数にしてしまうと、引数変数は1個になります。

• λ(x).(x≧10)

引数変数（ラムダで束縛された変数）が1個しかないラムダ式を、無名変数として「_」（アンダスコア）を使って次のように表すことにします。

• (_≧10)

これから先、アンダスコアを含む式は1変数のラムダ式であり、その値は真偽値（boolean value）であると約束します。

JSONデータのことをほんの少し

JSONデータは、スカラーデータまたは複合データです。スカラーデータと複合データには次の種類があります。

1. スカラー：数値型 number； 1, -2, 3.14 など
2. スカラー：文字列型 string； "hello", "", "檜山" など
3. スカラー：真偽値型 boolean； true, false
4. スカラー：ヌル型 null； null（リテラル）
5. 複合：配列型 array； [1, "hello"], [] など
6. 複合：オブジェクト型 object； {"x": 1, "y": -3.5, "color":"red"}, {} など

配列の成分を項目（item）と呼び、オブジェクトの成分をプロパティ（property）と呼びます。その他に、要素（element）、メンバ（member）、フィールド（field）、キー（key）などの言葉が使われることもあります。

ひとつのJSONストレージは、いくつかのJSONコレクション*1を含みます。コレクションは、JSONオブジェクトデータの集合です。

クエリ言語は、JSONデータに関する条件を記述するための言語です。記述された条件を満たすJSONデータがコレクションから抽出されます。別な言い方をすると、コレクションの部分集合を {x∈SomeCollection | ＜xに関する条件＞} と書きたいときに、＜xに関する条件＞を表現する言語がクエリ言語です。

二項関係による条件

二項関係は2つの変数を持ちますが、その片方を定数にして条件を定義できます。

等号

次は、等号を使った条件の例です。

1. (_ = 1)
2. (_ = -3.5)
3. (_ = "hello")
4. (_ = [1, 2, 3])
5. (_ = {"x": 1, "y":-3.5})

これ以上説明することはないです。

数値の大小比較

使える関係記号（比較演算子）は、＞、≧、＜、≦ の4つです。無名変数 _ に入る値は数値（number）に限ります。

1. (_ ＞ 0)
2. (_ ≧ 3.14)
3. (_ ＜ 256)
4. (_ ≦ -20)

これも、説明することがないです。

文字列のマッチング

マッチングの演算子として、=~ を使うことにします。=~ の右側には正規表現リテラルか、SQLのLIKEパターンが書けるとします。正規表現はスラッシュで囲み、LIKEパターンはシングルクォートで囲むことにします*2。無名変数 _ に入る値は文字列（string）に限ります。

1. (_ =~ /^h.*o$/)
2. (_ =~ 'h%o')
3. (_ =~ /^....$/)
4. (_ =~ '____')

所属（型の判定）

集合への所属を ∈ で表します。また、型の名前を集合の意味でも使います。x∈string は、「xは文字列の集合に所属する」または「xの型はstringである」を意味します。以下の例のintegerは、numberのなかで特に整数である型です。

1. (_ ∈ string)
2. (_ ∈ boolean)
3. (_ ∈ integer)

特別な型としてanyがあり、任意のJSONデータがanyに所属します。次の条件は常に真となります。

• (_ ∈ any)

論理結合子

論理結合子（logical connectives）は、お決まりの AND, OR, NOT の3つです。論理結合子は、基本的な条件から複雑な条件を組み立てる際に使えます。

1. (_ ≧ 0) AND (_ ≦ 10) …… 0以上10以下
2. NOT (_ ≧ 0) …… (_ ＜ 0) と同じ
3. (_ = true) OR (_ = false) …… (_ ∈ boolean) と同じ
4. (_ ∈ integer) AND (_ ＞ 0) AND (_ ≦ 2) …… (_ = 1) OR (_ = 2) と同じ
5. NOT ((_ = 0) OR (_ = "")) …… 0でもなく空文字列でもない

配列の条件

配列に関する条件は、項目に対する条件を並べて記述します。

• [(_ ≧ 0), (_ ∈ string)]

この例は、最初の項目が0以上の数値で、次の要素が文字列であることを示します。3番目以降（配列インデックスは2以上）の要素に関しては何の条件も課してません。次の配列インスタンスはこの条件を満たします。

1. [1, "hello"]
2. [3.14, "", true]
3. [0, "hello", "json", "strage", "query"]

最初の項目に何の条件も課さず、2番目だけに条件を付けたいときは次のようにします。

• [(_ ∈ any), (_ ∈ string)]

(_ ∈ any) は常に真なので、「何の条件も課さない」ときに使えます。

末尾に続く「その他の項目」に関する条件（繰り返し適用される）は、条件全体に「*」を付けます。

• [(_ ≧ 0), (_ ∈ string)*]

これは、最初の項目が0以上の数値で、2番目以降の項目があれば文字列であることを要求します。

オブジェクトの条件

プロパティに関する条件は、プロパティ値に関する条件の前にプロパティ名を付けるだけです。

• ＜プロパティ名＞ : ＜プロパティ値に関する条件＞

プロパティ名はダブルクォートされた文字列リテラルです。例えば、"age" : (_ ≧ 20) 。プロパティに関する条件を並べてブレイス（波括弧）で囲めばオブジェクトに関する条件です。

1. {"x" : (_ ≧ 0), "y" : (_ ≧ 0)} …… 第1象限の点
2. {"gender" : (_ = "M"), "age" : (_ ≧ 20)} …… 成人男子

「その他のプロパティ」に関する条件は、プロパティ名を「*」とします。

• {"x" : (_ = 0), * : (_ ≧ 0)} …… x座標は0、その他は負でない

ANYとUNDEFINED

(_ ∈ any) の略記としてANYを使います。ANYはこれだけで条件であり、どんなデータでもANY条件を満たします。
(_ ∈ undefined) の略記としてUNDEFINEDを使います。undefined型はJSONには存在しません。が、JavaScriptには undfined型があり、定義されてない配列項目／オブジェクトプロパティにアクセスするとundefined型の値が返ってきます。

ANY, UNDEFINEDは次のように使います。

1. [(_ ≧ 0), ANY, UNDEFINED]
2. {"age" : (_ ≧ 20), "maritalPartner" : UNDEFINED}
3. {"x" : (_ ∈ number), "y" : (_ ∈ number), * : UNDEFINED}

最初の例では、配列の3番目がUNDEFINDなので、この配列の長さが2であることを要求しています。第2項目（配列インデックスは1）は必須です。ANYにはundefined型が含まれてないのです。undefineでもよいと指定するなら、ANY OR UNDEFINED とします。

2番目の例は「成人で未婚」を意味します。ただし、配偶者（"maritalPartner"）のプロパティが存在しないときは未婚とみなすという前提があります。

3番目の例は、"x", "y" 以外のプロパティが出現しないことを要求しています。「*」がその他のプロパティを意味し、それがUNDEFINED、つまり存在しないことです。

＜条件＞ OR UNDEFINED はよく使うので、＜条件＞? と略記することにします。長さが1または2である配列は次の条件で記述できます。

• [ANY, ANY?, UNDEFINED]

配列に関する全称命題と存在命題

集合Sのすべての要素に対して命題Pが成立することを、∀x∈S.P(x) と書きます。集合Sの少なくとも1つの要素に対して命題Pが成立することを、∃x∈S.P(x) と書きます。集合の代わりに配列を使うことにして、同じ記号∀、∃を使って条件を記述することにしましょう。

∀＜条件＞ は、配列のすべての項目が＜条件＞を満たすことを表します。∃＜条件＞ は、配列の少なくとも1つの項目が＜条件＞を満たすことを表します。

1. ∀(_ ≧ 0) …… 配列のすべての項目が負でない数値
2. ∃(_ = 0) …… 配列の少なくとも1つの項目が0

論理結合子と組み合わせてみます。

1. ∀((_ ≧ 0) OR (_ = "unbounded")) …… 配列のすべての項目が「負でない数値か"unbounded"」
2. ∃(NOT (_ = 0)) …… 配列の少なくとも1つの項目が「0ではない」

まとめ

以上が、Catyクエリ言語の抽象的・論理的な構造です。

等号と、スカラーデータの領域上で定義された単項基本述語*3をもとにして、述語論理の論理演算（AND, OR, NOT, ∀, ∃）を使って組み立てた論理式の体系になっています。JSONの複合データ構成法である配列構成とオブジェクト構成にも対応しています。

これは、JSONインスタンスからなる集合を定義する論理式の言語となっており、与えられた集合（コレクション）を絞り込む目的に（つまりクエリ言語として）使えます。古典論理とデータ型に関する推論がそのまま素直に使える点がメリットだと思います。

*1:Catyではコレクションではなくテーブルと呼んでましたが、MongoDBの用語「コレクション」のほうがふさわしいと思うので、今後は「コレクション」にしようかと。

*2:LIKEパターンの場合、エスケープ文字が可変なのが困ったところです。

*3:基本述語が全域関数とは限りません。論理式に対するモデルは、一般に部分関数となります。