論文の概要: Proving Cypher Query Equivalence

• arxiv url: http://arxiv.org/abs/2504.15742v1
• Date: Tue, 22 Apr 2025 09:45:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-30 21:12:28.585059
• Title: Proving Cypher Query Equivalence
• Title（参考訳）: Cypher Query 等価性の証明
• Authors: Lei Tang, Wensheng Dou, Yingying Zheng, Lijie Xu, Wei Wang, Jun Wei, Tao Huang,
• Abstract要約: GraphQEは2つのCypherクエリが意味論的に等価かどうかを判断する自動計算である。 148対の等価クエリからなるデータセットを構築する。 我々は138対のCypherクエリを証明した。
• 参考スコア（独自算出の注目度）: 12.94125819777699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph database systems store graph data as nodes and relationships, and utilize graph query languages (e.g., Cypher) for efficiently querying graph data. Proving the equivalence of graph queries is an important foundation for optimizing graph query performance, ensuring graph query reliability, etc. Although researchers have proposed many SQL query equivalence provers for relational database systems, these provers cannot be directly applied to prove the equivalence of graph queries. The difficulty lies in the fact that graph query languages (e.g., Cypher) adopt significantly different data models (property graph model vs. relational model) and query patterns (graph pattern matching vs. tabular tuple calculus) from SQL. In this paper, we propose GraphQE, an automated prover to determine whether two Cypher queries are semantically equivalent. We design a U-semiring based Cypher algebraic representation to model the semantics of Cypher queries. Our Cypher algebraic representation is built on the algebraic structure of unbounded semirings, and can sufficiently express nodes and relationships in property graphs and complex Cypher queries. Then, determining the equivalence of two Cypher queries is transformed into determining the equivalence of the corresponding Cypher algebraic representations, which can be verified by SMT solvers. To evaluate the effectiveness of GraphQE, we construct a dataset consisting of 148 pairs of equivalent Cypher queries. Among them, we have successfully proven 138 pairs of equivalent Cypher queries, demonstrating the effectiveness of GraphQE.
• Abstract（参考訳）: グラフデータベースシステムはグラフデータをノードとリレーションシップとして格納し、グラフクエリ言語(例えばCypher)を使用してグラフデータを効率的にクエリする。 グラフクエリの等価性を証明することは、グラフクエリのパフォーマンスを最適化し、グラフクエリの信頼性を保証するための重要な基盤となります。 研究者はリレーショナルデータベースシステムのための多くのSQLクエリ等価プロバーを提案しているが、これらのプロバーはグラフクエリの等価性を証明するために直接適用することはできない。 難点は、グラフクエリ言語(例えば、Cypher)がSQLから大きく異なるデータモデル(プロパティグラフモデルとリレーショナルモデル)とクエリパターン(グラフパターンマッチングとテーブルタプル計算)を採用するという事実にある。 本稿では,2つのCypherクエリが意味論的に等価であるかどうかを判断する自動証明器GraphQEを提案する。 我々は、Cypherクエリのセマンティクスをモデル化するために、U-semiringベースのCypher代数表現を設計する。 我々のCypher代数表現は、非有界半環の代数構造の上に構築されており、プロパティグラフや複雑なCypherクエリにおけるノードと関係を十分に表現することができる。 次に、2つのCypherクエリの等価性を決定することによって、対応するCypher代数表現の等価性を決定する。 GraphQEの有効性を評価するために、128対の等価なCypherクエリからなるデータセットを構築した。 このうち、128対のCypherクエリを成功させ、GraphQEの有効性を実証した。

関連論文リスト

• Text2Cypher: Bridging Natural Language and Graph Databases [0.3774866290142281]
  Text2Cypherは、自然言語クエリをCypherクエリ言語に変換することで、このギャップを埋めることを目指している。 公開されているいくつかのデータセットを合計44,387のインスタンスに組み合わせ、整理し、整理した方法について説明している。
  論文  参考訳（メタデータ） (2024-12-13T11:50:51Z)
