論文の概要: The Complexity of Why-Provenance for Datalog Queries
- arxiv url: http://arxiv.org/abs/2303.12773v1
- Date: Wed, 22 Mar 2023 17:37:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-23 13:20:38.935737
- Title: The Complexity of Why-Provenance for Datalog Queries
- Title（参考訳）: データログクエリの why-provenance の複雑さ
- Authors: Marco Calautti, Ester Livshits, Andreas Pieris, Markus Schneider
- Abstract要約: クエリ結果を説明する標準的な方法は、いわゆるwhy-provenanceであり、クエリ結果に証人に関する情報を、その結果を引き出すのに十分な入力データベースのサブセットの形式で提供します。
驚いたことに、なぜデータログクエリが実現したのかという概念は何十年にもわたって研究されてきたが、その計算複雑性はまだ解明されていない。
我々は、データログクエリとそのキーサブクラスに対して、なぜ保証されているのかというデータの複雑さを指摘します。
- 参考スコア（独自算出の注目度）: 3.85203215318097
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Explaining why a database query result is obtained is an essential task
towards the goal of Explainable AI, especially nowadays where expressive
database query languages such as Datalog play a critical role in the
development of ontology-based applications. A standard way of explaining a
query result is the so-called why-provenance, which essentially provides
information about the witnesses to a query result in the form of subsets of the
input database that are sufficient to derive that result. To our surprise,
despite the fact that the notion of why-provenance for Datalog queries has been
around for decades and intensively studied, its computational complexity
remains unexplored. The goal of this work is to fill this apparent gap in the
why-provenance literature. Towards this end, we pinpoint the data complexity of
why-provenance for Datalog queries and key subclasses thereof. The takeaway of
our work is that why-provenance for recursive queries, even if the recursion is
limited to be linear, is an intractable problem, whereas for non-recursive
queries is highly tractable. Having said that, we experimentally confirm, by
exploiting SAT solvers, that making why-provenance for (recursive) Datalog
queries work in practice is not an unrealistic goal.
- Abstract（参考訳）: データベースクエリ結果がなぜ得られるのかを説明することは、Explainable AIの目標、特に近年では、データログのような表現豊かなデータベースクエリ言語がオントロジーベースのアプリケーションの開発において重要な役割を担っている。
クエリ結果を説明する標準的な方法は、いわゆるwhy-provenanceであり、クエリ結果に証人に関する情報を、その結果を引き出すのに十分な入力データベースのサブセットの形式で提供します。
驚いたことに、datalogクエリの why-provenance の概念は何十年も前から徹底的に研究されてきたが、計算の複雑さはいまだに解明されていない。
この研究の目的は、なぜ進歩文学のこの明らかなギャップを埋めることである。
この目的に向けて,datalogクエリとそのキーサブクラスに対する why-provenance の複雑性を指摘する。
我々の研究の要点は、再帰的クエリの理由は、再帰的クエリが線形に制限されているとしても、難解な問題である。
それにもかかわらず、SATソルバを利用することで、(再帰的な)Datalogクエリを実際に動作させるのは非現実的な目標ではないことを実験的に確認する。
関連論文リスト
- BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrieval [54.54576644403115]
多くの複雑な実世界のクエリは、関連する文書を特定するために詳細な推論を必要とする。
BRIGHTは、関係する文書を検索するために、集中的推論を必要とする最初のテキスト検索ベンチマークである。
私たちのデータセットは、経済学、心理学、数学、コーディングなど、さまざまな領域にまたがる1,384の現実世界のクエリで構成されています。
論文 参考訳（メタデータ） (2024-07-16T17:58:27Z) - Fact-Checking Complex Claims with Program-Guided Reasoning [99.7212240712869]
Program-Guided Fact-Checking (ProgramFC)は、複雑なクレームを単純なサブタスクに分解する新しいファクトチェックモデルである。
まず,大規模言語モデルの文脈内学習能力を活用して推論プログラムを生成する。
我々は,各サブタスクを対応するサブタスクハンドラに委譲することでプログラムを実行する。
論文 参考訳（メタデータ） (2023-05-22T06:11:15Z) - Reverse Engineering of Temporal Queries Mediated by LTL Ontologies [8.244587597395936]
データベースクエリのリバースエンジニアリングでは、与えられた回答と非回答の集合からクエリを構築することを目指している。
時間スタンプデータに対して線形時間論理の正のフラグメントで定式化されたクエリに対して,このクエリ・バイ・サンプル問題について検討する。
論文 参考訳（メタデータ） (2023-05-02T08:27:39Z) - Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。
これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。
提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
論文 参考訳（メタデータ） (2023-04-14T11:35:35Z) - CAPSTONE: Curriculum Sampling for Dense Retrieval with Document
Expansion [68.19934563919192]
本稿では,学習中に擬似クエリを利用して,生成したクエリと実際のクエリとの関係を徐々に向上させるカリキュラムサンプリング戦略を提案する。
ドメイン内およびドメイン外両方のデータセットに対する実験結果から,本手法が従来の高密度検索モデルより優れていることが示された。
論文 参考訳（メタデータ） (2022-12-18T15:57:46Z) - Graph Enhanced BERT for Query Understanding [55.90334539898102]
クエリ理解は、ユーザの検索意図を探索し、ユーザが最も望まれる情報を発見できるようにする上で、重要な役割を果たす。
近年、プレトレーニング言語モデル (PLM) は様々な自然言語処理タスクを進歩させてきた。
本稿では,クエリコンテンツとクエリグラフの両方を活用可能な,グラフ強化事前学習フレームワークGE-BERTを提案する。
論文 参考訳（メタデータ） (2022-04-03T16:50:30Z) - Complexity of Arithmetic in Warded Datalog+- [1.5469452301122173]
Warded Datalog+- ロジックベースの言語Datalogを拡張し、ルールヘッドに存在量化器を配置する。
我々はWarded Datalog+を算術演算で拡張し、P完全性を証明する新しい言語を定義する。
我々は,新たに定義された言語に対する効率的な推論アルゴリズムを提案し,最近導入された整数演算を用いたデータログフラグメントの記述的複雑性を証明した。
論文 参考訳（メタデータ） (2022-02-10T15:14:03Z) - Logic Embeddings for Complex Query Answering [56.25151854231117]
skolemisationを用いて効率的なクエリのための存在変数を排除する、複雑なクエリを組み込む新しいアプローチであるlogic embeddedsを提案する。
論理組込みは,大規模で不完全な知識グラフ上でのクエリ応答において競争的に高速かつ正確であり,否定的問合せよりも優れており,特に回答の不確かさのモデリングが向上している。
論文 参考訳（メタデータ） (2021-02-28T07:52:37Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。
我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。
一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文 参考訳（メタデータ） (2020-06-07T14:47:07Z) - Containment of Simple Regular Path Queries [1.869065967043578]
クエリの包含をテストすることは、知識表現における基本的な推論タスクである。
ここでは厳格に制限された断片に焦点をあてるが、実際には非常に関連性が高いことが知られている。
クエリの正規表現で使用される機能によらず,np, pitwo, pspace, expspace の完全性の結果が得られた。
論文 参考訳（メタデータ） (2020-03-09T21:05:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。