ヴァダログ

Vadalogは、知識グラフ上で複雑な論理推論タスクを実行するシステムです。その言語は、ルールベース言語Datalogの拡張であるWarded Datalog ^±に基づいています。^[1]

Vadalogは、オックスフォード大学とウィーン工科大学の研究者とイタリア銀行の従業員によって開発されました。

ナレッジグラフ管理システム（KGMS）は、事実と関係性の形で大量のデータを組み込んだナレッジグラフを管理する必要があります。一般的に、それは3つのコンポーネントの結合として見ることができます：^[2]

1. KBMS、つまり知識ベース管理システムは、
2. ビッグデータとは、大量のデータを処理する必要性であり、特にナレッジグラフは、企業と公共の知識の両方を含む複数のデータソースを統合するためのソリューションとして考えられており、大規模なナレッジグラフに統合できることを考えると、
3. (データ) 分析とは、機械学習、テキスト マイニング、データ分析、データ視覚化のための既存のソフトウェア パッケージへのアクセスを提供し、それらを同じプラットフォームに組み合わせる必要があることを意味します。

より技術的な観点から、適切な KGMS を定義するためのいくつかの追加要件を特定できます。

• 高い表現力を持つ言語と形式主義の定義、^{[3] [4]}
• データのクリーニングからウェブデータの抽出、さまざまなソースからのビッグデータへのアクセスまで、あらゆるステップでコスト効率の高いデータラングリングを行う。 ^[5]
• 効率的な論理的、確率的、存在論的推論、^{[6] [2]}
• 空間複雑度（ビッグデータを扱う場合）と構文の両面で複雑度が低い。
• 企業のRDBMS、NoSQLやRDFストア、ウェブ、機械学習、分析パッケージなど、さまざまな異種データソースにアクセスするためのインターフェース（API ）。 ^[7]

その他の要件には、Coddが提案したような、より一般的なDBMS機能やサービスが含まれる場合があります。^[8]

Vadalogは、上記のKGMSの要件をすべて満たすプラットフォームを提供しています。知識グラフ上でルールベースの推論タスクを実行でき、データの視覚化や機械学習などのデータサイエンスワークフローもサポートしています。^[2]

ルールは、 n  :− a ₁ , ..., a _nという形式の表現です。ここで、

• a ₁ , ..., a _{n は}物体の原子であり、
• n はヘッドの原子です。

ルールを使用すると、本体にある変数から新しい知識を推論できます。ルールの本体にあるすべての変数が正常に割り当てられると、ルールがアクティブになり、ヘッド述語が導出されます。データベースDとルール セットΣが与えられた場合、推論タスクは、セットΣのルールをデータベースD (拡張的知識) に適用して、新しい知識を推論することを目的とします。

過去数十年にわたって採用されてきた最も広範な知識の形態は、ルールベースシステム、オントロジーベースシステム、またはその他の形態のルールの形態であり、通常はナレッジグラフに記録できます。^{[7]ナレッジグラフの性質上、これらのルールにおける}再帰の存在も特に重要な側面となります。再帰とは、推論タスクの最終的な答えを得る前に同じルールが複数回呼び出される可能性があることを意味し、以前に推論された結果に基づく推論を可能にするため特に強力です。これは、システムが終了を保証する戦略を提供しなければならないことを意味します。より技術的には、ルールの適用によって構築された依存関係グラフが循環的である場合、プログラムは再帰的です。最も単純な形式の再帰は、ルールのヘッドが本体にも現れるものです (自己再帰ルール)。

Vadalog言語は、再帰も含む推論クエリに答えることができます。これは、ルールヘッドに存在量指定子を追加してDatalogを拡張し[9]、同時に決定可能性と扱いやすさを実現するために^構文を制限した^Datalog ±言語ファミリーに^属するWarded Datalog ±に基づいています。^{[10] [11]存在ルールは、}タプル生成依存関係（tgds ） としても知られています。^[12]

存在規則の形式は次のとおりです。

${\displaystyle \varphi (x)\Rightarrow \exists z\Psi (x,z)}$

または、Datalog 構文では次のように記述することもできます。

p ( X , Z )  :  -r ( X ) です。

Vadalog の変数は、一階論理の変数に似ており、変数はそれが発生するルールに対してローカルです。つまり、異なるルールで同じ変数名が発生した場合、異なる変数を参照します。

次のような 一連のルールの場合:${\displaystyle \Sigma }$

r ( X , Y )  :-  p ( X )。p 
( Z ) :- r ( X , Z ) 。  

