データログ

Datalog は宣言型 論理プログラミング言語です。構文的にはPrologのサブセットですが、Datalog は一般にトップダウンではなくボトムアップの評価モデルを使用します。この違いにより、Prologとは大きく異なる動作と特性が生まれます。Datalog は、演繹データベースのクエリ言語としてよく使用されます。Datalog は、データ統合、ネットワーク、プログラム分析など の問題に適用されてきました。

Datalog プログラムは、真実であるとされるステートメントである事実と、既知の事実から新しい事実を推論する方法を示すルールで構成されます。たとえば、 xerces が brooke の親であり、brooke が damocles の親であることを意味する 2 つの事実を次に示します。

親( xerces 、 brooke )。
親( brooke 、 damocles )。

大文字で始まる文字列は変数を表すため、名前は小文字で記述されます。次の 2 つのルールがあります。

祖先( X ,  Y )  :- 親( X ,  Y )。
祖先( X ,  Y )  :- 親( X ,  Z )、 祖先( Z ,  Y )。

記号:-は「if」と読み、コンマは「and」と読みます。したがって、これらの規則の意味は次のようになります。

• X が Y の親である場合、X は Y の祖先です。
• X が何らかの Z の親であり、Z が Y の祖先である場合、X は Y の祖先です。

プログラムの意味は、最初の事実とルールを使用して推測できるすべての事実の集合として定義されます。このプログラムの意味は、次の事実によって与えられます。

親( xerces 、 brooke )。
親( brooke 、 damocles )。
祖先( xerces 、 brooke )。
祖先( brooke 、 damocles )。
祖先( xerces 、 damocles )。

一部の Datalog 実装では、すべての可能性のある事実を推測するのではなく、クエリに回答します。

?- 祖先( xerces 、 X )。

このクエリは、「xerces の祖先である X は誰ですか?」と尋ねます。この例では、 brookeとdamoclesが返されます。

Datalog の非再帰サブセットは、SQLなどのリレーショナル データベースのクエリ言語と密接に関連しています。次の表は、Datalog、リレーショナル代数、およびSQL の概念間のマッピングを示しています。

より正式には、非再帰的 Datalog は、結合クエリの和集合、つまり否定のないリレーショナル代数に正確に対応します。

Datalogプログラムはルールのリスト（ホーン節）で構成されています。^[1] constantとvariableがそれぞれ定数と変数の2つの可算なセットであり、 relationが述語記号の可算なセットである場合、次のBNF文法はDatalogプログラムの構造を表します。

<プログラム>  ::=  <ルール>  <プログラム> | ""
 <ルール>  ::=  <アトム> ":-" <アトムリスト> "."
 <アトム>  ::=  <関係> "(" <用語リスト> ")"
 <アトムリスト>  ::=  <アトム> | <アトム> "," <アトムリスト> | ""
 <用語>  ::=  <定数> | <変数> 
<用語リスト>  ::=  <用語> | <用語> "," <用語リスト> | ""

アトムはリテラルとも呼ばれます。シンボルの左側のアトムはルールのヘッド:-と呼ばれ、右側のアトムはボディと呼ばれます。すべてのDatalogプログラムは、ルールのヘッドに現れるすべての変数がボディにも現れるという条件を満たす必要があります（この条件は範囲制限と呼ばれることもあります）。^{[1] [2]}

変数名には2つの一般的な規則があります。変数名を大文字にするか、先頭に疑問符を付けることです?。^[3]

この定義では、Datalog には否定や集約が含まれていないことに注意してください。これらの構成要素の詳細については、§ 拡張を参照してください。

本体が空のルールはファクトと呼ばれます。たとえば、次のルールはファクトです。

r ( x )  :-  .

事実の集合は、Datalog プログラムの拡張データベースまたはEDBと呼ばれます。Datalog プログラムを評価することによって計算されるタプルの集合は、内包データベースまたはIDBと呼ばれます。

論理プログラミングの多くの実装では、上記の文法を拡張して、:-次のように なしで事実を記述できるようにします。

