論文の概要: Computational Complexity of Preferred Subset Repairs on Data-Graphs
- arxiv url: http://arxiv.org/abs/2402.09265v1
- Date: Wed, 14 Feb 2024 15:51:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 14:43:13.254422
- Title: Computational Complexity of Preferred Subset Repairs on Data-Graphs
- Title（参考訳）: データグラフ上の優先サブセット修復の計算複雑性
- Authors: Nina Pardal and Santiago Cifuentes and Edwin Pin and Maria Vanina
Martinez and Sergio Abriola
- Abstract要約: 本稿では,標準サブセット修復セマンティクスに基づいて,重み,マルチセット,セットベースの優先度レベルを組み込んだ選好基準を提案する。
筆者らは最も一般的な補修作業について検討し、選好基準が適用できない場合と同様の計算複雑性を維持可能であることを示した。
- 参考スコア（独自算出の注目度）: 2.4186604326116874
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of repairing inconsistent knowledge bases has a long history
within the communities of database theory and knowledge representation and
reasoning, especially from the perspective of structured data. However, as the
data available in real-world domains becomes more complex and interconnected,
the need naturally arises for developing new types of repositories,
representation languages, and semantics, to allow for more suitable ways to
query and reason about it. Graph databases provide an effective way to
represent relationships among semi-structured data, and allow processing and
querying these connections efficiently. In this work, we focus on the problem
of computing prioritized repairs over graph databases with data values, using a
notion of consistency based on Reg-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
study the most common repairing tasks, showing that it is possible to maintain
the same computational complexity as in the case where no preference criterion
is available for exploitation. To complete the picture, 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（参考訳）: 一貫性のない知識ベースを修復する問題は、特に構造化データの観点から、データベース理論と知識表現と推論のコミュニティの中で長い歴史を持っている。
しかし、現実世界のドメインで利用可能なデータがより複雑で相互接続されるようになるにつれて、新しいタイプのリポジトリ、表現言語、セマンティクスを開発するためのニーズが自然に生まれ、それについてより適切なクエリと推論ができるようになる。
グラフデータベースは、半構造化データ間の関係を効果的に表現し、これらのコネクションの処理とクエリを効率的に行うことができる。
本稿では,reg-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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。