論文の概要: Harmless but Useful: Beyond Separable Equality Constraints in Datalog+/-
- arxiv url: http://arxiv.org/abs/2105.11147v1
- Date: Mon, 24 May 2021 08:22:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-26 00:33:18.208978
- Title: Harmless but Useful: Beyond Separable Equality Constraints in Datalog+/-
- Title（参考訳）: harmless but useful: beyond separable equal constraints in datalog+/
- Authors: Luigi Bellomarini, Emanuel Sallinger
- Abstract要約: 我々は、分離可能なEGDをサブセットとし、より広範な問題のクラスをモデル化できる「無害」と呼ばれるEGDのクラスを提案する。
分離可能な EGD とは異なり、無害な EGD は、基底の等式制約を強制する以外に、クエリ応答を専門化する。
このような断片において、クエリ応答は決定可能であり、PTIMEはデータ複雑性において決定可能である、と我々は主張する。
- 参考スコア（独自算出の注目度）: 3.42658286826597
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Ontological query answering is the problem of answering queries in the
presence of schema constraints representing the domain of interest. Datalog+/-
is a common family of languages for schema constraints, including
tuple-generating dependencies (TGDs) and equality-generating dependencies
(EGDs). The interplay of TGDs and EGDs leads to undecidability or
intractability of query answering when adding EGDs to tractable Datalog+/-
fragments, like Warded Datalog+/-, for which, in the sole presence of TGDs,
query answering is PTIME in data complexity. There have been attempts to limit
the interaction of TGDs and EGDs and guarantee tractability, in particular with
the introduction of separable EGDs, to make EGDs irrelevant for query answering
as long as the set of constraints is satisfied. While being tractable,
separable EGDs have limited expressive power.
We propose a more general class of EGDs, which we call ``harmless'', that
subsume separable EGDs and allow to model a much broader class of problems.
Unlike separable EGDs, harmless EGDs, besides enforcing ground equality
constraints, specialize the query answer by grounding or renaming the labelled
nulls introduced by existential quantification in the TGDs. Harmless EGDs
capture the cases when the answer obtained in the presence of EGDs is less
general than the one obtained with TGDs only. We conclude that the theoretical
problem of deciding whether a set of constraints contains harmless EGDs is
undecidable. We contribute a sufficient syntactic condition characterizing
harmless EGDs, broad and useful in practice. We focus on Warded Datalog+/- with
harmless EGDs and argue that, in such fragment, query answering is decidable
and PTIME in data complexity. We study chase-based techniques for query
answering in Warded Datalog+/- with harmless EGDs, conducive to an efficient
algorithm to be implemented in state-of-the-art reasoners.
- Abstract（参考訳）: オントロジークエリ応答は、関心領域を表すスキーマ制約の存在下でクエリに応答する問題である。
Datalog+/は、タプル生成依存性(TGD)や平等生成依存性(EGD)など、スキーマ制約のための共通言語である。
TGDとEGDの相互作用は、Warded Datalog+/-のようなトラクタブルなDatalog+/fragmentsにEGDを追加する際のクエリ応答の不決定性や難解性をもたらす。
TGDとEGDの相互作用を制限し、トラクタビリティ、特に分離可能なEGDの導入によって、制約の集合が満たされる限り、クエリ応答にEGDを無関係にする試みがある。
扱いやすいが、分離可能なegdは表現力に制限がある。
より一般的な EGD クラスを提案し、これは '`harmless'' と呼ばれ、分離可能な EGD をサブセットし、より広範な問題のクラスをモデル化することができる。
分離可能なegdとは異なり、harmless egdは基底的平等制約を強制するだけでなく、tgdsで存在量化によって導入されたラベル付きヌルを接地または改名することでクエリ応答を特殊化する。
無害なEGDは、EGDの存在下で得られた答えがTGDで得られたものよりも一般的でない場合に捕獲する。
制約の集合が無害なegdを含むかどうかを判断する理論的問題は決定不能である。
我々は,無害なegdを特徴付ける十分な構文条件に寄与する。
我々は、無害なEGDを持つWarded Datalog+/-に注目し、そのような断片的なクエリ応答は決定可能であり、PTIMEはデータ複雑性において決定可能であると論じる。
我々は,無害なEGDを用いたWarded Datalog+/-における問合せ応答のためのチェイスベース手法について検討した。
関連論文リスト
- Top Ten Challenges Towards Agentic Neural Graph Databases [56.92578700681306]
Neo4jやTigerGraphのようなグラフデータベース(GDB)は相互接続されたデータを扱うのが得意だが、高度な推論機能が欠けている。
本稿では,NGDBを3つのコア機能で拡張するエージェント型ニューラルネットワークデータベース(Agentic NGDB)を提案する。
論文 参考訳（メタデータ） (2025-01-24T04:06:50Z) - The Ability of Large Language Models to Evaluate Constraint-satisfaction in Agent Responses to Open-ended Requests [0.6249768559720121]
我々は,新しいArithmetic Constraint-Satisfaction(ACS)ベンチマークデータセットを開発し,リリースする。
このデータセットは、対応する制約を持つ複雑なユーザリクエスト、エージェント応答、応答における各制約の満足度を示すヒューマンラベルで構成されている。
ほとんどのモデルにはまだ改善のための重要なヘッドルームがあることを示し、エラーは主に推論の問題に起因する。
論文 参考訳（メタデータ） (2024-09-22T09:27:42Z) - Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) を使用して、差分プライバシ(DP)がモデルパフォーマンス劣化の犠牲となることを保証する。
DPSGD-GCに代わる新しいエラーフィードバック(EF)DPアルゴリズムを提案する。
提案アルゴリズムに対するアルゴリズム固有のDP解析を確立し,R'enyi DPに基づくプライバシ保証を提供する。
論文 参考訳（メタデータ） (2023-11-24T17:56:44Z) - Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
本稿では,共有並列計算問題に対する新しいアプローチを提案する。
2つの戦略を統一されたフレームワークに組み合わせることで、DPSGDはより良い取引計算フレームワークになります。
深層学習(DRL)問題と深層学習(DRL)問題(アドバンテージアクター - A2C)についてDPSGDにより潜在ゲインを達成できる。
論文 参考訳（メタデータ） (2022-10-06T13:06:08Z) - Mitigating Algorithmic Bias with Limited Annotations [65.060639928772]
機密属性が公開されていない場合、バイアスを軽減するために、トレーニングデータの小さな部分を手動でアノテートする必要がある。
本稿では,アルゴリズムバイアスの影響を最大限に排除するために,限定アノテーションを誘導する対話型フレームワークであるアクティブペナライゼーション・オブ・差別(APOD)を提案する。
APODは完全なアノテートバイアス緩和と同等のパフォーマンスを示しており、機密情報が制限された場合、APODが現実世界のアプリケーションに利益をもたらすことを実証している。
論文 参考訳（メタデータ） (2022-07-20T16:31:19Z) - Modeling the Data-Generating Process is Necessary for Out-of-Distribution Generalization [23.302060306322506]
実世界のデータは、しばしば異なる属性に対して複数の分散シフトを持つ。
最先端のDGアルゴリズムは、すべてのシフトに対して一貫してうまく動作しない。
我々は、データ生成プロセスに関する知識を用いて正規化のための正しい独立制約を適応的に識別し、適用するアルゴリズムであるCausally Adaptive Constraint Minimization (CACM)を開発した。
論文 参考訳（メタデータ） (2022-06-15T22:35:06Z) - On the complexity of finding set repairs for data-graphs [2.519906683279153]
データ値を持つグラフデータベースのサブセットとスーパーセット修復の計算問題について検討する。
本稿では,Reg-GX表現の正のフラグメントに対して,サブセットタイムのアルゴリズムが適用可能であるのに対して,言語の完全な表現力は難解であることを示す。
論文 参考訳（メタデータ） (2022-06-15T13:01:26Z) - Effect Identification in Cluster Causal Diagrams [51.42809552422494]
クラスタ因果図(略してC-DAG)と呼ばれる新しいタイプのグラフィカルモデルを導入する。
C-DAGは、限定された事前知識に基づいて変数間の関係を部分的に定義することができる。
我々はC-DAGに対する因果推論のための基礎と機械を開発する。
論文 参考訳（メタデータ） (2022-02-22T21:27:31Z) - QD-GCN: Query-Driven Graph Convolutional Networks for Attributed
Community Search [54.42038098426504]
QD-GCNは、ACS問題を解決するために、コミュニティ構造とノード属性を統一するエンドツーエンドフレームワークである。
本稿では、QD-GCNが既存の属性付きコミュニティ検索アルゴリズムを効率性と有効性の両方で上回ることを示す。
論文 参考訳（メタデータ） (2021-04-08T07:52:48Z) - Conditional Self-Attention for Query-based Summarization [49.616774159367516]
条件依存モデリング用に設計されたニューラルネットワークモジュールであるテキスト条件自己アテンション(CSA)を提案する。
DebatepediaとHotpotQAベンチマークデータセットの実験は、CSAがバニラトランスフォーマーを一貫して上回っていることを示している。
論文 参考訳（メタデータ） (2020-02-18T02:22:31Z) - The Limits of Efficiency for Open- and Closed-World Query Evaluation
Under Guarded TGDs [10.042878093985458]
制約が存在する場合のオントロジーによるクエリとクエリは2つの重要なデータベース問題である。
保護されたTGDとUCQのコンテキストにおける効率的なクエリ評価の限界を実際のクエリとして検討する。
論文 参考訳（メタデータ） (2019-12-28T11:08:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。