データログ

データログ
パラダイム論理、宣言的
家族プロローグ
初登場1977年; 48年前 （1977年）
タイピングの規律弱い
方言
Datomic、.QL、Soufflé、XTDB など。
影響を受けた
プロローグ
影響を受けた
SQL
データログ
ファイル名拡張子
.dl
インターネットメディアの種類
テキスト/vnd.データログ
Webサイトデータログ仕様情報

Datalogは宣言型 論理プログラミング言語です。構文的にはPrologのサブセットですが、一般的にトップダウンではなくボトムアップの評価モデルを採用しています。この違いにより、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の概念間のマッピングを示しています。

データログ関係代数SQL
関係関係テーブル
事実タプル行
ルール—マテリアライズドビュー
クエリ選択クエリ

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

構文

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

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

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

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

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

空の本文を持つルールはファクトと呼ばれます。例えば、次のルールはファクトです。

r ( x )  :-  。

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

糖衣構文

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

r ( x ) です。

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

p  :-  q .

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

セマンティクス

エルブラン宇宙、ベース、およびデータログプログラムのモデル
プログラム
エッジ( x ,  y )。エッジ( y ,  z )。パス( A ,  B )  :- エッジ( A ,  B )。パス( A ,  C )  :- パス( A ,  B )、 エッジ( B ,  C )。
エルブラン宇宙x、、y​z
エルブラン基地edge(x, x)、、、edge(x, y)... edge(z, z)、、、path(x, x)...、path(z, z)
エルブランモデルedge(x, y)、、、、、edge(y, z)​path(x, y)​path(y, z)​path(x, z)

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

アトムは、そのサブタームに変数がない場合、基底アトムと呼ばれます。直感的に言えば、それぞれのセマンティクスは、プログラムの意味を、事実から始めてプログラムの規則から推論できるすべての基底アトムの集合として定義します。

モデル理論的

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

固定小数点

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

不動点意味論は、最小モデルを計算するためのアルゴリズムを示唆しています。プログラムの基本事実の集合から始め、不動点に到達するまで規則の結果を繰り返し追加していきます。このアルゴリズムはナイーブ評価と呼ばれます。

証明理論的

path(x, z)プログラムから基底原子を導出する証明木
エッジ( x ,  y )。エッジ( y ,  z )。パス( A ,  B )  :- エッジ( A ,  B )。パス( A ,  C )  :- パス( A ,  B )、 エッジ( B ,  C )。

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

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

評価

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

ボトムアップ評価戦略

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

ナイーブな評価

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

半ナイーブ評価

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

パフォーマンスに関する考慮事項

並列Datalogエンジンはアルゴンヌ国立研究所のThetaスーパーコンピュータで評価されました。[9]

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

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

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

トップダウン評価戦略

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完全である（[25]の定理4.4を参照）。データ複雑性のP完全性とは、評価がP完全となる固定されたデータログクエリが存在することを意味する。証明は、命題論理プログラム用のDatalogメタインタープリタに基づいている。

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

Datalog の一部の拡張機能は、これらの計算量境界を保持しません。一部の Datalog エンジンに実装されている代数データ型などの拡張機能は、結果の言語をチューリング完全にすることさえ可能です。

拡張機能

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

Datalogは、 Prolog、選言的Datalog、解答集合プログラミング、DatalogZ、制約論理プログラミングの構文的サブセットです。解答集合プログラムとして評価された場合、Datalogプログラムは単一の解答集合を生成し、それがまさにその最小モデルとなります。[26]

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

集約

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

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

否定

Datalogに否定を追加するとセマンティクスが複雑になり、全く新しい言語や評価戦略が生まれます。例えば、安定モデルセマンティクスに否定を追加することで得られる言語は、まさに答え集合プログラミングです。

モデル理論的および固定小数点セマンティクスを維持しながら、層別否定をDatalogに追加できます。層別否定を実装している注目すべきDatalogエンジンには、以下が含まれます。

Prologとの比較

Prologとは異なり、Datalogプログラムの文は任意の順序で記述できます。DatalogにはPrologのカット演算子はありません。そのため、Datalogは完全に宣言的な言語です。

Prologとは対照的に、Datalog

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

この記事では、主に否定のないDatalogについて扱います（論理プログラミングの構文と意味論 § 否定も参照）。しかし、層別否定はDatalogによく追加される機能です。以下のリストは、Prologと層別否定のあるDatalogを比較したものです。層別否定のあるDatalog

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

