Chao Zhang
email: chao.zhang@uwaterloo.ca

Angela Bonifati
email: angela.bonifati@univ-lyon1.fr

M Tamer Özsu
email: tamer.ozsu@uwaterloo.ca

M Tamer

Angela Bonifati Lyon

An Overview of Reachability Indexes on Graphs

Keywords: Information systems → Graph-based database models, Data structures, Database query processing graph database, reachability query, reachability index

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Graphs are ubiquitous for modeling real-world data [START_REF] Newman | Networks: An Introduction[END_REF] where it is important to represent relationships as first-class objects -vertices represent entities and edges represent relationships. Examples can be found in various domains, e.g., biological networks [START_REF] Koutrouli | A Guide to Conquer the Biological Network Era Using Graph Theory[END_REF], financial networks [START_REF] Mathur | White Paper: Neo4j for Financial Services[END_REF], social networks, transportation networks [START_REF] Barthélemy | Spatial networks[END_REF], and knowledge graphs [START_REF] Gutierrez | Knowledge Graphs[END_REF]. With graph-structured data, one of the most interesting queries is to check the existence of a directed path from one vertex to another, i.e., the transitive relationship from one entity to another in the network, which is known as the reachability query (𝑄 𝑟 ). Reachability queries are well-known fundamental graph data processing operators and have been widely used in practice [START_REF] Sahu | The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing[END_REF][START_REF] Sahu | The ubiquity of large graphs and surprising challenges of graph processing: extended survey[END_REF]. They are considered by some as the most interesting graph-oriented queries [START_REF] Sherif Sakr | The future is big graphs: A community view on graph processing systems[END_REF].

Tutorial outline. In this tutorial, we present an in-depth review of each type of reachability indexes. We start the tutorial with the presentation of the background on reachability queries on graphs ( §2), followed by the review of plain reachability indexes ( §3) and the review of path-constrained reachability indexes ( §4). We end the tutorial by discussing the open challenges ( §5). We share our vision towards having full-fledged indexes in modern GDBMSs for reachability queries.

BACKGROUND

We adopt the common definition of a graph 𝐺 = (𝑉 , 𝐸), where 𝑉 is a set of vertices and 𝐸 is a set of edges, and 𝑒 ∈ 𝐸 ⊆ 𝑉 × 𝑉 . In this paper, the edges are directed. This definition will be enhanced as the graph is enriched. Therefore, the issue is checking the existence of paths in 𝐺 according to the arguments in 𝑄 𝑟 .

Plain reachability

Plain graphs follow the above definition 𝐺 = (𝑉 , 𝐸). Figure 1(a) shows a plain graph. The reachability queries over plain graphs are referred to as plain reachability queries. A plain reachability query 𝑄 𝑟 (𝑠, 𝑡) contains a pair of arguments, a source vertex 𝑠 ∈ 𝑉 and a target vertex 𝑡 ∈ 𝑉 , and 𝑄 𝑟 (𝑠, 𝑡) checks whether there exists a path from 𝑠 to 𝑡 in 𝐺, referred to as an 𝑠-𝑡 path, e.g., in Figure 1(a), 𝑄 𝑟 (𝐴, 𝐺) = 𝑡𝑟𝑢𝑒 because of an 𝑠-𝑡 path (𝐴, 𝐷, 𝐻, 𝐺).

Path-constrained reachability

Edge-labeled graphs can contain different kinds of relationships, where each edge is assigned a specific label, e.g., RDF graphs [START_REF] Graham | RDF 1.1 Concepts and Abstract Syntax[END_REF]. In this case, the graph is defined as 𝐺 = (𝑉 , 𝐸, 𝐿), where 𝐿 is a set of labels and each 𝑒 ∈ 𝐸 is assigned a label 𝑙 ∈ 𝐿. Figure 1(b) shows an edge-labeled graph, representing a social network with three kinds of relationships, i.e., 𝐿 = {friendOf, follows, worksFor}. Reachability queries over edge-labeled graphs can be expressed with additional constraints on paths using edge labels [START_REF] Jin | Computing Label-Constraint Reachability in Graph Databases[END_REF][START_REF] Zhang | A Reachability Index for Recursive Label-Concatenated Graph Queries[END_REF], referred to as path-constrained reachability queries. A pathconstrained reachability query 𝑄 𝑟 (𝑠, 𝑡, 𝛼) contains as arguments source (𝑠) and target (𝑡) vertices, and an expression 𝛼 specifying the path constraint using 𝐿. 𝑄 𝑟 (𝑠, 𝑡, 𝛼) checks whether there exists an 𝑠-𝑡 path in 𝐺 such that the path can satisfy the constraint enforced by 𝛼. In general, 𝛼 is defined as a regular expression using edge labels 𝑙 ∈ 𝐿 as literal characters and using concatenation '•', alternation '∪', and the Kleene operators (star ' * ' or plus '+') as

Reachability processing

Plain reachability queries can be processed by performing online traversal [START_REF] Hilmi Yildirim | GRAIL: Scalable Reachability Index for Large Graphs[END_REF], e.g., breadth-first traversal (BFS), depth-first traversal (DFS), or bidirectional breadth-first traversal (BiBFS). However, these approaches visit a large portion of the graph, which is prohibitively inefficient for large graphs. Path-constrained reachability queries can be processed by guided graph traversal: a finite automata (FA) can be built according to the regular expression 𝛼 in the query, and then the traversal is guided by the FA [START_REF] Angles | Foundations of Modern Query Languages for Graph Databases[END_REF][START_REF] Bonifati | Querying Graphs[END_REF]. However, a significant portion of the graph still needs to be visited because of the presence of the Kleene operator in 𝛼.

The naive approach to accelerate plain reachability queries is to build a transitive closure (TC) [START_REF] Agrawal | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases[END_REF], which can be extended to path-constrained reachability queries, called generalized transitive closure (GTC) [START_REF] Jin | Computing Label-Constraint Reachability in Graph Databases[END_REF][START_REF] Zhang | A Reachability Index for Recursive Label-Concatenated Graph Queries[END_REF]. TC computes and stores the existence of a path between every pair of vertices in the graph. Although query processing with TC requires only constant time, the high computation and storage costs make it infeasible in practice. GTC extends TC by adding additional information of edge labels to deal with path-constrained reachability queries. However, the computation of GTC is more challenging than the computation of TC because of the additional distinction of paths according to a large number of possible path constraints in graphs. Consequently, computing GTC is also infeasible in practice.

