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

- 著者はMichael Arntzenius（通称rntz）、データベース理論とプログラミング言語の研究者。Datalogは論理プログラミング言語Prologのサブセットで、再帰クエリを宣言的に書ける。 - Datalogは伝統的に「ボトムアップ評価（固定点計算）」され、停止性が保証される（Datalog自体はチューリング完全ではない）が、任意の関数を組み合わせた「Datalog^¬」など拡張系では非停止が起きうる。 - 記事は、クエリ言語において「評価順序（戦略）」が非停止性にどう影響するかを、Datalogとその周辺言語（SQLの再帰CTEなど）を題材に解析。SQLの実装ごとに再帰のセマンティクスが異なり、停止性が保証されないケースがある背景を理解するのに有用。 - Datalogは知識グラフや静的解析ツールで近年再注目されているため、評価戦略の理論的整理は実用的にも重要。