表現力

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

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

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

データログエンジン

Datalogに着想を得た言語を実装したシステム（コンパイラ、インタープリタ、ライブラリ、組み込みDSLなど）は、 Datalogエンジンと呼ばれます。Datalogエンジンは多くの場合、Datalogの拡張を実装し、追加のデータ型、外部関数インターフェース、またはユーザー定義ラティスのサポートを提供します。このような拡張により、非終端プログラムや不完全定義プログラムの作成が可能になります。 [要出典]

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

フリーソフトウェア/オープンソース

フリーソフトウェアおよびオープンソースのデータログエンジンのリスト
名前最新リリースの年書かれたライセンスデータソース説明リンク
Abcデータログ2023ジャワBSD共通の評価アルゴリズムを実装したデータログエンジン。拡張性、研究用途、教育用に設計されています。ホームページ
上昇2023さびMITライセンスマクロを介して Rust に埋め込まれた論理プログラミング言語 (Datalog に類似)。Lattice およびカスタマイズされたデータ構造をサポートします。リポジトリ
うわー2007ジャワGNU LGPL大規模な Java プログラムのポイントツー分析を含む Java バイトコードをクエリするように設計されたデータログ実装。内部的にはBDD を使用します。ホームページ
花（つぼみ）2017ルビーBSD 3条項データ中心の構造でプログラミングするためのRuby DSL。ロジックに時間的な次元を追加するDatalogのDedalus拡張に基づいています。ホームページリポジトリ
カスカログ2014クロージュアアパッチ2.0他のDBMSにクエリを実行できるHadoopで使用するために設計された、Clojure と Java 用のデータ処理およびクエリ ライブラリリポジトリホームページ（アーカイブ）
クリンゴ2024C++MITライセンス回答セットDatalog を特別なケースとしてサポートするプログラミングシステム。スタンドアロンの Grounder Gringoは、単純な Datalog には十分です。ホームページリポジトリオンラインデモ
コンセプトベース2025プロローグ/C++/JavaBSD 2節概念モデリングとメタモデリングのための演繹的およびオブジェクト指向的なデータベースシステム。これには、データログクエリ評価機能が含まれています。ホームページ
コーラル1997C++独自仕様、一部の用途では無料、オープンソースC++で記述された、半ナイーブなデータログ評価機能を備えた演繹データベースシステム。1988年から1997年にかけて開発されました。ホームページ
クレープ2023さびApache 2.0またはMIT手続き型マクロに基づいて、Datalogのような推論を表現するためのRustライブラリホームページ
データフロッグ2019さびApache 2.0またはMIT他のRustプログラムに組み込むことを目的とした軽量データログエンジンホームページ
データファン2016ラケットオープンソース、リポジトリにライセンスなし半格子上のDatalogを一般化した関数型プログラミング言語ホームページリポジトリ
データハイク2024クロージュアEclipse パブリックライセンス 1.0組み込みデータベース（メモリ内またはファイル）ヒッチハイカーツリーに基づく耐久性のあるバックエンドを備えた DataScript のフォーク。クエリ言語として Datalog を使用。ホームページ
データレビン2024クロージュアEclipse パブリックライセンス 1.0LMDBバインディングクエリ言語として Datalog を使用して、LMDB 耐久性ストレージ用に最適化された DataScript のフォークホームページ
データログ（Erlang）2019アーランアパッチ2.0Erlang で Datalog クエリをサポートするライブラリ。データはタプルのストリームとして表現されます。ホームページ
データログ（MITRE）2016ルアGNU LGPLメモリ制限のあるデバイスでも小さく使用できるように設計された軽量の演繹データベース システムホームページ オンラインデモ
データログ (OCaml)2019OCamlBSD 2節ボトムアップとトップダウンのアルゴリズムを備えたOCamlのインメモリデータログ実装ホームページ
データログ（ラケット）2022ラケットApache 2.0またはMITDatalogを使用するためのラケットパッケージホームページリポジトリ
データログ教育システム2025プロローグGNU LGPLDBMSコネクタデータログとSQLを教えるためのオープンソース実装[33]ホームページ

オンラインデモ

