論文の概要: Polygon: Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search
- arxiv url: http://arxiv.org/abs/2504.06542v1
- Date: Wed, 09 Apr 2025 02:46:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-10 13:07:48.563535
- Title: Polygon: Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search
- Title（参考訳）: Polygon: 衝突駆動型Under-Approximation Searchを用いたSQLのシンボリック推論
- Authors: Pinhan Zhao, Yuepeng Wang, Xinyu Wang,
- Abstract要約: シンボリック推論エンジンは、入力$I$ for $n$クエリを効率的に生成できる。
2つのクエリの等価性を反証し、クエリの集合を曖昧にするのに役立つ。
私たちはこれらのアイデアをPolygonというツールで実装し、30,000以上のベンチマークで評価しました。
- 参考スコア（独自算出の注目度）: 1.8776800987371118
- License:
- Abstract: We present a novel symbolic reasoning engine for SQL which can efficiently generate an input $I$ for $n$ queries $P_1, \cdots, P_n$, such that their outputs on $I$ satisfy a given property (expressed in SMT). This is useful in different contexts, such as disproving equivalence of two SQL queries and disambiguating a set of queries. Our first idea is to reason about an under-approximation of each $P_i$ -- that is, a subset of $P_i$'s input-output behaviors. While it makes our approach both semantics-aware and lightweight, this idea alone is incomplete (as a fixed under-approximation might miss some behaviors of interest). Therefore, our second idea is to perform search over an expressive family of under-approximations (which collectively cover all program behaviors of interest), thereby making our approach complete. We have implemented these ideas in a tool, Polygon, and evaluated it on over 30,000 benchmarks across two tasks (namely, SQL equivalence refutation and query disambiguation). Our evaluation results show that Polygon significantly outperforms all prior techniques.
- Abstract（参考訳）: 提案するSQLのシンボリック推論エンジンは,入力$I$ for $n$ query$P_1, \cdots, P_n$を効率よく生成する。
これは、2つのSQLクエリの等価性を証明せず、クエリの集合を曖昧にするなど、異なるコンテキストで有用である。
私たちの最初のアイデアは、各$P_i$ -- つまり、$P_i$の入出力動作のサブセットのアンダー近似を推論することです。
このアプローチはセマンティクスと軽量の両方を意識していますが、このアイデアだけでは不完全です(固定されたアンダー近似は興味のある振る舞いを見逃すかもしれません)。
したがって、我々の第2のアイデアは、関心のすべてのプログラム動作を包括的にカバーする)非近似の表現的なファミリーを探索することで、我々のアプローチを完了させることである。
私たちはこれらのアイデアをPolygonというツールで実装し、2つのタスク(SQL同値の反響とクエリの曖昧さ)にわたる30,000以上のベンチマークで評価しました。
評価の結果,ポリゴンは従来の手法よりも優れていたことが示唆された。
関連論文リスト
- FLARE: Faithful Logic-Aided Reasoning and Exploration [50.9814063216852]
タスク分解を用いて問題空間をトラバースする新しい手法を提案する。
我々はLarge Language Modelsを使ってソリューションを計画し、クエリを事実に軟式化し、論理プログラミングコードを使って述語する。
提案手法は,生成したコードに対する推論プロセスの忠実度を計算し,外部の解法に頼らずにマルチホップ探索のステップを解析する。
論文 参考訳（メタデータ） (2024-10-14T19:39:11Z) - Benchmarking and Improving Text-to-SQL Generation under Ambiguity [25.283118418288293]
我々はAmbiQTと呼ばれる新しいベンチマークを開発し、各テキストは語彙的および/または構造的あいまいさのために2つのもっともらしいSQLとして解釈できる。
提案するLogicalBeamは,計画ベースのテンプレート生成と制約付きインフィルを併用して,sql論理空間をナビゲートする新しい復号アルゴリズムである。
論文 参考訳（メタデータ） (2023-10-20T17:00:53Z) - UNITE: A Unified Benchmark for Text-to-SQL Evaluation [72.72040379293718]
テキスト・ツー・ドメイン・システムのためのUNIfiedベンチマークを導入する。
公開されているテキストからドメインへのデータセットと29Kデータベースで構成されている。
広く使われているSpiderベンチマークと比較すると、SQLパターンの3倍の増加が紹介されている。
論文 参考訳（メタデータ） (2023-05-25T17:19:52Z) - On polynomially many queries to NP or QMA oracles [0.0]
本稿では,NPやQuantum Merlin-Arthur-oracle(QMA)にアクセスして,決定論的時間で解ける問題の複雑性について検討する。
まず、検証クラス$CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$に対して、「セパレータ番号」$s$のクエリグラフを持つ任意の$PC$マシンをシミュレートできることを示す。
次に、Gottlobの"許容重み付け関数"フレームワークと"フラグキュービット"フレームワークを組み合わせる方法について説明する。
論文 参考訳（メタデータ） (2021-11-03T15:29:01Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。
一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。
情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-18T22:20:12Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Query complexity of heavy hitter estimation [6.373263986460191]
我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-05-29T07:15:46Z) - Query2box: Reasoning over Knowledge Graphs in Vector Space using Box
Embeddings [84.0206612938464]
query2boxは、不完全な知識グラフ上の任意のクエリを推論するための埋め込みベースのフレームワークである。
query2boxは、スケーラブルな方法で$wedge$, $vee$, $exists$で任意の論理クエリを処理可能であることを示す。
本稿では,3つの大規模KGに対するQuery2boxの有効性を示すとともに,クエリ2boxが技術状況に対して最大25%の相対的な改善を達成可能であることを示す。
論文 参考訳（メタデータ） (2020-02-14T11:20:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。