Amela Fejza
email: amela.fejza@inria.fr

Pierre Genevès
email: pierre.geneves@inria.fr

Nabil Layaïda
email: nabil.layaida@inria.fr

Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers

Query optimizers built on the transformation-based Volcano/Cascades framework are used in many database systems. Transformations proposed earlier on the logical query dag (LQDAG) data structure, which is key in such a framework, focus only on recursion-free queries. In this paper, we propose the recursive logical query dag (RLQDAG) which extends the LQDAG with the ability to capture and transform recursive queries, leveraging recent developments in recursive relational algebra. Specifically, this extension includes: (i) the ability of capturing and transforming sets of recursive relational terms thanks to (ii) annotated equivalence nodes used for guiding transformations that are more complex in the presence of recursion; and (iii) RLQDAG rewrite rules that transform sets of subterms in a grouped manner, instead of transforming individual terms in a sequential manner; and that (iv) incrementally update the necessary annotations. Core concepts of the RLQDAG are formalized using a syntax and formal semantics with a particular focus on subterm sharing and recursion. The result is a clean generalization of the LQDAG transformation-based approach, enabling more efficient explorations of plan spaces for recursive queries. An implementation of the proposed approach shows significant performance gains compared to the state-of-the-art.

INTRODUCTION

Recursive queries enable powerful information extraction, especially from linked data structures such as trees and graphs. However, important data management system components, such as the widely used Volcano framework [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF], were designed for recursion-free queries. A typical transformation-based query optimizer operates by (i) translating a query into a relational algebraic term, (ii) applying algebraic transformations in order to search for equivalent yet more efficient evaluation plans, during a so-called plan enumeration phase, (iii) executing the query by running one of the explored plans. Works on extending relational algebra (RA) with recursion [START_REF] Abiteboul | Foundations of Databases: The Logical Level[END_REF][START_REF] Bancilhon | An Amateur's Introduction to Recursive Query Processing Strategies[END_REF] resulted in powerful recursive relational algebras [START_REF]Alpha: an extension of relational algebra to express a class of recursive queries[END_REF][START_REF] Aho | Universality of Data Retrieval Languages[END_REF][START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF], capable of capturing queries with transitive closures [START_REF]Alpha: an extension of relational algebra to express a class of recursive queries[END_REF] and even more general forms of recursion [START_REF] Aho | Universality of Data Retrieval Languages[END_REF][START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF]. This line of works recently led to 𝜇-RA [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] which provides a rich set of rewrite rules for recursive terms enabling efficient recursive evaluation plans not available with earlier approaches. The enumeration phase is crucial as it may produce terms which are drastically more efficient. It has been heavily researched for recursion-free queries. It is common practice to allocate a time budget for this enumeration phase, as it is notoriously known that exhaustive plan space explorations may not be feasible in practice for certain queries. The faster we generate the space of equivalent plans, the more likely we will be able to find terms with more efficient evaluation. With recursion, plan spaces are often significantly larger than in the non-recursive setting, due to new interplays between recursive and non-recursive operators. The efficiency of recursive plan enumeration becomes critical. The speed of plan enumeration directly determines whether query evaluation plans enabled by, e.g. 𝜇-RA [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF], are within range or theoretically reachable, but still out of reach for a practical query optimizer. This motivates the search for efficient methods for enumerating recursive plans.

Contributions. We present the recursive logical query dag (RLQDAG), which extends Volcano's LQDAG [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF] and the 𝜇-RA framework [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] for the purpose of efficiently enumerating recursive query plans. Contributions include the first extension of the LQDAG with the support of recursive terms; a formalization of important RLQDAG concepts in terms of formal syntax and semantics, with a particular focus on the sharing of common subterms in the presence of recursion; RLQDAG transformations that generalize rewrite rules for individual recursive terms of [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] and enable efficient and grouped transformations of sets of recursive terms. The RLQDAG relies on a concept of annotated equivalence nodes with incremental updates, used for guiding transformations of recursive subterms. Contributions also include a complete implementation of the proposed approach; and experimental assessments using third-party queries on synthetic and real datasets.

BACKGROUND AND RELATED WORK 2.1 Approaches in recursive query optimization

Recursion is considered in only a small fraction of the numerous works on query optimization. Three main lines of work with recursive queries can be identified:

• The Datalog line of works [START_REF] Alvaro | Dedalus: Datalog in Time and Space[END_REF][START_REF] Fan | Scaling-Up In-Memory Datalog Processing: Observations and Techniques[END_REF][START_REF] Francis-Landau | Evaluation of Logic Programs with Built-Ins and Aggregation: A Calculus for Bag Relations[END_REF][START_REF] Shan | Datalog and Emerging Applications: An Interactive Tutorial[END_REF][START_REF] Seo | SociaLite: An Efficient Graph Query Language Based on Datalog[END_REF][START_REF] Shkapsky | Big Data Analytics with Datalog Queries on Spark[END_REF][START_REF] Vianu | Datalog Unchained[END_REF][START_REF] Wang | Asynchronous and Fault-Tolerant Recursive Datalog Evaluation in Shared-Nothing Engines[END_REF] developed methods for optimizing recursive queries formulated in Datalog: magic-sets [START_REF] Bancilhon | Magic Sets and Other Strange Ways to Implement Logic Programs (Extended Abstract)[END_REF][START_REF] Gardarin | Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs[END_REF][START_REF] Saccà | On the Implementation of a Simple Class of Logic Queries for Databases[END_REF], demand transformations [START_REF] Tekle | More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets[END_REF], automated reversals [START_REF] Naughton | Efficient Evaluation of Right-, Left-, and Multi-Linear Rules[END_REF], and the FGH rule [START_REF] Yisu | Optimizing Recursive Queries with Program Synthesis[END_REF].

Although the syntax of Datalog greatly differs from RA, the effects of magic-sets [START_REF] Bancilhon | Magic Sets and Other Strange Ways to Implement Logic Programs (Extended Abstract)[END_REF][START_REF] Gardarin | Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs[END_REF][START_REF] Saccà | On the Implementation of a Simple Class of Logic Queries for Databases[END_REF] and of demand transformations [START_REF] Tekle | More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets[END_REF] are comparable to pushing certain kinds of selections and projections. These techniques are very sensitive to whether the Datalog program is written in a left-linear or right-linear manner, but one can use the automated reversal technique proposed in [START_REF] Naughton | Efficient Evaluation of Right-, Left-, and Multi-Linear Rules[END_REF] to fully exploit them. The optimization framework proposed in [START_REF] Yisu | Optimizing Recursive Queries with Program Synthesis[END_REF] gathers magic-sets, semi-naive evaluation and proposes a new FGH rule for optimizing recursive Datalog programs with aggregations.

Datalog engines do not explore plan spaces but use heuristics to find a good plan to evaluate queries. However, currently, no matter which combination of existing Datalog optimizations a Datalog engine implements, it will not be able to find plans where recursions have been merged automatically similar to those found by the 𝜇-RA approach [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF]. This is because, currently, in a Datalog program corresponding to the optimized translation of A + /B + at least one of the two transitive closures A + or B + will be fully materialized (even if there is no solution to A + /B + ). On real datasets, this can make Datalog query evaluation an order of magnitude slower than query evaluation with RA-based systems, as noticed in [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF]. • The line of works based on relational algebra [START_REF]Alpha: an extension of relational algebra to express a class of recursive queries[END_REF][START_REF] Aho | Universality of Data Retrieval Languages[END_REF][START_REF] Codd | A Relational Model of Data for Large Shared Data Banks[END_REF][START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF][START_REF] Kifer | On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering[END_REF] attempts to extend relational algebra with operators to capture forms of recursion. For instance, 𝛼-RA [START_REF]Alpha: an extension of relational algebra to express a class of recursive queries[END_REF] extends RA with an operator to capture transitive closures. LFP-RA [START_REF] Aho | Universality of Data Retrieval Languages[END_REF] proposes a more general least fixpoint operator, and an extension of this work gave effective criteria for optimization in its presence [START_REF] Kifer | On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering[END_REF]. Recently, 𝜇-RA [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] proposed to extend RA with a 𝜇 operator which is also a fixpoint with an appropriate set of restrictions. This enables 𝜇-RA to combine all earlier RA-based recursion optimization rules in the same framework [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF], while adding new rewrite rules for recursive terms, in particular for merging recursions. This makes 𝜇-RA the most advanced system for RA-based recursive query optimization as it can generate plans not reachable by other approaches. The approach that we propose in this paper extends 𝜇-RA with a new method for enumerating recursive plans much more efficiently, thanks to a generalization of the rules presented in 𝜇-RA so that the generalized rules (presented in Section 4) apply directly on a factorized representation on the recursive plan space. Among the benefits, this makes it possible to apply transformations on sets of algebraic terms at once (instead of successively on individual terms), and to exploit the sharing of common subterms to avoid redundant computations. • Ad-hoc optimizations for regular queries. Both Datalogbased and RA-based approaches can capture queries with expressive forms of recursion, going beyond regularity. Several works have focused on optimizing queries in which recursion is restricted to regular patterns, such as regular path queries (RPQs). Automata based approaches have been developed to answer RPQ queries [START_REF] Goldman | Dataguides: Enabling query formulation and optimization in semistructured databases[END_REF][START_REF] Koschmieder | Regular path queries on large graphs[END_REF][START_REF] Zauner | A RPL through RDF: Expressive navigation in RDF graphs[END_REF]. A hybrid approach that combines finite state machines and 𝛼-RA is presented in [START_REF] Yakovets | WAVEGUIDE: Evaluating SPARQL Property Path Queries[END_REF] and extended in [START_REF] Abul-Basher | Tasweet: optimizing disjunctive regular path queries in graph databases[END_REF]. All these works are limited to RPQs and their unions or conjunctions. In comparison, the work we present in this paper supports more expressive forms of recursion, that may include non-regular patterns (see e.g. the experimental section 5 with queries of the form 𝐴 𝑛 𝐵 𝑛 for instance).

Limits of the RA-based approach

The RA line of work offers several advantages including high expressivity and rich plan spaces. In addition, it can be seen as an interesting approach for extending the (non-recursive) RA approach already widely used in RDBMS implementations. One main limit however, is that the whole approach critically depends on the ability to quickly enumerate plans during the plan exploration phase. While plan enumeration has not been studied yet in the presence of recursion, it has been extensively studied for recursion-free queries.