データスクリプト2024クロージュアEclipse パブリックライセンス 1.0インメモリデータベースクエリ言語として Datalog を使用してブラウザで実行される不変データベースホームページ
ダトミック2024クロージュアクローズドソース。Apache 2.0でリリースされたバイナリDynamoDB、Cassandra、PostgreSQLなどのバインディングクラウド アーキテクチャ上で実行される分散データベース。クエリ言語として Datalog を使用します。ホームページ
DDログ2021さびMITライセンス増分型、メモリ内、型付きデータログエンジン。Rustでコンパイル。差分データフロー[34]ライブラリ に基づく。ホームページ
DLV2023C++独自仕様だが、一部の用途では無料回答セットDatalog を特別なケースとしてサポートするプログラミングシステムホームページ
会社
ダイナ12013ハスケルGNU AGPL v3統計AIプログラミングのためのDatalogを使用した宣言型プログラミング言語。以降のDynaバージョンではDatalogは使用されません。リポジトリホームページ（アーカイブ）
フリックス2024ジャワアパッチ2.0Datalog にヒントを得た関数型および論理型プログラミング言語で、ユーザー定義のラティスと単調なフィルタ/伝達関数が拡張されています。ホームページ オンラインデモ
グラール2018ジャワCeCILL v2.1RDFインポート、CSVインポート、DBMSコネクタ存在ルール（タプル生成依存関係または Datalog+/- とも呼ばれる）のフレームワーク内で知識ベースを照会するための Java ツールキットホームページ
インター4QL2020C++BSD4値ロジックに基づくデータベースクエリ言語のインタープリタ。特別なケースとしてDatalogをサポート。ホームページ
虹彩2016ジャワGNU LGPL v2.1十分に根拠のある意味論の下でデータログと否定をサポートする論理プログラミングシステム。RDFSをサポートリポジトリ
イエナ2024ジャワアパッチ2.0RDFインポート汎用ルールエンジンの一部として Datalog 実装を含むセマンティック Web フレームワーク。RDF との互換性あり。ルールエンジンのドキュメント
マングル2024行くアパッチ2.0Datalogの拡張をサポートする演繹データベースプログラミングのためのプログラミング言語ホームページ
マップライブラリ2025さびApache 2.0、一部の用途ではプロプライエタリRDFインポート、PolarsデータフレームRDF としての知識グラフのデータログ推論をサポートする Python のセマンティック ウェブ フレームワークホームページ
ナガ2021クロージュアEclipse パブリックライセンス 1.0浅見グラフデータベースグラフ データベースに対して Datalog クエリを実行するクエリ エンジン。ブラウザー (メモリ)、JVM (メモリ/ファイル)、またはネイティブ (メモリ/ファイル) で実行されます。ホームページ
ニモ2024さびApache 2.0またはMITRDFインポート、CSVインポートナレッジグラフ分析とデータベース変換のためのインメモリルールエンジン。RDFおよびSPARQLと互換性があり、 tgdsをサポートします。ホームページ オンラインデモ
pyデータログ2015パイソンGNU LGPLPythonからのDBMSコネクタDatalogクエリを解釈するためのPythonライブラリホームページリポジトリ
RDFox2024C++独自仕様だが、一部の用途では無料インメモリデータベース、RDFインポート、CSVインポート、DBMSコネクタデータログ推論を備えたメインメモリベースのRDFトリプルストア。増分評価と高可用性設定 をサポートホームページ
ソーシャルライト2016ジャワアパッチ2.0HDFSバインディング大規模グラフ分析のためのデータログバリアントとエンジンホームページ（アーカイブ）リポジトリ
スフレ2023C++UPL v1.0CSVインポート、sqlite3バインディングデータログエンジンは元々アプリケーションの静的プログラム分析用に設計されており、ルールセットはC++プログラムにコンパイルされるか、解釈されます。ホームページ
tclbdd2015TclBSD二分決定図に基づくデータログ実装。Tclの最適化コンパイラの開発をサポートするために設計されている[35]ホームページ
ターミナスDB2024プロローグ/ Rustアパッチ2.0グラフデータベースとドキュメントストア。データログベースのクエリ言語も備えています。ホームページ
XSB2022CGNU LGPLPrologをベースにした論理プログラミングと演繹データベースシステム。テーブル化によりDatalogのような終了性と効率性を実現し、増分評価も含む[36]ホームページ
XTDB (旧Crux )2024クロージュアMPL 2.0Apache Kafkaなどのバインディングタイムトラベル機能を備えた不変データベース。XTDB 1.x ではクエリ言語としてデータログが使用されます (XTDB 2.x では変更される可能性があります)ホームページリポジトリ

