同値関係のユースケースを考える

「数理をソフトウェア開発に応用する話」は、どちらを出発点とするかによってアプローチが2つある。つまり「開発上の課題から出発して、それを解決する手段として数理にたどり着く」のか「数理から出発して、それを適用可能なソフトウェア開発上の課題にたどり着く」のかである。本記事は、前者のアプローチである。

さて。

プログラミングでデータを永続化したいとき、何らかのデータベースを使う。
その際に「同じデータは一つ」に「異なるデータは別々」になるよう、うまくキーを定義したくなる。

住所録や家計簿のような「情報を入力された時点で定型化されるようなデータ」なら特に難しいことを考えなくても大抵は自然にキーが決まる。しかし非定型データ、例えば「Webから集めたデータ」や「何らかのログ」のようなデータの場合、「同一性をうまく捉える」ことは結構難しかったりする。

例えばURIでは、最後に'/'をつけるかどうかや、複数のCGIパラメータの順番(&で結ぶ順番)は不定なので、同一性を捉える何らかの仕組みが必要になる。そこで検索エンジンの実装では、「正規化URL」「カノニカルURL」といった「いったん共通フォーマットに揃えておく」ような方法が使われていたりする。そのようにリソースの識別キーに不定性があるときに「形式(=正規形)を一つ定義してその形式に揃える」ことで不定性を消す方法はURI以外にも適用できるのでしばしば使われ、プログラミングでは「正規化」と呼ばれることが多い。

正規化は一つの方法だが「不定性の全パターンが予め分かっている」ときでないと使えないという欠点もある。パターンを網羅できていないと正規形を定義しようにも定義のしようが無いからだ。例えば、住所。ハイフンやスペース、全角英数字、アパートの部屋番号といった「典型的なパターン」を想定して正規形を作っておいたものの「大字(おおあざ)の有無」みたいな新たな不定性が発覚してデータが重複してしまった、みたいなケースはいかにもありえそうだ。

そういう、「全パターンを予め想定しておけないデータ」において「同一性を捉える」にはどうしたらよいだろうか。数学をうまく応用したくなるところだ。よくあるのは「全体の構造を決定づけ」てしまうような「2者間の関係(=二項関係)」をうまく見つけ、その関係を出発点として構造をあれこれしらべるというものだ。例えば、「同値関係」。同値関係が決まるとグループ分けができるので、各グループの代表者を決めておき、どのグループの代表者と同値関係が成り立つかで所属グループを決めればよい。またこのグループの代表者というのはグループ内のどれでもいいので、全グループについて予め代表データを決めておかなくても、所属グループがないときに新たなグループの代表データとして登録するようにすればよい。つまり「各グループの一番乗りのデータと同値関係を比較する」というやり方で「同一性を捉える」ことができる。

ここまで、本記事ではプログラミングにおいて同値関係を応用したくなるケースについて考えてみたが、二項関係としてもう一つ代表的なものに、「順序関係」がある。順序関係を応用したくなるケースについては、後日また考えてみたいと思う。