Over the past three decades, significant research has focused on designing advanced data structures to efficiently compute and store Table 1: A review of plain reachability indexes.

Indexing Technique

Framework Index Type Input Dynamic Tree cover [START_REF] Agrawal | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases[END_REF] Tree cover Complete DAG No Tree+SSPI [START_REF] Chen | Stack-Based Algorithms for Pattern Matching on DAGs[END_REF] Tree cover Partial DAG No Dual labeling [START_REF] Wang | Dual Labeling: Answering Graph Reachability Queries in Constant Time[END_REF] Tree cover Complete DAG No GRIPP [START_REF] Trißl | Fast and Practical Indexing and Querying of Very Large Graphs[END_REF] Tree cover Partial General No Path-tree [START_REF] Jin | Path-Tree: An Efficient Reachability Indexing Scheme for Large Directed Graphs[END_REF][START_REF] Jin | Efficiently Answering Reachability Queries on Very Large Directed Graphs[END_REF] Tree cover Complete DAG Yes GRAIL [START_REF] Hilmi Yildirim | GRAIL: Scalable Reachability Index for Large Graphs[END_REF] Tree cover Partial DAG No Ferrari [START_REF] Seufert | FERRARI: Flexible and efficient reachability range assignment for graph indexing[END_REF] Tree cover Partial DAG No DAGGER [START_REF] Hilmi Yildirim | DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs[END_REF] Tree cover Partial DAG Yes TCs or GTCs while providing efficient processing for (plain/pathconstrained) reachability queries. These advanced data structures are known as reachability indexes [2, 7-11, 13, 14, 17-20, 25-27, 29, 31, 34, 35, 39-41, 43, 45, 46, 49-51, 55]. The general intuition in designing reachability indexes is to reduce the redundant recording of reachability information in building TCs or GTCs and to store succinct information among different reachable pairs of vertices. This makes it possible to derive the reachability for any pair of vertices in the graph. The derivation process should take much less time than the query processing using online graph traversal, which makes indexes interesting. There exist two different types of reachability indexes that mirror the reachability queries: plain reachability indexes [2, 7-9, 11, 13, 14, 17-20, 25-27, 29, 31, 34, 35, 39-41, 43, 45, 46, 49-51, 55] and path-constrained reachability indexes [START_REF] Chen | DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs[END_REF][START_REF] Chen | Graph Indexing for Efficient Evaluation of Label-constrained Reachability Queries[END_REF][START_REF] Jin | Computing Label-Constraint Reachability in Graph Databases[END_REF][START_REF] Peng | Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond[END_REF][START_REF] Lucien | Landmark Indexing for Evaluation of Label-Constrained Reachability Queries[END_REF][START_REF] Zhang | A Reachability Index for Recursive Label-Concatenated Graph Queries[END_REF][START_REF] Zou | Efficient Processing of Label-Constraint Reachability Queries in Large Graphs[END_REF].

2-Hop

PLAIN REACHABILITY INDEXES

The existing plain reachability indexes can be grouped into three main classes according to the underlying frameworks with a few additional techniques: tree-cover [START_REF] Agrawal | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases[END_REF], 2-hop labeling [START_REF] Cohen | Reachability and Distance Queries via 2-Hop Labels[END_REF], and approximate TC [START_REF] Wei | Reachability Querying: An Independent Permutation Labeling Approach[END_REF]. The plain reachability indexes are summarized in Table 1. The Index Type column denotes whether an index is partial or complete. Complete indexes can process queries by using only index lookups, while partial indexes require additional graph traversal. The Input column indicates the type of graph that the index assumes as input: DAG for directed acyclic and General for general graphs. The Dynamic column indicates whether the index can support graph updates, i.e., edge/vertex deletion and insertion.

Tree-Cover-Based Indexes

The foundation of the tree-cover index [START_REF] Agrawal | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases[END_REF] is one or more intervals attached to each vertex, which are leveraged to process reachability queries. Let [𝑎 𝑣 , 𝑏 𝑣 ] denote the interval attached to vertex 𝑣. Treecover approach is defined on spanning trees of a general graph and then extended to deal with the edges that are not covered by the spanning trees. Thus, we can identify three basic structures: (1) trees; (2) DAGs; and (3) general graphs. The indexing techniques [START_REF] Chen | Stack-Based Algorithms for Pattern Matching on DAGs[END_REF][START_REF] Wang | Dual Labeling: Answering Graph Reachability Queries in Constant Time[END_REF][START_REF] Jin | Path-Tree: An Efficient Reachability Indexing Scheme for Large Directed Graphs[END_REF][START_REF] Jin | Efficiently Answering Reachability Queries on Very Large Directed Graphs[END_REF][START_REF] Seufert | FERRARI: Flexible and efficient reachability range assignment for graph indexing[END_REF][START_REF] Trißl | Fast and Practical Indexing and Querying of Very Large Graphs[END_REF][START_REF] Hilmi Yildirim | GRAIL: Scalable Reachability Index for Large Graphs[END_REF][START_REF] Hilmi Yildirim | DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs[END_REF] based on the tree-cover framework are listed in the the first block of Table 1. The intervals attached to vertices differ in each of these.

Interval labeling for trees. In this class of techniques, for each vertex 𝑣, 𝑏 𝑣 is 𝑣's post-order number obtained by the post-order traversal from the root of the tree, and 𝑎 𝑣 is the lowest post-order number of all the descendants of 𝑣 in the tree. 𝑄 𝑟 (𝑠, 𝑡) can be processed by checking if 𝑏 𝑡 ∈ [𝑎 𝑠 , 𝑏 𝑠 ]. The intuition is that 𝑄 𝑟 (𝑠, 𝑡) can be processed by checking whether the sub-tree rooted at 𝑠 in the spanning tree of 𝐺 contains 𝑡, and the intervals assigned to vertices encode sufficient information for such a checking.

Reachability in DAGs. A major problem arises when using the interval labeling approach to deal with reachability in a DAG: if vertex 𝑡 is reachable from vertex 𝑠 only via paths containing non-tree edges, interval labeling cannot capture such paths. In the original tree-cover approach, the problem is solved by first computing vertex intervals based on spanning trees of the DAG and then inheriting vertex intervals. For a non-tree edge (𝑢, 𝑣) with intervals [𝑎 𝑢 , 𝑏 𝑢 ] and [𝑎 𝑣 , 𝑏 𝑣 ] and