• GraphOTTER: Evolving LLM-based Graph Reasoning for Complex Table Question Answering [19.59852014700167]
  複雑なテーブル質問回答は、複雑なレイアウトと柔軟なヘッダロケーションを示す複雑なテーブルに基づいて、特定の質問に対する正確な回答を提供する。 本稿では,正解をピンポイントする推論プロセスを明確に確立するGraphOTTERを提案する。 その後、グラフ上でステップバイステップの推論を行い、各ステップは事前に定義された中間的推論アクションのセットによってガイドされる。
  論文  参考訳（メタデータ） (2024-12-02T07:49:23Z)
• Dinkel: Testing Graph Database Engines via State-Aware Query Generation [7.862046740710873]
  グラフデータベース管理システム(GDBMS)は、グラフデータを格納し、操作し、多くのデータ駆動アプリケーションの中核部分を形成する。 信頼性を確保するために、Cypherでクエリを生成することでGDBMSをテストするいくつかの方法が提案されている。 GDBMSのための複雑なCypherクエリを生成するための、新しい状態認識テスト手法を提案する。
  論文  参考訳（メタデータ） (2024-08-14T13:00:24Z)
• A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs [17.93455358818447]
  ほとんどのニューロシンボリッククエリプロセッサは木のようなグラフパターンクエリに制約されている。 不完全な知識グラフ上で任意のグラフパターンクエリに応答するフレームワークを導入する。
  論文  参考訳（メタデータ） (2023-10-06T21:31:17Z)
• Conversational Semantic Parsing using Dynamic Context Graphs [68.72121830563906]
  汎用知識グラフ(KG)を用いた会話意味解析の課題を,数百万のエンティティと数千のリレーショナルタイプで検討する。 ユーザ発話を実行可能な論理形式にインタラクティブにマッピングできるモデルに焦点を当てる。
  論文  参考訳（メタデータ） (2023-05-04T16:04:41Z)
• 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)
• Improving Text-to-SQL Semantic Parsing with Fine-grained Query Understanding [84.04706075621013]
  トークンレベルのきめ細かいクエリ理解に基づく汎用的モジュール型ニューラルネットワーク解析フレームワークを提案する。 我々のフレームワークは、名前付きエンティティ認識(NER)、ニューラルエンティティリンカ(NEL)、ニューラルエンティティリンカ(NSP)の3つのモジュールから構成されている。
  論文  参考訳（メタデータ） (2022-09-28T21:00:30Z)
• Integrating connection search in graph queries [6.948362325254044]
  SPARQLやCypherといったグラフクエリ言語に接続ツリーパターン(CTP)を統合する方法を示す。 非常に大きな探索空間に対処するため,我々は効率的な刈り込み手法を提案し,我々のアルゴリズムMOLESPがプルーニングでも完備しているケースの集合を正式に確立する。
  論文  参考訳（メタデータ） (2022-08-09T14:27:57Z)
• GraphQ IR: Unifying Semantic Parsing of Graph Query Language with Intermediate Representation [91.27083732371453]
  本稿では,グラフクエリ言語,すなわちGraphQ IRに対する統合中間表現(IR)を提案する。 セマンティックギャップをブリッジするIRの自然言語のような表現と、グラフ構造を維持するための正式に定義された構文によって、ニューラルネットワークによるセマンティックパーシングは、ユーザクエリをより効果的にGraphQ IRに変換することができる。 我々のアプローチは、KQA Pro、Overnight、MetaQAにおける最先端のパフォーマンスを一貫して達成できます。
  論文  参考訳（メタデータ） (2022-05-24T13:59:53Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。 提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
  論文  参考訳（メタデータ） (2022-02-22T01:34:35Z)
• Iterative Context-Aware Graph Inference for Visual Dialog [126.016187323249]
  本稿では,新しいコンテキスト認識グラフ(CAG)ニューラルネットワークを提案する。 グラフの各ノードは、オブジェクトベース(視覚)と履歴関連(テキスト)コンテキスト表現の両方を含む、共同意味機能に対応している。
  論文  参考訳（メタデータ） (2020-04-05T13:09:37Z)

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

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