r ( x ) です。

次のように、括弧なしで 0 項関係を記述できるものもあります。

p  :-  q .

これらは単なる略語 (構文糖) であり、プログラムの意味には影響しません。

Datalogプログラムのセマンティクスには、モデル理論的、固定小数点的、証明理論的の3つのアプローチが広く使用されています。これら3つのアプローチは同等であることが証明されています。^[4]

アトムは、そのサブタームのいずれも変数でない場合、グラウンドと呼ばれます。直感的に、各セマンティクスは、プログラムの意味を、事実から始めて、プログラムのルールから推測できるすべてのグラウンド アトムの集合として定義します。

ルールのアトム（ヘッドとボディ）がすべてグラウンドである場合、そのルールはグラウンドと呼ばれます。グラウンドルールR ₁は、別のルールR _2のグラウンドインスタンスである場合、R _1は、 R ₂内のすべての変数を定数に置き換えた結果です。Datalogプログラムのエルブラン基底は、プログラムに現れる定数で作成できるすべてのグラウンドアトムの集合です。Datalog プログラムのエルブランモデルは、プログラム内の各ルールの各グラウンドインスタンスについて、ルールのボディ内のアトムが集合内に存在する場合、ヘッドも集合内に存在するようなエルブラン基底の最小のサブセットです。^[5]モデル理論的意味論は、最小のエルブランモデルをプログラムの意味として定義します。

I をプログラムPのエルブラン基底のべき集合とする。Pの即時結果演算子は、 IからIへの写像Tであり、これはプログラムの規則から単一のステップで導出できるすべての新しい基底原子を追加する。最小固定点意味論は、Tの最小固定点をプログラムの意味として定義する。これは最小エルブランモデルと一致する。^[6]

固定点セマンティクスは、最小モデルを計算するためのアルゴリズムを提案します。プログラムの基本事実のセットから始めて、固定点に到達するまでルールの結果を繰り返し追加します。このアルゴリズムはナイーブ評価と呼ばれます。

証明理論的意味論は、Datalog プログラムの意味を、対応する証明ツリーを持つ事実の集合として定義します。直感的に言えば、証明ツリーは、事実とプログラムのルールから事実を導き出す方法を示します。

モデルの残りの部分についてはあまり気にしないかもしれませんが、特定の基底原子が Datalog プログラムの最小 Herbrand モデルに現れるかどうかを知ることに興味があるかもしれません。上記の証明ツリーをトップダウンで読み取ると、そのようなクエリの結果を計算するアルゴリズムが示唆されます。この読み取りは、Prologの評価の基礎となるSLD 解決アルゴリズムに情報を提供します。

Datalog プログラムを評価する方法は多数あり、それぞれパフォーマンス特性が異なります。

ボトムアップ評価戦略は、プログラム内の事実から開始し、何らかの目標またはクエリが確立されるまで、またはプログラムの完全な最小モデルが生成されるまで、ルールを繰り返し適用します。

ナイーブ評価は、 Datalog プログラムの固定点セマンティクスを反映しています。ナイーブ評価では、プログラム内の事実に初期化される「既知の事実」のセットを使用します。プログラム内の各ルールのすべての基本インスタンスを繰り返し列挙することで、評価が進められます。基本インスタンスの本体の各アトムが既知の事実のセットに含まれている場合、ヘッド アトムが既知の事実のセットに追加されます。このプロセスは、固定点に到達し、それ以上の事実を推測できなくなるまで繰り返されます。ナイーブ評価は、プログラムの最小モデル全体を生成します。^[7]

セミナイーブ評価は、ナイーブ評価よりも漸近的に高速化できるボトムアップ評価戦略です。^[8]

ナイーブ評価とセミナイーブ評価はどちらも、固定点に達するまで既知の事実のセットに繰り返し適用することで、再帰的な Datalog ルールを評価します。各反復では、ルールは「1 ステップ」のみ、つまり非再帰的に実行されます。前述のように、各非再帰的な Datalog ルールは、結合クエリに正確に対応しています。したがって、結合クエリを高速化するために使用されるデータベース理論の多くの手法は、Datalog のボトムアップ評価に適用できます。たとえば、

