HN 日本語サマリー

← 一覧へ戻る
プログラミング

クエリ言語における評価順序と非終端性

Evaluation order and nontermination in query languages (rntz.net)

35 pointsby luu3 コメント

要約

本稿では、関数型プログラミングと関係型プログラミングを組み合わせたλFSという新しい試みにおける、再帰による非終端性の問題と評価順序の重要性について論じます。特に、ユーザー定義関数を含むSQLやDatalogエンジンにおいて、評価順序がプログラムの終端性に影響を与える可能性があり、データベースの最適化とプログラミング言語の構成的推論の間の緊張関係が生じることを指摘しています。この問題に対処するため、左から右への評価順序、非決定論的な評価順序、そして再帰と非終端関数を扱うための新しいセマンティクスの3つの方向性が提案されています。

全文翻訳

クエリ言語における評価順序と非終端性

2026年6月

先月、私はFLOPSで、関数型プログラミングとDatalogやSQLのような関係型プログラミング、さらにはテンソル代数も組み合わせた私の最新の試みである「有限関数型プログラミング」(λFS)について講演しました。

λFSでは、関係Rを関数として扱います。R(x) = true とは x が R に含まれることを意味し、それ以外の場合は false とします。この関数は、R(x) = true となる入力 x が有限個である「有限」な関数です。これらの有限個の入力がその「サポート」となります。論文では、関数が有限サポートを持つことを保証する型システムが提案されています。実行時には、有限ブール関数を、そのサポートをハッシュテーブルや平衡木(データベースのテーブルのようなもの)に格納して表現します。

これは、ブール値以外にも「デフォルト値」を持つ任意の余域に一般化できます。関数のサポートとは、出力がデフォルト値でない入力の集合です。例えば、falseをデフォルトとするブール値、あるいは0をデフォルトとする整数などです。有限関数は、そのサポートをキーとするキー・バリューテーブルとして表現でき、それ以外のキーは暗黙的にデフォルト値にマッピングされます。非ブール値の有限マップは、集計の結果として自然に現れます。テンソル代数は、本質的に非ブール値(通常は実数値)の有限マップ上の関係代数です。

非終端性と評価順序

講演の中で、λFSにおける再帰は今後の課題であると述べました。当然、誰かが(アツシ・イガラシだったと思いますが)その難しさについて尋ねました。主な難しさは、再帰が非終端性を許容することです。非終端性の意味論は通常、近年流行から外れている圏論(domain theory)を使用しますが、私はそれを深く学んだことがなく、少し威圧的に感じます。1

さらに、非終端性や何らかの効果が関わる場合、評価順序の問題が生じます。型なしラムダ計算でさえ、評価は合流的ですが、名前渡し評価と値渡し評価は異なるプログラムで終端します。さらに悪いことに、関係言語では「評価順序」は関数型言語よりも広範な意味を持ちます。例を見てみましょう。入力テーブル R(x) と S(x)、およびブラックボックス述語 test(x)(任意のブール値関数)が与えられた場合、クエリ Q を次のように定義します。

Q(x) := R(x) and test(x) and S(x)

したがって、Q は R と S の共通部分を test でフィルタリングしたものです。中心的な問いは、「このクエリをどの順序で評価するか?」ということです。左から右へ進むことができます。R の各 x について、test(x) が成功すれば、x が S に含まれるかチェックします。Pythonでは次のようになります。

[x for x in R if test(x) if x in S]

あるいは、test は高価かもしれませんが、テーブルの検索は安価であることを考慮すると、test を呼び出す前に x が S に含まれるかチェックすることもできます。

[x for x in R if x in S if test(x)]

そして、もし S が R よりはるかに小さいことがわかっているなら、R を反復するよりも S を反復することで多くの時間を節約できます。

[x for x in S if x in R if test(x)]

標準的な関係型哲学では、評価順序はクエリプランナーによって決定される実装の詳細と見なされます。しかし、この順序は Q が終端するかどうかに影響を与える可能性があります。なぜなら、異なる順序は異なる引数で test を呼び出すからです。こじつけの例ですが、次のようになります。

R := {"hello", "world"}
S := {"hello", "alice"}
test(x) := x == "hello" or loop-forever()
Q(x) := R(x) and test(x) and S(x)

左から右への実行では、test("hello") が呼び出され、成功し、次に test("world") が呼び出されて無限ループに入ります。しかし、test を呼び出す前に R と S を共通部分にすれば、"hello" だけをテストするため、終端します。

私はこの問題をλFSで表現しましたが、これはユーザー定義関数をサポートするSQLまたはDatalogエンジンでも発生し、典型的なDBとPLの仮定の間の緊張関係を露呈します。

DB クエリエンジンはパフォーマンスを最適化するために実行戦略を選択する場合があります。

PL プログラムの動作、特に終端や実行時間について、構成的に推論できます。

