論文の概要: The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs

• arxiv url: http://arxiv.org/abs/1912.12442v1
• Date: Sat, 28 Dec 2019 11:08:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-17 13:14:04.095138
• Title: The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs
• Title（参考訳）: ガード付きTGDにおけるオープンおよびクローズドワールドクエリ評価の効率限界
• Authors: Pablo Barcelo, Victor Dalmau, Cristina Feier, Carsten Lutz, Andreas Pieris
• Abstract要約: 制約が存在する場合のオントロジーによるクエリとクエリは2つの重要なデータベース問題である。 保護されたTGDとUCQのコンテキストにおける効率的なクエリ評価の限界を実際のクエリとして検討する。
• 参考スコア（独自算出の注目度）: 10.042878093985458
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-mediated querying, TGDs can formalize the ontology and thus derive additional facts from the given data, while in querying in the presence of constraints, they restrict the set of admissible databases. In this work, we study the limits of efficient query evaluation in the context of the above two problems, focussing on guarded and frontier-guarded TGDs and on UCQs as the actual queries. We show that a class of ontology-mediated queries (OMQs) based on guarded TGDs can be evaluated in FPT iff the OMQs in the class are equivalent to OMQs in which the actual query has bounded treewidth, up to some reasonable assumptions. For querying in the presence of constraints, we consider classes of constraint-query specifications (CQSs) that bundle a set of constraints with an actual query. We show a dichotomy result for CQSs based on guarded TGDs that parallels the one for OMQs except that, additionally, FPT coincides with PTime combined complexity. The proof is based on a novel connection between OMQ and CQS evaluation. Using a direct proof, we also show a similar dichotomy result, again up to some reasonable assumptions, for CQSs based on frontier-guarded TGDs with a bounded number of atoms in TGD heads. Our results on CQSs can be viewed as extensions of Grohe's well-known characterization of the tractable classes of CQs (without constraints). Like Grohe's characterization, all the above results assume that the arity of relation symbols is bounded by a constant. We also study the associated meta problems, i.e., whether a given OMQ or CQS is equivalent to one in which the actual query has bounded treewidth.
• Abstract（参考訳）: 制約が存在する場合のオントロジーによるクエリとクエリは、タプル生成依存性(TGD)が中心的な役割を果たす2つの主要なデータベース問題である。 オントロジーを媒介とするクエリでは、tgdはオントロジーを形式化し、与えられたデータから追加の事実を導出することができる。 本研究では,上記2つの問題の文脈における効率的なクエリ評価の限界について検討し,ガード付き,フロンティアガード付きtgdと実際のクエリとしてucqsに着目した。 保護されたTGDをベースとしたオントロジー型クエリ(OMQ)のクラスをFPTで評価できることを示し,そのクラス内のOMQは,実際のクエリがツリー幅に有界なOMQと等価であることを示す。 制約の存在下でクエリを行うには、実際のクエリに一連の制約をバンドルする制約クエリ仕様(CQS)のクラスを検討する。 我々は、omqs と並行するガード付き tgd に基づく cqss の2分法結果を示し、さらに、fpt は ptime の複合複雑性と一致することを示した。 この証明は、OMQとCQS評価の新たな関係に基づいている。 また、直接的証明を用いて、TGDヘッドに原子が有界なフロンティアガードされたTGDをベースとしたCQSに対して、同様の二分法結果を示す。 CQS に関する我々の結果は、(制約なしで) CQ の抽出可能なクラスをグロエのよく知られた特徴付けの拡張と見なすことができる。 グロエの特徴づけと同様に、上記のすべての結果は関係記号のアリティが定数で有界であると仮定する。 我々はまた、関連するメタ問題、すなわち与えられたomqまたはcqsが実際のクエリが有界木幅を持つものと同値であるかどうかについても研究する。

関連論文リスト

• Controlled Query Evaluation through Epistemic Dependencies [7.502796412126707]
  本稿では,このフレームワークの表現能力を示し,CQEの(一対の)結合クエリにおけるデータ複雑性について検討する。 本稿では,非循環的依存関係の場合のトラクタビリティを,適切なクエリアルゴリズムを提供することにより証明する。
  論文  参考訳（メタデータ） (2024-05-03T19:48:07Z)
