ヴァダログ
Type of Knowledge Graph Management System
ヴァダログ
パラダイム論理、宣言的
家族データログ
デザイン：オックスフォード大学、ウィーン工科大学、イタリア銀行

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

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

ナレッジグラフ管理システム（KGMS）

KGMSリファレンスアーキテクチャ

ナレッジグラフ管理システム（KGMS）は、事実と関係性の形で大量のデータを統合したナレッジグラフを管理する必要があります。一般的に、KGMSは以下の3つのコンポーネントの集合体として考えることができます。[2]

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

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

  • 高い表現力を持つ言語と形式主義の定義、[3] [4]
  • データのクリーニングからウェブデータの抽出、そして様々なソースからのビッグデータへのアクセスまで、あらゆる段階で費用対効果の高いデータラングリングを行う。 [5]
  • 効率的な論理的、確率的、オントロジー的推論、[6] [2]
  • 空間計算量（ビッグデータを扱う場合）と構文の両面で複雑さが低い
  • 企業のRDBMS、NoSQLやRDFストア、ウェブ、機械学習、分析パッケージなど、多くの異種データソースにアクセスするためのインターフェース（API ）。 [7]

その他の要件には、コッドが提案したような、より一般的なDBMS機能やサービスが含まれる可能性がある。[8]

Vadalogシステム

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

推論課題と再帰

循環依存グラフ

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

  • a 1 , ..., a nは物体の原子であり、
  • nは頭部の原子です。

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

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

クエリ言語

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

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

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

