Proving Cypher Query Equivalence

• URL: http://arxiv.org/abs/2504.15742v1
• Date: Tue, 22 Apr 2025 09:45:37 GMT
• Title: Proving Cypher Query Equivalence
• Abstract summary: GraphQE is an automated calculus to determine whether two Cypher queries are semantically equivalent.<n>We construct a dataset consisting of 148 pairs of equivalent queries.<n>We have successfully proven 138 pairs of equivalent Cypher queries.
• Score: 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.

Related papers

• Graph Query Generation with Constraint-guided Large Language Agents [9.418317695662516]
  UniQGen is a constraint-based framework that extracts and refines representative graph query clauses.<n>We demonstrate that UniQGen outperforms state-of-the-art graph query generation techniques in both accuracy and efficiency.<n>We release Cypher outputs and a Neptune-ready Freebase snapshot to support cross-language KGQA research.
  arXiv  Detail & Related papers  (2026-04-09T21:50:47Z)
• STRuCT-LLM: Unifying Tabular and Graph Reasoning with Reinforcement Learning for Semantic Parsing [2.8977258426533115]
  We propose STRuCT-LLM, a unified framework for training large language models (LLMs)<n>Our approach jointly optimize Text-to-aware and Text-to-Cypher tasks using reinforcement learning (RL) combined with Chain-Thought supervision (CoT)
  arXiv  Detail & Related papers  (2025-06-15T22:40:36Z)
• Graph Inference with Effective Resistance Queries [2.2349172369559156]
  We study graph inference using an oracle that returns the effective resistance (ER) between a pair of vertices.<n>Although it is known that an $n$-vertex graph can be uniquely reconstructed from all possible ER queries, little else is known.
  arXiv  Detail & Related papers  (2025-02-25T16:37:25Z)
• Text2Cypher: Bridging Natural Language and Graph Databases [0.3774866290142281]
  Text2Cypher aims to bridge the gap by translating natural language queries into Cypher query language.<n>We show how we combined, cleaned and organized several publicly available datasets into a total of 44,387 instances.
  arXiv  Detail & Related papers  (2024-12-13T11:50:51Z)
• GraphOTTER: Evolving LLM-based Graph Reasoning for Complex Table Question Answering [19.59852014700167]
  Complex Table Question Answering involves providing accurate answers to specific questions based on intricate tables that exhibit complex layouts and flexible header locations. We propose GraphOTTER that explicitly establishes the reasoning process to pinpoint the correct answers. It then conducts step-by-step reasoning on the graph, with each step guided by a set of pre-defined intermediate reasoning actions.
  arXiv  Detail & Related papers  (2024-12-02T07:49:23Z)
• Dinkel: Testing Graph Database Engines via State-Aware Query Generation [7.862046740710873]
  Graph database management systems (GDBMSs) store and manipulate graph data and form a core part of many data-driven applications.<n>To ensure their reliability, several approaches have been proposed to test GDBMSs by generating queries in Cypher.<n>We propose a novel state-aware testing approach to generate complex Cypher queries for GDBMSs.
  arXiv  Detail & Related papers  (2024-08-14T13:00:24Z)
• A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs [17.93455358818447]
  Most neuro-symbolic query processors are constrained to tree-like graph pattern queries. We introduce a framework for answering arbitrary graph pattern queries over incomplete knowledge graphs.
  arXiv  Detail & Related papers  (2023-10-06T21:31:17Z)
• Conversational Semantic Parsing using Dynamic Context Graphs [68.72121830563906]
  We consider the task of conversational semantic parsing over general purpose knowledge graphs (KGs) with millions of entities, and thousands of relation-types. We focus on models which are capable of interactively mapping user utterances into executable logical forms.
  arXiv  Detail & Related papers  (2023-05-04T16:04:41Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• Improving Text-to-SQL Semantic Parsing with Fine-grained Query Understanding [84.04706075621013]
  We present a general-purpose, modular neural semantic parsing framework based on token-level fine-grained query understanding. Our framework consists of three modules: named entity recognizer (NER), neural entity linker (NEL) and neural entity linker (NSP)
  arXiv  Detail & Related papers  (2022-09-28T21:00:30Z)
• Integrating connection search in graph queries [6.948362325254044]
  We show how to integrate connecting tree patterns (CTPs) within a graph query language such as SPARQL or Cypher. To cope with very large search spaces, we propose an efficient pruning technique and formally establish a large set of cases where our algorithm, MOLESP, is complete even with pruning.
  arXiv  Detail & Related papers  (2022-08-09T14:27:57Z)
• GraphQ IR: Unifying Semantic Parsing of Graph Query Language with Intermediate Representation [91.27083732371453]
  We propose a unified intermediate representation (IR) for graph query languages, namely GraphQ IR. With the IR's natural-language-like representation that bridges the semantic gap and its formally defined syntax that maintains the graph structure, neural semantic parsing can more effectively convert user queries into GraphQ IR. Our approach can consistently achieve state-of-the-art performance on KQA Pro, Overnight and MetaQA.
  arXiv  Detail & Related papers  (2022-05-24T13:59:53Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• Iterative Context-Aware Graph Inference for Visual Dialog [126.016187323249]
  We propose a novel Context-Aware Graph (CAG) neural network. Each node in the graph corresponds to a joint semantic feature, including both object-based (visual) and history-related (textual) context representations.
  arXiv  Detail & Related papers  (2020-04-05T13:09:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.