• IfQA: A Dataset for Open-domain Question Answering under Counterfactual Presuppositions [54.23087908182134]
  本稿では,QA(FifQA)と呼ばれる,最初の大規模対実的オープンドメイン質問応答(QA)ベンチマークを紹介する。 IfQAデータセットには3,800以上の質問が含まれている。 IfQAベンチマークによって引き起こされるユニークな課題は、検索と対実的推論の両方に関して、オープンドメインのQA研究を促進することである。
  論文  参考訳（メタデータ） (2023-05-23T12:43:19Z)
• Toward Unsupervised Realistic Visual Question Answering [70.67698100148414]
  現実的なVQA(RVQA)の問題について検討し、モデルが答えられない質問(UQ)を拒絶し、答えられる質問(AQ)に答えなければならない。 1)データセットには不整合UQが多すぎること,(2)多数の注釈付きUQがトレーニングに必要とされること,の2つの欠点を最初に指摘した。 我々は、既存のVQAデータセットのAQと約29万の人間の注釈付きUQを組み合わせた新しいテストデータセットRGQAを提案する。 これは、画像と質問をランダムにペアリングして得られる擬似UQと、それを結合する。
  論文  参考訳（メタデータ） (2023-03-09T06:58:29Z)
• RoMQA: A Benchmark for Robust, Multi-evidence, Multi-answer Question Answering [87.18962441714976]
  堅牢でマルチエビデンスな質問応答(QA)のための最初のベンチマークであるRoMQAを紹介します。 我々は、最先端の大規模言語モデルをゼロショット、少数ショット、微調整設定で評価し、RoMQAが難しいことを発見した。 以上の結果から,RoMQAは大規模言語モデルにとって難しいベンチマークであり,より堅牢なQA手法を構築するための定量的なテストを提供する。
  論文  参考訳（メタデータ） (2022-10-25T21:39:36Z)
• Semantic Framework based Query Generation for Temporal Question Answering over Knowledge Graphs [19.851986862305623]
  本稿では,提案するエンティティの関連事実を探索し,問合せグラフを生成する時間的質問応答手法であるSF-TQAを提案する。 評価の結果,SF-TQAは知識グラフの異なる2つのベンチマークにおいて既存手法よりも有意に優れていた。
  論文  参考訳（メタデータ） (2022-10-10T08:40:28Z)
• Ontology-Mediated Querying on Databases of Bounded Cliquewidth [10.880181451789262]
  有界クリフ幅のデータベース上でのオントロジーによるクエリ(OMQ)の評価について検討する。 我々の主な貢献は、パラメータのランニング時間依存性の詳細な分析であり、いくつかの興味深い効果を示している。
  論文  参考訳（メタデータ） (2022-05-04T17:13:08Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。 提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
  論文  参考訳（メタデータ） (2022-02-22T01:34:35Z)
• Efficiency of Query Evaluation Under Guarded TGDs: The Unbounded Arity Case [1.370633147306388]
  本稿では、ガード付きTGD(GTGD)と接続型クエリ(UCQ)に基づいて、オントロジー媒介クエリ(OMQ)を評価する際のパラメータ化複雑性を分析する。
  論文  参考訳（メタデータ） (2021-01-27T22:32:16Z)
• Query Focused Multi-Document Summarization with Distant Supervision [88.39032981994535]
  既存の作業は、クエリとテキストセグメント間の関連性を推定する検索スタイルの手法に大きく依存している。 本稿では,クエリに関連するセグメントを推定するための個別モジュールを導入した粗大なモデリングフレームワークを提案する。 我々のフレームワークは、標準QFSベンチマークにおいて、強力な比較システムよりも優れていることを実証する。
  論文  参考訳（メタデータ） (2020-04-06T22:35:19Z)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  関係データベース上でのオントロジーによるクエリの評価について検討する。 OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。 また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
  論文  参考訳（メタデータ） (2020-03-17T16:32:00Z)
• Conditional Self-Attention for Query-based Summarization [49.616774159367516]
  条件依存モデリング用に設計されたニューラルネットワークモジュールであるテキスト条件自己アテンション(CSA)を提案する。 DebatepediaとHotpotQAベンチマークデータセットの実験は、CSAがバニラトランスフォーマーを一貫して上回っていることを示している。
  論文  参考訳（メタデータ） (2020-02-18T02:22:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。