Vadalog拡張機能

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番目の規則は、が の親である場合、もの先祖であると述べています。最初の規則の先祖述語の最初の位置に存在する量化に注目してください。これにより、追跡手続きにおいてヌル ν iが生成されます。このヌルは、2番目の規則の先頭に伝播されます。外延的事実を含むデータベースと、推論タスクとして、含意される先祖事実をすべて見つけるというクエリを考えてみましょう。 X {\displaystyle X} Y {\displaystyle Y} X {\displaystyle X} Z {\displaystyle Z} Y {\displaystyle Y} Z {\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 から直接データを取得できる Web データ抽出ツール OXPathを統合することもできます。これは、いわゆるアノテーションを通じて可能になります。アノテーションは、存在ルールのセットを特定の動作で拡張する特別なファクトです。@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がZを支配するか否かを、企業Yが保有するZの株式を合計し、 Xが支配するすべての企業Yに配分することで定義します。

このシナリオは、企業の所有権グラフにおいて、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番目の定義、つまりサードパーティのケースをモデル化しています。

参照

参考文献

  1. ^ Bellomarini, Luigi; Sallinger, Emanuel; Gottlob, Georg (2018-05-01). 「Vadalogシステム：知識グラフのためのデータログベース推論」 . VLDB Endowment Proceedings . 11 (9): 975– 987. doi :10.14778/3213880.3213888. ISSN  2150-8097. S2CID  49300741.
  2. ^ abc Bellomarini, Luigi; Gottlob, Georg; Pieris, Andreas; Sallinger, Emanuel (2018). 「ビッグデータとナレッジグラフのためのSwiftロジック」. Tjoa, A Min; Bellatreche, Ladjel; Biffl, Stefan; van Leeuwen, Jan; Wiedermann, Jiří (編). SOFSEM 2018: コンピュータサイエンスの理論と実践. コンピュータサイエンス講義ノート. 第10706巻. シュプリンガー・インターナショナル・パブリッシング. pp.  3– 16. doi :10.1007/978-3-319-73117-9_1. hdl :20.500.11820/ea876c0e-2cde-47e7-a38a-7898a35e635b. ISBN 978-3-319-73117-9. S2CID  3193327。
  3. ^ ab Bellomarini, Luigi; Fakhoury, Daniele; Gottlob, Georg; Sallinger, Emanuel (2019). 「ナレッジグラフとエンタープライズAI：実現技術の将来性」. 2019 IEEE 第35回国際データエンジニアリング会議 (ICDE) . マカオ, マカオ: IEEE. pp.  26– 37. doi :10.1109/ICDE.2019.00011. ISBN 978-1-5386-7474-1. S2CID  174818761。
  4. ^ 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.
  5. ^ Konstantinou, Nikolaos; Koehler, Martin; Abel, Edward; Civili, Cristina; Neumayr, Bernd; Sallinger, Emanuel; Fernandes, Alvaro AA; Gottlob, Georg; Keane, John A.; Libkin, Leonid; Paton, Norman W. (2017-05-09). 「コスト効率の高いデータラングリングのためのVADAアーキテクチャ」. 2017 ACM International Conference on Management of Data の議事録(PDF) . SIGMOD '17. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp.  1599– 1602. doi :10.1145/3035918.3058730. hdl : 20.500.11820/36295a10-0b57-48a8-82ac-19d856815a89 . ISBN 978-1-4503-4197-4. S2CID  11521729。
  6. ^ Cali`, Andrea; Gottlob, Georg; Pieris, Andreas (2012年12月1日). 「より表現力豊かなオントロジー言語を目指して：クエリ応答問題」.人工知能. 193 : 87–128 . doi : 10.1016/j.artint.2012.08.002 . ISSN  0004-3702.
  7. ^ abcde ベッロマリーニ、ルイージ;フェイズラクマノフ、ルスラン R.ゴットロブ、ゲオルグ。クラフチェンコ、アンドレイ。ラウレンツァ、エレオノーラ。ネノフ、ヤヴォル。ライスフェルダー、ステファン。サリンジャー、エマニュエル。シェルホノフ、エフゲニー。ウー、リアンロン（2018-07-23）。 「Vadalog を使用したデータ サイエンス: 機械学習と推論の橋渡し」。arXiv : 1807.08712 [cs.DB]。
  8. ^ コノリー、トーマス・M.、ベッグ、キャロリン・E. (2014). 『データベースシステム ― 設計・実装・管理への実践的アプローチ（第6版）』 ピアソン. ISBN 978-1292061184。
  9. ^ Calì, Andrea; Gottlob, Georg; Lukasiewicz, Thomas (2012-07-01). 「オントロジー上での扱いやすいクエリ回答のための汎用的なDatalogベースフレームワーク」 . Journal of Web Semantics . ウェブ・オブ・データの混乱への対処に関する特集号. 14 : 57–83 . doi :10.1016/j.websem.2012.03.001. ISSN  1570-8268.
  10. ^ アビテブール, セルジュ; ハル, リチャード; ヴィアヌ, ビクター (1995). 『データベースの基礎：論理レベル』（第1版）. 米国: Addison-Wesley Longman Publishing Co., Inc. ISBN 978-0-201-53771-0。
  11. ^ Calì, Andrea; Gottlob, Georg; Lukasiewicz, Thomas; Marnette, Bruno; Pieris, Andreas (2010). 「Datalog+/-: 新しいアプリケーションのための論理的知識表現およびクエリ言語ファミリー」2010 第25回IEEEコンピュータサイエンスにおける論理シンポジウム. pp.  228– 242. doi :10.1109/LICS.2010.27. ISBN 978-1-4244-7588-9. S2CID  16829529。
  12. ^ Bellomarini, Luigi; Fayzrakhmanov, Ruslan R.; Gottlob, Georg; 他 (2022年4月). 「Vadalogによるデータサイエンス：機械学習と推論を用いた実践的なナレッジグラフ」 . Future Generation Computer Systems . 129 : 407–422. doi :10.1016/j.future.2021.10.021. ISSN  0167-739X. S2CID 243885469  .
  13. ^ Bellomarini, Luigi; Benedetto, Davide; Gottlob, Georg; Sallinger, Emanuel (2022-03-01). 「Vadalog: 大規模知識グラフを用いた自動推論のための最新アーキテクチャ」情報システム105 101528. doi : 10.1016/j.is.2020.101528. ISSN  0306-4379. S2CID  218964910.
  14. ^ Shkapsky, Alexander; Yang, Mohan; Zaniolo, Carlo (2015). 「DeALSにおける単調な集約を用いた再帰クエリの最適化」. 2015 IEEE 31st International Conference on Data Engineering . pp.  867– 878. doi :10.1109/ICDE.2015.7113340. ISBN 978-1-4799-7964-6. S2CID  5345997。
  15. ^ Bellomarini, Luigi; Laurenza, Eleonora; Sallinger, Emanuel; Sherkhonov, Evgeny (2020). 「知識グラフにおける不確実性下での推論」. Gutiérrez-Basulto, Víctor; Kliegr, Tomáš; Soylu, Ahmet; Giese, Martin; Roman, Dumitru (編). 『ルールと推論』 . コンピュータサイエンス講義ノート. 第12173巻. シュプリンガー・インターナショナル・パブリッシング. pp.  131– 139. doi :10.1007/978-3-030-57977-7_9. ISBN 978-3-030-57977-7. S2CID  221193385。
  16. ^ Gottlob, G.; Pieris, Andreas (2015). 「OWL 2 QL含意レジームにおけるSPARQLを超えて：救済策となるルール」IJCAI . S2CID  6980701.
  17. ^ Atzeni, Paolo; Bellomarini, Luigi; Iezzi, Michela; Sallinger, Emanuel; Vlad, Adriano. 「企業ナレッジグラフの織り込み：企業オーナーシップグラフの事例」（PDF）EDBT : 555--566 .
  18. ^ アツェーニ、パオロ;ベッロマリーニ、ルイージ。イエッツィ、ミケーラ。サリンジャー、エマニュエル。ヴラド、アドリアーノ（2020）。 「ロジックベースのナレッジ グラフの拡張: 企業グラフの場合」(PDF)。Kr4L@ エカイ: 22--27。
  19. ^ Baldazzi, Teodoro; Benedetto, Davide; Brandetti, Matteo; Vlad, Adriano; Bellomarini, Luigi; Sallinger, Emanuel (2022). 「ナレッジグラフ上のヒューリスティックを用いたデータログベース推論」(PDF) .国際データログ2.0ワークショップ.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Vadalog&oldid=1308122002"