𝑏 𝑣 ∉ [𝑎 𝑢 , 𝑏 𝑢 ], in order to record that 𝑣 is reachable from 𝑢, 𝑢 inherits [𝑎 𝑣 , 𝑏 𝑣 ] from 𝑣. Consequently, 𝑢 has two intervals [𝑎 𝑢 , 𝑏 𝑢 ] and [𝑎 𝑣 , 𝑏 𝑣 ].
Interval inheritance is also required for tree edges in the DAG due to the transitivity of reachability, e.g., for a tree edge (𝑤, 𝑢), 𝑣 is reachable from 𝑤, such that 𝑤 needs to inherit [𝑎 𝑣 , 𝑏 𝑣 ] from 𝑢. in DAGs are examined in the reverse topological order to inherit intervals. In case intervals for a vertex happen to be adjacent, they can be merged for efficient storage, e.g., intervals [START_REF] Abiteboul | Regular Path Queries with Constraints[END_REF][START_REF] Bonifati | Navigating the Maze of Wikidata Query Logs[END_REF] and [START_REF] Bramandia | Incremental Maintenance of 2-Hop Labeling of Large Graphs[END_REF][START_REF] Cai | Path-Hop: Efficiently Indexing Large Graphs for Reachability Queries[END_REF] can be merged to interval [START_REF] Abiteboul | Regular Path Queries with Constraints[END_REF][START_REF] Cai | Path-Hop: Efficiently Indexing Large Graphs for Reachability Queries[END_REF].

