論文の概要: Answering Path Queries under Linear and Guarded Existential Rules

• arxiv url: http://arxiv.org/abs/2607.22636v1
• Date: Mon, 22 Jun 2026 09:34:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-02 22:55:38.998497
• Title: Answering Path Queries under Linear and Guarded Existential Rules
• Title（参考訳）: リニアおよびガード付き実例規則に基づく経路クエリーの解答
• Abstract要約: 我々は,(C)RPQの解答はデータ複雑性においてNL完全であることが示され,これは通常のグラフデータベース上でのRPQの解答の複雑さと一致することを示す。 ガードされたルールに対しては、線形ケースを非自明に還元し、(C)RPQ応答の複雑さがCQと同じであることを示す。
• 参考スコア（独自算出の注目度）: 2.4779082385578337
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ontology-mediated query answering is concerned with the problem of answering queries over knowledge bases consisting of a database instance and an ontology. While most work in the area focuses on conjunctive queries (CQs), navigational queries have gained increasing attention. In this paper, we investigate the complexity of answering two-way (conjunctive) regular path queries ((C)RPQs) over knowledge bases whose ontology is given by a set of guarded existential rules. We first consider the subclass of linear existential rules and show that (C)RPQ answering is NL-complete in data complexity, which matches the data complexity of answering RPQs over plain graph databases (i.e., without an ontology). In combined complexity, both tasks are ExpTime-complete in the general case, but RPQ and CRPQ answering drop to PTime-complete and PSpace-complete respectively if there is a bound on predicate arity. For guarded rules, we provide a non-trivial reduction to the linear case, which allows us to show that the complexity of (C)RPQ answering is the same as for CQs, namely 2ExpTime-complete in combined complexity (ExpTime-complete in the bounded-arity case) and PTime-complete in data complexity.
• Abstract（参考訳）: オントロジーによる問合せ応答は、データベースインスタンスとオントロジーからなる知識ベース上での問合せ応答の問題に関係している。 この分野の作業の多くは接続型クエリ(CQ)に重点を置いているが、ナビゲーション型クエリはますます注目を集めている。 本稿では,保護された存在規則の集合によってオントロジーが与えられる知識ベースに対して,双方向(接続型)正規経路クエリ((C)RPQ)に応答する複雑性について検討する。 まず、線形存在規則のサブクラスを考察し、(C)RPQ応答がデータ複雑性においてNL完全であることを示す。 複合複雑性では、どちらのタスクもExpTime完全であるが、述語アリティに制限がある場合、RPQ と CRPQ は PTime完全 と PSpace完全 にそれぞれ答える。 これにより、(C)RPQ 応答の複雑さが CQ と同じであることを示すことができる。

関連論文リスト

• The benefits of query-based KGQA systems for complex and temporal questions in LLM era [55.20230501807337]
  大規模言語モデルは質問回答(QA)に優れていますが、マルチホップ推論や時間的質問には苦戦しています。 クエリベースの知識グラフ QA (KGQA) は、直接回答の代わりに実行可能なクエリを生成するモジュール形式の代替手段を提供する。 WikiData QAのためのマルチステージクエリベースのフレームワークについて検討し、課題のあるマルチホップと時間ベンチマークのパフォーマンスを向上させるマルチステージアプローチを提案する。
  論文  参考訳（メタデータ） (2025-07-16T06:41:03Z)
• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  複雑なクエリに対する効率的でスケーラブルなシンボル検索フレームワークを提案する。 我々のフレームワークは、ほぼ同じ性能を維持しながら、シンボリックメソッドの計算負荷を90%削減する。
  論文  参考訳（メタデータ） (2025-05-13T01:24:09Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。 本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。 オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
  論文  参考訳（メタデータ） (2024-03-21T13:52:30Z)
• Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
  我々は、異なる複雑なクエリタイプではなく、異なる論理演算子型が一般化性を向上させる鍵であると主張する。 本稿では,メタ演算子を限られたデータで学習し,様々な複雑なクエリの演算子のインスタンスに適応するメタ学習アルゴリズムを提案する。 実験結果から,メタオペレータの学習は,従来のCQAモデルやメタCQAモデルよりも効果的であることが示唆された。
  論文  参考訳（メタデータ） (2024-03-15T08:54:25Z)
• Adapting Neural Link Predictors for Data-Efficient Complex Query Answering [45.961111441411084]
  本稿では,複雑な問合せタスクに対して,ニューラルネットワーク予測スコアを再校正するために最適化されたパラメータ効率のスコア強調モデルを提案する。 CQD$mathcalA$は現在の最先端手法よりもはるかに正確な結果が得られる。
  論文  参考訳（メタデータ） (2023-01-29T00:17:16Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  本稿では,ニューラルネットワーク演算子から知識グラフの埋め込みを分解する,複雑な問合せ応答のためのフレームワークを提案する。 クエリグラフの上に、局所的な原子式上のワンホップ推論とグローバル論理的推論を結びつける論理メッセージパッシングニューラルネットワーク(LMPNN)を提案する。 我々のアプローチは、最先端のニューラルCQAモデルをもたらす。
  論文  参考訳（メタデータ） (2023-01-21T02:34:06Z)
• Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
  我々は、クエリ言語、結合正則経路クエリの結合(UCRPQ)を考える。 記述論理 ALC を用いて,UCRPQ の包含のための厳密な 2EXP バウンドを示す。 入力オートマトンの背後にある決定論的有限オートマトンによって誘導される解釈の階層化を導入する新しいオートマトンベースの技術がある。
  論文  参考訳（メタデータ） (2022-04-29T17:38:13Z)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  本稿では,知識グラフにエッジを欠いた複雑な論理的クエリに応答するクエリ埋め込み手法を提案する。 回答エンティティは、エンティティの埋め込みとクエリの埋め込みの類似性に応じて選択される。 埋め込み空間上の様々な領域から多様な回答を検索するために,複雑なKGクエリ応答方法Q2Pを提案する。
  論文  参考訳（メタデータ） (2022-04-27T11:16:08Z)
• 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)
• Answering Counting Queries over DL-Lite Ontologies [0.0]
  本稿では,クエリをカウントする一般的な形式を導入し,従来の提案に関連付けるとともに,そのようなクエリに答えることの複雑さについて検討する。 我々は、複雑性境界の改善を確立させる、実践的に関連するいくつかの制約について検討する。
  論文  参考訳（メタデータ） (2020-09-02T11:10:21Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  Description Logics (DL) におけるプライバシ保護クエリ応答に関する研究 DL-Lite$_mathcal$$で応答するデータ複雑性の結果を導出します。 我々は,CQEに対する近似秘密性解答という意味論的に確立された概念を同定する。
  論文  参考訳（メタデータ） (2020-04-24T17:28:24Z)
• Containment of Simple Regular Path Queries [1.869065967043578]
  クエリの包含をテストすることは、知識表現における基本的な推論タスクである。 ここでは厳格に制限された断片に焦点をあてるが、実際には非常に関連性が高いことが知られている。 クエリの正規表現で使用される機能によらず,np, pitwo, pspace, expspace の完全性の結果が得られた。
  論文  参考訳（メタデータ） (2020-03-09T21:05:29Z)

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

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