論文メモ What You Always Wanted to Know About Datalog

論理型のデータベースのクエリ言語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項目に分類され、先行研究の案内がある。

---

論文をこちらからダウンロードできます。