From cyclic graphs to DAGs. General graphs with directed cycles can be transformed to a DAG using an efficient reduction method (Tarjan's algorithm [START_REF] Tarjan | Depth-first search and linear graph algorithms[END_REF]) in linear time. Specifically, all the strongly connected components (SCC), where each vertex is reachable from every other vertex, are identified, and each SCC is coarsened into a representative vertex. The output of the transformation will be a DAG. Then, 𝑄 𝑟 (𝑠, 𝑡) can be processed by first checking whether 𝑠 and 𝑡 belong to the same SCC, followed by checking the reachability in the DAG in case they are in different SCCs using the DAG approach discussed above. Thus, most plain reachability indexes in literature assume DAGs as input since generalization is easy.

In a nutshell, the tree-cover index is the interval labeling approach with interval inheritance. The main drawback of the treecover approach is the potentially large number of intervals as each vertex may need to inherit intervals form other vertices due to the existence of non-tree edges in the graph. The index size is defined as the total number of intervals allocated to vertices, and a DAG can be covered by spanning trees of different shapes, which result in different index sizes. The optimal tree cover [START_REF] Agrawal | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases[END_REF] can lead to the minimum index size. However, the complexity of computing the minimum size index based on the optimal tree cover is the same as that of computing TC [START_REF] Agrawal | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases[END_REF], which is unfeasibly high in practice.

Several follow-up works [START_REF] Chen | Stack-Based Algorithms for Pattern Matching on DAGs[END_REF][START_REF] Seufert | FERRARI: Flexible and efficient reachability range assignment for graph indexing[END_REF][START_REF] Hilmi Yildirim | GRAIL: Scalable Reachability Index for Large Graphs[END_REF] aim at reducing the number of intervals for each vertex. These works adopt two types of designs for reducing the number of intervals: (1) recording exactly 𝑘 intervals (e.g., GRAIL [START_REF] Hilmi Yildirim | GRAIL: Scalable Reachability Index for Large Graphs[END_REF]) and (2) recording at most 𝑘 intervals (e.g., Ferrari [START_REF] Seufert | FERRARI: Flexible and efficient reachability range assignment for graph indexing[END_REF]), where 𝑘 is an input parameter. In GRAIL, the 𝑘 intervals are computed by using 𝑘 random spanning trees. In Ferrari, intervals are merged even if they are not adjacent so as to guarantee that the maximum number of intervals for each vertex is not larger than 𝑘, which leads to the existence of approximate intervals. Neither approach computes a complete index, and the query results using index lookups may contain false positives but no false negatives. Thus, these partial indexes can be used to guide online traversal to compute correct query results. Although partial indexes require additional graph traversal for query processing, their index building time and index size scale linearly with the input graph size, making them one of the first methods feasible for large graphs with millions of vertices. In addition, reachability processing using these indexes can be an order of magnitude faster than using only graph traversal. GRAIL is extended for dynamic graphs in DAGGER [START_REF] Hilmi Yildirim | DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs[END_REF].

Several early works extend interval labeling, including duallabeling [START_REF] Wang | Dual Labeling: Answering Graph Reachability Queries in Constant Time[END_REF], GRIPP [START_REF] Trißl | Fast and Practical Indexing and Querying of Very Large Graphs[END_REF], and path-tree [START_REF] Jin | Path-Tree: An Efficient Reachability Indexing Scheme for Large Directed Graphs[END_REF][START_REF] Jin | Efficiently Answering Reachability Queries on Very Large Directed Graphs[END_REF]. However, their sophisticated designs might not be able to deal with current realworld graphs. Specifically, dual-labeling and path-tree are designed for tree structures e.g., XML databases, and their application to graphs works well only if the number of non-tree edges is very low. Although GRIPP is a partial index, it requires graph traversal if the partial index returns false, which is not competitive compared to the design of GRAIL and Ferrari that do not have false negatives in the query results returned by their partial indexes.

2-Hop-Based Indexes

The 2-hop labeling lies in between transitive closure materialization and online search (BFS, DFS, BiBFS). In the 2-hop index [START_REF] Cohen | Reachability and Distance Queries via 2-Hop Labels[END_REF], each vertex 𝑣 ∈ 𝑉 is labeled with two sets of vertices: 𝐿 𝑖𝑛 (𝑣) and 𝐿 𝑜𝑢𝑡 (𝑣). A vertex 𝑢 ∈ 𝐿 𝑖𝑛 (𝑣) if 𝑣 is reachable from 𝑢 and similarly for 𝐿 𝑜𝑢𝑡 (𝑣). Construction of these sets is discussed below. 𝑄 𝑟 (𝑠, 𝑡) is processed by checking whether one of the following cases can be satisfied:

(1) 𝑠 ∈ 𝐿 𝑖𝑛 (𝑡); (2) 𝑡 ∈ 𝐿 𝑜𝑢𝑡 (𝑠); (3) 𝐿 𝑖𝑛 (𝑡) ∩ 𝐿 𝑜𝑢𝑡 (𝑠) ≠ ∅, i.e., we can compute whether 𝑡 is reachable from 𝑠 by determining whether there exists at least a common hop 𝑢. The indexing techniques based on the 2-hop index [START_REF] Bramandia | Incremental Maintenance of 2-Hop Labeling of Large Graphs[END_REF][START_REF] Cai | Path-Hop: Efficiently Indexing Large Graphs for Reachability Queries[END_REF][START_REF] Cheng | TF-Label: A Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph[END_REF][START_REF] Hanauer | O'Reach: Even Faster Reachability in Large Graphs[END_REF][START_REF] Jin | Simple, Fast, and Scalable Reachability Oracle[END_REF][START_REF] Jin | 3-HOP: A High-Compression Indexing Scheme for Reachability Query[END_REF][START_REF] Lyu | DBL: Efficient Reachability Queries on Dynamic Graphs[END_REF][START_REF] Schenkel | Efficient creation and incremental maintenance of the HOPI index for complex XML document collections[END_REF][START_REF] Yano | Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths[END_REF][START_REF] Diwen Zhu | Reachability Queries on Large Dynamic Graphs: A Total Order Approach[END_REF] are listed in the second block of Table 1. Notice that unlike the tree-cover index, the 2-hop index can be directly applied to general graphs.

The index size of the 2-hop index is 𝑛 𝑖=1 |𝐿 𝑜𝑢𝑡 (𝑣 𝑖 )| + |𝐿 𝑖𝑛 (𝑣 𝑖 )| for a graph with 𝑛 vertices. The minimum 2-hop index is the one with the minimum index size. Computing the minimum 2-hop index is NP-hard [START_REF] Cohen | Reachability and Distance Queries via 2-Hop Labels[END_REF]. An approximation algorithm was proposed in the original work of the 2-hop index. However, the time complexity is 𝑂 (𝑛 4 ), which is infeasible for large graphs.

Efficiently computing the 2-hop index while reducing the index size maximally has been a long-standing problem. Advanced heuristics have been proposed, including TFL [START_REF] Cheng | TF-Label: A Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph[END_REF], DL [START_REF] Jin | Simple, Fast, and Scalable Reachability Oracle[END_REF], PLL [START_REF] Yano | Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths[END_REF], and TOL [START_REF] Diwen Zhu | Reachability Queries on Large Dynamic Graphs: A Total Order Approach[END_REF]. TOL is a general approach for computing the 2-hop index with a total order of vertices as input, and TFL, DL, and PLL are instantiations of TOL, i.e., an instantiation of a total order is used in each of them. Let 𝑜 be a strict total order on 𝑉 and 𝑜 (𝑣) be the rank of 𝑣 in 𝑜. TOL applies backward and forward BFSs from each vertex 𝑣 ∈ 𝑉 , and for each vertex 𝑢 visited by the BFSs, TOL adds 𝑣 to 𝐿 𝑜𝑢𝑡 (𝑢) and 𝐿 𝑖𝑛 (𝑢) respectively only if 𝑢 ∈ 𝑉 satisfies 𝑜 (𝑢) > 𝑜 (𝑣).

If a vertex 𝑤 such that 𝑜 (𝑤) < 𝑜 (𝑣) is visited by the backward and forward BFSs from 𝑣, then the BFSs immediately terminate, i.e., the search space for computing the reachability paths to and from each 𝑣 is pruned according to the total order 𝑜. An instantiation of 𝑜 is the topological order of a DAG (obtained after coalescing all the SCCs), which is the strategy used in TFL. Another instantiation of 𝑜 is based on vertex degree, which is adopted in DL and PLL. It has been proven that DL and PLL are equivalent [START_REF] Jin | Simple, Fast, and Scalable Reachability Oracle[END_REF].

Several works based on the 2-hop index also study how to accommodate dynamic graphs. TOL can handle both insertions and deletions by leveraging the total order of vertices. DBL [START_REF] Lyu | DBL: Efficient Reachability Queries on Dynamic Graphs[END_REF] is a recent proposal based on the 2-hop index designed for insertion-only. The U2-hop [START_REF] Bramandia | Incremental Maintenance of 2-Hop Labeling of Large Graphs[END_REF] approach and the approach by Ralf et al. [START_REF] Schenkel | Efficient creation and incremental maintenance of the HOPI index for complex XML document collections[END_REF] study the maintenance of the 2-hop index on dynamic graphs, but it has been shown that they cannot scale to large graphs [START_REF] Diwen Zhu | Reachability Queries on Large Dynamic Graphs: A Total Order Approach[END_REF].

There are a few extensions of 2-hop indexing. Early works replace the intermediate vertices in the reachability path with graph structures, i.e., chains in the 3-hop index [START_REF] Jin | 3-HOP: A High-Compression Indexing Scheme for Reachability Query[END_REF] and trees in the pathhop index [START_REF] Cai | Path-Hop: Efficiently Indexing Large Graphs for Reachability Queries[END_REF]. Although these approaches can further reduce the index size, they require more time to build the index compared to recent 2-hop indexes. O'Reach [START_REF] Hanauer | O'Reach: Even Faster Reachability in Large Graphs[END_REF], one of the state-of-the-art indexes, builds a partial 2-hop index by selecting 𝑘 vertices and processes queries with an extended topological order.

Approximate Transitive Closure

Let 𝑂𝑢𝑡 (𝑣) be the set of all the vertices that are reachable from 𝑣 in the graph (note that this is different from 𝐿 𝑜𝑢𝑡 (𝑣) defined earlier). Then, the computation of the TC for a graph is basically computing 𝑂𝑢𝑡 (𝑣) for every vertex 𝑣 in the graph, which is unrealistic in practice. The intuition of an approximate TC is computing an approximate version of 𝑂𝑢𝑡 (𝑣) efficiently. We use 𝐴𝑃 () to denote the approximating function. Note that |𝐴𝑃 (𝑂𝑢𝑡 (𝑣))| ≪ |𝑂𝑢𝑡 (𝑣)|. The 𝐴𝑃 () function needs to be carefully designed so that it provides correct query results instead of random ones. The design of 𝐴𝑃 () can be guided by the following observation. If it is known that vertex 𝑡 is reachable from vertex 𝑠 in the graph, then 𝑂𝑢𝑡 (𝑡) ⊆ 𝑂𝑢𝑡 (𝑠). If 𝐼𝑛(𝑣) is defined as the dual, namely it contains all the vertices that reach 𝑣, a similar observation can be obtained, i.e., if 𝑡 is reachable from 𝑠, then 𝐼𝑛(𝑠) ⊆ 𝐼𝑛(𝑡). Although the observation does not make sense since it contradicts processing 𝑄 𝑟 (𝑠, 𝑡), it turns out that the contra-positive condition can be leveraged: if 𝑂𝑢𝑡 (𝑡) is not a subset of 𝑂𝑢𝑡 (𝑠), then 𝑡 is not reachable from 𝑠 in the graph. Therefore, as long as the 𝐴𝑃 () function preserves the contra-positive conditions -if 𝐴𝑃 (𝑂𝑢𝑡 (𝑡)) is not a subset of 𝐴𝑃 (𝑂𝑢𝑡 (𝑠)), then 𝑂𝑢𝑡 (𝑡) is not a subset of 𝑂𝑢𝑡 (𝑠) -the approximate TC built using the 𝐴𝑃 () function will not provide false negatives.

The first design of the 𝐴𝑃 () function uses a k-min-wise independent permutation, leading to the IP index [START_REF] Wei | Reachability Querying: An Independent Permutation Labeling Approach[END_REF][START_REF] Wei | Reachability Querying: An Independent Permutation Labeling Approach[END_REF], followed by using a Bloom filter in BFL [START_REF] Su | Reachability Querying: Can It Be Even Faster?[END_REF], which is one of the state-of-the-art techniques for plain reachability indexing. Query processing using IP or BFL does not have false negatives since the corresponding 𝐴𝑃 () function can preserve the contra-positive condition. However, false positives might exist, which calls for additional graph traversal. Similar to the case of the partial indexing techniques based on the tree cover framework, the graph traversal can be pruned by recursively querying the index, i.e., if all the neighbors of 𝑣 (the vertex currently visited by the traversal from the source vertex) do not reach the target vertex, then 𝑣 can be skipped in the traversal.

Other Techniques

A few graph reduction techniques are proposed to accelerate reachability indexing, including SCARAB [START_REF] Jin | SCARAB: Scaling Reachability Computation on Large Graphs[END_REF], ER [START_REF] Zhou | DAG Reduction: Fast Answering Reachability Queries[END_REF], and RCN [START_REF] Zhou | Fast Reachability Queries Answering Based on RCNRCN Reduction[END_REF]. These reduction techniques are orthogonal to the indexing techniques. Several other techniques that do not use the three indexing frameworks discussed earlier also exist in literature, including HL [START_REF] Jin | Simple, Fast, and Scalable Reachability Oracle[END_REF], Feline [START_REF] Rodrigues Veloso | Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach[END_REF], and Preach [START_REF] Merz | PReaCH: A fast lightweight reachability index using pruning and contraction hierarchies[END_REF]. In general, these indexes have their own designs to deal with reachability queries. A few early works study the maintenance of transitive closure or SCCs on dynamic graphs, including [START_REF] Henzinger | Fully dynamic biconnectivity and transitive closure[END_REF][START_REF] Roditty | Decremental Maintenance of Strongly Connected Components[END_REF][START_REF] Roditty | A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time[END_REF], but these approaches cannot scale to large graphs [START_REF] Diwen Zhu | Reachability Queries on Large Dynamic Graphs: A Total Order Approach[END_REF].

PATH-CONSTRAINED REACHABILITY INDEXES

The

= (𝑙 1 •𝑙 2 • ...) * , ∀𝑙 𝑖 ∈ 𝐿[52].
Unfortunately, there is currently no index that can support both query classes; indexes have been proposed for either one or the other and these are shown in Table 2. As indicated in the table, there are three index classes that support alternation-based queries:

(1) tree-based, (2) 2-hop, and (3) GTC. The first two are extensions of their counterparts for the plain graphs, while GTC is an extended TC enriched by edge label information specific for this query type. There is only one index that has been proposed for concatenation. In the remainder, we discuss each of these index classes.

Indexes for Alternation-Based Queries

An alternation of edge labels defines a set of labels 𝐿 ′ ⊆ 𝐿, and the path constraint in 𝑄 𝑟 (𝑠, 𝑡, 𝛼) enforces that an 𝑠-𝑡 path should only contain edges with labels that are in 𝐿 ′ , e.g., if 𝛼 = (friendOf ∪ follows) * , then 𝐿 ′ = {friendOf, follows}, and 𝑄 𝑟 (𝐴, 𝐺, 𝛼) = 𝑓 𝑎𝑙𝑠𝑒 in Figure 1(b). An alternation-based reachability query is also known as label-constrained reachability (LCR) query. Sufficient path-label sets. The problem of indexing alternationbased reachability queries is first studied by Jin et al. [START_REF] Jin | Computing Label-Constraint Reachability in Graph Databases[END_REF], where two foundations on edge label information for indexing such queries are proposed. The first foundation is that if there are two 𝑠-𝑡 paths with edge-label sets 𝑆 1 and 𝑆 2 and 𝑆 1 ⊆ 𝑆 2 , then 𝑆 2 is redundant, which means recording 𝑆 1 in the index is sufficient. Edge-label sets such as 𝑆 1 are denoted as sufficient path-label sets (SPLS). For instance, in Figure 1(b), vertex M is reachable from vertex L via two paths: 𝑝 1 = (L, worksFor, C, worksFor, M), and 𝑝 2 = (L, follows, K, worksFor, M), and the label set of 𝑝 1 is a subset of the label set of 𝑝 2 , such that the former is the SPLS from 𝐿 to 𝑀. The second foundation is that the SPLSs of paths from vertex 𝑠 to vertex 𝑡 can be obtained by computing the cross product of the ones from vertex 𝑠 to vertex 𝑢 and the ones from vertex 𝑢 to vertex 𝑡 (transitivity of SPLSs). For instance, in Figure 1(b), the SPLS from A to M is {follows, worksFor}, which can be computed by using the SPLS from A to L, i.e., {follows}, and the SPLS from L to M, i.e., {worksFor}.

4.1.1

Tree-Based Indexes. The first indexing approach is proposed by Jin et al. [START_REF] Jin | Computing Label-Constraint Reachability in Graph Databases[END_REF], which consists of a tree-based index enriched with SPLSs and a partial GTC for paths with non-tree edges. The general idea is to characterize paths in the graph into 2 cases: case (1) the first or the last edge in the path is a tree edge, and case (2) neither the first nor the last edge is a tree edge. A partial GTC containing SPLSs is pre-computed to deal with the reachability caused by the paths in case [START_REF] Agrawal | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases[END_REF]. Reachability due to the paths in case ( 1) is processed by combining spanning trees and the partial GTC, i.e., visiting the successors of the source and the predecessors of the target in a spanning tree and then for each possible successor-predecessor pair checking the partial GTC. Two optimization techniques are proposed to speed up query processing. The first optimization is based on interval labeling to efficiently find the successors and the predecessors in a spanning tree. The second optimization is recording the occurrences of individual edge labels in SPLSs of the paths from the root 𝑟 of a spanning tree to each vertex in the spanning tree. Then, the SPLS of an 𝑠-𝑡 path in the spanning tree can be computed by subtracting the SPLS of the 𝑟 -𝑠 path from the SPLS of the 𝑟 -𝑡 path in the tree.

One of the state-of-the-art indexes is proposed by Chen et al. [START_REF] Chen | Graph Indexing for Efficient Evaluation of Label-constrained Reachability Queries[END_REF]. The approach uses spanning trees to classify edges and distinguishes the reachability caused by different classes. Specifically, after computing a spanning tree (or forest) 𝑇 in 𝐺, directed edges (𝑢, 𝑣) are grouped into four disjoint classes: (1) tree edge if (𝑢, 𝑣) is an edge in 𝑇 ; (2) forward edge if 𝑣 is a descendant of 𝑢 in 𝑇 ; (3) back edge if 𝑣 is an ancestor of 𝑢 in 𝑇 ; and (4) cross edge if 𝑣 is neither an ancestor nor descendant of 𝑢 in 𝑇 . Tree and forward edges are grouped together to form a tree-like structure, denoted as T . The reachability information in T can be efficiently encoded by the interval labeling approach enriched with SPLSs. More precisely, as there is already a path in 𝑇 for each forward edge in T , the interval labeling built for 𝑇 is able to encode the plain reachability information in T . In order to efficiently record the SPLSs in T , the second optimization technique in the approach discussed earlier [START_REF] Jin | Computing Label-Constraint Reachability in Graph Databases[END_REF] is adopted, i.e., recording the SPLSs of paths from the root of T to each 𝑣 in T and the occurrence of each individual edge label in each SPLS. Then, 𝐺 is compressed by keeping only the vertices and edges that can transfer the reachability information caused by cross edges, which leads to a summary 𝐺 𝑐 . Thus, 𝐺 is decomposed into (T , 𝐺 𝑐 ). 𝐺 𝑐 is then taken as input, denoted as 𝐺 1 , and further decomposed into (T 1 , 𝐺 1 𝑐 ), which are the tree-like structure and the graph summary of 𝐺 1 , respectively. The approach applies a recursive decomposition method until the decomposition of 𝐺 𝑖 only contains a tree-like structure T 𝑖 . The series of the decomposition results are used as the index of the approach. In each decomposition result (T 𝑖 , 𝐺 𝑖 𝑐 ), the reachability information caused by back edges in 𝐺 𝑖 are taken into account by performing online search with a optimization of chaining back edges, e.g., for back edges (𝑢, 𝑣) and (𝑢 ′ , 𝑣 ′ ), if 𝑢 ′ is a descendant of 𝑣 in T 𝑖 , then they are chained into a back path (𝑢, 𝑣 ′ ). Finally, 𝑄 𝑟 (𝑠, 𝑡, 𝛼) is recursively decomposed into sub-queries that are evaluated on the series (T , T 1 , ...) with online search for back paths, and if an 𝑠-𝑡 satisfying 𝛼 can be found by using T 𝑖 , then query result 𝑡𝑟𝑢𝑒 will be returned.

4.1.2 GTC-Based Indexes. The problem of efficiently computing a GTC for alternation-based reachability queries is extensively studied by Zou et al. [START_REF] Xu | Answering Label-Constraint Reachability in Large Graphs[END_REF][START_REF] Zou | Efficient Processing of Label-Constraint Reachability Queries in Large Graphs[END_REF]. The fundamental step is to compute a single-source GTC, e.g., computing all the vertices that are reachable from a source vertex and the corresponding SPLSs. A Dijkstra-like algorithm is proposed by using the number of distinct labels in path-label sets to simulate distances between vertices. Consider the computation of the single-source GTC from vertex 𝐿 in Figure 1(b). 𝐻 is reachable from 𝐿 via two paths: 𝑝 3 = (𝐿, worksFor, 𝐶, worksFor, 𝐻 ) and 𝑝 4 =(𝐿, worksFor, 𝐷, friendOf, 𝐻 ). Path 𝑝 3 is 'shorter' than 𝑝 4 since 𝑝 3 has only 1 distinct label while 𝑝 4 has 2. Thus, 𝑝 3 is expanded to compute SPLS from 𝐿 to 𝐺 and 𝑝 4 is ignored. An input graph is first transformed into a DAG, and then the computation is done by following the topological order of the DAG so as to share the single-source GTC of vertices in a bottom-up manner. The transformation from a general graph to a DAG for alternation-based reachability is more complicated than the one for plain reachability discussed in Section 3, because paths in SCCs are not equivalent due to different SPLSs. Each SCC is replaced by a bipartite graph with in-portal and out-portal vertices. A vertex 𝑣 in an SCC is in-portal (or out-portal) iff 𝑣 has at least one incoming (or outgoing) edge from vertices out of the SCC. Then, the SPLSs from in-portal to out-portal vertices are computed and recorded in the index. In computing the reachability information within each SCC, the Dijkstra-like algorithm is further optimized by starting the computation from vertices of high degree; the single-source GTC of such vertices will be leveraged to prune search space for the subsequent computations. The index maintenance problem on dynamic graphs is also discussed.

A partial index with online BFS has been proposed [START_REF] Lucien | Landmark Indexing for Evaluation of Label-Constrained Reachability Queries[END_REF]. The partial index is a set of single-source GTCs for a subset of vertices in the graph. The subset of vertices is selected as those in the top-𝑘 degree ranking, referred to as landmark vertices. 𝑄 𝑟 (𝑠, 𝑡, 𝛼) is processed by performing BFS with acceleration through leveraging the partial index when landmark vertices are hit during the traversal from 𝑠. If the single-source GTC of a landmark vertex 𝑣 that is hit by the BFS from 𝑠 contains 𝑡 with a SPLS that can satisfy 𝛼, then the approach returns true. Otherwise, all the vertices that are reachable from the landmark 𝑣 under the constraint 𝛼 can be pruned in the subsequent search. In addition, the querying process is further improved by computing the reachability and SPLSs of paths from non-landmark vertices to landmark vertices, where the number of indexed paths is controlled by a predefined parameter.

4.1.3 2-Hop-Based Indexes. P2H+ [START_REF] Peng | Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond[END_REF] is a 2-hop-based reachability index for alternation-based reachability queries. The index utilizes the 2-hop index as the framework and adds SPLSs to deal with path constraints. The 2-hop indexing algorithm is extended to build the P2H+ index by leveraging the transitivity of 2-hop reachability and SPLSs. The indexing algorithm of P2H+ performs backward and forward BFSs from vertices sorted in a total order according to vertex degree (from high degree to low degree), during which pruning rules are applied to skip redundant traversal. In addition, the indexing algorithm can guarantee that the built index does not contain any redundancy, which is achieved by prioritizing the visiting of edges with labels that are already contained in the SPLSs of the paths from 𝑣 to current frontier vertices during the BFS from each vertex 𝑣.

DLCR [START_REF] Chen | DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs[END_REF], one of the state-of-the-art indexes, extends P2H+ to support graph updates, including edge insertions and deletions. When an edge is updated, DLCR will identify a set of nodes that need to perform backward and forward BFSs to reflect the update into the index. The BFS performed for edge updates only needs to traverse paths that contain the updated edges. During the BFS traversal, DLCR further identifies affected vertices that require additional index updates to either remove redundancy (in the case of edge insertion) or keep the index correct (in the case of edge deletion). In general, in the case of edge insertion, the newly inserted edge could make existing index entries redundant, which needs to be deleted. For each index entry 𝐼𝐸 in DLCR, there might be index entries that are redundant because of 𝐼𝐸 so that the set of such redundant index entries, referred to as 𝑅𝐼𝐸, is not included in DLCR. However, if the updates for reflecting the changes caused by a deleted edge require deleting 𝐼 𝐸, index entries in 𝑅𝐼𝐸 might become non-redundant so that they need to be inserted into DLCR to keep the index correct.

Indexes for Concatenation-Based Queries

A concatenation of edge labels defines a sequence, and the corresponding path constraint in 𝑄 𝑟 (𝑠, 𝑡, 𝛼) enforces that the edge-label sequence of an 𝑠-𝑡 path must be an arbitrary number of repeats of the sequence of concatenated edge labels defined under the Kleene operator in 𝛼, e.g., 𝑄 𝑟 (𝐿, 𝐵, worksFor • friendOf) * ) = 𝑡𝑟𝑢𝑒 in Figure 1(b). A concatenation-based reachability query is also known as recursive label-concatenated (RLC) query.

