論文の概要: Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints
- arxiv url: http://arxiv.org/abs/2306.03523v2
- Date: Thu, 30 May 2024 12:36:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-01 00:02:40.337730
- Title: Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints
- Title（参考訳）: 普遍制約付き優先データベースにおける不整合処理: 複雑性解析とアクティブ積分制約付きリンク
- Authors: Meghyn Bienvenu, Camille Bourgaux,
- Abstract要約: 本稿では,普遍的な制約を備えた一貫性のないデータベースを修復・クエリする問題を再考する。
我々は対称的な差分修復を採用しており、削除と事実の追加の両方を一貫性の回復に利用することができる。
より単純な否定的制約と、事実の削除のみに基づいて定義された、既存の最適修復の概念が、よりリッチな設定に適切に拡張可能であることを示す。
- 参考スコア（独自算出の注目度）: 5.87010466783654
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper revisits the problem of repairing and querying inconsistent databases equipped with universal constraints. We adopt symmetric difference repairs, in which both deletions and additions of facts can be used to restore consistency, and suppose that preferred repair actions are specified via a binary priority relation over (negated) facts. Our first contribution is to show how existing notions of optimal repairs, defined for simpler denial constraints and repairs solely based on fact deletion, can be suitably extended to our richer setting. We next study the computational properties of the resulting repair notions, in particular, the data complexity of repair checking and inconsistency-tolerant query answering. Finally, we clarify the relationship between optimal repairs of prioritized databases and repair notions introduced in the framework of active integrity constraints. In particular, we show that Pareto-optimal repairs in our setting correspond to founded, grounded and justified repairs w.r.t. the active integrity constraints obtained by translating the prioritized database. Our study also yields useful insights into the behavior of active integrity constraints.
- Abstract（参考訳）: 本稿では,普遍的な制約を備えた一貫性のないデータベースを修復・クエリする問題を再考する。
我々は、整合性回復に事実の削除と付加の両方を使用できる対称差分補修を採用し、(否定された)事実に対する二項優先関係によって、優先的な修理動作が特定されると仮定する。
最初のコントリビューションは、より単純な否定的制約と事実削除のみに基づく修復のために定義された、既存の最適修復の概念が、よりリッチな設定にどのように拡張できるかを示すことである。
次に, 補修概念の計算特性, 特に補修チェックと不整合性問合せ応答の複雑さについて検討する。
最後に、優先度付けされたデータベースの最適修復と、アクティブな整合性制約の枠組みで導入された修復概念との関係を明らかにする。
特に、我々の設定におけるパレート最適修復は、優先順位付けされたデータベースを翻訳して得られる能動的整合性制約に対して、確立、基礎化、正当化された修復に対応していることを示す。
また,本研究は,能動的整合性制約の挙動に関する有用な知見も得る。
関連論文リスト
- Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
オンライン報酬指標の偏りのないオフライン推定を最適化する意思決定ポリシーを学習することを目指している。
学習シナリオにおける同値性に基づく単一のフレームワークを提案する。
我々のフレームワークは、分散最適非バイアス推定器の特徴付けを可能にし、それに対する閉形式解を提供する。
論文 参考訳（メタデータ） (2024-05-09T12:52:22Z) - OTClean: Data Cleaning for Conditional Independence Violations using
Optimal Transport [51.6416022358349]
sysは、条件付き独立性(CI)制約下でのデータ修復に最適な輸送理論を利用するフレームワークである。
我々はSinkhornの行列スケーリングアルゴリズムにインスパイアされた反復アルゴリズムを開発し、高次元および大規模データを効率的に処理する。
論文 参考訳（メタデータ） (2024-03-04T18:23:55Z) - Computational Complexity of Preferred Subset Repairs on Data-Graphs [2.254434034390529]
データ値を持つグラフデータベースを優先的に修復する問題について検討する。
本稿では,標準的なサブセット修復セマンティクスに基づいて,いくつかの選好基準を示す。
優先基準が適用できない場合と同様の計算複雑性を維持可能であることを示す。
論文 参考訳（メタデータ） (2024-02-14T15:51:55Z) - Disentangled Representation Learning with Transmitted Information
Bottleneck [73.0553263960709]
textbfDisTIB (textbfTransmitted textbfInformation textbfBottleneck for textbfDisd representation learning) は情報圧縮と保存のバランスを保った新しい目的である。
論文 参考訳（メタデータ） (2023-11-03T03:18:40Z) - Calibrated Data-Dependent Constraints with Exact Satisfaction Guarantees [46.94549066382216]
データに依存した制約で機械学習モデルを訓練する作業について検討する。
我々は、データ依存の制約を校正するように修正し、修正された制約を強制することで、期待値の制約がユーザによって規定された確率で満たされることを保証する。
論文 参考訳（メタデータ） (2023-01-15T21:41:40Z) - Relational Action Bases: Formalization, Effective Safety Verification,
and Invariants (Extended Version) [67.99023219822564]
我々はリレーショナルアクションベース(RAB)の一般的な枠組みを紹介する。
RABは両方の制限を解除することで既存のモデルを一般化する。
データ対応ビジネスプロセスのベンチマークにおいて、このアプローチの有効性を実証する。
論文 参考訳（メタデータ） (2022-08-12T17:03:50Z) - On the complexity of finding set repairs for data-graphs [2.519906683279153]
データ値を持つグラフデータベースのサブセットとスーパーセット修復の計算問題について検討する。
本稿では,Reg-GX表現の正のフラグメントに対して,サブセットタイムのアルゴリズムが適用可能であるのに対して,言語の完全な表現力は難解であることを示す。
論文 参考訳（メタデータ） (2022-06-15T13:01:26Z) - Querying Inconsistent Prioritized Data with ORBITS: Algorithms,
Implementation, and Experiments [12.952483242045366]
優先順位付けされた知識ベース上で不整合耐性問合せ応答を行うための実用的なアルゴリズムについて検討する。
最適補修の2つの概念に基づく3つのよく知られた意味論(AR, IAR, 勇敢)を考える(パレート, 完成)。
論文 参考訳（メタデータ） (2022-02-16T10:44:39Z) - Second-Order Specifications and Quantifier Elimination for Consistent
Query Answering in Databases [0.0]
本稿では, 補修プログラムを用いて一貫した問合せ応答の問題を w.r.t の推論問題に変換する方法を示す。
また, 2次量子化器の除去手法を適用して, 代わりに1次理論を得る方法も検討した。
論文 参考訳（メタデータ） (2021-08-19T01:06:01Z) - Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation [5.87010466783654]
優先知識ベース(KB)に対する不整合の問題について検討する。
本稿では, 接地拡張に着想を得た優先順位付きKBのセマンティクスを提案し, 良好な特性を享受する。
本研究は、嗜好に基づく議論フレームワークに関する独立した関心の結果ももたらした。
論文 参考訳（メタデータ） (2020-03-12T12:38:37Z) - GenDICE: Generalized Offline Estimation of Stationary Values [108.17309783125398]
重要なアプリケーションでは,効果的な推定が依然として可能であることを示す。
我々のアプローチは、定常分布と経験分布の差を補正する比率を推定することに基づいている。
結果として得られるアルゴリズム、GenDICEは単純で効果的である。
論文 参考訳（メタデータ） (2020-02-21T00:27:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。