Plan enumeration for non-recursive (SPJ) queries

Most of the works on plan enumeration focus on select-projectjoin (SPJ) queries. Techniques proposed for SPJ can be divided into two main groups: bottom-up and top-down approaches. Bottomup approaches generate the plan space by starting from the leaves (initial relations) and going up in the tree of operators when progressively exploring alternate combinations of operators. In contrast, top-down approaches start from the root and recursively explore subbranches in search for possible alternatives.

Bottom-up approaches.

Pioneering and seminal works on the bottom-up approach were proposed in [START_REF] Selinger | Access Path Selection in a Relational Database Management System[END_REF] with refinements in execution strategies [START_REF] Guy | Query Processing in R*[END_REF] and the Starburst plan generator [START_REF] Haas | Extensible Query Processing in Starburst[END_REF][START_REF] Guy | Grammar-like Functional Rules for Representing Query Optimization Alternatives[END_REF].

More recently, E-Graphs [START_REF] Willsey | egg: Fast and extensible equality saturation[END_REF] and equality saturation techniques [START_REF] Tate | Equality Saturation: A New Approach to Optimization[END_REF] introduced in the context of SMT solvers have been used in the database community to optimize recursion-free relational and tensor algebra [START_REF] Schleich | Optimizing Tensor Programs on Flexible Storage[END_REF][START_REF] Yisu | SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra[END_REF]. E-graph [START_REF] Willsey | egg: Fast and extensible equality saturation[END_REF] basically corresponds to the LQDAG [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF] (also known as AND-OR-DAG), as noticed in [START_REF] Yisu | SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra[END_REF]. In comparison to LQDAG and E-Graph, that do not support recursive queries, RLQDAG adds the support for recursion. E-Graph is fundamentally bottom-up, whereas RLQDAG relies on top-down search to prune the search space. The top-down aspect of RLQDAG is essential to solve the problem of exploring recursive plans, since transformations of sets of recursive subterms critically rely on a complete view of recursive patterns.

Top-down approaches.

The top-down approach was introduced with EXODUS [START_REF] Graefe | The EXODUS Optimizer Generator[END_REF] and the seminal works on Volcano [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF] and Cascades [START_REF] Graefe | The Cascades Framework for Query Optimization[END_REF] that added memoization to increase efficiency. The purpose of memoization is to re-use information already found in order to avoid redundant calculations. An advantage of the topdown approach is that it makes it possible to use branch and bound pruning, as noticed in [START_REF] Shapiro | Exploiting Upper and Lower Bounds in Top-Down Query Optimization[END_REF].

All the previous approaches focus mainly on SPJ queries, with some extensions to support outer joins [START_REF] Fender | Counter Strike: Generic Top-down Join Enumeration for Hypergraphs[END_REF][START_REF] Fender | Top down plan generation: From theory to practice[END_REF][START_REF] Galindo-Legaria | How to extend a conventional optimizer to handle one-and two-sided outerjoin[END_REF][START_REF] Galindo-Legaria | Outerjoin simplification and reordering for query optimization[END_REF][START_REF] Moerkotte | On the correct and complete enumeration of the core search space[END_REF] and aggregations [START_REF] Chaudhuri | Including group-by in query optimization[END_REF]. Very few works consider other operators, as noticed in [START_REF] Chaudhuri | An Overview of Query Optimization in Relational Systems[END_REF] and [START_REF] Shanbhag | Optimizing Join Enumeration in Transformation-Based Query Optimizers[END_REF]. To the best of our knowledge, plan enumeration for transformation-based query optimizers has not been studied yet in the presence of recursive operators.

Union and recursion greatly extend the expressive power of SPJ queries. However, they not only make plan enumeration significantly more complex, but they also generate significantly larger plan spaces. This is because their addition generates many new possible combinations to be explored due to new interplays, for instance between unions and joins (e.g. distributivity of natural join over union) or between recursions and joins. This worsens the combinatorics of plans to be enumerated and motivates even more the interest of finding efficient techniques for enumerating recursive plans.

The logical query dag (LQDAG)

The method that we propose extends a key component used in the top-down enumeration approach: the logical query dag (LQDAG). The LQDAG is a directed acyclic graph data structure used to represent and generate the logical plan space. It was introduced in [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF] and improved in [START_REF] Graefe | The Cascades Framework for Query Optimization[END_REF] by the same authors. It is also well described as the AND-OR-DAG in [START_REF] Roy | Efficient and Extensible Algorithms for Multi Query Optimization[END_REF][START_REF] Shanbhag | Optimizing Join Enumeration in Transformation-Based Query Optimizers[END_REF] where it is used for detecting and unifying common subexpressions for multi-query optimization [START_REF] Roy | Efficient and Extensible Algorithms for Multi Query Optimization[END_REF]; and for generating the space of cross-product free join trees [START_REF] Shanbhag | Optimizing Join Enumeration in Transformation-Based Query Optimizers[END_REF].

The LQDAG contains nodes of two different types: equivalence nodes and operation nodes. Equivalence nodes can only have operation nodes as children and vice versa: operation nodes can only have equivalence nodes as children. The purpose of an equivalence node is to explicitly regroup equivalent subterms. An operation node corresponds to an algebraic operation like: join (⊲⊳), filter (𝜎 𝜃 ) etc. The LQDAG can be seen as a factorized representation of a set of terms.

Inspired from [START_REF] Roy | Efficient and Extensible Algorithms for Multi Query Optimization[END_REF], Figure 1 illustrates a sample LQDAG and its expansion obtained after the application of commutativity and associativity rules for the join operator.

THE RLQDAG

The RLQDAG extends the LQDAG with the ability to capture and transform sets of recursive terms.

Syntax

First of all, we propose a syntax for the RLQDAG. The purpose is to be able to syntactically express a term that denotes a (potentially very large) set of recursive algebraic terms. This makes it possible to develop transformations of sets of terms formally (i.e. with a high level of precision), and express them as rewrite rules that transform one RLQDAG term 𝑑 into another RLQDAG term 𝑑 ′ . The syntax of RLQDAG terms, given in Fig. 2, focuses on formalizing the concepts of equivalence nodes, operation nodes, sharing of common subterms, and recursion. An equivalence node is a node that can have several operation nodes 𝑑 as children, possibly with binders. The binder construct "let 𝑌 = 𝛼 1 in 𝛼 2 " enables the explicit sharing of a common equivalence node 𝛼 1 within the branches of another equivalence node 𝛼 2 . For that purpose, it assigns a new fresh reference name 𝑌 to 𝛼 1 , and allows 𝑌 to be used multiple times in 𝛼 2 as a reference to Recursive RLQDAGs can be expressed using fixpoint operation nodes. The principle, inspired from earlier works in recursive relational algebras [START_REF] Aho | Universality of Data Retrieval Languages[END_REF][START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF], consists in the introduction of a least-fixpoint binder operation node (𝜇) that binds a fresh variable 𝑋 to some expression in which the variable 𝑋 can appear, thus explicitly denoting recursion. In the RLQDAG, as defined in the abstract syntax of Fig. 2 and illustrated in Fig. 3, a fixpoint operator node is written 𝜇𝑋 . 𝛾 ∪ 𝛼 𝑟𝑒𝑐 . The first operand 𝛾 is an equivalence node that models the constant part (the base case) of the recursion. 𝑋 cannot occur within 𝛾. The other equivalence node 𝛼 𝑟𝑒𝑐 is the recursive part. An important aspect is that 𝛼 𝑟𝑒𝑐 contains at least one free occurrence of the recursive variable 𝑋 . This is a major difference between the fixpoint operation node and the other operation nodes. This aspect will lead to a number of new definitions and formal developments. This is because depending on how the recursive variable is used in that branch, the transformation and sharing of subterms in the RLQDAG may, or may not, be allowed.

For example, on the Yago graph dataset [START_REF] Yago | YAGO: A high-quality knowledge base[END_REF], the query Q 𝑒 1 :

?𝑠, ?𝑡 ← ?𝑠 isLocatedIn+ ?𝑡 retrieves all pairs (𝑠, 𝑡) of source and target nodes connected by a path composed of a sequence of edges labeled isLocatedIn (transitive closure). The following RLQDAG term Σ corresponds to query

Q 𝑒 1 : 𝜇𝑋 . isLocIn ∪ 𝜋 𝑚 𝜌 𝑚 𝑡 ( isLocIn ) ⊲⊳ 𝜌 𝑚 𝑠 ( 𝑋 ) ℜ 𝔇
It makes recursion explicit using the fixpoint operator. The equivalence node for the constant part contains the relation variable isLocIn whose column names are 𝑠 and 𝑡. The equivalence node for the recursive part is composed of a join between the recursive variable 𝑋 with the relation variable isLocIn. Here, the path traversal is performed from right to left, by introducing a temporary column name "𝑚" and renaming the columns so that the natural join is performed on the only common column "𝑚" before "𝑚" is discarded by the antiprojection. Fig. 3 illustrates the RLQDAG of Q 𝑒 1 with two recursive subterms Σ and Σ ′ . Notice that Σ ′ is semantically equivalent to Σ and encodes the left to right direction of traversal using a different column renaming in the recursive part. In a RLQDAG, the recursive equivalence node of each fixpoint operation node is annotated with annotations 𝔇 and ℜ. These annotations will be useful for guiding the application of transformations and will be defined and explained in Section 3.4.

There are two reasons why we distinguish 𝛼 𝑟𝑒𝑐 from a general equivalence node 𝛼 in the abstract syntax. The first reason is that those equivalence nodes for recursive parts are equipped with annotations (see Section 3.5.). The second reason is that we want to allow a maximum level of sharing while preventing the sharing of subterms with free occurences of a recursive variable. We thus forbid the use of the binding construct to share subterms with free variables.

We consider the following restrictions over the abstract syntax presented in Fig. 2: we consider only positive, linear and non mutually recursive RLQDAG terms: (i) positive means that recursive variables only appear in the left-hand operand of an antijoin operator node; (ii) linear means that one of the operands in a join or antijoin operator node is constant in the free variable; (iii) Non-mutually recursive terms means that fixpoint operator nodes are properly nested so that there is only one free variable in any subbranch of an annotated equivalence node (this variable may occur several times). These restrictions define a subset of RLQDAG terms that simplifies the theory while supporting the encoding of expressive queries like union of conjunctive regular path queries (UCRPQs).