The problem of indexing concatenation-based reachability queries is first studied by Zhang et al. [START_REF] Zhang | A Reachability Index for Recursive Label-Concatenated Graph Queries[END_REF] which proposes the RLC index. To index such queries, the minimum repeats (MR) of edge-label sequence are recorded, e.g., the MR of the path (L, worksFor, D, friendOf, H, worksFor, G, friendOf, B) is (worksFor, friendOf), and the MR is helpful in processing 𝑄 𝑟 (𝐿, 𝐵, worksFor•friendOf) * ). The RLC index leverages the 2-hop index framework and records, additionally, MRs of edge-label sequences. Recording the MRs might be prohibitive due to the presence of infinite MRs of 𝑠-𝑡 paths as a result of directed cycles on the paths. In order to deal with this challenge, the concatenation length under the Kleene operator in 𝛼 is leveraged to guide the computation of MRs. The second challenge is that MRs do not necessarily have the transitive property, e.g., it is unfeasible to derive the MR of an 𝑠-𝑡 path given that the MRs of an 𝑠-𝑢 path and a 𝑢-𝑡 path are (𝑙 1 ) and (𝑙 2 ), respectively. Thus, the indexing algorithm of the RLC index separates the index building process into two phases: the first phase computes all the possible MRs for any (𝑠, 𝑡), and the second phase selects the transitive MRs to build the index. Pruning rules are proposed to avoid redundant computation and recording in the index.

