12 citations · 18 across the 8 of their papers we have counts for
10 papers
Graphs with Bounded Push-Pop Walk Orderings
Antoine Amarilli, Claire David, Nadime Francis +3
Consider a directed graph G and the (generally infinite) set Walks(G) of the walks in that graph. We are interested in ordering Walks(G) as w1, w2,... in a way that ensures that ea…
Expressive Power of Property Graph Constraint Languages
Stefania Dumbrava, Nadime Francis, Victor Marsault +1
We present the first principled and systematic study of the expressive power of property graph constraint languages, focused on the recent PG-Keys language, set to inform the upcom…
Gray Codes With Constant Delay and Constant Auxiliary Space
Antoine Amarilli, Claire David, Nadime Francis +3
We give the first two algorithms to enumerate all binary words of (like Gray codes) while ensuring that the delay and the auxiliary space is independent from ,…
Distinct Shortest Walk Enumeration for RPQs
Claire David, Nadime Francis, Victor Marsault
We consider the Distinct Shortest Walks problem. Given two vertices and of a graph database and a regular path query, enumerate all walks of minimal length fr…
Enumerating regular languages in radix order : Revisiting the Ackerman-Shallit algorithm
Nadime Francis, Victor Marsault
We consider the problem of enumerating a regular language in radix order, or more precisely, the equivalent problem of enumerating all words in of a given length in lexicog…
Run-Based Semantics for RPQs
Claire David, Victor Marsault, Nadime Francis
The formalism of RPQs (regular path queries) is an important building block of most query languages for graph databases. RPQs are generally evaluated under homomorphism semantics;…
GPC: A Pattern Calculus for Property Graphs
Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo +7
The development of practical query languages for graph databases runs well ahead of the underlying theory. The ISO committee in charge of database query languages is currently deve…
Graph Pattern Matching in GQL and SQL/PGQ
Alin Deutsch, Nadime Francis, Alastair Green +15
As graph databases become widespread, JTC1 -- the committee in joint charge of information technology standards for the International Organization for Standardization (ISO), and In…
Formal Semantics of the Language Cypher
Nadime Francis, Alastair Green, Paolo Guagliardo +8
Cypher is a query language for property graphs. It was originally designed and implemented as part of the Neo4j graph database, and it is currently used in a growing number of comm…
Datalog Rewritings of Regular Path Queries using Views
Nadime Francis, Luc Segoufin, Cristina Sirangelo
We consider query answering using views on graph databases, i.e. databases structured as edge-labeled graphs. We mainly consider views and queries specified by Regular Path Queries…