Semantics of RLQDAG terms

The interpretation of a RLQDAG term is the set of all recursive relational algebraic terms that it represents. Formally, the semantics of a RLQDAG [𝛼] is a set of 𝜇-RA terms as defined by the functions 𝑆 𝛼 and 𝑆 𝛾 presented in Fig. 4, where 𝐸 denotes a variable environment used to keep track of the variable definitions introduced by binders for the sharing of subterms. The interpretation of a RLQDAG A well-formed RLQDAG is a RLQDAG whose interpretation is a set of semantically equivalent terms:

[𝛼] is 𝑆 𝛼 𝛼 ∅ . 𝑆 𝛾 [𝛼 ] 𝐸 = 𝑆 𝛼 𝛼 𝐸 𝑆 𝛾 𝑌 𝐸 = 𝑆 𝛼 𝐸 (𝑌 ) 𝐸 𝑆 𝛼 𝑑 𝐸 = 𝑆 𝑑 𝑑 𝑆 𝛼 𝑑, 𝛼 𝐸 = 𝑆 𝑑 𝑑 ∪ 𝑆 𝛼 𝛼 𝐸 𝑆 𝛼 let 𝑌 = 𝛼 1 in 𝛼 2 𝐸 = 𝑆 𝛼 𝛼 2 𝐸 ⊕{𝑌 ↦ →𝛼 1 } 𝑆 𝑑 𝑋 = 𝑋 𝑆 𝑑 𝜎 𝑓 (𝛾 ) = { 𝜎 𝑓 (𝑡 ) | 𝑡 ∈ 𝑆 𝛾 𝛾 𝐸 } 𝑆 𝑑 𝛾 1 ⊲⊳ 𝛾 2 = { 𝑡 ⊲⊳ 𝑡 ′ | 𝑡 ∈ 𝑆 𝛾 𝛾 1 𝐸 ∧ 𝑡 ′ ∈ 𝑆 𝛾 𝛾 2 𝐸 } 𝑆 𝑑 𝛾 1 ⊲ 𝛾 2 = { 𝑡 ⊲ 𝑡 ′ | 𝑡 ∈ 𝑆 𝛾 𝛾 1 𝐸 ∧ 𝑡 ′ ∈ 𝑆 𝛾 𝛾 2 𝐸 } 𝑆 𝑑 𝛾 1 ∪ 𝛾 2 = { 𝑡 ∪ 𝑡 ′ | 𝑡 ∈ 𝑆 𝛾 𝛾 1 𝐸 ∧ 𝑡 ′ ∈ 𝑆 𝛾 𝛾 2 𝐸 } 𝑆 𝑑 𝜌 𝑏 𝑎 (𝛾 ) = { 𝜌 𝑏 𝑎 (𝑡 ) | 𝑡 ∈ 𝑆 𝛾 𝛾 𝐸 } 𝑆 𝑑 𝜋 𝑎 (𝛾 ) = { 𝜋 𝑎 (𝑡 ) | 𝑡 ∈ 𝑆 𝛾 𝛾 𝐸 } 𝑆 𝑑 𝜇𝑋 . 𝛾 ∪ 𝛼 𝑟𝑒𝑐 = {𝜇𝑋 . 𝑡 ∪ 𝑡 𝑟𝑒𝑐 | 𝑡 ∈ 𝑆 𝛾 𝛾 𝐸 ∧ 𝑡 𝑟𝑒𝑐 ∈ 𝑆 𝛼 𝛼 𝑟𝑒𝑐 𝐸 }
Definition 1 (Well-formedness). A RLQDAG 𝛼 is well-formed if and only if ∀𝑡, 𝑡 ′ ∈ 𝑆 𝛼 𝛼 ∅ , eval(𝑡) = eval(𝑡 ′ ).
In this definition eval(𝑡) returns the interpretation of the individual recursive relational algebraic term 𝑡 (i.e. the set of tuples returned by 𝑡 when evaluated in a database instance).

For example, Fig. 5 illustrates a well-formed RLQDAG capturing two semantically equivalent relational terms obtained before and after the application of join distributivity over union. Fig. 6 illustrates a RLQDAG which is not well-formed, since its top-level equivalence node contains two subterms that are not semantically equivalent. The type of an operation node 𝑑 is the set of column names obtained in the result of the evaluation of any subbranch of 𝑑. In a well-formed RLQDAG, all 𝑑 𝑖 under the same equivalence node are semantically equivalent, and thus have the same type. For this reason, we also define the type of an equivalence node: type(𝛾) as the type of one of its operation nodes. Notice that the type of an annotated equivalence node of some fixpoint operation node 𝑑 corresponds to the type of the equivalence node of the constant part of 𝑑. For a given filter operation node 𝜎 𝑓 (𝛾), we denote by filt(f) ⊆ type(𝜎 𝑓 (𝛾)) the subset of column names used in the filtering function 𝑓 .

Recursive terms and rule applicability

A significant novelty introduced by recursion when compared to the classical setting of non-recursive algebraic terms resides in the criteria used to trigger rewrite rules. In the classical non-recursive setting these criteria are trivial in the sense that they only depend on top-level operators. In the example of Fig. 5, when applying join distributivity over union, the applicability of the rewrite rule 𝐴 ∪ (𝐵 ⊲⊳ 𝐶) -→ (𝐴 ⊲⊳ 𝐵) ∪ (𝐴 ⊲⊳ 𝐶) can be determined by examining only the combination of the two top-most operators, i.e. the top-level (∪) with the operator immediately underneath (i.e. ⊲⊳).

For some other rewrite rules, applicability criteria may also include some additional verifications such as (non)-interaction between e.g. the set of columns being filtered, or the columns being removed (in the cases of filter and antiprojection, respectively). In the non-recursive setting, these verifications can be done without the need to traverse the whole term. This means that usually no further traversal of subtrees of operators are required. For instance, in the previous example of join distributivity over union, 𝐵 and 𝐶 do not need to be traversed at all when determining rule applicability. In sharp contrast, rules for transforming recursive terms rely on criteria that are significantly more sophisticated as they sometimes require a whole traversal of the recursive part of a fixpoint term. This is because opportunities for rule application with recursive terms depend on how the recursive variable is used within the recursive parts of fixpoints. It is known since the works of [START_REF] Aho | Universality of Data Retrieval Languages[END_REF][START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF][START_REF] Kifer | On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering[END_REF] that criteria for rule application are significantly more sophisticated in the presence of recursion as they need to examine how the recursive variables are used. We show that it is still possible to apply rules over sets of recursive terms at once, using the concept of annotated equivalence nodes, that we define in § 3.5, and for which we need some preliminary definitions.

Preliminary definitions of auxiliary functions in RLQDAG

Definition 2 (Unfolding). Let 𝛼 be an equivalence node. The unfolding of 𝛼, denoted unfold(𝛼) is 𝛼 in which all occurrences of equivalence node variable names 𝑌 are replaced by their definitions (binders are simply unfolded).

We now define two auxiliary functions over RLQDAG terms. These functions will be used for defining annotated equivalence nodes in Section 3.5.

Notion of destabilizer in RLQDAG.

We define the destabilizer of an RLQDAG equivalence node as the set of columns that can be modified by an iteration of a parent fixpoint node. Specifically, destab() traverses subterms and analyzes how the occurrences of free variables are used in order to compute the set of columns that are subject to modifications during a fixpoint node iteration (e.g. renaming or antiprojection). Definition 3. For a fixpoint operation node 𝜇𝑋 . 𝛾 ∪ 𝛼 𝑟𝑒𝑐 we consider 𝛼 ′ = unfold(𝛼 𝑟𝑒𝑐 ) and we define destab(𝛼 ′ , 𝑋 ) as the following set of column names:

destab(𝛼 ′ , 𝑋 ) = {𝑐 ∈ ℭ | ∃𝑝 ∈ d(𝛼 ′ , 𝑋 ) 𝑝 (𝑐 ) ≠ 𝑐 } where d(•, •) computes the set of derivations over a RLQDAG term: d( (𝑑, 𝛼 ), 𝑋 ) = d(𝑑, 𝑋 ) d( 𝛼 1 ∪ 𝛼 2 , 𝑋 ) = d(𝛼 1 , 𝑋 ) ∪ d(𝛼 2 , 𝑋 ) d( 𝛼 1 ⊲ 𝛼 2 , 𝑋 ) = d(𝛼 1 , 𝑋 ) d( 𝛼 1 ⊲⊳ 𝛼 2 , 𝑋 ) = d(𝛼 1 , 𝑋 ) ∪ d(𝛼 2 , 𝑋 ) d(𝜌 𝑏 𝑎 ( 𝛼 ), 𝑋 ) = {𝑝 • (𝑏 → 𝑎, 𝑎 →⊥) | 𝑝 ∈ d(𝛼, 𝑋 ) } d( 𝜋 𝑎 ( 𝛼 ), 𝑋 ) = {𝑝 • (𝑎 →⊥) | 𝑝 ∈ d(𝛼, 𝑋 ) } d(𝜎 𝑓 ( 𝛼 ), 𝑋 ) = d(𝛼, 𝑋 ) d(𝜇 (𝑍 . 𝛾 ∪ 𝛼 ℜ 𝔇 ), 𝑋 ) = ∅ d(𝑋 , 𝑋 ) = { () } (a singleton identity) d(𝑅, 𝑋 ) = ∅
and where • represents the composition and (𝑎 1 → 𝑏 1 , ..., 𝑎 𝑛 → 𝑏 𝑛 ) denotes the function that maps each 𝑎 𝑖 to its 𝑏 𝑖 and every other column name to itself.

For instance, in the RLQDAG of Fig. 3, 𝔇 = {𝑠, 𝑚} in Σ and 𝔇 ′ = {𝑡, 𝑚} in Σ ′ . Intuitively, this is because these columns are renamed in front of the recursive variables.

Notion of rigidity in RLQDAG. We define a function rigid() that computes the set of columns that cannot be added nor removed from a fixpoint operation node, without breaking the semantics of the RLQDAG term.

A column 𝑐 ∈ ℭ cannot be added nor removed from an annotated equivalence node 𝛼 𝑟𝑒𝑐 (recursive in 𝑋 ) when 𝑐 ∈ rigid(unfold(𝛼), 𝑋 ) and rigid() is defined as follows: Definition 4 (Rigidity).