• インデックスの選択^[10]
• クエリの最適化、特に結合順序^{[11] [12]}
• 結合アルゴリズム
• 関係を格納するために使用されるデータ構造の選択。一般的な選択肢にはハッシュテーブルとBツリーが含まれますが、他の可能性としては、分離集合データ構造（同値関係を格納するため）、^{[13]ブリー（}トライの変形）、^[14] 二分決定図、^{[15] 、さらには}SMT式^[16]などがあります。

このような技術の多くは、 Souffléなどの現代のボトムアップDatalogエンジンに実装されています。一部のDatalogエンジンはSQLデータベースを直接統合します。^[17]

Datalog のボトムアップ評価も並列化に適しています。並列 Datalog エンジンは、一般的に 2 つのパラダイムに分けられます。

• 共有メモリ、マルチコア設定では、Datalog エンジンは単一のノードで実行されます。スレッド間の調整は、ロックまたはロックフリー データ構造を使用して実現できます。共有メモリ設定は、さらに、単一命令、複数データと複数命令、複数データのパラダイムに分けられます。
  • グラフィックス処理装置上で実行されるデータログエンジンはSIMDパラダイムに分類されます。^[18]
  • OpenMP ^[19]を使用したデータログエンジンはMIMDパラダイムのインスタンスである。
• シェアードナッシング設定では、Datalogエンジンはノードのクラスタ上で実行されます。このようなエンジンは通常、ハッシュ関数に基づいて関係を分離したサブセットに分割し、各ノードで計算（結合）を実行し、新しく生成されたタプルをネットワーク経由で交換することによって動作します。^{[20]例としては、} MPI、^[9] Hadoop、^[21] Sparkに基づくDatalogエンジンがあります。^[22]

SLD 解像度は、データログ プログラムにとって健全かつ完全です。

トップダウン評価戦略は、クエリまたは目標から始まります。ボトムアップ評価戦略は、最小限のモデル全体を計算してクエリを照合することでクエリに答えることができますが、答えがモデル全体の小さなサブセットにのみ依存する場合は非効率的です。マジックセットアルゴリズムは、Datalogプログラムとクエリを受け取り、ボトムアップ評価を使用しながらクエリに対して同じ答えを計算する、より効率的なプログラムを生成します。^[23]マジックセットアルゴリズムのバリアントは、半ナイーブ評価を使用して評価された場合、トップダウン評価と同じくらい効率的なプログラムを生成することが示されています。^[24]

Datalog評価の決定問題の定式化は次のようになります。DatalogプログラムPが事実の集合（EDB）Eとルールの集合Rに分割され、基底原子Aが与えられたとき、AはPの最小モデルに含まれるでしょうか？この定式化では、Datalogプログラムを評価する計算の複雑さには3つのバリエーションがあります。^[25]

• データの複雑さは、 AとEが入力で、Rが固定されている場合の決定問題の複雑さです。
• プログラムの複雑さは、 AとRが入力でEが固定されている場合の決定問題の複雑さです。
• 複合複雑度は、 A、E、およびRが入力である場合の意思決定問題の複雑度です。

データの複雑さに関しては、Datalog の決定問題はP 完全です。プログラムの複雑さに関しては、決定問題はEXPTIME 完全です。特に、Datalog プログラムの評価は常に終了します。Datalog はチューリング完全ではありません。

Datalog の一部の拡張機能では、これらの複雑度の境界が保持されません。代数データ型などの一部の Datalog エンジンに実装された拡張機能により、結果の言語がチューリング完全になることもあります。

Datalog には、否定、集約関数、不等式をサポートしたり、オブジェクト指向プログラミングを可能にしたり、節の先頭として選言を許可したりするなど、いくつかの拡張機能が加えられています。これらの拡張機能は、言語のセマンティクスと対応するインタープリターの実装に大きな影響を与えます。