λFSはDBとPLの橋渡しをしようとして、中途半端な位置にいます。私は一方の視点を他方に優先させるか、あるいは針の穴を通すような方法を見つけなければなりません。まだどうするのが最善かはわかりません。代わりに、λFSに再帰(または非終端関数を持つDatalog)を追加するための3つの方向性、つまり可能な意味論のスケッチを以下に示します。

1 左から右への評価は単純なコストモデルを持つ

実装が最も単純な戦略は、最も直接的な意味論を持ちます。左から右へ評価します。これは最も典型的なPLアプローチであり、クエリプランニングを回避し、ジョブを完全にプログラマに任せます。これにより、クエリの実行時間を予測し、推論しやすくなります。友人のRob Simmonsが、Finite Choice Logic Programmingに取り組んでいる際に指摘してくれたことです。これは、Dusa(FCLPの実装)のコストモデルとほぼ同じです。

このアプローチでは、n 個の項の連言は最大 n 個のネストしたループに変換されます。例えば、R(x) and S(y) は2つのループになります。

for x in R:
    for y in S:
        yield (x,y)

R(x) and S(x) のようなクエリで、S(x) の変数がすべてグラウンド化されている場合、ループではなくテストを生成します。

for x in R:
    if x not in S: continue
    yield x

一部の変数はグラウンド化されているがすべてではない場合、インデックスが必要です。例えば、R(x,y) and S(y,z) を実行するには、S を y でインデックス付けしたいと考えます。

for x,y in R:
    for z in S_index[y]: -- 適切なS_indexを仮定
        yield (x,y,z)

これらのインデックスがあり、すべての連言が有限マップの適用である場合、コストモデルは単純です。プレフィックスの発火回数を数えます。つまり、連言の各プレフィックスについて、その自由変数の代入のうちいくつがそれを満たすかを数えます。したがって、R(x,y) and S(y,z) の場合、次の合計を追加します。

  1. R(x,y) を満たす x,y タプルの数。
  2. R(x,y) and S(y,z) を満たす x,y,z タプルの数。

ブラックボックス述語 test(x) のようなものについてはどうでしょうか?そのような連言の場合:

  1. そのすべての引数は、先行する連言によってグラウンド化されている必要があります。これにより、それに到達したときに具体的な値が得られます。
  2. 先行する連言の発火ごとに test(x) を評価するコストを追加します。これは、総 x 値の数を超える可能性があります。例えば、R(x) and S(y) and test(x) は、各 x,y ペアに対して test(x) を呼び出します。

これにより、元の質問である終端性について直接的に答えることができます。述語は、先行する連言を満たすまさにその値に対して実行されます。偶然ですが、左から右へのグラウンド化要件は、有限関数型プログラミング論文の型システムと正確に一致します。私は当初これを型システムの弱点と考えていましたが、左から右への実行戦略があれば、完全に理にかなっています。

このアプローチの単純さと予測可能性を気に入っています。また、プログラマにパフォーマンスの責任を負わせる(これも明らかに欠点ですが)という「覚悟を決める」点も評価しています。残念ながら、一部のクエリ(巡回クエリ)では、許容できるパフォーマンスを達成することが不可能になります。例えば、三角形クエリ edge(x,y) and edge(y,z) and edge(x,z) です。2

2 非決定論的な評価順序は宣言的な最適化を可能にする

R(x) and test(x) and S(x) のための3つのもっともらしい評価順序を見てきました。なぜ不必要にコミットする必要があるのでしょうか?典型的なDBアプローチは、評価順序を指定しないことで、クエリプランナー/オプティマイザーに最大限の裁量を与えることです。これは、test をどの値で呼び出すかを正確に言うことはできませんが、その集合を上下から境界づけることができます。同様に、プログラムの終端は、はい/いいえの質問から、はい/いいえ/かもしれない、へと移行します。

進行中の例 R(x) and test(x) and S(x) に戻ると、x の値なしでは test を呼び出すことはできません。私たちが持っている唯一の情報源は R と S です。したがって、どのクエリ実行も、最大で R または S のいずれかの値で test を呼び出し、少なくとも 両方に含まれる値で呼び出します。もし test(x) がすべての x ∈ R ∪ S に対して終端するなら、私たちのクエリは終端します。もし x ∈ R ∩ S の一部に対して発散するなら、私たちのクエリは発散します。そうでなければ、どちらの方向にも進む可能性があります。しかし、すべての終端する実行は同じ結果を与えるはずです。

残念ながら、この非決定性を構成可能な方法で指定する方法がわかりません。意味論には通常、操作的意味論と指示的意味論の2つのアプローチがあります。

