論文の概要: Computational Complexity of Preferred Subset Repairs on Data-Graphs

• arxiv url: http://arxiv.org/abs/2402.09265v2
• Date: Mon, 27 May 2024 15:24:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-29 07:25:03.163253
• Title: Computational Complexity of Preferred Subset Repairs on Data-Graphs
• Title（参考訳）: データグラフ上の優先サブセット修復の計算複雑性
• Authors: Nina Pardal, Santiago Cifuentes, Edwin Pin, Maria Vanina Martinez, Sergio Abriola,
• Abstract要約: データ値を持つグラフデータベースを優先的に修復する問題について検討する。 本稿では,標準的なサブセット修復セマンティクスに基づいて,いくつかの選好基準を示す。 優先基準が適用できない場合と同様の計算複雑性を維持可能であることを示す。
• 参考スコア（独自算出の注目度）: 2.254434034390529
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Preferences are a pivotal component in practical reasoning, especially in tasks that involve decision-making over different options or courses of action that could be pursued. In this work, we focus on repairing and querying inconsistent knowledge bases in the form of graph databases, which involves finding a way to solve conflicts in the knowledge base and considering answers that are entailed from every possible repair, respectively. Without a priori domain knowledge, all possible repairs are equally preferred. Though that may be adequate for some settings, it seems reasonable to establish and exploit some form of preference order among the potential repairs. We study the problem of computing prioritized repairs over graph databases with data values, using a notion of consistency based on GXPath expressions as integrity constraints. We present several preference criteria based on the standard subset repair semantics, incorporating weights, multisets, and set-based priority levels. We show that it is possible to maintain the same computational complexity as in the case where no preference criterion is available for exploitation. Finally, we explore the complexity of consistent query answering in this setting and obtain tight lower and upper bounds for all the preference criteria introduced.
• Abstract（参考訳）: 優先順位は、実際的な推論において重要な要素であり、特に、追求されるさまざまな選択肢や行動のコースに対する意思決定に関わるタスクにおいてである。 本研究は, グラフデータベースの形で, 不整合な知識ベースを修復し, 問合せすることに焦点を当てる。 事前のドメイン知識がなければ、可能なすべての修復は同じように好まれる。 これはいくつかの設定に適しているかもしれないが、潜在的な修復の中で何らかの好みの順序を確立し、利用することは合理的であると思われる。 本稿では,GXPath式に基づく一貫性の概念を整合性制約として用いて,データ値を持つグラフデータベース上での優先度の高い補修問題について検討する。 本稿では,標準部分集合補修セマンティクスに基づいて,重み,多重セット,セットベース優先レベルを取り入れたいくつかの選好基準を提案する。 優先基準が適用できない場合と同様の計算複雑性を維持可能であることを示す。 最後に、この設定における一貫した問合せ応答の複雑さを考察し、導入されるすべての選好基準について、下限と上限を厳密に求める。

関連論文リスト

• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  オンライン報酬指標の偏りのないオフライン推定を最適化する意思決定ポリシーを学習することを目指している。 学習シナリオにおける同値性に基づく単一のフレームワークを提案する。 我々のフレームワークは、分散最適非バイアス推定器の特徴付けを可能にし、それに対する閉形式解を提供する。
  論文  参考訳（メタデータ） (2024-05-09T12:52:22Z)
• 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)
• Consistent Query Answering for Existential Rules with Closed Predicates [2.559168320734115]
  Consistent Query Answering (CQA)は、データベースのデータアクセスに対する一貫性のないアプローチである。 既存のルールで表されるデータ依存データベースにおけるCQAについて検討する。
  論文  参考訳（メタデータ） (2024-01-11T08:48:40Z)
• $\text{EFO}_{k}$-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation [36.77373013615789]
  本稿では,データ生成,モデルトレーニング,メソッド評価のためのフレームワークを提案する。 実験的な評価のために,データセットとして$textEFO_k$-CQAを構築した。
  論文  参考訳（メタデータ） (2023-07-15T13:18:20Z)
• Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints [5.87010466783654]
  本稿では,普遍的な制約を備えた一貫性のないデータベースを修復・クエリする問題を再考する。 我々は対称的な差分修復を採用しており、削除と事実の追加の両方を一貫性の回復に利用することができる。 より単純な否定的制約と、事実の削除のみに基づいて定義された、既存の最適修復の概念が、よりリッチな設定に適切に拡張可能であることを示す。
  論文  参考訳（メタデータ） (2023-06-06T09:17:56Z)
• Conjunctive Query Based Constraint Solving For Feature Model Configuration [79.14348940034351]
  本稿では、制約満足度問題を解決するために共役クエリーを適用する方法を示す。 このアプローチは、構成タスクを解決するために、広範囲のデータベース技術の応用を可能にする。
  論文  参考訳（メタデータ） (2023-04-26T10:08:07Z)
• On the complexity of finding set repairs for data-graphs [2.519906683279153]
  データ値を持つグラフデータベースのサブセットとスーパーセット修復の計算問題について検討する。 本稿では,Reg-GX表現の正のフラグメントに対して,サブセットタイムのアルゴリズムが適用可能であるのに対して,言語の完全な表現力は難解であることを示す。
  論文  参考訳（メタデータ） (2022-06-15T13:01:26Z)
• CoreDiag: Eliminating Redundancy in Constraint Sets [68.8204255655161]
  最小コア(最小非冗長制約集合)の決定に利用できる新しいアルゴリズムを提案する。 このアルゴリズムは、冗長性の度合いが高い分散知識工学シナリオにおいて特に有用である。 本手法の適用可能性を示すために, 商業的構成知識ベースを用いた実証的研究を実施した。
  論文  参考訳（メタデータ） (2021-02-24T09:16:10Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。 ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
  論文  参考訳（メタデータ） (2021-02-17T19:55:42Z)
• Robust Question Answering Through Sub-part Alignment [53.94003466761305]
  我々はアライメント問題として質問応答をモデル化する。 私たちは、SQuAD v1.1でモデルをトレーニングし、いくつかの逆および外ドメインデータセットでそれをテストします。
  論文  参考訳（メタデータ） (2020-04-30T09:10:57Z)
• Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation [5.87010466783654]
  優先知識ベース(KB)に対する不整合の問題について検討する。 本稿では, 接地拡張に着想を得た優先順位付きKBのセマンティクスを提案し, 良好な特性を享受する。 本研究は、嗜好に基づく議論フレームワークに関する独立した関心の結果ももたらした。
  論文  参考訳（メタデータ） (2020-03-12T12:38:37Z)

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

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