rigid( (𝑑, 𝛼 ), 𝑋 ) = rigid(𝑑, 𝑋 ) rigid( 𝛼 1 ∪ 𝛼 2 , 𝑋 ) = rigid(𝛼 1 , 𝑋 ) ∪ rigid(𝛼 2 , 𝑋 ) rigid( 𝛼 1 ⊲⊳ 𝛼 2 , 𝑋 ) = rigid(𝛼 1 , 𝑋 ) ∪ rigid(𝛼 2 , 𝑋 ) rigid( 𝛼 1 ⊲ 𝛼 2 , 𝑋 ) = rigid(𝛼 1 , 𝑋 ) ∪ rigid(𝛼 2 , 𝑋 ) rigid(𝜌 𝑏 𝑎 ( 𝛼 ), 𝑋 ) = rigid(𝛼, 𝑋 ) ∪ {𝑎, 𝑏 } rigid( 𝜋 𝑎 ( 𝛼 ), 𝑋 ) = ∅ when 𝑋 ∉ free(𝛼 ) = rigid(𝛼, 𝑋 ) ∪ {𝑎} otherwise rigid(𝜎 𝑓 ( 𝛼 ), 𝑋 ) = rigid(𝛼, 𝑋 ) ∪ filt( 𝑓 ) rigid(𝜇 (𝑍 .𝛾 ∪ 𝛼 ℜ 𝔇 ), 𝑋 ) = rigid(𝛼, 𝑋 ) ∪ rigid(𝛾, 𝑋 ) rigid(𝑅, 𝑋 ) = 𝑡 𝑦𝑝𝑒 (𝑅) when 𝑋 ≠ 𝑅 rigid(𝑋 , 𝑋 ) = ∅
For instance, in the RLQDAG of Fig. 3, ℜ = {𝑠, 𝑡 } in Σ. Intuitively, this is because these columns cannot be added nor removed without changing the semantics of the recursion.

Annotated equivalence node

An annotated equivalence node (𝛼 𝑟𝑒𝑐 in the abstract syntax of RLQDAG terms given in Fig. 2) is an equivalence node of a recursive part of a fixpoint, which is annotated with information that characterize how the recursive variable is used. Specifically: Definition 5. Given a RLQDAG operation node 𝑑 = 𝜇𝑋 . 𝛾 ∪ 𝛼 𝑟𝑒𝑐 , the annotated equivalence node 𝛼 𝑟𝑒𝑐 is defined as: 𝛼 ℜ 𝔇 where 𝔇 = destab(𝛼, 𝑋 ) and ℜ = rigid(𝛼, 𝑋 ).

For example, in the RLQDAG of Fig. 3, the two subterms Σ and Σ ′ (that correspond to the right-to-left and left-to-right path traversals) carry different annotations:

𝔇 = {𝑠, 𝑚} in Σ whereas 𝔇 ′ = {𝑡, 𝑚} in Σ ′ .
Annotations are intended to characterize all the subterms of the annotated equivalence node (thanks to definition 6). The goal of annotated equivalence nodes is to guide and maximize the grouped application of transformations, while also maximizing the sharing of common subterms. In the sequel, we detail RLQDAG transformations, by introducing new rewrite rules capable of transforming sets of subterms at once. Notion of consistency. Intuitively, a RLQDAG is consistent iff it is well-formed and in addition, for any of its annotated equivalence nodes 𝛼 2 ℜ 𝔇 , the annotations 𝔇 and ℜ are the same for all operation nodes directly underneath (no matter on which subbranch of the equivalence node they are computed, they coincide). More formally: Definition 6 (Consistency). A RLQDAG 𝛼 is consistent iff:

(1) it is well-formed;

(2) for all fixpoint operator node 𝜇𝑋 . 𝛾 ∪ 𝛼 2 ℜ 𝔇 occurring in 𝛼, we have cons(𝛼 2 , 𝑋 ) ℜ 𝔇 where:

cons( 𝑑 , 𝑋 ) ℜ 𝔇 = destab(𝑑, 𝑋 ) = 𝔇 ∧ rigid(𝑑, 𝑋 ) = ℜ cons( 𝑑, 𝛼 , 𝑋 ) ℜ 𝔇 = destab(𝑑, 𝑋 ) = 𝔇 ∧ rigid(𝑑, 𝑋 ) = ℜ ∧ cons( 𝛼 , 𝑋 ) ℜ 𝔇
An example of a consistent RLQDAG is shown in Fig. 3 provided 𝔇, ℜ, 𝔇 ′ and ℜ ′ are correctly computed. An example of an inconsistent RLQDAG would be a variant of Fig. 3 with a wrong annotation (e.g. 𝔇 ′ = 𝔇), later exposing the structure to incorrect transformations. This is because incorrect criteria satisfaction might then result in, for example, wrongly pushing a join operation node inside a fixpoint operation node. This would typically produce a not well-formed RLQDAG, breaking the semantics of the initial query. In the remaining, we only consider consistent RLQDAGs.

RLQDAG TRANSFORMATIONS

We now propose RLQDAG transformations whose purpose is to efficiently build the space of equivalent recursive plans.

RLQDAG transformations capture all the most advanced rewritings of recursive algebraic terms found in previous approaches (e.g. [START_REF]Alpha: an extension of relational algebra to express a class of recursive queries[END_REF][START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF]). Unlike previous approaches RLQDAG transformations make it possible to systematically group sets of recursive terms and exploit the sharing of common subterms to avoid redundant computations.

RLQDAG transformations leverage annotated equivalence nodes to guide the transformation of recursive subterms. They also update the RLQDAG structure with new annotations when needed, in an incremental manner. The incremental aspect for updating annotations is important as it avoids numerous subterm traversals, thus enabling more efficient grouped transformations.

For each recursive transformation, we describe which subterms can be shared, how newly generated terms are attached and what happens with the other plans already present in the equivalence node. The creation of new combinations of operation nodes may in turn generate more opportunities for transformations that are also explored.

RLQDAG rewrite rules

We formalize all these ideas by introducing RLQDAG rewrite rules, based on the syntax of RLQDAG terms introduced in Section 3. Specifically, RLQDAG rewrite rules are formalized as functions that take an equivalence node 𝛾 and return another equivalence node 𝛾 ′ obtained after applying transformations.

Pushing filters into fixpoint operation nodes. For pushing filters into sets of recursive terms, we introduce a function pf(), defined by considering all the syntactic decomposition cases of the input 𝛾. Fig. 7 focuses on the two main cases that correspond to potential opportunities of pushing filters, i.e. the cases pf( 𝑑 ) and pf( 𝑑, 𝛼 ) where 𝑑 filters an equivalence node which contains a recursive subterm. For all the other cases, pf() does not reorder operation nodes in the RLQDAG structure but simply traverses it in search for further transformation opportunities underneath 1 .

In Fig. 7, whenever the filter can be pushed through the fixpoint operation node, pf() generates a new RLQDAG in which the filter operation node is put within the constant part of the fixpoint operation node. In the resulting equivalence node, the initial (suboptimal) term is replaced by the new term where filtering is done earlier 1 For instance, two sample cases are the following:

pf(𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) = 𝜇𝑋 . expand(𝛾 ) ∪ expand(𝛼 ) ℜ 𝔇 pf( 𝐴 ⊲⊳ 𝐵 ) = expand( 𝐴 ) ⊲⊳ expand( 𝐵 )
where the expand( ) function, defined in Section 4.2, simply traverses subterms in search for more transformation opportunities. pf( ) is defined similarly for all the other syntactic cases of 𝛾 . Notice that when 𝛾 is a reference 𝑌 , there is no need to introduce a new binder, the reference name is used directly.

Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers (hence more efficient). For this transformation to happen, the criteria (on the last line of Fig. 7) must be satisfied. Whenever it is not the case, the RLQDAG structure is not reordered but simply recursively traversed in search for more transformation opportunites. The creation of new combinations of operation nodes may in turn provide new opportunities for other rewritings (for instance, new opportunities for pushing filters even further, or even other kinds of rewritings). This is the role of the expand() function, formally defined in section 4.2. Intuitively, a call to expand() on an equivalence node may further populate the equivalence node with new subterms. The expand() function is in charge of exploring all opportunities for transformations. This is useful because other rewrite rules may apply, and the expand() function basically triggers all possible applications of all rewrite rules.

pf( 𝜎 𝑓 ( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) ) =          • 𝜇𝑋 ′ . expand( 𝜎 𝑓 (𝛾 ) ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 𝑤ℎ𝑒𝑛 filt(f) ∩ 𝔇 = ∅ • 𝜎 𝑓 (expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) ) 𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 pf( 𝜎 𝑓 ( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) ) =                    • 𝜇𝑋 ′ . expand( 𝜎 𝑓 (𝛾 ) ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 , expand( 𝜎 𝑓 ( 𝛼 2 ) ) 𝑤ℎ𝑒𝑛 filt(f) ∩ 𝔇 = ∅ • 𝜎 𝑓 (expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) ) , expand( 𝜎 𝑓 ( 𝛼 2 ) ) 𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 where ℜ ′ = ℜ ∪ filt(f)
For example, the query Q 𝑒 2 :

?𝑠 ← ?𝑠 isLocatedIn+ Sweden retrieves all nodes that are connected to the constant node "Sweden" by a path composed of a sequence of edges labeled isLocatedIn from the Yago graph dataset [START_REF] Yago | YAGO: A high-quality knowledge base[END_REF]. Fig. 8 illustrates graphically a portion of Q 𝑒 2 RLQDAG, and Fig. 9 depicts its updated structure obtained after the pushing filter transformation defined in Fig. 7. New branches created by pf() are represented in blue color. The new term is added in the same equivalence node as the previous term, since they are semantically equivalent. Notice the incremental update of annotations performed by pf() in Fig. 7: the annotations of the newly created term (in blue) are obtained from the annotations of the initial term. In that case 𝔇 is simply propagated whereas

