Minimizing Conjunctive Regular Path Queries CCS: Information systems Query languages CCS: Information systems Query reformulation

Diego Figueira, Rémi Morvan, Miguel Romero · 2025

Read Minimizing Conjunctive Regular Path Queries CCS: Information systems Query languages CCS: Information systems Query reformulation by Diego Figueira, Rémi Morvan, Miguel Romero (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-00612.txt.

Introduction

Diego Figueira, Rémi Morvan, and Miguel Romero present a 2025 computer science paper on shrinking database path queries. The queries join patterns along paths in a graph, and users may ask if a query equals a smaller one with at most k parts. Smaller queries cost less to run, so the size in parts drives the search.

The authors show the shrinking question can always be decided, for single queries and for unions of them. For single queries, they give a brute-force method with a high space bound and a lower bound one step below. For unions, the problem matches the known hardness of the containment problem. With simple path forms, the hardness drops to a lower class, again matching containment.

Catalog record

CREATORDiego Figueira, Rémi Morvan, Miguel Romero
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-00612

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Minimizing Conjunctive Regular Path Queries CCS: Information systems Query languages CCS: Information systems Query reformulation Diego Figueira, Rémi Morvan, Miguel Romero Abstract . We study the minimization problem for Conjunctive Regular Path Queries (CRPQs) and unions of CRPQs (UCRPQs). This is the problem of checking, given a query and a number k k , whether the query is equivalent to one of size at most k k . For CRPQs we consider the size to be the number of atoms, and for UCRPQs the maximum number of atoms in a CRPQ therein, motivated by the fact that the number of atoms has a leading influence on the cost of query evaluation. We show that the minimization problem is decidable, both for CRPQs and UCRPQs. We provide a 2ExpSpace upper-bound for CRPQ minimization, based on a brute-force enumeration algorithm, and an ExpSpace lower-bound. For UCRPQs, we show that the problem is ExpSpace-complete, having thus the same complexity as the classical containment problem. The upper bound is obtained by defining and computing a notion of maximal under-approximation. Moreover, we show that for UCRPQs using the so-called simple regular expressions consisting of concatenations of expressions of the form a + a^{+} or a 1 + ⋯ + a k a_{1}+\dotsb+a_{k} , the minimization problem becomes Π 2 p \Pi^{p}_{2} -complete, again matching the complexity of containment. 🖙 This pdf contains internal links: clicking on a notion leads to its definition . 🖙 This article is based on a PODS’25 paper ( Figueira et al. 2025 ) . 1. Introduction Conjunctive Regular Path Queries (CRPQs) and unions of CRPQs (UCRPQs) form the backbone of graph database query languages, including the new ISO standard Graph Query Language (GQL) ( International Organization for Standardization (2024a) ISO ) and the SQL extension for querying graph-structured data SQL/PGQ ( International Organization for Standardization (2024b) ISO ) (see also ( Francis et al. 2023b ; Francis et al. 2023a ) ). These extend the well-known classes of Conjunctive Queries (CQs) and unions of CQs (UCQs), with the ability to reason about paths in a graph. Optimizing and understanding the fundamental properties of such queries has then become a major topic in graph database theory. Static optimization for CRPQs has received considerable attention. The basic study of containment and equivalence problems for CRPQs, possibly with unions and inverses, was initiated over 25 years ago ( Florescu et al. 1998 ; Calvanese et al. 2000 ) , where they were shown to be ExpSpace -complete. These problems have also been investigated under different scenarios: restrictions on the shape of queries ( Figueira 2020 ) , restrictions on their regular languages ( Figueira et al. 2020 ) , alternative semantics ( Figueira and Romero 2023 ) , or under schema information ( Gutiérrez-Basulto et al. 2022 ; Gutiérrez-Basulto et al. 2024 ) . This has enabled the study of more advanced static analysis problems motivated by the following general question: Can a given query be equivalently rewritten as one from a target fragment (which enjoys desirable properties)? In the literature the problem has been studied where the target fragment are queries which either (i) avoid having infinite languages, or (ii) have a tree-like structure. This gives rise to the so-called (i) boundedness problem for CRPQs ( i.e. , whether a CRPQ is equivalent to a UCQ) ( Barceló et al. 2019 ; Figueira et al. 2024 ) , and (ii) semantic treewidth problem for CRPQs ( i.e. , whether a CRPQ is equivalent to one of a given treewidth) ( Barceló et al. 2016 ; Figueira and Morvan 2025 ; Feier et al. 2024 ) . Minimization of queries. Minimization – that is, the problem of transforming a query into a strictly smaller equivalent query – is perhaps the most fundamental query optimization question. This problem corresponds to the question posed above, where the target fragment are queries of bounded sizes. For CQs (and UCQs), minimization is well understood, and there exists a canonical unique minimal query, called the core . The mechanism for obtaining such minimal query is simple: eliminate any atom from the query that results in an equivalent query ( i.e. , any atom which is ‘redundant’ in the sense of equivalence). In contrast, minimization of CRPQs is poorly understood from a theoretical perspective. In this case, the situation is more challenging: there is no natural notion of ‘core’, and it is not clear whether a notion of ‘canonical’ smallest query may even be possible. In particular, eliminating redundant atoms of a CRPQ as done for CQs, in general results in a query which is neither minimal nor canonical. In this paper we study the minimization problem for CRPQs and UCRPQs. In the case of CRPQs, we aim at minimizing the number of atoms of a CRPQ, and hence we formulate the problem as follows ( \mathrel{{\color[rgb]{0.0859,0.2891,0.3477}\equiv}} denotes query equivalence, i.e. , the fact that the queries output the same answer for all databases): 1 1 1 Note that we can always assume k to be smaller than the number of atoms of the input query, since otherwise the instance of the minimization problem is trivially solvable by answering ‘yes’. So, whether k is given in unary or binary does not affect the size of the input. Minimization problem for CRPQs : Input : A finite alphabet \mathbb{A} , a CRPQ \gamma over \mathbb{A} and k\in\mathbb{N} . Question : Is there a CRPQ \delta over \mathbb{A} with at most k atoms such that \gamma\mathrel{{\color[rgb]{0.0859,0.2891,0.3477}\equiv}}\delta ? On the other hand, in the case of UCRPQs, we minimize the maximum number of atoms of the CRPQs participating in a UCRPQ: Minimization problem for UCRPQs : Input : A finite alphabet \mathbb{A} , a UCRPQ \Gamma over \mathbb{A} and k\in\mathbb{N} . Question : Is there a UCRPQ \Delta over \mathbb{A} whose every CRPQ has at most k atoms s.t. \Gamma\mathrel{{\color[rgb]{0.0859,0.2891,0.3477}\equiv}}\Delta ? Observe that the minimization problem for CRPQs and UCRPQs are two different problems: an algorithm for the minimization problem for UCRPQs (where the equivalent query may have unions) in principle does not imply any bound on the minimization for CRPQs (where we insist in being only one CRPQ). Contributions We investigate the minimization problem for CRPQs and UCRPQs, and present several fundamental results. More concretely: • We show that the minimization problem for CRPQs and UCRPQs are both decidable. As explained before, these are different problems and we give two very different algorithms. Contrary as what happens for CQs, minimizing a CRPQ by unions of CRPQs may result in smaller queries, hence in a sense UCRPQ minimization may be seen as a strictly more powerful approach ( Proposition 5.1 ). • For the minimization of CRPQs , the algorithm is essentially by brute-force. By carefully bounding the sizes of the automata involved, we show that the algorithm can be implemented in 2ExpSpace in Theorem 4.1 . We also show an ExpSpace -hard lower bound in 6.2 , leaving an exponential gap. • For the minimization of UCRPQs we can apply a more elegant solution, and in fact we show how to compute ‘maximal under-approximations’ of a query by UCRPQs of a given size ( Lemma 5.3 ). The minimization then follows

Read the complete text