論文の概要: 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式に基づく一貫性の概念を完全性制約として用い,データ値を持つグラフデータベースよりも優先順位付けされた修復の計算の問題に焦点をあてる。
本稿では,標準部分集合修復セマンティクスに基づいて,重み,マルチセット,セットに基づく優先度レベルを組み込んだ選好基準を提案する。
筆者らは最も一般的な補修作業について検討し、選好基準が適用できない場合と同様の計算複雑性を維持可能であることを示した。
本稿では,この設定における一貫性のある問い合わせ応答の複雑さを調べ,導入されるすべての選好基準に対して,下限と上限を厳密に求める。
関連論文リスト
- Inconsistency Handling in Prioritized Databases with Universal
Constraints: Complexity Analysis and Links with Active Integrity Constraints [12.952483242045366]
本稿では,普遍的な制約を備えた一貫性のないデータベースを修復・クエリする問題を再考する。
我々は対称的な差分修復を採用しており、削除と事実の追加の両方を一貫性の回復に利用することができる。
より単純な否定的制約と、事実の削除のみに基づいて定義された、既存の最適修復の概念が、よりリッチな設定に適切に拡張可能であることを示す。
論文 参考訳(メタデータ) (2023-06-06T09:17:56Z) - Conjunctive Query Based Constraint Solving For Feature Model
Configuration [79.14348940034351]
本稿では、制約満足度問題を解決するために共役クエリーを適用する方法を示す。
このアプローチは、構成タスクを解決するために、広範囲のデータベース技術の応用を可能にする。
論文 参考訳(メタデータ) (2023-04-26T10:08:07Z) - Learnable Pillar-based Re-ranking for Image-Text Retrieval [119.9979224297237]
画像テキスト検索は、モダリティギャップを埋め、意味的類似性に基づいてモダリティコンテンツを検索することを目的としている。
一般的なポストプロセッシング手法であるリグレードは, 単一モダリティ検索タスクにおいて, 隣り合う関係を捕捉する優位性を明らかにしている。
本稿では,画像テキスト検索のための新しい学習可能な柱型リグレードパラダイムを提案する。
論文 参考訳(メタデータ) (2023-04-25T04:33:27Z) - Rethinking Complex Queries on Knowledge Graphs with Neural Link
Predictors [65.56849255423866]
本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。
これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。
提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
論文 参考訳(メタデータ) (2023-04-14T11:35:35Z) - Mixed-modality Representation Learning and Pre-training for Joint
Table-and-Text Retrieval in OpenQA [85.17249272519626]
最適化された OpenQA Table-Text Retriever (OTTeR) を提案する。
検索中心の混合モード合成事前学習を行う。
OTTeRはOTT-QAデータセット上でのテーブル・アンド・テキスト検索の性能を大幅に改善する。
論文 参考訳(メタデータ) (2022-10-11T07:04:39Z) - HyperImpute: Generalized Iterative Imputation with Automatic Model
Selection [77.86861638371926]
カラムワイズモデルを適応的かつ自動的に構成するための一般化反復計算フレームワークを提案する。
既製の学習者,シミュレータ,インターフェースを備えた具体的な実装を提供する。
論文 参考訳(メタデータ) (2022-06-15T19:10:35Z) - On the complexity of finding set repairs for data-graphs [2.519906683279153]
データ値を持つグラフデータベースのサブセットとスーパーセット修復の計算問題について検討する。
本稿では,Reg-GX表現の正のフラグメントに対して,サブセットタイムのアルゴリズムが適用可能であるのに対して,言語の完全な表現力は難解であることを示す。
論文 参考訳(メタデータ) (2022-06-15T13:01:26Z) - Semi-Structured Query Grounding for Document-Oriented Databases with
Deep Retrieval and Its Application to Receipt and POI Matching [23.52046767195031]
半構造化データにおけるクエリグラウンドリング問題に対する埋め込み型検索の実践的課題に対処することを目的としている。
クエリとデータベースの両方のエントリの埋め込みと検索において,モジュールの最も効果的な組み合わせを見つけるために,広範な実験を行う。
提案モデルでは,従来の手動パターンモデルよりも大幅に優れ,開発コストやメンテナンスコストの低減が図られている。
論文 参考訳(メタデータ) (2022-02-23T05:32:34Z) - Dynamic Hybrid Relation Network for Cross-Domain Context-Dependent
Semantic Parsing [52.24507547010127]
ドメイン間コンテキスト依存のセマンティック解析は研究の新たな焦点である。
本稿では,コンテキストの発話,トークン,データベーススキーマ,会話の進行に伴う複雑なインタラクションを効果的にモデル化する動的グラフフレームワークを提案する。
提案したフレームワークは既存のモデルを大きなマージンで上回り、2つの大規模ベンチマークで新しい最先端性能を達成する。
論文 参考訳(メタデータ) (2021-01-05T18:11:29Z) - On Embeddings in Relational Databases [11.52782249184251]
低次元埋め込みを用いた関係データベースにおけるエンティティの分散表現学習の問題に対処する。
近年の埋め込み学習法は,すべてのテーブルの完全結合をリレーショナル化し,知識グラフとして表すことにより,データベースの完全非正規化を考慮に入れたナイーブな手法である。
本稿では,テーブル内の列の基本的なセマンティクスを利用して表現を学習する上で,関係結合と潜時関係を用いて,より優れた方法論を実証する。
論文 参考訳(メタデータ) (2020-05-13T17:21:27Z) - Querying and Repairing Inconsistent Prioritized Knowledge Bases:
Complexity Analysis and Links with Abstract Argumentation [12.952483242045366]
優先知識ベース(KB)に対する不整合の問題について検討する。
本稿では, 接地拡張に着想を得た優先順位付きKBのセマンティクスを提案し, 良好な特性を享受する。
本研究は、嗜好に基づく議論フレームワークに関する独立した関心の結果ももたらした。
論文 参考訳(メタデータ) (2020-03-12T12:38:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。