ℜ ′ = ℜ ∪ filt(f).
Pushing joins into fixpoint operation nodes. For pushing joins into sets of recursive terms we define a function pj(). pj() takes an equivalence node 𝛾 as input and returns an expanded equivalence node 𝛾 ′ that contains all the subterms in 𝛾 with, in addition, all the subterms where all joins pushable in fixpoint operation nodes have been pushed. We define pj() for all possible syntactic decompositions of a RLQDAG. Fig. 10 presents the definition of pj() for the two main cases of interest. Again, other cases are defined without structure rearrangement but involving recursive calls to expand() in search for further transformation opportunites underneath. Notice that whenever a join can be pushed within a fixpoint operation node (see Fig. 10), it is possible to share the constant part of the fixpoint operation node. This is made explicit by the creation of the outermost "let" binder whose goal is to define and associate a name to the equivalence node, so that it can be referred multiple times (thus explicitly showing the sharing of subterms).

For example, the query Q 𝑒 3 : ?𝑠, ?𝑡 ← ?𝑠 haschild+/livesin ?𝑡 retrieves all pairs of nodes that are connected by a path composed of a sequence of edges labeled haschild followed by a single edge labeled livesin. Fig. 11 illustrates graphically a portion of Q 𝑒 3 RLQDAG, after the application of the rule that pushes joins into fixpoint operation nodes described in Fig. 10. Fig. 11 shows that the newly created branch (in blue color) extends the set of semantically equivalent terms of the existing equivalence node.

Merging fixpoint operation nodes. The function mf() defined in Fig. 12 takes an input 𝛾 and returns an equivalence node 𝛾 ′ containing all the subterms in 𝛾 with, in addition, all the terms in which recursions that can be merged are merged. A merging happens whenever (i) two recursions are joined and (ii) their annotated equivalence nodes allow them to be merged into a single recursion, as described in Fig. 12. The constant part of the new recursive term created is the join of the constant parts of the two initial fixpoints, and a new recursive part is created. Since the constant part has changed, a new recursive variable is introduced and recursive parts are also new (and cannot be shared2 ).

For example, the query Q 𝑒 4 : ?𝑠, ?𝑡 ← ?𝑠 islocatedin+/dealswith+ ?𝑡 retrieves all pairs of nodes that are connected by a path composed of two successive sequences of edges labeled islocatedin and dealswith respectively. Fig. 13 illustrates a portion of Q 𝑒 4 RLQDAG, with the new recursive term produced, using subterm-sharing, after the merging of fixpoint operation nodes.

pj( 𝛽 ⊲⊳ 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) =                    • let const = 𝛾 in expand(𝛽 ) ⊲⊳ expand( 𝜇𝑋 . const ∪ 𝛼 ℜ 𝔇 ) , 𝜇𝑋 ′ . expand( 𝛽 ⊲⊳ const ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 ′ 𝑤ℎ𝑒𝑛 type (𝛽 ) ∩ 𝔇 = ∅ 𝑎𝑛𝑑 type (𝛽 )\type (𝛾 ) ∩ ℜ = ∅ • expand(𝛽 ) ⊲⊳ expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) 𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 pj( 𝛽 ⊲⊳ 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) =                              • let const = 𝛾 in expand(𝛽 ) ⊲⊳ expand( 𝜇𝑋 . const ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) , 𝜇𝑋 ′ . expand( 𝛽 ⊲⊳ const ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 ′ , expand(𝛽 ) ⊲⊳ expand( 𝛼 2 ) 𝑤ℎ𝑒𝑛 type (𝛽 ) ∩ 𝔇 = ∅ 𝑎𝑛𝑑 type (𝛽 )\type (𝛾 ) ∩ ℜ = ∅ • expand(𝛽 ) ⊲⊳ expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) , expand(𝛽 ) ⊲⊳ expand( 𝛼 2 )
𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 where we define 𝔇 ′ = 𝔇 ∪ destab(𝛽, 𝑋 ) and ℜ ′ = ℜ ∪ rigid(𝛽, 𝑋 ). This is because we need to recompute the destabilizer on the underlying set of derivations updated with d(𝛽, 𝑋 ) and we have destab(𝐴 ∪ 𝐵) = destab(𝐴) ∪ destab(𝐵 ).

α 2 μ ⋈ ⋈ (X)
Figure 11: Expansion of a RLQDAG by pushing a join in a fixpoint operation node. The initial RLQDAG is in green color, and parts added by pj() are in blue color.

mf( 𝜇𝑋 1 . 𝛾 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 ⊲⊳ 𝜇𝑋 2 . 𝛾 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟 ) =                        • let const 1 = 𝛾 1 in let const 2 = 𝛾 2 in expand( 𝜇𝑋 1 . const ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 ) ⊲⊳ expand( 𝜇𝑋 2 . const ∪ 𝛼 ℜ 𝟟 𝟟 ) , 𝜇𝑋 . const 1 ⊲⊳ const 2 ) ∪ expand( 𝛼 1 {𝑋 1 /𝑋 } ∪ 𝛼 2 {𝑋 2 /𝑋 } ℜ 𝔇 ) 𝑤ℎ𝑒𝑛 (type (𝛾 1 ) ∩ type (𝛾 2 ) ) ∩ (𝔇 𝟞 ∪ 𝔇 𝟟 ) = ∅ 𝑎𝑛𝑑 type (𝛾 1 )\type (𝛾 2 ) ∩ ℜ 𝟟 = ∅ 𝑎𝑛𝑑 type (𝛾 2 )\type (𝛾 1 ) ∩ ℜ 𝟞 = ∅ • expand( 𝜇𝑋 1 . const 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 ) ⊲⊳ expand( 𝜇𝑋 2 . const 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟 ) 𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 mf( 𝜇𝑋 1 . 𝛾 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 , 𝛼 3 ⊲⊳ 𝜇𝑋 2 . 𝛾 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟 , 𝛼 4 ) =                                                • let const 1 = 𝛾 1 in let const 2 = 𝛾 2 in expand( 𝜇𝑋 1 . const 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 ) ⊲⊳ expand( 𝜇𝑋 2 . const 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟 ) , 𝜇𝑋 . expand( const 1 ⊲⊳ const 2 ) ∪ expand( 𝛼 1 {𝑋 1 /𝑋 } ∪ 𝛼 2 {𝑋 2 /𝑋 } ℜ 𝔇 ) , expand( 𝛼 3 ) ⊲⊳ expand( 𝜇𝑋 2 . 𝛾 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟 , 𝛼 4 ) , expand( 𝛼 4 ) ⊲⊳ expand( 𝜇𝑋 1 . 𝛾 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 , 𝛼 3 ) 𝑤ℎ𝑒𝑛 (type (𝛾 1 ) ∩ type (𝛾 2 ) ) ∩ (𝔇 𝟞 ∪ 𝔇 𝟟 ) = ∅ 𝑎𝑛𝑑 type (𝛾 1 )\type (𝛾 2 ) ∩ ℜ 𝟟 = ∅ 𝑎𝑛𝑑 type (𝛾 2 )\type (𝛾 1 ) ∩ ℜ 𝟞 = ∅ • expand( 𝜇𝑋 1 . 𝛾 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 , 𝛼 3 ) ⊲⊳ expand( 𝜇𝑋 2 . 𝛾 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟 , 𝛼 4 ) , expand( 𝛼 3 ) ⊲⊳ expand( 𝜇𝑋 2 . 𝛾 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟 , 𝛼 4 ) , expand( 𝛼 4 ) ⊲⊳ expand( 𝜇𝑋 1 . 𝛾 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 , 𝛼 3 )
𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 where 𝔇 = 𝔇 𝟞 ∪ 𝔇 𝟟 and ℜ = ℜ 𝟞 ∪ ℜ 𝟟 and 𝛼 𝑖 {𝑋 𝑖 /𝑋 } denotes 𝛼 𝑖 in which all occurrences of 𝑋 𝑖 are replaced by 𝑋 . This is because the only transformation of the recursive part that needs to be propagated to update the annotations is the union of the two former recursive parts and both destab and rigid are distributive over union. Pushing an antiprojection in a fixpoint operation node. For pushing antiprojections into fixpoint operation nodes we introduce a function pp() that takes an equivalence node 𝛾 as input and returns an expanded equivalence node 𝛾 ′ where all pushable antiprojections have been pushed. pp() is defined in Fig. 14. The antiprojection is pushed when the criteria allows it, and this results in the creation of a new term which replaces the initial one in the existing equivalence node. Whenever the criteria is not satisfied, the initial term is left unchanged, but traversed in search for more transformation opportunities.

Pushing an antijoin in a fixpoint operation node. For pushing antijoins into fixpoints we introduce a function pa() that takes an equivalence node 𝛾 as input and returns an expanded node 𝛾 ′ that contains all the subterms in 𝛾 with, in addition, all subterms where all pushable antijoins have been pushed in fixpoint operation nodes. pa() is defined in Fig. 15. Again, Fig. 15 focuses on the syntactic cases that correspond to when an antijoin might be pushed in a fixpoint. When criteria are satisfied, the antijoin is pushed in the constant part of the fixpoint operation node and the newly created term is added to the set of equivalent terms along with the rest.

⋈ (X) (isLocIn) (isLocIn) µ ⋈ (X) (dealsWith) µ (dealsWith) ⋈ ⋈ (X) μ ⋈ U ⋈ (X) α 4 α3
Figure 13: RLQDAG structure after merging fixpoint operation nodes.

pp( 𝜋 𝑎 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) =          • 𝜇𝑋 ′ . expand( 𝜋 𝑎 (𝛾 ) ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 ′ 𝑤ℎ𝑒𝑛 𝑎 ∉ ℜ • 𝜋 𝑎 (expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) ) 𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 pp( 𝜋 𝑎 ( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) ) =              • 𝜇𝑋 ′ . expand( 𝜋 𝑎 (𝛾 ) ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 ′ , expand( 𝜋 𝑎 ( 𝛼 2 ) ) 𝑤ℎ𝑒𝑛 𝑎 ∉ ℜ • 𝜋 𝑎 (expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) ) , expand( 𝜋 𝑎 ( 𝛼 2 ) )
𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 where 𝔇 ′ = 𝔇 ∪ {𝑎} and ℜ ′ = ℜ ∪ {𝑎}. RLQDAG rules can be divided into two groups. The first group is composed of rewrite rules pj(), pa() and mf(). The application of these rules always preserve preexisting terms in an equivalence node. These rules can only perform additions of new operation nodes in an equivalence node 3 . The second group is composed of the rules pf() and pp() that perform logical optimizations. The application of these rules can replace terms in an equivalence node by more optimal variants (i.e. they discard logically suboptimal variants).

