論文の概要: On the complexity of finding set repairs for data-graphs
- arxiv url: http://arxiv.org/abs/2206.07504v1
- Date: Wed, 15 Jun 2022 13:01:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-16 15:16:58.150220
- Title: On the complexity of finding set repairs for data-graphs
- Title(参考訳): データグラフの集合修復の複雑さについて
- Authors: Sergio Abriola, Santiago Cifuentes, Mar\'ia Vanina Mart\'inez, Nina
Pardal, Edwin Pin
- Abstract要約: データ値を持つグラフデータベースのサブセットとスーパーセット修復の計算問題について検討する。
本稿では,Reg-GX表現の正のフラグメントに対して,サブセットタイムのアルゴリズムが適用可能であるのに対して,言語の完全な表現力は難解であることを示す。
- 参考スコア(独自算出の注目度): 2.519906683279153
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the deeply interconnected world we live in, pieces of information link
domains all around us. As graph databases embrace effectively relationships
among data and allow processing and querying these connections efficiently,
they are rapidly becoming a popular platform for storage that supports a wide
range of domains and applications. As in the relational case, it is expected
that data preserves a set of integrity constraints that define the semantic
structure of the world it represents. When a database does not satisfy its
integrity constraints, a possible approach is to search for a 'similar'
database that does satisfy the constraints, also known as a repair. In this
work, we study the problem of computing subset and superset repairs for graph
databases with data values using a notion of consistency based on a set of
Reg-GXPath expressions as integrity constraints. We show that for positive
fragments of Reg-GXPath these problems admit a polynomial-time algorithm, while
the full expressive power of the language renders them intractable.
- Abstract(参考訳): 私たちが住む深く相互に結びついた世界では、情報の断片が周囲のドメインをリンクします。
グラフデータベースは、データ間の効果的な関係を取り入れ、それらの接続を効率的に処理およびクエリできるため、幅広いドメインとアプリケーションをサポートするストレージのプラットフォームとして急速に普及しています。
関係性の場合と同様に、データが表現する世界のセマンティック構造を定義する完全性制約のセットを保持することが期待される。
データベースがその整合性制約を満たさない場合、可能なアプローチは、修復として知られる制約を満たす'類似'データベースを探すことである。
本研究では,Reg-GXPath式を整合性制約とする一貫性の概念を用いて,データ値を持つグラフデータベースのサブセットとスーパーセット修復の問題を考察する。
reg-gxpathの正の断片に対して、これらの問題は多項式時間アルゴリズムを認め、言語の完全な表現力はそれらを難解にする。
関連論文リスト
- RelGNN: Composite Message Passing for Relational Deep Learning [56.48834369525997]
本稿では,リレーショナルデータベースの特徴を捉えた新しいGNNフレームワークであるRelGNNを紹介する。
我々のアプローチの核となるのは、高次三部構造を形成するノードの列である原子経路の導入である。
RelGNNは、最先端の精度を最大25%改善して一貫して達成している。
論文 参考訳(メタデータ) (2025-02-10T18:58:40Z) - Federated Neural Graph Databases [53.03085605769093]
プライバシを保ちながらマルチソースグラフベースのデータの推論を可能にする新しいフレームワークであるFederated Neural Graph Database (FedNGDB)を提案する。
既存の方法とは異なり、FedNGDBは複雑なグラフ構造と関係を扱うことができ、様々な下流タスクに適合する。
論文 参考訳(メタデータ) (2024-02-22T14:57:44Z) - Computational Complexity of Preferred Subset Repairs on Data-Graphs [2.254434034390529]
データ値を持つグラフデータベースを優先的に修復する問題について検討する。
本稿では,標準的なサブセット修復セマンティクスに基づいて,いくつかの選好基準を示す。
優先基準が適用できない場合と同様の計算複雑性を維持可能であることを示す。
論文 参考訳(メタデータ) (2024-02-14T15:51:55Z) - GFS: Graph-based Feature Synthesis for Prediction over Relational
Databases [39.975491511390985]
グラフベース特徴合成(GFS)と呼ばれる新しいフレームワークを提案する。
GFSは関係データベースを異種グラフデータベースとして定式化する。
4つの実世界のマルチテーブルリレーショナルデータベースに対する実験では、GFSはリレーショナルデータベース用に設計された従来の手法よりも優れていた。
論文 参考訳(メタデータ) (2023-12-04T16:54:40Z) - Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints [5.87010466783654]
本稿では,普遍的な制約を備えた一貫性のないデータベースを修復・クエリする問題を再考する。
我々は対称的な差分修復を採用しており、削除と事実の追加の両方を一貫性の回復に利用することができる。
より単純な否定的制約と、事実の削除のみに基づいて定義された、既存の最適修復の概念が、よりリッチな設定に適切に拡張可能であることを示す。
論文 参考訳(メタデータ) (2023-06-06T09:17:56Z) - Neural Graph Reasoning: Complex Logical Query Answering Meets Graph
Databases [63.96793270418793]
複雑な論理クエリ応答(CLQA)は、グラフ機械学習の最近登場したタスクである。
ニューラルグラフデータベース(NGDB)の概念を紹介する。
NGDBはNeural Graph StorageとNeural Graph Engineで構成されている。
論文 参考訳(メタデータ) (2023-03-26T04:03:37Z) - LGPMA: Complicated Table Structure Recognition with Local and Global
Pyramid Mask Alignment [54.768354427967296]
テーブル構造認識は、様々な構造と複雑な細胞間関係のために難しい課題である。
本研究では,局所・グローバルな特徴マップにソフトピラミッドマスク学習機構を採用した局所・グローバルピラミッドマスクアライメントの枠組みを提案する。
その後、ピラミッドマスク再記録モジュールが統合され、ローカルおよびグローバル情報を妥協し、予測される境界を洗練します。
論文 参考訳(メタデータ) (2021-05-13T12:24:12Z) - Topological Data Analysis of Database Representations for Information
Retrieval [2.729524133721473]
永続ホモロジーはデータベーストポロジーの厳密な特徴付けを提供する。
我々は、一般的な埋め込みが接続を維持するのに失敗することを示した。
この効果を捉えるために、拡散不変ボトルネック距離を導入する。
論文 参考訳(メタデータ) (2021-04-04T19:29:47Z) - Dynamic Hybrid Relation Network for Cross-Domain Context-Dependent
Semantic Parsing [52.24507547010127]
ドメイン間コンテキスト依存のセマンティック解析は研究の新たな焦点である。
本稿では,コンテキストの発話,トークン,データベーススキーマ,会話の進行に伴う複雑なインタラクションを効果的にモデル化する動的グラフフレームワークを提案する。
提案したフレームワークは既存のモデルを大きなマージンで上回り、2つの大規模ベンチマークで新しい最先端性能を達成する。
論文 参考訳(メタデータ) (2021-01-05T18:11:29Z) - Partially-Aligned Data-to-Text Generation with Distant Supervision [69.15410325679635]
我々はPADTG(Partially-Aligned Data-to-Text Generation)と呼ばれる新しい生成タスクを提案する。
自動的にアノテートされたデータをトレーニングに利用し、アプリケーションドメインを大幅に拡張するため、より実用的です。
我々のフレームワークは、全てのベースラインモデルより優れており、部分整合データの利用の可能性を検証する。
論文 参考訳(メタデータ) (2020-10-03T03:18:52Z) - On Embeddings in Relational Databases [11.52782249184251]
低次元埋め込みを用いた関係データベースにおけるエンティティの分散表現学習の問題に対処する。
近年の埋め込み学習法は,すべてのテーブルの完全結合をリレーショナル化し,知識グラフとして表すことにより,データベースの完全非正規化を考慮に入れたナイーブな手法である。
本稿では,テーブル内の列の基本的なセマンティクスを利用して表現を学習する上で,関係結合と潜時関係を用いて,より優れた方法論を実証する。
論文 参考訳(メタデータ) (2020-05-13T17:21:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。