2番目のルールの変数Zは危険であると言われています。これは、最初のルールがアトムrの2番目の項にヌルを生成し、これが2番目のルールに注入されてアトムpを取得し、プログラムの回答を見つけようとするときにヌルの伝播につながるためです。任意の伝播が許可されている場合、推論は決定不能であり、プログラムは無限になります。^[7] Warded Datalog ^±は、セットで定義されたすべてのルールに対して、ルール本体のすべての変数が、ワードと呼ばれるヘッドの少なくとも1つのアトムに共存する必要があることを要求することで、この問題を解決します。ワードの概念は、プログラム内で危険な変数を使用する方法を制限します。これは表現力の点で制限ですが、この要件とアーキテクチャと終了アルゴリズムのおかげで、 Warded Datalog ^±は有限数のステップでプログラムへの回答を見つけることができます。また、計算の複雑さと表現力の間の適切なトレードオフを示し、オントロジー推論と再帰によるプログラムの実行を可能にしながら、PTIMEデータの複雑さをキャプチャします。 ^[13]${\displaystyle \Sigma }$

^{Vadalog は Warded Datalog ±}を完全に複製し、以下の言語を追加して拡張します。

• 単調な集計（min、max、sum、prod、count演算子）、^[14]
• 重層否定、
• さまざまなデータ型のサポート（文字列、整数、倍精度、日付、ブール値、セット、リスト、マークされたヌル）
• データ ソースや外部ライブラリと対話する方法を定義するための豊富な注釈メカニズム。

さらに、このシステムは、効率的な計算を可能にするために高度に設計されたアーキテクチャを提供します。これは、次の 2 つの方法で行われます。

1. メモリ内処理アーキテクチャとプルストリーム ベースのアプローチを採用することで、メモリ消費を制限したり予測可能にしたりします。
2. 積極的な終了制御戦略を使用して、（答えを生成するために使用される）追跡グラフの構築中にパターンと冗長性をできるだけ早く検出し、それらが発生したときに計算を中止します。^{[7]これは、事実の}同型性の概念と関連しており、答えを得るために必要なステップ数を減らします。事実hがh'と同型である場合、システムは事実hの追跡グラフのみを探索します。^[15]

VadalogシステムはDatalogファミリーに属しているため、オントロジー推論タスクを実行できます。Vadalogの論理コアによる推論は、OWL 2 QLとSPARQL ^[16]（存在量指定子の使用による）とグラフ分析（再帰と集約のサポートによる）をキャプチャします。

次の Vadalog ルール セットを検討してください。

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

最初のルールは、各人物に先祖 が存在することを述べています。2 番目のルールは、が の親である場合、も の先祖であると述べています。最初のルールの先祖述語の最初の位置にある存在量化に注目してください。これにより、追跡手順で null ν _iが生成されます。この null は、2 番目のルールの先頭に伝播されます。外延的事実を含むデータベースと、推論タスクとして、含意される先祖事実をすべて見つけるクエリについて考えてみましょう。 ${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Z}$${\displaystyle Y}$${\displaystyle Z}$D = {person(Alice), person(Bob), parent(Alice,Bob)}

チェイス手順を実行すると、の最初のルールがトリガーされてファクトが生成されます。次に、およびの 2 番目のルールがアクティブ化されて が作成されます。最後に、 で最初のルールがトリガーされる可能性がありますが、結果として得られるファクトはと同型であるため、このファクトは生成されず、チェイス グラフの対応する部分は探索されません。 ancestor(ν1,Alice)person(Alice)ancestor(ν1,Bob)ancestor(ν1,Alice)parent(Alice,Bob)person(Bob)ancestor(ν2,Bob)ancestor(ν1,Bob)

結論として、クエリに対する答えは事実の集合です。 {ancestor(ν1,Alice), ancestor(ν1,Bob)}

Vadalogとデータサイエンスツールの統合は、データバインディングプリミティブと関数によって実現されます。^[7]

1. データ バインディング プリミティブ:バインディングを使用すると、データベース、フレームワーク、ライブラリなどの外部データ ソースまたはシステムに接続し、それらの処理方法をシステムに指示できます。これには、PostgreSQLやMySQLなどのリレーショナル データベース システムや、 Neo4jなどのグラフ データベースとの接続が含まれます。機械学習ライブラリ ( Weka、scikit-learn、Tensorflow ) と Web データ抽出ツール OXPathを統合して、Web から直接データを取得することもできます。これは、いわゆる注釈によって可能になります。注釈は、存在規則のセットを特定の動作で拡張する特別なファクトです。@input注釈は、プログラムのアトムのファクトがリレーショナル データベースなどの外部データ ソースからインポートされたことをシステムに伝えます。注釈は、プログラム@outputのアトムのファクトが標準出力やリレーショナル データベースなどの外部ターゲットにエクスポートされることを指定します。、、などの他の注釈を使用すると@bind、@mapping注釈のデータ ソースまたは注釈のターゲット@qbindをカスタマイズできます。@input@output
2. 関数:算術演算子、文字列操作、比較を使用するカスタム式もサポートされます。Python で記述されたライブラリも有効になっており、専用のアノテーションを使用して統合できます@library。