The overall expansion algorithm

We can now describe the overall RLQDAG expansion algorithm. We define the function expand() that takes an equivalence node 𝛾 and returns the equivalence node 𝛾 ′ which contains all the terms obtained by transformations. The expand function is simply defined as follows:

expand( 𝑑 ) = applyAll( 𝑑 ) expand( 𝑑, 𝛼 ) = applyAll( 𝑑 ) ∪ expand(𝛼 )
where applyAll() is in charge of applying all possible transformations on each operation node. This includes applying all rewrite rules defined in Section 4 in combination with the more classical 3 One operation node will then be selected using cost estimation heuristics depending on statistics on the cardinalities of the database instance.

pa( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ⊲ 𝛽 ) =                  • let const = 𝛾 in expand( 𝜇𝑋 . const ∪ 𝛼 ℜ 𝔇 ) ⊲ expand(𝛽 ) , 𝜇𝑋 ′ . expand( const ⊲ 𝛽 ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 𝑤ℎ𝑒𝑛 type (𝛽 ) ∩ 𝔇 = ∅ • expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ) ⊲ expand(𝛽 ) 𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒 pa( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ⊲ 𝛽 ) =                            • let const = 𝛾 in expand( 𝜇𝑋 . const ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) ⊲ expand(𝛽 ) , 𝜇𝑋 ′ . expand( const ⊲ 𝛽 ) ∪ expand(𝛼 {𝑋 /𝑋 ′ } ) ℜ ′ 𝔇 , expand( 𝛼 2 ) ⊲ expand(𝛽 ) 𝑤ℎ𝑒𝑛 type (𝛽 ) ∩ 𝔇 = ∅ • expand( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 , 𝛼 2 ) ⊲ expand(𝛽 ), expand( 𝛼 2 ) ⊲ expand(𝛽 )
𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒

where ℜ ′ = ℜ ∪ rigid(𝛽, 𝑋 ).

Figure 15: Pushing antijoin in an equivalence node containing a fixpoint. ones of relational algebra 4 :

pfj( 𝜎 𝑓 ( 𝛾 1 ⊲⊳ 𝛾 2 , 𝛼 ) ) =                              • exp( 𝜎 𝑓 (𝛾 1 ) ) ⊲⊳ exp(𝛾 2 ), exp( 𝜎 𝑓 (𝛼 ) ) 𝑤ℎ𝑒𝑛 filt(f) ⊆ type (𝛾 1 ) ∧ filt(f) ⊈ type (𝛾 2 ) • exp(𝛾 1 ) ⊲⊳ exp( 𝜎 𝑓 (𝛾 2 ) ), exp( 𝜎 𝑓 (𝛼 ) ) 𝑤ℎ𝑒𝑛 filt(f) ⊈ type (𝛾 1 ) ∧ filt(f) ⊆ type (𝛾 2 ) • exp( 𝜎 𝑓 (𝛾 1 ) ) ⊲⊳ exp( 𝜎 𝑓 (𝛾 2 ) ), exp( 𝜎 𝑓 (𝛼 ) ) 𝑤ℎ𝑒𝑛 filt(f) ⊆ type (𝛾 1 ) ∧ filt(f) ⊆ type (𝛾 2 ) • 𝜎 𝑓 (exp( 𝜑 ⊲⊳ 𝜓 ), exp( 𝜎 𝑓 (𝛼 ) ) ) 𝑜𝑡ℎ𝑒𝑟 𝑤𝑖𝑠𝑒
applyAll( 𝑑 ) = pf( 𝑑 ) ∪ pa( 𝑑 ) ∪ pj( 𝑑 ) ∪ mf( 𝑑 ) ∪ pp( 𝑑 ) ∪ allCodd( 𝑑 )
where allCodd() applies all rewrite rules concerning classical (non-recursive) relational algebra adapted for RLQDAG. For example: pfj() for pushing filters in join operation nodes, paj() for pushing antiprojections in a join operation node, jassoc() (for join associativity), dju() (for distributivity of join over union operation nodes) etc.

allCodd( 𝑑 ) = pfj( 𝑑 ) ∪ paj( 𝑑 )∪ jassoc( 𝑑 ) ∪ ... ∪ dju( 𝑑 )
For instance, pfj() is defined as shown in Fig. 16 for an RLQDAG in which a filter precedes an equivalence node which contains a join operation node. In other cases, pfj() recursively traverses the structure with appropriate calls to expand() in search for further transformation opportunities. Other rewrite rules of non-recursive relational algebra are also implemented in a similar way in the RLQDAG.

Correctness and completeness

Proposition 1 (Correctness). Let 𝛼 be a consistent RLQDAG, and 𝛼 ′ = expand( 𝛼 ), then we have 𝑆 𝛾 𝛼 ∅ ⊆ 𝑆 𝛾 𝛼 ′ ∅ and 𝛼 ′ is consistent.

Proof Sketch. The proof of correctness is done by induction on the structure of 𝛼 ′ , using a case-by-case analysis of syntactic decompositions (i.e. by considering separately each RLQDAG subcase and the corresponding case of the generalized rewrite rule that applies to it). The complete formal proof is too large to be listed here (with many straightforward subcases). We summarize the main principles as well as useful auxiliary properties. When proving correctness for each RLQDAG rewrite rule, (i) we focus on each newly created recursive term added by the expansion, and (ii) use the consistency hypothesis on the recursive term before transformation to apply the theorems for individual terms of [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] to each rearrangement of fixpoint operation node. We also need to show that the incremental updates of annotations performed by the RLQDAG rewrite rules preserve consistency. This is done for each update by leveraging the properties that both destab () and rigid() are distributive over union. □ Proposition 2 (Completeness properties). Let be a set of RLQDAG rewrite rules such that 𝑅 contains the 5 RLQDAG rewrite rules for recursive terms presented in Section 4, we consider 𝛼 = unfold(expand 𝑅 ( 𝛼 ′ )) where 𝛼 ′ is a consistent RLQDAG, and expand 𝑅 () is the expand() function in which rules in 𝑅 are activated. The following properties hold:

Property 1 (All pushable filters have been pushed). Property 4 (All mergeable fixpoints merged).

∀ (𝛾 1 ⊲⊳ 𝛾 2 ) ∈ 𝛼 , if 𝜇𝑋 1 . 𝜅 1 ∪ 𝛼 1 ℜ 𝟞 𝔇 𝟞 ∈ 𝛾 1 and 𝜇𝑋 2 . 𝜅 2 ∪ 𝛼 2 ℜ 𝟟 𝔇 𝟟
∈ 𝛾 2 and we have 𝛾 1 ≠ 𝛾 2 and (type(𝛾 1 ) ∩ type(𝛾 2 ) ) ∩ (𝔇 𝟞 ∪ 𝔇 𝟟 ) = ∅ and type(𝛾 1 )\type(𝛾 2 ) ∩ ℜ 𝟟 = ∅ and type(𝛾 2 )\type(𝛾 1 ) ∩ ℜ 𝟞 = ∅ then there exists 𝑑 ∈ 𝛼 such that 𝑑 =

𝜇𝑋 . 𝜅 1 ⊲⊳ 𝜅 2 ∪ 𝛼 1 ∪ 𝛼 2 ℜ 𝔇 .
Property 5 (All pushable antijoins pushed).

∀ ( 𝜇𝑋 . 𝛾 ∪ 𝛼 ℜ 𝔇 ⊲ 𝛽 ) ∈ 𝛼 , if type(𝛽 ) ∩ 𝔇 = ∅ then ∃𝑑 ∈ 𝛼 such that 𝑑 = 𝜇𝑋 ′ . 𝛾 ⊲ 𝛽 ∪ 𝛼 {𝑋 /𝑋 ′ } ℜ ′ 𝔇
Proof Sketch. These properties are proved by contradiction: (i) assuming the existence of a missed transformation opportunity in the expansion, which (ii) necessarily implies some unrealized rule application (whereas the rule was applicable), and (iii) showing that the systematic structure traversal performed by expand 𝑅 () leaves no room for such a missed opportunity, thus (iv) leading to a contradiction. □

EXPERIMENTAL RESULTS

We evaluate the RLQDAG experimentally. Our assessment is driven by the following research questions:

RQ1 How efficient is RLQDAG exploration of recursive plan spaces compared to the state-of-the-art? RQ2 How relevant are explorations of large recursive plan spaces for practical query evaluation?

In the following subsections we first introduce the experimental setup and the experimental methodology with chosen baselines and metrics. We then report on the results and the main lessons learned.

Experimental setup

Datasets. We consider various datasets, graphs and trees, real and generated, as described in Table 1.

Dataset #nodes & #edges

Type Nature

Yago [START_REF] Yago | YAGO: A high-quality knowledge base[END_REF] 42M & 62M Knowledge graph Real Bahamas Leaks [START_REF]Bahamas Leaks[END_REF] 202K & 249K Property graph Real Airbnb [START_REF]Airbnb[END_REF] 24K & 14K Property graph Real LDBC [START_REF] Boncz | LDBC: Benchmarks for Graph and RDF Data Management[END_REF] 908K & 1.9M Property graph Synthetic Wikitree [START_REF] Fire | Data mining of online genealogy datasets for revealing lifespan patterns in human population[END_REF] 9.1M & 1.3M Tree Real Academic tree [START_REF] Jean F Liénard | Intellectual synthesis in mentorship determines success in academic careers[END_REF] 765K & 1.5M Tree Real

Table 1: Datasets (available from [START_REF]Datasets and Queries used in experiments with the RLQDAG[END_REF]).

Queries. We consider a variety of recursive queries formulated against these datasets. Queries for Yago are mainly third-party regular path queries already considered in earlier papers in the literature 5 , and chosen because they are representative of the variety of possible recursive optimizations that can apply to them. Queries over the Airbnb dataset are inspired from [START_REF] Sharma | Practical and comprehensive formalisms for modelling contemporary graph query languages[END_REF]. We added more queries formulated over the Bahamas and LDBC datasets. We consider non-regular queries (variants of same generation, and a 𝑛 b 𝑛 ) for the Wikitree and Academic Tree datasets. Queries and datasets used in experiments are available at [START_REF]Datasets and Queries used in experiments with the RLQDAG[END_REF].