非フリーソフトウェア

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

参照

注記

  1. ^ ab Ceri、Gottlob & Tanca 1989、p. 146.
  2. ^ アイズナー、ジェイソン;フィラルド、ナサニエル W. (2011)。 「Dyna: 最新 AI 向けのデータログの拡張」。オーゲ州デ・ムーアにて。ゴットロブ、ゲオルグ。ファーチェ、ティム。セラーズ、アンドリュー（編）。データログがリロードされました。コンピューターサイエンスの講義ノート。 Vol. 6702. ベルリン、ハイデルベルク: Springer。 pp.  181–220。土井:10.1007/978-3-642-24206-9_11。ISBN 978-3-642-24206-9。
  3. ^ Maier, David; Tekle, K. Tuncay; Kifer, Michael; Warren, David S. (2018-09-01)「Datalog: concepts, history, and outlook」, Declarative Logic Programming: Theory, Systems, and Applications , vol. 20, Association for Computing Machinery and Morgan & Claypool, pp.  3– 100, doi :10.1145/3191315.3191317, ISBN 978-1-970001-99-0, S2CID  69379310 , 2023年3月2日取得
  4. ^ Van Emden, MH; Kowalski, RA (1976-10-01). 「プログラミング言語としての述語論理の意味論」. Journal of the ACM . 23 (4): 733– 742. doi : 10.1145/321978.321991 . ISSN  0004-5411. S2CID  11048276.
  5. ^ チェリ、ゴットロブ、タンカ 1989、p. 149.
  6. ^ チェリ、ゴットロブ、タンカ 1989、p. 150。
  7. ^ チェリ、ゴットロブ、タンカ 1989、p. 154.
  8. ^ Alvarez-Picallo, Mario; Eyers-Taylor, Alex; Peyton Jones, Michael; Ong, C.-H. Luke (2019). 「増分計算の修正：固定点の導関数とDatalogの再帰的意味論」. Caires, Luís (編).プログラミング言語とシステム. コンピュータサイエンス講義ノート. 第11423巻. シュプリンガー・インターナショナル・パブリッシング. pp.  525– 552. doi :10.1007/978-3-030-17184-1_19. ISBN 978-3-030-17184-1. S2CID  53430789。
  9. ^ ab Gilray, Thomas; Sahebolamri, Arash; Kumar, Sidharth; Micinski, Kristopher (2022-11-21). 「高階データ並列構造化演繹」. arXiv : 2211.11573 [cs.PL].
  10. ^ Subotić, Pavle; Jordan, Herbert; Chang, Lijun; Fekete, Alan; Scholz, Bernhard (2018-10-01). 「大規模データログ計算のための自動インデックス選択」. Proceedings of the VLDB Endowment . 12 (2): 141– 153. doi :10.14778/3282495.3282500. ISSN  2150-8097. S2CID  53569679.
  11. ^ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). 「doop の Soufflé への移植」.第 6 回 ACM SIGPLAN 国際プログラム分析ワークショップの議事録. SOAP 2017. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  25– 30. doi :10.1145/3088515.3088522. ISBN 978-1-4503-5072-3. S2CID  3074689。「LogicBlox エンジンは完全なクエリ最適化を実行します。」
  12. ^ Arch, Samuel; Hu, Xiaowen; Zhao, David; Subotić, Pavle; Scholz, Bernhard (2022). 「Souffléの結合オプティマイザーの構築」. Villanueva, Alicia (編). Logic-Based Program Synthesis and Transformation . Lecture Notes in Computer Science. Vol. 13474. Cham: Springer International Publishing. pp.  83– 102. doi :10.1007/978-3-031-16767-6_5. ISBN 978-3-031-16767-6。
  13. ^ Nappa, Patrick; Zhao, David; Subotic, Pavle; Scholz, Bernhard (2019). 「データログコンパイラにおける高速並列同値関係」. 2019 第28回国際並列アーキテクチャおよびコンパイル技術会議 (PACT) . pp.  82– 96. doi :10.1109/PACT.2019.00015. ISBN 978-1-7281-3613-4. S2CID  204827819。
  14. ^ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (2019-02-17). 「Brie: 並行データログのための特殊トライ」.第10回国際ワークショップ「マルチコアおよびメニーコア向けプログラミングモデルとアプリケーション」議事録. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  31– 40. doi :10.1145/3303084.3309490. ISBN 978-1-4503-6290-0. S2CID  239258588。
  15. ^ Whaley, John; Avots, Dzintars; Carbin, Michael; Lam, Monica S. (2005). 「プログラム分析における二分決定図を用いたデータログの利用」 Yi, Kwangkeun (編). 『プログラミング言語とシステム』 . コンピュータサイエンス講義ノート. 第3780巻. ベルリン, ハイデルベルク: Springer. pp.  97– 118. doi :10.1007/11575467_8. ISBN 978-3-540-32247-4. S2CID  5223577。
  16. ^ Hoder, Kryštof; Bjørner, Nikolaj; de Moura, Leonardo (2011). 「μZ - 制約付き固定点のための効率的なエンジン」. Gopalakrishnan, Ganesh; Qadeer, Shaz (編).コンピュータ支援検証. コンピュータサイエンス講義ノート. 第6806巻. ベルリン、ハイデルベルク: Springer. pp.  457– 462. doi :10.1007/978-3-642-22110-1_36. ISBN 978-3-642-22110-1。
  17. ^ Fan, Zhiwei; Zhu, Jianqiao; Zhang, Zuyu; Albarghouthi, Aws; Koutris, Paraschos; Patel, Jignesh (2018-12-10). 「インメモリデータログ処理のスケールアップ：考察と手法」. arXiv : 1812.03975 [cs.DB].
  18. ^ Shovon, Ahmedur Ra​​hman; Dyken, Landon Richard; Green, Oded; Gilray, Thomas; Kumar, Sidharth (2022年11月). 「cuDFによるデータログアプリケーションの高速化」. 2022 IEEE/ACM ワークショップ「不規則アプリケーション：アーキテクチャとアルゴリズム」(IA3) . IEEE. pp.  41– 45. doi :10.1109/IA356718.2022.00012. ISBN 978-1-6654-7506-8. S2CID  256565728。
  19. ^ Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard (2019-02-16). 「並行データログ評価のための特殊Bツリー」.第24回並列プログラミングの原理と実践シンポジウム議事録. PPoPP '19. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  327– 339. doi :10.1145/3293883.3295719. ISBN 978-1-4503-6225-2. S2CID  59617209。
  20. ^ Wu, Jiacheng; Wang, Jin; Zaniolo, Carlo (2022-06-11). 「マルチコアマシンにおける並列再帰データログ評価の最適化」. 2022年国際データ管理会議議事録. SIGMOD '22. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  1433– 1446. doi :10.1145/3514221.3517853. ISBN 978-1-4503-9249-5. S2CID  249578825。これらのアプローチは、ハッシュなどの識別関数を用いてテーブルを互いに素なパーティションに分割し、各パーティションを並列ワーカーの1つにマッピングすることで、並列ボトムアップ評価の概念を実装します。各反復処理の後、ワーカーは必要に応じて新たに生成されたタプルを交換するために相互に連携します。
  21. ^ Shaw, Marianne; Koutris, Paraschos; Howe, Bill; Suciu, Dan (2012). 「Hadoopにおける大規模セミナイーブデータログ評価の最適化」Barceló, Pablo; Pichler, Reinhard (編). 『学術界と産業界におけるデータログ』 . 『コンピュータサイエンス講義ノート』. Vol. 7494. ベルリン、ハイデルベルク: Springer. pp.  165– 176. doi :10.1007/978-3-642-32925-8_17. ISBN 978-3-642-32925-8。
  22. ^ Shkapsky, Alexander; Yang, Mohan; Interlandi, Matteo; Chiu, Hsuan; Condie, Tyson; Zaniolo, Carlo (2016-06-14). 「Spark におけるデータログクエリによるビッグデータ分析」. 2016年国際データ管理会議議事録. SIGMOD '16. Vol. 2016. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  1135– 1149. doi :10.1145/2882903.2915229. ISBN 978-1-4503-3531-7. PMC  5470845 . PMID  28626296 .
  23. ^ Balbin, I.; Port, GS; Ramamohanarao, K.; Meenakshi, K. (1991-10-01). 「階層化データベースにおけるクエリの効率的なボトムアップ計算」. The Journal of Logic Programming . 11 (3): 295– 344. doi : 10.1016/0743-1066(91)90030-S . ISSN  0743-1066.
  24. ^ Ullman, JD (1989-03-29). 「データログではボトムアップがトップダウンに勝る」.第8回ACM SIGACT-SIGMOD-SIGARTシンポジウム「データベースシステムの原理 - PODS '89」の議事録. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  140– 149. doi :10.1145/73721.73736. ISBN 978-0-89791-308-9. S2CID  13269547。
  25. ^ ab Dantsin, Evgeny; Eiter, Thomas; Gottlob, Georg; Voronkov, Andrei (2001-09-01). 「論理プログラミングの複雑性と表現力」. ACM Computing Surveys . 33 (3): 374– 425. doi :10.1145/502807.502810. ISSN  0360-0300.
  26. ^ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (2023-01-11). 「SMTからASPへ：ソルバーベースのアプローチによるデータログ合成ルール選択問題の解決」 ACM on Programming Languages 誌7 ( POPL): 7:185–7:217. doi : 10.1145/3571200 . S2CID  253525805.
  27. ^ Zaniolo, Carlo; Yang, Mohan; Das, Ariyam; Shkapsky, Alexander; Condie, Tyson; Interlandi, Matteo (2017年9月). 「Fixpoint semantics and optimization of recursive Datalog programs with aggregates*. Theory and Practice of Logic Programming . 17 ( 5–6 ): 1048–1065 . arXiv : 1707.05681 . doi :10.1017/S1471068417000436. ISSN  1471-0684. S2CID  6272867.
  28. ^ 「第7章 ルール - LogicBlox 3.10リファレンスマニュアル」。developer.logicblox.com 。2023年3月4日閲覧。
  29. ^ 「6.4. 否定 - LogicBlox 3.10 リファレンスマニュアル」。developer.logicblox.com 。2023年3月4日閲覧。さらに、否定は、プラットフォームが否定を使用するすべてのルールと制約を階層化する方法を決定することができる場合にのみ許可されます。
  30. ^ Michael Lam; Sin Min Lee博士. 「Datalog」.コース CS 157A . サンノゼ州立大学 コンピュータサイエンス学部. 2017年3月25日時点のオリジナルよりアーカイブ。
  31. ^ Kolaitis, Phokion G.; Vardi, Moshe Y. (1990-04-02). 「データログの表現力について：ツールとケーススタディ」.第9回ACM SIGACT-SIGMOD-SIGARTシンポジウム「データベースシステムの原理」議事録. ACM. pp.  61– 71. doi :10.1145/298514.298542. ISBN 978-0-89791-352-2。 {{cite book}}:|journal=無視されました (ヘルプ)
  32. ^ Hillebrand, Gerd G; Kanellakis, Paris C; Mairson, Harry G; Vardi, Moshe Y (1995-11-01). 「データログプログラムにおける決定不能な有界性問題」. The Journal of Logic Programming . 25 (2): 163– 190. doi : 10.1016/0743-1066(95)00051-K . ISSN  0743-1066.
  33. ^ Saenz-Perez (2011)、「DES：演繹データベースシステム」、電子計算機科学理論ノート、271、ES：63-78、doi：10.1016/j.entcs.2011.02.011。
  34. ^ Differential Dataflow、2022年7月
  35. ^ Kenny, Kevin B (2014年11月12～14日). 二分決定図、リレーショナル代数、そしてDatalog: Tclのための演繹的推論(PDF) . 第21回Tcl/Tkカンファレンス. オレゴン州ポートランド. 2015年12月29日閲覧。
  36. ^ XSB システム、バージョン 3.7.x、第 1 巻: プログラマーズ マニュアル(PDF)。
  37. ^ FoundationDB Datalog Tutorial、2013年8月9日時点のオリジナルよりアーカイブ。
  38. ^ “Leapsight”. 2018年11月11日時点のオリジナルよりアーカイブ。
  39. ^ Semmle QL、2019 年 9 月 18 日。
  40. ^ "SecPAL". Microsoft Research . 2007年2月23日時点のオリジナルよりアーカイブ。
  41. ^ Lifschitz, Vladimir. 「論理プログラミングの基礎」 Principles of knowledge representation 3 (1996): 69-127. 「[Datalog] の表現力は、知識表現への有意義な応用にはあまりにも限られている。」
  42. ^ Huang、Green、Loo、「データログと新興アプリケーション」、SIGMOD 2011 (PDF)、カリフォルニア大学デービス校{{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)。
  43. ^ Mei, Hongyuan; Qin, Guanghui; Xu, Minjie; Eisner, Jason (2020). 「Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification」ICML 2020 Proceedings . arXiv : 2006.16723 .
  44. ^ チン、ブライアン;ディンクレイジ、ダニエル・フォン。エルジェゴヴァツ、ヴク。ホーキンス、ピーター。ミラー、マーク・S。ああ、フランツ。クリストファー・オルストン。ペレイラ、フェルナンド (2015)。ボール、トーマス。ボディク、ラスチスラフ。クリシュナムルティ、シュリラム。ラーナー、ベンジャミン S.モリセット、グレッグ (編)。 Yedalog: 大規模な知識の探索。第 1 回プログラミング言語の進歩に関するサミット (SNAPL 2015)。ライプニッツ国際情報学会議 (LIPIcs)。 Vol. 32. ダグシュトゥール、ドイツ: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik。 pp.  63–78 . doi : 10.4230/LIPIcs.SNAPL.2015.63。ISBN 978-3-939897-80-4。
  45. ^ Whaley, John; Avots, Dzintars; Carbin, Michael; Lam, Monica S. (2005). 「プログラム分析における二分決定図を用いたデータログの利用」 Yi, Kwangkeun (編). 『プログラミング言語とシステム』 . コンピュータサイエンス講義ノート. 第3780巻. ベルリン, ハイデルベルク: Springer. pp.  97– 118. doi :10.1007/11575467_8. ISBN 978-3-540-32247-4. S2CID  5223577。
  46. ^ Scholz, Bernhard; Jordan, Herbert; Subotić, Pavle; Westmann, Till (2016-03-17). 「Datalogにおける高速大規模プログラム解析について」. Proceedings of the 25th International Conference on Compiler Construction. CC 2016. ニューヨーク, NY, USA: Association for Computing Machinery. pp.  196– 206. doi :10.1145/2892208.2892226. ISBN 978-1-4503-4241-4. S2CID  7531543。
  47. ^ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). 「doop の Soufflé への移植」.第 6 回 ACM SIGPLAN 国際プログラム分析ワークショップの議事録. SOAP 2017. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  25– 30. doi :10.1145/3088515.3088522. ISBN 978-1-4503-5072-3. S2CID  3074689。
  48. ^ Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (2020-11-13). 「Formulog: SMTベースの静的解析のためのデータログ」. Proceedings of the ACM on Programming Languages . 4 (OOPSLA): 141:1–141:31. doi : 10.1145/3428209 . S2CID  226961727.
  49. ^ マドセン、マグナス;そう、ミンホー。ロタク、オンドジェ (2016-06-02)。 「Datalog から flix へ: 格子上の固定点の宣言型言語」。ACM SIGPLAN の通知。51 (6): 194–208。土井:10.1145/2980983.2908096。ISSN  0362-1340。
  50. ^ Gryz、Guo、Liu、Zuzarte (2004). 「DB2 Universal Databaseにおけるクエリサンプリング」(PDF) . 2004 ACM SIGMOD 国際データ管理会議議事録 - SIGMOD '04 . p. 839. doi :10.1145/1007568.1007664. ISBN 978-1581138597. S2CID  7775190。
  51. ^ ガレール、エルヴェ;ミンカー、ジョン「ジャック」編。 (1978)、「Logic and Data Bases、Symposium on Logic and Data Bases、Center d'études et de recherches de Toulouse、1977」、Advances in Data Base Theory、ニューヨーク: Plenum Press、ISBN 978-0-306-40060-5。
  52. ^ アビテブール、セルジュ、ハル、リチャード、ヴィアヌ、ビクター（1995年）、データベースの基礎、アディソン・ウェスレー、p. 305、ISBN 9780201537710。

参考文献

  • 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.
  • アビテブール, S. (1995).データベースの基礎. リチャード・ハル, ビクター・ヴィアヌ. マサチューセッツ州レディング: アディソン・ウェスリー. ISBN 0-201-53771-0OCLC  30546436 。
「https://en.wikipedia.org/w/index.php?title=データログ&oldid=1317850320」より取得