論文の概要: Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability

• arxiv url: http://arxiv.org/abs/2311.14579v2
• Date: Wed, 11 Sep 2024 12:29:56 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-12 22:03:32.452895
• Title: Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability
• Title（参考訳）: 結合型クエリに対するカウントソリューション:構造的およびハイブリッドなトラクタビリティ
• Authors: Hubie Chen, Gianluigi Greco, Stefan Mengel, Francesco Scarcello,
• Abstract要約: 接続的クエリに対する回答の数をカウントすることは、標準的な仮定では効率的な解を持たないデータベースの基本的な問題である。 固有インスタンスの構造特性を調べ、#-ハイパーツリー分解という新しい概念を導入することにより、抽出可能なクラスをピンポイントする。
• 参考スコア（独自算出の注目度）: 8.618430843854048
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Counting the number of answers to conjunctive queries is a fundamental problem in databases that, under standard assumptions, does not have an efficient solution. The issue is inherently #P-hard, extending even to classes of acyclic instances. To address this, we pinpoint tractable classes by examining the structural properties of instances and introducing the novel concept of #-hypertree decomposition. We establish the feasibility of counting answers in polynomial time for classes of queries featuring bounded #-hypertree width. Additionally, employing novel techniques from the realm of fixed-parameter computational complexity, we prove that, for bounded arity queries, the bounded #-hypertree width property precisely delineates the frontier of tractability for the counting problem. This result closes an important gap in our understanding of the complexity of such a basic problem for conjunctive queries and, equivalently, for constraint satisfaction problems (CSPs). Drawing upon #-hypertree decompositions, a ''hybrid'' decomposition method emerges. This approach leverages both the structural characteristics of the query and properties intrinsic to the input database, including keys or other (weaker) degree constraints that limit the permissible combinations of values. Intuitively, these features may introduce distinct structural properties that elude identification through the ''worst-possible database'' perspective inherent in purely structural methods.
• Abstract（参考訳）: 接続的クエリに対する回答の数をカウントすることは、標準的な仮定では効率的な解を持たないデータベースの基本的な問題である。 この問題は本質的に#P-hardであり、非循環インスタンスのクラスにまで拡張されている。 これを解決するために、インスタンスの構造特性を調べ、#-hypertree分解という新しい概念を導入することで、抽出可能なクラスをピンポイントする。 我々は,#-hypertree幅の有界なクエリのクラスに対して,多項式時間で回答をカウントできる可能性を確立する。 さらに、固定パラメータ計算複雑性の領域からの新しい手法を用いて、有界アリティクエリに対して、有界#-ハイパーツリー幅特性は、カウント問題に対するトラクタビリティのフロンティアを正確に規定することを証明する。 この結果から,制約満足度問題 (CSP) において,このような基本的問題の複雑性を理解する上で重要なギャップを埋めることができた。 #-hypertree分解に基づいて'hybrid'分解メソッドが現れる。 このアプローチでは、クエリの構造的特性と、入力データベースに固有の特性の両方を活用している。 直感的には、これらの特徴は純粋に構造的手法に固有の 'Worst-possible database'' の観点で識別を損なう独特な構造的特性を導入するかもしれない。

関連論文リスト

• The Computational Complexity of Concise Hypersphere Classification [49.57441416941195]
  本稿では,二元データに対する超球分類問題の複雑性理論による最初の研究である。 パラメータ化複雑性のパラダイムを用いて、入力データに存在する可能性のある構造特性の影響を分析する。
  論文  参考訳（メタデータ） (2023-12-12T09:33:03Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems [5.099537069575897]
  非負・正の行列とテンソル完備問題を定義・解決するための新しい一貫性に基づくアプローチを導入する。 単一特性/制約: 単位スケールの一貫性を保ち、解の存在を保証し、比較的弱いサポート仮定の下では、一意性を示す。
  論文  参考訳（メタデータ） (2022-04-04T19:42:46Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。 提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
  論文  参考訳（メタデータ） (2022-02-22T01:34:35Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。 ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
  論文  参考訳（メタデータ） (2021-02-17T19:55:42Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)
• Robust Question Answering Through Sub-part Alignment [53.94003466761305]
  我々はアライメント問題として質問応答をモデル化する。 私たちは、SQuAD v1.1でモデルをトレーニングし、いくつかの逆および外ドメインデータセットでそれをテストします。
  論文  参考訳（メタデータ） (2020-04-30T09:10:57Z)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  関係データベース上でのオントロジーによるクエリの評価について検討する。 OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。 また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
  論文  参考訳（メタデータ） (2020-03-17T16:32:00Z)

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

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