Dinkel: State-Aware and Granular Framework for Validating Graph Databases

• URL: http://arxiv.org/abs/2408.07525v3
• Date: Mon, 29 Sep 2025 15:15:17 GMT
• Title: Dinkel: State-Aware and Granular Framework for Validating Graph Databases
• Abstract summary: Graph database management systems (GDBMSs) have been powering many data-driven applications.<n>We propose a novel and practical approach Dinkel, to thoroughly test GDBMSs.
• Score: 6.966247442329522
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph database management systems (GDBMSs) have been powering many data-driven applications. To ensure GDBMS reliability, several testing approaches have been proposed. However, they all suffer from two key limitations: (1) insufficient support for generating complex and valid queries to exercise deep GDBMS code, and (2) lack of general oracles to validate the execution correctness of arbitrary queries. In this paper, we propose a novel and practical approach Dinkel, to thoroughly test GDBMSs. Our approach consists of two core techniques. First, to generate complex and valid queries, we model two kinds of graph state, query context and graph schema, to describe the Cypher variables and the manipulated graph labels and properties. We generate queries clause-by-clause, and modify the graph states on the fly to ensure each clause references the correct state information. Second, to generally validate query results, we introduce two fine-grained query transformations: clause-level and expression-level transformations. These transformations can operate on arbitrary queries while preserving their semantics. Dinkel validates GDBMSs by checking whether the transformed query produces the same results as the original. We evaluated Dinkel on three well-known GDBMSs. In total, we found 127 bugs, among which 113 were confirmed, 84 were fixed, and 33 were logic bugs. Compared to existing approaches, Dinkel can cover over 70% more code and find substantially more bugs within a 48-hour testing campaign. We expect Dinkel's powerful bug detection to lay a practical foundation for GDBMS testing.

Related papers

• Detecting DBMS Bugs by Constructing Equivalent Representations of Intermediate Query Results [4.984008334354563]
  We propose ERIQ, a novel testing approach for detecting logic bugs.<n>In total, ERIQ detected 64 bugs, 63 of which were confirmed by developers, and two have been fixed.
  arXiv  Detail & Related papers  (2026-08-31T07:41:09Z)
• Towards Researcher Agents for Knowledge-Graph Question Answering [0.0]
  We present an agentic text-to-SPARQL system that goes one step beyond static tool-using agents.<n>We instantiate the loop on DBpedia, evolve nine successive versions of the agent driven by a low-cost reasoning model, and deploy the best-performing configuration.
  arXiv  Detail & Related papers  (2026-08-07T18:42:53Z)
• Graph-Aware Fuzzing for Graph Database Management Systems [22.261896283072137]
  We propose GRAF, a black box fuzzing framework for GDBMS query engines.<n>It generates valid and structurally diverse queries under complex graph constraints.<n>It applies five graph specific mutation operators guided by execution state feedback, including execution time, result size, and system status.<n> GRAF consistently improves line coverage by 31.6% to 41.1% over the strongest baseline on each target.
  arXiv  Detail & Related papers  (2026-07-04T07:08:14Z)
• A Set-Theoretic Approach to Detecting Logic Bugs in DBMS Inner Join Optimizations [15.757749995343715]
  We propose a testing approach to detect bugs related to INNER JOIN optimization through the lens of set theory.<n>We implement this design in JoinEquiv, which serves as an oracle testing executor.
  arXiv  Detail & Related papers  (2026-06-22T13:09:04Z)
• Rethinking RAG in Long Videos: What to Retrieve and How to Use It? [56.38819694781005]
  We introduce V-RAGBench, a benchmark of $langle$query, evidence chunk, answer$rangle$ triplets that enables faithful, decoupled evaluation of retrieval and generation.<n>We also present CARVE, a method that runs parallel retrievers across configurations and employs chunk-adaptive reranking to identify the winning configuration for each chunk.
  arXiv  Detail & Related papers  (2026-06-11T10:05:49Z)
• FineVerify: Scaling Test-Time Compute with Fine-Grained Self-Verification for Agentic Search [88.16262636915975]
  FineVerify is a fine-grained self-verification framework for agentic search.<n>It decomposes each question into checkable sub-questions, verifies sampled candidates, and selects the candidate with the highest aggregated score.<n>FineVerify consistently outperforms standard scaling baselines.
  arXiv  Detail & Related papers  (2026-05-30T10:21:20Z)
• GREPO: A Benchmark for Graph Neural Networks on Repository-Level Bug Localization [50.009407518866965]
  Repository-level bug localization is a critical software engineering challenge.<n>GNNs offer a promising alternative due to their ability to model complex, repository-wide dependencies.<n>We introduce GREPO, the first GNN benchmark for repository-scale bug localization tasks.
  arXiv  Detail & Related papers  (2026-02-14T23:22:15Z)