このシステムはJupyterLabプラットフォームとの統合も提供しており、プラットフォームの機能を活用して Vadalog プログラムを作成して実行し、出力を読み取ることができます。また、構文の強調表示、コード分析(コードが正しいかエラーがあるかを確認)、結果の説明(結果がどのように得られたか) などのツールを使用して、プログラムの正確性を評価し、実行し、出力ファクトの導出プロセスを分析することもできます。これらの機能はすべてノートブックに埋め込まれており、Vadalog コードの作成と分析に役立ちます。

Vadalogシステムは、さまざまな研究分野や産業分野の多くの実際のユースケースに対応するために使用できます。^[3]後者の中で、このセクションでは、金融分野に属する関連性がありアクセスしやすい2つのケースを紹介します。^{[17] [18] [19]}

会社の所有権グラフでは、エンティティがノードとして、株式がエッジとして表示されます。あるエンティティが別のエンティティの株式を一定量保有している場合 (通常は絶対多数として識別されます)、そのエンティティは別のエンティティに対して決定権を行使することができ、これによって会社のコントロールが構成され、より一般的にはグループ構造が構成されます。すべてのコントロール関係を検索するには、さまざまなシナリオと非常に複雑なグループ構造 (直接コントロールと間接コントロール) を調査する必要があります。このクエリは、次のルールに変換されます。

• X社がY社の総株式の50%以上を直接所有している場合、 X社はY社を直接支配していることになる。
• 会社X が、 Yの株式を共同で（つまり、合計で） 50% 以上所有する中間会社の集合を支配している場合、会社Yは間接的に会社Yを支配していることになります。

これらのルールは、次のようにすべての制御エッジ を導出する Vadalog プログラムで記述できます。

コントロール( X 、X )  ：- 会社( X )。
コントロール( X 、Y )  ：- コントロール( X 、Y ) 、 所有( Y 、Z 、W ) 、 V  = 合計( W 、<Y> )、V > 0.5 。   

最初のルールは、各企業が自らを管理することを規定しています。 2 番目のルールは、 Xが管理するすべての企業Yに対して企業Y が保有するZの株式を合計することによって、 XによるZの支配を定義します。

このシナリオは、企業の所有権グラフ内の 2 つのエンティティ間にリンクが存在するかどうかを判断することです。このようなリンクの存在を判断することは、たとえば銀行監督や信用力評価に関係します。なぜなら、2 つの企業がこのような関係を共有している場合、企業は別の企業への融資の保証人になることはできないからです。正式には、次の場合に 2 つの企業XとYは密接なリンクに関係しています。

• x (resp., Y )は直接または間接的にY (resp., X )の株式の20%以上を所有している、または
• 共通の第三者であるZ は、 XとY両社の株式の 20% 以上を直接または間接的に所有しています。

これらのルールは、次のようにすべての近いリンクエッジ を導出する Vadalog プログラムで記述できます。

mcl ( X , Y , S )  :-  own ( X , Y , S )。
mcl ( X 、Z 、S1  *  S2 )  :-  mc1 ( X 、Y 、S1 )、 own ( Y 、Z 、S2 )。
cl1 ( X , Y )  :-  mcl ( X , Y , S )、 TS  =  sum ( S )、 TS  >  0.2 。
cl2 ( X , Y )  :-  cl1 ( Z , X )、 cl1 ( Z , Y )、 X  ! =  Y 。
クローズリンク( X , Y )  :-  cl1 ( X , Y )。
クローズリンク( X , Y )  :-  cl2 ( X , Y )。

最初のルールは、所有権エッジで接続された2 つの企業XとY は、可能なクローズ リンクであると述べています。2 番目のルールは、 XとY が株式S1で可能なクローズ リンクであり、 Yから株式S2で企業Zへの所有権エッジが存在する場合、XとZも株式S1 * S2で可能なクローズ リンクであると述べています。3 番目のルールは、 Xが直接または間接的に所有するYの部分株式Sの合計がYの株式の 20% 以上である場合、それらは最初の定義に従ってクローズ リンクであると述べています。4 番目のルールは、クローズ リンクの 2 番目の定義、つまりサードパーティのケースをモデル化しています。

• データログ
• プロローグ
• データベース
• セマンティック Web ルール言語
• グラフデータベース