Hardware. All experiments are conducted on a machine with an Intel Xeon 2.20GHz CPU and 192Gb of RAM.

RQ1: Efficiency of plan space exploration.

To answer RQ1, we implemented a prototype of the RLQDAG and compare it with MuEnum, which is the plan enumerator of the state-of-the-art 𝜇-RA system [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF]. As described in Section 2, this system is of the most advanced relational-based system for recursive query optimization; providing the richest plan spaces for recursive terms. MuEnum [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] explores them using a state-of-the-art dynamic programming strategy, in which terms are made unique in memory so as to obtain very efficient term equality tests.

We measure the enumeration capability of the RLQDAG in terms of the number of plans explored per second for each query. We compare the performance of our RLQDAG prototype implementation with the performance of MuEnum. Figures 17,[START_REF] Fender | Top down plan generation: From theory to practice[END_REF][START_REF] Fire | Data mining of online genealogy datasets for revealing lifespan patterns in human population[END_REF]and Fig. 20 respectively show the results obtained for the queries over each dataset.

Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q 9 Q 1 0 Q 1 1 Q 1 2 Q 1 3 Q 1 4 Q 1 5 Q 1 6 Q 1 7 Q 1 8 Q 1 9 Q 2 0 Queries

Plans per second (log scale)

RLQDAG MuEnum [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] Figure 17: Yago queries.

Q 2 1 Q 2 2 Q 2 3 Q 2 4 Q 2 5 Q 2 6 Q 2 7 Q 2 8 Q 2 9 Q 3 0 Q 3 1 Q 3 2 Q 3 3 Queries

Plans per second (log scale)

RLQDAG MuEnum [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] Figure 18: Bahamas Leaks queries. In these figures, the 𝑦 axis (in log scale) indicates the number of plans per second explored by each approach for a given query (on the 𝑥 axis). Results suggest that the RLQDAG approach always enumerates plans much faster (up to two orders of magnitude) when compared to MuEnum6 . Now, we set a time budget 𝑡 (in seconds) for the plan space exploration and let the two systems generate plan spaces for that time budget. This means that after 𝑡 elapsed seconds we stop the two explorations and look at the plan spaces obtained by the two systems. Fig. 21 shows the results obtained for a time budget of 𝑡 = 0.5 seconds with queries from Bahamas Leaks (Q31-Q32), Airbnb (Q34-Q37-Q38-Q39) and LDBC (Q51-Q53-Q54). The 𝑦 axis (in log scale) indicates the number of plans found.

Q 3 4 Q 3 5 Q 3 6 Q 3 7 Q 3 8 Q 3 9 Q 4 0 Q 4 1 Q 4 2 Q 4 3 Q 4 4 Q 4 5 Q 4 6 Q 4 7 Q 4 8 Q 4 9 Q 5 0 Q 5 1 Q 5 2 Q 5 3 Q 5

Plans per second (log scale)

RLQDAG MuEnum [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] Figure 20: Non-regular queries.

any time restriction for the plan exploration (𝑡 = ∞). For example, for query Q31, the complete plan space contains more than 21.4 million plans. In 0.5 seconds, the RLQDAG prototype explored 1,019,026 plans whereas MuEnum explored only 5,751 plans. This is because although MuEnum uses dynamic programming techniques, it is not capable of benefitting from the RLQDAG's grouping effect when applying complex rewrite rules on sets of recursive terms at once, thus rules are significantly more costly to apply. Seen from another perspective, this means that the RLQDAG's approach is more effective in avoiding redundant subcomputations. We have conducted extensive experiments and overall results indicate that, for a given time budget, the RLQDAG prototype explores many more terms in comparison to MuEnum, in all cases. In some cases, the RLQDAG generates a number of plans which is greater by up to two orders of magnitude (for the same time budget). Such a speedup sometimes enables a complete exploration of the whole plan space in some cases (as shown e.g. for Q34, Q51, Q53, Q54 in Fig. 21).

Q31 Q32 Q34 Q37 Q38 Q39 Q51 Q53 Q54 We now report on experiments of exploring plan spaces with varying and increasing time budgets for the same query. For instance, Fig. 22 presents the number of plans explored (on the 𝑦 axis) for different time budgets shown on the 𝑥 axis for query Q31 and query Q53 (2 queries from 2 different datasets).

Number of plans (log scale)

RLQDAG MuEnum [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] Figure 22: Plans explored per time budgets for Q31 and Q53.

Again, results shown in Fig. 22 indicate that the RLQDAG explores significantly more plans than the other approach for all considered time budgets (the 𝑦 axis is in log scale). We can also observe that the difference between the amount of plans explored by each system stays of the same order, even when exploration time increases.

RQ2: Relevance of exploring large plan

spaces.

To answer RQ2, we use the same backend (PostgreSQL) in order to execute query plans generated by MuEnum and RLQDAG. For a given query, we set a time budget for plan space exploration, and we let MuEnum and RLQDAG generate plan spaces for this same time budget. Now, we pick the best estimated plan from each generated plan space. We use the same heuristics for cost estimations [START_REF] Lawal | A Cost Estimation Technique for Recursive Relational Algebra[END_REF], thus making relevant a head to head comparison. We measure and compare the times spent by PostgreSQL for evaluating the plans.

Q31 Q32 Q34 Q37 Q38 Q39 Q51 Q53 Q54 Queries For example, Fig. 23 illustrates the time spent in evaluating the best estimated plan taken from each of the explored plan spaces reported in Fig. 21. Results show the benefits of exploring a much larger plan space: the RLQDAG approach always provides similar or better performance, which is a direct consequence of the availability of more efficient recursive plans in the larger plan space explored.

Furthermore, for the same query, we also measure the time spent in evaluating the best estimated plans from the different plan spaces explored with a varying time budget. For instance, Fig. 24 shows the time spent in evaluating the best plans selected from each plan space explored with the time budget shown on the 𝑥 axis. The sizes of the corresponding plan spaces are given in Fig. 22. Results shown in Fig. 24 show that the best estimated term selected from the larger plan space is more efficiently evaluated. This suggests that in practice, larger plan spaces are very prone to contain more efficient recursive plans. This confirms the interest of efficiently exploring large recursive plan spaces. Finally, we assess to which extent the availability of more relational algebraic plans can be useful in practice, when compared to other RDBMS and state-of-the-art approaches in graph query evaluation. For this purpose, we consider 2 engines based on relational algebra (MuEnum [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] and Virtuoso [START_REF] Erling | Virtuoso, a Hybrid RDBMS/Graph Column Store[END_REF] version 7.2.6.1), 3 native graph database engines (MilleniumDB [START_REF] Vrgoč | MillenniumDB: An Open-Source Graph Database System[END_REF], Neo4j [START_REF] Webber | A Programmatic Introduction to Neo4j[END_REF] version 4.4.11,Blazegraph [53] version 2.1.6), and 3 plain-vanilla RDBMS capable of evaluating recursive SQL queries (PostgreSQL [START_REF] Stonebraker | The Design of POSTGRES[END_REF] version 15.1, MySQL [START_REF]MySQL[END_REF] version 8.1.0, SQLite [START_REF] Richard | SQLite[END_REF] version 3.36.0). We measure the time spent in query evaluation with each system. For each system, this includes the time spent in query optimization and the time spent in retrieving the whole set of query results. We set a timeout of 600s (10 min). Fig. 25 shows the corresponding times spent for systems which were able to answer. If a system does not answer before the timeout, we consider that it is unable to answer, and it is absent from Fig. 25 for the given query. RLQDAG MuEnum [START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF] MilleniumDB [START_REF] Vrgoč | MillenniumDB: An Open-Source Graph Database System[END_REF] PostgreSQL [START_REF] Stonebraker | The Design of POSTGRES[END_REF] Blazegraph [START_REF] Thompson | The Bigdata® RDF graph database[END_REF] MySQL [START_REF]MySQL[END_REF] SQLite [START_REF] Richard | SQLite[END_REF] Virtuoso [START_REF] Erling | Virtuoso, a Hybrid RDBMS/Graph Column Store[END_REF] Neo4j [START_REF] Webber | A Programmatic Introduction to Neo4j[END_REF] Figure 25: Comparative evaluation of third-party queries (excerpt from [START_REF]Datasets and Queries used in experiments with the RLQDAG[END_REF]).

Results suggest that the availability of more plans -thanks to the RLQDAG -is beneficial to the relational-based approach. More specifically, existing RDBMS consider recursive queries in a very restricted way. Most of them optimize recursion-free subexpressions, without being able to optimize the recursive part as a whole: they cannot make significant structural changes to the entire recursive query. This has an important consequence: they do explore much smaller plan spaces when compared to RLQDAG, potentially missing very efficient plans. In some cases, it even makes the relational-based approach more efficient than specialized graph engines.

CONCLUSION AND PERSPECTIVES

We propose the RLQDAG for capturing and efficiently transforming sets of recursive relational terms. This is done by introducing annotated equivalence nodes, and a formal syntax and semantics for RLQDAG terms that enable the development of RLQDAG rewrite rules on a solid ground. RLQDAG rewrite rules transform sets of recursive terms while precisely describing how new subterms are created, attached, shared, and how new structural annotations are obtained with incremental updates. The proposed formalisation of the RLQDAG in terms of syntax and semantics provided a convenient -if not instrumental -means to develop transformations. It helps in defining expansions, and for detecting and fixing intricate transformational issues. We believe that this formalization can also serve in further extensions, thus contributing to the extensibility of the top-down transformational approach. Practical experiments with the RLQDAG show the interest of exploring large plan spaces, and suggest that it represents an interesting foundation for efficiently enumerating recursive relational query plans.

Figure 1 :

 1 Figure 1: Sample LQDAG (in green) with expansion (in blue).

Figure 3 :

 3 Figure 3: Structure of recursive terms in RLQDAG.

Figure 4 :

 4 Figure 4: Formal semantics of RLQDAG terms, with one interpretation function for each syntactic construct of Fig. 2.

Figure 6 :

 6 Figure 5: Well-formed RLQDAG.

  and 𝛼 {𝑋 /𝑋 ′ } denotes 𝛼 in which all occurrences of 𝑋 are replaced by 𝑋 ′ .

Figure 7 :

 7 Figure 7: Pushing a filter in an equivalence node containing a fixpoint.

2 Figure 8 :

 28 Figure 8: Initial RLQDAG before expansion with opportunity to apply pf().