OPEN CHALLENGES

The state-of-the-art plain reachability indexes can be built for a large graph efficiently, e.g., BFL can be built in a few seconds on graphs with millions of vertices, with an index size of only a few hundred megabytes. The main challenge is that these advanced indexing techniques, i.e., partial indexes with guided graph traversal, are mainly designed for static graphs. The only approaches that can deal with graph updates are DAGGER [START_REF] Hilmi Yildirim | DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs[END_REF], IP [START_REF] Wei | Reachability Querying: An Independent Permutation Labeling Approach[END_REF], and DBL [START_REF] Lyu | DBL: Efficient Reachability Queries on Dynamic Graphs[END_REF]. However, the dynamic approach adopted in IP is based on DAGGER that could be no faster than BFS [START_REF] Diwen Zhu | Reachability Queries on Large Dynamic Graphs: A Total Order Approach[END_REF], and DBL can only support insertion-only graphs. Having partial indexes, which can process queries and deal with graph updates of insertions and deletions efficiently, is highly interesting.

A partial index only records partially reachability information in an input graph, so that they can scale to large graphs. 𝑄 𝑟 (𝑠, 𝑡) can be processed by performing online traversal that can be guided by using index lookups in partial indexes. Let 𝑣 be a current frontier vertex during the online traversal from 𝑠. In a partial index without false positives, if the index lookup for evaluating the reachability from 𝑣 to 𝑡 returns true, the online traversal can immediately terminate. In the case of a partial index without false negatives, the online traversal does not need to visit the outgoing neighbours of 𝑣 if the index lookup for evaluating the reachability from 𝑣 to 𝑡 returns false. From the evolution of plain reachability indexing techniques over the last three decades, we observe that partial indexes play an important role in making reachability indexes scale to large graphs, i.e., obtaining efficient query processing with realistic indexing cost. More importantly, partial indexes that do not have false negatives in query results using only index lookups (e.g., GRAIL, Ferrari, IP, and BFL) have demonstrable advantages. That is because if a vertex 𝑡 is not reachable from 𝑠, 𝑄 𝑟 (𝑠, 𝑡) can stop immediately, and in real-world graphs there will be many such vertices 𝑠.