DatalogはProlog、disjunctive Datalog、answer set programming、DatalogZ、およびconstraint logic programmingの構文サブセットです。答えセットプログラムとして評価されると、Datalogプログラムは単一の答えセットを生成し、それがまさにその最小モデルです。^[26]

Datalog の多くの実装では、追加機能によって Datalog が拡張されます。詳細については、§ Datalog エンジンを参照してください。

Datalogは集計関数をサポートするように拡張することができます。^[27]

集計を実装する注目すべき Datalog エンジンには次のものがあります。

• ロジックブロックス^[28]
• スフレ

Datalog に否定を追加するとセマンティクスが複雑になり、評価のためのまったく新しい言語と戦略が必要になります。たとえば、安定したモデルのセマンティクスに否定を追加した結果の言語は、まさに答えセットプログラミングです。

モデル理論的および固定小数点セマンティクスを維持しながら、 階層化否定を Datalog に追加できます。階層化否定を実装する注目すべき Datalog エンジンには、次のものがあります。

• ロジックブロックス^[29]
• スフレ

Prologとは異なり、Datalog プログラムのステートメントは任意の順序で記述できます。Datalog には Prolog のカット演算子がありません。これにより、Datalog は完全に宣言的な言語になります。

Prologとは対照的に、Datalog

• 述語の引数として複合項を許可しません。例えば、p(x, y)は許可されますが、は許可されませんp(f(x), y)。
• 否定を禁止する、
• 節の先頭に現れるすべての変数が、節の本体のリテラルにも現れる必要があります。

この記事では、主に否定のない Datalog について扱います (論理プログラミングの構文と意味論 § 否定による Datalog の拡張も参照)。ただし、階層化否定は Datalog によく追加される機能です。次のリストは、 Prologと階層化否定のある Datalog を対比したものです。階層化否定のある Datalog

• また、述語の引数として複合項を使用することはできない。
• 節の先頭に現れるすべての変数は、節の本体の肯定的な（つまり否定されていない）アトムにも現れる必要がある。
• 節本体の否定リテラルに現れるすべての変数は、節本体の何らかの肯定リテラルにも現れる必要がある。^{[30] [信頼できない情報源? ]}

Datalog は他の多くのクエリ言語を一般化します。たとえば、結合クエリと結合クエリの結合はDatalog で表現できます。Datalog は通常のパス クエリも表現できます。

順序付きデータベース、つまりアクティブドメイン上に順序関係を持つデータベースを考えると、 Immerman-Vardiの定理は、 Datalogの表現力がまさにPTIMEクラスの表現力であることを意味します。つまり、プロパティがDatalogで表現できるのは、多項式時間で計算できる場合のみです。^[31]

Datalogの有界性問題は、Datalogプログラムが与えられたときに、それが有界であるかどうか、つまり、入力データベース上でプログラムを評価するときに到達する最大再帰深度が、ある定数によって制限されるかどうかを問うものです。言い換えれば、この質問は、Datalogプログラムを非再帰的なDatalogプログラムとして書き直すことができるかどうか、または同等に、連言クエリの和集合として書き直すことができるかどうかを問うものです。任意のDatalogプログラム上で有界性問題を解決することは決定不可能ですが、^[32] Datalogの一部のフラグメントに制限することで決定可能にすることができます。

コンパイラ、インタープリタ、ライブラリ、または組み込み DSLなど、 Datalog にヒントを得た言語を実装するシステムは、Datalog エンジンと呼ばれます。Datalog エンジンは、多くの場合、Datalog の拡張機能を実装し、追加のデータ型、外部関数インターフェイス、またはユーザー定義のラティスのサポートで拡張します。このような拡張機能により、終了しないプログラムや定義が不十分なプログラムを作成できるようになります。 ^{[引用が必要]}

以下は、Datalog をベースにしているか、Datalog インタープリターを提供しているシステムの短いリストです。

