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

先月、私はFLOPSで有限関数型プログラミング、あるいは「λFS」についての講演を行いました。これは、関数型プログラミングとDatalogやSQLのような関係型プログラミング、そしてついでにテンソル代数も組み合わせようという私の最新の試みです（以前はDatafun）。λFSでは、関係Rは関数として扱われます。R(x) = true とは、xがRに含まれることを意味し、そうでなければfalseです。この関数は、R(x) = true となる入力xが有限個であるという意味で有限です。これらがそのサポートです。論文では、関数が有限サポートを持つことを保証するための型システムが提供されています。実行時には、有限ブール関数を、そのサポートをハッシュテーブルまたは平衡木（データベースのテーブルのような）に表形式で格納することによって表現します。これは、ブール値だけでなく、デフォルト値を持つ任意のコードメインに一般化できます。関数のサポートとは、出力がデフォルト値ではない入力のことです。例えば、falseをデフォルトとするブール値、あるいは0をデフォルトとする整数などです。有限関数は、キーが関数のサポートであるキー・バリューテーブルとして表現でき、それ以外のキーは暗黙的にデフォルト値にマッピングされます。非ブール値の有限マップは、集計の結果として自然に生じ、テンソル代数は、本質的に非ブール値（通常は実数値）の有限マップ上の関係代数です。 非終端性と評価順序 講演の中で、λFSにおける再帰は将来的な作業であると述べました。当然、誰か（アツシ・イガラシだったと思います）が、その難しさについて尋ねました。主な難しさは、再帰が非終端性を許容することです。非終端性の意味論は通常、近年流行から外れているドメイン理論を使用しますが、私はそれを深く学んだことがなく、少し威圧的に感じます。さらに、非終端性や何らかのエフェクトが関わるようになると、評価順序の問題が生じます。型のないラムダ計算でさえ、評価が共鳴する場合、コールバイネームとコールバイバリューの評価は異なるプログラムで終端します。さらに悪いことに、関係言語では「評価順序」は関数型言語よりも広範な意味を持ちます。この例を考えてみましょう。R,S : nat => bool を入力テーブルとし、test : nat -> bool をブラックボックス述語とします。Q(x) := R(x) かつ test(x) かつ 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を共通部分化すると、test("hello")のみをテストするため、終端します。私はこの問題をλFSで表現しましたが、これはユーザー定義関数をサポートする任意のSQLまたはDatalogエンジンで発生し、典型的なDBとPLの仮定の間の緊張関係を露呈させます。DB: クエリエンジンはパフォーマンスを最適化するために実行戦略を選択する場合があります。PL: プログラムの振る舞い、特に終端性や実行時間について構成的に推論できます。λFSはDBとPLの橋渡しをしようとしますが、厄介な中間地点で立ち往生します。私は一方の視点を他方に優先させるか、針の穴を通す方法を見つける必要があります。まだ最善の方法はわかりません。代わりに、再帰（または非終端関数を持つDatalog）を持つλFSのための可能なセマンティクスの3つのスケッチ、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)のような場合、ループではなくテストを生成します: for x in R: if x not in S: continue yield x 一部の変数がグラウンド化されているがすべてではない場合、インデックスが必要です。例えば、R(x,y) and S(y,z)を実行するには、yでSをインデックス付けしたいです: for x,y in R: for z in S_index[y]: -- 適切なS_indexを仮定して yield (x,y,z) これらのインデックスがあり、すべての連鎖が有限マップの適用である場合、コストモデルは単純です。プレフィックスの発火を数えます。つまり、連鎖の各プレフィックスについて、その自由変数の代入がそれを満たす回数を数えます。したがって、R(x,y) and S(y,z) の場合、次の合計を追加します。R(x,y)を満たすx,yタプルの数。R(x,y) and S(y,z)を満たすx,y,zタプルの数。test(x)のようなブラックボックス述語についてはどうでしょうか？そのような連鎖の場合: そのすべての引数は、先行する連鎖によってグラウンド化されている必要があります。そのため、それに到達したときには具体的な値があります。先行する連鎖の発火ごとに、test(x)を評価するコストを追加します。これは、総x値の数を超える場合があります。例えば、R(x) and S(y) and test(x) は、各xに対してtest(x)を1回呼び出します。これは、元の終端性に関する質問に直接答えます。先行する連鎖を満たす値に対してのみ述語を実行します。偶然ですが、左から右へのグラウンド化要件は、有限関数型プログラミング論文の型システムと正確に一致します。当初は型システムの弱点だと考えていましたが、左から右への実行戦略があれば、完全に理にかなっています。このアプローチのシンプルさと予測可能性を気に入っており、プログラマーにパフォーマンスの責任を負わせる（これは明らかに欠点でもありますが）という点で「弾丸を噛む」ことを評価しています。残念ながら、一部のクエリ（巡回クエリ）では、例えば三角形クエリ edge(x,y) and edge(y,z) and edge(x,z) のような、許容できるパフォーマンスを達成することが不可能になります。 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に対して終端する場合、クエリは終端します。test(x)が一部のx ∈ R ∩ Sで発散する場合、クエリは発散します。それ以外の場合は、どちらの方向にも進む可能性があります。しかし、すべての終端する実行は同じ結果をもたらすはずです。残念ながら、この非決定論を構成可能な方法で指定する方法はわかりません。セマンティクスには通常2つのアプローチがあります。