論文メモ What You Always Wanted to Know About Datalog
December 12, 2020論理型のデータベースのクエリ言語Datalogの構文、意味論、最適化が解説されている。 最適化の節はサーベイ論文の形式で、最適化を分類し、各種類の先行研究に案内がある。
Datalogの構文はPrologの構文のサブセットである一方で、両者の意味論は異なる。
Prologは、操作的意味論で定義され、深さ優先探索で節とリテラルを探索し、プログラムが停止することを保証しない。
例えば、次の左再帰を含むホーン節の場合、Prologだとsgc
の位置を変えないと評価できないが、Datalogであれば位置に関係なく評価できる。
r1 sgc(X, Y) :- sgc(X1, Y1), par(X, X1), par(Y, Y1)
r2 sgc(X, X) :- person(X)
最適化については、次の図のCRITERIONの通り6項目に分類され、先行研究の案内がある。
論文をこちらからダウンロードできます。