• FoundationDBはpyDatalog用のデータベースバインディングを無料で提供しており、その使用方法に関するチュートリアルも提供しています。^[37]
• Leapsightセマンティックデータスペース（LSD）は、高可用性、フォールトトレランス、操作のシンプルさ、スケーラビリティを備えた分散推論データベースです。LSDは、クエリと推論にLeaplog（Datalog実装）を使用しており、Leapsightによって作成されました。^[38]
• LogicBlox は、Web ベースの小売計画および保険アプリケーションに使用される Datalog の商用実装です。
• Profium Sense は、Java で記述されたネイティブ RDF 準拠のグラフ データベースです。ユーザー定義ルールの Datalog 評価サポートを提供します。
• .QLは、Semmleがソースコードを解析してセキュリティの脆弱性を検出するために作成した、Datalogの商用オブジェクト指向版です。^[39]
• SecPALはマイクロソフトリサーチが開発したセキュリティポリシー言語である。^[40]
• Stardog は、 Javaで実装されたグラフ データベースです。RDFとすべてのOWL 2プロファイルをサポートし、データログ評価を含む広範な推論機能を提供します。
• StrixDB: 商用 RDF グラフ ストア、Lua API および Datalog 推論機能に準拠したSPARQL。httpd ( Apache HTTP Server ) モジュールまたはスタンドアロンとして使用できます(ただし、ベータ バージョンは Perl Artistic License 2.0 に基づいています)。

Datalog の表現力はかなり限られています。チューリング完全ではなく、整数や文字列などの基本的なデータ型は含まれていません。この簡素さは理論的な観点からは魅力的ですが、Datalog自体がプログラミング言語や知識表現言語として使用されることはほとんどないことを意味します。^[41]ほとんどの Datalog エンジンは、Datalog の大幅な拡張を実装しています。ただし、Datalog はそのような実装に強い影響を与えており、多くの著者は、この記事で紹介されているように、それらを Datalog と区別しようとしません。したがって、このセクションで説明するアプリケーションには、Datalog ベースの言語の現実的な実装のアプリケーションが含まれます。

Datalogは、データ統合、情報抽出、ネットワーキング、セキュリティ、クラウドコンピューティング、機械学習などの問題に適用されています。^{[42] [43]} Googleはビッグデータ処理用にDatalogの拡張機能を開発しました。^[44]

Datalogは静的プログラム解析に応用されています。^[45] Soufflé方言はJavaのポインタ解析やSchemeの制御フロー解析を書くために使われてきました。^{[46] [47] Datalogは}SMTソルバーと統合されており、特定の静的解析の記述を容易にしています。^[48] Flix方言も静的プログラム解析の記述に適しています。^[49]

広く使用されているデータベースシステムの中には、Datalog用に開発されたアイデアやアルゴリズムが含まれているものがあります。たとえば、SQL:1999標準には再帰クエリが含まれており、Magic Setsアルゴリズム（当初はDatalogクエリの高速評価のために開発されました）はIBMのDB2に実装されています。^[50]

Datalogの起源は論理プログラミングの始まりにまで遡りますが、1977年頃にHervé GallaireとJack Minkerが論理とデータベースに関するワークショップを開催した際に独立した分野として注目されるようになりました。^[51] Datalogという用語を作ったのはDavid Maierと言われています。 ^[52]

• 回答セットプログラミング
• 結合クエリ
• データログZ
• 分離データログ
• フリックス
• スウェル
• タプル生成依存関係(TGD) は、 Datalog に似た構文を持つリレーショナル データベースの整合性制約用の言語です。

• Ceri, S.; Gottlob, G.; Tanca, L. (1989 年 3 月) 。「Datalog についていつも知りたかったこと (そして聞く勇気がなかったこと)」( PDF )。IEEE Transactions on Knowledge and Data Engineering。1 ( 1): 146–166。CiteSeerX 10.1.1.210.1118。doi : 10.1109 /69.43410。ISSN 1041-4347  。 
• Abiteboul, S. (1995)。データベースの基礎。Richard Hull、Victor Vianu。マサチューセッツ州レディング：Addison- Wesley。ISBN 0-201-53771-0. OCLC  30546436。