Figure 9 :

 9 Figure 9: Expansion of a RLQDAG by pushing a filter in a fixpoint operation node, with branches added by pf() in blue color.

Figure 10 :

 10 Figure 10: Pushing join in an equivalence node containing a fixpoint.

Figure 12 :

 12 Figure 12: Merging fixpoint operation nodes.

Figure 14 :

 14 Figure 14: Pushing antiprojection in an equivalence node containing a fixpoint.

Figure 16 :

 16 Figure 16: Pushing a filter in an equivalence node composed of at least one join operation node and other operation nodes (exp() stands for expand()).

∀ 2 ℜProperty 2 ( 2 ℜProperty 3 ( 2 ℜ

 22232 𝜎 𝑓 (𝛾 ) ∈ 𝛼 , 𝑑 ∈ 𝛾 | 𝑑 = 𝜇𝑋 . 𝜅 ∪ 𝛼 𝔇 and filt(f) ∩ 𝔇 = ∅. All pushable antiprojections pushed). ∀ 𝜋 𝑎 (𝛾 ) ∈ 𝛼 , 𝑑 ∈ 𝛾 | 𝑑 = 𝜇𝑋 . 𝜅 ∪ 𝛼 𝔇 and 𝑎 ∉ ℜ. All pushable joins pushed). ∀ (𝛽 ⊲⊳ 𝛾 ) ∈ 𝛼 , if ∃𝑑 ∈ 𝛾 such that 𝑑 = 𝜇𝑋 . 𝜅 ∪ 𝛼 𝔇 and type(𝛽 ) ∩ 𝔇 = ∅ and type(𝛽 )\type(𝛾 ) ∩ ℜ = ∅ then ∃𝑑 ′ ∈ 𝛼 such that 𝑑 ′ = 𝜇𝑋 ′ . 𝛽 ⊲⊳ 𝜅 ∪ 𝛼 2 {𝑋 /𝑋 ′ } ℜ ′ 𝔇 ′ .

Figure 19 :

 19 Figure 19: Airbnb and LDBC queries.

  Fig. 21 also indicates the size of the complete (exhaustive) plan space obtained without Q55 Q56 Q57 Q58 Q59 Q60 Q61 Q62 Q63 Queries

Figure 21 :

 21 Figure 21: Plan spaces explored in 500ms.

Figure 23 :

 23 Figure 23: Evaluating best estimated plans found in explored spaces of Fig 21.

Figure 24 :

 24 Figure 24: Evaluating best estimated plans found in explored spaces of Fig 22.

  𝛼 1 . Hence, the general definition of 𝛾 is either an equivalence node 𝛼 or a reference 𝑌 to an existing equivalence node. Operation nodes are defined by the variable 𝑑 in the abstract syntax of Fig.2. They include the main algebraic operations of recursive relational algebra. Each operand of an operation node 𝑑 points in turn to an equivalence node (through 𝛾). The rename operator 𝜌 b a (𝛾) renames column 𝑎 into column 𝑏 in the equivalence node 𝛾. The filter operator 𝜎 𝑓 (𝛾) applies the filtering expression 𝑓 to the equivalence node 𝛾. The antiprojection operator 𝜋 𝑎 (𝛾) removes column 𝑎 from the equivalence node 𝛾.For example, with this syntax, the LQDAG of Fig.1is written as the term [[𝐴 ⊲⊳ 𝐵] ⊲⊳ 𝐶] before expansion and is written [[𝐴 ⊲⊳ 𝐵] ⊲⊳ 𝐶, 𝐴 ⊲⊳ [𝐵 ⊲⊳ 𝐶], 𝐵 ⊲⊳ [𝐴 ⊲⊳ 𝐶]] after expansion, where for the sake of readability we omit brackets around relation variables.

	𝛾 ::=			Pointer to equivalence node
		𝛼		Equivalence node
	|	Y		Reference
	𝛼 ::=			Equivalence node internals
		𝑑		Operation node
	|	𝑑, 𝛼		Operation nodes
	|	let Y = 𝛼 1 in 𝛼 2	Reference binder
	𝑑 ::=			Operation node
		𝑋		Relation variable
	|	𝜌 𝑏 𝑎 (𝛾 )	Rename
	| | | |	𝜎 𝑓 (𝛾 ) 𝛾 ⊲⊳ 𝛾 ′ 𝛾 ⊲ 𝛾 ′ 𝛾 ∪ 𝛾 ′	Filter Join Antijoin Union
	|	𝜋 𝑎 (𝛾 )	Antiprojection
	|	𝜇𝑋 . 𝛾 ∪ 𝛼 𝑟𝑒𝑐	Fixpoint (recursion)
	𝛼 𝑟𝑒𝑐 ::=	𝛼	ℜ 𝔇	Annotated equivalence node
		Figure 2: Syntax of RLQDAG terms.

This does not prevent the sharing of potential subparts with no occurrence of a free variable.

As a slight discrepancy between the theory and the implementation, the implementation of the RLQDAG expansion avoids some redundant calls to the expand( ) function by implementing the applyAll( ) function in an imperative-style double nested for loop, so as to implement a single case analysis and to trigger expand( ) once only when needed.

We consider 7 queries (Q1-Q7) taken from[START_REF] Abul-Basher | Tasweet: optimizing disjunctive regular path queries in graph databases[END_REF], 2 queries (Q8-Q9) taken from[START_REF] Yakovets | WAVEGUIDE: Evaluating SPARQL Property Path Queries[END_REF], (Q10-Q11) taken from[START_REF] Gubichev | Sparqling kleene: fast property paths in RDF-3X[END_REF] and (Q12-Q20) come from[START_REF] Jachiet | On the Optimization of Recursive Relational Queries: Application to Graph Queries[END_REF].

Cases where histogram bars look very similar correspond to situations where both systems completed the plan space exploration in a very short time duration, which makes the difference hardly visible with the log scale.


Clemence Chupin

Valérie Ballu

Laurent Testut

Yann-Treden Tranchant

Geodetic instrumentation to validate altimetry sea-level measurements in the Noumea Lagoon -New results from the GEOCEAN-NC 2019 campaign

Geodetic instrumentation to validate altimetry sea level measurements in the Noumea Lagoon -New results from the GEOCEAN-NC 2019 campaign -EGU23 14669

Clémence Chupin 1 , Valérie Ballu 2 , Laurent Testut 2 , and Yann-Treden Tranchant 2 1 Lab-STICC, ENSTA Bretagne, Brest, France (clemence.chupin@ensta-bretagne.fr) 2 LIENSs, UMR CNRS -La Rochelle Université, La Rochelle, France

Context

GEOCEAN-NC Campaign

In situ geodetic measurements

CalNaGeo survey

Multi-mission comparison Long-term comparison

Geodetic instrumentation in the Lagoon

Altimetry validation

Conclusion Bibliography

Today, monitoring the evolution of sea level in coastal areas is of importance, since almost 11% of the world's population leave in low-lying areas (i.e. < 10m above sea level) [1]. Reducing uncertainties in sea level estimates requires a better unederstanding of both altimetry measurements and local sea level dynamics. In New-Caledonia, the GEOCEAN-NC 2019 campaign addresses these issues with the deployment of various geodetic sea level observing systems (e.g. GNSS Buoy, pressure sensor, CalNaGeo GNSS towed carpet), with a particular focus on the intersection of 3 altimetric tracks (i.e. 1 Jason and 2 Sentinel-3a tracks). This work presents a method inspired from altimetry validation studies to re-analyse about 20 years of altimetry data and re-address the question of sea level evolution in the lagoon.

[

1-

  1] Haasnoot et al. "Long-term sea-level rise nessecitates a commitment to adaptation" In: Climate Risk Management 34 (2021), 100355 DOI : 10.1016/ j.crm.2021.100355 [2] Gourdeau et al. "Project SWOT in the tropics -Internal tides and mesoscale interactions in a tropical area: insights from model, in situ data, and SWOT" (2020) [3] Marty et al. "GINS: The CNES/GRGS GNSS scientific software" In: ESA Proceedings WPP326 (2011) [4] Aucan et al. "Historical Sea Level in the South Pacific from Rescued Archives, Geodetic Measurements, and Satellite Altimetry" In: Pure Appl. Geophys. 174 (2017) p.3813-3823 DOI : 10.1007/s00024-017-1648-1 [5] Chupin et al. "Mapping Sea Surface Height Using New Concepts of Kinematic GNSS Instruments" In: Remote Sensing 12 (2020) 2656 DOI : 10.3390/rs12162656 Link pressure sensor observation to a global reference frame by comparing with GNSS buoy data over their common observation period gradient (amplitude and phase) and a datum correction between the pressure gauge and the Noumea tide gauge -Long-term sea level time series [1957-present] : Chaleix and Numbo tide gauges observations linked by Aucan et al. (2017) [4] -Harmonic analysis over [Pressure gauge -Tide gauge] residuals -Datum correction : 57.1 cm (consistent wrt. geoid models estimates) -Tidal gradient : main difference of M2 (~4.5cm) and S2 (~1.7cm) Nadir missions (TOPEX, Jason, Sentinel,etc.) -SWOT Cal/Val path and planned field campaign [2] s s u re G a u g e GNSS Buoy -3 days measurements at the satellite crossover point -Processing in PPP mode using GINS software [3] Pressure gauge -SBE 26 plus deployed at 20m depth over 1 year -Tidal correction to account for tidal differences between the buoy and the pressure gauge location (~ 4km) Basis of the absolute referencing of the in situ observations 2 Validate XGM 2019e gravity field model [7] in our area to account for geoid gradient in altimetry measurements CalNaGeo -GNSS floating carpet towed by N/O ALIS -Map sea surface in motion in various sea and weather conditions [5,6] -Processing in PPP mode using GINS software [3] CalNaGeo geoid anomaly [m] (with respect to the crossover point) CalNaGeo -XGM 2019e [m] T i d e G a u g e Application of tidal gradient reduce RMSE on residuals from 3.7cm to 1.3cm -GDR along-track data processing to derive SSH alt at the crossover point -Validation of radiometer wet tropospheric delays compared to GNSS and ECMWF model estimates -Atmospheric and geophysical corrections from GDR (ionospheric delay, sea state bias, solid earth tide, etc.)

Long-term sea level evolution in Noumea Lagoon