According to Table 2, the only partial index for path-constrained reachability queries is the landmark index. However, landmark index is a partial index without false positives, which means that if the index returns false, the online traversal for query processing has to continue. As noted above, in real-world graphs, it is likely that there will be many vertices that might not be reachable from a given source vertex, and, therefore, it would be interesting to have a partial index without false negatives for path-constrained reachability queries. Equally importantly, we observe that the index construction cost of path-constrained reachability indexes is high and takes hours of indexing for graphs with millions of vertices [START_REF] Chen | DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs[END_REF][START_REF] Chen | Graph Indexing for Efficient Evaluation of Label-constrained Reachability Queries[END_REF][START_REF] Peng | Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond[END_REF][START_REF] Zhang | A Reachability Index for Recursive Label-Concatenated Graph Queries[END_REF]. This also calls for the design of partial indexes without false negatives. Analogously, practical issues of updates on dynamic graphs should be also taken into account for the integration into GDBMSs.

Another important challenge for path-constrained reachability indexes is that the existing solutions can only deal with a specific type of path constraint 𝛼, as shown in Table 2. However, real-world query log analysis [START_REF] Bonifati | Navigating the Maze of Wikidata Query Logs[END_REF] has shown that practical path constraints have many more types. It will be of great interest to have one indexing technique for general path constraints and thus the entire fragment of regular path queries [START_REF] Bonifati | Querying Graphs[END_REF].