• CompassVerifier: A Unified and Robust Verifier for LLMs Evaluation and Outcome Reward [50.97588334916863]
  We develop CompassVerifier, an accurate and robust lightweight verifier model for evaluation and outcome reward.<n>It demonstrates multi-domain competency spanning math, knowledge, and diverse reasoning tasks, with the capability to process various answer types.<n>We introduce VerifierBench benchmark comprising model outputs collected from multiple data sources, augmented through manual analysis of metaerror patterns to enhance CompassVerifier.
  arXiv  Detail & Related papers  (2025-08-05T17:55:24Z)
• ImpliRet: Benchmarking the Implicit Fact Retrieval Challenge [50.93758649363798]
  Impliret is a benchmark that shifts the reasoning challenge to document-side processing.<n>We evaluate a range of sparse and dense retrievers, all of which struggle in this setting.
  arXiv  Detail & Related papers  (2025-06-17T11:08:29Z)
• Proving Cypher Query Equivalence [12.94125819777699]
  GraphQE is an automated calculus to determine whether two Cypher queries are semantically equivalent. We construct a dataset consisting of 148 pairs of equivalent queries. We have successfully proven 138 pairs of equivalent Cypher queries.
  arXiv  Detail & Related papers  (2025-04-22T09:45:37Z)
• GraphRAFT: Retrieval Augmented Fine-Tuning for Knowledge Graphs on Graph Databases [0.0]
  GraphRAFT is a retrieve-and-reason framework that finetunes LLMs to generate provably correct Cypher queries. Our method is the first such solution that can be taken off-the-shelf and used on Knowledge Graphs stored in native graph DBs.
  arXiv  Detail & Related papers  (2025-04-07T20:16:22Z)
• Parser Knows Best: Testing DBMS with Coverage-Guided Grammar-Rule Traversal [6.300885279363564]
  We propose Fuzz, a novel fuzzing framework that automatically extracts grammar rules from built-in syntaxs' built-in definition files forsql generation.<n>Fuzz can generate diverse query statements to saturate the grammar features of the testeds, which grammar features could be missed by previous tools.<n>In our evaluation, Fuzz outperforms all state-of-the-art existing testing tools in terms of bug finding, grammar rule coverage and code coverage.
  arXiv  Detail & Related papers  (2025-03-05T20:50:41Z)
• Top Ten Challenges Towards Agentic Neural Graph Databases [56.92578700681306]
  Graph databases (GDBs) like Neo4j and TigerGraph excel at handling interconnected data but lack advanced inference capabilities. This paper introduces Agentic Neural Graph Databases (Agentic NGDBs), which extend NGDBs with three core functionalities.
  arXiv  Detail & Related papers  (2025-01-24T04:06:50Z)
• Constant Optimization Driven Database System Testing [6.246028398098516]
  Logic bugs are bugs that can cause database management systems (DBMSs) to silently produce incorrect results for given queries.<n>We propose Constant-Optimization-Driven Database Testing (CODDTest) as a novel approach for detecting logic bugs in databases.
  arXiv  Detail & Related papers  (2025-01-20T03:32:55Z)
• Auto-Cypher: Improving LLMs on Cypher generation via LLM-supervised generation-verification framework [4.080333216826685]
  We present an automated, LLM-Supervised, pipeline to generate high-quality synthetic data for Text2Cypher. Our Cypher data generation pipeline introduces LLM-As-Database-Filler, a novel strategy for ensuring Cypher query correctness. Using our pipeline, we generate high quality Text2Cypher data - SynthCypher containing 29.8k instances across various domains and queries with varying complexities.
  arXiv  Detail & Related papers  (2024-12-17T07:21:25Z)
• Towards Evaluating Large Language Models for Graph Query Generation [49.49881799107061]
  Large Language Models (LLMs) are revolutionizing the landscape of Generative Artificial Intelligence (GenAI) This paper presents a comparative study addressing the challenge of generating queries a powerful language for interacting with graph databases using open-access LLMs. Our empirical analysis of query generation accuracy reveals that Claude Sonnet 3.5 outperforms its counterparts in this specific domain.
  arXiv  Detail & Related papers  (2024-11-13T09:11:56Z)
• Combining LLMs and Knowledge Graphs to Reduce Hallucinations in Question Answering [0.0]
  Large Language Models (LLM) and Knowledge Graphs (KG) are combined to improve the accuracy and reliability of question-answering systems. Our method incorporates a query checker that ensures the syntactical and semantic validity of LLM-generated queries. To make this approach accessible, a user-friendly web-based interface has been developed.
  arXiv  Detail & Related papers  (2024-09-06T10:49:46Z)
