論文の概要: How Hard is it to Decide if a Fact is Relevant to a Query?

• arxiv url: http://arxiv.org/abs/2604.22422v1
• Date: Fri, 24 Apr 2026 10:29:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-27 15:36:26.424581
• Title: How Hard is it to Decide if a Fact is Relevant to a Query?
• Title（参考訳）: Fact が Query に関連があるかどうかを判断するのはどのくらい難しいか?
• Authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade,
• Abstract要約: データベース D が与えられたとき、ブール共役クエリ (CQ) q と D の事実 f は、f が q wrt に関連するかどうかを決定する。 自己結合(同じ関係を持つ複数の原子)を犯人とみなす。 この結果から,クエリ評価よりも関連性の判断が困難であることや,効率のよい関連性計算を許容するクエリの自然クラスを同定した。
• 参考スコア（独自算出の注目度）: 1.6058099298620423
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the following fundamental problem: given a database D, Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt. D, i.e., does f belong to a minimal subset S of D such that S |= q. Despite being of central importance to query answer explanation, the combined complexity of deciding query relevance has not been studied in detail, leaving open what makes this problem hard, and which restrictions can yield lower complexity. Relevance has already been shown to be harder than query evaluation: namely, $Σ^p_2$-complete for CQs, even over a binary signature. We further observe that NP-hardness applies already to (acyclic) chain CQs. Our work identifies self-joins (multiple atoms with the same relation) as the culprit. Indeed, we prove that if we forbid or bound the occurrence of self-joins, then relevance has the same complexity as query evaluation, namely, NP (without structural restrictions) and LogCFL (for bounded hypertreewidth classes). In the ontology setting, we establish an analogous result for ontology-mediated queries consisting of a CQ and DL-Lite_R ontology, namely that relevance is no harder than query answering provided that we bound the interaction width (which generalizes both self-join width and a recently introduced 'interaction-free' condition). Our results thus pinpoint what makes relevance harder than query evaluation and identify natural classes of queries which admit efficient relevance computation.
• Abstract（参考訳）: データベース D, ブール共役クエリ (CQ) q, 事実 f in D が与えられたとき、f が q wrt に関連するか否かを決定する。 つまり、f は D の最小部分集合 S に属して S |= q となる。 問合せ説明の中心的な重要性にもかかわらず、問合せ関連性を決定するための複合的な複雑さは、詳細は研究されておらず、この問題を困難にしているのは、どの制限がより少ない複雑さをもたらすかである。 関連性はすでにクエリ評価よりも難しいことが示されている。すなわち、バイナリシグネチャでさえ、CQに対して$Σ^p_2$-completeである。 さらに、NP-ハードネスが(非環状)鎖 CQ に対して既に適用されていることを観察する。 我々の研究は、犯人と自己結合(同じ関係を持つ複数の原子)を識別する。 実際、自己結合の発生を禁止または制限すると、関係性はクエリ評価と同じ複雑さ、すなわちNP(構造的制約無し)とLogCFL(境界超ツリー幅クラス)を持つことが証明される。 オントロジー設定では、CQおよびDL-Lite_Rオントロジーからなるオントロジーによるクエリの類似結果を確立する。 この結果から,クエリ評価よりも関連性の判断が困難であることや,効率のよい関連性計算を許容するクエリの自然クラスを同定した。

関連論文リスト

• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  そこで我々は,論理的推論から述語レベルの妥当性推定を分離するニューロシンボリック検索フレームワークOrLogを紹介する。 大規模言語モデル (LLM) は1つの復号のない前方通過において原子述語に対する可視性スコアを提供し、確率論的推論エンジンはクエリ満足度の後方確率を導出する。
  論文  参考訳（メタデータ） (2026-01-30T15:31:58Z)
• Tractable Responsibility Measures for Ontology-Mediated Query Answering [3.1952340441132474]
  オントロジーによる問合せ応答の設定における計算責任スコアの複雑さについて検討する。 このような測定は、一階述語クエリのクラスで最小限のデータ複雑性を享受できることを示す。 言語が協調してサポートしている場合、アトミッククエリにインタラクタビリティがすでに適用されていることを証明します。
  論文  参考訳（メタデータ） (2025-07-31T02:08:12Z)
• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  複雑なクエリに対する効率的でスケーラブルなシンボル検索フレームワークを提案する。 我々のフレームワークは、ほぼ同じ性能を維持しながら、シンボリックメソッドの計算負荷を90%削減する。
  論文  参考訳（メタデータ） (2025-05-13T01:24:09Z)
• GRS-QA -- Graph Reasoning-Structured Question Answering Dataset [50.223851616680754]
  グラフ推論-構造化質問応答データセット(GRS-QA)を導入する。 既存のM-QAデータセットとは異なり、GRS-QAは推論グラフを構築することで複雑な推論経路を明示的にキャプチャする。 実験により, LLMは, 様々な推論構造を用いて, 問合せ処理を行う際に, 異なる性能を示すことが明らかとなった。
  論文  参考訳（メタデータ） (2024-11-01T05:14:03Z)
• Answering Fuzzy Queries over Fuzzy DL-Lite Ontologies [0.2741266294612776]
  ファジィDL-Liteにおける接続クエリとしきい値クエリに応答する問題について検討する。 idemdent G"odel t-norm に対して、古典的ケースへの還元に基づく効果的な方法を提案する。
  論文  参考訳（メタデータ） (2021-11-23T10:45:54Z)
• The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard [11.193504036335503]
  論理に基づく知識表現では、クエリ応答は基本的に単に満足度チェックに置き換えられている。 基本記述論理 ALC の知識ベースでは、連結クエリ(CQ)応答の計算複雑性はExpTime-complete であることが知られている。 自己演算子のみによるALCの拡張さえも,CQ含意の複雑さを2ExpTimeに高めることを示す。
  論文  参考訳（メタデータ） (2021-06-29T08:12: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)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  関係データベース上でのオントロジーによるクエリの評価について検討する。 OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。 また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
  論文  参考訳（メタデータ） (2020-03-17T16:32:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。