Finally, the parallel computation of indexes (e.g., parallel 2-hop indexing [START_REF] Jin | Parallelizing Pruned Landmark Labeling: Dealing with Dependencies in Graph Algorithms[END_REF]) is also worth exploring.

Figure 1 :

 1 Figure 1: A plain graph (a) and an edge-labeled graph (b).

Table 2 :

 2 A review of path-constrained reachability indexes.

	Indexing Technique Framework Path Constraint Index type Input Dynamic
	Jin et al. [21]	Tree cover	Alternation	Complete	General	No
	Chen et al. [12]	Tree cover	Alternation	Complete	General	No
	Zou et al. [48, 56]	GTC	Alternation	Complete	General	Yes
	Landmark index [44]	GTC	Alternation	Partial	General	No
	P2H+ [33]	2-Hop	Alternation	Complete	General	No
	DLCR [10]	2-Hop	Alternation	Complete	General	Yes
	RLC index [52]	2-Hop	Concatenation	Complete	General	No


Comparing pH sensors IrOx and ISE (PH-01)

IrOx shows higher sensitivity and stability than ISE under the same conditions.

  R&D contracts Address societal needs in the fields of biology, healthcare, environment and security Create & develop innovative solutions for our industrial partners Artificial Intelligence and new Technologies for Tracking key indicator Traits in animal facing challenges of the agro-ecological Transition Source: Website of the Chamber of Agriculture for Animal Welfare (France) To be proactive for animal welfare (AW), we need to understand their point of view and needs Project goal: Increasing research-based capacities to quantify and characterize AW in the agro-ecological (AE) perspective and revising farming practices and decision-making tools by considering interactions between the animal and its environment  WP1: Analysis of interactions between the animal and its environment, using artificial intelligence  WP2: Monitoring physiology for acute and mid-term adaptation to stress factors  WP3: Determining the impact of agro-ecological transition on animal welfare  WP4: Dissemination CEA Objective: Coupling hydrogel microneedles (MN) to electrochemical sensors in order to develop minimally invasive connected devices for real-time monitoring in animals Interstitial Fluid (ISF) A.Aubert / CEA 7 WAIT4: Welfare Artificial Intelligence and new Technologies for Tracking key indicator Traits in animal facing challenges of the agro-ecological Transition WP2-New sensors of animal physiology  Hydrogel formulation  MN design  Morphological and structural characterization  Hydrogel formulation  MN design  Morphological and structural characterization  Formulation ISE (Na + , pH) and REF  Electrodes Design  Calibration test on simple model solutions, complex and ISF sampling  Formulation ISE (Na + , pH) and REF  Electrodes Design  Calibration test on simple model solutions, complex and ISF sampling  Set up communication protocol  collect data  send data  Set up communication protocol  collect data  Artificial Intelligence and new Technologies for Tracking key indicator Traits in animal facing challenges of the agro-ecological Transition electrochemical platform for monitoring physiological variables of interest like potassium and pH in animals Interstitial Fluid (ISF) ISF is a complex fuid containing amino acids, sugars, fatty acids, coenzymes, hormones, neurotransmitters, salts and waste products from the cells. ISF is present between cells and represents around 80% of extracellular fluids (ECF). ■ pH: variation between 7.35 and 7.50 in blood (in cows) Desired sensitivity range 0.03 to 0.05 pH point ■ ∆E over full range < 9 mV ■ Sensitivity range < 3 mV ■ Na + -cow and sow in plasma: 130-145 mmol/L Desired sensitivity range < 4-5 mmol/L ■ ∆E over full range < 3 mV ■ Sensitivity range < 1 mV WAIT4: Physiological variables of interest 10 Very low values at the limit of possible detection Na + and pH: concentration range (sensitivity & accuracy) Electrochemical sensors WAIT4: Electrochemical Sensors Multi-parameter electrochemical platform for monitoring physiological variables of interest like sodium, potassium and pH in animals Interstitial Fluid (ISF)

  17

  electrochemical platform validation These are the first promising results of potentiometric electrochemical detection of Na+, pH and K+ in artificial ISFsIn this study, we demonstrate that applying our design and our fabrication strategy of this platform enables the detection of multiple parameters involved in the animal stress 20 Ionophore Na IV Ionophore K IIIFuture perspectives / challengesThe next step will be the integration of electrochemical platform with the micro-needle patches to perform measurements of physiological parameters minimally invasive for the animals This work was supported by a French government grant managed by the Agence Nationale de la Recherche under the France 2030 program,

https://bien-etre-animal.chambres-agriculture.fr