Summary:
Datalogは,有限の関係データベースに対する問い合わせや推論を表現するために設計されたものであり,事実集合と導出規則を用いて論理的に導かれる結論を記述する構文と意味論を持つ.
Datalogのプログラムは,事実[ファクト]とルールから構成され,ユーザはデータに対して「何を問うか」を宣言的に記述する.命令的な手続きの指定を避け,問い合わせ結果は論理的推論によって自動的に導かれるため,リレーショナルデータベースとの親和性が高い.関数記号を排除することにより,Datalogにおけるすべての問い合わせは有限の結果集合に収束する性質を持ち,計算可能性と決定性が保証される.
Datalogの技術的特徴は,Horn節によって表されるルール構文と,再帰的な問い合わせの自然な表現力にある.各ルールは,ヘッドと呼ばれる導出されるべき事実と,ボディと呼ばれる既知の条件から成る.この形式は「もしボディの条件がすべて満たされれば,ヘッドが成立する」と解釈され,データベース上での事実の導出や問い合わせの評価に適用される.ボディ部では,正のリテラル[肯定的原子式]のみが許可され,否定は標準的なDatalogでは使用できない.ただし,層化意味論[Stratified Semantics]に基づく拡張版や,安定モデル意味論を採用するDatalogバリアントでは,制限付きで否定が導入される.再帰的ルールを用いることで,階層構造,経路探索,親子関係の多段階推論といった処理が容易に記述可能となる.たとえば,あるノードから別のノードへの到達可能性を示すパスの存在を問う再帰的問い合わせは,Datalogでは非常に簡潔に表現できるが,従来のSQLでは長らく困難であった.
実行時には,データベースに与えられた初期事実[拡張述語,EDB]とルールに従って,導出可能なすべての新たな事実[内包述語,IDB]が反復的に生成される.この推論処理は,最小固定点意味論に基づき,有限回の繰り返しによって安定状態に到達する.具体的な評価戦略としては,ボトムアップ評価が一般的に用いられ,セミナイーブ評価やマジックセット変換といった最適化技法により効率的な実行が実現される.これにより,Datalogプログラムは意味論的に明確であり,問い合わせの結果は常に一意に定まる.
構文的には,Datalogの項[term]は定数と変数のみで構成され,複合項や関数適用は許可されない.原子式は述語記号に項のタプルを適用した形で表現され,ルールは「ヘッド :- ボディ」の形式で記述される.変数は大文字で始まり,定数は小文字で始まるという慣例が一般的である.安全性条件として,ルールのヘッドに現れるすべての変数はボディ部にも現れなければならないという制約が課され,これにより有限性と計算可能性が保証される.
Datalogの起源は,1970年代末から1980年代初頭にかけての関係モデルと論理プログラミング研究の融合にある.当時,関係代数や関係論理に基づくデータベース理論が発展する一方で,Prologに代表される論理プログラミング言語が人工知能分野で注目されていた.Datalogはこの両者の橋渡しとして開発され,データベースへの論理的アプローチを可能にするモデルとして受け入れられた.特に重要な貢献者として,Jeffrey Ullman,Moshe Vardi,Georg Gottlob,Phokion Kolaitisなどの研究者が挙げられる.Datalogはリレーショナルデータベースの理論的解析,問い合わせ最適化,データ依存性の検証,推論エンジンの構築といった分野で広く研究され,理論的な枠組みの中で再帰処理を厳密に扱える手段として重要な役割を果たした.
計算複雑性の観点では,Datalogの問い合わせ評価はデータ複雑性においてPTIME完全であることが知られており,これは一階述語論理やリレーショナル代数よりも高い表現力を有することを意味する.特に推移閉包の計算がDatalogで自然に表現できることは,グラフ理論的問題やネットワーク分析において大きな意味を持つ.
また,Datalogは実際のリレーショナルデータベース言語,特にSQLの設計思想に大きな影響を与えた.宣言的な問い合わせ記述,集合論的処理,再帰的問い合わせの表現といった概念は,SQLの後続バージョン[とりわけSQL:1999以降]におけるWITH RECURSIVE構文などに取り入れられている.さらに近年では,知識ベース,データ整合性検査,セキュリティポリシー検証,ネットワーク構成管理,静的プログラム解析,分散システムのデバッグなどの分野でDatalogの応用が再評価されている.具体的な実装として,LogicBlox,Soufflé,Flix,Datalog Z3,Datomicなどが商用・学術両分野で活用され,静的解析ツール[Facebook Infer,Amazon s2nなど]やポリシー言語[Rego,ASP.NET Core Authorizationなど]においても利用されている.
Datalogの変種として,制約Datalog[Constraint Datalog],時相Datalog[Temporal Datalog],確率的Datalog[Probabilistic Datalog],分散Datalog[Distributed Datalog]などの拡張版も研究されており,より複雑な推論と解析に対応している.また,機械学習分野においても,知識グラフの構築・推論,ニューラルシンボリック統合,説明可能AIなどの文脈でDatalogの活用が進んでいる.
Datalogはその理論的簡潔さ,形式的意味論の明確さ,再帰と推論の自然な表現力により,リレーショナルデータベースの研究と応用において今なお重要な位置を占めている.
Mathematics is the language with which God has written the universe.