操作的には、ボトムアップ論理プログラミングに対応する意味論を、ましてや評価順序の変動を捉えるものをどのように与えるべきか確信が持てません。特にλFSでは、有限λはどのように評価されるのでしょうか?通常のプロシージャルλは、引数に適用されてから還元されるまで待ちますが、有限関数のポイントは、それらがそうしないことです。それらはデータベースクエリのように意欲的にテーブル化されます。しかし、この動作を小さなステップの操作的意味論で捉えることは明らかではありません。(Datafunには操作的意味論がありますが、それは左から右への評価にコミットするモナド内包表記を使用しているためです。まさに私が避けたいことです!)

指示的には、自然な前進は、有限関数型プログラミング論文の指示的意味論の概要に、圏論と何らかの形式の非決定性を追加することでしょう。残念ながら、非決定性の圏論(べき集合論)にまだ十分に精通していないため、これがどのように機能するかはわかりません。

もし、適切なアプローチを知っていると思われる方、または一緒にこの問題に取り組みたい方がいれば、私にメールしてください(qnrxunery@tznvy.pbz、rot13)。

3 「並列AND」は最も宣言的な振る舞いを持つ

すべてを手に入れることはできないでしょうか?これまでのところ、test(x) を実行してそれが発散した場合、クエリも発散すると仮定してきました。だからこそ評価順序が重要なのです。それは test を呼び出す x に影響します。少し逐次的に考えるのをやめれば、この仮定を捨てることができます。

⊥ を発散とします。and の典型的な実装は逐次的であり、まず左側の引数を調べ、false を返した場合はショートサーキットします。

false and x = false       -- ショートサーキット; xを評価しない
true  and x = x
⊥     and x = ⊥           -- xを評価する段階に至らない。

これは醜いです。論理的連言は対称ですが、この and は左バイアスです。対称性を維持しつつ連続性を保ちましょう。

false and x     = false   -- xをさらに評価する必要はない
true  and x     = x
x     and false = false   -- xをさらに評価する必要はない
x     and true  = x

Plotkinの並列ORにちなんで、これを「並列AND」と呼びます。3 逐次的な and は常に左側の引数を完全に評価しますが、並列的な and は両方の引数を同時に評価し、どちらかが false を返すか両方が true を返したときに終了します。これはλFSに奇跡的に決定論を回復させます。前の例を考えてみましょう。

R := {"hello", "world"}
S := {"hello", "alice"}
test x := (x == "hello") or loop-forever()
Q(x) := R(x) and test(x) and S(x)

左から右への実行では、test("world") and S("world") = ⊥ and false が評価されます。逐次的な and ではこれは発散しますが、並列的な and では単に false です。R を先に反復しても、S を先に反復しても、あるいはそれらの共通部分を反復しても、直感的に正しい同じ答えが得られます:Q = {"hello"}。

残念ながら、並列 and を効率的に実装する方法は明らかではありません。しかし、不可能ではありません。miniKanrenの検索戦略は、例えば並列ORの実装に似ています。また、Will Byrdから、Andorra Prologが並列ANDに類似した連言の形式をサポートしていたと聞きました。私自身、worst-case optimal joinsの実装のためのイテレータインターフェースを使用した公平な連言に関するminiKanren 2025の論文を発表しました。したがって、この問題は解決可能だと推測します。しかし、それだけの価値はあるでしょうか?4

フッター

  1. さらに複雑なことに、再帰には2つの異なる種類があります。(a) 再帰的な関数。これらは遅延評価されます。関数本体は、関数適用によって必要とされるまで評価されません。(b) 再帰的な関係(λFSでは有限関数)。これらはボトムアップ関係プログラミングでは、不動点への反復によって意欲的に計算されます(空の関係から開始し、定義が安定するまで繰り返し適用します)。しかし、後者は前者に基づいて定義できる可能性があります。再帰は反復を定義するのに十分です。 ↩

  2. 具体的には、edge = {(1, x) : x ∈
    [1..n]} ∪ {(x, 1) : x ∈
    [1..n]} とします。この場合、三角形(クエリの回答)は、x, y, z のうち少なくとも2つが1であり、残りが
    [1..n] のいずれかであるようなトリプルです。したがって、その数は 3n − 2 ∈ Θ(n) です。しかし、プレフィックス edge(x,y) and edge(y,z) を満たすトリプルは Θ(n2) 個あります。したがって、左から右への評価は、線形結果を見つけるために二次的な作業を行います。より一般的に、左から右への評価は左深二分結合プランに対応し、巡回クエリの場合、二分結合プランは漸近的に非効率になる可能性があることが知られています。巡回クエリには最悪ケース最適結合が必要です。 ↩

  3. 「並列OR」はGordon PlotkinのLCF Considered as a Programming Language(1977年)に由来すると考えられますが、これらの講義ノートの方がより分かりやすい入門書だと思います。p64、§8.1、「Failure of full abstraction」を参照してください。 ↩

  4. Meven Lennon-Bertrandとのこのマストドンでの議論も参照してください。彼は、ブール値に対する並列OR/ANDと、公平な論理プログラミングの論理和/連言との間の私の類推の妥当性に、非常に合理的に疑問を呈しています。 ↩