• DAC: Decomposed Automation Correction for Text-to-SQL [51.48239006107272]
  We introduce De Automation Correction (DAC), which corrects text-to-composed by decomposing entity linking and skeleton parsing. We show that our method improves performance by $3.7%$ on average of Spider, Bird, and KaggleDBQA compared with the baseline method.
  arXiv  Detail & Related papers  (2024-08-16T14:43:15Z)
• BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrieval [54.54576644403115]
  We introduce BRIGHT, the first text retrieval benchmark that requires intensive reasoning to retrieve relevant documents.<n>Our dataset consists of 1,384 real-world queries spanning diverse domains, such as economics, psychology, mathematics, and coding.<n>We show that incorporating explicit reasoning about the query improves retrieval performance by up to 12.2 points.
  arXiv  Detail & Related papers  (2024-07-16T17:58:27Z)
• UQE: A Query Engine for Unstructured Databases [71.49289088592842]
  We investigate the potential of Large Language Models to enable unstructured data analytics. We propose a new Universal Query Engine (UQE) that directly interrogates and draws insights from unstructured data collections.
  arXiv  Detail & Related papers  (2024-06-23T06:58:55Z)
• Database-Augmented Query Representation for Information Retrieval [59.57065228857247]
  We present a novel retrieval framework called Database-Augmented Query representation (DAQu) DAQu augments the original query with various (query-related) metadata across multiple tables. We validate DAQu in diverse retrieval scenarios that can incorporate metadata from the relational database.
  arXiv  Detail & Related papers  (2024-06-23T05:02:21Z)
• MCS-SQL: Leveraging Multiple Prompts and Multiple-Choice Selection For Text-to-SQL Generation [10.726734105960924]
  Large language models (LLMs) have enabled in-context learning (ICL)-based methods that significantly outperform fine-tuning approaches for text-to- tasks. This study considers the sensitivity of LLMs to the prompts and introduces a novel approach that leverages multiple prompts to explore a broader search space for possible answers. We establish a new SOTA performance on the BIRD in terms of both the accuracy and efficiency of the generated queries.
  arXiv  Detail & Related papers  (2024-05-13T04:59:32Z)
• Testing Database Engines via Query Plan Guidance [6.789710498230718]
  We propose the concept of Query Plan Guidance (QPG) for guiding automated testing towards "interesting" test cases. We apply our method to three mature, widely-used, and diverse database systems-DBite, TiDB, and Cockroach-and found 53 unique, previously unknown bugs.
  arXiv  Detail & Related papers  (2023-12-29T08:09:47Z)
• Detecting DBMS Bugs with Context-Sensitive Instantiation and Multi-Plan Execution [11.18715154222032]
  This paper aims to solve the two challenges, including how to generate semantically correctsql queries in a test case, and how to propose effective oracles to capture logic bugs. We have implemented a prototype system called Kangaroo and applied three widely used and well-tested semantic codes. The comparison between our system with the state-of-the-art systems shows that our system outperforms them in terms of the number of generated semantically valid queries, the explored code paths during testing, and the detected bugs.
  arXiv  Detail & Related papers  (2023-12-08T10:15:56Z)
• CERT: Finding Performance Issues in Database Systems Through the Lens of Cardinality Estimation [6.789710498230718]
  We propose Cardinality Restriction Testing (CERT), a technique that finds performance issues through the lens of cardinality estimation. CERT tests cardinality estimation specifically, because they were shown to be the most important part for query optimization.
  arXiv  Detail & Related papers  (2023-06-01T05:21:31Z)
• 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)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  We propose a query embedding method to answer complex logical queries on knowledge graphs with missing edges. The answer entities are selected according to the similarities between the entity embeddings and the query embedding. A complex KG query answering method, Q2P, is proposed to retrieve diverse answers from different areas over the embedding space.
  arXiv  Detail & Related papers  (2022-04-27T11:16:08Z)
• Bridging Textual and Tabular Data for Cross-Domain Text-to-SQL Semantic Parsing [110.97778888305506]
  BRIDGE represents the question and DB schema in a tagged sequence where a subset of the fields are augmented with cell values mentioned in the question. BRIDGE attained state-of-the-art performance on popular cross-DB text-to- relational benchmarks. Our analysis shows that BRIDGE effectively captures the desired cross-modal dependencies and has the potential to generalize to more text-DB related tasks.
  arXiv  Detail & Related papers  (2020-12-23T12:33:52Z)

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.